close
Skip to main page content
U.S. flag

An official website of the United States government

Dot gov

The .gov means it’s official.
Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

Https

The site is secure.
The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

Access keys NCBI Homepage MyNCBI Homepage Main Content Main Navigation
. 2023 Jun;618(7964):257-263.
doi: 10.1038/s41586-023-06004-9. Epub 2023 Jun 7.

Faster sorting algorithms discovered using deep reinforcement learning

Daniel J Mankowitz #  1 , Andrea Michi #  2 , Anton Zhernov #  2 , Marco Gelmi #  2 , Marco Selvi #  2 , Cosmin Paduraru #  2 , Edouard Leurent #  2 , Shariq Iqbal  2 , Jean-Baptiste Lespiau  2 , Alex Ahern  2 , Thomas Köppe  2 , Kevin Millikin  2 , Stephen Gaffney  2 , Sophie Elster  2 , Jackson Broshear  2 , Chris Gamble  2 , Kieran Milan  2 , Robert Tung  2 , Minjae Hwang  3 , Taylan Cemgil  2 , Mohammadamin Barekatain  2 , Yujia Li  2 , Amol Mandhane  2 , Thomas Hubert  2 , Julian Schrittwieser  2 , Demis Hassabis  2 , Pushmeet Kohli  2 , Martin Riedmiller  2 , Oriol Vinyals  2 , David Silver  2
Affiliations

Faster sorting algorithms discovered using deep reinforcement learning

Daniel J Mankowitz et al. Nature. 2023 Jun.

Abstract

Fundamental algorithms such as sorting or hashing are used trillions of times on any given day1. As demand for computation grows, it has become critical for these algorithms to be as performant as possible. Whereas remarkable progress has been achieved in the past2, making further improvements on the efficiency of these routines has proved challenging for both human scientists and computational approaches. Here we show how artificial intelligence can go beyond the current state of the art by discovering hitherto unknown routines. To realize this, we formulated the task of finding a better sorting routine as a single-player game. We then trained a new deep reinforcement learning agent, AlphaDev, to play this game. AlphaDev discovered small sorting algorithms from scratch that outperformed previously known human benchmarks. These algorithms have been integrated into the LLVM standard C++ sort library3. This change to this part of the sort library represents the replacement of a component with an algorithm that has been automatically discovered using reinforcement learning. We also present results in extra domains, showcasing the generality of the approach.

PubMed Disclaimer

Conflict of interest statement

D.J.M., A.Michi, A.Z., M.G., M.S., C.P., E.L., S.I., A.Mandhane, P.K., M.R., D.S. and O.V. are planning to file a patent application relating to subject matter contained in this paper in the name of DeepMind Technologies Limited. The remaining authors declare no competing interests.

Figures

Fig. 1
Fig. 1. The relationship between C++ and assembly programs.
a, A C++ implementation of a variable sort 2 function that sorts any input sequence of up to two elements. b, The C++ implementation in a is compiled to this equivalent low-level assembly representation.
Fig. 2
Fig. 2. The AssemblyGame and algorithm correctness computation.
a, The AssemblyGame is played by AlphaDev, which receives as input the current assembly algorithm generated thus far St and plays the game by selecting an action to execute. In this example, the action is a mov<Register0,Memory1> assembly instruction, which is appended to the current algorithm. The agent receives a reward that is a function of the algorithm’s correctness, discussed in b, as well as the algorithm’s latency. The game is won by the player discovering a low latency, correct algorithm. b, The program correctness and latency computations are used to compute the reward rt. In this example, test sequences are input to the algorithm; for example, in the case of sorting three elements, test inputs comprise all sequences of unsorted elements of length 3. For each sequence, the algorithm output is compared to the expected output (in the case of sorting, the expected output is the sorted elements). In this example, the output D′ does not match the expected output B′ and the algorithm is therefore incorrect.
Fig. 3
Fig. 3. Sorting networks and algorithmic improvements discovered by AlphaDev.
a, An optimal classic sorting network for three inputs. The circled comparators have been improved by AlphaDev. See the AlphaDev swap move for more details. b,c, The assembly pseudocode before applying the AlphaDev swap move (b) and after applying the AlphaDev swap move (c), resulting in the removal of a single instruction. d, An optimal classic sorting network comparator configuration that has been improved by AlphaDev. See the AlphaDev copy move for more details. e,f, The assembly pseudocode before applying the AlphaDev copy move (e) and after applying the AlphaDev copy move (f), resulting in the removal of a single instruction.
Fig. 4
Fig. 4. Fundamentally different algorithms discovered by AlphaDev.
a, A flow diagram of the variable sort 4 (VarSort4) human benchmark algorithm. In this algorithm, a sequence of unsorted numbers are input into the algorithm. If the sequence length is four, three or two numbers, then the corresponding sort 4, sort 3 or sort 2 sorting network is called that sorts the resulting sequence. The result is then returned and output by the function. b, The VarSort4 algorithm discovered by AlphaDev. This algorithm also receives sequences of length four, three or two numbers as input. In this case, if the length is two, then it calls the sort 2 sorting network and returns. If the length is three then it calls sort 3 to sort the first three numbers and returns. If, however, the length is greater than three, then it calls sort 3, followed by a simplified sort 4 routine that sorts the remaining unsorted number. It is this part of the routine that results in significant latency savings.
Extended Data Fig. 1
Extended Data Fig. 1. The AlphaDev representation network architecture.
(a) The AlphaDev representation network comprises a Transformer Encoder network that receives as input the assembly algorithm generated thus far. It also contains a CPU State Encoder network that receives as input the current state of memory and registers. The exact architecture and hyperparameters can be found in the Supplementary Information, Appendix A. (b) Before inputting instructions into the Transformer Encoder network, each program instruction’s opcode and operands are converted to one-hot encodings and concatenated. The resulting encoding is then fed into the Transformer Encoder network.
Extended Data Fig. 2
Extended Data Fig. 2. An example sorting network.
(a) The horizontal lines are called wires and the vertical lines are called comparators. (b) An initially unsorted sequence of values are input into the sorting network on the left hand side. At various stages two wires encounter a comparator. If the value at the top of the comparator is smaller than the value at the bottom of the comparator, the numbers switch wires. An optimal sorting network places comparators in specific positions so as to sort any sequence of unsorted values using the minimum number of comparators.
Extended Data Fig. 3
Extended Data Fig. 3. Hypothesis for improved exploration using AlphaDev.
(a) A 2D t-SNE projection indicating the regions explored by AlphaDev (blue) compared to AlphaDev-S. (b) The same 2D t-SNE projection as in (a) with algorithm correctness superimposed onto each point from incorrect programs (purple) to correct programs (yellow). As seen in the figure, AlphaDev-S struggles to move out of local optima whereas AlphaDev is able to explore from the space of incorrect programs to the space of correct programs.
See this image and copyright information in PMC

References

    1. Amazon. Amazon S3—two trillion objects, 1.1 million requests/second. AWShttps://aws.amazon.com/blogs/aws/amazon-s3-two-trillion-objects-11-milli... (2013).
    1. Cormen, T. H. et al. Introduction to Algorithms (MIT Press, 2022).
    1. Gelmi, M. Introduce branchless sorting functions for sort3, sort4 and sort5. LLVM.orghttps://reviews.llvm.org/D118029 (2022).
    1. Bansal, S. & Aiken, A. Automatic generation of peephole superoptimizers. ACM SIGARCH Comput. Arch. News34, 394–403 (2006).
    1. Alur, R. et al. Syntax-Guided Synthesis (IEEE, 2013).

LinkOut - more resources