AlphaEvolve 与矩阵乘法

49 变成 48

两个 4 × 4 的矩阵相乘，照定义要做 64 次乘法。1969 年起，能一层层套用到更大矩阵上的做法，在实数和复数上最少用 49 次。2025 年 5 月，Google DeepMind 公布：AlphaEvolve 找到了一种 48 次的做法，系数是复数。

这些系数都是精确的，每一项都能核对。台上前排的七块、后排的八块、立方体和这块纪录牌，讲的是这一次乘法从哪里省出来，又是怎样被找到的。

4 × 4 · 1969 年起 49 次 · 2025 年 48 次，复数系数

八次乘法

先看 2 × 2。结果 C 的每个元素，是 A 的一行和 B 的一列对应相乘再相加：C₁₁ = A₁₁B₁₁ + A₁₂B₂₁。四个元素，每个两次乘法，一共 8 次乘法、4 次加法。

后排的八块，就是这八次乘法，一块一次。n × n 的矩阵照这个办法要做 n³ 次乘法：4 × 4 是 64 次，1000 × 1000 是十亿次。

2 × 2 照定义：8 次乘法 · 4 次加法 · n × n：n³ 次乘法

七次就够

1969 年，Strassen 发表了一种只用 7 次乘法的做法。先算七个乘积，比如 M₁ = (A₁₁ + A₂₂)(B₁₁ + B₂₂)：每个乘积的两边，各是 A 和 B 的元素相加或相减；再把这七个乘积加加减减，拼出 C 的四个元素。

代价是加减法变多了：从 4 次变成 18 次。前排的七块，就是这七个乘积。1971 年已经证明：不用乘法交换律的做法里，2 × 2 至少要 7 次乘法。

7 次乘法 · 18 次加减法 · 2 × 2 至少要 7 次（1971 年证明）

一块立方体

还可以换一种写法。把 A 的四个元素排在一条边上，B 的四个排在另一条边上，C 的四个排在竖直方向：一共 4 × 4 × 4 = 64 格。如果 A 的某个元素乘 B 的某个元素要加进 C 的某个元素，那一格就是 1，其余都是 0。

2 × 2 相乘，正好有 8 格是 1，就是那 8 次乘法。把立方体按 C 切成四层：最下面一层是 C₁₁，亮着的两格就是 A₁₁B₁₁ 和 A₁₂B₂₁。

4 × 4 × 4 = 64 格 · 8 格是 1 · 每一层是 C 的一个元素

一次乘法，一块

每一次乘法，在立方体里对应一块：A 的哪些元素相加、B 的哪些元素相加、结果加进 C 的哪些元素，三组系数相乘，填出一块带正负号的格子。一种做法，就是几块加起来正好等于这块立方体；块数就是乘法的次数。

Strassen 的七块一共占 32 格，有正有负。把它们放进立方体，12 格里一正一负互相抵消，剩下的正好是那 8 格。找更少的乘法，就是找更少的块。

七块 · 32 格 · 12 格正负抵消 · 剩下 8 格

一层一层省下来

省下一次乘法为什么要紧？Strassen 的做法从不调换乘法的前后次序，所以元素也可以是矩阵块。4 × 4 的矩阵可以看成 2 × 2 个 2 × 2 的块：外面一层做 7 次块乘法，每次块乘法里面再做 7 次，一共 7 × 7 = 49 次。

写成立方体也是这样：4 × 4 相乘是 16 × 16 × 16 格。按块给元素排好次序，64 个 1 正好分成 8 组，每组 8 格，组里和组与组之间都是 2 × 2 的那个图样。后面的水晶块里刻的就是它。

矩阵越大，层数越多，省得越多：n = 2ᵏ 时照定义要 8ᵏ 次，Strassen 要 7ᵏ 次，大约是 n 的 2.81 次方。1024 × 1024 时，前者约 10.7 亿⁠次，后者约 2.8 亿⁠次，少了约四分之三。

如果元素是可以调换次序的数，Winograd 1968 年的办法算 4 × 4 只要 48 次乘法；但它要调换次序，元素换成矩阵块就不对了，不能这样一层层套用。49 是能套用的做法里的纪录。

n = 2ᵏ：照定义 8ᵏ = n³ · Strassen 7ᵏ ≈ n^2.81 · 1024 × 1024：约 10.7 亿⁠次对约 2.8 亿⁠次

47，换了一种算术

2022 年，DeepMind 的 AlphaTensor 把拆立方体写成一个单人游戏，用强化学习去玩。它为 4 × 4 找到了 47 块的拆法，但只在模 2 的算术里成立：那里只有 0 和 1，1 + 1 = 0。

换回普通的数，这种拆法不成立。在实数和复数上，4 × 4 能套用的做法，仍是 Strassen 两层的 49 次。

AlphaTensor，2022 · 4 × 4：模 2 算术 47 次 · 普通算术仍是 49 次

改程序，再打分

AlphaEvolve 不直接拆立方体，它改的是一个程序。人先写好一个能运行的初始程序和打分的函数；一个程序库存着试过的程序和它们的分数。每一轮，从库里挑出程序写进提示，Gemini 2.0 Flash 和 2.0 Pro 两个语言模型提出改动，写成一段段“找到这几行，换成那几行”。

改好的程序交给评估程序，真的运行，按打分函数给分。分数好的存回库里，下一轮再改。台上的动画只是示意：三个候选依次放进立方体，红格是加起来不对的地方，纪录牌上 2 × 2 那一栏跟着这一轮最好的分数，从 8 变成 7。

对矩阵乘法，被改的是一个用梯度下降找拆法的程序：怎样初始化、损失怎样算、用什么优化器。评估时用不同的随机种子运行它，看它在一组尺寸上最少用几块；系数都取整到整数或半整数，保证拆法精确。搜索的是程序，不是一步棋；下棋的那种搜索，见“AlphaGo：搜索加上直觉”这一页。

程序库 → 提示 → 语言模型提出改动 → 运行、打分 → 好的存回库里

48 块

4 × 4 相乘的立方体有 16 × 16 × 16 = 4096 格，其中 64 格是 1，就是水晶块里的那 64 格。AlphaEvolve 找到的拆法有 48 块，系数只取 0、±½、±½i、±½ ± ½i 这九个值。

系数是公开的。我们用精确的算术把 48 块逐格加了一遍，4096 格都和立方体相同。系数里有 i，所以这些乘法要按复数来算。

论文说它是第一个找到这种做法的方法；不过 2024 年已有人用数值方法报告过一个复数系数的 48 次做法。2025 年 6 月，又有人把 AlphaEvolve 的这一个换成了只用有理数的 48 次做法，只要能除以 2 就能用。48 是不是最少，还没有人知道。

4 × 4：4096 格，64 格是 1 · 48 块 · 系数 0、±½、±½i、±½ ± ½i · 逐格核对相同

要有分数可打

这个循环能转，靠的是每个候选都能由程序自动打分：拆法对不对、用了几块，一算就知道。论文自己说，它的主要局限，就是只能处理写得出自动评估的问题。

同一套方法也用在了别处：Google 数据中心的一个调度规则，平均找回了约 0.7% 本来会闲置的算力；训练 Gemini 用的一个矩阵乘法内核，换了分块的规则，平均快了 23%，整个训练时间少了约 1%。这些都是别的程序，和 48 无关。

乘法少，也不等于实际更快。两层 Strassen 算 4 × 4，乘法 49 次，加减法却有 198 次，照定义只要 48 次加法；还要搬更多数据，舍入误差的界也更松。论文和发布文章都没有说 48 让哪个实际程序变快。专门做矩阵乘法的硬件，见“TPU 与脉动阵列”这一页。

只用于能自动打分的问题 · 4 × 4 两层 Strassen：49 次乘法、198 次加减法 · 照定义：64 次乘法、48 次加法

拆开来看

台上：2 × 2 乘法的立方体站在石阶上的黄铜底板上；前排石座上是 Strassen 的七块，后排高一级的是照定义的八块，两排间距相同，后排多出一格；右后方是纪录牌，立方体和纪录牌之间升起 4 × 4 乘法的水晶块。

乘法立方体 · 七块 · 八块 · 水晶块 · 纪录牌