No Priors Ep. 120 | With Google DeepMind’s Pushmeet Kohli and Matej Balog

AlphaDev is an autonomous coding agent that leverages Gemini models and evolutionary search to discover new, more efficient algorithms. It represents a leap beyond boilerplate generation, demonstrating a form of technical creativity capable of making novel discoveries for open scientific problems. These discovered algorithms are not just theoretical; they are practical enough to be deployed in key parts of Google’s infrastructure, improving performance on tasks that have been heavily optimized by human experts for years.

The Evolutionary Path from AlphaGo to AlphaDev

The philosophy behind AlphaDev originates from systems like AlphaGo, which demonstrated that neural network-based systems could efficiently explore vast search spaces and uncover creative, superhuman solutions like the famous “Move 37.” This led to the question: if an AI can search for optimal moves in a game, why not for optimal algorithms in the space of computer science?

The first major breakthrough in this area was AlphaTensor (2022). It was a specialized system using reinforcement learning that discovered faster algorithms for matrix multiplication, a fundamental computational task. It proved that AI could surpass decades of human research in a specific, important domain.

However, AlphaTensor was purpose-built. The next step was to create a more general agent. This led to FunSearch, an LLM-based system that could search more naturally in the space of programs, leading to the first scientific discovery from an LLM. AlphaDev is the direct successor and extension of this work, scaling the approach to solve even more complex problems.

How AlphaDev Works: Combining LLMs and Evolution

The process hinges on a collaboration between a human user and the AI system.

1. Define the Problem with an Evaluator: The user’s primary role is to define the problem by providing a precise evaluation function. This function, often a simulator, takes a proposed algorithm as input and returns a score indicating its quality. For example, when optimizing data center job scheduling, the evaluator was a simulator that Google already used to test new scheduling algorithms.

2. Evolutionary Search: AlphaDev takes this evaluator and an optional starting point (e.g., an existing, human-written algorithm) and begins an evolutionary process:

   • Population: It maintains a diverse pool of candidate algorithms.
   • Mutation: It uses an LLM’s creative capabilities to propose novel changes and improvements to the algorithms in the pool, effectively “mutating” the code.
   • Selection: The evaluation function acts as the selection pressure, filtering out ineffective mutations and identifying promising ones.
   • Iteration: The system repeats this process, combining ideas from the strongest solutions in each “generation” to produce progressively better algorithms.

A key feature of AlphaDev is its ability to sustain this improvement over time without plateauing, allowing it to tackle problems of immense difficulty that have remained unsolved for decades.

The Crucial Role and Future of Evaluation

The evaluation function is the linchpin of the system. It allows AlphaDev to harness the “hallucinations” or creativity of the LLM for productive ends by providing a strict, objective measure of success.

While a precise evaluator is currently a prerequisite, this is not seen as a permanent conceptual limitation. Future research directions include:

• LLM-based Evaluators: Using LLMs themselves to critique and evaluate proposed solutions, a concept demonstrated in parallel work like “AI Co-scientist.”
• Imperfect Signals: Using simulators or evaluation functions that are not perfect but are correlated with the true objective. The evolutionary framework can be built to make progress even with noisy signals.

Implications for Self-Improving AI and Science

AlphaDev has been used to discover more efficient algorithms for sorting, which in turn sped up the training of future Gemini models by 23%. This represents an early, concrete example of recursive self-improvement, where an AI improves the infrastructure used to build the next generation of AI. While the current feedback loop is long (months) and the improvement is in computational efficiency, it points toward a future of potentially compounding advancements.

In science, this approach signals a fundamental shift. Many scientific challenges are search problems.

• Math and Computer Science: These are natural fits, as evaluation is often straightforward (e.g., does the proof hold? is the algorithm faster?).
• Other Sciences: The same principles apply to fields like biology and chemistry, where simulators can predict the properties of a candidate molecule, serving as an evaluation function.

The Human-AI Collaboration Model

AlphaDev is not a replacement for scientists and engineers but a powerful tool that changes their role. The human expert is crucial for:

• Problem Framing: Defining the problem and, most importantly, the evaluation criteria.
• Constraint Specification: Providing hints and constraints for the desired solution (e.g., a drug must have low toxicity).
• Interpretation and Insight: The output of AlphaDev is interpretable code. Experts can inspect, understand, and verify the discovered algorithm before deployment. This collaborative process can also yield new insights; collaborations with mathematicians revealed that AlphaDev’s algorithms contained novel mathematical symmetries, deepening human understanding.

• Tags:
• Code Generation
• LLM
• AlphaDev
• Algorithm Discovery
• Evolutionary Algorithms
• Self-Improving AI
• Gemini
• Feature