The DOI matches its Crossref record; 57 of the 57 references it cites were found in a registry or an index.
Faster sorting algorithms discovered using deep reinforcement learning
Open accessAbstract
Fundamental algorithms such as sorting or hashing are used trillions of times on any given day 1. As demand for computation grows, it has become critical for these algorithms to be as performant as possible. Whereas remarkable progress has been achieved in the past 2, making further improvements on the efficiency of these routines has proved challenging for both human scientists and computational approaches. Here we show how artificial intelligence can go beyond the current state of the art by discovering hitherto unknown routines. To realize this, we formulated the task of finding a better sorting routine as a single-player game. We then trained a new deep reinforcement learning agent, AlphaDev, to play this game. AlphaDev discovered small sorting algorithms from scratch that outperformed previously known human benchmarks. These algorithms have been integrated into the LLVM standard C++ sort library 3. This change to this part of the sort library represents the replacement of a component with an algorithm that has been automatically discovered using reinforcement learning. We also present results in extra domains, showcasing the generality of the approach.
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.
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
Language Models are Few-Shot Learners
Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. (2020) · arXiv · doi:10.48550/arxiv.2005.14165 · Cited by 23,372 · cited 1×
“Transformers are natural text encoders and have had much success with language models recently 14,34,41 .”
BackgroundMastering 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-citationA 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 2×
“AlphaZero 33 is an RL algorithm that leverages MCTS as a policy improvement operator.”
MethodSelf-citationEvaluating Large Language Models Trained on Code
Chen, M., Tworek, J., Jun, H., Yuan, Q., Pinto, H. P. D. O., Kaplan, J., Edwards, H., Burda, Y., Joseph, N., Brockman, G., et al. (2021) · arXiv · doi:10.48550/arxiv.2107.03374 · Cited by 1,436
Mastering Atari, Go, chess and shogi by planning with a learned model
Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al. (2020) · RePEc: Research Papers in Economics · Cited by 1,310
Self-citationMastering Atari, Go, chess and shogi by planning with a learned model
Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al. (2020) · Nature · doi:10.1038/s41586-020-03051-4 · Cited by 1,214 · cited 3×
“Then, the true dynamics or dynamics network (for MuZero) as well as the prediction network f pred ( h t ) are used to simulate several trajectories that fill out a search tree, by sampling state transitions.”
MethodInfluentialSelf-citationCompetition-level code generation with AlphaCode
Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Dal Lago, A., et al. (2022) · Science · doi:10.1126/science.abq1158 · Cited by 1,043
Self-citationCompetition-Level Code Generation with AlphaCode
Li, Y., Choi, D., Chung, J., Kushman, N., Schrittwieser, J., Leblond, R., Eccles, T., Keeling, J., Gimeno, F., Lago, A. D., et al. (2022) · arXiv · doi:10.48550/arxiv.2203.07814 · Cited by 1,043
Self-citationLanguage to Logical Form with Neural Attention
Dong, L., & Lapata, M. (2016) · Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/p16-1004 · Cited by 700
Alur, R., Bodik, R., Juniwal, G., Martin, M. M. K., Raghothaman, M., Seshia, S. A., Singh, R., Solar-Lezama, A., Torlak, E., & Udupa, A. (2013) · 2013 Formal Methods in Computer-Aided Design · doi:10.1109/fmcad.2013.6679385 · Cited by 656
Research works printed but not linked: 14
- Cormen, T. H. et al. Introduction to Algorithms (MIT Press, 2022).
- Bunel, R. et al. Learning to superoptimize programs. In Proc. International Conference on Learning Representations (ICLR, 2016).
- Chen, X., Liu, C. & Song, D. Towards synthesizing complex programs from input-output examples. In Proc. International Conference on Learning Representations (ICLR, 2018).
- Mehlhorn, K., Sanders, P. & Sanders, P. Algorithms and Data Structures: The Basic Toolbox Vol. 55. (Springer, 2008).
- Irvine, K. R. et al. Assembly Language for Intel-Based Computers (Prentice Hall, 2003).
- Vaswani, A. et al. Attention is all you need. Adv. Neural Inform. Proc. Syst. 30, 5999–6009 (2017).
- Sutton, R. S. & Barto, A. G. Reinforcement Learning: An Introduction 2nd edn (MIT Press, 2018).
- Maillard, O.-A., Ryabko, D. & Munos, R. Selecting the state-representation in reinforcement learning. Adv. Neural Inform. Proc. Syst. 24, 2627–2635 (2011).
- Hahn, G. J. & Meeker, W. Q. Statistical Intervals: A Guide for Practitioners Vol. 92 (John Wiley & Sons, 2011).
- Warren, H. S. Hacker’s Delight (Pearson Education, 2013).
- Chen, X., Liu, C. & Song, D. Execution-guided neural program synthesis. In Proc. International Conference on Learning Representations (ICLR, 2018).
- Ibarz, B. et al. A generalist neural algorithmic learner. In Proc. Learning on Graphs Conference Vol. 198, 2:1–2:23 (PMLR, 2022).
- Chen, X., Song, D. & Tian, Y. Latent execution for neural program synthesis beyond domain-specific languages. Adv. Neural Inform. Proc. Syst. 34, 22196–22208 (2021).
- Ellis, K., Solar-Lezama, A. & Tenenbaum, J. Sampling for Bayesian program learning. Adv. Neural Inform. Proc. Syst. 29, 1297–1305 (2016).
Cited by
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
“We also note that reinforcement learning has recently been applied to discover new faster algorithms for fundamental operations such as matrix multiplication 89 and sorting 90 .”
MethodSelf-citationThe STARD-AI reporting guideline for diagnostic accuracy studies using artificial intelligence
Sounderajah, V., Guni, A., Liu, X., Collins, G. S., Karthikesalingam, A., Markar, S. R., Golub, R. M., Denniston, A. K., Shetty, S., Moher, D., et al. (2025) · Nature Medicine · doi:10.1038/s41591-025-03953-8 · Cited by 592
Optimizing generative AI by backpropagating language model feedback
Yuksekgonul, M., Bianchi, F., Boen, J., Liu, S., Lu, P., Huang, Z., Guestrin, C., & Zou, J. (2025) · Nature · doi:10.1038/s41586-025-08661-4 · Cited by 85
Learning Performance-Improving Code Edits
Shypula, A., Madaan, A., Zeng, Y., Alon, U., Gardner, J., Hashemi, M., Neubig, G., Ranganathan, P., Bastani, O., & Yazdanbakhsh, A. (2023) · arXiv · doi:10.48550/arxiv.2302.07867 · Cited by 146
“Recent work has demonstrated the promise of deep learning for automating performance optimization (Garg et al., 2022; Mankowitz et al., 2023).”
BackgroundOlympiad-level formal mathematical reasoning with reinforcement learning
Hubert, T., Mehta, R., Sartran, L., Horváth, M. Z., Žužić, G., Wieser, E., Huang, A., Schrittwieser, J., Schroecker, Y., Masoom, H., et al. (2026) · Nature · doi:10.1038/s41586-025-09833-y · Cited by 19
“…family of agents, for instance, demonstrated the ability to achieve superhuman performance in challenging board games such as Go, chess and shogi 2 , optimize quantum dynamics 5 , and discover more efficient algorithms for fundamental computations such as sorting 6 and matrix multiplication 7 .”
Self-citation
Metadata
- Authors
- Mankowitz, D. J., Michi, A., Zhernov, A., Gelmi, M., Selvi, M., Paduraru, C., Leurent, E., Iqbal, S., Lespiau, J.-B., Ahern, A., Köppe, T., Millikin, K., Gaffney, S., Elster, S., Broshear, J., Gamble, C., Milan, K., Tung, R., Hwang, M., Cemgil, T., Barekatain, M., Li, Y., Mandhane, A., Hubert, T., Schrittwieser, J., Hassabis, D., Kohli, P., Riedmiller, M., Vinyals, O., & Silver, D.
- Affiliations
- Google DeepMind (United Kingdom) (GB)
- Google (United States) (US)
- Corresponding author
- Mankowitz, Daniel J.
- ORCID
- Venue
- Nature
- Published
- 2023-06-07
- Volume
- 618
- Issue
- 7964
- Pages
- 257-263
- ISSN
- 0028-0836 (ISSN-L)
- 1476-4687
- PMC
- PMC10247365
- OpenAlex
- W4379739787
- Cited by
- 177
- References
- 57
- Citations by year
- 2026: 38 · 2025: 68 · 2024: 53 · 2023: 18
- FWCI
- 16.66
- 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 › Artificial Intelligence › Evolutionary Algorithms and Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Artificial Intelligence in Games
- Physical Sciences › Computer Science › Information Systems › Software Engineering Research
- Keywords
- algorithm discovery, sorting algorithms, deep reinforcement learning, C++ standard library, performance optimization
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: Faster sorting algorithms discovered using deep reinforcement learning. https://app.cochat.ai/papers/10.1038/s41586-023-06004-9
- The paper
- Mankowitz, D. J., Michi, A., Zhernov, A., Gelmi, M., Selvi, M., Paduraru, C., Leurent, E., Iqbal, S., Lespiau, J.-B., Ahern, A., Köppe, T., Millikin, K., Gaffney, S., Elster, S., Broshear, J., Gamble, C., Milan, K., Tung, R., Hwang, M., . . . Silver, D. (2023). Faster sorting algorithms discovered using deep reinforcement learning. Nature. https://doi.org/10.1038/s41586-023-06004-9
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.