Microsoft Researcher and Collaborator Prove 31-Year-Old KLS Conjecture

Microsoft Research announced on October 21, 2026 that Xinzhi Zhang, a senior researcher in its Machine Learning and Optimization group, and collaborator Zhao Song have proved the Kannan–Lovász–Simonovits conjecture, a 31-year-old problem in high-dimensional geometry and probability, using a human-directed agentic AI research process.

The Conjecture and the New Bound

The proof appears in the 140-page paper An O(1) Bound for the KLS Constant, credited to Zhao Song and Xinzhi Zhang, first submitted to arXiv on October 1, 2026 and revised on October 4, 2026, with Zhang as the submitting author. The abstract states that the authors prove the KLS constant ψ_n is bounded above by a universal constant C, resolving the conjecture, and that they also prove a universal bound on the Poincaré constant of every isotropic log-concave probability measure.

Formally, the conjecture, proposed in 1995, asks whether every isotropic log-concave probability measure on n-dimensional space has a Cheeger constant bounded below by a universal positive constant. In the Microsoft Research post’s plainer terms, it asks whether, for a broad class of high-dimensional probability distributions, the best flat or hyperplane cut is always nearly as effective as the best cut of any shape, with the two differing 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 plays a central role in the theory of high-dimensional sampling.

Before this work, the best known result was the 21-page paper The KLS constant is O(log^{1/4} n) by Brayden Letwin, submitted on July 27, 2026. It established that ψ_n is at most a constant times log^{1/4} n, a bound that the Microsoft Research post notes still grew slowly as the number of dimensions increased. The new work holds with a fixed bound that does not vary with dimension.

The conjecture’s standing was recognized well before its resolution. The post records that the Mathematical Sciences Research Institute’s 2017–18 annual report called KLS a central open problem in high-dimensional convex geometry, that the Simons Institute described it as one of the most important open problems in convex geometry, and that Ronen Eldan noted its broad implications in the proceedings of the 2022 International Congress of Mathematicians.

A Human-Directed Agentic Research Process

According to the post, the authors began by working to improve the July 2026 result. Through a structured, human-directed process with AI agents, they explored more than 100 candidate approaches, many involving lengthy calculations with higher-order tensors, and produced a new mathematical criterion that became the foundation of the final proof.

The authors then discovered that the criterion could be applied recursively, with each improved bound fed back into the same argument to produce a still tighter one. In the October 1, 2026 version of the paper, this reduced the dependence on dimension to the iterated logarithm, which grows extremely slowly but still grows with dimension and therefore did not yet resolve the conjecture. The final step was to repeat the entire recursive refinement rather than applying it only once, an idea the post says was inspired by the authors’ earlier work on fast algorithms for linear programming. The authors proved that the small errors introduced at each stage shrink fast enough that their total remains bounded by a universal constant independent of dimension, completing the proof in the October 4, 2026 version.

The post states that the recursive method, its repeated application, and the bounded-error argument are the researchers’ original contributions. AI tools helped explore candidate approaches, carry out detailed derivations, prepare the manuscript, and perform internal proof checks, while the researchers determined the mathematical direction, selected the promising ideas, assembled them into the final argument, and verified the proof. The post describes the method as agentic search with iterative human-assisted pruning: as multiple agents explored variations of an idea in parallel, the researcher examined intermediate results, eliminated unpromising directions, and passed the most promising result to the next round. Roughly one hundred research trajectories were explored before the key breakthrough emerged.

In a separate track of the project, the authors made repeated unguided attempts to solve the same problem with several leading AI models using roughly the same total token budget as the main process, and the post reports that this effort fell short of the goal. The eventual success, the post states, depended on both the capabilities of the AI systems and the mathematical judgment of the researchers. The post thanks Song for his contributions to the work, and Victor Reis and Ishai Menache for discussions throughout the project.

Independent Proofs and Machine Verification

On October 4, 2026, the same day the complete proof was posted, Pierre Bizeul, Boaz Klartag, and Joseph Lehec posted a 32-page proof developed in parallel, titled Presenting a proof of the Kannan-Lovász-Simonovits conjecture. The paper’s abstract states that “the crucial step in the proof is the very recent criterion from Song and Zhang involving high-order derivatives of tilt averages,” and its arXiv comments note that the paper contains a paragraph describing AI use. The abstract places KLS alongside Bourgain’s slicing problem and the variance conjecture as driving forces for mathematical developments in high-dimensional geometry in recent decades.

Krishnakumar Balasubramanian and Shiva Kasiviswanathan posted a separate proof, A Dimension-Free Bound on the Poincaré Constant of Isotropic Log-Concave Measures, first submitted on October 6, 2026 and revised on October 8, 2026. Its abstract describes a deterministic variational proof with an explicit bound of 25 on the Poincaré constant of any isotropic log-concave probability measure.

A Lean 4 formalization named KLS500 followed, formalizing a dimension-free Poincaré constant of at most 500 for every isotropic log-concave probability law. According to the repository, the development is based chiefly on the cumulant and suspension approach of Bizeul, Klartag, and Lehec, incorporating the tilt–spectral criterion of Song and Zhang, and its verification rebuilt 1,710 mathematical modules at kernel trust level zero. Lean verification also passed for the exact KLS conjecture statement defined by OpenAI, using the universal Poincaré constant 500. The project is licensed under Apache 2.0.

The Microsoft Research post describes independent proofs as among mathematics’ strongest forms of validation, because they demonstrate that a result does not rest on a single chain of reasoning. With the conjecture resolved, the post states, results that previously relied on it as an assumption can now be stated unconditionally. The authors have shortened their proof and verified the streamlined argument in Lean, and the post reports they plan to release both after final review.