Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning
Authors: Anja Šurina
Amin Mansouri
Lars C.P.M. Quaedvlieg
Amal Seddas
Maryna Viazovska
Emmanuel Abbe
Caglar Gulcehre
Venue: COLM 2025 (2025)
Keywords: Large Language Models
Reinforcement Learning
Evolutionary Search
Algorithm Discovery
Self-Improvement
AI for Math
TL;DR: We propose an approach that integrates LLM-based evolutionary search with RL fine-tuning for accelerated discovery of algorithms, as demonstrated on combinatorial optimization tasks.

Abstract: 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.

Published as a conference paper at COLM 2025
Algorithm Discovery With LLMs:
Evolutionary Search Meets Reinforcement Learning
Anja Surina', Amin Mansouri', Lars Quaedvlieg', Amal Seddas', Maryna Viazovska', Emmanuel Abbe'2, Caglar Gulcehre' EPPFL2Appl
Abstract
Discovering efficient algorithms for solving complex problems has been an outstanding challenge in mathematics and computer science, requiring subslantial human expertise over the years. Recent advancements in evolu- tionary search with large language models (LLMs) have shown promise in accelerating the discovery of algorithms across various domains, particu- larly 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 refin- ing 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 opti- mization tasks demonstrate that integrating RL with evolutionary search accelerates the discovery of superior algorithms, showcasing the potential RL-enhanced evolutionary strategies for algorithm design.
Introduction
The ability to solve complex problems efficiently is at the heart of scientific and technological advancement. Whether calculating planetary trajectories, analyzing genomic sequences, ensuring reliable communications; or solving large-scale optimization problems, these challenges require formal and systematic methods to process, analyze, and transform information into decisions by means of algorithmss. Thus, the history of algorithm design is as ancient mathematics itself. From early examples like Euclid's 's algorithm for computing the greatest common divisor and the Sieve of Eratosthenes for identifying prime numbers to modern advancements such as gradient descent (Ruder, 2016) and backpropagation (Rumelhart al., 1986; Kelley, 1960), the discovery effective computational methods has consistently shaped the trajectory of science and technology. Despite rapid advancements, the demand for new and efficient algorithms remains strong, as scientific and technological progress continuously presents new challenges. Hence, the impact of well-crafted a algorithms make their discovery an everlasting pursuit of significant importance.
Today, this pursuit finds powerful ally in the unprecedented capabilities of large language models (LLMs). As some of the recent models exhibit reasoning-lle behavior (OpenAI, 2024; DeepSeek-AI Al et al., 2025), new opportunity arises where LLMs could assist algo- rithm design, reshaping problem-solving across disciplines. A particularly powerful way to harness such capabilities for algorithm design through evolutionary search strategies that explore the space of algorithms as executable programs. By combining LLMs with evolu- tionary search, researchers have achieved remarkable breakthroughs, including discovering novel mathematical constructs that surpass existing knowledge on challenging problems (Romera-Paredee et al., 2024), designing reward functions for training robotic policies (Ma
"oorrespondence to anja suri na@epf1 cc 'We open source our code implementation in https: / //el/t re- labo. abbo.githu.... weittub.io/eeee io/EveTune/ to facilitate future research in this promising area.
1

---

Published as a conference paper at COLM 2025
Evolutionary Search
Training
Rewerd viy
M
Evclucte
Store
7
vig
Update LLM Policy
Prompt
Figure 1: Method overview: EvoTune iteratively alternates between two phases: (a) evo- lutionary search that iteratively improves solutions by bootstrapping from the best ones discovered so far, and (b) RL fraining, which updates the model parameters based infor- mation gained from the search process. this loop, evolutionary search used to explore the space of programs efficiently and collect data, and RL is used to improve the policy based on the data generated with evolutionary search. Python programs generated by an LLM are evaluated set of combinatorial optimization problem instances and then stored in a program database for later use in RL training and prompt construction.
et al., 2023), developing preference optimization algorithms (Lu et al., 2024), and outper- forming top human teams in combinatorial competitive programming (Veličković et al., 2024).
An influential approach in this line of research is the FunSearch method (Romera-Pareder, et al., 2024). Funsearch iteratively proposes new solutions, represented programs, by combining the most promising programs discovered in earlier iterations. Bootstrapping on previous successes gradually improves the performance of the best program found.
Although FunSearch-like methods achieve impressive results, they regard the LLM as static generator and do not take advantage of the fact that LLMs are parametric models that can be optimized for specific objectives. Thus, in our work, we propose to augment evolutionary search with LLMs by continuously refining the search operator, the LLM, through RL fine-tuning using feedback from evolutionary exploration. This aligns with the "Bitter Lesson" " (Sutton, 2019), which argues that search and learning are synergistic: Search generates new data, while learning distills patterns from the data to guide future exploration more effectively. Furthermore, most Al systems that have outperformed human performance from board games (Silver et al., 2016) to real-time strategy games (Vinyals et al., 2019) - have relied on RL in a similar spirit (Sutton & Barto, 2018; Fawzi et al., 2022; Berner et al., 2019), demonstrating the power of this synergy. Using search alone is inefficient and may fail to capture emergent patterns while relying on a fixed dataset for training limits exploration.
Motivated by this gap, we hypothesize that combining reinforcement learning with FunSearch-like approach can exploit the strengths of both paradigms, enabling more effec- tive algorithm discovery. Similarly to alignment methods (Ouyang et al., 2022; Stiennon et al., 2020), we propose train the LLM in-weighht using the evaluation scores of the gener- ated programs as the reward signal. By adding in-weight training, we aim to enable the model better utilize insights gained from exploration to improve understanding of the search space and therefore enable better-targeted search at subsequent iterations.
Our contributions are summarized as follows:
To the best of our knowledge, we are the first to demonstrate the potential of tightly integrating LLM-based evolutionary search with RL in the loop. Our method EvoTune uses evolutionary search as an exploration strategy and RL to optimize and improve the policy. For updating the policy, we employ the DPO algorithm (Rafailov et al., 2024); however, in contrast to its standard offline formulation, we leverage it in an off-policy setting with non-fixed inputs.
2

---

Published as a conference paper at COLM 2025
By improving the efficiency of the search mechanism, our method accelerates the discovery of superior algorithms. Our experiments spanning three instruction- tuned LLMs demonstrate consistent performance gains over the baseline FunSearch method across a diverse set of benchmarks, including bin packing, the traveling salesman problem, flatpack, Hash Code programming competition problems, and symbolic regression tasks.
We show the advantage of using a modified version of the standard alignment objective in terms preserving output diversity, which is critical to the success of evolutionary search strategies.
2 Preliminaries
Here, we provide a basic overview of the components needed for the workflow of EvoTune. comprises three components: 1) LLM, 2) evolutionary search, and 3) RL training.
LLMs In this work, we use pre-trained LLMs and denote an LLM as (-p-))), which models conditional distribution Ty (y(())) autoregressively. E X' corresponds to the input prompt and E y corresponds to the output generated by the model.
Evolutionary search Evolutionary search can be defined as an iterative optimization process inspired by biological evolution (Goldberg Holland, 1988). In the context of LLMs, the goal is to explore the space of LLM-generated programs to maximize a fitness function represented by the reward score r(x,y) (Lehman et al., 2023). The optimization process to find the best output y" is typically gradient-free, using search heuristics for selection, variation, and diversity maintenance:
arg max
max E,-D 1y
RL training RL has proven be powerful tool for optimizing policies in complex search spaces, especially when a well-defined reward function is available (Silver et al., 2016; Fawzi et al., 2022; Sutton & Barto, 2018; Vinyals al., 2019). In EvoTune, we integrate RL into the evolutionary search to refine the LLM generation policy over time. Using feedback from the evolutionary search phase, we adapt the parameters of the LLM generate program candidates that achieve higher performance scores in subsequent search iterations.
To optimize the LLM policy Ti we can employ an RL objective with regularization keep the outputs of reference model [y x) and trained model 7i (y(x)) close to each other:
max Ex-Dyy [xx, y)] (Dy (xxxx xx)xxx))))) T2g
where Dy is an f-divergence typically implemented with reverse KL-divergence, f hyperparameter controlling the strength of the KI. regularization and πh is the reference policy, in our case the initial policy nig, corresponding to the base LLM. It possible to maximize the reward model scores r rxx, directly, for example, using PPO (Schulman al., 2017). However, PPO-style methods would be more expensive, and instead, we formulate the task as a preference optimization problem so that LLM-generated programs can be ranked according to r(x,y), which makes the objective amenable to preference-based RL algorithms such as (Rafailov et al., 2024; Calandriello et al., 2024). Preference optimization methods bypass the learning of the separate reward model and do not require value function, which makes them more efficient than the on-policy RL methods. We provide reinforcement learning formulation of EvoTune in Appendix A.5, along with discussion of how it constitutes policy optimization in an off-policy manner.
y",y"" y²) > the loss function can be defined as For a preference data set Dpref = {(x", (xx,,",,
the objective of direct preference optimization (DPO) (Rafailov et al., 2024; Wang et al., 2023):
3

---

Published as a conference paper at COLM 2025
To - Ty x))
BB Toly- x) Teerly- x)) ) (3)
(TT Fref) E (x Dror
logo $f
o represents the sigmoid function, and f' depends on the chosen f-divergence. For example, for forward KL, (u) -1/u, u,, and for reverse KL, f log it + 1.
EvoTune: Evolutionary search meets RL
EvoTune tightly combines evolutionary search with RL, where evolutionary search is used to discover new programs, and RL subsequently used to optimize the pol- icy with the better programs found by evo- lutionary search. Thus, EvoTune simulta- neously improves both the outputs of the model and the model itself. We illustrate the pseudocode for EvoTune in Algorithm 1 and explain the two key components of our process: 1) Evolutionary search and 2) RL training.
Algorithm 1 EvoTune
Initialize: Program database D with initial programs and policy (base LLM) xz.. to do
Sample a subset of programs from D Construct new prompt from the sam- pled programs.
Generate K outputs (y K J== by sampling
from ( |x)).
Extract candidate programs from outputs and evaluate them on the validation set to obtain reward scores r(yl*). Update the program database:
3.1 Evolutionary search
In evolutionary search phase, EvoTune ex- plores the space of possible programs to expand the program database denoted as D'. This database stores all valid programs generated up to the timestep t. At each timestep, EvoTune selects a subset of high- scoring programs from D' and constructs prompt x². The prompt is constructed by concatenating m = 2 program-score pairs, followed by a task prompt that briefly describes the problem. This task prompt is structured in Shiin-of-Though (CoT) prompt style (Wei et al., 2022) (see Appendix A.7 for the prompt details) and encourages the LLM to identify patterns in how high-performing programs differ from the worse-performing ones.
D Dt I (xt, y r(y+*))) if mod fRI. then TT + RI-Updaaee (=g. D*).
else
no. - n² 1. end if end for
The LLM generation policy vth is then conditioned on the prompt x' to generate K new out- puts {yt where every output consists of program and the rationale behind it. Each generated program is evaluated on predefined set of validation task instances. Programs that are successfully evaluated without errors or exceeding computational constraints are assigned score based on their performance. The evaluated programs and their respective scores are subsequently registered in the program database D'.
Program database Similar the FunSearch method (Romera-Paredes et al., 2024), we use an ssland-based program database (Tanese, 1989; Cantú-Paz et al., 1998). We cluster programs into separate "islands" and evolve each island in isolation. Further details on the program database can be found in the Appendix A.4.
3.2 RL training
During the RL training phase, the generation policy nτ, is updated to improve its ability to generate high-quality outputs. After fRL. search iterations, the policy is fine-tuned using RL objective on the accumulated dataset D' to steer the policy toward generating programs with higher scores. While our framework is compatible with various RL algorithms in place of RL-Upddaee-) from Algorithm 1, we opt for DPO (Rafailov et al., 2024) due to its efficiency and simplicity.

---

Published as a conference paper at COLM 2025
Preference dataset As DPO fine-tuning works with preferences, update the preference pref {(1x, """""""""""""""""""""""""""" "=") Each triplet consists of prompt x' and two LLM outputs (each containing a program and a reasoning trace). The output containing the higher scoring program is denoted as yd" and the output with the lower scoring program as yL"".
dataset at each iteration D pref - D
f To construct triples (x', ,44 _y"",, we start by taking all K outputs {yd*) Jk=1 generated from the same prompt x². The outputs with valid programs those that successfully passed the evaluation scoring and the lower-scoring half. We then randomly pair up members of these two groups so that each output yd is used at most once. In addition, we create extra preference pairs by matching failed outputs those that contain an invalid program with outputs containing a valid program. This process results in the design of N' preference pairs per prompt x².
divided into two groups preppaaoon according to their reward r(yt*): the higher-
To improve the quality of the dataset D pref' we employ an additional filtering step that excludes triplets "f",""""y" for which the reward of the higher scoring output r(y!") does not exceed a dynamically determined threshold r!. For a detailed description of threshold filtering, refer to Appendix A.6.
Maintaining output diversity throughout training Output diversity is crucial for effective evolutionary search, yet RL fine-tuning can reduce (Shumailov et al., 2024; Kirk al., 2023; Casper et al., 2023). To mitigate this, we use forward KL-regularized DPO objective (Equation 3), which encourages mass-covering behavior and avoids the mode collapse that is often induced by reverse KL (Wang et al., 2023). We set high B to ensure strong regularization. Additionally, we train on high-scoring programs from all search phases - not just recent ones to maintain much diversity as possible in the DPO dataset. Furthermore, each run is initialized from the base model reJ, following Singh et al. (2023). Hyperparameter details are in Appendix A.8.
4 Experiments
4.1 Evaluation tasks
We evaluate our approach three well-known combinatorial optimization tasks that are suitable benchmarks for Python program generation by LLMs. Specifically, we focus on the online bin packing (BP) problem (Coffman Jr et al., 1984), the traveling salesman (TSP) problem (Jünger et al., 1995; Gutin & Punnen, 2006), and the flatpack (FP) problem (Bonnet et al., 2023).
Bin packing In the BP problem, the objective is to assign an incoming stream of varying- sized items to as few fixed-size bins as possible. For each item, our method evolves priority function (i.e., Python program) that determines which bin should receive the item, given both the item's 's size and the current state of all bins (Romera-Parede initialize the search, we begin with best-fit heuristic function. This heuristic places each incoming item into the fullest bin with enough space to accommodate it.
et al., 2024). To
Traveling salesman problem With TSP, each problem instance is represented by a fully connected graph whose nodes correspond to cities and edges correspond to connections between them. Given a distance matrix specifying the inter-city distances, the objective is to find minimal-distance route that passes through all cities. In our experiments, the evolved Python program used in conjunction with a Guided Local Search (GLS) (Voudouris & Tsang, 1999; Alsheddy et al., 2018), following previous work by Liu et al. (2024); Ye et al. (2024). The LLM's task is to propose heuristics for computing penalty matrix based on the input distance matrix. This penalty is used iteratively in the GLS procedure to penalize certain edges in the solution. For TSP, we use the identity function as the starting point for evolutionary search.
5

---

Published as a conference paper at COLM 2025
Flatpack For FP, each problem instance is represented by two-dimensional grid and set of randomly generated connected blocks maximum size 3 x 3. The objective is to sequentially place all blocks in any rotation onto the grid without overlap, maximizing the fraction of the grid covered. In our experiments, the evolved Python program receives the current state of the grid input, and oulputs scores for each possible combination of block, rotation, and placement location. Higher scores are interpreted as better placements, and the combination with the highest score that results in valid placement is selected. This process is repeated sequentially until no more blocks can be placed. We initialize the search with a function that assigns the same score all all possible block, rotation, and location combinations.
Evaluation protocol In addition to evaluating our method on the validation set, we also evaluate on the vulidation-perturbee set with controlled modifications of the validation set, and the fest set consisting of new problem instances drawn from the same distribution as the validation set. For all tasks, performance is measured with the optimality gap. Details on the dataset construction, instance perturbation, and metric definitions are provided in Appendix A.1.
Broader Evaluation Scope To further evaluate the generality of our approach, we include two additional sets of benchmarks. First, we tackle two real-world combinatorial optimiza- tion challenges from the Google Hash Code programming competition (Veličković al., 2024), which involve optimally placing servers in a datacenter to maximize fault tolerance and assigning fleet of self-driving cars ride requests. Second, we address two symbolic regression tasks from the LLM-SR benchmark suite (Shojaee et al., 2024). These tasks aim to uncover underlying scientific equations from observational data and require modeling the mechanical stress behavior of a material and discovering a differential equation for bacterial growth dynamics. Appendix A.1 provides detailed descriptions of these additional tasks.
4.2 Results
We compare EvoTune against FunSearch-style baseline (Romera-Paredes et al., 2024) denotes simply as FunSearch. This baseline uses only evolutionary search and does not involve training the LLM. We test our method on three instruction-tuned LLMs: Llama3.2 1B Instruct (Dubey et al., 2024), Phi 3.5 Mini Instruct (Abdin al., 2024), and Granite 3.1 2B Instruct (Granite Team, 2024). To account for the high experimental variability, each reported result is the average of ten random seeds. Our objective is to maximize the reward, which we define the negative of the optimality gap. Hence, minimizing the optimality gap is equivalent to maximizing the reward.
During program evolution (t O,..., T), we evaluate LLM-generated programs problem-specific validation set of problem instances. In Figure (Top) we report the progres- sion of the reward of the 50 rest-rerformnng discovered programs. Compared to evaluating a single best program, the top-50 metric allows us to obtain more robust estimates as it indicates whether the search policy found more promising regions within the search space, rather than sampling an isolated high-reward program by chance. For completeness, we also report the best overall program scores (top 1 scores) in the Appendix A.10.
Across all evaluated LLMs and problem domains, our method, EvoTune, consistently achieves higher final top-50 reward scores compared to the baseline. This improvement demonstrates that refining the search policy via RL accelerates the discovery of high-quality algorithms. Notably, in most cases, the performance gap between the baseline and FvoTure widens more programs are sampled, suggesting that larger sampling budgets could amplify our method's advantage over the baseline.
In addition to the top-50 metric, EvoTune attains higher average reward scores across all generated programs relative to the baseline. We note that nearly every training run resulted in an increased average reward. However, achieving significant gains in the performance of the top programs (top 50 and top 1) required more careful tuning. Results in terms of average rewards are detailed in Figure 5 in Appendix A.10.

---

Published as a conference paper at COLM 2025
9,6K
J8K
22.4K
9.5K
1ok
22.4K
9.65
18K
22.4K
BIN PACKING
LEAMA FUNSCARCH
5.00
4,67 0.15
1.
4,45 0.14
4.01 0.10
2.15
4.52 0.15
4.00 0..1
5 D.18
LLAMA EIOTIRE
8.96 0.09
8:31 6:3
8
831 8:38
5:99 0.30
838 9.17
4339 6.15
8 6014
PIE FONSEARCH
2.13
3.85 8:13
4-6.15
5.19
BroTors
9312
9 6:0
9:33
0.38 0.37
2,00 0:10
GRANITE FUNSPARCH
9:6 0.00
3.57 0:5
535 0.0
6-05
2.05 0.00
7.86 0.00
5.30 + 0.00
3.05 005-000 0.06
2.57 D/66
GRANTT KOOTIE
(.90 0.10
0:33 6:88
838 0.05
2,93 8.04
9.75 0.08
2.66 1 9.07
300 6.18
2:89 0.07
2 EUB
TRAVELING
FLE PUNSEARCH
2,600 22 0.033
2393 0.205
15555 01423
2.55 2. 0,005
2.411 = (.00
2106 3 0.001
1,647 2 0,005
2,04 2 0.006
2,533 2 ELEIN
PLU RYSTEHA
2.509 2 0.933
2.397 0.805
1.551 0.005
2.942 6 8.383
2.953 = 0.002
2.223 0.083
2.837 2 0.007
2.592 2 0.006
2.375 2 EL006
3,468
(3608)
PLAT PACK
TLAMA FUNRRANCH
0.16 0.000
01555
0:001
5-148 01011
0.151 6.005
0.341 01005
13535 1-0.36
3:165
0.15 0.035
0.148 DUEDS
LLAMA EroZuRK
0.150 0.003
0.338
5.805
0:329
9.304
0.322
0.112
B:849
0.002
0.354 0.903
PSE PURSEARCH
111924
5:405
0.125
01413
0.154
0.324 01485
11311 0.005
5.166 0,145
0.142 0.005
0.131 D,010
PLB RYSTEHE
0.150
0.003
8.806
0:115 0.003
0.139
6.316 0.000
0.308 0.882
8:356 2 0.000
0,036
0.603
GRANNE FUNSHAMMC
0.113
8:001
5:311 01I
0.105 6.001
0.305 01001
01301 0.093
5:124 0.001
0.023
0.218 ILEMT
GRANTE AYCIUEE
0.003
0.800
0:105 0.003
0.183 8.383
8.301
0.099 0.891
8.320
0.116 0.000
0.313 0.001
Table 1: Results for Bin Packing (Top), Traveling Salesman Problem (Middle), and Flatpack (Botfom). We report mean optimality gaps of top 50 programs and standard error across 10 seeds on validation,
and test sets at three different sampling budgets (9.6k, 16k and 22.4k sampled programs, corresponding to the x-axis in Figure 2). Across different models, tasks, and sampling budgets, EvoTune consistently outperforms FunSearch. The best performance is highlighted in blue
calidation-peturbben
In many mathematical problems, the challenge lies in finding optimal solutions within o
a specific search space, regardless of their generalization beyond it. For instance, many problems require identifying high-quality solutions within particular dimensions, where cross-dimensional generalization is not the primary concern (Grochow, 2019; MacWilliams & Sloane, 1977). The observed improvement in search performance on the validation set using EvoTune is thus a promising indicator of its potential to address such challenging mathematical problems.
To further assess the robustness and generalization of the generated programs, we evaluate their performance on the validation -perturre and test sets. For these evaluations, we
BeeTuse
Graste- FuBarch
EwTTure
Fudaadi
Ewiuur
Liuee Fašod
00.33
10.34
2.55
-00
2.00
-55
00.0
5020
2000C
9200
10000
3000
10020
Narther of Sampled Pragram
Number of Sampled Progren
Number of Sompludl Praggat
4000
5000
Noobbr tfthogn Soutss
1500
5000
5000
1000
2000
4000
4000
0
3500
Number of Sumpled Program
Number of Sampled Program
Number of Sampial Prugmas
(a) Flatpack
(b) Bin packing
(c) Traveling salesman problem
Figure 2: Top-50 rewards and the number of unique scores. The reward score of the best 50 generated programs (Top) and the number of programs with unique scores across different models Bottom for (a) flatpack, (b) bin packing, and (c) traveling salesman problem. The shaded areas denote the standard error computed over 10 seeds. Across all models and tasks, EveTune finds higher-scoring best 50 programs. Additionally, it finds a greater number of uniquely scoring solutions.
7

---

Published as a conference paper at COLM 2025
Progna-Smmplnn ing Budget
Prapram-Smmpinng Budle:
Astoge hrrgusyy
100
Evollxe FeaSeand
Bevand of Sap Promnzzz
No Traininngg
10
20
Ferwand KL
Revens KL
4.5
4.0
5.0
5.0
4.0
5.0
5.0
15.0
Avenge Iequnnyy
100
1000
5.5
1000
Number Unique Stree
2.5
3.0
2.5
2.5
3,0
3.5
800
Aucrape Fequaic
500
200
100
200
2000
Optimality Gop
Optinality Gap
Stnppled
(a)
(b)
Figure 3: (a) Evolution of optimality gap distributions. Histograms illustrating the distri- bution of optimality gap scores for programs in the program database at an early checkpoint with limited sampling budget (Left) and at the final checkpoint with full sampling budget (Right). The Top, Middle, and Bottom rows show results for the BP, TSP, and FP tasks, respec- tively. All results are averaged over 10 seeds. Throughout the search process, EvoTune produces higher number of high-quality programs (indicated by lower optimality gap scores) compared to the baseline. (b) Forward KL vs. Reverse KL. Comparison of KL variants based on the reward of the top 50 programs (Top) and the number of unique scores (Bottom). Forward KL yields higher rewards and higher number of unique solutions, which we attribute higher diversity of outputs.
consider all programs in the program database that are generated up to given sampling budget and measure their performance on the corresponding evaluation sets. As shown in Table 1, our method outperforms the baseline both the validation-perturbel and test set across all tasks and models.
Number of unique solutions discovered Figure 2 (Bottom) illustrates the number of unique solutions found by the methods, as measured by the number of unique evaluation scores in the program database. Although achieving a higher count of unique solutions is not not strictly necessary for finding higher scoring programs, it indicates a more comprehensive search uncovering wider range of potential solutions. Across all benchmarks and LLMs, EvoTune consistently discovers a greater number of unique solutions compared to the baseline. For any specific model and benchmark, achieving higher number of unique solutions correlates with achieving higher rewards. Additionally, while tuning the training hyperparameters, tracking the unique solution metric proved effective in signaling when the training began to overfit.
Distribution of scores in program database Figure 3a compares how the distribution of scores within the program database evolves from an early-stage checkpoint to the final one for both methods. Initially, the distributions of the optimality gap scores of both methods are comparable. As the search progresses, EvoTune exhibits a greater increase in the frequency of high-scoring solutions relative to the baseline. While the counts across all optimality gap scores increase more with EvoTune, this increase is especially pronounced in the highest-quality region (i.e., low optimality gap). This improves the chances of finding record-breaking mutations beyond the current frontier, more diverse candidate solutions become available to the model to innovate upon.
We include similar optimality gap distributions for all models and benchmarks in Ap- pendix A. along with a complementary t-SNE analysis of function embeddings (Figure 9a, Figure 9b) that provides structural insight beyond score-based diversity.
Forward vs. reverse KL As discussed in Section 3.2, a key design choice in our RL phase is using the forward KI. variant of DPO rather than the more commonly used reverse KL.
8

---

Published as a conference paper at COLM 2025
(Rafailov et al., 2024). To evaluate the impact of this choice, we conducted an ablation study on the bin packing task using the Llama3.2 1B Instruct model, comparing the performance of forward and reverse KL regularization. As depicted in Figure 3b (Top), both KL variants of our method surpass the FunSearch baseline, but the forward KL. variant discovers the best- perforreno programs. In addition, it generates greater number of unique solutions, as shown in Figure 3b (Bottom), demonstrating its effectiveness in promoting output diversity.
Additionally, we evaluated an alternative RL algorithm: the ReSTEM approach (Singh et al., 2023; Gulcehre et al., 2023). This offline RL method iteratively applies supervised fine-tuning (SFT) on high-scoring outputs. Our experiments indicate that ReSTEM underperforms rela- tive to DPO and is more sensitive to hyperparameters. Detailed results for this investigation are provided in the Appendix A.13.
While we improve the baseline method by adding in-weight learning to the LLM,, we also tried improving in-context learning (Dong et al., 2022) by providing more examples in the prompt, but could not gain considerable improvements.
Results on Hash Code and LLM-SR problems To expand the scope and further test applicability and generality of our method, we benchmark it on two problems from the Hash Code programming competition organized by Google and two problems from the LLM-SR benchmark suite on discovering scientific equations.
The results, shown in Figure 4, are consistent with our previous findings Evo consis- tently outperforms FunSearch in terms of both the reward of the best 50 solutions found and the number of unique solutions discovered during the evolutionary process.
Notably, on the Datacenter Optimization task from Hashcode, EvoTune achieves a score of 418 surpassing the competition's 's top human score of 407. FunSearch also improves over the human baseline, achieving a score of 414, but it does not match Evotune's peak performance. For this task, we set the sampling budget for both methods at 10,000 functions. Across the LLM-SR tasks, EvoTune consistently outperforms the evolutionary search baseline, both throughout the optimization trajectory and on the final in-distribution (ID) and out-of- distribution (OOD) evaluation sets. On the Stress-Strain task, our method, even when using the small Phi-3.5 Mini (3.8B) model, surpasses baselines that rely on larger or proprietary models such as Mixtral 8x7B and GPT-3.5-turbo.
These results demonstrate that our method scales effectively to real-world settings and discovers high-quality solutions for these problems, Full results for these tasks can be found in Appendix A.9
Comparison to non-LLM baselines To contextualize EvoTune's performance, we bench- marked it against specialized non-LLM approaches. Our evaluation shows that this general- purpose method can discover solutions that surpass both task-specific methods and es- tablished human-designed heuristics. Full experimental details are available in Appendix A.12.
5 Related Work
Evolutionary search with LLMs Lehman et al. (2023) introduce ELM for evolving Python programs that configure walking robots, using RL only to condition generation in new domains - not to improve the search itself. In contrast, we integrate RL with evolutionary search to refine the generator policy. Liu et al. (2024) evolve heuristics and their thoughts with an LLM without training. Ye et al. (2024) extend this with self-reflectigg LLM and specialized evolutionary steps. Liu et al. (2023a) evolve optimization algorithms via prompt- based mutation and crossover without reward feedback. Liu et al. (2023b) propose LMEA, which relies on carefully curated prompts and directly evolves solutions in natural language, not algorithms, which does not scale with the size of the problem.
Prompt optimization A closely related line of research explores how to vary and optimize the prompts to better elicit desirable outputs from L.Mss. Yang et al. (2024) leverage the LLM
9

---

Published as a conference paper at COLM 2025
as a prompt optimizer that directly outputs solutions as black-box method without iterating over algorithms and without updating the generator policy. Guo et al. (2023) introduce EvoPrompt, which integrates evolutionary search with LLMs for prompt optimization without a learning component. Similarly, Fernando et al. (2023) developed an evolutionary method that self-referentially evolves and improves the prompts and mutation operators jointly.
Self-improvement and self-training Iterative self- self-improvement training techniques work by training models using their own generated outputs (Zelikman et al., 2022; Gulcehre et al., 2023; Singh et al., 2023; Ishibashi et al., 2024; Pang et al., 2024). Candidate solutions are generated and then filtered based on correctness or alignment with predefined criteria. The selected outputs are used to fine-tune the model, and this cycle repeated, gradually improving its ability to produce desirable solutions. Our method adds to the repertoire of Scchiques--b the evolutionary search capabilities of the model. For more comprehensive discussion of additional related work, including neural combinatorial optimization, we refer the reader to Appendix A.3.
self-improving techniques - by training the LLM on self-discovered solutions, we improve
6 Conclusion
We found that existing evolutionary search approaches can converge to suboptimal solutions soluuttoo with a limited sampling budget. To address this, we introduced EvoTune, a novel approach that integrates evolutionary search with RL fine-tuning to improve LLM-driven algorithm discovery. By iteratively refining the LLM through RL. finetuning, our method outperforms purely search-based baseline challenging combinatorial optimization and symbolic regression tasks Our results establish the viability of integrating RL into evolutionary search such that (i) the training effectively guides the evolutionary search toward superior solutions (measured by the single best or top-k performance) rather than merely increasing the average score of the population and (ii) the diversity of sampled functions is maintained, a critical and non-trivial challenge in self-improvement training, which we achieve through techniques like Forward KL regularization.
Although our results highlight the promise of EvoTune, several questions remain for further investigation. Our experiments were conducted with LLMs ranging from 1B to 3.8B parameters and with a sampling budget of up to 22.4k outputs. Further scaling of both the model size and sampling budget is needed to fully understand the method's potential. Furthermore, while EvoTure une discovers better solutions within a fixed sampling budget, it incurs additional compute costs due to the RL training phase. Investigating the trade-offs between training and inference costs, especially at larger scales, is an important direction for future research.
In a nutshell, EvoTune demonstrates the potential of combining the synergistic strengths of evolutionary search and reinforcement learning, paving the way for future advances in LLM-based algorithm discovery.
Ethics Statement
LLMs are dual-use technologies capable of serving both beneficial and potentially harmful purposes. Enhancing their capabilities, as demonstrated in this work, can advance the discovery of automated algorithms, fostering innovations in various scientific and industrial domains. However, these advancements raise concerns about misuse, such as generating malicious algorithms. It is crucial to implement robust safeguards and ethical guidelines to mitigate these risks, ensuring that the improved capabilities of LLMs are harnessed responsibly and for the greater good of society.
10

---

Published as a conference paper at COLM 2025
Acknowledgements
We are grateful to Bernardino Romera Paredes and Alhussein Fawzi for the insightful discussions that contributed to this work. We also thank the SwissAI Initiative and the SCITAS team at EPFL for providing the computational resources that enabled our research. We extend our appreciation to Karin Getaz for administrative support, and to Skander Moalla and Yugesh Ajit Kothari for their assistance with the technical implementation.
References
Marah Abdin, Jyoti Aneja, Hany Awadalla, Ahmed Awadallah, Ammar Ahmad Awan, Nguyen Bach, Amit Bahree, Arash Bakhtiari, Jianmin Bao, Harkirat Behl, et al. Phi-3 technical report: A highly capable language model locally on your phone. arv preprint arXio:2404.14219, 2024.
Abdullah Alsheddy, Christos Voudouris, Edward PK Tsang, and Ahmad Alhindi. Guided local search., 2018.
Florian Arnold and Kenneth Sörensen. Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research, 105:32-46, 2019.
John E Beasley. Or-library: distributing test problems by electronic mail. Journal of the operational research society, 41(11):1069-1072, 1990.
Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arviv preprint ar Xrx:v11611 111.09994, 2016.
Christopher Berner, Greg Brockman, Brooke Chan, Vicki Cheung, Przemyslaw Debiak, Christy Dennison, David Farhi, Quirin Fischer, Shariq Hashme, Chris Hesse, et al. Dota with large scale deep reinforcement learning. arXiv preprint arXiv:1912.06688, 2019.
Clément Bonnet, Daniel Luo, Donal Byrne, Shikha Surana, Sasha Abramowitz, Paul Duck- worth, Vincent Coyette, Laurence Midgley, Elshadai Tegegn, Tristan Kalloniatis, et al. Jumanji: diverse suite of scalable reinforcement learning environments in jax. arXiv preprint ar Xix::2306. 098844 2023.
Lola Le Breton, Quentin Fournier, Mariam El Mezouar, and Sarath Chandar. Neobert: A next-generation bert. arXiv preprint ar wxXix:2502.115883 2025.
Daniele Calandriello, Daniel Guo, Remi Munos, Mark Rowland, Yunhao Tang, Bernardo Avila Pires, Pierre Harvey Richemond, Charline Le Lan, Michal Valko, Tianqi Liu, al. Human alignment of large language models through online preference optimi- sation. Xrv preprint ar wxix:2243.00555 08635, 2024.
Erick Cantú-Paz et al. A survey of parallel genetic algorithms. Calculateurs paralleles, reseaux el systems repartis, 10(2):141-171, 1998.
Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, et al. Open problems and fundamental limitations of reinforcement learning from human feedback. Xiv preprint ar axXiv:2307.15217, 2023.
Xinyun Chen and Yuandong Tian. Learning to perform local rewriting for combinatorial optimization. Advances in Neural Information Processing Systems, 32, 2019.
Edward G Coffman Jr, Michael R Garey, and David S Johnson. Approximation algorithms for bin-packing- an updated survey. In Algorithm design for computer system design, pp. 49-106. Springer, 1984.
11

---

Published as a conference paper at COLM 2025
DeepSeek-AI, Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Ruoyu Zhang, Runxin Xu, Qihao Zhu, Shirong Ma, Peiyi Wang, Xiao Bi, Xiaokang Zhang, Xingkai Yu, Yu Wu, Z. F. Wu, Zhibin Gou, Zhihong Shao, Zhuoshu Li, Ziyi Gao, Aixin Liu, Bing Xue, Bingxuan Wang. Bochao Wu, Bei Feng, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, Damai Dai, Deli Chen, Dongjie Ji, Erhang Li, Fangyun Lin, Fucong Dai, Fuli Luo, Guangbo Hao, Guanting Chen, Guowei Li, H. Zhang, Han Bao, Hanwei Xu, Haocheng Wang, Honghui Ding, Huajian Xin, Huazuo Gao, Hui Qu, Hui Li, Jianzhong Guo, Jiashi Li, Jiawei Wang, Jingchang Chen, Jingyang Yuan, Junjie Qiu, Junlong Li, J. L. Cai, Jiaqi Ni, Jian Liang, Jin Chen, Kai Dong, Kai Hu, Kaige Gao, Kang Guan, Kexin Huang, Kuai Yu, Lean Wang. Lecong Zhang, Liang Zhao, Litong Wang, Liyue Zhang, Lei Xu, Leyi Xia, Mingchuan Zhang, Minghua Zhang, Minghui Tang, Meng Li, Miaojun Wang, Mingming Li, Ning Tian, Panpan Huang, Peng Zhang, Qiancheng Wang. Qinyu Chen, Qiushi Du, Ruiqi Ge, Ruisong Zhang, Ruizhe Pan, Runji Wang, R. J. Chen, R. L. Jin, Ruyi Chen, Shanghao Lu, Shangyan Zhou, Shanhuang Chen, Shengfeng Ye, Shiyu Wang, Shuiping Yu, Shunfeng Zhou, Shuting Pan, S. S. Li, Shuang Zhou, Shaoqing Wu, Shengfeng Ye, Tao Yun, Tian Pei, Tianyu Sun, T. Wang, Wangding Zeng, Wanjia Zhao, Wen Liu, Wenfeng Liang, Wenjun Gao, Wenqin Yu, Wentao Zhang, W. L. Xiao, Wei An, Xiaodong Liu, Xiaohan Wang, Xiaokang Chen, Xiaotao Nie, Xin Cheng, Xin Liu, Xin Xie, Xingchao Liu, Xinyu Yang, Xinyuan Li, Xuecheng Su, Xuheng Lin, X. Q Li, Xiangyue Jin, Xiaojin Shen, Xiaosha Chen, Xiaowen Sun, Xiaoxiang Wang, Xinnan Song, Xinyi Zhou, Xianzu Wang, Xinxia Shan, Y. K. Li, Y. Q. Wang, Y. Wei, Yang Zhang, Yanhong Xu, Yao Li, Yao Zhao, Yaofeng Sun, Yaohui Wang, Yi Yu, Yichao Zhang, Yifan Shi, Yiliang Xiong, Ying He, Yishi Piao, Yisong Wang. Yixuan Tan, Yiyang Ma, Yiyuan Liu, Yongqiang Guo, Yuan Ou, Yuduan Wang, Yue Gong, Yuheng Zou, Yujia He, Yunfan Xiong, Yuxiang Luo, Yuxiang You, Yuxuan Liu, Yuyang Zhou, Y. X. Zhu, Yanhong Xu, Yanping Huang, Yaohui Li, Yi Zheng, Yuchen Zhu, Yunxian Ma, Ying Tang, Yukun Zha, Yuting Yan, Z. Z. Ren, Zehui Ren, Zhangli Sha, Zhe Fu, Zhean Xu, Zhenda Xie, Zhengyan Zhang, Zhewen Hao, Zhicheng Ma, Zhigang Yan, Zhiyu Wu, Zihui Gu, Zijia Zhu, Zijun Liu, Zilin Li, Ziwei Xie, Ziyang Song, Zizheng Pan, Zhen Huang, Zhipeng Xu, Zhongyu Zhang, and Zhen Zhang. Deepseek-ri: Incentivizing reasoning capability in llms via reinforcement learning, 2025.
F. Dimitrovski. elkai: A python library for solving travelling salesman problems, 2019. Based on LKH algorithm by Keld
URL https: //githubg com/ Helsgaun.
Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Jingyuan Ma, Rui Li, Heming Xia, Jingjing Xu, Zhiyong Wu, Tianyu Liu, et al. A survey on in-context learning. arXiv preprint Stit:22301.022:44 2022.
Abhimanyu Dubey, Abhinav Jauhri, Abhinay Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama herd of models. Xrv preprint ar Xrv::22407. 217783 2024.
Alhussein Fawzi, Matej Balog, Aja Huang, Thomas Hubert, Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Francisco J R Ruiz, Julian Schrittwieser, Grzegorz Swirszez, et al. Discovering faster matrix multiplication algorithms with rein- forcement learning. Nature, 610(7930) 2022.
Chrisantha Fernando, Dylan Banarse, H. Michalewski, Simon Osindero, and Tim Rock- täschel. Promptbreeder: Self-referential self-imprrvemment via prompt evolution. Interna- fional Conference on Machine Learning, 2023. doi: 10.48550 htt0//a2xx.....167000
Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre-trained model to arbitrarily large tsp instances. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 7474-7482, 2021.
David E. Goldberg and John H. Holland. Genetic algorithms and machine learning. Machine Learning, 3(2):95-99 1988. doi: 10.1023 A.000///...222019113...
IBM Granite Team. Granite 3.0 language models, October 2024. URL https: / gitthb.. com/ htmm://mmgraantt/rrrnieeeee 3. 0- anguage-modells
12

---

Published as a conference paper at COLM 2025
Joshua Grochow. New applications of the polynomial method: the cap set conjecture and beyond. Bulletin of the American Mathematical Society, 56(1):29-66 24,29944,60 2019.
Sylvain Gugger, Lysandre Debut, Thomas Wolf, Philiip Schmid, Zachary Mueller, Sourab Mangrulkar, Mare Sun, and Benjamin Bossan. Accelerate: Training and inference at scale made simple, efficient and adaptable. https://githi: com/ wwt.ccco//hhhh.ee httph/uggggggc/////o//c/o accel erate, 2022.
Çaglar Gülçehre, Ziyu Wang, Alexander Novikov, Thomas Paine, Sergio Gómez Col- menarejo, Konrad Zolna, Rishabh Agarwal, Josh Merel, Daniel J Mankowitz, Cosmin Paduraru, et al. RI unplugged: A collection of benchmarks for offline reinforcement learning. In NeurIPS, 2020.
Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang, Chenjje Gu, et al. Reinforced self-training (rest) for language modeling. arXiv preprint ar ftf::2308.089998, 2023.
Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, Yujiu Yang, Tsinghua University, and Microsoft Research. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. International Conference on Learning Representations, 2023. doi: 10.48550 10.48550/arxiv233000 arlvvvi33222000532222
Gregory Gutin and Abraham P Punnen. The traveling salesman problem and its variations, volume 12. Springer Science & Business Media, 2006.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. The curious case of neural text degeneration. arXiv preprint ar 1rXto:1904.09751,2000 2019.
André Hottung and Kevin Tierney. Neural large neighborhood search for the capacitated vehicle routing problem. In 24th European Conference on Artificial Intelligence (ECAI 2020), 2020.
André Hottung, Bhanu Bhandari, and Kevin Tierney. Learning latent search space for routing problems using variational autoencoders. In Infernational Conference on Learning Representations, 2021a.
20211.
André Hottung, Yeong- Dae Kwon, and Kevin Tierney. Efficient active search for combinato- rial optimization problems. arXiv preprint arXiv:2106.05126, 2021b.
Doong-Dae
Edward Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arviv preprint ar XrXi:2206609685, 2021.
Hugging Face. Text generation inference, 2025. URL https: /ttpps://ithhbb.com Version 3.0.1.
Yoichi Ishibashi, Taro Yano, and Masafumi Oyamada. Can large language models invent algorithms to improve themselves? arXiv e-prints, pp. arXiv-2410 2024.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint ar Xii::9066012277 2019.
Chaitanya K Joshi, Quentin Cappart, Louis-Martin Rousseau, and Thomas Laurent. Learning the travelling salesperson problem requires rethinking generalization. Constraints, 27(1-2): 70-98, 2022.
Michael Jünger, Gerhard Reinelt, and Giovanni Rinaldi. The traveling salesman problem. Handbooks in operations research and management science, 7:225-330, 330, 1995.
Henry J Kelley. Gradient theory of optimal flight paths. Ars Journal, 30(10):947-954, 19600.
13

---

Published as a conference paper at COLM 2025
Robert Kirk, Ishita Mediratta, Christoforos Nalmpantis, Jelena Luketina, Eric Hambro, Edward Grefenstette, and Roberta Raileanu. Understanding the effects of rlhf on Ilm generalisation and diversity. arv preprint ar arXi::2310.06452, 2023.
S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi. Optimization by simulated annealing. Science, 220(4598))6716660) 1983, doi: 10.1126/ 10.1126/science.222 scceence220.4498..677
Wouter Kool, Herke Van Hoof, and Max Welling. Attention, learn to solve routing problems! arviv preprint ar arXiv:1803.08475. 2018.
Wouter Kool, Herke van Hoof, Joaquim Gromicho, and Max Welling. Deep policy dynamic programming for vehicle routing problems. In Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 19th International Conference, CPAIOR 2022, Los Angeles, CA, USA, June 20-23, 2022, Proceedings, Pp. 190-213. Springer, 2022.
Yeong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iijoo Yoon, Youngjune Gwon, and Seung- jai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems, 33:21188 118-1189,,,,,, 2020.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Joel Lehman, Jonathan Gordon, Shawn Jain, Kamal Ndousse, Cathy Yeh, and Kenneth O Stanley. Evolution through large models. In Handbook of Evolutionary Machine Learning, pp. 331-366. Springer, 2023.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arviv preprint ar Xiv:22005 1000000.0666 01643, 2020.
Fei Liu, Xialiang Tong, Mingxuan Yuan, and Qingfu Zhang. Algorithm evolution using large language model. arXiv preprint ar arXi::2311.1524: 2023a.
Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. ar Xiv preprint ar Aivi:2240 Kio:2400.02051, 2024.
Shengcai Liu, Caishun Chen, Xinghua Qu, Ke Tang, and Yew-Soon Ong. Large language models evolutionary optimizers. ar preprint Xiv: 2310.19046, 2023b.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arviv preprint arXiv:1711.05101, 2017.
Chris Lu, Samuel Holt, Claudio Fanconi, Alex Jakob Foerster, Mihaela van der Schaar, and Robert Lange. Discovering preference optimization algorithms with and for large language models. Advances in Neural Information Processing Systems, 37:86528-86573 2024.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial opti- mization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems, 36:8845-8846 2023.
Yecheng Jason Ma, William Liang, Guanzhi Wang, De-An Huang, Osbert Bastani, Dinesh Jayaraman, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Eureka: Human-level reward design via coding large language models. Xiv preprint arXio:2310.12931, 2023.
FJ. MacWilliams and N.J.A. Sloane. The Theory of Error-correcting Codes. Mathematical Library. North-Holland Publishing Company, 1977. ISBN 9780444850102. URL https: //books. google. ch/books did=nv66CJge.eee.
Silvano Martello and Paolo Toth. Lower bounds and reduction procedures for the bin packing problem. Discrete Applied Mathematics, 28(1):59-70, 1990. ISSN 0166-218X. doi:
14

---

Published as a conference paper at COLM 2025
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(73400:529-533, 2015.
OpenAl. ol.
www.clocoooooooooo 2024. Large language model.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-27744, 2022.
Richard Yuanzhe Pang, Weizhe Yuan, He He, Kyunghyun Cho, Sainbayar Sukhbaatar, and Jason Weston. Iterative reasoning preference optimization. Advances in Neural Information Processing Systems, 37:116617-116677 2024.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Advances in Neural Information Processing Systems, 36, 2024.
B. Romera- Nomera-Paredes, M. Barekatain, A. Novikov, et al. Mathematical discoveries from program search with large language models. Nature, 625:468-475, 2024.
Sebastian Ruder. An overview of gradient descent optimization algorithms. Vestnik komp iuternykh informalsionnykh tekhnologii, 2016. doi: 1011488//vit.2001.11pp..000...00
David E. Rumelhart, Geoffrey E. Hinton, and Ronald J. Williams. Learning representations by back-propagating errors. Nature, 323:533-536, 1986. doi: 10.1038/323533a0.
Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver. Prioritized experience
replay. arXiv preprint ar Xrir:1511.05952, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arviv preprint vxXio:1707.063// 2017.
Parshin Shojaee, Kazem Meidani, Shashank Gupta, Amir Barati Farimani, and Chandan Reddy. Llm-sr: Scientific equation discovery via programming with large language models. Xiv preprint ar arXiv:2404.18400, 2024.
Shumailov, Z. Shumaylov, Y. Zhao, et al. Ai models collapse when trained on recursively generated data. Nature, 631:755-759, 2024. doi: 10.1038/ //////560024-07566666
David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Tlya Sutskever, Timothy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hassabis. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587): 484-489, Jan 2016. ISSN 1476-4687.
Avi Singh, John D Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil, Peter Liu, James Harrison, Jaehoon Lee, Kelvin Xu, Aaron Parisi, al. Beyond human data: Scaling self-training for problem-solving with language models. arXio preprint ar arXio:2312.06555, 2023.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021, 2020.
Jingyan Sui, Shizhe Ding, Boyang Xia, Ruizhi Liu, and Dongbo Bu. Neuralgls: learning to guide local search with graph convolutional network for the traveling salesman problem. Neural Comput. Appl., 36(17))9687-776 2024.
Rich Sutton. The bitter lesson, March 2019. URL http://ww..iccmmpleeeee..e. mecdeess/Bitter..eee html.
15

---

Published as a conference paper at COLM 2025
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Reiko Tanese. Distributed genetic algorithms for function optimization. University of Michigan, 1989.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11), 2008.
Petar Veličković, Alex Vitvitskyi, Larisa Markeeva, Borja Ibarz, Lars Buesing, Matej Balog, and Alexander Novikov. Amplifying human performance in combinatorial competitive programming. ar Xiv preprint ar Xit:2411.19744, 2024.
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly. Pointer networks. Advances in neural information processing systems, 28, 2015.
Oriol Vinyals, Igor Babuschkin, Wojciech M Czarnecki, Michaël Mathieu, Andrew Dudzik, Junyoung Chung, David H Choi, Richard Powell, Timo Ewalds, Petko Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. nature, 575
(7782):350-354, 2019.
Leandro von Werra, Younes Belkada, Lewis Tunstall, Edward Beeching, Tristan Thrush, Nathan Lambert, Shengyi Huang, Kashif Rasul, and Quentin Gallouédec. Trl: Transformer reinforcement learning, https: /gii/tttttt github...... com/ bugginggaaeeee 1t, 2020.
Christos Voudouris and Edward Tsang. Guided local search and its application to the traveling salesman problem. European journal of operational research, 113(2):469-99,, 1999.
Chaoqi Wang, Yibo Jiang, Chenghao Yang, Han Liu, and Yuxin Chen. Beyond reverse kl: Generalizing direct preference optimization with diverse divergence constraints. arviv preprint Xiv::2009.166 16240, 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. of-tigh prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-24837, 2022.
Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoe V Le, Denny Zhou, and Xinyun Chen. Large language models optimizers. In The Twelfth International Conference on Learning Representations, 2024.
Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. Reevo: Large language models hyper-heuristics with reflective evolution. In Advances Neural Information Processing Systems, 2024.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15476-15488, 2022.
A Appendix
A.1 Evaluation tasks
Bin packing problem BP validation set consists of 20 packing instances, each containing 500 items sampled according to the OR-Library (Beasley, 1990). Perforraanc is measured as the fraction of excess bins used in the lower bound (Martello & Toth, 1990). To generate the validation perttudd dataset, we randomly perturb the order items the validation dataset to measure the robustness of programs when presented with perturbed but familiar inputs. To generate the test set, we sample new problem instances from the same distribution as the OR dataset (Romera-Paree Paredes et al., 2024).
16

---

Published as a conference paper at COLM 2025
Traveling salesman problem For TSP instance of size c, we sample c pairs of (x, city coordinates uniformly from [0, 1]2 and use the distance matrix as input to the GLS procedure (see Appendix A.2 for more details on GLS). Performance is measured as the fraction of excess cost incurred by the calculated route over the optimal route given by the Elkai solver (Dimitrovski, 2019). The validation set consists of 100 problem instances of size set, we
100 and 100 instances of size = 200. To generate the validation-perture alter the adjacency matrix such that the cost of each edge is replaced by a high value with probability p 0.2. This allows us to evaluate the robustness of the generated programs in proposing heuristics that work well when the input is slightly changed. It resembles real-world situation where the connection between two cities is suddenly cut off or travel is slow. To generate the test set, we sample new batch of TSP instances using the same procedure as for the validation set.
Flatpack problem The validation set consists of 45 problem instances, with 15 instances
using a 9 x 9 grid, 20 instances using an 11 x 11 grid, and 10 instances using 15 x 15 grid. The dalidatiio-perturrben
set is constructed by modifying each instance in the training set: rectangle of size LVF + 0.5] x L 0.5] is placed in the center of the grid, where and c denote the number of rows and columns of the grid, respectively. This obstacle prevents block placements in the center region and allows us to evaluate the robustness of generated heuristics when confronted with partially obstructed configurations, The test set follows the same grid size distribution as the training set.
Hash Code datacenter optimization: This problem, taken from the 2015 Google Hash Code qualification round, involves optimally placing servers of varying sizes and capacities into a grid-like data center while assigning them to logical pools to maximize fault tolerance. The data center consists of rows and slots, some of which may be unavailable, and each server must be placed in a contiguous sequence of unblocked slots and assigned to a pool. The goal is to maximize the guaranteed capacity, defined as the minimum remaining capacity in any pool if single row fails. Formally, this is a min-max optimization problem: for each pool, the guaranteed capacity equals the total capacity of its servers minus the maximum capacity loss from a single row failure, and the overall objective is to maximize the minimum such value across all pools. Analogous to Veličković et al. (2024), we evolve a heuristic function score_greede two distinct phases. This function takes as input a server, a candidate row, an optional pool, and the current distribution of capacities, and outputs score reflecting the desirability of the configuration. The initial heuristic function prioritizes servers with high capacity-to -tizie ratios for placement, while discouraging assignments that disproportionately concentrate capacity within a single row of a given pool. All functions are evaluated on a fixed instance from the original competition benchmark.
(), which evaluates server placements and pool assignments in
Hash Code self-driving rides This problem, taken from the 2018 Google Hash Code qualification round, involves assigning a fleet of self-driving cars to a set of ride requests on grid. Each ride order is constrained by a start and end location point, earliest start time, and a latest finish time. Following the setup from Veličković et al. (2024), our approach evolves a function, pick rides (), which takes as input a car's current location and time, along with a tuple of candidate rides, and returns the index of the selected ride. The greedy initial policy simply selects the first feasible ride, if it exists. Performance is evaluated on holdout datasets from the competition, with scores based on the total distance covered and bonuses for early starts.
LLM-SR material stress behavior This task models the mechanical behavior of Alu- minium 6061-T651 under tension across six temperature settings (20ºC to 3009C), based on real experimental data. The goal is to predict stress as a function of strain and temperature. Unlike classical physics problems with known governing equations, this setting lacks standard closed-form solution due to complex, nonlinear, and piecewise behavior in the ma- terial's 's response across different conditions. These characteristics make the task particularly challenging for symbolic regression, as it requires uncovering empirical patterns without relying on established physical laws. The regression search begins from simple linear
17

---

Published as a conference paper at COLM 2025
model, with parameters optimized via gradient descent. To assess generalization, data at 200%C is held out as an out-of-domain (OOD) validation set.
LLM-SR bacterial growth modeling This task involves modeling the growth rate dynam- ics of Escherichia coli (E. coli) bacteria using a differential equation that accounts for key environmental and biological factors such as population density, substrate concentration, temperature, and pH level. The benchmark reflects the prior biological knowledge; however, to reduce the possibility of models solving the task through memorization, the task uses synthetic data generated from custom formulations, rather than standard textbook equa- tions. This encourages reasoning and exploration over mere recall. Out-of-domain (OOD) set includes parameters outside the ranges seen during the equation evolution, thereby testing generalization to unfamiliar conditions. The search is initialized from simple multiplicative initial equation the evaluation score is mean squared error (MSE).
A.2 Guided local search
Guided Local Search (GLS) (Voudouris & Tsang, 1999; Alsheddy et al., 2018) is an opti- mization technique designed to improve the performance of local search algorithms by helping them escape local optima. This is achieved by penalizing certain feature sets of solutions that contribute to suboptimal solutions, thereby guiding the search process to more promising areas of the solution space. GLS works by iteratively adjusting the objective function with a penalty term, discouraging the search from revisiting or remaining in areas of the search space that contain undesirable features.
When applied to the Traveling Salesman Problem (TSP), GLS can improve the efficiency of local search methods. In the context of TSP, GLS penalizes edges (or tours) that frequently appear in suboptimal solutions, thus encouraging the search to explore alternative routes. By systematically guiding the local search away from suboptimal solutions, GLS helps in finding shorter and more optimal tours. Similar to Ye et al. (2024), we use a variation of GLS that interleaves local search with perturbations (Arnold & Sörensen, 2019). More specifically, at the beginning of the GLS procedure, an initial tour is obtained using the nearest neighbor heuristic, then for i rounds, we alternate between local search and perturbation, updating the best tour (i 16, 8 for c 100, 200, respectively).
Local search consists of two operations: a) Relocate-Once, b) Two-Opt. The Relocate-Once operation involves removing a single city from its current position in the tour and inserting it into different position. This move aims to explore the impact of shifting from one city to another location in the tour, potentially leading to a shorter overall path. The Two-Opt operation is well-known heuristic that involves selecting two edges in the tour, removing them, and reconnecting the segments in a different way that still results in a valid tour. This operation can effectively eliminate crossings in the tour, which are often associated with suboptimal solutions, leading to a shorter and more efficient route.
The perturbation operation in the GLS uses controlled disruptions to the current solution to escape local optima, leveraging a guide computed using programs generated by the LLM that take the distance matrix as input. The perturbation operation iteratively penalizes certain edges in the current tour, encouraging the search to explore alternative routes. The goal is modify the solution such that it escapes local optima and continues searching for global optimum. For each edge in the current tour, a utility value is computed using the guide provided by the LLM. The edge with the highest utility value identified as the most promising candidate for perturbation and the penalty associated with the selected edge is incremented, discouraging the local search from selecting this edge in subsequent iterations. This helps diversify the search space by effectively increasing the cost of returning to previously explored (and penalized) solutions. This is followed by the distance matrix being adjusted by the weighted penalties, resulting in new guided edge weight matrix which directs the subsequent local search by reflecting both the original distances and the imposed penalties.
18

---

Published as a conference paper at COLM 2025
A.3 Extended related work
Neural combinatorial optimization (NCO) NCO is an important orthogonal class of methods that learn to construct solutions for combinatorial optimization problems using embeddings of problem instances as input. Such models can be trained with supervised learning (Vinyals et al., 2015; Joshi et al., 2019; Fu et al., 2021; Joshi et al., 2022; Kool et al., 2022; Hottung et al., 2021a) or RL (Bello et al., 2016; Kool et al., 2018; Hottung & Tierney, 2020; Hottung et al., 2021b; Chen & Tian, 2019) (See Luo et al. (2023) for more references). Our work the other hand does not deal with problem instances directly; rather, it searches for an algorithm or heuristic that can later be utilized with problems of any size.
A.4 Program database
Inspired by Romera-Paredest et (2024), we organize our program database into islands and clusters (Tanese, 1989; Cantú-Paz et al., 1998). Each island represents that evolve independently. Within an island, programs are further grouped into clusters based on their scores.
of programs
We use the following procedure to form the prompt x', which consists of in programs sampled from the program database. First, we select an island uniformly at random. Next, we sample m clusters from the chosen island i. This ensures that the selected programs, which will be used to construct the prompt, have different scores, making it possible for the LLM to identify "the direction" of improvement. Additionally, we observed that programs within the same cluster often differ only superficially (e.g., minor variations in subroutines or variable names while performing the same computation). Hence, to avoid constructing prompts with overly similar programs, we sample different clusters. To sample m clusters, we draw from softmax distribution over cluster scores, using a temperature parameter. We also incorporate an annealing strategy (Kirkpatrick et al., 1983) to adjust sampling over time such that toward the later stages, the clusters will be sampled from the top pt > P1-1 percentile of the database to balance exploration-exploitatiin sample one program from each cluster, prioritizing shorter programs et al., 2024). Unlike Romera-Pareder et al. (2024), we do not reset the islands that contain low-scoring programs.
After choosing m clusters,
A Aterr sampling programs from an island we construct the prompt xt as detailed in Appendix A.7. All newly generated outputs from this prompt are placed back in the same island This approach helps prevent excessive similarity between programs in the database and encourages the exploration of wider set of ideas.
A.5 RL formulation of EvoTune
In this section, we detail the reinforcement learning framework underlying EvoTune and explain why we classify it as reinforcement learning approach, although its optimization is performed using DPO.
We define an MDP M (S,ARR,T) as follows:
States (S): Partial sequences (x, y1s)) consisting of prompt and partially gener- ated output of length k. Note that the prompts x are not fixed, unlike the formulation in the DPO paper.
Actions (A):
Sampling the next token yx+1 E V from the vocabulary V.
Rewards (R): Rewards assigned by the Bradley-Terry reward model in terminal state (end of sequence token or full context). The reward reflects the performance on the task-specific evaluation set over the generated program extracted from the output yı.x. The reward reflects the quality of the generated program and is undiscounted, meaning the discount factor is set to 1.
Transitions (T): Deterministic transitions from (x, v1*) to (x, 11kk 1) as new tokens are appended to the sequence.
19

---

Published as a conference paper at COLM 2025
The RL problem in the context of preference learning could be formulated as:
arg max
E X-
ply+ > y-lx) - (Tn
(4)
e
(y mm1
Off-policy DPO training DPO was proposed as an RL-free method, as the reward model it optimizes is implicit, and training can be conducted entirely offline. However, it still performs constrained reward maximization but by adopting the Bradley-Terry reward model p(v+ > y-lx), it diverges from the classical RLHF training setting. While standard DPO operates on fixed offline samples, EveTune functions in an off-policy setting, as the updated model is iteratively used to generate new outputs enabling further performance improvements. In this sense, our method is similar to iterative DPO (Pang et al., 2024; Ishibashi et al., 2024). Furthermore, the samples in the program database are dynamically generated and not fixed. We believe that this makes the DPO approach in EvoTune closer to a more traditional RL algorithm.
Alternative RL formulation The RL problem that DPO optimizes can also be seen as one-step offline RL problem (Gülçehre et al., 2020; Levine et al., 2020) or an offline bandit (Lattimore & Szepesvári, 2020). Since rewards are only provided at terminal states and transitions are fully deterministic, the problem reduces to bandit formulation, where an action corresponds to sampling the entire output y1:k-
A.6 DPO dataset filtering
To reduce training time and computational cost, we apply filtering procedure reduce the size of the DPO dataset DI pref- This ensures that the training focuses on high-quality data points while maintaining diversity. We filter out any datapoints yf"",, "24""," y²") where the reward of the higher scoring output yf"" falls under a predefined threshold z². The threshold r is calculated based on the distribution of rewards from the outputs generated since the last RL Iraining phase. More specifically, it is set as the 30th percentile of rewards from newly generated outputs. As the average reward improves over time, this threshold also naturally improves, ensuring that only progressively better outputs are retained.
A.7 LLM prompts
We present here the system prompts as well as the task descriptions for BP, TSP, and FP in Prompt 2, 3, and 4. A complete query to the LLM consists of concatenating the system prompt, two sampled programs accompanied by their score, and the task description.
You are a helpful, excellent, and innovative problem-saee solver specializing in mathematical optimization and algorithm design. You expert writing Python functions.
Prompt System prompt for the LLM.
You are tasked with creating a new function, pricrity(), that outperforms the other two presented funetions,
To schieve this, follow there guidelines:
think Outside the sex: Aveid simply resriting or rephrasing existing approaches. Prioritize ze crearing navel sonutions rather than making asperficta) tweaks.
Analyze the Score Drivers: Analyze the characteristics of the higher-scoring function. Identify what Jetermine which specific changes or techniques lead to better performance. Experiment with Variations: successful ideas but introdices innovative variations. Consider entirely new strategies or opiimazations that were not present the previous attempte. To sumearize, your task is to write new function named prfority() that will perform bettez than both funotions above and achieve a highez scoze.
deing differently er
effectively than the lower-scering function.
the insights create
function that builds upon
Leet us note that that the program database is similar to replay buffer in off-policy RL (Mnih et al., 2015; Schaul et al., 2015)
20

---

Published as a conference paper at COLM 2025
Prompt 2: Description of the bin packing problem.
You are tasked with creating a new function, heuristics (), that outperforms the other two presented functiona.
The heuristics() () function takes as Input a distance matrix, and returna prior indicatora
how undesirable
include each edge in solution. The returned matrix should of the same shape as the input.
When sriting the new Lunction, follow these quidelines:
Think Outside the Box: Avoid simely zewriting rephrasing existing approaches. Prioritize creating navel solutions rather than making superficial twoaks.
Analyza the Score frivers: Analyze the characterísties of the higher-scoring function.
Identify what it is doing di differently or more effectively than the lowez scozing fusction.
Determine which specific changes or techniques lead to better pezformance.
function named heuristics () that will perform better than both functions above and achieve a highez score.
To summarize, your taak is to write
Prompt 3: Description of the traveling salesman problem.
You are Lasked with creating new function, priority,, that outpertorms the other two presented functions.
The priority() function takes three inputs:
i. curreat_grid: aumpy arrey (flost32) of shape (aum_ rows, com_cols) with values in the zange 10, blncklecks) (corresponding
number each block). . this grid will have zeros where nо blocks have been placeo and nimbers corraspending to each black where that particular block has been placed.
2. biecks: numpy array (fioat32) of shape (nam_blocks,
of all possible blocks in that can fit in the current grid, These blocks will always have shape (3, 3).
3. action_mast mack: nampy array (bool) of shope mnun_bleos,, 4, num roms2o num_cols-21, representing which actions are possible given the current state of the grid. the first index indicates the block index, the second index indicates the rotation index, third and fourth indices indicate the row and colume coordinate of where blocks top left most cozner may be placed respectively. num_cols-2 respectively to make it impossible to place block outside the cusrent grid. it returns a numpy array of size inun_blocks, 4, num_rows-2, num_cols-2) representing how the row, 6cl
the
These values will always be nonL_ 2 and
sulubble it ia to place block with rotation with ita top-left position in the grid.
When writing the new function, fol these guidel Think Octaide the Box: Avold zephrasing existing approaches. Prioritize creating novel solutions
simply rewrlting zether than making superficiel tweaks. Anelyze the Score Drivers: Analyze the characteristics of the higher-scoring function. identify what is doing difforently or more offectivgly than the lower-scoring function. betermine which apecific changes or techniques lead to better performance.
To summarize, your task is to write new function named priority that will perform better than both funct tons above and achieve a higher score.
Prompt 4: Description of the flatpack problem.
A.8 Experimental details
In our experimental setup, we maintain database of programs consisting of six islands. For prompt construction, we use m = 2 programs, and we generate K = 8 outputs for every prompt. We set the reinforcement learning frequency parameter to fRI. 400, which results in alternating between the two phases after generating 3,200 outputs. We run our experiments up the timestep 2800, which corresponds total of approximately 22,400 output samples from the LLM.
Sampling parameters For each query to the LLM, we generate K = 8 outputs using temperature of 0.9, top-k sampling with k 100, and nucleus sampling with p p= 0.95 (Holtzman et al., 2019). The generated outputs are constrained to maximum length of 2048 tokens. For inference, we utilize the Text Generation Inference (TGI) implementation (Hugging Face, 2025).
Training Parameters For DPO training, we apply a regularization strength of β 0.4. Each training phase consists of 2 epochs and the AdamW (Loshchilov & Hutter, 2017) optimizer. In addition to the learning rate schedule across timesteps t, use cosine learning rate schedule inside each training phase, where the learning rate obtained by the timestep schedule is used as the starting learning rate. The learning rate is optimized for
21

---

Published as a conference paper at COLM 2025
every model on the validation set via grid search sweep the range [3 10 3,5 10 10- Once we found good training hyperparams for the bin packing problem, we used the same ones to perform experiments memory-efficiens fine-tuning of the model, we utilized LoRA adapters (Hu et al., 2021), configuring the rank to 64 and setting a to 32. Our implementation leverages the TRL. library (von Werra et al., 2020) in combination with Accelerate (Gugger et al., 2022).
the other two benchmarks, without further tuning. For
As there are fewer data points to train in the early training phases and more data points in the late phases, it is crucial to balance training sufficiently in the initial stages while not overfitting in the final stages. To achieve this balance, we implement learning rate schedule that decays the learning rate over time based on the timestep t: a, = Ainit * /1000/t.
Constraints programs To prevent scenarios where the LLM might produce non- terminating or excessively time-consuming programs, we establish maximum execution times of 60 seconds for bin packing and flatpack tasks, and 90 seconds for the traveling packing salesman problem. Additionally, to avoid excessive memory consumption, we limit the memory usage to 5 GB.
A.9 Results on Hashcode competition problems and LLM-SR benchmarks
Pli BndTaae
Ilu PadBarch
Revatt of 90
0,000
oo Preperme Bevand of top Peogaaa
of Unique Same
1300
300
a 454
Datacmner Optmitation
(P)
0,300
Number of Linque
Haokoode Self Drivarz
-030
0.390
100
688
4000
-0.000
Number of Unique Some
3000
To S0
0.005
0.03
Namter Uniqqu
2000
1500
LLMSR
1. L.LM-R J: Coll Growdh
Strees
0.007
4000
Samin
0.602
4003
4000
800
Namber
Mumber
Number of sanaaalllllpannnn progamm
Number of camplel progrmm
Figure Results on two Hashcode problems, and two problems from LLM-SR. EvoTune consistently outperforms FunSearch across all problems in terms of discovering higher scor- ing best 50 solutions and higher diversity as measured by number of discovered solutions with unique scores. Shaded regions show standard deviation across 4 seeds.
Hashcode results In Figure 4, we show the performance our method against FunSearch two complex real-world problems from the Google HashCode competition. These tasks offer a testbed to evaluate whether our evolved heuristics can match, or even surpass, the performance of solutions developed by top human teams in competitive programming.
We compare Evotune to a standard Funsearch-style setup using the same model (Phi- 3.5 Instruct). As mentioned in the main text, the Datacenter Optimization task, both methods are able to outperform the best solutions found by human teams in the competition. However, on Self-Driving task, neither TvoT FunSearch do not outperform the best solution found by human teams within the sampling budget of 20,000 functions. However both methods still achieve competitive results of reaching percentiles of 87 6.. and 87.1 1, respectively.
LLM-SR results We evaluate EvoTune on two real-world symbolic regression tasks from the LLM-SR benchmark suite (Shojaee et al., 2024): E. coli Growth and Stress-Strain Pre- diction. Our experimental setup mirrors that the original work, using a comparable compute budget of approximately 10,000 program samples (equivalent to the reported
22

---

Published as a conference paper at COLM 2025
Method
E. coli Growth (ID)
E, coli Growth (OOD)
Stress-Strain (ID)
Stress-Strain (OOD)
EvoTune (Phi 3.5 Mini 3.8B)
0.0082
0.0322
0.0033
0.0035
FunSearch (Phi 3.5 Mini 3.8B)
0.0383
0.0636
0.0037
0.0074
LLM-SR (Mixtral 8x7B)
0.0026
0.0037
0.0162
0,0946
LLM-SR (GPT-3.5-turbo)
0.0214
0.0264
0.0210
0.0516
Table 2: Results on two problems from the LLM-SR Shojaee et al. (2024) benchmark suite.
We report the Normalized Mean Squared Error (NMSE) on in-distribution (ID) and out-of- distribution (OOD) test sets; lower is better. FunSearch denotes LLM-based evolutionary search in our implementation.
2,500 iterations). As shown in Figure 4, EvoTTune consistently achieves better performance than our FunSearch baseline during the evolutionary search. As our implementation of the FunSearch baseline closely resembles the LLM-SR method, the performance advantage of EvoTune in both Figure and Table 2 can be attributed to the addition of its reinforcement learning fine-tuning stage standard LLM-based evolutionary search.
Throughout the equation evolution on the training dataset, Evotune outperforms FunSearch as shown in Figure 4. As our implementation of FunSearch baseline closely parallels the LLM-SR method, the performance advantage of Evo'Tune over FunSearch in both Figure 4 and Table can be interpreted as the benefit of adding a reinforcement learning fine-tuning stage to the LLM-SR method.
For the final evaluation, we take the best performing program found on the training set and evaluate it on in-distribution (ID) and out-of-distributio (OOD) test sets. Table 2 reports the Normalized Mean Squared Error (NMSE), where lower values are better. The results demonstrate that Evo Tune is highly competitive, despite utilizing significantly smaller model (Phi-3.5 Mini, 3.8B parameters) compared to the LLM-SR baselines (Mixtral 8x7B and GPT-3.5-turbo) Notably, on the Stress-Strain task, EvoTune outperforms both larger models on the ID and OOD test sets and remains competitive with the other methods on E.Coli Growth.
A.10 Additional results for bin packing, travelling salesman problem, and flatpack
Beyond the results presented in Section 4.2, we provide additional insights into the perfor- mance of our method.
37.4K
9:66
THE
14k
77.4k
BiN PAUKING
TE RosSeste
644-01
361 0155
4:3:1-6:0
3.76 0.19
3:33 0-13
3:24 0.18
5.15
L. LLAMA Ves FoRr
8.18 0.19
3.36 6.34
132 0.15
344 0.53
X:14 6.19
300 1 8.37
1010 6.17
3.25 0.34
3.35 1115
GRANITE FUNSCARCTI
0.15
3,07 806
2
231 0.05
2.51 0.06
275
3,65 = 0.05
2.93 0.07
2.845 0.09
GRANEE AVo2UER
3.00 0.07
2.31 1223500 0.87
3.5 0.07
2 9.80
2.66 0.00
2.56 0.05
3.91 6.07
2.90 0300:00 0.07
3.75 6.06
TRAPIIN
8.844 0.005
93945 8.349
3.565
8991 1
3.556 0.000
0.005
PIE PONSEARCH
2.566 2 0.004
2543
2 8:06
2555 0.002
2913 0.004
2.300 = 0.005
2,00 9
1.567 = 0.000
2559 = 0.008
2.555 D.E0R
PHE BUOTURE
2882 2 0000
2319
6.007
3,50 01008
2,905 9.804
2,79
0.008
2364 9.886
2.589 8 01000
2.568 0.008
2,530 2: (U006)
GRANNE TUNSRAMCN
2:006
0100
2.874 0.007
3,500
0100
2.834 0.007
3.519 0.003
2.50: 0.005
2,305 DUEEN
GRANITE ENOTUSE
2.501 01000
2.444
6.008
8.4%
01055
2: 8.807
2,500
- 0.007
2,853 4-008
2.535 0.00)
28 2.504 0.004
2,497 SA EUROS
LLAMA PUNSCARCH
01935
0.138
5:05
8:558
0.013
0.140
0.006
6.352 0.007
11128 8:
5:555 S 0,005
0.143 =2 0.005
0.338 E1016
LLAMA EroZuse
6:332
8865
8.312 0.004
0.128 2 9.364
6:311 0.003
0.305 3: 0.084
B:30 5 8.003
0.003
8.604
PUNSTARCH
0.005
0.109
0.115
0,102
0.101
0.002
RAUTCHE
0.005
0.100 8:06
6.163
0.104
(0,99
3/135 0.006
0317 0.005
BJ307 0.600)
GRANITE FUNSCARCIS
0.000
0,006 2: 9:00
0J101 0.002
6.000
0 0.000
0.09 2: 0.000
5:115 S 0,001
0.114 =5 0.001
0,009 EL002
GRANITE EruTusu
86307 2 0.00
0.383 6:00
0.100 0.002
0.101 0.000
0,899 = 0.002
0.09 0.002
8:334 5 0.001
0.3E3 2 0.003
0,009 5: 0.002
Table 3: Optimality gap achieved by the single best program found. We report the mean and standard error across 10 seeds on validation, validation-perturber and test sets for three sampling budgets (9.4k, 16k and 22.4k). Similarly to results in Table 1, our method outperforms the baseline in most cases.
23

---

Published as a conference paper at COLM 2025
Table 3 reports the best score achieved by single program. This metric is volatile than the average of the top 50 programs and despite the variability, our method still surpasses the FunSearch baseline in most cases.
Gade Rellen
Pe-Tadoud
Lien- Ieclee Uiee Parcork
Lin Eooises
-00
-32
-01
Naa
(a) Bin Packing
(b) Traveling Salesman Problem
4.5
4.21
0.39
033
Ph: Fedforch
Lama Pocher
7004
2000
(c) Flatpack Problem
Figure 5: Average reward scores valid sampled programs. The shaded areas represent the standard егror over 10 seeds. Our method outperforms the baseline in terms of its outputs having a better average score.
Figure presents the average score values of the programs that pass the evaluation. The results indicate that, on average, EvoTune generates higher-scoring programs than the baseline, demonstrating a sustained advantage throughout the search process.
We analyze the distribution of optimality gap scores across different sampling budgets for programs generated by various models in BP (Figure 6), TSP (Figure 7) and FP (Figure 8). Initially, both EvoTune and FunSearch yield similar optimality gap distributions. However, as the search progresses, EvoTune shifts its distribution more significantly towards lower optimality gaps by discovering greater number of high-scoring programs. As most of the increase occurs in the high-performing region, this validates the effectiveness of the RL-augmented search mechanism.
In summary, EvoTune effectively guides program generation toward high-scoring solutions, achieving superior performance compared the baseline by more rapidly discovering higher scoring solutions.
In addition to performance evaluation, we analyze the structural and semantic organization of the functions discovered by both EvoTune and FunSearch. To this end, we embed all generated functions into a semantic embedding space using pre-trained NeoBERT (Breton et al., 2025) encoder, and visualize the resulting representations via t-SNE (Van der Maaten & Hinton, 2008). Figure 9a and Figure 9b show t-SNE visualizations for EvoTune and FunSearch across three tasks. In the top rows, functions are colored by their assigned island in the program database; in the bottom rows, coloring reflects the timestep of their discovery. Both methods exhibit structured clusters that progressively diverge from the initialization function as the sampling budget increases. Notably, functions within the same island tend to display greater semantic similarity compared to those across different islands.
24

---

Published as a conference paper at COLM 2025
Averge Proputedy Scopllig Brigen 100
Liano EvoTuse Llana FarSeark
Graste- BroTuee
EvoTure
Grante- FuaSeach
FurSearch
150
125
10.0
7.5
500
25
6.0
5.0
00
2.
4.0
50
8.9
2.0
4.0
6.0
5.9
Optimolity Gop
Optiaaiity Cap
Optimlley Cup
Aoring lequroy Simplng lidgor W0b
35
40
Liano ParSearch
Graste- PeaSearch
Phi- FuzSeach
25
35
30
20
255
25
15
20
15
40
6.0
80
2.0
4.0
5.0
800
2.0
40
6.0
Optimdity Clup
Optimality
Optimality Cup
Auray Pequeyy- Canging Tudge 1400
Llamu Evw/lase
35
Grante- BvoTaze
Pli- EvwTune
Limes -1 ParrScech
Crotte PenSearch
Pli- FurSoorch
35
25
25
30
2.5
20
26
15
1.5
10
10
6.0
'20
4.0
5.0
9.0
2.0
4.
3.0
Optimnlity
Optinalityy
Optizallts
Awapg Prqueey- Senginng Nukgen 22000
355
Liano EvoTuse
Liama- FazSearch
401
Graste- BroTuce
Granie- FeaSearch
40
Phi- ExoTuas
Pli- - FunScarch
35
25
30
30
25
20
10
1.0
6.0
3.0
Optimolity Gop
Optieality Gap
Optinaliy Cip
Figure 6: Histograms showing the distribution of scores in the program database on the BP task for four checkpoints and all three models. Results are averaged across 10 seeds. EvoTune outperforms FunSearch in steering the policy towards high-performing regions of the search space.
25

---

Published as a conference paper at COLM 2025
20.0
Avcite Froqueey Sunplia Bolet: 1900
Uioe BroTuce
40
Guzite EvoTuse
Pli EvoTare
17.5
Liaea FanBearc
Grastic FunSbarck
Fundbacch
35
15.0
50
12.9
25
10.0
20
7.5
5.0
2.5
0.0
Optimality Glip
Oprimality Gap
Ortimality Gap
140
Joenag Frequzie Saupling Bulget 500
Liure EveTuze
Guante- EveTuse
250
Pti EveTanne PurSenchh
120
Fuseeuck
FunSearch
150
240
100
150
150
100
50
2.5
12
3.5
Ostinaalte
Ossianality
Aorruge Ficuzzey Satpling Bodye: 1600
Llana BroTuse
700
Guzste- EvoTuse
Fli. EveTare
Liurs Fundleack
Guanite FunSicrcc
350
Phi Purdiarch
200
600
300
150
250
400
200
100
300
150
100
2.5
2.8
3.0
3.2
3.5
3.5
2.5
2.8
3.0
32
3.5
3,6
2.5
288
3.0
3.2
3.5
3.8
Optimally
Oprimaiity
Optimality
JvergeFooutia Sanpling Balget 2300
400
Liura BooTuze
Gusite- Eoullnee
500
Phi- -reolan
Lbmo PunStarch
1000
Gonite Searkccc
Phi PurnSarch
350
410
250
300
1.50
200
100
2.5
2.8
3.5
3.2
3.5
2.5
2.55
3.2 Oycimnlity Glap
3.0
3.5
3.8
2.5
2.5
3.0
3.2
3.5
3.8
Oyyimolity
Ogtimolity Gag
Figure 7: Histograms showing the distribution of scores in the program database on the TSP task for four checkpoints and all three models. Results are averaged across 10 seeds. EvoTune outperforms FunSearch in steering the policy towards high-performing regions of the search space.
26

---

Published as a conference paper at COLM 2025
Lieza EveTure
Guatto- EvoTas PunScarc
Llama ParSkarch
PutSwcch
Proqueeyy
2
0.10
0.15
0.20
0.25
0.33
0.10
0.15
0.20
0.25
0.30
01.00
0.15
0.20
0.23
0.50
Oyrimilit Caa
Optnally Cup
Ogrimality Gig
100
Liams-
EDesTine Gradio- FurBeacc
Arcige Proqucay Sacpling Rolee: 340
Liass Sann--arre FatSourch
250
Phi BuiSards
80
200
150
40
100
20
50
5
0.10
0.15
0.20
0.25
0.30
0.10
0.15
6.20
0.25
0.30
0.30
0.35
6.25
0.25
0.50
Qysindlyy
Opdimaity Cup
Oysinaity Gap
Jecue Fremnncy- Sangling Badgn 19200
Llarss Ban
Lietu - FazSourch
400
Guaitt- Tae
Guante-Fureea Fureench
70
Phi- FusSarrd
Thi Duoitto
175
350
1.0
300
125
230
40
100
200
75
150
-50
10
0.20 Optiallt Cap
0.30
0.35
6.20
0.50
Optimodly Gap
Oprimaliy Gup
Asour Freeons)- Saapiin Sodant Salgen222000 22400
Liant - EveTane
Granio: Grasto-EroTas
140
Pui EvoTTn
500
Llassa FarSearch
500
Guarit- Purfcasch
ParSaach
120
250
400
100
200
300
150
2001
100
20
0.10
0.20
0.10
0.15
0.20
0.25
0.30
0.10
6.20
0.25
0.5
Optimait Gap
Optimality Gop
Oytimally Gay
Figure 8: Histograms showing the distribution of scores in the program database on the FP task for four checkpoints and all three models. Results are averaged across 10 seeds. EvoTune outperforms FunSearch in steering the policy towards high high-performing regions of the search space.
27

---

Published as a conference paper at COLM 2025
Ben Pocking Saaaingttebbe lebed
Traveling Silerras Freblens teand
Faiiaac Ieand
Bio Pocking Round
Traveling Saleuron Poollen Roand
FluPock Royal
(a) I-SNE visualizations of function embeddings produced by EvoTune using representations from a pre-trained NeoBERT encoder. The top row is colored by program database island, while the bottom row is colored with increasing sampling budget. For each task, functions are taken from the best-performing model and seed. EvoTune reveals structured clusters that divert from the initialization function over increasing sampling budget.
Bie Packing Islod
Trvelling Stzenrnn Problen Mdadd
FlyPack Mdadd
Nin Packing- Raced
Troellig Salerron PreMenn Brand
Tlathack- Bran
4000
(b) t-SNE visualizations of function embeddings from FunSearch using the same setup as Figure 9a.
Figure 9: Comparison of t-SNE visualizations for EvoTune (Top) and FunSearch (Bottom) across three tasks.
28

---

capacity on Published as a conference paper at COLM 2025
A.11 Generated programs
For completeness, we present the best heuristic found for BP, TSP, and FP in Listing 1, 2, and 3. These heuristics are found by Phi 3.5 Instruct 3,8B, Granite 3.1 2B Instruct and Llama3.2 1B Instruct, respectively.
import numpy as up
def priority float, bins: nd.rray,,y, 6ecay_rate: float 1.2, load_bolaacee_elgg
- Float 0,5, gelance_thresholie flest 0.35, max_balance bonus: float 7.0,
urgency_ing
lotpooy__nnnitttooooeeeoooo iotteonrrrrt_oo float = 1.3,
innovation_factorr fleat 1.5, dynamic_etate__wiiie
float 0.25, Lime_weight:
Elcat = 0.1,
flozt = 0.01, cestory_deccy_reee flost = 0,95, urgency_trend weightt float = bin_state jiinssatt_edaptation andppattttoonnonoooooaa float 0.05, saaeitty_eessitiivyy_eeee
flost = 1.1, exploration_ facter: float 0,05, 0.99, exploration_decay: float 0.07) -> ndaraar:y::
Lemporal_diversillyyeee
innovative priority calculation function that only builds upon the advanced atratagies of the previous versiona but
incorporates real-time adaptive leazning forecasting antioipate ruture bin states, ensuring optimal bin allecstion.
Args:
item: Size of the item to be added to the bin.
bins: Array copacitios for each bin.
decay_rate, Rate of exponential decay: higher values ingrease sensitivity to capacity differences,
ipac__sience__eeghe weight: Influence of load belancing the priority score. thresshlirr threshold < balanced.
bin balance considered insufficiently
max max_halance_bone bonus: Maximum bonus for a perfectly balanced bin.
urgency_ inflacion_raaee Rate which urgency increases for hina cioser capacity. innovation factor: Multipiles ler for balance, urgency impact, and dynamic state,
dynemic_stad state_ Weight given performance.
dynemic state, such historicel
factor into optimization. reai_time_ ceee_pptiee optpoppeaatte tmizatton sin_stonsstep. steps Adjuatment factor in real-time optimisation.
time_weight: Woight for incorporating
diatory_decay_rate Becay fastor for reducing the weight of historical performance ever time.
trgency_trend weigd Weight to emphasize urgency Lrends in the bia ilnocation strategy. bin_state_adie aaste_aaaptation_rtte Rate which bin state adaptation influences priority scores.
copacity_sends ionsttivvity_fatto maltiplier that amp) ifies effect
priority scores.
explaraticn_ factror Weight given to unused hin space as a pricrity.
ixploration_dedet decay: Decay factor reducing the influence of exploration time. temporai diwersitt Neight given to diversity in usage acruss time for optimization.
Returna:
Array priority scores for each bin siming foz optimal strategic allocation.
Celculate ideal capacity and balance fector ideal soppeity np- me-maan (bins) balance_ffecte fector = where (bs. abs (oins - idea" adea'_capacitt <s balance_threahhld,, 1, (1 (1
ab. (bins ideal_oapacity!
balanoe_threstoole
Calouiate urgency bonus boges ap. where ibins item belance_thrrshhole usgency_inflaation.eesss
Apply influence real-time optimization
iime_influence = anp.aann (1en (ains))
[aal_tim__opcmmiaatiooo aapiimiatte sestooootonttt
Calcuiate adaptive decay considering uzgency and time influence
ddaptive_decaat - abp (bins 8 item) v decay_rate a* (np. abs (bins item)
urgency_bonu time_influence)) balance_factor
score and exploration bonus Calculate load mp.elip(ng atd. / mean (bins) baad_balance weigh_
pnploorationboouse ap.clip ap. sumsumibins item) ap ap.sum + expieration_faateei, 0,
Introduce capacity sensitivity factor sepacity_consitive np.power max. (bins) np. np.min capacity..ammiitiiity.....
29

---

Published as a conference paper at COLM 2025
caleuiste temporel diversity
temporal_ddvarae ep.exp (-np.arange (een (ains)) / np. np.mex (bins)))))
immoraal_diveraityyyoo
calcuiste dynamic state impact
bin_stato_immaet np.exp (-np.ver (hins) dynmis__stato_ temporal_divarsity
Combine factors
emphasis on dynamic states, urgeney consitivaty, load ba balancing, exploration and capacity sensitivicyy
pelority_scores edaptive_dedt decay
prlority_scores +- lesd_balance__coe
max_balance__onit
priority_scored + bin_state_
prtority_soores exploration honus exploration__aaee
Normalize scale sccres real-time optimization, considering historieal
performance decay, urgency, temporat diversity, and capacity sensitivity
priority ap.elip (piippppirityy.coo 0, 1) np. tap.sumbbins item) })
indovation_Factor time_weight
return priority_soores
The highest scoring program discovered for bin packing problem. This program was generated by EvoTune with Phi 3.5 Instruct model and it achieves an optimality-ga of 2.06.
Listing 1:
import numpy as up heuristics
nun_nodes = distance_matrik.hhap
Average Distance and Connectivity
avg_distances sp.mean matrix, axia=l)
looal_connestivite op. (dinttnce, matrix, axis=1) (num_nodea
global_conmeetiviin ivity op. (op.aumddistance_mattt
/ (nam_nodes inum_nodes 1)1
Adaptive Shorteut Factor
cdaptiva_chorteut__fc
np.moximum (avg (aggaummavvg_dcctnnaaa 0.5) mp.nox
sicrorchical Complexity
herrrccioon laoorpppooopopppoooe eomplexityy (p.aumddistanee
2, axis=1)
Importence
node_impertance ap. sum/cisstancennatiic axis=l)
Dynanic Influence
infloonce_facton = / (1 (-dagggdddstssmtttteeeee 10)) $ Gasssian decay
local and Globel Connect Ivity Adjustment axis=l)
local decal_density np. sammdddstancemmatiill
hww._ node importance
mp.minimum(-. np.exp woop-llcol_densttty f Adjusted for lccal
Novel Dynamic Becay: Adapt facal Benafty Adjustment
weight less densely connected
docal_density_fectte = miniminmu 1 cocal_conectivvttyl
Popularity Factor
poputarity_facter snp. (distance_matzik, 21, axis=l) www.suistttneeeeatiii.. axis-1)
Novel Factor: Edge Connectivity
edge_ coneecceentttvtyy co.copy (ditta)ce_matrii) for range (mm_nndess): edge_conneet (vityy
hammddistance_marixike Inum_nodes 1)
WigheDegree Reight
wewedeeeeeeeeeeeeeeeeeeeeeeeeeee 0.5 Adjusted to emphasize sigh-degree nodes
heuristio_natrix idistance_natrix
avg_distances)
whtpriiee__rrrtt__eeeeeeeeeee hierarchical
cacpeeaalll_oo_ooeeeeeeaeoopplee complexity)) node_ mote_mmmortance degh__degre_wweignt
up
0.5) Favor high degree modes
# Time Stability Factor
time_stability np. dxpttdiistaneeeaataa 100) Adjusted edges larger
*9 differences heurlat'o canttraarrx cime_stab/11sp
30

---

Published as a conference paper at COLM 2025
Novel Factor: Edge-wise Connectivity
This factor considers local centrality diversity and edge-wise connect ivity adge_diversity abs minimum clooss_.onnectiviee suge__ooneettiviyy up wwp.mmxximmmmiimem (oc.ccccccccctiivrc.o..o edge_comnsctivixy) adga_diversity
heurlsti c_matrix aege__oometLiiisy_aaeeeee Lime_stability
dew.senyy_aattoo influance hetlunne_afttorrrrr populartty_faaton eaartix v= lo
local
Normalization to ensure the heuristic matrix volues sum to 1 for each sew (each edge) heurist! c_natrii /= np.sum(beuriatt cuattir axis=1) [t, np.newaxis)
nevel factor: Temporai stability Factor
temporal_stabi differences beuristic_matrix semplrsl_stability
(=distance_matrix 1006) Aajusted for edges with oider time
return heuristio_natrix
The highest scoring program discovered for traveling salesman problem. This program was generated by EvoTune with Granite 3.1 2B Instruct model and it achieves an optimality gap of 2.446.
Listing 2:
import numpy w.bb.ssrrde_triiee as st import numpy.lib.
import
from typing import Tuple, Unien
priority(
ourrent_arid: ap.ndarray,
blocks: np. adarray, sctien_mask: ap.ndarray
ap.rdarray:
nun_blocks blocks. shoptsssshppllle [0] blocks
Precompute rotated versions
rotated_bie blocked np.array
9op (block, k=z) for range(4)] for block blocks
1)
Pad the grid once (for boundary checking)
padded_grid np. ped 1, mode- 'constant, constant_valueew
Ieitialise O-vaive satrix
values (acl(aacion_nal shape, in.inf, )
float32)
Compute for each possible placement of block with rotation that has been blooked
bloct_idx range (aum blocks):
for rotation in ra]g
block zotsted (block_idk, rotation 1] Subtract to adjust rocation index
block_rexs, block_cols shoek
Extract all poseible placements vaing NumPy slicing
sub_grids ap. str.sttrieeeeeee sliding windowwwwwwwwwwoe www.wwwwwwwwwpaddddde..... (biock_rows
block_cols 1)1
Compute the scoras [)
for each placement
range (blook_rowa
for in zange (block_cols 1):
top-left corner
if biock_idx block_idx;
top_lef: block(i:112, j:5+2]
else:
top_lefs None
np. (np. (top_ieft, 4 1)
(block_rowa (block_cols
scores. sspendsee
Compute the weighted sum of the scores for blocks with rotation that has been blacked
weights np. (blook_roww block_colst 12 ** rows 11 [2
[block_oole
31

---

Published as a conference paper at COLM 2025
weighted ap.sum [weights scores for scores in scores]) ve valuas (block_ddd,, rotation - ...] weight-dd_aun
Apply action mask in operation
values (-action " -np.inf
calculate absoluče va valuea of 0-Valuea for all blooks abs_values up. ivalues)
Calcuiate cumulalive sum
ap. cunsum vaauuv, axis=2)
return cum
Listing 3: The highest scoring program discovered for the flatpack problem. This pro- gram was generated by EvoTure with the Llama3.2 1B Instruct model and it achieves optimality gap of 0.0829.
A.12 Comparison to non-LLM-based methods
The primary goal of our work was not to achieve state-of-the-art performance on specific benchmarks, especially as we use smaller, open-source LLMs, but rather to use these tasks as testbeds for rigorously evaluating the effectiveness of our proposed EvoTune method compared to the baseline with no training. Nevertheless, to contextualize its performance, we benchmark Evo against specialized non-LLM methods. For the TSP, compare against methods specifically designed for this problem, and for bin packing and flatpack problems, we use human-designed heuristics as baselines.
Comparison to task-specific methods (traveling salesman problem) We compare Evo- Tune with the following methods specialized for the traveling salesman problem:
LEHD (Luo et al., 2023) is a neural solver successor to POMO (Kwon et al., 2020) and Attention Model (Kool et al., 2018), which augments supervised learning of heuristics with a decoder specialized for TSP
KGLS (Amold & Sörensen, 2019) is a search-based baseline a more advanced version of the Guided Local Search (GLS).
NeuralGLS (Sui et al., 2024) is hybrid model integrating GLS with graph convolu- tional networks specialized for TSP
We evaluate EvoTune on 29 TSP instances from TSPLib, comprising real-world TSP instances of varying difficulty. In this way, can directly compare with the results reported in (Luo et al., 2023; Arnold Sörensen, 2019; Sui et al., 2024). Additionally, this evaluation serves as an additional benchmark for EvoTune to test the robustness and generalization of the evolved heuristics, since no instances from TSPLib are shown to EvoTune during training. Evaluation was done on the top-performing program evolved by Granite 3.1 as the base model.
For TSP, EvoTune evolves the heuristic that is used by guided local search (GLS), and GLS operation can be budgeted to call local search fmax times. While the specialized baselines operate with large budget of fmax 1000, EvoTune was trained with a minimal budget of just max 20 to reduce evaluation times due to computational constraints. In the table below, we we present the performance of EvoTune's heuristic when deployed with fmax 100, 200, 1000, i.e., it was never optimized to find heuristics under such budgets. The results, presented Table 4, confirm the strong generalization capabilities of the evolved heuristic. Evotune successfully achieves near-optimal performance when it is provided the same (or even less) local search budget as the baselines. It already performs comparably average to other baselines at fmax E 100, 200, and with f mmx 1000 it achieves the best average across all TSPLib instances, outperforming all other methods.
Comparison to human-designed heuristics (bin packing and flatpack problem For bin packing and flatpack problems, we include direct comparison to human-designed heuristics. For bin packing, we report results for the well-established best-fit heuristic. For flatpack, use greedy heuristic that promotes compact, efficient placements by placing larger
32

---

Published as a conference paper at COLM 2025
Instance
POMO
LEHD
NeuralGLS
KGLS
EvoTune Faax
100
EvoTune Fmax
200
EvoTune Fmax
1000
eil51
0.67
0.70
0.70
berlin52
0.04
0.03
0.00
0.03
0.03
0.03
0.03
st70
0.31
0.33
0.00
0.31
0.31
0.31
0.31
ei176
2.54
1.18
1.64
1.18
pr76
0.00
0.22
0.82
0.00
0.00
0.00
0.00
rat99
2.39
0.72
0.68
1.24
1.24
kroA100
11.41
0.12
0,113
0.06
0.12
0.12
0.02
kroB100
0.32
0.26
0.88
0.25
0.25
0.25
0.25
kroC100
0.18
1.77
0.01
1.25
0.83
0.01
kroD100
0.84
0.38
0.00
0.00
0.30
0.07
0.00
kroE100
0.45
043
1.05
0.07
0.49
0.17
rd100
0.01
0.01
0,00
0.02
0.01
0.01
0.01
ed1101
1.84
2.31
0.36
2.07
2.07
2.07
1.78
lin105
0.52
0.65
0.03
0.03
0.03
0.03
prl07
0.52
11.24
0.81
0.00
0,40
0,00
0.00
pr124
0.60
0.08
0.08
0.08
0.08
bier127
13.72
4.76
2.73
0.42
0.57
0.57
0.57
ch130
0.16
0.55
1.19
0.01
0.01
0.01
0.01
pr136
0.93
2.32
0.24
2.88
2.88
0.81
pr144
0.53
0.19
1.74
0.00
0.38
0.09
0.00
ch150
0.53
0.52
2.49
0.04
0.68
0.44
kroA150
0.70
1.40
0.77
0.17
2.54
2.54
0.65
kroB150
1.17
0.76
3.11
0.08
1.04
1.04
0.04
pr152
1.05
0.19
1.03
0.64
u159
11.95
1.13
0.90
0.96
1.44
1.44
0.00
rat195
8.15
1442
0.48
0.97
0.91
0.91
d198
17.29
9.23
1.28
0.31
0.90
0.90
0.71
kroA200
1.58
0.64
0.86
0.71
0.56
0.23
0.20
knoH200
1.43
Average
2.02
1.92
0.96
0.36
0.82
0.69
0.32
Table 4: Performance comparison TSPLib instances, showing the optimality gap (lower better). The EvoTune heuristic was evolved using minimal training budget fmax = 20. When deployed with the same budget as the specialized baselines fmax 1000, it achieves the best average performance.
Human-designed heuristic
EvoTuuee
FunSearch
Bin Packing
5.37
2.06
2.96
Flatpack
0.1092
0.0829
0.0898
Table 5: Comparison of optimality gaps against human-designed heuristics (lower better).
blocks first and maximizing adjacency. Note that these human-designed heuristics are used to initialize the search process. As shown in Table 5, using small open-source LLMs and budget of 22.4k samples, both methods successfully discovered algorithms that outperform the human-designed starting points, with EvoTune consistently finding the best-scoring solutions.
A.13 Alternative RL algorithm
In addition to our DPO-based RL-Update, we experimented with an alternative RL method based on the RMSTEM algorithm (Gulcehre et al., 2023; Singh et al., 2023). This approach iteratively refines the base model through supervised fine-tuning on high-scoring outputs gathered during evolutionary search. Unlike DPO, which uses a ranking- based objective,ReST EM progressively filters the program database to focus increasingly better-scoring samples and then fine-tunes the model on this refined dataset. At each RL-Update step (i.e. when f mod fRL O), we proceed as shown in Algorithm 2. In our experiments, we set p = 60 and = 3. The rest of the training parameters are similar to the ones described in Appendix A.8, including the learning rate schedule.
Our results in Figure 10 demonstrate that incorporating offline RL training using either RMSTEM or DPO yields better performance than no training at all. The DPO-based update consistently outperforms the EM variant across tested learning rates, indicating that its ranking-based signal more effectively guides the model toward high-scoring programs.
33

---

Published as a conference paper at COLM 2025
Algorithm 2 RI-Update using ReSTEM algorithm
Input: Program database D', base model nep.
Set the initial threshold z! to the p-th percentile of all rewards r(y) obtained from outputs generated since the previous RL-Update phase (i.e., from step fRL onward).
Let of max max m (x,y,r(y)) D'
for / = 0 to L - 1 do
Construct the SFT dataset:
DSFT ((x,1) E rly)) J.).
Update é by minimizing the negative likelihoo loss:
(0) -E (xy)>D log Ty x).
Update the threshold:
p max 71.0
7141 f- 7ld +
L
end for Output: Updated model zzh with parameters 8.
3.26
3.20
Mean Upiraae
3.16
3.10
3.06
3.00
1x10
3x
1
1x10 3x10 10
Evo TuoTune (DPO)
EvoTune (Re5)91)
Figure 10: Mean optimality gap (lower is better) for the top 50 programs on the validation at the final sampling budget, averaged over 10 seeds. Experiments were done using the Granite model on the bin packing problem. We compare EvoTune to two RL update methods DPO and ReST across three learning rates x 10 6 3 10 and 1 10 5). While both EvoTune variants outperform the baseline, the DPO variant achieves lower optimality gaps compared to the RM variant. Note that for the Granite model, the learning rate of x 10-5 was used to perform DPO experiments presented in the rest of the paper.
Our early experiments also revealed that tuning ReSTEM is challenging and its performance rapidly degrades with suboptimal hyperparameter choices. Although we focused primarily on the learning rate, which we identified as one of the most impactful hyperparameters, more comprehensive hyperparameter sweep needed to fully characterize the differences. Moreover, while initial SFT phase is typically applied before DPO updates, omitted to reduce training time. Future work may explore hybrid approaches that combine SFT with DPO updates to further enhance performance.
34


Reviews:
[{"review_id": "j8ERCEWcTq", "reviewer": "Reviewer_e6jZ", "summary": "The paper targets automated discovery of efficient algorithms and advances prior LLM‑based evolutionary search by making the language model itself a learnable search operator. The proposed framework interleaves evolutionary exploration with reinforcement‑learning fine‑tuning (RL‑FT): newly discovered, higher‑quality candidate algorithms serve as rewards to update the LLM, which in turn generates stronger offspring in subsequent generations. Evaluations on three classic combinatorial‑optimization benchmarks—bin packing, traveling salesman, and flat‑pack assembly—show that the RL‑augmented evolutionary loop finds better algorithms faster than a static‑LLM baseline, demonstrating the practical benefit of coupling RL with evolutionary strategies for algorithm design.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "This work has solid motivation, good writing, intensive and well-presented numerical experiments, crystal clear details and presentations, and impressive empirical results.", "reasons_to_reject": "1. The computation overheads induced by RL fine-tuning of LLMs are not discussed in this paper. A good way to show this is to draw figures similar to Fig. 2 but replace the x-axis as search time.\n\n2. It might have been discussed in the FunSearch paper, but it will be more self-contained if the authors could also compare with non-LLM-based search algorithms. Such algorithms can be more efficient with sampling and thus are more search-time friendly, or not because I can imagine the bottleneck of the search efficiency lies at the long evaluation time of searched programs.", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EdG51mt9ma", "reviewer": "Reviewer_rxQm", "summary": "- Quality: The algorithm is clearly specified and includes sufficient testing scenario, while it is still doubtful if the comparison is complete and makes sense. \n- Clarity: The paper has very high clarity. It explains the algorithm and everything very well. \n-  Originality: This is not the first work combining LLM with evolutionary search for algorithm discovery. The only novelty is maybe using RL. (see Reasons To Reject) \n- Significance:  I don't think the paper solves broader tasks. The paper is evaluated only on three well-known combinatorial optimization tasks without any extension to other meaningful tasks. For example, LLM-SR is more on the realistic scenario than this paper.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The idea is clear and noval. It is true that this is the first paper I see to combine DPO with LLM with evolutionary search in scientific discovery. \n- The storyline is clear and the method is easier to get understand. \n- In the experiment section seems all settings are been listed, which is good for reproduction.", "reasons_to_reject": "- Lack of a crucial reference. The LLM-SR proposes similar ideas but using training-free methods. Lack of comparison to LLM-SR makes this paper less convincing.  \n- Lack of baselines. Why only FunSearch? What about other existing methods? What is the performance without RL fine-tuning? Based on Algorithm 1, I believe the RL-Update steps won't be a necessary step if the EvoTune is combined with models like GPT-4o. Without that update, what are the results?  \n- Compute‑efficiency trade‑off unquantified. The additional RL phase surely adds GPU hours, how to compare that with FUNSEARCH?  \n\n[1] Shojaee, P., Meidani, K., Gupta, S., Farimani, A. B., & Reddy, C. K. (2024). Llm-sr: Scientific equation discovery via programming with large language models. arXiv preprint arXiv:2404.18400.", "questions_to_authors": "The improvements the paper needs to make is to compare with LLM-SR, which I think is a very good benchmarks and baseline for scientific discovery. \nTo the MDP definition, what is your discount factor $\\gamma$?", "extra_scores": {}}, {"review_id": "Za7XQ7vNaM", "reviewer": "Reviewer_YtJU", "summary": "This paper studies LLM-based algorithm discovery for combinatorial optimization (CO). Specifically, the authors propose EvoTune, a novel approach that combines evolutionary search with RL fine-tuning (i.e., DPO) to enhance LLM-driven algorithm discovery. Overall, the paper is solid and makes a meaningful contribution to the field.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* The topic studied is interesting and well-motivated.\n* The paper is well-written and easy to understand.\n* The proposed method is sound.", "reasons_to_reject": "* The paper evaluates the proposed approach on only three CO tasks. Including a broader set of CO or non-CO tasks would strengthen the evaluation.\n* Missing baselines. For example, comparisons with traditional TSP solvers (e.g., Concorde, LKH-3) and recently proposed neural solvers should be included. \n* Evaluation on large-scale instances, such as TSP1000, is necessary to assess scalability.\n* The RL fine-tuning introduces additional computational overhead. What hardware was used for the experiments? In addition to reporting the optimality gap, please also report runtime. Could you further benchmark all methods under the same time budget?", "questions_to_authors": "* Does the `Generate K outputs [...]` step in Alg. 1 involve evolutionary search? Based on the prompt provided in Appendix A.7, it appears that no crossover or mutation operations are used.\n* How is the validation dataset constructed to ensure that the optimization process remains unbiased (e.g., not overfitting to a specific data distribution)? Can the proposed method generalize to test sets containing larger-scale problem instances or those with significantly different data distributions?", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a new method that combines evolutionary search and reinforcement learning to help large language models discover algorithms. The initial reviews were positive about the paper's clarity and novel idea. However, all reviewers raised important questions. They were concerned about the computational overhead from the reinforcement learning phase, the limited comparisons to other methods, and the scope of the evaluation. 

I was particularly impressed with the authors' rebuttal, which was not just a clarification but included substantial new experimental results. (and as I've checked COLM policy, it seems adding new experimental results is allowed.) They provided the requested wall-clock time analysis, benchmarked against strong non-LLM baselines, and demonstrated the method's effectiveness on entirely new task domains. This thorough response resolved the reviewers' initial concerns and significantly strengthened the paper. The AC decide to recommend Accept.
Decision: Accept