AlphaDev discovers faster sorting algorithms, added to the C++ library
The new sequences were merged into LLVM's libc++ standard library, its first change to that section of code in over a decade and the first written by a reinforcement-learning system.
- Models & capabilities
- Notable
Google DeepMind published AlphaDev, a reinforcement-learning system built on the AlphaZero line that discovered new, faster sorting algorithms at the level of individual CPU assembly instructions. The result was published simultaneously as a paper in Nature. Rather than generating code as text, DeepMind framed algorithm discovery as a single-player game: the system watched the CPU state produced by each instruction it added and was rewarded for correctness and execution speed, gradually assembling short instruction sequences that outperformed those refined by engineers and compiler-writers over decades.
DeepMind reported the discovered algorithms were up to 70% faster for short sequences of three to five elements, and about 1.7% faster for sequences beyond 250,000 elements, along with sorting algorithms roughly 30% faster for hashing in certain byte ranges. The gains came from what researchers called “swap and copy moves” — counterintuitive instruction orderings that skip steps a human engineer would consider necessary, a discovery DeepMind compared to AlphaGo’s widely discussed “move 37.”
DeepMind reverse-engineered the discovered instruction sequences into C++ and contributed them to LLVM’s libc++ standard library, where they were adopted — the library’s first change to its sorting algorithms in more than ten years, and, DeepMind said, the first code contribution to that library generated by a reinforcement-learning system. Because libc++ underlies software run by a very large number of programs, the change gave AlphaDev’s output a form of real-world deployment unusual for an AI research result: instead of remaining a benchmark demonstration, its output became infrastructure other code depended on.