DeepMind, the company behind advanced AI systems, continues its streak of groundbreaking discoveries in computer science. Last year, their game-playing AI AlphaZero achieved a significant breakthrough by finding new ways to accelerate the calculation of a crucial mathematical component used in various types of code, surpassing a record that had stood for 50 years.
Now, DeepMind has accomplished this feat once again—twice. Utilizing a newer iteration of AlphaZero called AlphaDev, the UK-based company (now known as Google DeepMind following a merger with its sister company’s AI lab in April) has identified a method to sort items in a list up to 70% faster than the most efficient existing technique.
Furthermore, DeepMind has also enhanced a key algorithm employed in cryptography, resulting in a 30% speed improvement. Cryptography algorithms serve as fundamental building blocks in software, and even slight enhancements can lead to significant cost reductions and energy savings.
According to Daniel Mankowitz, a research scientist at Google DeepMind, the industry is in need of innovative approaches for optimizing computing as Moore’s Law reaches its limits, with computer chips approaching their physical constraints.
Peter Sanders, an expert in efficient algorithm design and implementation at the Karlsruhe Institute of Technology in Germany, who was not involved in the research, praised the new approach. Sanders emphasized that sorting remains one of the most widely utilized subroutines in computing.
The findings by DeepMind have been published in the journal Nature. The sorting algorithms developed by AlphaDev are already being used by millions of software developers. In fact, in January 2022, DeepMind submitted these algorithms to the organization responsible for managing C++, one of the most popular programming languages worldwide. After undergoing rigorous independent scrutiny for two months, AlphaDev’s sorting algorithms were integrated into the language. This marked the first modification to C++’s sorting algorithms in over a decade and the first-ever update involving an algorithm discovered using AI.
Additionally, DeepMind incorporated its other new algorithms into Abseil, an open-source collection of prewritten C++ algorithms accessible to any C++ programmer. These algorithms are employed in computing unique identification numbers called hashes for various types of data. DeepMind estimates that its newly developed algorithms are currently being utilized billions of times each day.
AlphaDev is constructed upon AlphaZero, the reinforcement learning model that DeepMind trained to excel in games such as Go and chess. The company’s breakthrough approach involves treating the task of finding faster algorithms as a game and training the AI system to win this game—similar to their previous work in speeding up matrix multiplications.
In the case of AlphaDev, the game involves selecting and arranging computer instructions to form an algorithm within the context of assembly language. Assembly language is used to provide specific instructions for manipulating numbers on a computer chip and is typically a lower-level language into which higher-level languages like C++ are translated before execution. Assembly language allows algorithms to be broken down into fine-grained steps, making it a suitable starting point for seeking optimizations.
AlphaDev plays moves in the game by adding new assembly instructions to the algorithm it is constructing. Initially, AlphaDev randomly adds instructions, resulting in non-functional algorithms. However, through reinforcement learning, it gradually learns to play winning moves. It adds instructions that generate correct and faster algorithms, which can be executed successfully.
DeepMind focused its efforts on optimizing algorithms for sorting short lists containing three to five items. These sorting algorithms are frequently called in programs that handle longer lists, so improvements in the shorter algorithms have a cumulative effect on performance.
Although researchers at DeepMind didn’t expect to surpass human-devised algorithms, they managed to achieve faster sorting for lists of three and five items. For three items, AlphaDev discovered a sorting algorithm requiring 17 instructions instead of the previously best-known 18-instruction algorithm. For five
items, the number of instructions was reduced from 46 to 42, outperforming the best human-developed algorithm.
These improvements resulted in significant speed-ups. On a typical Intel Skylake chip, the existing C++ algorithm for sorting a list of five items took around 6.91 nanoseconds, while AlphaDev’s algorithm took only 2.01 nanoseconds—a speed improvement of approximately 70%.
DeepMind likens the discovery made by AlphaDev to one of AlphaGo’s surprising but effective moves during its match against grandmaster Lee Sedol in 2016. Despite initial skepticism from experts, the move turned out to be successful and even influenced strategies used by professional Go players.
While impressed by DeepMind’s achievements, Peter Sanders suggests that caution should be exercised in not overhyping the results. He acknowledges the increasing impact of machine learning techniques on programming and the expectation that AI will soon be able to devise new and superior algorithms. However, he believes that we haven’t reached that point yet.
Sanders highlights that AlphaDev only employs a subset of the available assembly instructions, whereas many existing sorting algorithms utilize instructions that AlphaDev did not explore. This makes direct comparisons with other approaches more challenging.
Furthermore, AlphaDev has its limitations. The longest algorithm it generated consisted of 130 instructions for sorting lists of up to five items. At each step, AlphaDev had a choice of 297 assembly instructions out of many more possibilities. As the length of algorithms and the number of available moves increase, the learning process becomes slower. The number of potential algorithms AlphaDev could construct surpasses the estimated number of atoms in the universe and exceeds the possible number of games in chess.
For longer algorithms, the DeepMind team plans to adapt AlphaDev to work with C++ instructions instead of assembly language. Although this approach may overlook certain shortcuts due to the decreased control at a finer-grained level, it would be applicable to a wider range of algorithms.
Sanders suggests that a more exhaustive comparison with the best human-designed approaches, particularly for longer algorithms, would be beneficial. DeepMind acknowledges this and intends to incorporate the best human-devised methods into AlphaDev, allowing the AI system to build upon human intuition rather than starting from scratch.
The potential for further speed-ups is substantial, as identifying such optimizations would typically require extensive expertise and a significant investment of time. Mankowitz emphasizes that humans have not previously attempted this type of exploration, as it necessitates examining programs in detail and identifying improvements, a task that can take days or even weeks.