微软用 AI 智能体破解 KLS 猜想

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

概览

• 基础科学突破： 研究人员解决了 Kannan-Lovász-Simonovits (KLS) 猜想，这是一个拥有 31 年历史、被广泛视为高维几何领域核心开放问题之一的难题，其成果对统计学、优化、算法和计算机科学均具有深远影响。
• 普适几何原理： 该结果确立了对数凹分布（log-concave distributions）的一个普适几何原理，表明简单的平面切割可以在固定因子范围内捕捉到其最窄的瓶颈，且这一特性与维度无关。
• 人机协作： 这一突破源于一个由人类主导的智能体研究过程（agentic research process），其中 AI 系统探索数学可能性，而研究人员负责评估、剪枝并引导搜索方向。
• 独立验证： 多位独立研究人员已验证了这项研究，确认其核心准则是关键突破点，随后还进行了机器辅助的形式化验证。

数十年来，关于在高维空间中计算难度的一个根本性问题一直未能得到证明。最新的研究解决了这一问题，消除了理解科学和计算领域中随机算法效率的主要理论障碍。

Kannan–Lovász–Simonovits (KLS) 猜想于 1995 年提出。它探讨的是：对于一大类高维概率分布，最佳的平面或超平面切割是否总是几乎同样有效，无论采用何种形状的切割方式。更准确地说，KLS 预测这两者之间的差异不会超过一个普适常数，且与维度数量无关。这将建立一个与维度无关的几何原理，对高维几何、概率论和理论计算机科学具有重要意义。由于这些切割的几何结构决定了随机游走探索分布的速度，KLS 也在高维采样理论中扮演着核心角色。

图 1：正四面体上 KLS 猜想的示意图（简化版）。

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

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

技术细节

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

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

最后一步是重复整个递归精化过程，而不仅仅应用一次。这一想法受到作者早期在线性规划快速算法方面工作的启发。作者证明，每个阶段引入的小误差收缩得足够快，使得其总和仍由一个与维度无关的通用常数界定。这消除了对维度数量的依赖，并在 2026 年 10 月 4 日版本的论文中完成了证明。

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

独立确认

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

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

人机协作指导

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

在该项目的另一条独立路径中，作者使用几个领先的 AI 模型，以大致相同的总 token 预算，反复尝试无指导地解决同一问题。这一努力未能达成目标。最终的成功既取决于 AI 系统的能力，也取决于研究人员的数学判断力。

结论

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

这项工作还展示了精心引导的人机协作如何能够促进真正的科学发现，同时强化而非取代人类的洞察力。它凸显了科学判断力的持续重要性，即在识别有前景的方向、发现概念间的联系以及洞察局部见解何时指向更深层次结果方面的作用。作者目前正在简化证明并扩展其形式化验证，以便数学和理论计算机科学社区更容易审查该结果并在此基础上继续研究。

致谢

感谢我们的合著者赵 Song（Zhao Song）对本工作的贡献，以及 Victor Reis 和 Ishai Menache 在整个项目期间提供的有益讨论。

在新标签页中打开

文章 解决数学领域一项历时 31 年的重大挑战——KLS 猜想 首发于 Microsoft Research。