Faster sorting algorithms discovered using deep reinforcement learning (AlphaDev)

AlphaDev (Nature, June 2023) applies AlphaZero-style reinforcement learning to discover novel computer algorithms — specifically, assembly-level sorting routines that are faster than the hand-optimized functions that have been in widespread use for decades. The system frames algorithm design as a game: each move adds one CPU instruction, and the reward is a combination of correctness and runtime latency on real hardware. AlphaDev discovered sorting algorithms for 3, 5, 6, 7, and 8 element sequences that were 70% faster than the best known implementations — algorithms that are now deployed in LLVM's standard library and used in virtually every C++ program worldwide. The significance for AI research: this is the first time AI discovered a genuinely new algorithm (not just optimized an existing one) that was deemed good enough to replace hand-written expert code at scale. It also demonstrates that deep RL can operate in domains with combinatorially large discrete action spaces — a key capability requirement for future AI systems that must reason about symbolic structures rather than continuous spaces.