The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index.
Discovering faster matrix multiplication algorithms with reinforcement learning
Open accessAbstract
Improving the efficiency of algorithms for fundamental computations can have a widespread impact, as it can affect the overall speed of a large amount of computations. Matrix multiplication is one such primitive task, occurring in many systems—from neural networks to scientific computing routines. The automatic discovery of algorithms using machine learning offers the prospect of reaching beyond human intuition and outperforming the current best human-designed algorithms. However, automating the algorithm discovery procedure is intricate, as the space of possible algorithms is enormous. Here we report a deep reinforcement learning approach based on AlphaZero 1 for discovering efficient and provably correct algorithms for the multiplication of arbitrary matrices. Our agent, AlphaTensor, is trained to play a single-player game where the objective is finding tensor decompositions within a finite factor space. AlphaTensor discovered algorithms that outperform the state-of-the-art complexity for many matrix sizes. Particularly relevant is the case of 4 × 4 matrices in a finite field, where AlphaTensor’s algorithm improves on Strassen’s two-level algorithm for the first time, to our knowledge, since its discovery 50 years ago 2 . We further showcase the flexibility of AlphaTensor through different use-cases: algorithms with state-of-the-art complexity for structured matrix multiplication and improved practical efficiency by optimizing matrix multiplication for runtime on specific hardware. Our results highlight AlphaTensor’s ability to accelerate the process of algorithmic discovery on a range of problems, and to optimize for different criteria.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Figures









Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“Despite being general-purpose, AlphaEvolve goes beyond [26], improving the SOTA for 14 matrix multiplication algorithms”
From AlphaEvolve: A coding agent for scientific and algorithmic discovery (2025) · cites this paper as [26]
Experimental — accuracy not yet measured
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Mastering the game of Go with deep neural networks and tree search
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016) · Nature · doi:10.1038/nature16961 · Cited by 15,612
Self-citationTensorFlow: A system for large-scale machine learning
Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., et al. (2016) · arXiv (Cornell University) · doi:10.48550/arxiv.1605.08695 · Cited by 11,822
Tensor Decompositions and Applications
Kolda, T. G., & Bader, B. W. (2009) · SIAM Review · doi:10.1137/07070111x · Cited by 10,301
International Conference on Learning Representations (ICLR 2013)
松尾, 豊. (2013) · 人工知能学会誌 = Journal of Japanese Society for Artificial Intelligence · Cited by 6,286
A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al. (2018) · Science · doi:10.1126/science.aar6404 · Cited by 3,562 · cited 8×
“, n(2) do (4) c w m w m i R 1 i i R (1) ( ) ← + + return C”
BackgroundMethodInfluentialSelf-citationGaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509 · cited 5×
“, R do (2) ← + + + + m u a u a v b v b ( ) ( ) r n n 1 1 r n r r n r 1 ( ) ( ) 1 ( ) ( ) 2 2 2 2”
InfluentialPlanning chemical syntheses with deep neural networks and symbolic AI
Segler, M. H. S., Preuss, M., & Waller, M. P. (2018) · Nature · doi:10.1038/nature25978 · Cited by 1,847
Deep reinforcement learning for de novo drug design
Popova, M., Isayev, O., & Tropsha, A. (2018) · Science Advances · doi:10.1126/sciadv.aap7885 · Cited by 1,182
Most Tensor Problems Are NP-Hard
Hillar, C. J., & Lim, L.-H. (2013) · Journal of the ACM · doi:10.1145/2512329 · Cited by 1,099
Powers of tensors and fast matrix multiplication
Le Gall, F. (2014) · Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation · doi:10.1145/2608628.2608664 · Cited by 856
Research works printed but not linked: 10
- Bürgisser, P., Clausen, M. & Shokrollahi, A. Algebraic Complexity Theory Vol. 315 (Springer Science & Business Media, 2013).
- Zhang, W. & Dietterich, T. G. A reinforcement learning approach to job-shop scheduling. In International Joint Conferences on Artificial Intelligence Vol. 95, 1114–1120 (Morgan Kaufmann Publishers, 1995).
- Vaswani, A. Attention is all you need. In International Conference on Neural Information Processing Systems Vol 30, 5998–6008 (Curran Associates, 2017).
- Loshchilov, I. & Hutter, F. Decoupled weight decay regularization. In International Conference on Learning Representations (ICLR) (2019).
- Elser, V. A network that learns Strassen multiplication. J. Mach. Learn. Res. 17, 3964–3976 (2016).
- Tschannen, M., Khanna, A. & Anandkumar, A, StrassenNets: deep learning with a multiplication budget. In International Conference on Machine Learning 4985–4994 (PMLR, 2018).
- Bunel, R., Desmaison, A., Kohli, P., Torr, P. H. & Kumar, M. P. Learning to superoptimize programs. In International Conference on Learning Representations (ICLR) (2017).
- Schmidhuber, J. Evolutionary Principles in Self-Referential Learning. On Learning now to Learn: The Meta-Meta-Meta...-Hook. Diploma thesis, Technische Univ. Munchen (1987).
- Kaliszyk, C., Urban, J., Michalewski, H. & Olšák, M. Reinforcement learning of theorem proving. In International Conference on Neural Information Processing Systems 8836–8847 (Curran Associates, 2018).
- Bansal, K., Loos, S., Rabe, M., Szegedy, C. & Wilcox, S. HOList: an environment for machine learning of higher order logic theorem proving. In International Conference on Machine Learning 454–463 (PMLR, 2019).
Cited by
Reinforcement learning algorithms: A brief survey
Shakya, A. K., Pillai, G., & Chakrabarty, S. (2023) · Expert Systems with Applications · doi:10.1016/j.eswa.2023.120495 · Cited by 656
Mathematical discoveries from program search with large language models
Romera-Paredes, B., Barekatain, M., Novikov, A., Balog, M., Kumar, M. P., Dupont, E., Ruiz, F. J. R., Ellenberg, J. S., Wang, P., Fawzi, O., et al. (2024) · Nature · doi:10.1038/s41586-023-06924-6 · Cited by 544
Self-citationCao, Y., Li, S., Liu, Y., Yan, Z., Dai, Y., Yu, P. S., & Sun, L. (2023) · arXiv · doi:10.48550/arxiv.2303.04226 · Cited by 463
“ChatBot Xiaoice Microsoft 2018 [200] Xiaoice ChatBot Meena Google 2020 [201] Meena Blog ChatBot BlenderBot Meta 2022 [202] Blenderbot ChatBot ChatGPT OpenAI 2022 [10] ChatGPT ChatBot Alexa Amazon 2014 Amazon Alexa ChatBot Lex Amazon 2017 Amazon Lex Music AIVA Aiva Tech 2016 AIVA Music Jukebox OpenAI 2020 [203] Jukebox…”
MethodMulti-Agent Deep Reinforcement Learning for Multi-Robot Applications: A Survey
Orr, J., & Dutta, A. (2023) · Sensors · doi:10.3390/s23073625 · Cited by 206
“Deep reinforcement learning has recently been used in finding a faster matrix multiplication solution [8], for drug discovery [9], to beat humans in Go [10], play Atari [6], and for routing in communication networks [11], among others.”
MethodNeurosymbolic Artificial Intelligence (Why, What, and How)
Sheth, A., Roy, K., & Gaur, M. (2023) · IEEE Intelligent Systems · doi:10.1109/mis.2023.3268724 · Cited by 238
“2,3 However, knowledge enables humans to engage in cognitive processes beyond what is explicitly stated in available data.”
Background
Metadata
- Authors
- Fawzi, A., Balog, M., Huang, A., Hubert, T., Romera-Paredes, B., Barekatain, M., Novikov, A., R. Ruiz, F. J., Schrittwieser, J., Swirszcz, G., Silver, D., Hassabis, D., & Kohli, P.
- Affiliations
- Google DeepMind (United Kingdom) (GB)
- Corresponding author
- Fawzi, Alhussein
- ORCID
- Venue
- Nature
- Published
- 2022-10-05
- Volume
- 610
- Issue
- 7930
- Pages
- 47-53
- ISSN
- 0028-0836 (ISSN-L)
- 1476-4687
- PMC
- PMC9534758
- OpenAlex
- W4302010773
- Cited by
- 478
- References
- 40
- Citations by year
- 2026: 69 · 2025: 115 · 2024: 136 · 2023: 148 · 2022: 7
- FWCI
- 54.92
- Type
- journal article
- Language
- en
- Open access
- hybrid
- doi.org
- Licence
- cc-by
- creativecommons.org/licenses/by/4.0 (tdm)
- creativecommons.org/licenses/by/4.0 (vor)
- Locations
- Nature (publishedVersion, cc-by)
- PubMed Central (publishedVersion, cc-by)
- PubMed (publishedVersion)
- RePEc: Research Papers in Economics (submittedVersion)
- Funders
- DeepMind
- Topics
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence Applications
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Polynomial and algebraic computation
- Keywords
- matrix multiplication, algorithm discovery, AlphaZero, deep reinforcement learning, tensor decomposition, Strassen's algorithm, computational complexity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Discovering faster matrix multiplication algorithms with reinforcement learning. https://app.cochat.ai/papers/10.1038/s41586-022-05172-4
- The paper
- Fawzi, A., Balog, M., Huang, A., Hubert, T., Romera-Paredes, B., Barekatain, M., Novikov, A., R. Ruiz, F. J., Schrittwieser, J., Swirszcz, G., Silver, D., Hassabis, D., & Kohli, P. (2022). Discovering faster matrix multiplication algorithms with reinforcement learning. Nature. https://doi.org/10.1038/s41586-022-05172-4
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.