DeepMind turned matrix multiplication into a one-player game and beat a 50-year record

Ars Technica reported in October 2022 that DeepMind had found a more efficient way to multiply matrices, beating a 50-year-old record. In 1969 Volker Strassen found an algorithm that multiplies two 4x4 matrices in 49 multiplications instead of 64 by the schoolroom method. Using a neural network called AlphaTensor, DeepMind found a way to do it in 47, and published in Nature.

DeepMind set the problem up as a single-player game. The 'board' is a three-dimensional tensor capturing how far the current algorithm is from correct; the allowed moves correspond to algorithm instructions, and the player tries to zero out the tensor's entries. Doing so yields a provably correct algorithm for any pair of matrices, with efficiency captured by the number of steps. Trained by reinforcement learning, like AlphaGo, AlphaTensor first rediscovered Strassen's work and that of other mathematicians, then surpassed them, per DeepMind.

For 5x5 matrices AlphaTensor found a 96-step method against 98 for the older one. A week later Manuel Kauers and Jakob Moosbauer of Johannes Kepler University Linz reported 95, writing that their solution was obtained from DeepMind's scheme by a sequence of transformations that eliminated one multiplication. Ars notes that matrix multiplication sits under speech and image recognition and graphics, and that trillions of such calculations run on GPUs every day, so small savings can add up.

A correct algorithm is a tensor reduced to zero, so correctness is built into the game's rules.

The number of steps used is a clean score, so the AI can learn which moves lead to shorter algorithms.

Matrix multiplication is so widely used that even going from 49 to 47 steps matters at GPU scale.

Publishing the discovered scheme let human researchers build on it within a week.

If a research problem can be framed as a game with a clear score, a game-playing AI can search it, and its results can seed further human improvement.

A week after DeepMind's announcement, the two Austrian researchers claimed a 95-multiplication scheme for 5x5 matrices, building on DeepMind's. Ars speculated that with AI now searching for new algorithms, other longstanding math records could fall soon.