Microsoft Says Human-Directed AI Helped Prove the 31-Year-Old KLS Conjecture — Unguided Runs on the Same Token Budget Fell Short

Microsoft Research announced on October 21, 2026 that two researchers — Xinzhi Zhang of its Machine Learning and Optimization group and co-author Zhao Song — have proved the Kannan–Lovász–Simonovits (KLS) conjecture, a 31-year-old problem widely described as a central open question in high-dimensional convex geometry. The announcement matters beyond mathematics because of how Microsoft says it happened: a human-directed agentic process in which AI systems explored more than 100 candidate approaches while the researchers evaluated, pruned and redirected the search — and a control track in which repeated unguided attempts by several leading models, using roughly the same total token budget, fell short.

The problem

KLS, proposed in 1995, asks whether for a broad class of high-dimensional log-concave probability distributions the best flat hyperplane cut is always within a fixed universal constant of the best cut of any shape. Because the geometry of cuts governs how quickly random walks can explore a distribution, the conjecture sits at the center of high-dimensional sampling theory, with consequences for statistics, optimization, algorithms and theoretical computer science — the machinery under probabilistic inference and optimization across machine learning. Microsoft’s post recalls that the Simons Institute called KLS “one of the most important open problems in convex geometry” and that Quanta Magazine wrote it “lies at the heart of many questions in statistics and computer science.”

Before this work, the best known result — established in July 2026, per the post — still let the bound grow slowly with the number of dimensions. The new proof pins it to a universal constant: simple flat cuts capture the narrowest bottlenecks of log-concave distributions regardless of dimension.

A directed search, not an autonomous run

The workflow Microsoft describes will look familiar to anyone operating agent fleets. Parallel agents explored variations of an idea; 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 new mathematical criterion emerged, many involving lengthy calculations with higher-order tensors that AI tools helped carry out.

The control track is the striking part. In a separate effort, 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, directed process. That effort fell short of the goal. Microsoft is explicit about the division of labor: the recursive method, its repeated application, and the proof that accumulated errors remain bounded are original contributions of the researchers; AI tools explored candidate approaches, carried out detailed derivations, helped prepare the manuscript and performed internal proof checks.

From iterated logarithm to O(1)

Date	Milestone (per Microsoft’s post)
1995	KLS conjecture proposed
July 2026	Prior best result: bound still grows slowly with dimension
Oct. 1, 2026 paper version	Recursive criterion cuts the dependence to the iterated logarithm
Oct. 4, 2026 paper version	Repeated recursion removes dimension dependence: O(1) bound
Same day	Separate group posts a parallel full proof; a third proof appears
Afterward	Lean 4 formalization released; streamlined Lean-checked proof planned

The final move — repeating the entire recursive refinement rather than applying it once, an idea inspired by the authors’ earlier work on fast algorithms for linear programming — is what converted an extraordinarily slow-growing dependence into a fixed constant and completed the proof.

Independent confirmation

Microsoft stresses validation. On the same day the complete proof was posted, a separate group of leading experts posted a full proof developed in parallel, building on the first version of the Microsoft paper and calling it “the crucial step in the proof.” A third proof relying on a closely related idea appeared the same day, and a Lean 4 formalization combining the key criterion with additional research was subsequently released. The authors have also shortened their proof and verified the streamlined argument in Lean, with release planned after final review. For a result announced by a corporate lab, that mix of parallel independent proofs and machine-checked formalization is unusually strong corroboration.

Why agent operators should care

Recent capability coverage has leaned toward autonomy claims — Anthropic’s report that Claude Mythos 5 autonomously designed record-beating quantum circuits, or four Gemini 4 Argon agents beating Minecraft end to end. The KLS result points the other way, and it is the cleaner data point: the same class of models, given the same token budget without direction, did not produce the proof. The win came from a human-in-the-loop pruning loop of exactly the kind described in subagent orchestration playbooks — fan out, inspect intermediate results, kill branches, promote survivors — and it rhymes with the agents propose, humans merge review posture: AI generated, derived and checked material, but the humans decided what counted and verified the final argument.

Caveats

Everything here comes from Microsoft Research’s own announcement, written by the author of the result. The underlying paper, “An O(1) Bound for the KLS Constant,” and the independent proofs are linked from the post but are not independently assessed in this article; the size of the AI contribution, the “human-directed” framing and the description of the unguided control are Microsoft’s claims. This is a research result, not a product: no tool ships, no API changes, and nothing needs to be deployed.

Sources

• Solving a 31-year-old grand challenge in mathematics – the KLS conjecture — Microsoft Research, primary source, October 21, 2026
• Microsoft Research Blog index — lists the post as October 21, 2026, by Xinzhi Zhang
• Microsoft Research home — lists the announcement under What’s new, October 21, 2026