When the Candidate Is an Algorithm: The Matrix-Multiplication Test
AlphaEvolve’s matrix-multiplication experiment is a demanding test of its central idea: can a language model help evolve the program that searches for an algorithm, rather than merely suggest a finished implementation? This case makes the question precise. The target is a lower-rank tensor decomposition, the candidate is a complete search program, and the evaluator must distinguish an approximate numerical improvement from an exact algorithm. The result is impressive, but its meaning depends on keeping those three layers separate.
Why matrix multiplication becomes a search over rank
Matrix multiplication is a basic operation inside many computational systems, but finding the fastest general algorithms for it is surprisingly difficult. The cost is not determined only by how many additions or lines of code an implementation contains. In the formulation used by AlphaEvolve, the central quantity is the number of scalar multiplications required to compute the product.
A matrix product can be described by a three-dimensional tensor that records how entries of the first matrix, entries of the second matrix, and entries of the output interact. A rank-one term in a decomposition of that tensor corresponds to one scalar multiplication, together with the additions and linear combinations needed to assemble the result. The rank of the decomposition therefore specifies the number of scalar multiplications in the resulting bilinear algorithm. Searching for a lower-rank decomposition is consequently a way of searching for a faster matrix-multiplication algorithm within this particular model.
The formulation gives the evaluator a crisp objective. For a target such as multiplying an m-by-n matrix by an n-by-p matrix, a candidate decomposition either reconstructs the required multiplication tensor or it does not. Among valid decompositions, lower rank is better. This is a much sharper feedback signal than asking a language model to “optimize matrix multiplication” in the abstract. It also exposes why the problem remains open: the space of possible decompositions is large, continuous during optimization, and full of solutions that may look numerically close without encoding an exact algorithm.
The paper notes that even the minimum rank for the simple case of multiplying two 3-by-3 matrices is unknown. That fact supplies the right context for the experiment. AlphaEvolve is not polishing an obviously inefficient loop. It is searching a difficult space in which decades of specialized solvers, custom search methods, and reinforcement-learning approaches had already made progress without resolving every target.
The case also has a useful denominator. “Faster” here means fewer scalar multiplications in the tensor-decomposition formulation, not necessarily fewer total operations on every processor or lower wall-clock time for every matrix shape. Additions, memory movement, numerical representation, and hardware behavior still matter in a deployed implementation. The matrix experiment is valuable precisely because it isolates a fundamental algorithmic quantity and asks whether evolutionary code search can improve it.
The starting point was already an algorithm searcher
AlphaEvolve did not receive a blank mathematical canvas. The researchers supplied a standard gradient-based program for learning a tensor decomposition. It included an initializer, a reconstruction-loss function, and an Adam optimizer.