AlphaDev: an Artificial Intelligence System for Faster Sorting Algorithms: A Proposal for DeepMind

Ellis, K. et al. in Proc. The 33rd Neuralinf. PROCESS is underway. Syst. Wallach, H. and Larochelle, H., along with Beygelzimer, A. and d’Alché-Buc, F. were included in the book.

For decades, the computing industry relied on Moore’s law: as transistors became ever smaller, the number that could be crammed onto a computer chip seemed to double every two years, enabling a similar leap in computing power. Software Optimization is as important as miniaturization due to Moore’s law being a natural limit. Writing in Nature, Mankowitz et al.1, show that the code that is generated by artificial intelligence can improve the efficiency with which the programming language sorts items in a list. Although seemingly mundane, this task is needed in computer programs the world over, and the AI version is now baked into a widely used implementation of the C++ library. Perhaps even more remarkably, the AI system can improve the code without any previous knowledge of the problem itself.

Computer scientists for decades have been trying to improve the efficiency of computers to reduce the time it takes for a search to return results. Now DeepMind, based in London, has vastly improved sorting speeds by applying the technology behind AlphaZero — its artificial-intelligence system for playing the board games chess, Go and shogi — to a game of building sorting algorithms. Emma Brunskill, who is a computer scientist at Stanford University, said it was an exciting result.

The system, AlphaDev, is described in a paper in Nature1, and has invented faster algorithms that are already part of two standard C++ coding libraries, so are being used trillions of times per day by programmers around the world.

AlphaDev works similarly to its predecessor, AlphaZero, which combines computer versions of deliberation and intuition to choose moves in a board game2. AlphaDev doesn’t choose moves; instead, it chooses instructions to add to a procedure (in what DeepMind engineers call AssemblyGame).

In future, the DeepMind team would like to apply AlphaZero-style algorithms to more kinds of problems, even the design of hardware itself, Mankowitz says. “We really want to be tackling the whole stack.”