AlphaEvolve Cracks the Matrix Multiplication Exponent: ω < 2.371177

DeepMind’s AlphaEvolve team just did something that would have been unthinkable a decade ago: they used machine learning to tighten a fundamental bound in theoretical computer science.

A new note from a collaboration between DeepMind researchers (Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Balog) and leading complexity theorists (Zhou from CMU, Alman from Columbia, Vassilevska Williams from MIT) improves the upper bound on the matrix multiplication exponent ω from 2.371339 to 2.371177. The improvement is tiny — 1.62 × 10⁻⁴ — but in the world of ω, every decimal place is a war fought over decades.

The punchline: they used gradient descent and AlphaEvolve to solve a non-convex optimization problem that was previously considered too large to tackle. The result is a new bound that wouldn’t exist without ML.

What Is ω and Why Does It Matter?

Matrix multiplication is everywhere. Every training step of every model you’ve ever run, every graphics pipeline, every linear solve — they all trace back to multiplying matrices. The question: how many operations does it take to multiply two n×n matrices?

Naively: O(n³). Strassen (1969) showed it’s O(n^2.807). Over 55 years of incremental improvements, the exponent has been pushed down to 2.371339 — but the hard part isn’t proving existence; it’s solving the optimization problem at the core of the laser method, the only technique that has produced improvements in the past 40 years.

The laser method works by constructing a matrix multiplication algorithm indirectly — it’s an existence proof, not a practical algorithm. The “combination loss analysis” refinement (Duan et al. 2022; Williams et al. 2024; Alman et al. 2025) reformulates the bound as a non-convex optimization problem. Find a feasible solution, and you’ve proven ω is at most that value.

mindmap
  root((ω Timeline))
    Strassen 1969: 2.807
    Coppersmith-Winograd 1990: 2.376
    Williams 2012: 2.3729
    Le Gall 2014: 2.372863
    Alman-Williams 2020: 2.372859
    Duan-Wu-Zhou 2022: 2.371866
    Williams et al. 2024: 2.371552
    Alman et al. 2025: 2.371339
    This note: 2.371177
    

What Changed: ℓ* Goes to 5

The combination loss analysis has a parameter — the maximum recursion level ℓ* — that controls the complexity of the optimization. The problem grows doubly exponentially in ℓ*: at ℓ* = 3, the optimization involves tens of thousands of variables. At ℓ* = 4, it’s millions. At ℓ* = 5, it’s computationally infeasible with previous methods.

The previous SOTA bound (Alman et al. 2025) used ℓ* = 3. The authors of this note pushed to ℓ* = 5 by reformulating the problem into a differentiable form and applying gradient descent — a technique that scales to the larger problem. The key steps:

1. Reformulation: They rewrote the optimization problem so it could be solved in the larger setting of ℓ* = 5. This required restructuring the tree structure of the combination loss analysis to handle the exponentially larger parameter space.
2. Gradient descent: They made the objective differentiable and used standard ML optimization techniques (Adam, essentially) to find a feasible solution. This alone improved the bound by ≈ 0.97 × 10⁻⁴ (from 2.371339 to approximately 2.371242).
3. AlphaEvolve refinement: They fed the gradient descent solution into AlphaEvolve, which evolved the optimization algorithm itself to find better solutions. This raised the total improvement to ≈ 1.62 × 10⁻⁴, yielding ω < 2.371177.

The Numbers

Method	ω bound	Improvement
Alman et al. 2025 (ℓ* = 3)	2.371339	—
Gradient descent (ℓ* = 5)	~2.371242	+0.97 × 10−4
GD + AlphaEvolve (ℓ* = 5)	2.371177	+1.62 × 10−4

Each improvement is small, but the trajectory matters. The bound has been stuck at ~2.37 for over a decade. This is the first time ML has directly improved the theoretical exponent — as opposed to AlphaTensor, which found practical algorithms for specific matrix sizes but didn’t improve the asymptotic bound.

Limitations

• Not a practical algorithm: The laser method provides an existence proof, not a deployable algorithm. The constant factors are astronomical. ω < 2.371177 doesn’t mean your PyTorch matmul gets faster tomorrow.
• ℓ* = 5 is still small: The theoretically optimal ℓ* is much larger, but the doubly-exponential growth makes further scaling extremely difficult. The reformulation doesn’t solve the fundamental scaling problem.
• Rigorous verification is manual: The authors note that the optimization output requires a separate, rigorous verification step (Section 4). The feasible solution found by the optimizer must be checked by a formal proof. This is done manually and is not automated.
• AlphaEvolve contribution is opaque: The authors report that AlphaEvolve “improves our optimization algorithm,” but the specific changes it made — and whether they generalize to other optimization problems — are not analyzed in detail.
• Single improvement: This is one bound on one constant. The same approach may not generalize to other problems in the laser method or to other complexity-theoretic constants.

Why You Should Care

If you build infrastructure — compilers, ML frameworks, or hardware — the matrix multiplication exponent is your North Star. Every matmul kernel optimization, every tensor core design, every improvement in BLAS libraries is fighting for fractions of the exponent. The theoretical bound tells you how far you can go.

But the real story here is ML meeting complexity theory. The laser method’s optimization problem has been studied for 40 years by world-class mathematicians. The best they could do with hand-crafted solvers was ℓ* = 3. Gradient descent + AlphaEvolve got to ℓ* = 5 in a single paper. The implication is not that mathematicians are obsolete — it’s that the space of feasible optimization strategies just expanded dramatically.

For anyone building ML systems: this is the first time your own tools have turned around and improved the theoretical foundations of the hardware you run on. The loop is closing. What else in complexity theory is just a hard optimization problem waiting for the right gradient?