Articles Systems
Fifty Years of Multiplying Matrices, and the Week a Machine Improved It
Strassen's 1969 algorithm went unbeaten for small matrices until a reinforcement learning system played the problem as a game. The result held up, mostly.
To multiply two 2-by-2 matrices, the definition requires eight multiplications and four additions. Every entry of the result is a sum of two products, and there are four entries.
In 1969 Volker Strassen showed it can be done with seven multiplications. His method uses more additions, which does not matter, because the construction is recursive. Apply it to blocks of a large matrix and you get an algorithm running in roughly n to the power of 2.807 rather than n cubed. For large matrices that gap is enormous.
Strassen's result was a shock. Everyone had assumed the obvious algorithm was optimal, and nobody had thought to check. It opened a research area that has run for fifty-five years and the exponent has been pushed down to around 2.371 through progressively more intricate constructions, none of which is practical.
For the specific case of 4-by-4 matrices, Strassen's method applied recursively gives 49 multiplications. That stood as the best known for over five decades.
Reframing as a game
In October 2022 a DeepMind team published AlphaTensor in Nature. Their move was to represent matrix multiplication algorithms as tensor decompositions and then treat finding a decomposition as a single-player game.
The bilinear map that multiplies two n-by-n matrices corresponds to a specific three-dimensional tensor. A decomposition of that tensor into R rank-one terms corresponds exactly to an algorithm using R multiplications. So minimising multiplications is minimising tensor rank, which is NP-hard in general and has an enormous search space.
The game: start with the target tensor. Each move subtracts a rank-one term. Reach the zero tensor and you win, with a score based on how few moves you used. This is now the same shape of problem AlphaZero handles, and the same machinery applies, with Monte Carlo tree search guided by a neural network trained through self-play.
The search space is far larger than chess or Go. The action space at each step is effectively infinite, requiring discretisation of the coefficient values. Training used synthetic examples generated by randomly decomposing tensors and presenting the result as a puzzle, which gives an unlimited supply of instances with known solutions.
The results
AlphaTensor rediscovered Strassen's algorithm for the 2-by-2 case, which is the expected sanity check.
For 4-by-4 matrices over the field with two elements, where arithmetic is modulo 2, it found a decomposition with 47 multiplications, beating the 49 that had stood since 1969. It also improved the known bounds for over 70 different matrix sizes.
It found a 5-by-5 algorithm using 96 multiplications, improving the previous best of 98.
The team also ran a variant that optimised for actual wall-clock runtime on specific hardware rather than for multiplication count, and found algorithms that ran measurably faster on TPUs and GPUs than the standard implementations, in the range of 10 to 20 percent for particular sizes.
The caveats, stated properly
The 47-multiplication result for 4-by-4 is over the field with two elements. That restriction matters. Arithmetic modulo 2 has properties that general fields do not, and the result does not automatically transfer to real or complex matrices, where 49 remained the record.
Within two weeks of publication, Manuel Kauers and Jakob Moosbauer at Johannes Kepler University Linz posted an improvement, finding a 5-by-5 decomposition with 95 multiplications using a different search method they had been developing. They were explicit that AlphaTensor's result prompted them to look again at a problem they had set aside.
Later work by the same group and others found further improvements, including a 4-by-4 algorithm over general fields using 48 multiplications, published in 2024, which finally beat Strassen's recursive bound in the general case.
So the honest history: a reinforcement learning system found a genuine improvement in a special case, and its publication triggered a burst of human work that produced further improvements by other methods within months.
What that sequence actually shows
Two readings are available and both have merit.
The deflationary reading: AlphaTensor was quickly outperformed by classical search methods that a small academic group implemented. The advance was real but narrow, and the field's response demonstrated that the problem was more tractable than fifty years of neglect had suggested.
The other reading: fifty years of neglect is the point. The problem sat because everyone assumed Strassen was optimal for small cases. A machine finding an improvement forced attention back onto it, and the subsequent human improvements would not have happened otherwise. Measuring the contribution only by the final record misses how the record moved.
Kauers has said something close to the second reading himself, noting that the AlphaTensor paper was what made him revisit the search.
The general lesson about search
Matrix multiplication algorithm discovery has properties that make it unusually amenable to this treatment, and they are worth listing because they tell you where else the approach might work.
The objective is a single number, the multiplication count, with no ambiguity about what better means.
Verification is instantaneous. Given a proposed decomposition, checking it is a tensor arithmetic computation. A wrong answer cannot survive.
Training data is free. You can generate valid decompositions by construction and use them as supervised examples.
The search space is discrete and combinatorial, with no continuous optimisation required once coefficients are discretised.
Any problem with those four properties is a candidate. Circuit minimisation has them. Some coding theory constructions have them. Certain combinatorial design searches have them. Problems that lack them, which is most of mathematics, are not addressable this way, and the absence of a crisp verifiable objective is usually what is missing.
Practical impact
Close to zero, so far, and it is worth being clear about that.
Real matrix multiplication libraries do not use Strassen's algorithm for most sizes. The reduced multiplication count is offset by worse memory access patterns, worse numerical stability, and the fact that highly tuned implementations of the naive algorithm exploit hardware in ways the recursive structure disrupts. Strassen becomes worthwhile only above a crossover point that depends on the machine, and even then it is used carefully.
The AlphaTensor variants that optimised directly for hardware runtime are more interesting practically, because they targeted the metric that matters. Whether they end up in production libraries depends on maintenance and numerical analysis work that is unglamorous and largely undone.
The result's significance is not that matrices multiply faster now. It is a demonstration that a well-posed mathematical search problem, with fast verification, can be handed to a reinforcement learning system and produce something a field had missed for half a century. That is a narrow claim and it is well supported.
Corrections and counter-arguments are welcome. Write to us through the contact page and we will publish the ones that change our mind.