AlphaDev discovers faster small-sort routines, merged into LLVM's C++ standard library
AlphaDev (Nature, 7 Jun 2023) treated writing assembly as a game and found sort3/sort4/sort5 routines shorter than human versions; they were merged into LLVM libc++. Critics argued the gains were small tricks a compiler or GPT-4 could also find.
Key facts
- Sort routines merged into LLVM libc++, used by millions of programs
- DeepMind: up to 70% faster for short sequences, ~1.7% for sequences >250k elements
- Critics: essentially a known sorting network plus one removed mov instruction; Cassio Neri published a shorter, faster sort3 (arXiv 2307.14503)
Science result
- Field
- computer-science / algorithms / program synthesis
- Problem
- Optimal assembly for fixed-size sorting
- Result
- RL-discovered sort3–sort5 routines with fewer instructions than human-written libc++ code, adopted upstream.
- AI system
- AlphaDev
- Human role
- Autonomous search; humans integrated code into LLVM
- Verification
- Peer-reviewed in Nature; code merged into LLVM
- Status
- disputed
What happened
AlphaDev found instruction sequences for sorting 3–5 elements that saved instructions over decades-old library code. LLVM maintainers accepted them.
Why it matters
It was AI-discovered code shipping in core infrastructure, though experts argued about how novel the discovery really was.
Changelog
- 2026-09-29: created
Related events
Sources (3)
- paperFaster sorting algorithms discovered using deep reinforcement learning (Nature)
- officialDeepMind: AlphaDev discovers faster sorting algorithms
- discussionCassio Neri: shorter and faster than Sort3AlphaDev (arXiv 2307.14503)
id: 2023-06-07-alphadev-sorting · updated 2026-09-29 · open in the interactive timeline