Sorting algorithms are fundamental to computer science, used trillions of times daily. Despite significant past advancements, further optimization has proven challenging for both humans and traditional computational approaches. This research explores the use of artificial intelligence, specifically deep reinforcement learning (DRL), to overcome this limitation. The core challenge is to find new, more efficient sorting routines—a problem often solved by humans through intuition and experience, which has plateaued in recent years. The ever-increasing demand for computational speed necessitates superior sorting algorithms to avoid performance bottlenecks. This study investigates whether DRL can discover novel algorithms that are not only correct but also outperform existing human-designed benchmarks in terms of speed and efficiency, measured at the CPU instruction level. The focus is on small-sort algorithms (sorting sequences of a fixed or variable length), critical components of larger, divide-and-conquer sorting approaches. The aim is to demonstrate that DRL can push the boundaries of algorithm optimization beyond what is achievable through traditional methods, and potentially revolutionize the way we design and improve fundamental algorithms.

The existing literature on program synthesis spans decades, encompassing techniques like enumerative and stochastic search for program optimization and latency reduction. More recently, deep learning has emerged as a promising approach for generating correct programs. However, these methods often struggle with generating high-performing algorithms optimized at the CPU instruction level. This research differentiates itself by using DRL to directly optimize for actual latency measurements, thereby efficiently searching the space of correct and fast programs. Previous work primarily focused on correctness or latency proxies, whereas this research directly optimizes for the actual performance metric.

The research employs a novel approach by framing the task of finding better sorting algorithms as a single-player game, termed "AssemblyGame." AlphaDev, the DRL agent developed for this game, consists of two key components: a learning algorithm and a representation function. The learning algorithm extends AlphaZero, using a neural network to guide a Monte Carlo tree search (MCTS) to discover efficient algorithms. The representation function, based on Transformers, captures the underlying structure of assembly programs, allowing AlphaDev to effectively explore the complex space of instruction sequences. The input to the neural network is the current state of the game (including the partially generated algorithm and the CPU state), and the output is a policy (probability distribution over possible actions, i.e., assembly instructions) and a value function (prediction of the cumulative reward). The AssemblyGame rewards the agent for both correctness (matching expected output for a set of test sequences) and latency (algorithm execution time). A dual value function setup predicts algorithm correctness and latency separately, significantly improving performance. The AlphaDev representation network uses a transformer encoder to represent the assembly instructions and a CPU state encoder (multi-layer perceptron) to predict the effect of the algorithm on memory and registers. The transformer encoder processes opcode and operands to generate embeddings. Latency is measured directly, resulting in more accurate optimization compared to using algorithm length as a proxy. The agent is trained from scratch to discover fixed-length (e.g., sort 3, sort 4, sort 5) and variable-length sorting algorithms. For comparison, AlphaDev is also compared to a stochastic search optimization approach (AlphaDev-S).

AlphaDev discovered novel fixed-length sorting algorithms for sort 3, sort 4, and sort 5 that either matched or improved upon existing human-designed benchmarks in terms of both instruction count and latency. These improved algorithms were integrated into the LLVM standard C++ sort library, a widely used library with millions of users. AlphaDev also discovered improved variable-length sorting algorithms (VarSort3, VarSort4, VarSort5), significantly reducing latency compared to the human benchmarks. AlphaDev's algorithms achieved substantial latency reductions, particularly for VarSort4 and VarSort5, indicating the effectiveness of the approach. The analysis demonstrates that AlphaDev explores orders of magnitude fewer programs than stochastic search, avoiding local optima more effectively. While AlphaDev-S (stochastic search) performs well with branchless algorithms or when warm-started with near-optimal solutions, AlphaDev consistently outperforms it for algorithms requiring branching, where algorithm length and latency are not strongly correlated. Furthermore, AlphaDev's ability to generalize was tested on additional domains, including a protocol buffer deserialization subroutine (VarInt), where it discovered a significantly faster algorithm than the human benchmark. The performance improvements in LLVM translate to real-world benefits: the newly discovered algorithms are estimated to be called trillions of times each day. In the context of the VarInt algorithm, AlphaDev even discovered a novel 'VarInt assignment move', enabling the combination of two operations into a single instruction and leading to further performance gains. AlphaDev discovered novel algorithmic optimizations, including the 'AlphaDev swap move' and the 'AlphaDev copy move', which were applied to existing sorting networks to improve their efficiency, resulting in fewer instructions and reduced latency. These moves involve strategically rearranging or copying elements to reduce the number of comparisons required, thereby improving performance.

The results demonstrate the significant potential of DRL for discovering faster algorithms. AlphaDev's success in finding novel and more efficient sorting algorithms, integrated into a widely used library, underscores the importance of this approach for algorithm optimization. The comparison with stochastic search highlights AlphaDev's ability to more effectively explore the algorithm space and avoid local optima, especially when dealing with branching instructions where latency is less directly correlated with algorithm length. The generalization to additional domains, such as the VarInt deserialization subroutine, further supports the broad applicability of this DRL-based approach. This research opens new avenues for algorithm design, pushing beyond the limitations of human intuition and traditional optimization techniques. The integration of AI-discovered algorithms into mainstream software libraries represents a major milestone in the field.

This research successfully demonstrates the power of deep reinforcement learning in discovering novel, high-performance algorithms. AlphaDev has yielded significant improvements in sorting algorithms, implemented and integrated into a widely used library, showing the practical impact of this AI-driven approach. Future work could explore applying this method to other fundamental algorithms, such as hashing or cryptographic functions, and investigate the potential synergy between DRL and stochastic search methods.

While AlphaDev shows promising results, some limitations exist. The current approach is computationally intensive, requiring significant resources for training. The specific design of AssemblyGame and the reward function may influence the algorithms discovered, potentially leading to different results with alternative designs. Furthermore, the generalization of AlphaDev to other complex algorithms remains an open area for future research and investigation.