Microsoft Research reports proof of the 31-year-old KLS conjecture with human-directed AI
Microsoft Research says it has resolved the Kannan-Lovász-Simonovits (KLS) conjecture, a problem proposed in 1995 and described as one of the central open questions in high-dimensional geometry. The conjecture asks whether, for a broad class of high-dimensional probability distributions (log-concave ones), the best flat or hyperplane cut is always nearly as effective as the best cut of any shape. KLS predicts that the two differ by no more than a universal constant, regardless of the number of dimensions. Because the geometry of these cuts governs how quickly random walks can explore a distribution, the conjecture also plays a central role in the theory of high-dimensional sampling.
Two researchers, including Xinzhi Zhang from the Machine Learning and Optimization group at Microsoft Research, have now proved it, showing the relationship holds with a fixed bound however many dimensions a shape has. The best previous result, established in July 2026, still let that bound grow slowly as dimensions increased.
The route to the proof had three steps. The authors first set out to sharpen the July 2026 result. Working with AI agents in a structured, human-directed process, they explored more than 100 candidate approaches, many involving lengthy calculations with higher-order tensors. That produced a new mathematical criterion, which became the foundation of the final proof. They then found the criterion could be applied recursively: each improved bound can be fed back into the same argument to give a tighter one. In the October 1, 2026 version of the paper, this cut the dependence on dimension to the iterated logarithm, a function that grows extremely slowly but still grows, so the conjecture was not yet fully resolved. The last step was to repeat the whole recursive refinement rather than apply it once, an idea inspired by the authors' earlier work on fast algorithms for linear programming. They proved that the small errors introduced at each stage shrink fast enough that their total stays bounded by a universal constant independent of dimension. That removed the dimension dependence and completed the proof in the October 4, 2026 version of the paper.
The post says the recursive method, its repeated application, and the proof that the accumulated errors stay bounded are the researchers' original contributions. AI tools helped explore candidate approaches, carry out detailed derivations, prepare the manuscript and perform internal proof checks. The researchers set the direction, chose the promising ideas, assembled the argument and verified the proof.
The post also reports outside confirmation. On the same day the authors posted their complete proof, a separate group of leading experts posted a full proof developed in parallel. It built on the first version of the Microsoft paper, calling its criterion "the crucial step in the proof." A third proof, appearing separately that day, relies on a closely related idea. A Lean 4 formalization was later released, combining the key criterion from the first Microsoft paper with additional research. The authors have also shortened their proof and checked the streamlined version in Lean; they plan to release both after final review.
On the AI process itself, the agents ran in parallel on variations of an idea, and a researcher examined intermediate results, dropped unpromising directions and passed the best one to the next round. Roughly one hundred research trajectories were explored before the key breakthrough emerged. In a separate track, repeated unguided attempts by several leading AI models, with roughly the same total token budget, fell short of the goal. The post concludes that success depended on both the AI systems' capabilities and the researchers' mathematical judgment, and that many results which assumed the conjecture can now be stated unconditionally.
Key facts
- Microsoft Research reports that two researchers, including Xinzhi Zhang, proved the KLS conjecture (proposed in 1995): the best flat cut and the best cut of any shape differ by at most a universal constant, in any dimension.
- The best earlier result, from July 2026, still allowed the bound to grow slowly with dimension. The October 1, 2026 paper version cut this to the iterated logarithm; the October 4, 2026 version removed it entirely.
- AI agents explored more than 100 candidate approaches under human pruning, and roughly one hundred trajectories preceded the key breakthrough. Unguided attempts by several leading AI models with a similar token budget fell short.
- A separate expert group posted a full proof the same day, building on the first Microsoft paper's criterion; a third proof and a Lean 4 formalization followed.
- The authors say they have shortened the proof and verified the streamlined version in Lean, and plan to release both after final review.
Why it matters
KLS has stood as an open problem since 1995, and the post cites others on its standing: the Mathematical Sciences Research Institute called it "a central open problem in high-dimensional convex geometry," and the Simons Institute called it one of the most important open problems in convex geometry. Ronen Eldan noted its broad implications for high-dimensional convex and computational geometry in the 2022 International Congress of Mathematicians proceedings. Quanta Magazine wrote that it "lies at the heart of many questions in statistics and computer science." A dimension-free bound means the obstacles to navigating high-dimensional spaces do not grow without limit as dimensions increase. The post also presents the work as an example of AI directed by researchers rather than left to solve a problem in one end-to-end run.
Who it affects
Mathematicians and theoretical computer scientists working in convex geometry, probability and high-dimensional sampling are the direct audience. The post says a wide range of results that previously assumed the conjecture can now be stated unconditionally, and ties the topic to statistics, optimization and the efficiency of randomized algorithms. It also speaks to anyone weighing how to use AI agents in research: the account is of a researcher steering many parallel agents, not handing over the problem.
How to use it
This is a research result, not a product. The practical takeaway the post offers is the process: run multiple agents in parallel on variations of an idea, have a researcher inspect intermediate results, remove unpromising directions and pass the best one to the next round. The authors link the paper, the parallel proof, the third proof and the Lean 4 formalization from the post. They say they are simplifying the proof and extending its formal verification so that other mathematicians and computer scientists can examine it and build on it.
How solid is it
The claim comes from Microsoft Research's own blog, so the account of the AI process is the authors' self-report. The mathematical claim has several outside supports according to the post: a parallel full proof by a separate group of leading experts, a third proof relying on a closely related idea, and a Lean 4 formalization of the key criterion combined with additional research. The source does not say the proof has been peer-reviewed or accepted by a journal. The authors' own shortened proof and its Lean check are not yet released and await final review. The names of the independent group and of the authors of the third proof and the formalization are not given in the text.
Risks and caveats
No AI model, vendor or product names are given for the agents, and the total token budget is not stated, only that the unguided comparison used roughly the same budget. That comparison is a single sentence, so the post gives little to judge how well it was controlled. The source does not give the explicit constant or numerical value of the bound. The authors say the success depended on both the AI systems and the researchers' mathematical judgment; the recursive method and the bounded-error argument are credited to the researchers, not the AI. Several of the independent confirmations build on the first Microsoft paper's criterion, so they are not wholly separate from it.
“a central open problem in high-dimensional convex geometry.”
— Mathematical Sciences Research Institute (MSRI), 2017-18 Annual Report