KLS Conjecture Proof Explained AI Agents Microsoft Research: 31-Year-Old Maths Problem Solved in Simple Words

Image: Unsplash (free Unsplash licence) — Illustrative image: mathematics formulas on a board

TL;DR — The kls conjecture proof explained ai agents microsoft research story in one line: Microsoft Research's Xinzhi Zhang and collaborator Zhao Song say they have proved the 31-year-old KLS conjecture with a fixed O(1) bound, after AI agents explored 100+ approaches under human direction — a preprint claim, not yet peer-reviewed.

📌 KEY HIGHLIGHTS

• Announced 21 October 2026: the Kannan–Lovász–Simonovits (KLS) conjecture, open since 1995, is claimed proved in a ~140-page arXiv paper, "An O(1) Bound for the KLS Constant".
• The result: for a broad class of high-dimensional distributions, the best flat cut is always within a fixed, universal constant of the best cut of any shape — the bound no longer grows with the number of dimensions.
• How it was found: AI agents explored more than 100 candidate approaches while the researchers pruned, redirected and assembled the final argument. Unguided AI attempts at a similar budget fell short.
• Strong informal validation followed fast: two further proofs appeared the same day the complete proof was posted, and a Lean 4 machine-checked formalisation was released afterwards.
• Honest status: this is a preprint, not yet peer-reviewed. Treat it as a major claimed breakthrough with unusually strong early checks — not a textbook fact yet.

What happened?

Some maths problems are famous because they are useful, and KLS is one of them. Proposed in 1995 by Ravi Kannan, László Lovász and Miklós Simonovits, it asks a deceptively simple question about cutting shapes in many dimensions: if you split a well-behaved high-dimensional distribution into two equal halves, is the best flat cut — a single straight hyperplane slice — always nearly as good as the best cut of any curved shape? KLS says yes, and that the gap between the two never exceeds one fixed constant, however many dimensions you add.

That matters far beyond geometry, because those cuts are bottlenecks. How narrow the tightest cut is governs how quickly a random walk can wander through a distribution — and random-walk sampling sits underneath statistics, volume computation, convex optimisation and a large family of randomised algorithms. The Simons Institute has called KLS "one of the most important open problems in convex geometry", and Quanta Magazine wrote that it "lies at the heart of many questions in statistics and computer science." For 31 years, researchers chipped the bound down step by step; as recently as July 2026, the best known result, by Brayden Letwin, still let it grow slowly with dimension. The new paper claims to remove that growth entirely.

KLS conjecture proof explained AI agents Microsoft Research — before vs after

Question	Before (up to July 2026)	Zhang & Song (Oct 2026, claimed)
How does the KLS bound behave as dimensions grow?	Grew slowly — best known O(log1/4 n)	Fixed O(1) — a universal constant, independent of dimension
Status of the conjecture	Open since 1995; widely believed, used as an assumption	Claimed proved; results that assumed KLS could become unconditional
How the proof was found	Decades of human progress: stochastic localisation and successors	Human-directed AI agents explored 100+ approaches; a new criterion, applied recursively twice over
Verification so far	Peer-reviewed incremental results	Two same-day independent proofs + Lean 4 formalisation; journal peer review still pending

The proof's engine, in plain words, is recursion. The AI-assisted search produced a new mathematical criterion. The authors realised each improved bound could be fed back into the same argument to produce a tighter one: the 1 October version cut the dimension dependence down to the iterated logarithm — a function that grows extraordinarily slowly, but still grows. The decisive human idea, borrowed from their earlier work on fast linear-programming algorithms, was to repeat the entire recursive refinement a second time and show the small errors at each stage shrink fast enough that their total stays bounded. That finished the argument in the 4 October version. Microsoft is explicit about the division of labour: AI explored approaches, carried out detailed derivations, helped prepare the manuscript and ran internal proof checks; the researchers chose the direction, selected the promising ideas, assembled the proof and verified it. If you enjoy research explained this way, our new algorithm to simulate quantum computers on normal computers explained post covers Edinburgh's recent breakthrough, and our NVIDIA Nemotron 3.5 open models explained post shows the other side of AI research this week.

Image: Unsplash (free Unsplash licence) — Illustrative image: abstract geometric shapes

Why it matters for algorithms and sampling

A proved KLS does not make any app faster tomorrow — no library ships a new sampler because of this paper. What it changes is the ground theorists stand on. A wide range of results in convex geometry, probability and theoretical computer science were proved "assuming KLS"; those can now be stated unconditionally, and algorithm designers get a firmer guarantee that high-dimensional spaces do not hide bottlenecks that grow without bound as dimensions increase. Just as significant is the method: this is one of the clearest documented cases of AI agents contributing to a genuine open-problem breakthrough — but only inside a tight human loop of pruning and judgement, with the unguided control experiment failing. That is a more useful lesson for research teams than either "AI solved maths" or "AI did nothing".

Should you care?

✅ Care if you work on sampling, optimisation, statistics or AI research — ⏳ everyone else can simply enjoy a 31-year-old puzzle falling. The caveats are real: 140-page proofs can hide errors, and peer review has not happened yet. But two independent same-day proofs building on the key criterion, plus a Lean 4 formalisation, are about the strongest early signals a preprint can get. Watch for the shortened, Lean-verified version the authors say will follow final review.

FAQs

What is the KLS conjecture?
The Kannan–Lovász–Simonovits conjecture, proposed in 1995, says that for isotropic log-concave probability distributions — a broad, well-behaved class used across statistics and computer science — the best flat (hyperplane) cut dividing the distribution is always within a fixed universal constant of the best cut of any shape, no matter how many dimensions there are. Because cuts act as bottlenecks, the conjecture underpins how fast random walks can sample from such distributions.

Has the KLS conjecture been proved?
Xinzhi Zhang of Microsoft Research and collaborator Zhao Song posted a complete claimed proof on arXiv in October 2026 ("An O(1) Bound for the KLS Constant", first submitted 1 October, revised 4 October), announced by Microsoft Research on 21 October. It has not yet been peer-reviewed, but two further proofs appeared the same day building on its key criterion, and a Lean 4 formalisation followed — strong informal validation while formal review continues.

How did AI agents help prove the KLS conjecture?
The authors used a human-directed agentic search: multiple AI agents explored variations of an idea in parallel — more than 100 research trajectories in total, many involving long higher-order tensor calculations — while a researcher reviewed intermediate results, pruned weak directions and passed the most promising one to the next round. That search surfaced the new criterion at the heart of the proof. Notably, repeated unguided attempts with leading AI models at roughly the same token budget fell short.

Why does the KLS conjecture matter for algorithms and sampling?
The geometry of cuts controls how quickly a random walk can explore a distribution, and random-walk sampling underlies volume computation, integration, convex optimisation and many randomised algorithms in statistics and machine learning. A dimension-free KLS bound means those methods rest on a proved guarantee rather than a 31-year-old assumption, and that high-dimensional spaces are better behaved than was previously known.

TAKEAWAY
A fixed O(1) bound ends the 31-year KLS chase on paper — and the way it was found, humans steering AI agents through 100+ dead ends, may be the template for the next one.
Follow World Tech on TechByCountry for the next hourly update.

Sources: Microsoft Research — Solving a 31-year-old grand challenge in mathematics: the KLS conjecture (21 Oct 2026, primary) • Unite.AI — Microsoft Researcher and Collaborator Prove 31-Year-Old KLS Conjecture (21 Oct 2026). Checked 22 Oct 2026.