AlphaTensor discovers faster matrix multiplication algorithms, beating Strassen's 1969 record for 4×4 mod 2
DeepMind's AlphaTensor (Nature, Oct 2022) framed matrix multiplication as a tensor-decomposition game. It found a 4×4 algorithm over GF(2) with 47 multiplications (Strassen-based: 49) and improved 5×5 to 96. Human researchers cut 5×5 further to 95 within days.
Key facts
- 4×4 matrices in modular (GF(2)) arithmetic: 47 multiplications vs 49 from Strassen's 1969 method
- 5×5×5: 96 multiplications (from 98); Kauers & Moosbauer improved to 95 days later with a flip-graph method
- Found 14,236 non-equivalent 4×4 algorithms; also hardware-tuned algorithms faster on GPUs/TPUs
Science result
- Field
- computer-science / algebraic complexity
- Problem
- Minimum number of multiplications for small matrix products (tensor rank) (open since 1969)
- Result
- New lower-rank decompositions: 4×4 over GF(2) with 47 multiplications; improvements for several other sizes.
- AI system
- AlphaTensor
- Human role
- Autonomous search within a human-designed RL game
- Verification
- Peer-reviewed in Nature; algorithms checkable by direct computation
- Status
- confirmed
- Why surprising
- First improvement in over 50 years to a Strassen-era record for a small matrix size.
What happened
AlphaTensor, an AlphaZero descendant, searched the space of tensor decompositions and found matrix multiplication schemes using fewer scalar multiplications than any known for several sizes.
Why it matters
It was the first AI-found improvement to a famous algorithmic record. It prompted rapid human counter-improvements and led to AlphaEvolve's 48-multiplication complex 4×4 result in 2025.
Changelog
- 2026-09-29: created
Related events
- AlphaEvolve: Gemini-powered agent discovers new algorithms ★★★★
- AlphaDev discovers faster small-sort routines, merged into LLVM's C++ standard library ★★★
- AlphaEvolve helps lower the matrix multiplication exponent ω to below 2.371177 ★★★
Sources (3)
- paperDiscovering faster matrix multiplication algorithms with reinforcement learning (Nature)
- codeGitHub: google-deepmind/alphatensor
- discussionComputational Complexity blog on AlphaTensor
id: 2022-10-05-alphatensor-matrix-multiplication · updated 2026-09-29 · open in the interactive timeline