Microsoft Research mathematicians prove the 31-year-old KLS conjecture with AI agent help

What the researchers announced

Microsoft Research published an account on 21 October 2026 of a proof of the Kannan, Lovász and Simonovits (KLS) conjecture, an open problem in high-dimensional geometry since 1995. The post is by senior researcher Xinzhi Zhang of the Machine Learning and Optimization group and names Zhao Song as co-author.

The conjecture asks whether, for a broad class of high-dimensional probability distributions, the best flat cut is nearly as good as the best cut of any shape, differing by at most a universal constant whatever the dimension. That question governs how fast random walks explore a distribution, which is central to sampling algorithms. The previous best result, from July 2026, still had a bound that grew slowly with dimension. The authors' version of 1 October cut the dependence to an iterated logarithm, and their version of 4 October removed it. The method applies a new criterion recursively and then repeats the whole refinement, an idea the authors say came from their earlier work on fast linear programming algorithms. The post cites the Simons Institute calling KLS "one of the most important open problems in convex geometry".

How AI was used

The authors ran an agentic search: several AI agents explored variations in parallel while the researchers pruned unpromising directions. The post says roughly 100 research trajectories were explored. AI tools also helped with derivations, manuscript preparation and internal proof checks. The authors say the recursive method, its repetition and the error-control proof are their own contributions, and that the researchers chose the direction, assembled the final argument and verified it. Repeated unguided attempts by several leading AI models, with about the same token budget, fell short.

How solid the result is

A separate group posted a full proof on arXiv on the same day as the complete Microsoft version, building on the first Microsoft paper and calling its criterion "the crucial step in the proof". A third proof posted that day uses a closely related idea. A Lean 4 formalisation combining the key criterion with other work was released later, and the authors say they verified a streamlined version in Lean that they will release after review. The papers are preprints, and the blog does not mention peer review. For another example of AI-assisted maths this autumn, see Anthropic's Lean proof of Fermat's Last Theorem.

What to watch next

The next markers are journal acceptance, release of the authors' own Lean proof, and whether the new bound speeds up practical sampling algorithms. More research stories are under AI Research.

Questions people ask

What is the KLS conjecture?

A 1995 conjecture by Kannan, Lovász and Simonovits that, for a broad class of high-dimensional distributions, the best flat cut is within a universal constant of the best cut of any shape, regardless of dimension.

Did AI prove the KLS conjecture?

Not on its own. The authors used AI agents to explore about 100 research paths and help with derivations, but say they chose the direction, built the final argument and verified it. Unguided AI attempts fell short.

Has the proof been peer reviewed?

The blog post cites arXiv preprints and does not mention peer review. An independent proof and a Lean 4 formalisation have been posted.

Sources

1. Solving a 31-year-old grand challenge in mathematics: the KLS conjecture (Microsoft Research, 21 Oct 2026)
2. An O(1) Bound for the KLS Constant (arXiv, 4 Oct 2026)