AlphaTensor discovers new matrix multiplication algorithms

Google DeepMind published AlphaTensor, a reinforcement-learning system that discovered new algorithms for matrix multiplication, in a paper in Nature accompanying the DeepMind announcement. Multiplying matrices is one of the most heavily used operations in computing, underlying graphics, physics simulation and neural networks themselves, and the method taught to students uses more multiplications than known faster ones — a gap that has driven a decades-long, largely manual search for improvements since Volker Strassen’s 1969 algorithm.

DeepMind framed the search as a single-player game: a three-dimensional tensor representing the multiplication to be solved, with moves that decomposed it and a reward for reaching a correct decomposition in fewer steps. Built on the AlphaZero line of game-playing systems, AlphaTensor found an algorithm for multiplying a 4-by-5 matrix by a 5-by-5 matrix in 76 multiplications, four fewer than the best previously known method and the first improvement on Strassen’s specific case in more than fifty years. DeepMind also reported that some of the algorithms it found ran 10 to 20% faster on real hardware — an Nvidia V100 GPU and a Google TPU — when tuned for that hardware’s particular characteristics, rather than optimising only for an abstract, hardware-independent operation count.

AlphaTensor’s algorithms were mathematically proven correct by construction, rather than merely tested empirically, distinguishing the result from many machine-learning claims of the period. DeepMind applied the same approach the following year with AlphaDev, which reframed sorting-algorithm discovery as a comparable game and saw its output merged directly into a widely used C++ standard library — a further step from mathematical curiosity toward deployed infrastructure that AlphaTensor’s results had not themselves reached at the time of publication.