🤖 machine learning

Improving the matrix multiplication exponent with modern optimization and AlphaEvolve

本文通过重新构建底层优化问题，并利用现代机器学习技术与 AlphaEvolve 增强求解过程，将矩阵乘法指数 $\omega$ 的上界改进至小于 2.371177。

原作者： Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog

发布于 2026-08-18

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在计算机科学的广袤领域中，很少有操作能像两个大型数字网格相乘（这一过程被称为矩阵乘法）那样具有基础性意义。这项数学任务支撑着从训练人工智能模型到在视频游戏中渲染逼真图像的一切。几十年来，科学家们一直知道这种操作可以比标准的、直观的方法更快地完成，但其究竟能快到什么程度的精确极限，一直是该领域最顽固的谜团之一。这个极限由一个单一的数字描述，即一个数学指数，它决定了随着网格规模增加，计算所需的时间增长方式。这个数字越小，计算机的效率就越高。虽然理论上的最小值已知至少为 2，但目前已证实的最佳上界多年来一直徘徊在 2.37 之上，研究人员一直在利用日益复杂的数学工具不断尝试突破这一障碍。

来自 Google DeepMind 的一个研究团队及其来自多所大学的合作者，现在将这一边界又向前推进了一步。通过将现代优化技术与一种新形式的人工智能相结合，他们创下了新的纪录，证明该指数可以降低到 2.371177 以下。这是一个微小的数值变化，但在这一特定问题的语境下，它代表了一个显著的进步。之前的最佳结果是在 2025 年取得的，为 2.371339。这项新发现并未解决关于确切极限的终极之谜，也不会立即改变现实中计算机进行矩阵乘法的方式，但它收紧了该问题的理论约束，表明天花板比此前认为的可能要低。

通往这一新纪录的路径始于一种被称为“激光方法”（laser method）的数学框架，这是一种四十多年前开发的用于间接设计更快速矩阵乘法算法的技术。该方法最新的改进形式——称为“组合损失分析”（combination loss analysis）——依赖于求解一个庞大且复杂的优化问题。这个问题涉及寻找将一个大型数学结构分解为更小部分的最佳方式。研究人员发现，这个问题的难度取决于代表分解深度的参数。此前的尝试都停留在深度为 3 的阶段，这限制了可以调整的变量数量。新团队意识到，通过将这种深度增加到 4，他们可以探索一个更大的可能性空间，但这样做需要解决一个涉及数百万个变量的问题，这对于过去使用的传统算法来说任务过于繁重。

为了应对这种规模，研究人员转向了借鉴自机器学习的技术。他们没有使用标准的数学求解器，而是重新构建了问题，使其能够通过梯度下降法（一种常用于训练神经网络的方法）来处理。这种方法允许他们利用强大的计算机硬件进行并行数据处理，从而应对随深度分解而来的复杂度爆炸。他们将数学变量视为类似于学习模型中可调节的权重，通过迭代优化这些变量来寻找更好的解。仅这一策略的转变就使上界得到了可衡量的提升，证明了现代计算工具可以释放出旧方法未能挖掘出的潜力。

然而，团队并未止步于此。他们采用了名为 AlphaEvolve 的系统，这是一种旨在编写并改进自身代码的人工智能。研究人员不仅是运行优化算法，还让 AI 去修改算法本身。该系统会生成新版本的代码，运行它以观察产生的上界，然后进一步进化代码以最小化该上界。这种自我改进的过程使得研究人员能够发现优化策略中细微的改进点，而这些细节是人类团队可能会忽略的。这种自动化进化的结果带来了进一步的提升，将上界推向了 2.371177 的新纪录。

为了确保这一结果不是由于计算机舍入误差或浮点精度问题造成的，团队执行了严格的验证步骤。他们提取了由算法找到的解，并将所有数字转换为精确的分数，以完美的精度进行最终计算。他们还将方程中的每个对数都替换为一个安全的有理数界限，以确保满足约束条件。这种严谨的认证过程确认了新的上界在数学上是有效的，并且不存在经常困扰此类复杂计算的数值噪声。

研究人员指出，尽管他们的方法取得了更好的上界，但改进的难度正在日益增加。他们所取得的增益在量级上与过去四十年里看到的渐进式进展相当。他们认为，虽然通过继续完善这些优化技术可能仍能实现进一步的微调，但若要实现对真实极限理解的巨大飞跃，则可能需要全新的数学思想。目前，这项工作证明了将深厚的理论数学与现代机器学习的计算能力相结合的力量，证明了即使在一个拥有悠久历史的领域中，仍然存在着发现的空间。

技术摘要：利用现代优化与 AlphaEvolve 改进矩阵乘法指数

问题陈述
矩阵乘法的计算复杂度由指数 $\omega$ 表征，即两个 $n \times n$ 矩阵可以在 $O(n^{\omega + o(1)})$ 次操作内完成乘法，这仍然是理论计算机科学中的一个基本开放问题。虽然 Strassen 在 1969 年的突破确立了 $\omega < 2.81$ ，但目前的最佳上界为 $\omega < 2.371339$ (Alman et al., 2025)。该上界是通过对被称为“组合损失分析”（combination loss analysis）的“激光方法”（laser method）进行改进而得出的。这种方法的核心在于解决一个复杂的非凸优化问题。其难点在于优化复杂度（随递归层级 $\ell^*$ 呈双指数级增长）与所得界限紧密程度之间的权衡。之前的最先进（SOTA）结果是在递归层级 $\ell^* = 3$ 时实现的，涉及约 25,000 个参数。

方法论
作者提出了一种两步走的方法，旨在改进用于组合损失分析的优化过程，目标是将递归层级提升至 $\ell^* = 4$ 。

重构与基于梯度的优化：
- 问题扩展： 作者重新构建了优化问题以处理 $\ell^* = 4$ 的情况。这使得可优化的参数量从约 2.5 万个增加到了约 700 万个。
- 可微目标函数： 为了解决这一高维非凸问题，他们放弃了先前研究中使用的序列二次规划法（SQP），转而采用基于梯度的方法。
- 参数化： 为了处理概率必须为非负且总和为 1 的约束，分布通过 Logits 进行参数化并使用 Softmax 函数进行转换，从而实现无约束优化。
- 最大熵处理： 该问题涉及在边缘约束条件下计算最大熵分布（ $H_{max}$ ）。作者并非直接优化这些分布，而是利用来自最优传输理论的 Sinkhorn-Knopp 算法来计算它们。他们采用了隐式微分技术对该算法进行反向传播，确保目标函数保持可微且稳定。
- 实现： 该算法在 Jax 中实现，以利用硬件并行化（GPU）。为了管理优化树的非均匀图结构，他们引入了带有掩码（masking）的“虚节点”（phantom nodes），并将节点聚类为专门的“阶段”（stages），从而使问题能够表示为多维张量，以便进行高效的并行处理。
AlphaEvolve 集成：
- 作者应用 AlphaEvolve (Novikov et al., 2025) 来进一步精炼优化算法。
- AlphaEvolve 修改了优化程序本身。通过使用“进化构造”（evolving constructions）功能，每一代算法都从父代算法找到的最佳解点开始，通过迭代演化代码以最小化所得的 $\omega$ 界限。
严格验证：
- 为确保结果不受浮点误差影响，作者执行了一个独立的验证步骤。他们将浮点解舍入为有理数，并使用精确的有理算术重新评估所有推导出的量。
- 对数被替换为向确保所有约束仍满足优化问题要求的方向进行舍入的有理界限，从而为该界限提供了一个数学上严谨的证明。

主要贡献与结果

新上界： 结合后的方法得出了新的上界 $\omega < 2.371177$ 。
改进幅度： 这比之前的 SOTA（ $\omega < 2.371339$ ）提高了约 $1.62 \times 10^{-4}$ 。仅基于梯度的优化本身就改进了约 $0.97 \times 10^{-4}$ ，剩余的增益归功于 AlphaEvolve 的精炼。
可扩展性： 本研究展示了解决 $\ell^* = 4$ 规模下组合损失分析问题的可行性，由于参数量的爆炸，这一规模此前在使用标准 SQP 方法时是无法实现的。

意义与主张
论文声称，这一改进在量级上与自 Coppersmith-Winograd 界限（ $\omega < 2.376$ ）确立以来过去 40 年间的大多数进展相当。作者强调，他们的贡献在于利用现代机器学习技术（梯度下降、最优传输和进化代码生成）更有效地解决现有的数学框架。

作者对未来前景保持谦逊，指出虽然通过这种以优化为中心的路径可能实现进一步的微小改进，但要实现 $\omega$ 的显著降低，可能需要超越当前激光方法框架的新数学思想。这项工作是受 2025 年秋季西蒙斯计算理论研究所（Simons Institute for the Theory of Computing）相关讨论的启发。

类似论文