微软研究者证明 31 年未解的 KLS 猜想，AI 智能体参与探索证明路径

微软研究员与合作伙伴将新的数学思想与人类引导的 AI 相结合，解决了高维几何与概率论中的一个核心问题

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

• 基础性科学突破： 研究人员解决了 Kannan-Lovász-Simonovits（KLS）猜想，这是一个已有 31 年历史的问题，被广泛视为高维几何领域的核心未解难题之一，对统计学、优化、算法和计算机科学均有影响。
• 普适几何原理： 该结果确立了 log-concave 分布的一条普适几何原理，表明简单的平坦切割能够在固定因子范围内捕捉其最窄的瓶颈，且与维度无关。 
• 人机协作： 这一突破源自一个由人类主导的智能体研究过程，其中 AI 系统探索数学可能性，而研究人员则评估、筛选并重新引导搜索方向。
• 独立验证： 多位独立研究人员已验证了这项研究，认定其核心判据为关键突破，随后还进行了机器校验的形式化验证。 

• 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.

Kannan–Lovász–Simonovits（KLS）猜想于 1995 年提出。它追问的是：对于一大类高维概率分布，最佳的平坦切割或超平面切割是否总是几乎与任意形状的最佳切割同样有效。更准确地说，KLS 预测两者之差不超过一个普适常数，且与维数无关。这将确立一条无维度限制的几何原理，对高维几何、概率论和理论计算机科学具有重要影响。由于这些切割的几何性质决定了随机游走探索分布的快慢，KLS 在高维采样理论中也扮演着核心角色。

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.

自 1995 年以来，数学家们已积累了大量证据表明该猜想成立，但完整证明始终难以企及。如今，包括微软研究院机器学习和优化组的 Xinzhi Zhang 在内的两位研究人员证明了 KLS 猜想（在新标签页中打开）。他们证明了无论一个形状有多少维，这一关系都以固定界成立。在此项工作之前，已知的最佳结果（在新标签页中打开）（于 2026 年 7 月确立）允许该界随维数增加而缓慢增长。这项工作确立了一条基础性几何原理：高维空间的表现比此前所知更好，且随着维数增加，在其中穿行的障碍不会无界增长。 

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). 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), 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. 

早在KLS猜想被解决之前，其重要性就已在整个领域得到公认。在2017-18年度报告中，数学科学研究所（MSRI）（在新标签页中打开）称其为“高维凸几何中的一个核心未解问题”。西蒙斯研究所（在新标签页中打开）将其描述为“凸几何中最重要的未解问题之一”。在2022年国际数学家大会（ICM）（在新标签页中打开）的会议录中，Ronen Eldan指出了它对高维凸几何与计算几何的广泛影响。Quanta Magazine（在新标签页中打开）写道，KLS“处于统计学和计算机科学中许多问题的核心”。

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) called it “a central open problem in high-dimensional convex geometry.” The Simons Institute (opens in new tab) 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), Ronen Eldan noted its broad implications for high-dimensional convex and computational geometry. Quanta Magazine (opens in new tab) wrote that KLS “lies at the heart of many questions in statistics and computer science.”

技术细节

Technical details

作者们首先改进了2026年7月的结果，以使数学界更精确。在结构化、由人类主导的流程中与AI智能体协作，他们探索了100多种候选方法，其中许多涉及高阶张量的冗长计算。这产生了一个新的数学判据，成为最终证明的基础。

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.

作者们随后发现，新判据可以递归应用。每个改进后的界都可以反馈到同一论证中，从而产生更紧的界。在2026年10月1日版本的论文中，这将对方维的依赖降低到迭代对数。该函数增长极其缓慢，但仍随维数增长，因此尚未完全解决该猜想。

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.

最后一步是重复整个递归细化过程，而不是只应用一次。这一想法受到作者们此前关于线性规划快速算法工作的启发。作者们证明，每个阶段引入的小误差收缩得足够快，其总和保持在一个与维数无关的通用常数之内。这消除了对维数的依赖，并在2026年10月4日版本的论文中完成了证明。

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.

递归方法、其重复应用，以及累积误差保持有界的证明，都是研究者的原创贡献。AI工具帮助探索候选方法、进行详细推导、准备手稿并执行内部证明检查。研究者确定了数学方向，选出了有前景的想法，将它们整合为最终论证，并验证了证明。

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

在作者们发布完整证明的同一天，另一个顶尖专家小组发布了一份完整证明（在新标签页中打开），是他们平行开发的。他们的工作建立在微软论文第一版（在新标签页中打开）的发现之上，称其为“证明中的关键一步”。同一天单独出现的第三份证明（在新标签页中打开）依赖于一个密切相关的想法。此外，随后发布了一个Lean 4形式化（在新标签页中打开），将微软第一篇论文的关键判据与额外研究结合起来。 

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) that they developed in parallel. Their work built upon the findings in the first version (opens in new tab) of the Microsoft paper, calling it “the crucial step in the proof.” A third proof (opens in new tab) which appeared separately on the same day relies on a closely related idea. In addition, a Lean 4 formalization (opens in new tab) was subsequently released, combining the key criterion from the first Microsoft paper with additional research. 

独立证明是数学中最有力的验证形式之一，因为它表明一个结果并不依赖于单一的推理链条。随后出现的替代方法和形式化验证进一步增强了人们的信心，即该领域发现的是一个真正的底层原理，而非脆弱的技术论证。作者还缩短了他们的证明，并在 Lean 中验证了精简后的论证；他们计划在最终审查后发布两者。这些进展共同提供了互补形式的确认。

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

在证明 KLS 的过程中，这项研究还展示了让研究人员引导 AI 的力量，而不是简单地要求 AI 通过前沿模型或智能体的单次端到端运行来解决复杂问题。作者使用了智能体搜索过程，并辅以迭代式、人工辅助的“剪枝”：当多个智能体并行探索一个想法的变体时，研究人员检查它们的中间结果，剔除没有希望的方向，并将最有希望的结果传递到下一轮。在关键突破出现之前，大约探索了一百条研究轨迹。 

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. 

在项目的另一条独立路线中，作者使用几个领先的 AI 模型，以与主流程大致相同的总 token 预算，对同一问题进行了多次无引导的尝试。这一努力未能达到目标。最终的成功既取决于 AI 系统的能力，也取决于研究人员的数学判断力。 

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

综上所述，解决 KLS 解决了高维几何中的一个核心问题。此前依赖该猜想作为假设的广泛结果现在可以无条件地陈述。因此，该证明为凸几何、概率论和理论计算机科学的研究提供了更坚实的基础。

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 

感谢我们的合著者 Zhao Song 对这项工作的贡献，以及 Victor Reis（在新标签页中打开） 和 Ishai Menache 在整个项目过程中的有益讨论。 

Thank you to our co-author Zhao Song for his contributions to this work, and Victor Reis (opens in new tab) and Ishai Menache for helpful discussions throughout the project. 

在新标签页中打开

Opens in a new tab

文章 解决数学领域一个 31 年之久的重大挑战——KLS 猜想 首次发表于 Microsoft Research。

The post Solving a 31-year-old grand challenge in mathematics – the KLS conjecture appeared first on Microsoft Research.

注意转载授权 · 阅读原文。中文正文为 AI 翻译，请以原文为准。

注意转载授权 · 阅读原文