用现代优化与 AlphaEvolve 改进矩阵乘法指数 Improving the matrix multiplication exponent with modern optimization and AlphaEvolve
梯度优化加 AlphaEvolve 把矩阵乘法指数上界降到 2.371177
前置知识
矩阵乘法指数 $\omega$
刻画两个 $n\times n$ 矩阵相乘所需算术运算次数的增长速率，即 $O(n^{\omega+o(1)})$。教科书算法对应 $\omega=3$；Strassen 在 1969 年给出首个次三次方算法，证明 $\omega<2.81$。此后上界不断被压低，但 $\omega$ 的精确值至今未知，是理论计算机科学最著名的开放问题之一。
本文的全部目标就是压低 $\omega$ 的上界，从 2.371339 降到 2.371177，所有方法、约束和验证步骤都围绕这个量展开。
激光方法（laser method）
过去 40 年所有 $\omega$ 上界改进依赖的间接构造技术：不直接写出矩阵乘法算法，而是把大张量（如 Coppersmith–Winograd 张量 $CW_q^{\otimes N}$）递归分解成许多小张量，对每块套用已有的快速算法，再从分解结构中推导出渐近指数。Strassen 1986、Coppersmith–Winograd 1990 以及此后的所有改进都在此框架内。
本文优化的对象正是激光方法最新变体的核心问题，论文中的树状递归分解结构就是激光方法分解的数学化描述。
组合损失分析（combination loss analysis）
激光方法的精细化，目前最强的上界技术（Duan et al. 2023；Williams et al. 2024；Alman et al. 2025）。它把“分解方案好不好”化成一个非凸优化问题：只要找到一组满足约束的可行参数，就能证明一个 $\omega$ 上界。此前用序列二次规划软件 SNOPT 求解，$\ell_*=3$ 时得到 2.371339。
本文没有发明新的代数构造，而是直接攻击这个优化问题——它是理解本文贡献的出发点，也是唯一被改进的环节。
熵与最大熵约束 $H^{\max}$
对有限支撑分布 $\rho$，熵 $H(\rho)=-\sum_x \rho(x)\log\rho(x)$（以 2 为底）。文中反复需要求“固定三个边际时熵最大的分布”，记作 $H^{\max}_D(\rho)$，惩罚项 $P_D(\rho)=H^{\max}_D(\rho)-H(\rho)$ 度量分解造成的损失，是目标函数的关键组成。$H^{\max}$ 没有解析解，需数值求解并严格界定。
它既是优化算法要处理的内层子问题（用 Sinkhorn-Knopp 解），又要在认证阶段用拉格朗日乘子证书严格上界（Lemma 1），贯穿全文。
Sinkhorn-Knopp 算法
最优传输中的经典迭代算法（Sinkhorn & Knopp 1967）：通过交替做行、列归一化，收敛到熵正则化的最优耦合，天然可微。Cuturi 在 2013 年用它把最优传输变成可扩展的机器学习工具。本文用它求固定边际的最大熵分布及对应拉格朗日乘子。
本文用它替代把最大熵分布当作自由变量的做法，使整个目标端到端可微、可以用自动微分和梯度下降训练。
隐式微分
当目标由某个内部迭代算法（如 Sinkhorn-Knopp）的收敛解定义时，不展开迭代记录计算图反传，而是利用收敛解满足的最优性条件直接推导它对输入参数的梯度（Cuturi et al. 2020；Eisenberger et al. 2022），更省显存也更稳定。
$\ell_*=4$ 时有约 700 万个参数，直接展开 SK 迭代反传代价极高；隐式微分是本文能把问题规模扩大一层的关键工程手段之一。
AlphaEvolve
Google DeepMind 的进化式代码搜索系统（Novikov et al. 2025）：用大模型变异程序代码，按适应度筛选并进化种群，此前已改进过复数乘法等多种算法。本文让它在 evolving constructions 模式下进化优化程序本身：每一代的优化算法都从父代找到的最优解点出发继续训练。
本文提升量的后半段（从约 $0.97\times10^{-4}$ 到约 $1.62\times10^{-4}$）完全来自 AlphaEvolve 改写优化代码，是“AI 设计算法”路线的代表性案例。
研究动机
矩阵乘法是机器学习加速、计算机图形学等关键应用的基础运算，但其复杂度 $O(n^{\omega})$ 中 $\omega$ 的精确值 50 多年来悬而未决。自 Strassen (1969) 证明 $\omega<2.81$ 以来，40 年间所有改进都依赖激光方法；当前最佳上界 2.371339 由其精细化版本“组合损失分析”给出（Alman et al. 2025），该方法把计算机辅助证明归约成一个非凸优化问题。这个优化问题带一个参数——最大递归层数 $\ell_*$——它控制优化复杂度与上界质量之间的权衡：问题规模随 $\ell_*$ 双重指数增长，可优化变量从 $\ell_*=3$ 时的约 2.5 万个暴涨到 $\ell_*=4$ 时的约 700 万个。此前基于序列二次规划（SQP）的 SNOPT 求解器只能处理 $\ell_*=3$，而更大的 $\ell_*$ 潜藏着更好的上界，于是“求解器能力不足”成了压低 $\omega$ 的直接瓶颈。
本文的目标是本文的目标非常聚焦：不动激光方法的代数框架，纯粹通过改进组合损失分析的核心优化问题来压低 $\omega$ 上界。具体分三步：第一，重新表述优化问题，使求解能扩展到此前不可行的更大设置（$q=5$、$\ell_*=4$）；第二，利用机器学习和最优传输等相邻领域的最新进展，设计全新的基于梯度的优化算法，替换传统 SQP；第三，用 AlphaEvolve 进化改写这个优化算法本身，进一步榨取解的质量；最后把浮点解取整并在严格的有理数算术下重新验证所有约束，目标是把 $\omega<2.371339$ 推向更低。
与已有工作不同的是，此前社区的精力几乎都花在发明新的代数构造（新张量、新分解）上，优化器只是辅助工具，用的仍是传统 SQP 软件。本文的独特切入点是承认“好上界来自好优化”：把可扩展性当作纯粹的数值优化与软件工程问题来攻坚——用 softmax 参数化消掉单纯形约束、用 Sinkhorn-Knopp 解最大熵子问题、用张量化表示替代图上消息传递以获得 GPU 并行能力，并首次把 LLM 驱动的进化代码搜索（AlphaEvolve）引入 $\omega$ 上界证明流程。这条“现代优化 + AI 代码进化”的路线与以往的数学构造式改进完全互补，也让计算机辅助证明的求解器第一次用上了深度学习基础设施。
核心方法
整个方法围绕一个由有根树描述的非凸优化问题展开：树递归描述如何把 Coppersmith–Winograd 张量 $CW_q^{\otimes 2^{\ell_*} q}$ 分解成小张量，每个节点携带可优化的分布参数。直觉上，只要找到一组参数使约束 $E_{\mathrm{total}} + M_{\mathrm{total}}\cdot\Omega \ge 2^{\ell_*-1}\log(q+2)$ 成立（$E_{\mathrm{total}}$ 为各层保留指数之和，$M_{\mathrm{total}}$ 为叶节点局部矩阵大小的最小值），就证明了 $\omega\le\Omega$。技术路线上：分布用 logits 加 softmax 无约束参数化；最大熵子问题交给 Sinkhorn-Knopp 迭代求解并用隐式微分回传；目标用 Jax 实现，享受自动微分与 GPU 并行，外层用 Adam；再把整段优化程序交给 AlphaEvolve 进化改写；最后对浮点解取整并在有理数算术下严格验证。$q=5$、$\ell_*=4$ 时约 700 万个参数，单 GPU 一次运行约 5 小时。
核心创新有两点。其一，问题的可微化重构：原问题的两类约束被分别消掉——概率单纯形约束用 logits + softmax 参数化处理；最大熵 $H^{\max}_D(\rho)$ 及其拉格朗日乘子不再像 Alman et al. (2025) 那样作为自由变量与其它分布一起优化，而是视为 Sinkhorn-Knopp 内层迭代的收敛解，用隐式微分回传。这得到一个无约束、端到端可微的目标。其二，计算表示的根本改造：从“图节点上存参数、靠消息传递更新 + SQP”换成“多维张量上的并行计算 + Adam”——引入带掩码的幻影节点（代价是参数最多增加 3 倍），并把节点聚成少量高度特化的 stage，最终把整张图表示成最多 10 个轴的张量运算，逼近张量后端的能力极限，从而使 $\ell_*=4$（约 700 万参数）在硬件上真正可解。
方法步骤详情
第一步，建树并参数化：固定 $q=5$、$\ell_*=4$；根节点 $G$ 为每个区域和每个 level-$\ell_*$ 形状 $s$（三个非负坐标和为 $2^{\ell_*}$）生成子节点；正形状节点继续分裂，其余为叶；所有分布与标量 $\mu_T$ 用 logits 随机初始化。第二步，前向计算：自上而下递推质量 $m_T$（$m_G=1$，子节点按 $A^{(r)}\alpha^{(r)}$ 分配），自下而上拼完整分裂分布；逐层算熵、惩罚与保留指数，求和得 $E_{\mathrm{total}}$；叶节点局部矩阵大小取最小得 $M_{\mathrm{total}}$。第三步，内层：Sinkhorn-Knopp 求固定边际的最大熵分布，隐式微分反传。第四步，外层：Adam 最小化 $\Omega$，单 GPU 约 5 小时。第五步，AlphaEvolve 以 $\omega$ 上界为适应度改写优化程序，每代由父代最优解热启动。第六步，认证：浮点解取整为有理数并保持熵证书有效，对数用有理界替代，得 $\omega<2.371177$。
技术新颖性
新颖性体现在三个层面。数学层面：把最大熵子问题从“优化变量”降格为“内层收敛解”，并配合 Lemma 1 的证书结构——分布 $y$、乘子 $\lambda_0$ 与 $\lambda_W(w)$、误差 $\varepsilon$，满足 $\log y(a)-(\lambda_0+\lambda_X(a_X)+\lambda_Y(a_Y)+\lambda_Z(a_Z))\le\varepsilon$，从而 $H(y)\le H^{\max}_D(\rho)\le H(y)+2\varepsilon$——既缩小搜索空间又保留严格验证路径；同时首次把该问题解到 $\ell_*=4$。工程层面：幻影节点加掩码、节点聚类成 stage、张量化表示，把不规则的图计算变成 GPU 友好的稠密张量流水线，属于把深度学习基础设施移植进计算机辅助证明的少见实践。AI 层面：AlphaEvolve 的角色不是发明新数学，而是进化数值优化代码本身，并用“每代从父代解热启动”的 evolving constructions 把进化搜索与梯度下降串成双层循环，这个用法在 $\omega$ 上界研究史上是第一次。
实验结果
最终成果是把 $\omega$ 的认证上界从 2.371339 降到 2.371177，总改进量约 $1.62\times10^{-4}$。两个阶段贡献分明：仅用新的梯度优化算法（$q=5$、$\ell_*=4$、约 700 万参数、Jax 实现）就比此前 SOTA 改进约 $0.97\times10^{-4}$；再用 AlphaEvolve 进化优化算法后，累计改进达到约 $1.62\times10^{-4}$。对照近几次改进：Duan et al. (2023) 得 2.371866，Williams et al. (2024) 得 2.371552，Alman et al. (2025) 得 2.371339，本文 2.371177——单步下降幅度与 Coppersmith–Winograd 1990 年 $\omega<2.376$ 之后 40 年里的大多数单步改进相当。所有数值都经过独立验证步骤：浮点解取整为有理数、最大熵证书保持有效、对数用方向正确的有理界替代，认证结果不含浮点误差。作者同时明确：继续沿这条路只能获得小幅改进，更大的改进需要新的数学思想。
查看结构化数据
| 任务 | 指标 | 本文 | 基线 | 提升 |
|---|---|---|---|---|
| 组合损失分析优化问题（$q=5$、$\ell_*=4$）的矩阵乘法指数上界 | 严格认证的 $\omega$ 上界 | 2.371177 | 2.371339（Alman et al. 2025，$\ell_*=3$ + SNOPT） | 降低约 $1.62\times10^{-4}$ |
| 梯度优化算法（未用 AlphaEvolve）单独求解 | 相对此前 SOTA 的上界降低量 | 约 $0.97\times10^{-4}$ | SNOPT/SQP 在 $\ell_*=3$ 下可达的最优 | 单步即可比肩历史上多数单步改进 |
| 问题规模扩展 | 可优化参数数量 | $\ell_*=4$ 时约 700 万个，单 GPU 约 5 小时 | Alman et al. 2025 仅能解 $\ell_*=3$（约 2.5 万参数） | 可解规模扩大逾百倍 |
局限与改进
作者自己承认：靠改进优化求解器获得的提升幅度有限，与 Coppersmith–Winograd (1990) 以来的多数单步改进同量级，要显著压低 $\omega$ 需要全新的数学思想，而不是更快地搜同一个问题的解。从我的观察看还有几点：其一，改进依赖 $\ell_*=4$ 这个特定设置，$\ell_*=5$ 时参数量将再次双重爆炸，方法本身并未给出可扩展性的通解；其二，约 700 万参数的非凸优化本质上是在巨大非凸景观中找好局部解，论文没有理论保证所得解接近全局最优，改进里可能含运气成分（AlphaEvolve 的贡献尤其如此）；其三，认证流程要求取整后最大熵证书仍然有效，这一步的鲁棒性与失败重试策略文中未详述；其四，$10^{-4}$ 量级的理论改进对实际规模的矩阵运算没有可感知影响，意义纯粹在于理论认知。
独立分析的弱点
第一，问题表示与硬件耦合过紧：幻影节点带来最多 3 倍冗余参数、10 轴张量已经“挑战后端极限”，说明当前表示逼近天花板，$\ell_*=5$ 需要全新表示；改进方向是研究分解树的对称性与条件独立性，做精确的稀疏或分块分解，而非用掩码把结构补成规则张量。第二，缺乏全局最优性度量：论文无法回答 2.371177 距离该问题在 $\ell_*=4$ 下的最优可行值还有多远，可以引入对偶问题给出下界，或用多次随机重启的解分布估计搜索潜力。第三，AlphaEvolve 环节成本与统计不透明：单次优化约 5 小时 GPU，但进化代数、种群规模、变异样本量均未报告，无法评估改进的显著性；可换成可控的算法配置搜索（如贝叶斯优化）并做多次重复实验。第四，验证代码与解在论文写作时“仓库正在准备中”尚未发布，而计算机辅助证明的可信度高度依赖验证代码的可审计性。
未来方向
作者提出的方向：发布验证代码与解的仓库；承认此路线只能带来温和改进，更大的 $\omega$ 改进需要新的数学思想并称之为激动人心的开放方向。可以延伸的方向：其一，把 $\ell_*$ 推到 5，或系统绘制上界随 $\ell_*$ 的收敛曲线，估计组合损失分析的渐近极限究竟在哪；其二，把 AlphaEvolve 的搜索空间从“优化算法代码”扩大到“分解树结构本身”，让 AI 直接提议新的代数构造，而不只是在固定问题上调优化器；其三，把 Sinkhorn-Knopp + 隐式微分 + Adam 的可微化框架复用到其他计算机辅助证明中的非凸问题，例如 Coppersmith–Winograd 族之外的张量分解和其他 laser method 变体；其四，研究理论上界改进与数值稳定的实用快速矩阵乘法算法之间的桥梁，让理论指数下降有朝一日转化为实际收益。
复现评估
论文是 10 页的 note，方法描述相当完整：优化问题形式化在 Alman et al. (2025) 中，本文补足了数值求解全部关键细节（softmax 参数化、Sinkhorn-Knopp、隐式微分、Adam、幻影节点、stage 聚类）和认证方法（Lemma 1 证书 + 有理数算术），理论上可复现。但当前实际可复现性有限：作者声明“正在准备一个仓库”发布验证代码与发现的解，截至成文尚未发布；AlphaEvolve 是闭源系统，第三方无法原样重跑进化环节，只能用普通超参搜索近似。算力门槛不高：优化在单 GPU 上约 5 小时，认证是纯 CPU 有理算术；真正的难点在于正确实现约 700 万参数的张量化前向计算以及取整认证逻辑。若官方解与验证代码发布，复核结果是可行的；从头独立复现整条管道预计需要数周工程量。
论文图表