📄 Faster Sorting Algorithms Discovered Using Deep Reinforcement Learning

Summary

Tiny sorting routines for a handful of elements run an enormous number of times, because divide-and-conquer sorts call them on short subarrays. Decades of expert tuning have left little obvious room to speed them up. Mankowitz et al. (DeepMind) turn the search for such routines into AssemblyGame, a one-player game in which an agent builds a program by adding x86 assembly instructions (AT&T syntax) one at a time. The reward combines two parts. Correctness is checked by running the program on test inputs and comparing the results with the expected outputs. Efficiency is scored either by program length or by directly measured latency. The agent, AlphaDev, extends AlphaZero. A neural network guides MCTS, combining a Transformer encoder of the program with an encoder of the CPU register and memory state. Starting from scratch, AlphaDev found fixed and variable sorting routines that match or beat the best human-written versions in length and run faster in measured latency. Its sort 3, sort 4 and sort 5 routines are now part of the LLVM standard C++ library. This marks an RL-discovered component replacing hand-written code in widely used software.

Key points

• AlphaDev targets two kinds of small sort. Fixed sorts handle exactly n elements (sort 3/4/5). Variable sorts (VarSort3/4/5) accept any length up to n.
• Measured latency is lower than the human baselines in every case:
  • VarSort3: 236,498 vs 246,040.
  • VarSort4: 279,339 vs 294,963.
  • VarSort5: 312,079 vs 331,198.
  • VarInt: 97,184 vs 295,358, roughly three times faster.
  • "Competitive": 75,973 vs 86,056.
  • All figures are the 5th percentile over 100 machines, with 95% confidence intervals.
• AssemblyGame's search space is compared in size to chess (~10^120 games) and Go (~10^700). A single wrong instruction can make a whole program incorrect.
• Compared with a stochastic-search baseline (AlphaDev-S), AlphaDev needs far fewer explored programs. AlphaDev-S fails from a cold start, and its warm-started version tends to get stuck in local optima once branching is involved.
• The approach is also applied beyond sorting (e.g., VarInt and a competitive-programming task), suggesting it generalizes to other domains.