PaperlayerView exact revision on arXiv

Source-linked AI summary

Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning

Anja Surina, Amin Mansouri, Lars Quaedvlieg, Amal Seddas, Maryna Viazovska, Emmanuel Abbe, Caglar Gulcehre

arXiv:2504.05108v4cs.AIcs.LGcs.NE

TL;DR

Algorithm discovery still requires efficient methods, while existing evolutionary approaches leave LLMs as static generators. EvoTune alternates evolutionary search with RL fine-tuning of the LLM policy, and reports consistent gains over FunSearch across diverse benchmarks. The results support integrating RL with evolutionary search, although the method adds compute costs and has so far been tested at limited model sizes and sampling budgets.

  • Problem

    FunSearch-like evolutionary methods treat the LLM as a static generator rather than updating it with signals from exploration.

    Source: §1 · p. 2

  • Method

    EvoTune uses evolutionary search to explore programs and RL fine-tuning to update the LLM policy from search feedback.

    Source: §1 · p. 2

  • Results

    Across three instruction-tuned LLMs, EvoTune reports consistent performance gains over FunSearch across diverse benchmarks.

    Source: §1 · p. 3

  • Takeaways & Limitations

    EvoTune consistently achieves higher final top-50 reward scores than the baseline across evaluated LLMs and problem domains.

    Source: §4.2 · p. 6

    Experiments used 1B–3.8B-parameter LLMs and up to 22.4k outputs, and RL training adds compute costs.

    Source: §6 · p. 10

Abstract

from arXiv · show

Discovering efficient algorithms for solving complex problems has been an outstanding challenge in mathematics and computer science, requiring substantial human expertise over the years. Recent advancements in evolutionary search with large language models (LLMs) have shown promise in accelerating the discovery of algorithms across various domains, particularly in mathematics and optimization. However, existing approaches treat the LLM as a static generator, missing the opportunity to update the model with the signal obtained from evolutionary exploration. In this work, we propose to augment LLM-based evolutionary search by continuously refining the search operator - the LLM - through reinforcement learning (RL) fine-tuning. Our method leverages evolutionary search as an exploration strategy to discover improved algorithms, while RL optimizes the LLM policy based on these discoveries. Our experiments on combinatorial optimization tasks demonstrate that integrating RL with evolutionary search accelerates the discovery of superior algorithms, showcasing the potential of RL-enhanced evolutionary strategies for algorithm design.

1 Introduction

Algorithm discovery remains important as scientific and technological challenges continue to demand new efficient algorithms. EvoTune addresses the limitation of static LLM generators by combining evolutionary exploration with reinforcement-learning updates, and reports consistent gains over FunSearch across diverse benchmarks.

1 Introduction

  • Algorithm discovery matters because scientific and technological progress continues to create demand for new, efficient algorithms.Source: §1 · p. 1
  • FunSearch-like methods treat the LLM as a static generator, while EvoTune refines the search operator using feedback from evolutionary exploration.The paper argues that search alone may be inefficient and fixed training data limits exploration.Source: §1 · p. 2
  • EvoTune trains the LLM in-weight using generated-program evaluation scores as rewards, aiming to improve subsequent search.The proposed combination is motivated as a way to exploit evolutionary search and RL together.Source: §1 · p. 2
  • EvoTune uses evolutionary search for exploration and off-policy DPO to optimize the LLM policy with non-fixed inputs.The authors describe this as a tight integration of LLM-based evolutionary search and RL.Source: §1 · p. 2
  • EvoTune reports consistent performance gains over FunSearch across bin packing, traveling salesman, flatpack, Hash Code, and symbolic regression benchmarks.The experiments span three instruction-tuned LLMs.Source: §1 · p. 3
  • A modified alignment objective is presented as preserving output diversity, which the paper identifies as critical to evolutionary search.Source: §1 · p. 3

2 Preliminaries

The preliminaries frame EvoTune as search over LLM-generated programs guided by reward scores, with RL adapting the generation policy. The paper uses preference optimization to update that policy rather than directly optimizing a reward model.

2 Preliminaries

  • An LLM is represented as an autoregressive conditional distribution over output y given prompt x.The prompt is x ∈ X and the generated output is y ∈ Y.Source: §2 · p. 3
  • Evolutionary search explores LLM-generated programs to maximize reward, using gradient-free heuristics for selection, variation, and diversity maintenance.The target is the best output y* under reward r(x, y).Source: §2 · p. 3
  • EvoTune uses evolutionary-search feedback to adapt the LLM policy toward program candidates with higher scores in later iterations.Source: §2 · p. 3
  • The policy objective can regularize the trained model toward a reference policy, with β controlling KL-regularization strength.The reference policy is the initial policy π0.Source: §2 · p. 3
  • EvoTune formulates program ranking as preference optimization, avoiding a separate reward model and value function; it uses DPO as a preference-based RL algorithm.The paper describes its policy optimization as off-policy.Source: §2 · p. 3

3 EvoTune: Evolutionary search meets RL

EvoTune alternates program discovery through evolutionary search with policy improvement through RL. Search evaluates and stores candidate programs; RL uses accumulated search data to steer later generations toward higher-scoring outputs while preserving diversity.

3 EvoTune: Evolutionary search meets RL

  • EvoTune couples evolutionary discovery of programs with RL policy optimization, thereby improving both generated outputs and the model.Source: §3 · p. 4

3.1 Evolutionary search

  • At each search step, EvoTune samples high-scoring programs, builds a prompt from two program-score pairs and a task description, then generates candidate outputs.The task prompt uses Chain-of-Thought style to encourage pattern identification across stronger and weaker programs.Source: §3.1 · p. 4
  • Generated programs are evaluated on validation instances; successful candidates receive performance scores and are added to the program database.The database clusters programs into islands that are evolved separately.Source: §3.1 · p. 4

3.2 RL training

  • After every fRL search iterations, RL fine-tunes the policy on accumulated data to favor higher-scoring programs; the implementation uses DPO for efficiency and simplicity.Source: §3.2 · p. 4
  • DPO preference pairs compare higher- and lower-scoring valid outputs from the same prompt, and can pair invalid outputs against valid ones.The method also filters the preference dataset and trains on high-scoring programs from all search phases to maintain diversity.Source: §3.2 · p. 5

4 Experiments

The experiments evaluate EvoTune on three core combinatorial optimization tasks and broader benchmarks, comparing it with FunSearch across models, tasks, and evaluation settings. EvoTune generally finds better programs and more diverse solutions, with results also reported for alternative training choices and specialized baselines.

4.1 Evaluation tasks

  • Evaluation covers bin packing, TSP, and flatpack, where evolved programs assign items to bins, propose TSP penalties for Guided Local Search, or score block placements.The core evaluation also includes two Hash Code challenges and two symbolic-regression tasks.Source: §4.1 · pp. 5–6
  • Programs are evaluated on validation, perturbed-validation, and test sets; comparisons average 10 seeds, and reward is the negative optimality gap.The broader evaluation includes Hash Code server placement and ride assignment, plus symbolic-regression tasks for material stress and bacterial growth.Source: §4.1 · p. 6, §4.2 · p. 6

4.2 Results

  • Across evaluated models and domains, EvoTune achieves higher final top-50 rewards than FunSearch; Table 1 reports lower mean optimality gaps across core tasks, splits, and sampling budgets.Table 1 covers bin packing, traveling salesman, and flatpack, with results averaged over 10 seeds.Source: §4.2 · p. 6, Table 1 · p. 7
  • EvoTune outperforms FunSearch on validation-perturbed and test sets across all evaluated tasks and models.The comparison measures programs accumulated in the database up to each sampling budget.Source: §4.2 · p. 8
  • EvoTune’s database gains more high-scoring, low-gap programs and unique scores; average rewards also rise in nearly every run, while top-program gains require more tuning.The top-50 reward summarizes promising search regions rather than a potentially isolated high-reward program.Source: §4.2 · pp. 6, 8, Figure 2 · p. 7
  • Forward-KL DPO finds better top programs and more unique solutions than reverse-KL DPO; ReSTEM underperforms DPO, while more prompt examples bring no considerable gains.The KL ablation uses Llama3.2 1B Instruct on bin packing; ReSTEM is more hyperparameter-sensitive.Source: §4.2 · p. 9
  • On Hash Code datacenter optimization, EvoTune scores 418 versus the top human score of 407; it also outperforms FunSearch across LLM-SR optimization trajectories and evaluation sets.On Stress-Strain, Phi-3.5 Mini (3.8B) surpasses the cited Mixtral 8x7B and GPT-3.5-turbo baselines.Source: §4.2 · p. 9
  • EvoTune also discovers solutions surpassing specialized non-LLM methods and established human-designed heuristics.The paper provides full experimental details in Appendix A.12.Source: §4.2 · p. 9

5 Related Work

Related work spans LLM-driven evolutionary search, prompt optimization, and self-improvement training. EvoTune differs by using RL to refine the generator policy during evolutionary algorithm search.

Evolutionary search with LLMs

  • ELM uses RL to condition generation for new domains, while EvoTune uses RL to refine the generator policy; other cited methods evolve heuristics or algorithms without training.The passage contrasts EvoTune with ELM (Lehman et al. (2023)), Liu et al. (2024), Ye et al. (2024), and Liu et al. (2023a).Source: §5 · p. 9

Prompt optimization

  • Prompt-optimization approaches vary prompts or mutation operators, but the cited methods do not update the generator policy while iterating over algorithms.EvoPrompt (Guo et al. (2023)) combines evolutionary search with LLMs for prompt optimization without a learning component.Source: §5 · pp. 9–10

Self-improvement and self-training

  • Self-improvement methods fine-tune models on selected self-generated outputs; EvoTune applies this pattern to solutions discovered during evolutionary search.The passage cites Zelikman et al. (2022), Gulcehre et al. (2023), Singh et al. (2023), Ishibashi et al. (2024), and Pang et al. (2024).Source: §5 · p. 10

6 Conclusion

The conclusion presents EvoTune as an RL-enhanced evolutionary search method for algorithm discovery. It reports improved search outcomes while noting unresolved questions about scaling and compute costs.

6 Conclusion

  • EvoTune combines evolutionary exploration with RL fine-tuning and outperforms a search-only baseline on combinatorial optimization and symbolic-regression tasks.The reported benefits include better single-best or top-k performance, rather than only higher population-average scores, while maintaining sampled-function diversity through techniques such as Forward KL regularization.Source: §6 · p. 10
  • Experiments cover 1B–3.8B-parameter LLMs and up to 22.4k outputs; larger models and sampling budgets are needed to assess the method’s potential fully.RL training adds compute costs, leaving training-versus-inference trade-offs for future investigation.Source: §6 · p. 10
  • The authors present combining evolutionary search and reinforcement learning as a promising direction for future LLM-based algorithm discovery.Source: §6 · p. 10

Ethics Statement

The ethics statement notes that stronger LLM capabilities may support algorithm discovery but also raise misuse concerns.

Ethics Statement

  • Enhanced LLM capabilities may advance scientific and industrial algorithm discovery, but could also enable malicious algorithms, motivating safeguards and ethical guidelines.Source: Ethics Statement · p. 10

A.1 Evaluation tasks

The evaluation tasks cover bin packing, traveling salesman, flatpack, two Hash Code competitions, and two symbolic-regression settings, with task-specific validation or holdout data.

Bin packing problem

  • Bin packing uses 20 validation instances of 500 items, with performance measured by excess bins relative to the lower bound.Perturbed validation shuffles item order; test instances are newly sampled from the same distribution.Source: §A.1 · p. 16

Traveling salesman problem

  • Traveling salesman evaluation samples city coordinates for instances of size 100 and 200 and measures route excess cost over the Elkai optimum.Perturbed validation raises each edge cost with probability 0.2; test instances are newly sampled.Source: §A.1 · p. 17

Flatpack problem

  • Flatpack’s validation set contains 45 instances—15 on 9 × 9 grids, 20 on 11 × 11, and 10 on 15 × 15; perturbed validation adds a central rectangle obstacle that prevents placements there.The test set follows the same grid-size distribution as the training set.Source: §A.1 · p. 17

Hash Code datacenter optimization

  • The datacenter task evolves a server-placement and pool-assignment heuristic to maximize the minimum guaranteed capacity across pools after a single-row failure.Programs are evaluated on one fixed instance from the original competition benchmark.Source: §A.1 · p. 17

Hash Code self-driving rides

  • The rides task evolves a function that selects a ride for each car from its location and time, scoring holdout performance by distance covered and early-start bonuses.The initial policy chooses the first feasible ride, if one exists.Source: §A.1 · p. 17

LLM-SR tasks

  • Symbolic regression covers aluminium stress across six temperatures, with 200°C held out for OOD validation, and synthetic E. coli growth data tested on out-of-range parameters.The stress task lacks a standard closed-form solution; bacterial-growth data uses custom formulations to discourage memorization.Source: §A.1 · pp. 17–18

A.2 Guided local search

The TSP procedure combines local search with LLM-guided perturbations: it penalizes selected edges to move the search away from previously explored tours.

A.2 Guided local search

  • Guided Local Search (GLS) improves local search by penalizing features associated with suboptimal solutions, helping the search escape local optima.The penalties adjust the objective function and discourage revisiting undesirable regions.Source: §A.2 · p. 18
  • For TSP, the procedure starts with a nearest-neighbor tour and alternates local search and perturbation for 16 rounds at size 100 or 8 rounds at size 200.The variation interleaves local search with perturbations.Source: §A.2 · p. 18
  • Local search uses Relocate-Once, which moves one city, and Two-Opt, which reconnects tour segments after removing two edges.Two-Opt can eliminate crossings associated with suboptimal tours.Source: §A.2 · p. 18
  • An LLM-generated guide scores tour edges for perturbation; the highest-utility edge receives an increased penalty that adjusts weights for subsequent local search.The weighted penalties encourage exploration of alternative routes.Source: §A.2 · p. 18

A.3 Extended related work

Neural combinatorial optimization learns to construct solutions from instance embeddings, whereas this work searches for algorithms or heuristics applicable across problem sizes.

A.3 Extended related work

  • Neural combinatorial optimization (NCO) learns to construct combinatorial solutions using embeddings of problem instances as input.Source: §A.3 · p. 19
  • NCO models can be trained with either supervised learning or reinforcement learning.Source: §A.3 · p. 19
  • Unlike NCO, this work searches for an algorithm or heuristic that can later be used with problems of any size.Source: §A.3 · p. 19

A.4 Program database

The program database is organized into independently evolving islands and score-based clusters, from which the method samples programs to construct prompts.

A.4 Program database

  • Each island evolves independently, and programs within an island are grouped into clusters according to their scores.Source: §A.4 · p. 19
  • Prompt construction samples one island, then draws clusters by a score-based softmax and selects one program from each, favoring shorter programs.Different clusters provide varied scores and reduce superficial similarity; sampling is annealed toward higher-scoring percentiles over time.Source: §A.4 · p. 19
  • New outputs are returned to the same island used to sample the prompt, a choice intended to limit similarity and broaden exploration.Source: §A.4 · p. 19

A.5 RL formulation of EvoTune

This section describes EvoTune’s terminal-reward RL formulation for token generation, its iterative policy updates using dynamically generated preference data, and its training and prompting procedures. It summarizes evaluations reporting advantages over FunSearch and untrained or human-designed baselines, stronger DPO than ReSTEM across tested learning rates, and TSP generalization to unseen TSPLib instances with the best average performance at tmax = 1000.

A.5 RL formulation of EvoTune

  • EvoTune models partial prompt-output sequences as states, next-token samples as actions, deterministic token-appending transitions, and undiscounted task-evaluation rewards at termination.Its dynamically generated program database and iterative output generation make DPO off-policy; with deterministic transitions and terminal rewards, the formulation also reduces to a one-step bandit over full outputs.Source: §A.5 · pp. 19–20

A.6 DPO dataset filtering

  • DPO data filtering retains higher-quality, diverse samples using the 30th percentile of rewards from newly generated outputs as a moving threshold.Because the threshold is recalculated from recent outputs, it rises naturally as average reward improves.Source: §A.6 · p. 20

A.7 LLM prompts

  • Each LLM query concatenates the system prompt, two sampled programs with scores, and a task description; the prompt asks for a better function that analyzes score drivers and explores novel variations.Source: §A.7 · p. 20

A.8 Experimental details

  • Experiments use six database islands, two programs per prompt, eight outputs per prompt, and alternate phases every 3,200 outputs, totaling about 22,400 samples.The learning-rate schedule decays over time to balance early training with the larger late-stage dataset.Source: §A.8 · pp. 21–22

A.9 Results on Hashcode competition problems and LLM-SR benchmarks

  • On Stress-Strain, EvoTune outperformed both larger LLM-SR baselines on ID and OOD tests; it also outperformed FunSearch during equation evolution.On Datacenter Optimization, both methods beat the best human-team solutions; on Self-Driving, neither did, but they reached 87.6% and 87.1% percentiles, respectively. EvoTune remained competitive with other methods on E. coli Growth.Source: Figure 4 · p. 22, §A.9 · pp. 22–23, Table 2 · p. 23

A.10 Additional results for bin packing, travelling salesman problem, and flatpack

  • EvoTune surpassed FunSearch in most single-program optimality-gap cases and generated higher average-scoring valid programs throughout the search.As search progressed, its score distributions shifted toward lower optimality gaps by discovering more high-scoring programs.Source: Table 3 · p. 23, Figure 5 · p. 24, §A.10 · p. 24
  • t-SNE embeddings show structured clusters that diverge from initialization as sampling increases, with functions from the same database island tending to be more semantically similar.The visualizations use NeoBERT embeddings and color functions by island or discovery timestep.Source: §A.10 · pp. 24, 28, Figure 9 · p. 28

A.11 Generated programs

  • The appendix lists the best BP, TSP, and FP heuristics found by Phi 3.5 Instruct 3.8B, Granite 3.1 2B Instruct, and Llama3.2 1B Instruct, respectively.Source: §A.11 · p. 29
  • EvoTune’s highest-scoring listed programs reached optimality gaps of 2.06 for bin packing, 2.446 for TSP, and 0.0829 for flatpack.They were generated using Phi 3.5 Instruct, Granite 3.1 2B Instruct, and Llama3.2 1B Instruct, respectively.Source: §A.11 · pp. 30–32

A.12 Comparison to non-LLM-based methods

  • The study uses the tasks to evaluate EvoTune against untrained baselines, while also contextualizing performance against specialized TSP methods and human-designed heuristics.The authors state that achieving state-of-the-art performance on specific benchmarks was not the primary goal, particularly given their use of smaller open-source LLMs.Source: §A.12 · p. 32
  • On 29 unseen TSPLib instances, EvoTune’s Granite TSP heuristic performs comparably on average at tmax = 100 and 200 and achieves the best average at tmax = 1000.The heuristic was trained with tmax = 20, below the specialized baselines’ tmax = 1000.Source: §A.12 · p. 32, Table 4 · p. 33
  • With 22.4k samples, EvoTune discovered bin-packing and flatpack algorithms that outperform their human-designed starting heuristics and consistently find the best-scoring solutions.The human-designed heuristics initialize the search process.Source: §A.12 · pp. 32–33, Table 5 · p. 33

A.13 Alternative RL algorithm

  • ReSTEM iteratively fine-tunes the base model on high-scoring evolutionary-search outputs, progressively filtering the program database; the experiments used p = 60 and L = 3.Unlike DPO’s ranking-based objective, ReSTEM uses supervised fine-tuning on the refined dataset at each RL update.Source: §A.13 · p. 33
  • Both offline RL updates outperform no training, and DPO achieves lower optimality gaps than ReSTEM across all tested learning rates.Figure 10 reports mean optimality gap for the top 50 validation programs at the final sampling budget, averaged over 10 seeds, on Granite bin packing.Source: §A.13 · p. 33, Figure 10 · p. 34
  • ReSTEM performance rapidly degrades with suboptimal hyperparameters, and the experiments omitted an initial SFT phase to reduce training time.The authors identify learning rate as impactful, note that a broader hyperparameter sweep is needed, and suggest exploring hybrid SFT-DPO approaches.Source: §A.13 · p. 34
Loading 2504.05108v4…