# Microsoft Research 与合作者证明 31 年历史的 KLS 猜想
> 原标题:Solving a 31-year-old grand challenge in mathematics – the KLS conjecture
- 来源:Microsoft Research 博客
- 发布时间:2026-10-21T16:00:00.000Z
- AIHOT:https://aihot.news/items/y1fd2c0s3ydociygdah7apvme
- 原文:https://www.microsoft.com/en-us/research/blog/solving-a-31-year-old-grand-challenge-in-mathematics-the-kls-conjecture/
## 摘要
Microsoft Research 的 Xinzhi Zhang 与 Zhao Song 证明 1995 年提出的 Kannan–Lovász–Simonovits(KLS)猜想,表明对数凹分布的最优平面切割与任意形状切割的差距不随维度增长,以普适常数为界。
## 推荐理由
微软研究员亲述证明过程,展示了人类引导多智能体迭代剪枝的科研协作方式,约百条研究路径中筛出关键判据。
## 正文 · 中文译文
## 微软研究员与合著者将新的数学思想与人类引导的 AI 相结合,解决了高维几何与概率论中的一个核心问题

## 概览
- **基础性科学突破:** 研究人员解决了 Kannan-Lovász-Simonovits(KLS)猜想,这是一个已有 31 年历史的问题,被广泛视为高维几何领域的核心未解问题之一,对统计学、优化、算法和计算机科学均有影响。
- **一条普适的几何原理:** 该结果确立了对数凹分布的一条普适几何原理,表明简单的平坦切割能够在固定倍数内捕捉到它们最窄的瓶颈,与维数无关。
- **人机协作:** 这一突破源自一个由人类引导的智能体研究过程,其中 AI 系统探索数学可能性,而研究人员则评估、筛选并重新引导搜索方向。
- **独立验证:** 多位独立研究人员已验证这项研究,认定其核心判据为关键突破,随后还进行了机器校验的形式化验证。
数十年来,一个关于高维空间计算难度的根本性问题一直未能得到证明。新研究解决了这一问题,消除了理解科学与计算中广泛使用的随机算法效率的一大理论障碍。
Kannan–Lovász–Simonovits(KLS)猜想于 1995 年提出。它追问:对于一大类高维概率分布,最佳的平坦切割或超平面切割是否总是几乎与任意形状的最佳切割同样有效。更准确地说,KLS 预测两者之差不超过一个普适常数,与维数无关。这将确立一条与维数无关的几何原理,对高维几何、概率论和理论计算机科学具有重要影响。由于这些切割的几何性质决定了随机游走探索分布的速率,KLS 在高维采样理论中也扮演着核心角色。

图 1:正四面体上 KLS 猜想的示意图(简化版)。
自 1995 年以来,数学家们已积累了大量证据表明该猜想成立,但完整证明始终难以企及。如今,包括微软研究院机器学习和优化组的 Xinzhi Zhang 在内的两位研究人员[证明了 KLS 猜想(在新标签页中打开)](https://arxiv.org/pdf/2610.01447v2)。他们证明了无论一个形状有多少维,这一关系都以固定界成立。在此项工作之前,2026 年 7 月确立的[最佳已知结果(在新标签页中打开)](https://arxiv.org/abs/2607.24164v1)允许该界随维数增加而缓慢增长。这项工作确立了一条基本几何原理:高维空间的表现比此前所知更好,且在其间穿行的障碍不会随维数增加而无界增长。
早在KLS猜想被解决之前,其重要性就已在整个领域得到公认。在2017-18年度报告中,[数学科学研究所(MSRI)(在新标签页中打开)](https://legacy.slmath.org/system/cms/files/855/files/original/00._NSF_Annual_Report_2017-18_WEBVERSION.pdf)称其为“高维凸几何中的一个核心未解问题”。[西蒙斯研究所(在新标签页中打开)](https://simons.berkeley.edu/news/theory-institute-beyond-january-2021)将其描述为“凸几何中最重要的未解问题之一”。在[2022年国际数学家大会(ICM)(在新标签页中打开)](https://ems.press/books/standalone/278/5556)的会议录中,Ronen Eldan指出了它对高维凸几何与计算几何的广泛影响。[Quanta Magazine(在新标签页中打开)](https://www.quantamagazine.org/statistics-postdoc-tames-decades-old-geometry-problem-20210301/)写道,KLS“处于统计学和计算机科学中许多问题的核心”。
## 技术细节
作者首先改进了2026年7月的结果,以使数学界更精确。在结构化、由人类主导的流程中与AI智能体协作,他们探索了100多种候选方法,其中许多涉及高阶张量的冗长计算。这产生了一个新的数学判据,成为最终证明的基础。
随后,作者发现这一新判据可以递归应用。每一个改进后的界都可以反馈回同一论证,从而产生更紧的界。在2026年10月1日版本的论文中,这将维度依赖性降低到迭代对数。该函数增长极为缓慢,但仍随维度增长,因此尚未完全解决该猜想。
最后一步是重复整个递归精化过程,而不是只应用一次。这一想法受到作者此前关于线性规划快速算法工作的启发。作者证明,每个阶段引入的小误差收缩得足够快,其总和被一个与维度无关的通用常数所界定。这消除了对维数的依赖,并在2026年10月4日版本的论文中完成了证明。
递归方法、其重复应用,以及累积误差保持有界的证明,都是研究者的原创贡献。AI工具帮助探索候选方法、进行详细推导、准备手稿并执行内部证明检查。研究者确定了数学方向,选出了有前景的想法,将它们整合为最终论证,并验证了证明。
## 独立确认
在作者发布完整证明的同一天,另一组顶尖专家[发布了一份完整证明(在新标签页中打开)](https://arxiv.org/abs/2610.05474),是他们并行开发的。他们的工作建立在微软论文[第一版(在新标签页中打开)](https://arxiv.org/abs/2610.01447v1)的发现之上,称其为“证明中的关键一步”。同日单独出现的[第三份证明(在新标签页中打开)](https://arxiv.org/abs/2610.07728)依赖于一个密切相关的想法。此外,随后发布了一个[Lean 4形式化(在新标签页中打开)](https://github.com/HongruZhao/KLS500),将第一篇微软论文的关键判据与额外研究结合起来。
独立证明是数学中最有力的验证形式之一,因为它们表明一个结果并不依赖于单一的推理链条。随后出现的替代方法和形式化验证进一步增强了人们的信心,即该领域发现的是一个真正的底层原理,而非脆弱的技术论证。作者还缩短了他们的证明,并在 Lean 中验证了精简后的论证;他们计划在最终审查后发布两者。这些进展共同提供了互补形式的确认。
## 人机引导
在证明 KLS 的过程中,这项研究还展示了让研究人员引导 AI 的力量,而不是简单地要求 AI 通过前沿模型或智能体的单次端到端运行来解决一个复杂问题。作者使用了一种带有迭代式、人工辅助“剪枝”的智能体搜索过程:当多个智能体并行探索一个想法的各种变体时,研究人员检查它们的中间结果,剔除没有希望的方向,并将最有希望的结果传递到下一轮。在关键突破出现之前,大约探索了一百条研究轨迹。
在项目的另一条独立路线中,作者使用几个领先的 AI 模型对同一问题进行了多次无引导的尝试,使用的总 token 预算与主流程大致相同。这一努力未能达到目标。最终的成功既取决于 AI 系统的能力,也取决于研究人员的数学判断力。
## 结论
综上所述,解决 KLS 解决了高维几何中的一个核心问题。此前依赖该猜想作为假设的广泛结果现在可以在无条件下陈述。因此,该证明为凸几何、概率论和理论计算机科学的研究提供了更坚实的基础。
这项工作还展示了经过精心引导的人机协作如何能够为真正的科学发现做出贡献,同时增强而非取代人类的洞察力。它突显了科学判断在识别有希望的方向、认识概念联系以及看出部分洞察何时指向更深层结果方面的持续重要性。作者现在正在简化证明并扩展其形式化验证,以便数学和理论计算机科学界能够更容易地审查这一结果并在此基础上继续发展。
## 致谢
感谢我们的合著者 Zhao Song 对这项工作的贡献,以及 [Victor Reis(在新标签页中打开)](https://loop.usercontent.microsoft/?disableExtension=true&preview=true#) 和 [Ishai Menache](https://www.microsoft.com/en-us/research/people/ishai/) 在整个项目过程中的有益讨论。
在新标签页中打开
文章 [解决数学领域一个 31 年的大挑战——KLS 猜想](https://www.microsoft.com/en-us/research/blog/solving-a-31-year-old-grand-challenge-in-mathematics-the-kls-conjecture/) 首次出现在 [Microsoft Research](https://www.microsoft.com/en-us/research)。
## 正文 · 原文
## Microsoft researcher and collaborator combine new mathematical ideas with human-directed AI to resolve a central problem in high-dimensional geometry and probability

## At a glance
- **Fundamental scientific breakthrough:** Researchers resolved the Kannan-Lovász-Simonovits (KLS) conjecture, a 31-year-old problem widely regarded as one of the central open questions in high-dimensional geometry, with implications for statistics, optimization, algorithms, and computer science.
- **A universal geometric principle:** The result establishes a universal geometric principle for log-concave distributions, showing that simple flat cuts can capture their narrowest bottlenecks within a fixed factor, regardless of dimension.
- **Human-AI collaboration:** The breakthrough emerged from a human-directed agentic research process in which AI systems explored mathematical possibilities while researchers evaluated, pruned, and redirected the search.
- **Independent confirmation:** Multiple independent researchers have validated this research, identifying its central criterion as the key breakthrough, followed by a machine-checked formal verification.
For decades, a fundamental question about the difficulty of computing in high-dimensional spaces has resisted proof. New research resolves this question, removing a major theoretical obstacle to understanding the efficiency of randomized algorithms used across science and computing.
The Kannan–Lovász–Simonovits (KLS) conjecture was proposed in 1995. 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. More precisely, KLS predicts that the two differ by no more than a universal constant, regardless of the number of dimensions. This would establish a dimension-free geometric principle with important consequences for high-dimensional geometry, probability, and theoretical computer science. Because the geometry of these cuts governs how quickly random walks can explore a distribution, KLS also plays a central role in the theory of high-dimensional sampling.

Figure 1: An illustration of the KLS Conjecture (simplified) on regular tetrahedron.
Since 1995, mathematicians have accumulated evidence that the conjecture was true, but a complete proof remained elusive. Now, two researchers, including Xinzhi Zhang from the Machine Learning and Optimization group at Microsoft Research, have [proved the KLS conjecture (opens in new tab)](https://arxiv.org/pdf/2610.01447v2). They have shown that the relationship holds with a fixed bound, regardless of how many dimensions a shape has. Before this work, the [best known result (opens in new tab)](https://arxiv.org/abs/2607.24164v1), established in July 2026, allowed that bound to grow slowly as the number of dimensions increased. This work establishes a fundamental geometric principle: high-dimensional spaces are better behaved than previously known, and the obstacles to navigating them do not grow without bound as dimensions increase.
The importance of the KLS conjecture was recognized across the field long before it was resolved. In its 2017-18 Annual Report, the [Mathematical Sciences Research Institute (MSRI) (opens in new tab)](https://legacy.slmath.org/system/cms/files/855/files/original/00._NSF_Annual_Report_2017-18_WEBVERSION.pdf) called it “a central open problem in high-dimensional convex geometry.” The [Simons Institute (opens in new tab)](https://simons.berkeley.edu/news/theory-institute-beyond-january-2021) described it as “one of the most important open problems in convex geometry.” In the proceedings of the [2022 International Congress of Mathematicians (ICM) (opens in new tab)](https://ems.press/books/standalone/278/5556), Ronen Eldan noted its broad implications for high-dimensional convex and computational geometry. [Quanta Magazine (opens in new tab)](https://www.quantamagazine.org/statistics-postdoc-tames-decades-old-geometry-problem-20210301/) wrote that KLS “lies at the heart of many questions in statistics and computer science.”
## Technical details
The authors began by improving the July 2026 result in order to make the mathematical 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.
The authors then discovered that the new criterion could be applied recursively. Each improved bound could be 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. This function grows extraordinarily slowly, but it still grows with the dimension and therefore did not yet fully resolve the conjecture.
The final step was to repeat the entire recursive refinement, rather than applying it only once. This idea 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 the dimension. This eliminated the dependence on the number of dimensions and completed the proof in the October 4, 2026 version of the paper.
The recursive method, its repeated application, and the proof that the accumulated errors remain bounded are original contributions of the researchers. AI tools helped explore candidate approaches, carry out detailed derivations, prepare the manuscript, and perform internal proof checks. The researchers determined the mathematical direction, selected the promising ideas, assembled them into the final argument, and verified the proof.
## Independent confirmation
On the same day that the authors posted their complete proof, a separate group of leading experts [posted a full proof (opens in new tab)](https://arxiv.org/abs/2610.05474) that they developed in parallel. Their work built upon the findings in the [first version (opens in new tab)](https://arxiv.org/abs/2610.01447v1) of the Microsoft paper, calling it “the crucial step in the proof.” A [third proof (opens in new tab)](https://arxiv.org/abs/2610.07728) which appeared separately on the same day relies on a closely related idea. In addition, a [Lean 4 formalization (opens in new tab)](https://github.com/HongruZhao/KLS500) was subsequently released, combining the key criterion from the first Microsoft paper with additional research.
Independent proofs are among mathematics’ strongest forms of validation because they demonstrate that a result does not rest on a single chain of reasoning. The subsequent appearance of alternative approaches and formal verification further strengthens confidence that the field has uncovered a genuine underlying principle rather than a fragile technical argument. The authors have also shortened their proof and verified the streamlined argument in Lean; they plan to release both after final review. Together, these developments provide complementary forms of confirmation.
## Human-AI guidance
In the process of proving KLS, this research also demonstrates the power of having researchers direct AI rather than simply asking AI to solve a complex problem through a single end-to-end run of a frontier model or agent. The authors used an agentic search process with iterative, human-assisted “pruning”: As multiple agents explored variations of an idea in parallel, the researcher examined their intermediate result, 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. That effort fell short of the goal. The eventual success depended on both the capabilities of the AI systems and the mathematical judgment of the researchers.
## Conclusion
Taken together, resolving KLS settles a central problem in high-dimensional geometry. A wide range of results that previously relied on the conjecture as an assumption can now be stated unconditionally. The proof therefore provides a stronger foundation for research in convex geometry, probability, and theoretical computer science.
The work also demonstrates how carefully guided human-AI collaboration can contribute to genuine scientific discovery while reinforcing, rather than replacing human insight. It highlights the continuing importance of scientific judgment in identifying promising directions, recognizing conceptual connections, and seeing when a partial insight points toward a deeper result. The authors are now simplifying the proof and extending its formal verification so that the mathematics and theoretical computer science communities can more easily examine the result and build on it.
## Acknowledgements
Thank you to our co-author Zhao Song for his contributions to this work, and [Victor Reis (opens in new tab)](https://loop.usercontent.microsoft/?disableExtension=true&preview=true#) and [Ishai Menache](https://www.microsoft.com/en-us/research/people/ishai/) for helpful discussions throughout the project.
Opens in a new tab
The post [Solving a 31-year-old grand challenge in mathematics – the KLS conjecture](https://www.microsoft.com/en-us/research/blog/solving-a-31-year-old-grand-challenge-in-mathematics-the-kls-conjecture/) appeared first on [Microsoft Research](https://www.microsoft.com/en-us/research).