This paper presents AlphaTensor, a deep reinforcement learning agent based on AlphaZero, designed to discover efficient and provably correct algorithms for matrix multiplication. AlphaTensor formulates the problem as a single-player game, TensorGame, where the goal is to find tensor decompositions. The agent surpasses state-of-the-art complexity for many matrix sizes, notably improving upon Strassen's algorithm for 4x4 matrices in a finite field for the first time in 50 years. AlphaTensor's flexibility is demonstrated through applications to structured matrix multiplication and hardware-specific optimizations, achieving improved practical efficiency.

Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J. R. Ruiz, Julian Schrittwieser, Grzegorz Swirszcz, David Silver, Demis Hassabis, Pushmeet Kohli