Source-linked AI summary
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
TL;DR
Determining the computational complexity of matrix multiplication remains a major open problem. This note improves the optimization underlying combination loss analysis with gradient descent and AlphaEvolve, obtaining the bound ω < 2.371177.
Problem
The computational complexity of matrix multiplication remains unknown, making its determination a major open question in theoretical computer science.
Method
The paper reformulates and numerically solves the combination-loss optimization using gradient descent and AlphaEvolve, enabling optimization at recursion level ℓ*=4.
Results
ω < 2.371177, improving the previous state-of-the-art bound by approximately 1.62 × 10^-4.
Takeaways & Limitations
Modern optimization techniques and AlphaEvolve yield a modest improvement to the matrix multiplication exponent bound, while larger gains likely require new mathematical ideas.
Takeaways & Limitations
The formulation adopts the convention 0·undefined := 0 so that its derived equations remain well-defined.
Abstract
from arXiv · showhide
The current best bounds on the matrix multiplication exponent $ω$ are obtained through a refinement of the laser method called combination loss analysis (Duan et al., 2022; Williams et al., 2024; Alman et al., 2025). In this note, we address the optimization problem at the core of this approach and propose several improvements. First, we reformulate the optimization problem allowing us to solve it in a larger setting than was previously possible. Second, we leverage recent advances in machine learning to design a new optimization algorithm for this problem. Finally, we refine the resulting optimization algorithm with AlphaEvolve. Our combined approach yields an upper bound of $ω$ < 2.371177, improving the previous best bound of 2.371339.
1. Introduction
This note improves the matrix multiplication exponent bound to ω < 2.371177 through gradient-based optimization and AlphaEvolve refinement. It addresses the optimization problem underlying combination loss analysis and describes numerical solution and rigorous certification of the resulting bound.
- Matrix multiplication complexity remains unknown despite its fundamental role in applications and its importance as an open theoretical computer science problem.
- Strassen’s work established sub-cubic matrix multiplication, with O(n^ω+o(1)) operations for ω < 2.81, prompting continued efforts to reduce ω.
- ω < 2.371177 is achieved in two steps: gradient descent improves the previous SOTA by ≈0.97 × 10^-4, and AlphaEvolve raises the improvement to ≈1.62 × 10^-4.
- The approach targets a revised combination-loss optimization problem, whose recursion parameter ℓ* trades off doubly exponential optimization complexity against the best achievable bound on ω.The previous SOTA used ℓ* = 3, while the new gradient-based optimization is implemented in Jax.
- The note details the optimization problem, its numerical solution, AlphaEvolve’s application, and rigorous certification of the resulting ω bound.
2. Optimization problem
The optimization problem is represented by a rooted tree that recursively decomposes the Coppersmith–Winograd tensor, with node-specific shapes, regions, and optimizable distributions. A feasible solution determines all remaining quantities and implies an upper bound on the matrix multiplication exponent.
- Tree structure: The rooted tree recursively decomposes the Coppersmith–Winograd tensor, with fixed hyperparameters q≥1 and ℓ*≥2.Each node carries a collection of optimizable parameters.
- Tree structure: Each non-root node has a level ℓ∈{2, …, ℓ*}, a shape of three non-negative coordinates summing to 2ℓ, and one of six permutation-indexed regions.The root G has no level, shape, or region; its children include every level-ℓ* shape and region.
- Tree structure: Positive-shape nodes at level ℓ≥3 branch over regions and shapes in Split(s_T), while zero-shape and level-2 positive-shape nodes are leaves.A child’s region may differ from its parent’s region.
- Optimizable parameters: The free variables are distributions over regions and shapes or splits at the root and positive-shape nodes, complete split distributions at zero-shape nodes, and μ_T∈[0, 1/2] at level-2 nodes.Zero-shape parameters are indexed by the first nonzero dimension, while level-2 nodes have only the scalar μ_T.
- Derived quantities: With free variables fixed, masses, complete split distributions, and retained exponents are computed deterministically through the tree using base-two logarithms and entropies.The retained exponent is aggregated from intermediate quantities at the root and at positive-shape nodes of levels ℓ≥3.
- Optimization guarantee: Any feasible solution of Equation (11) implies ω≤Ω for the asymptotic matrix multiplication exponent.The retained exponent Ω is the quantity constrained by the optimization problem.
3. Solving the optimization problem numerically
The authors numerically minimize Ω under the stated constraints using a gradient-based, machine-learning-informed approach, then refine the optimizer with AlphaEvolve. They parameterize distributions for unconstrained optimization, differentiate through Sinkhorn-Knopp, and implement a parallelizable Jax computation for ℓ*=4.
- Optimization formulation: q=5 and ℓ*=4 define the optimization setting, replacing Alman et al.’s SQP/SNOPT approach with gradient-based optimization.The algorithm incorporates techniques from machine learning and adjacent areas, including optimal transport.
- Differentiable optimization: Logit parameterization converts probability-distribution constraints into an unconstrained optimization problem.This addresses non-negativity and normalization constraints while enabling a differentiable objective.
- Differentiable optimization: Sinkhorn-Knopp computes maximum-entropy distributions sharing prescribed marginals, providing a stable differentiable treatment of those constraints.This draws on the connection to optimal transport and differs from Alman et al. (2025)’s treatment.
- Differentiable optimization: Automatic differentiation, implicit differentiation through Sinkhorn-Knopp, and Adam updates form the optimization procedure.Implicit differentiation is used to improve stability when backpropagating through Sinkhorn-Knopp.
- Implementation: ℓ*=4 involves nearly 7 million parameters, motivating a Jax implementation that replaces graph-node loops with naturally parallelizable tensor computations.The new representation is designed to leverage hardware platforms such as GPUs and improve efficiency.
- AlphaEvolve refinement: AlphaEvolve evolves the optimization program to minimize omega, with each run taking approximately 5 hours on a single GPU.Improved results came from the “evolving constructions” feature, which initializes each generation at the parent algorithm’s best solution point.
4. Rigorous verification of the omega upper bound
The omega bound is rigorously certified through a separate verification step using rational arithmetic throughout. The procedure rounds the optimized floating-point solution and bounds logarithms in the proper direction to preserve valid certificates.
- A separate verification step computes all quantities in rational arithmetic to guard against floating-point errors.
- The floating-point optimization solution is rounded to rational numbers so the maximum-entropy certificates remain valid.
- Derived quantities are evaluated exactly, while logarithms are replaced with rational bounds rounded in the proper direction.
5. Discussion
The note improves the state-of-the-art upper bound on ω to 2.371177 by using modern optimization techniques and AlphaEvolve to design a better optimization algorithm. The authors suggest that further improvements may be modest, while larger gains likely require new approaches.
- Discussion: 2.371177 is the note’s improved state-of-the-art upper bound on ω.The improvement is described as comparable in magnitude to most advances over the last 40 years since ω < 2.376 was attained in 1990.
- Discussion: Modern optimization techniques and AlphaEvolve produce a better optimization algorithm for the problem described by Alman et al. (2025).
- Discussion: The authors expect further improvements from this approach to be modest, while larger improvements to ω likely require new methods.