Improving the matrix multiplication exponent with modern optimization and AlphaEvolve
Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog
cs.DS, cs.AI, cs.CC, cs.LG
2026-08-18
用可微优化把组合损失分析扩到 700 万参数,再让 AlphaEvolve 进化求解器,矩阵乘法指数 ω 上界从 2.371339 降到 2.371177。
两个 n×n 矩阵相乘,朴素算法要 n³ 次乘法。1969 年 Strassen 用分块技巧把上界做到 2.81 以下之后,「矩阵乘法指数 ω 到底能多小」成了理论计算机科学最老的开放问题之一。下界是 2,因为输出本身就有 n² 个数;普遍猜想 ω=2。上界一侧,过去 40 年的所有改进都靠激光方法(laser method):不直接构造算法,而是分析 Coppersmith-Winograd 张量的性质来间接界定 ω。
最新一轮精化叫组合损失分析(Duan 等 2023),它把「找更好的乘法算法」变成「解一个非凸优化问题」,任何可行解都直接换算出一个 ω 上界。瓶颈随即从数学转移到计算:参数量随递归深度 ℓ 双指数增长,上一个最好结果 2.371339(Alman 等 2025)只在 ℓ=3、约 2.5 万参数的规模下,用 SQP 求解器(SNOPT)串行解出;ℓ=4 意味着约 700 万参数,旧路线跑不动。
Google DeepMind 联合 CMU、哥伦比亚、MIT 的作者,三步推进。
先把问题重构成可扩展的形式。 原实现的自由参数挂在图节点上,靠逐节点消息传递更新,图的形状太不规则,没法并行。新实现引入带掩码的幻影节点,把图补齐成规整的高维张量,代价是参数最多膨胀 3 倍;再把节点聚类成少数几类高度特化的 stage。整个问题在 JAX 里重写,最多 10 个轴同时并行,单卡 5 小时跑完一次完整优化,ℓ=4 的 700 万参数才变得可解。
再换掉求解算法。 三件套:概率分布全部用 logits 过 softmax 参数化,把「非负且和为一」的约束优化变成无约束优化;最大熵分布不再当作自由参数跟其余变量一起优化(Alman 等 2025 的做法),改用最优传输里的 Sinkhorn-Knopp 迭代直接算出,并用隐函数微分把梯度穿过 Sinkhorn-Knopp 稳定回传;更新用 Adam。整套就是标准的深度学习配方,只是优化对象从网络权重换成了数学构造。
最后让 AlphaEvolve 改进算法本身。 它不搜解,搜的是求解程序:程序跑一遍约 5 小时、输出一个 ω 上界,这个分数就是适应度。用上「evolving constructions」特性后,每一代都从父代算法找到的最好解热启动,不从零开始。
| 来源 | ω 上界 |
| Duan 等 2023 | 2.371866 |
| Williams 等 2024 | 2.371552 |
| Alman 等 2025 | 2.371339 |
| 本文 | 2.371177 |
超参数取 q=5、ℓ=4。单是新的梯度优化就把上界推进约 0.97×10⁻⁴,AlphaEvolve 再把总改进抬到约 1.62×10⁻⁴。按论文自己的说法,这个幅度与 1990 年 Coppersmith-Winograd 得到 2.376 之后的多数单次改进相当。
结果不是「数值上看起来成立」。优化结束后有独立的验证步骤:浮点解四舍五入成有理数,所有导出量用精确有理算术重算,每个对数换成朝正确方向取整的有理界,保证每条约束严格满足、不受浮点误差影响。
分工模式本身是最大的产出:人类给框架(定理 1,任何可行解给出 ω 上界),机器学习找解,LLM 进化系统改进求解器,有理算术做最终验证。这套流水线可复用,下一个能写成「可行解换证书」形式的数学问题都能照搬。
对组合损失分析这条线,可解规模从 2.5 万参数推到 700 万,搜索空间扩了不止一个量级,后来者的工程门槛已经铺平。
冷水也要泼:ω 是渐近指数,2.371177 对实用矩阵乘法没有任何影响,这类构造要 n 大到天文数字才占优势,工程界连 Strassen 算法都很少真用。这篇的意义在复杂性理论,不在 GPU kernel。
作者自己承认:沿这条路继续挖只能指望小幅改进,更大的跳跃需要新的数学想法。对照 2.371177 与猜想的 2 之间的距离,1.62×10⁻⁴ 确实只是一小步。
解本身是约 700 万个参数的数值点,论文没有给出任何人类可读的结构,回答不了「为什么这个解好」;AlphaEvolve 对优化程序具体改了什么,论文也只描述了机制,没有列出改动清单。验证保证的是「这个数严格成立」,不保证方法可解释。验证代码和找到的解承诺开源,但成稿时仓库还在准备中。