Felix Laurent
Microsoft Research said on Oct 21 that its senior researcher Xinzhi Zhang and independent researcher Zhao Song have proved the Kannan–Lovász–Simonovits (KLS) conjecture, a problem in high-dimensional geometry open since 1995. On the way, AI agents explored roughly 100 research trajectories while a researcher cut weak branches between rounds. We read the Microsoft post, the paper and the two independent proofs to separate what the models did from what the authors did.
What Microsoft announced
The result sits in the paper "An O(1) bound for the KLS constant" (arXiv 2610.01447). Version 1 went up on Oct 1, version 2 – the one that closes the conjecture – on Oct 4. Microsoft's blog post, written by Zhang, followed on Oct 21, and @rohanpaul_ai's post on X pushed it into the AI feed on Oct 22.
The claim: the KLS constant is bounded by a universal constant in every dimension. The best result before it was Brayden Letwin's paper from July 2026, which still let the bound grow with dimension as (log n)^1/4.
What the conjecture says
Take a convex shape – or, more generally, a log-concave probability distribution – in n dimensions and cut it into two halves of equal volume. KLS says the best flat cut is never worse than the best cut of any shape by more than a fixed factor, and that factor does not grow with n. Microsoft's illustration on a regular tetrahedron: the flat cut has area 0.25, the smallest curved cut ~0.2173.
Why it matters outside pure math: the narrowest bottleneck of a distribution decides how fast a random walk can explore it. That ties KLS to sampling, volume computation, log-concave integration and convex optimization. Results that assumed KLS can now be stated without that assumption.
How the bound moved, per the paper's own table:
| Year | Authors | Upper bound on the KLS constant |
|---|---|---|
| 1995 | Kannan, Lovász, Simonovits | √n |
| 2013 | Eldan | n^1/3 · √log n |
| 2017/2024 | Lee, Vempala | n^1/4 |
| 2021 | Chen | First subpolynomial bound |
| 2022 | Klartag, Lehec | log^5 n |
| 2023 | Klartag | √log n |
| 2026 | Letwin | log^1/4 n |
| 2026 | Song, Zhang | O(1) – a universal constant |
In 31 years the bound went from √n to a constant that does not depend on dimension.
How the proof was built
The authors started by trying to sharpen Letwin's July bound. Working with AI agents, they explored more than 100 candidate approaches, many of them long calculations with higher-order tensors. That search produced a new criterion – a link between variance bounds for polynomials of every degree and the full Poincaré constant – which every later proof relies on.
The authors then found the criterion can be applied recursively: each improved bound feeds back into the same argument. The Oct 1 version used this to cut the dimension dependence to an iterated logarithm (log-star) – a function that grows extremely slowly, but still grows. The Oct 4 version repeats the whole refinement and proves the errors added at each stage shrink fast enough to sum to a constant. Microsoft says the idea came from the authors' earlier work on fast linear-programming algorithms.
What the AI did, and what it didn't
Microsoft draws the line explicitly:
| Task | Who | Source |
|---|---|---|
| Exploring candidate approaches (~100 trajectories) | AI agents, pruned by a researcher between rounds | Microsoft blog |
| Detailed derivations | AI | Microsoft blog |
| Preparing the manuscript | AI | Microsoft blog |
| Internal proof checks | AI | Microsoft blog |
| The recursive method and its repeated application | The authors | Microsoft blog |
| The proof that accumulated errors stay bounded | The authors | Microsoft blog |
| Choosing direction, assembling the argument, verifying | The authors | Microsoft blog |
| Which models were used | Not published | – |
The workflow: several agents explored variations of one idea in parallel, a researcher read the intermediate results, dropped the weak directions and passed the best one to the next round.
The control run
In a separate track, the authors ran several leading AI models unguided on the same problem, with roughly the same total token budget as the guided search. Microsoft says that effort fell short. The same compute spent as one end-to-end run did not reach the result; the human-pruned search did.
How the result is being checked
Two independent proofs and a machine-checked version followed within days:
| Work | Authors | Date (arXiv) | Relation to Song–Zhang |
|---|---|---|---|
| An O(1) bound for the KLS constant | Song, Zhang | Oct 1 (v1), Oct 4 (v2) | The proof |
| Presenting a proof of the KLS conjecture | Bizeul, Klartag, Lehec | Oct 4 | Independent proof, 32 pages; calls the Song–Zhang criterion "the crucial step" |
| A dimension-free bound on the Poincaré constant | Balasubramanian, Kasiviswanathan | Oct 6 | Separate variational proof with an explicit constant (Poincaré ≤ 25); Microsoft says it relies on a closely related idea |
| KLS500 | Lean 4 formalization on GitHub | After Oct 4 | Machine-checked proof combining the Song–Zhang criterion with other work |
Worth flagging: Microsoft's post says the third proof appeared on the same day as the full Song–Zhang proof; arXiv lists it as submitted on Oct 6. The Bizeul–Klartag–Lehec paper also carries a note that it contains a paragraph on AI use.
Klartag and Lehec are the authors of two of the earlier bounds in the table above – the confirmation comes from people who held the record before.
What the X post gets right
The numbers in @rohanpaul_ai's post match the sources: 31 years, ~100 explored paths, AI on derivations, manuscript and internal checks, the recursive method credited to the people. One line needs a correction: "Microsoft researcher proved" leaves out the second author – the paper lists Zhao Song as an independent researcher, not a Microsoft employee.
What is still missing
Three parts of the story are not public yet:
- The models: neither the blog nor the paper's abstract names which AI systems ran the search or the control run.
- The short version: the authors say they have shortened the proof and verified it in Lean, and will release both after final review.
- Peer review: all three proofs are arXiv preprints; none has gone through a journal yet.
Until the models are named, the share of the work done by AI can be read only from Microsoft's own description.
Sources
- Microsoft Research blog, Oct 21, 2026
- Song, Zhang – An O(1) bound for the KLS constant
- Bizeul, Klartag, Lehec – Presenting a proof of the KLS conjecture
- Balasubramanian, Kasiviswanathan – A dimension-free bound on the Poincaré constant
- KLS500 Lean 4 formalization
- Letwin – The KLS constant is O(log^1/4 n)
