AlphaTensor
A reinforcement learning agent plays a tensor decomposition game with Monte Carlo Tree Search to discover faster exact matrix multiplication algorithms.
The loop
- Proposes
Rank-1 tensor factors (triplets of vectors u, v, w) proposed by a neural policy and value network
- Judged by
Exact algebraic tensor subtraction and Monte Carlo Tree Search that checks whether the residual tensor reaches zero
- Steers
Completed zero-residual decompositions and synthetic tensor demonstrations train the network and guide further tree search
Headline result
In Nature (2022), AlphaTensor discovered a 4x4 matrix multiplication algorithm using 47 multiplications in modulo-2 arithmetic (Z_2), beating Strassen's 1969 construction of 49 in that field, and improved the best known rank across more than 70 matrix sizes up to 5x5. By adding hardware runtime to the reward, it also found algorithms 10% to 20% faster than human and compiler baselines on NVIDIA V100 GPUs and Google TPU v2.
What this does not prove
The 47-multiplication 4x4 result holds in Z_2 (modulo-2 arithmetic); in standard arithmetic on 4x4 matrices AlphaTensor matched Strassen's 49 and improved larger sizes such as 5x5 (96 vs 98). Each tensor decomposition verifies exact algebraic identity only for the fixed matrix dimensions tested.
How it generalizes the harness
- The algorithm is the solver
- Inverted control
- A domain authority judges
- Feedback retrains the generator
- Search over a population
- The generator is not an LLM
- The output outlives the model
- AI at design time
- Intra-algorithmic surgery (inside the while-loop)
Monte Carlo Tree Search and exact tensor algebra run the search, train a custom torso-policy-value network rather than an LLM, and output an exact multiplication algorithm that executes without AI.
Classification
| What it proposes | Program |
|---|---|
| Generative model | Custom transformer-based torso, policy and value network trained with reinforcement learning and synthetic demonstrations (not an LLM) |
| Algorithmic authority | Exact algebraic tensor-rank verifier and Monte Carlo Tree Search, plus target GPU/TPU runtime benchmarker |
| Feedback | Reward signal |
| What gets updated | Search tree, model weights and training data |
| When it runs | Offline, at design time |
| Validity | Formal (machine-checked) |
| Evidence | Experiments reported |
| Lineage | Original system |