Improving the matrix multiplication exponent with modern optimization and AlphaEvolve
2026-08-17 • Data Structures and Algorithms
Data Structures and AlgorithmsArtificial IntelligenceComputational ComplexityMachine Learning
AI summaryⓘ
The authors studied a complex math problem about how fast we can multiply matrices, measured by a number called the matrix multiplication exponent (ω). They improved the way this problem is solved by changing how the problem is set up and by using new techniques from machine learning. Additionally, they refined their method using a tool called AlphaEvolve. Together, these improvements helped them find a slightly better upper limit for ω, making the estimate more accurate than before.
matrix multiplication exponentlaser methodcombination loss analysisoptimization problemmachine learningAlphaEvolveupper boundmatrix multiplicationalgorithms
Authors
Emilien Dupont, Marvin Eisenberger, Borislav Kozlovskii, Abbas Mehrabian, Francisco J. R. Ruiz, Abigail See, Renfei Zhou, Josh Alman, Virginia Vassilevska Williams, Matej Balog
Abstract
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.