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
Differentiable optimization at 7 million parameters plus AlphaEvolve-tuned solvers cut the matrix multiplication exponent bound from 2.371339 to 2.371177.
Multiplying two n×n matrices naively costs n³ operations. Since Strassen's 1969 block-trick algorithm pushed below 2.81, the matrix multiplication exponent ω has been one of the oldest open problems in theoretical computer science. The lower bound is 2 (the output alone has n² entries) and the conjecture is ω=2. Every upper-bound improvement in the past 40 years has come from the laser method, which never constructs an algorithm directly but bounds ω by analyzing properties of the Coppersmith-Winograd tensor.
The latest refinement, combination loss analysis (Duan et al., 2023), turns “find a better algorithm” into “solve a non-convex optimization problem”: any feasible solution certifies an upper bound on ω. The bottleneck then moved from mathematics to computation. The parameter count grows doubly exponentially with the recursion depth ℓ, and the previous best bound of 2.371339 (Alman et al., 2025) was obtained with an SQP solver (SNOPT) at ℓ=3, about 25k parameters. ℓ=4 means roughly 7 million parameters, out of reach for that pipeline.
A Google DeepMind team with collaborators from CMU, Columbia and MIT pushed in three steps.
First, a reformulation built for scale. The previous implementation stored free parameters on graph nodes updated by message passing, and the graph was too irregular to parallelize. The new one adds masked phantom nodes that pad the graph into regular tensors, at the cost of up to 3× more parameters, and clusters nodes into a few highly specialized “stages”. The whole problem is rewritten in JAX with up to 10 parallel axes; one full optimization takes about 5 hours on a single GPU, which is what makes the 7 million parameters of ℓ=4 tractable.
Second, a new solver assembled from standard deep learning parts. Distributions are parameterized by logits passed through softmax, turning constrained optimization into unconstrained optimization. Maximum-entropy distributions are no longer free parameters optimized alongside everything else (the choice in Alman et al., 2025); they are computed directly with the Sinkhorn-Knopp iteration borrowed from optimal transport, and implicit differentiation backpropagates through it stably. Updates use Adam.
Third, AlphaEvolve improves the algorithm itself. It does not search over solutions; it evolves the solver program. One run takes roughly 5 hours and outputs a bound on ω, which serves as the fitness. The “evolving constructions” feature warm-starts each generation from the best solution found by the parent algorithm instead of starting from scratch.
| Source | ω upper bound |
| Duan et al. 2023 | 2.371866 |
| Williams et al. 2024 | 2.371552 |
| Alman et al. 2025 | 2.371339 |
| This work | 2.371177 |
Settings: q=5, ℓ=4. The gradient-based optimizer alone improves the bound by about 0.97×10⁻⁴; AlphaEvolve raises the total improvement to about 1.62×10⁻⁴. By the paper's own account, this is comparable in magnitude to most single improvements since Coppersmith and Winograd reached 2.376 in 1990.
The result is not merely numerically plausible. A separate verification step rounds the floating-point solution to rationals, recomputes every derived quantity in exact rational arithmetic, and replaces each logarithm with a rational bound rounded in the safe direction, so every constraint provably holds without floating-point error.
The division of labor is the real deliverable: humans supply the framework (Theorem 1, any feasible solution bounds ω), machine learning finds the solution, an LLM code-evolution system improves the solver, and exact rational arithmetic certifies the final claim. Any mathematical question phrased as “feasible point in, certificate out” can reuse this pipeline.
For combination loss analysis specifically, the tractable scale jumps from 25k to 7 million parameters, more than an order of magnitude more search space, with the engineering path paved for whoever digs next.
The cold water: ω is an asymptotic exponent. 2.371177 changes nothing for practical matrix multiplication; such constructions only win at astronomically large n, and even Strassen's algorithm is rarely used in production. The audience here is complexity theory, not GPU kernels.
The authors state it plainly: further modest improvements may come from this route, but larger jumps likely require new mathematical ideas. Against the distance between 2.371177 and the conjectured value of 2, a gain of 1.62×10⁻⁴ is a small step.
The solution itself is a numerical point with about 7 million parameters. The paper offers no human-readable structure and cannot answer why this solution is good, nor does it list the specific changes AlphaEvolve made to the solver beyond describing the mechanism. Verification certifies that the number is correct, not that the method is interpretable. The verification code and the discovered solution are promised as open source, but the repository was still in preparation at submission time.