AlphaDev

AlphaDev is an AI system developed by Google DeepMind that uses reinforcement learning to discover enhanced computer science algorithms. The system was introduced in a June 7, 2023, paper titled "Faster sorting algorithms discovered using deep reinforcement learning," which describes how AlphaDev was used to uncover a faster sorting algorithm. To discover new, more enhanced algorithms, AlphaDev formulates the problem as a single-player game, referred to as AssemblyGame. In this game, the system selects a series of low-level CPU instructions, referred to as assembly instructions, to combine in order to yield a new and more efficient algorithm.

AlphaDev is a learning agent trained to search for correct and efficient algorithms. It is comprised of two core components:

• A learning algorithm
• A representation function

The learning algorithm can incorporate both deep reinforcement learning (DRL) and stochastic search optimization algorithms to play AssemblyGame. The primary learning algorithm is an extension of AlphaZero, DeepMind's reinforcement learning model that defeated world champions in games such as Go, chess, and shogi. The representation function is interchangeable and captures the underlying structure of assembly programs. The primary AlphaDev representation is based on Transformers.

Sorting is a method of organizing items into a particular order. For example, alphabetizing or arranging numbers from biggest to smallest. The process is used across a number of applications, including ranking search results and data processing.

Rather than refining or enhancing existing methods, AlphaDev discovered a faster sorting algorithm by starting from scratch using assembly instructions. These instructions create the low-level binary code that controls computers. Training AlphaDev to uncover new sorting algorithms, the problem was transformed into a single-player "assembly game." At each turn, AlphaDev assesses the algorithm generated and the information contained in the processing unit, then chooses a move, adding an instruction to the algorithm. The AI system has to efficiently search through a large number of possible combinations of instructions to find an algorithm that can sort faster than the current iteration. The possible combinations are similar to the number of particles in the universe or the number of possible combinations of moves in games of chess (10¹²⁰ games) and Go (10⁷⁰⁰ games).

A reward system favors sorting algorithms that sort numbers correctly in a fast and efficient manner. AlphaDev wins the game by discovering a correct, faster program. The AI system uncovered new sorting algorithms that led to improvements in the LLVM libc++ sorting library that were up to 70% faster for shorter sequences and about 1.7% faster for sequences exceeding 250,000 elements. DeepMind focused on improving sorting algorithms for shorter sequences of three to five elements, as these are among the most widely used and are often called as part of larger sorting functions.

The new algorithms were reverse-engineered and translated into C++ to make them more usable. DeepMind made them available in the LLVM libc++ standard sorting library, which is used by millions of developers and companies around the world. The software is released under the Apache License, Version 2.0. Accompanying material is licensed under the Creative Commons Attribution 4.0 International License (CC-BY).