Faster matrix-multiplication algorithms found by reinforcement learning
AlphaTensor discovered matrix-multiplication schemes using fewer scalar multiplications than any previously known, including a way to multiply 4×4 matrices over GF(2) in 47 multiplications versus the 49 of two-level Strassen.
- Model
- AlphaTensor (AlphaZero-based)
- Field
- Computer science
- Date
- 2022-10-05
- Problem posed
- 1969 · open 53 yrs
Sources
Original work
Announcement
Media coverage
What was found
AlphaTensor recast the search for matrix-multiplication algorithms as a single-player game of decomposing a 3-D tensor into rank-one terms, then trained an AlphaZero-style agent to play it. It matched or beat the best known rank for many matrix sizes, and over GF(2) found a 4×4 scheme using 47 multiplications, improving on the 49 obtained by applying Strassen's 1969 algorithm twice. Every decomposition it returns is an exact identity checkable by hand. Published in Nature.
Video explainers
Nothing loads from YouTube until you press play.
Novelty check
Fast matrix multiplication has an exhaustively catalogued literature going back to Strassen (1969) and Laderman (1976). AlphaTensor's schemes were checked against the standing per-size records; the 4×4 result over GF(2) was new at publication.
Caveats and known objections
The 4×4 improvement is specific to characteristic-2 arithmetic and the practical speedup is limited. Within about a week, Kauers and Moosbauer used a classical computer search to improve the 5×5 GF(2) case from AlphaTensor's 96 multiplications to 95, showing conventional methods remained competitive. 'Discovered' here means an RL search over decompositions, not an autonomous mathematical insight.
Independent checks
Kauers & Moosbauer (computer-algebra search): verified and shortly improved on the 5×5 case · link ↗
Disagree with these grades?
Bring a citation: a grade moves on evidence, not on argument.
Or on GitHub: submit a check challenge the grade send a correction or send a pull request
Flag this for triage
Signals order the review queue and nothing else. They are never published, and they never move a grade: that takes a citation.
Entry history (1 event)
- AddedEntered the registry graded Peer reviewed and Search scaffold.
Entries are never deleted. A grade that does not hold up is downgraded on the record, with the reason beside it.
Community discussion
Graded peer reviewed for verification and search scaffold for autonomy. What these mean.
Cite this entry
whataifound.org. (2022). Faster matrix-multiplication algorithms found by reinforcement learning. whataifound.org: A Registry of AI Scientific and Mathematical Discoveries. https://whataifound.org/finding/2022-10-05-alphatensorBibTeX
@misc{whataifound-googledeepmind-2022-alphatensor,
title = {Faster matrix-multiplication algorithms found by reinforcement learning},
author = {{whataifound.org}},
year = {2022},
howpublished = {whataifound.org: A Registry of AI Scientific and Mathematical Discoveries},
note = {Result by Google DeepMind. Verification: Peer reviewed. Autonomy: Search scaffold.},
url = {https://whataifound.org/finding/2022-10-05-alphatensor}
}