The Pulse
AI-Assisted Proof Resolves 31-Year-Old KLS Conjecture
A paper by Zhao Song and Xinzhi Zhang proves a dimension-free bound for the Kannan–Lovász–Simonovits conjecture, a problem proposed in 1995. The researchers say AI agents helped explore and check ideas, while human mathematicians directed a
AI.info Team · Written with AI · fact-checked ·
More than 100 candidate approaches and roughly one hundred research trajectories went into a proof of the Kannan–Lovász–Simonovits conjecture, according to a Microsoft Research account published October 21, 2026. The result, by Xinzhi Zhang, a senior researcher at Microsoft Research, and Zhao Song, an independent researcher, establishes a bound that does not grow with the dimension of the space. The researchers’ account says AI agents helped explore and check ideas, while human mathematical judgment set the direction and assembled the proof.
A bound that no longer grows with dimension
Proposed in 1995, the KLS conjecture concerns the geometry of isotropic log-concave probability distributions, a broad family of distributions used in probability and high-dimensional geometry. In simplified terms, it predicts that a flat cut through such a distribution can capture its narrowest bottlenecks nearly as well as a cut of any shape, with a fixed factor that does not depend on the number of dimensions.
That property matters for random walks used to explore high-dimensional distributions. The paper says bounds on the KLS constant affect conductance and mixing times, and therefore the complexity of sampling, volume computation and integration. The conjecture also connects to algorithms in convex optimization.
Song and Zhang state their result as a universal bound on the Poincaré constant for every isotropic log-concave measure, including measures without smooth densities or bounded support. The authors, independent researcher Zhao Song and Microsoft Research researcher Xinzhi Zhang, write:
“The constant is independent of the dimension, the measure, and the test function.”
“An O(1) Bound for the KLS Constant,” by Zhao Song and Xinzhi Zhang
How repeated refinement closed the gap
The proof grew from a sequence of improvements. The researchers first developed a criterion that could be applied recursively: each better bound became an input to the next round. An October 1 version reduced the remaining dependence on dimension to an iterated logarithm, which grows extremely slowly but still is not constant.
The final move was to repeat the whole refinement rather than stop after one application. The authors say the approach drew on their earlier work on fast linear-programming algorithms. Their analysis shows that the small losses introduced by successive rounds shrink quickly enough for their total to remain bounded, eliminating the dependence on dimension.
Microsoft says AI agents explored candidate approaches, including lengthy higher-order tensor calculations, and helped with derivations, manuscript preparation and internal checks. Researchers examined intermediate results, discarded unproductive lines and steered promising ones into the next round. In a separate effort using roughly the same total token budget, unguided attempts by several leading AI models did not solve the problem.
Separate proofs provide another check
The claim is accompanied by work from other mathematicians. Pierre Bizeul, Boaz Klartag and Joseph Lehec posted a separate proof on October 4, built in part on a criterion introduced by Song and Zhang. Their paper calls that criterion “the crucial step in the proof.” Their paper on arXiv A third paper, by Krishnakumar Balasubramanian and Shiva Kasiviswanathan, presents a deterministic argument and gives an explicit upper bound of 25 for the Poincaré constant. Their paper on arXiv
A Lean 4 formalization of the conjecture is also available in a public repository, which describes a dimension-free Poincaré bound of at most 500. The KLS500 repository Formal verification checks that a proof follows from its encoded definitions and steps; it does not by itself settle questions about how the mathematics should be interpreted or whether the formalized argument captures the intended result. Microsoft says Zhang and Song have also shortened their proof and checked the streamlined version in Lean, but plan to release it after final review.
The next test is scrutiny of the full proof
The parallel proofs and formalization give mathematicians more than one route to inspect.
The practical significance is mathematical rather than an immediate change to software: results that previously assumed KLS can now be pursued on the basis of a proof, if the argument withstands further examination.
The proof’s central idea is a repeated refinement whose accumulated error stays bounded. Whether the shortened, Lean-checked version makes that argument easier for other specialists to audit depends on the release Zhang and Song say they are preparing.