Faster sorting algorithms discovered using deep reinforcement learning
Problem
Improving the efficiency of fundamental sorting routines had stalled for both human scientists and computational approaches.
Why it matters
Sorting runs trillions of times daily, so faster routines save computation at global scale.
What the AI did
AlphaDev, a deep reinforcement learning agent trained on a sorting-optimization game, discovered new small sorting algorithms from scratch that beat human benchmarks.
Results
Discovered sorting algorithms outperforming previously known human benchmarks; integrated into the LLVM standard C++ sort library
Impact
Discovered algorithms were adopted into LLVM, a widely used C++ library, indicating real-world deployment.
Record
| Venue | Nature |
|---|---|
| Published | 2023 |
| Work type | article |
| Authors | Daniel J. Mankowitz, Andrea Michi, Anton Zhernov, Marco Gelmi, Marco Selvi, Cosmin Păduraru, Edouard Leurent, Shariq Iqbal et al. |
| Citations | 175 (OpenAlex, at import time) |
| References | 64 |
| Model or method | AlphaDev (deep reinforcement learning agent) |
| Organization | not stated in source |
| Primary source | https://doi.org/10.1038/s41586-023-06004-9 |
| Open access | hybrid |
| Keywords | reinforcement learning, sorting algorithms, AlphaDev, LLVM, program optimization |
Importance rating
major — millions of lives, an industry or a field
Abstract states fundamental algorithms run trillions of times daily; discovered faster sorting routines integrated into LLVM, a widely used C++ library, affecting global computation.
More in Software & Coding
| # | Paper | Year | Citations | Importance |
|---|---|---|---|---|
| 1 | ImageNet classification with deep convolutional neural networks | 2017 | 106,345 |
8
|
| 2 | Deep Residual Learning for Image Recognition | 2016 | 221,134 |
8
|
| 3 | A deep learning‐based approach for software vulnerability detection using code metrics | 2022 | 42 |
7
|
| 4 | Deep Learning-Based Attack Detection and Classification in Android Devices | 2023 | 41 |
7
|
| 5 | Dota 2 with Large Scale Deep Reinforcement Learning | 2019 | 969 |
6
|