Microsoft Researchers Resolve 31-Year-Old KLS Conjecture With Human-Directed AI

What the KLS conjecture asks

The KLS conjecture was proposed in 1995. It concerns a broad class of high-dimensional probability distributions and asks whether the best flat cut, known as a 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.

The question matters beyond pure geometry. According to Microsoft, the geometry of these cuts governs how quickly random walks can explore a distribution, so KLS plays a central role in the theory of high-dimensional sampling. The company says the result has implications for statistics, optimization, algorithms and computer science.

The field had long treated the problem as a priority. Microsoft cites the Mathematical Sciences Research Institute, which called it “a central open problem in high-dimensional convex geometry,” and Quanta Magazine, which wrote that KLS “lies at the heart of many questions in statistics and computer science.”

How the proof was built

Two researchers, including Xinzhi Zhang of the Machine Learning and Optimization group at Microsoft Research, proved that the relationship holds with a fixed bound in any number of dimensions. Before this work, the best known result, established in July 2026, allowed the bound to grow slowly as dimensions increased.

The authors first improved that result to make the bound more precise. 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. This produced a new mathematical criterion that became the foundation of the final proof.

They then found that the criterion could be applied recursively, with each improved bound fed back into the same argument to yield a tighter one. The October 1, 2026 version of the paper reduced the dependence on dimension to the iterated logarithm, a function that grows extremely slowly but still grows. 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 from each stage add up to a total bounded by a universal constant, which completed the proof in the October 4, 2026 version.

Independent confirmation and the role of AI

On the 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, which it called “the crucial step in the proof.” A third proof, relying on a closely related idea, appeared the same day. A Lean 4 formalization was released afterward, combining the key criterion from the first Microsoft paper with additional research. The authors have also shortened their proof and checked the shorter version in Lean, and plan to release both after final review.

Microsoft stresses that humans steered the AI. Multiple agents explored variations of an idea in parallel, while a researcher examined intermediate results, dropped unpromising directions and passed the best result to the next round. Roughly one hundred research trajectories were explored before the key breakthrough emerged. AI tools helped explore approaches, carry out derivations, prepare the manuscript and run internal proof checks, while the researchers chose the direction and verified the proof.

In a separate track, the authors made repeated unguided attempts to solve the problem with several leading AI models, using roughly the same total token budget. According to Microsoft, that effort fell short of the goal.

What it means

Microsoft says a wide range of results that previously assumed the conjecture can now be stated unconditionally, giving a stronger foundation for convex geometry, probability and theoretical computer science. The company presents the work as an example of guided human-AI collaboration that reinforces rather than replaces human insight.

The authors are now simplifying the proof and extending its formal verification so that other mathematicians and computer scientists can examine it and build on it more easily.