Technical Summary: Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning

Problem Statement

The discovery of efficient algorithms for complex problems, particularly in mathematics and combinatorial optimization, has historically relied on substantial human expertise. While recent advancements in Large Language Models (LLMs) combined with evolutionary search (e.g., the FunSearch method) have shown promise in automating this discovery, existing approaches treat the LLM as a static generator. These methods utilize the LLM to propose new programs based on previous successes but fail to update the model's internal parameters based on the signals obtained during the evolutionary exploration. Consequently, they miss the opportunity to leverage the LLM's parametric nature to refine its search policy over time, potentially leading to suboptimal convergence or inefficient exploration of the solution space.

Methodology: EvoTune

The authors propose EvoTune, a framework that tightly integrates evolutionary search with Reinforcement Learning (RL) to continuously refine the LLM search operator. The method operates in an iterative loop consisting of two alternating phases:

1. Evolutionary Search (Exploration):

   • The LLM generates candidate Python programs (algorithms) based on prompts constructed from high-scoring programs discovered in previous iterations.
   • These programs are evaluated on specific combinatorial optimization tasks (e.g., Bin Packing, Traveling Salesman Problem, Flatpack) to obtain reward scores (typically the negative optimality gap).
   • Valid programs and their scores are stored in a program database, organized into "islands" to maintain diversity and prevent premature convergence.
   • The search employs a "bootstrapping" strategy, where the LLM analyzes the differences between high-performing and low-performing programs to guide the generation of new candidates.

2. RL Training (Refinement):

   • Periodically (every $f_{RL}$ iterations), the LLM's generation policy ($\pi_\theta$) is updated using the accumulated data from the evolutionary search.
   • The authors formulate this as a Preference Optimization problem. They construct a preference dataset $D_{pref}$ consisting of triplets $(x, y^+, y^-)$, where $x$ is the prompt, $y^+$ is a program with a higher reward, and $y^-$ is a program with a lower reward.
   • The model is fine-tuned using Direct Preference Optimization (DPO). Unlike standard offline DPO, EvoTune operates in an off-policy setting where the data is dynamically generated by the evolving model itself.
   • Diversity Preservation: A critical design choice is the use of Forward KL regularization (as opposed to the more common Reverse KL) within the DPO objective. This encourages "mass-covering" behavior, preventing the model from collapsing into a single mode and preserving the output diversity essential for effective evolutionary search.

Key Contributions

1. Integration of RL into Evolutionary Search: The paper claims to be the first to demonstrate the potential of tightly integrating LLM-based evolutionary search with RL fine-tuning in the loop. Unlike previous methods that use LLMs solely as static generators, EvoTune updates the model weights to better utilize insights gained from exploration.
2. Accelerated Algorithm Discovery: By refining the search policy via RL, the method accelerates the discovery of superior algorithms. Experiments across three instruction-tuned LLMs (Llama3.2 1B, Phi 3.5 Mini, Granite 3.1 2B) show consistent performance gains over the baseline FunSearch method.
3. Diversity-Preserving Alignment: The authors demonstrate the advantage of using a modified alignment objective (Forward KL-regularized DPO) to preserve output diversity. This is critical for evolutionary strategies, as mode collapse can hinder the discovery of novel solutions.
4. Broad Applicability: The method is validated on diverse benchmarks, including standard combinatorial problems (Bin Packing, TSP, Flatpack), real-world Google Hash Code challenges (Datacenter Optimization, Self-Driving Rides), and symbolic regression tasks (LLM-SR).

Experimental Results

The authors evaluated EvoTune against a FunSearch-style baseline (evolutionary search without model training) across multiple tasks and models:

• Performance Gains: EvoTune consistently achieved higher final reward scores (lower optimality gaps) for the top 50 discovered programs compared to the baseline. The performance gap often widened as the sampling budget increased, suggesting that larger budgets amplify the method's advantages.
• Generalization: The evolved programs demonstrated robustness on validation-perturbed sets and test sets drawn from the same distribution, indicating that the learned policies generalize beyond the specific instances seen during training.
• Real-World Benchmarks:
  • On the Google Hash Code Datacenter Optimization task, EvoTune achieved a score of 418, surpassing the top human score of 407 and outperforming the FunSearch baseline (414).
  • On Symbolic Regression tasks (LLM-SR), EvoTune outperformed the evolutionary baseline and, notably, surpassed baselines using larger or proprietary models (e.g., Mixtral 8x7B, GPT-3.5-turbo) while using a smaller model (Phi-3.5 Mini, 3.8B parameters).
• Ablation Studies:
  • Forward vs. Reverse KL: Experiments confirmed that Forward KL regularization yields higher rewards and a greater number of unique solutions compared to Reverse KL, validating the importance of diversity preservation.
  • Alternative RL: The authors tested ReSTEM (Supervised Fine-Tuning on high-scoring outputs) as an alternative to DPO. Results indicated that DPO consistently outperformed ReSTEM and was less sensitive to hyperparameter tuning.

Significance and Claims

The paper positions EvoTune as a significant step forward in automated algorithm design by addressing the "Bitter Lesson" (Sutton, 2019), which argues that search and learning are synergistic. The authors claim that:

• Synergy: Search generates new data, while learning distills patterns from that data to guide future exploration more effectively.
• Efficiency: Integrating RL allows the system to move beyond merely increasing the average score of a population; it actively guides the evolutionary search toward superior solutions (measured by top-k performance) while maintaining the diversity required for innovation.
• Scalability: The method demonstrates potential for scaling to real-world settings, as evidenced by its success on complex, non-synthetic problems like datacenter optimization and stress-strain modeling.

The authors modestly acknowledge limitations, noting that their experiments were conducted with models ranging from 1B to 3.8B parameters and that further scaling of model size and sampling budgets is needed to fully understand the method's potential. They also highlight the trade-off between the additional compute costs of the RL training phase and the gains in inference efficiency and solution quality.