31-Year-Old KLS Conjecture Falls to Human-Directed AI Agents at Microsoft Research

A 31-Year-Old Problem, Solved by "Humans Directing AI"

On October 21, Microsoft Research published a blog post: senior researcher Xinzhi Zhang and collaborator Zhao Song have proved the Kannan–Lovász–Simonovits (KLS) conjecture — a central problem in high-dimensional geometry and probability, open since 1995. Their paper, An O(1) Bound for the KLS Constant, first appeared on arXiv on October 1; the revised October 4 version completed the proof.

First, what the KLS conjecture asks, in plain language. Picture a "convex body" in high-dimensional space (a high-dimensional watermelon). You want to cut it into two equal volumes. There are infinitely many ways to cut: a flat hyperplane slice, or a wiggly curved cut. KLS says: the best flat cut is never much worse than the best cut of any shape — the ratio of their areas is capped by a universal constant that does not grow with dimension. From 3 dimensions to 3,000, the conclusion holds.

Why does it matter? The geometry of such "cuts" governs how quickly random walks can explore a distribution — the theoretical foundation of high-dimensional sampling, statistics, and optimization algorithms. The Simons Institute called it "one of the most important open problems in convex geometry"; Quanta wrote that it "lies at the heart of many questions in statistics and computer science." Before this work, the best known result (July 2026) still let the bound grow slowly with dimension.

The Point Is Not How Smart the AI Is, but How Humans Directed It

The most worth-reading part of this story is not the math but the method. The Microsoft blog is unusually candid about the division of labor:

• What the AI agents did: in a structured, human-directed process, explored 100+ candidate approaches, carried out lengthy higher-order tensor calculations, and found a new mathematical criterion that became the foundation of the final proof; they also handled detailed derivations, manuscript preparation, and internal proof checks.
• What the humans did: set direction, pruned, assembled. The researchers examined intermediate results each round, killed unpromising directions, and passed the best candidates to the next round.
• The decisive move was human: discovering the new criterion could be applied recursively — each improved bound fed back into the same argument yields a tighter one; the October 1 version cut dimension dependence to the iterated logarithm (grows extraordinarily slowly, but still grows); the final step was to repeat the entire recursive refinement and prove the small errors introduced at each stage shrink fast enough that their total stays bounded by a universal constant. That idea came from the authors' earlier work on fast linear-programming algorithms — the AI didn't come up with it.

Microsoft also ran a control: on a separate track, several leading models tried to solve the same problem unguided, with roughly the same total token budget — and fell short. In the blog's words: "The eventual success depended on both the capabilities of the AI systems and the mathematical judgment of the researchers."

That is an important reminder for anyone who works with agents daily: the right way to use an agent is not "throw in a problem and wait for the answer" but "humans set direction, agents fan out the search, humans prune." The KLS proof is the textbook case of that workflow.

Validation at Full Strength

A big math result announced by a corporate lab risks sounding self-serving. This time the external corroboration is unusually strong:

• On the same day, a separate group of leading experts posted a full proof developed in parallel, building directly on the first version of the Microsoft paper and calling it "the crucial step in the proof";
• A third proof based on a closely related idea appeared the same day;
• A Lean 4 formalization combining the key criterion with machine checking was subsequently released;
• The authors also shortened their proof and verified the streamlined argument in Lean, to be released after final review.

Independent proofs are among mathematics' strongest forms of validation: they show the result doesn't rest on a single fragile chain of reasoning. The takeaway for vibe coders is practical: when you let an agent generate critical code or do important derivations, a "second independent path" is the cheapest insurance — redo it with a different model or a different prompt, and only trust it when both agree.

How This Differs from Previous "AI Math Breakthrough" Stories

Readers may recall the recent news of Terence Tao boycotting OpenAI's math proofs (we covered it). That dispute centered on whether AI-generated proofs are trustworthy or even count as mathematics. Microsoft's narrative is smarter: it never claims "AI proved the conjecture" — it claims a "human-directed agentic research process" did, and it cleanly separates the humans' original contributions (the recursive method, the bounded-error argument) from the AI's (search, computation, checking).

That "transparent division of labor" is exactly the template future human-AI collaboration reporting should follow: neither hyping the AI nor diminishing the human. The agents' role, in Microsoft's own words: "exploring mathematical possibilities while researchers evaluated, pruned, and redirected the search."

Three Takeaways for Vibe Coders

First, treat agents as "searchers," not "solvers." The KLS team had agents explore 100+ paths in parallel while humans judged. You can copy this pattern for refactors, bug hunts, and tech evaluations: fan out multiple approaches with the agent, you play referee — don't let it run one path into the ground.

Second, the key ideas still come from human cross-domain association. The "repeat the whole recursive refinement" insight came from linear programming — a seemingly unrelated old field. Agents excel at exhaustive search within a frame; they are bad at jumping out of it. Your domain knowledge and old experience are precisely the missing piece.

Third, pair agent output with a "second verifier." Mathematics used independent proofs plus Lean formalization; in engineering you can use: re-derive with a different model, reverse-verify with tests, human review on critical paths. The faster agents write code, the less skippable this verification becomes.

A 31-year-old conjecture fell not to a smarter model, but to a smarter human-machine division of labor. That sentence deserves a sticky note on every monitor of everyone who pair-programs with agents daily.

Why It Was Hard: 31 Years in Brief

The KLS conjecture is named for Ravi Kannan, László Lovász, and Santosh Vempala (1995). It asks a deceptively simple question: for "well-behaved" high-dimensional probability distributions (isotropic log-concave measures), how much worse is the best flat cut than the best cut of any shape?

Picture a 1,000-dimensional watermelon and its narrowest "waist" (bottleneck). You can hunt for it with a "flat knife" (hyperplane cut) or a wiggly one. KLS says the flat knife never does much worse — the ratio is capped by a dimension-independent universal constant. From 10 to 10,000 dimensions, the multiple doesn't budge.

Mathematicians care because "cuts" govern how fast random walks (MCMC sampling) explore a distribution. If KLS holds, a pile of high-dimensional sampling theorems get a unified foundation; many results were previously stated as "assuming KLS, then…". Those assumptions can now be dropped — in the blog's words, "a wide range of results that previously relied on the conjecture as an assumption can now be stated unconditionally."

Over 31 years the bound was squeezed from exponential to polynomial; in July 2026 Brayden Letwin's 21-page paper reached O(log1/4 n) — so close, yet the bound still grew with dimension. The 140-page October paper closed that last gap: O(1), dimension-free.

The Three Steps: Criterion, Recursion, Repeated Recursion

Step 1: find the criterion. Starting from improving the July result, AI agents explored 100+ candidate paths in a structured process — heavy higher-order tensor calculations, classic "machine-strong, human-weak" grunt work. The output: a new mathematical criterion, a verifiable condition implying better bounds. It became the foundation.

Step 2: discover recursion. The researchers noticed the new criterion could "feed itself": each improved bound fed back into the same argument yields a tighter one. The October 1 version cut dimension dependence to the iterated logarithm (log* n) — extraordinarily slow-growing, but still growing. Not fully resolved.

Step 3: repeat the whole recursion. The inspired move: don't apply the recursion once — repeat the entire recursive refinement, and prove the small errors introduced at each stage shrink fast enough that their total stays bounded by a universal constant. The idea came from the authors' earlier work on fast linear-programming algorithms — cross-domain association the AI didn't make. The October 4 revision completed the O(1) proof.

Note the elegant division: AI owned breadth (exhaustive exploration of 100+ paths); humans owned depth (recognizing the recursive structure, cross-domain leaps, the bounded-error argument). The blog stresses the recursive method, its repeated application, and the error-bounded proof are the researchers' original contributions — not politeness, but mathematical authorship ethics.

Lean 4 Formalization: Why Mathematicians Now Trust Machine Checking

An easy-to-miss supporting actor: Lean 4 formal verification — translating the proof into a machine-checkable formal language so a computer verifies each step. Someone formalized the paper's key criterion; the authors verified their streamlined proof in Lean too (release pending).

This matters almost as much as the proof. Proofs keep getting longer (140 pages); no human referee can check every line, and formal verification is becoming the "second pair of eyes." The analogy for vibe coders is direct: Lean is to proofs what tests are to code. You wouldn't merge untested code; mathematicians are starting to treat long unverified proofs the same way. AI accelerates this shift — formalization is exactly the "tedious but deterministic" work machines do well.

A Reproducible Playbook for Agentic Research

The proof's most valuable legacy may be the "human-directed agentic research process" itself. Translated into a playbook anyone can use:

• 1. Humans define the search space, not the theorem. Researchers didn't ask AI to "prove KLS" but to "explore paths improving the July result." Task granularity decides everything: too big and agents spray randomly, too small and there's no surprise.
• 2. Fan out in parallel, prune in batches. 100+ trajectories explored in parallel; humans reviewed intermediate results each round and killed dead ends. The same "plan → batch-generate → human picks" pattern from coding agents, applied to research.
• 3. Give agents grunt work. Tensor calculations, in-paper proof checks, manuscript prep — tedious, deterministic, verifiable. Save human brains for structure recognition and cross-domain association.
• 4. Keep an unguided control group. Microsoft ran a separate unguided track on the same token budget, proving "human direction" is real gain, not placebo. When evaluating your own agent workflows, keep a control: same budget, pure-agent vs human-in-the-loop — what's the delta?
• 5. Outputs must survive a "second verifier." Mathematics uses independent proofs plus Lean; yours can be another model, another test suite, one human review.

The boundary is clear too: this fits problems with "large search space, crisp verification" (proofs, bug hunts, architecture choices), not "fuzzy goals" (product taste, aesthetics). Knowing the boundary matters as much as knowing the method.

The Control Experiment: Same Budget, Unguided Fails

The blog's most honest passage covers "the other track": several leading models tried the same problem unguided, on roughly the same total token budget — and failed. It answers the question everyone asks: how much does "human direction" really add — gain or placebo?

Answer: the gain is real, and it's the difference between solved and unsolved. Same compute, directed solves it, undirected stalls. The bottleneck for current agents isn't compute or single-step smarts but search strategy: which 5 of 100 paths deserve depth, when to switch approaches, when to stop — meta-decisions humans still make better.

The direct corollary for daily agent users: don't just add budget to agents — add pruning. Rather than burning 10x tokens down a wrong path, checkpoint every 20 minutes and eyeball the intermediate output. The KLS team's "iterative human pruning" translates to: checkpoints plus human review, not fire-and-forget.

Why a Math Story Belongs on VibeFix

Three reasons. First, it's the hardest public evidence yet for human-AI collaboration — not a toy game or demo, but a 31-year-old conjecture. Every debate about "can agents do real work" gets first-hand evidence here.

Second, it defines the shape of agent products for the next two years. "Parallel exploration + human pruning + second verifier" is what next-gen coding agents should look like: not a black box that works in silence, but a checkable, prunable, verifiable collaboration surface. Codex, Claude Code, Copilot are all heading there; this story is their theoretical footnote.

Third, it answers vibe coders' deepest anxiety: "as agents get stronger, what am I for?" KLS answers: your job moves from writing to judging — which directions deserve pursuit, which results are trustworthy, when to stop. In this division of labor, human taste and judgment aren't replaced; they're promoted. Perhaps the least mathematical, most keepable line in this math story.

One timeline detail: the October 1 arXiv version was incomplete (only reached iterated logarithm); the October 4 revision completed O(1). The crucial three days were the landing of the human idea — "repeat the recursion, bound the errors." Agents paved the road for three months; humans walked the last mile in three days. That rhythm — machines to 99%, humans spotting the final 1% — is the normal shape of human-machine collaboration.

Microsoft Research official KLS diagram: flat cut vs smallest curved cut