Algorithm Discovery With LLMs: Evolutionary Search Meets Reinforcement Learning

6. Validation dataset construction and generalization

How is the validation dataset constructed to ensure that the optimization process remains unbiased (e.g., not overfitting to a specific data distribution)?

In addition to reporting results on a held-out test set, we also include a perturbed validation set designed to simulate domain shifts. Details on dataset construction are provided in Appendix A.1. In a nutshell:

• Test Set: For each problem, we sample new instances from the same distribution as the validation set, evaluating on unseen but in-distribution data.
• Perturbed Set: To further assess generalization, we introduce domain shifts in the validation set:
  • TSP: modify the adjacency matrix by assigning prohibitively high costs to selected edges, making certain connections untraversable (simulating road closures or network disruptions).
  • Bin Packing: randomly perturb the order of items to be packed.
  • FlatPack: introduce an obstacle at the center of the grid where no blocks can be placed.

Please also see our response to all reviewers for additional generalization and robustness results for TSP on TSPLib, a collection of real-world TSP instances that is not presented to EvoTune during training.

Our intention with these additional evaluation datasets was to explore how much the improvements gained by EvoTune in the original search space would translate to related problem instances. We were encouraged to observe that the gains generalized to these similar search spaces.

Can the proposed method generalize to test sets containing larger-scale problem instances or those with significantly different data distributions?

To assess OOD generalization to larger problem instances, we benchmarked the performance on the TSP dataset with 1000 nodes, which we detailed earlier in this response. For researchers interested in achieving even stronger OOD generalization, we suggest incorporating many different problem sizes within the validation dataset (for TSP, we currently only include two - 100 nodes and 200 nodes graphs). This already disincentivizes the discovered algorithms from becoming specialized to particular problem sizes and has encouraged solutions that generalize more broadly across scales, as can be observed by our results on TSP1000 and various TSPLib instances.

The primary focus of our work is on improving search efficiency and solution quality within a fixed search regime, rather than maximizing OOD generalization. In some problems, mathematicians are only concerned with optimizing the solution for a specific configuration or dimension. However, the additional experiments we carried out, as well as those suggested by the reviewer, help showcase the generalizability of evolved heuristics as a by-product of our method.

Thanks for your response.

To strengthen the evaluation, we incorporated...

You may also want to include how LLM-SR performs in these tasks. The key insight is not about the LLM-SR task, but also how your method compares to LLM-SR.

To clarify, the “without RL-Update” variant requested by the reviewer is precisely the FunSearch baseline reported..

Sorry for the confusion. What I mean is how your method compares to proprietary models. My question should be "if the FunSearch is combined with models like GPT-4o." For example, the improvements of RL fine-tuning over the non-fine-tuning version are indeed since you include the extra training steps. But how does it compare to the GPT4-o FunSearch? Will the RL result beat GPT4-o? These experiments will be helpful. It also might be helpful to compare the fine-tune 1B version to the Funsearch 3B version. My key concern is, RL does improve the performance, but will the extra training be worth it? If 3B version is better than the 1B fine-tuned version, how can to justify the necessity of fine-tuning?

I am also confused about the generalization ability of this method. Will the RL-finetuned version have worse generation ability on other datasets? To further clarify, the generation ability is, if you fine-tune your method on traveling salesmen, will it still perform good on BinPack (FunSearch)? Will there be a domain overfitting problem?

To summarize, my major concern is, fine-tuning always improves the model performance, which does not seem to be a good contribution.

Thanks a lot for your external experiments and looking forward if some of the results will be presented. Sorry again for my confusing question in the original reviews. Also, please let me know if any of my questions or understanding is wrong. I am happy to increase my score if my major concern gets resolved.

We thank the reviewer for their follow-up, clarifications, and openness to revisiting their evaluation. We appreciate the opportunity to address these points directly, please find our responses below.

1. Comparison to LLM-SR

You may also want to include how LLM-SR performs in these tasks. The key insight is not about the LLM-SR task, but also how your method compares to LLM-SR.

The LLM-SR paper indeed introduces both a (i) benchmark for symbolic regression and (ii) a method for solving it. The core methodology of LLM-SR, however, closely parallels FunSearch - LLM-SR utilizes an LLM-based evolutionary search framework and adapts it for symbolic regression tasks.

As acknowledged by the LLM-SR authors:

Most related to our work is FunSearch (Romera-Paredes et al., 2024) that combines LLMs with systematic evaluators to search for heuristics... Building upon these ideas, our LLM-SR framework employs LLM as an optimizer...

The LLM-SR method can be understood as a specialization of FunSearch for symbolic regression, with the following task-specific adjustments:

• The prompt contains a problem specification (concise description of the scientific problem).
• The generated program is specifically an equation function.
• Evaluation includes optimization of equation parameters on a problem-specific dataset, using either stochastic gradient descent or BFGS, as described in their work (Torch/Numpy versions).

Another key shared element is the program database (which LLM-SR refers to as an "experience buffer"). This component is structurally identical to the one used in the original FunSearch paper and in our work. This commonality encompasses both the architecture (island-based with clusters within islands) and the sampling methodology (uniform random island selection, Boltzmann sampling prioritizing higher-scoring clusters, and a preference for shorter programs when sampling within clusters).

Given these methodological similarities, the FunSearch baseline we employed in our experiments already includes the core techniques underlying LLM-SR. Thus, we believe that our existing reported improvements of EvoTune over the FunSearch baseline implicitly demonstrate that adding RL finetuning would benefit an LLM-SR-like approach. In summary, the baseline we call “FunSearch” is essentially the LLM-SR method, and “EvoTune” can be interpreted as combining the LLM-SR method with RL finetuning.

However, to fully address the reviewer’s request for comparison with LLM-SR, we ran experiments on two of their benchmark tasks (E. coli Growth and Stress-Strain), under comparable compute budgets of ~10,000 sampled programs (as reported as 2,500 iterations in the LLM-SR paper). We report the Normalized MSE (lower is better) of the best-performing function found on the train set, evaluated on both in-distribution (ID) and out-of-distribution (OOD) test datasets from LLM-SR.

We hope these results demonstrate the strength of our pipeline and address the reviewer’s request for comparison to LLM-SR. Furthermore, these results show that EvoTune, using the relatively small Phi-3 Mini (3.8B) model, is competitive and, in the case of the Stress-Strain problem, outperforms both the Mixtral 8x7B and GPT-3.5-turbo versions of LLM-SR, even on this specialized benchmark. This highlights the efficacy of EvoTune's RL-based fine-tuning.

We are encouraged that EvoTune demonstrates strong performance even within LLM-SR's specific domain. Additionally, we emphasize that while the LLM-SR method is targeted to symbolic regression, EvoTune is a more general framework - it can be applied to any problem where solutions are readily verifiable with a sufficiently dense feedback signal and can be structured around a code skeleton. It supports a broad class of reward signals, e.g., optimality gap, runtime, memory use, or even verbal feedback of a judge LLM translated to some scalar range. As such, EvoTune is designed for much wider applicability in scientific discovery and optimization.

2. Comparisons to Larger or Proprietary Models (e.g., GPT-4o, 3B vs 1B)

Sorry for the confusion. What I mean is how your method compares to proprietary models. My question should be "if the FunSearch is combined with models like GPT-4o." For example, the improvements of RL fine-tuning over the non-fine-tuning version are indeed since you include the extra training steps. But how does it compare to the GPT4-o FunSearch? Will the RL result beat GPT4-o? These experiments will be helpful.

Regarding comparing to a frontier model like GPT-4o, we would like to clarify that EvoTune is a technique designed to improve the performance of the underlying language model, whatever that model may be.

If we had access to GPT-4o and the resources for extensive experimentation, the most direct test of EvoTune's added value would be to compare GPT-4o + FunSearch against GPT-4o + EvoTune. If GPT-4o + EvoTune showed improvements, it would demonstrate EvoTune's ability to further boost even the most capable models. While we don't claim that EvoTune on a small open-sourced model surpasses GPT-4o + FunSearch on sample efficiency (as the base model's capability is an important factor), we hypothesize that GPT-4o + EvoTune could outperform GPT-4o + FunSearch.

Furthermore, as a relevant data point, for the LLM-SR task, our results show that EvoTune with Phi 3.5 Mini 3.8B model can already outperform GPT-3.5-Turbo + FunSearch.

We also note that querying proprietary models many times, as is required for evolutionary search methods, can be expensive. For example, in the FunSearch paper, which uses a proprietary model, Codey, they sample on the order of a million functions (a conservative back-of-the-envelope estimate suggests that a single instance of evolutionary search with 1 million program prompts costs ~$5-15k), which is prohibitively expensive for many scientific use cases, especially for academic labs.

It also might be helpful to compare the fine-tune 1B version to the Funsearch 3B version. My key concern is, RL does improve the performance, but will the extra training be worth it? If the 3B version is better than the 1B fine-tuned version, how can to justify the necessity of fine-tuning?

The reviewer's suggestion to compare 3B+FunSearch to 1B+EvoTune likely comes from understanding that the RL finetuning step presents an extra computational load. The reviewer proposes to offset the extra load by sampling from a larger, more resource-intensive base model. As other reviewers raised a similar concern on the extra computational load of the RL phase, we address this point in the Computational overhead of RL phase section in our common response to all reviewers. We invite the reviewer to consult the section where we show that EvoTune can not only improve sample efficiency but also wall-clock efficiency over the FunSearch baseline for the same underlying model. Moreover, we point out that using larger models could actually yield worse wall-clock efficiency. Although larger models often produce higher-quality outputs on average, they also require more time to generate each sample. As a result, fewer samples can be obtained within a fixed time frame, in addition to requiring more GPU memory.

Additionally, when comparing larger models to smaller ones, Table 1 in the original manuscript reveals an noteworthy trend: both FunSearch and EvoTune variants of Granite model (2B parameters) outperform the FunSearch variant of Phi models (3.8B parameters) across nearly all tasks and data splits, despite Granite being roughly half the size of Phi. A similar trend can even be observed when comparing Llama EvoTune (1B) with Phi FunSearch on some problems and data splits. These trends show that the base model’s size is not necessarily the determining factor, and EvoTune consistently boosts the performance of any base model. We hope this helps address the question about the scale of the base model used with FunSearch.

In summary, the core contribution of EvoTune is orthogonal to the underlying model capabilities and scale, it provides a lightweight, model-agnostic framework to steer generation toward high-performing programs, regardless of model size. While scaling remains a valuable research direction, we demonstrate that RL-based updates bring measurable improvements even in small models, without relying on parameter count or pretraining data to carry the search.

3. “Fine-tuning Always Helps”

my major concern is, fine-tuning always improves the model performance, which does not seem to be a good contribution

While we recognize that fine-tuning is broadly beneficial, the assertion that it "always improves performance" does not fully account for the nuanced dynamics of evolutionary search. In the context of evolutionary search, it is not straightforward that fine-tuning is always beneficial - overfitting to past good solutions can reduce exploration and harm long-term discovery of better functions.

This is precisely why we frame the update as an RL objective (specifically DPO) rather than traditional supervised fine-tuning. Additionally, we show that RL training does not merely increase the average score of the population, but extends the “tail” of the distributions towards higher scores.

Moreover, as diversity collapse is commonly observed in training LLMs with RLHF methods, another contribution in our work shows that using forward KL divergence to regularize against the reference policy outperforms using reverse KL divergence (which is commonly used in DPO). This is likely due to its mean-seeking behaviour, which avoids mode collapse and preserves the creativity of LLM outputs, which are crucial for evolutionary search to work well.

Thus, we believe our contribution lies in how we fine-tune, not just in the fact that we do, and in showing that principled reward-based updates yield consistent performance gains in evolutionary LLM search pipelines.

4. Generalization and Overfitting Across Domains

I am also confused about the generalization ability of this method. Will the RL-finetuned version have worse generation ability on other datasets? To further clarify, the generation ability is, if you fine-tune your method on traveling salesmen, will it still perform good on BinPack (FunSearch)? Will there be a domain overfitting problem?

Similarly to FunSearch, LLM-SR, and other methods in automatic algorithm discovery, our approach is task-specific by design. We do not aim for cross-task generalization — e.g., transferring from TSP to Bin Packing — unless explicitly adapted for it. Generalization in the context of discovery methods like EvoTune is usually considered across instances within a task (e.g., different sizes of TSP), not across unrelated tasks. This is essential when tackling diverse domains such as combinatorial optimization, symbolic regression, or biological modeling. Since finetuning with LoRA adapters is relatively cheap, each task is tackled separately.

That said, our formulation naturally supports continual fine-tuning across domains, as rewards can be aggregated online. We see this as a promising avenue for future work in lifelong scientific discovery and highlight that our method provides a unified framework to make this tractable, unlike supervised approaches, which require new ground truth for every domain shift.

We thank the reviewer again for their thoughtful engagement and detailed follow-up questions. We hope this response has clarified the key points raised, including the nature of our baselines and LLM-RS comparison, the role of model size, and the scope of generalization. If this addresses the concerns of the reviewer, we would sincerely appreciate the consideration in raising the score.

Thank you for your follow-up question. We appreciate the opportunity to provide further support for our statement:  "In the context of evolutionary search, it is not straightforward that fine-tuning is always beneficial - overfitting to past good solutions can reduce exploration and harm long-term discovery of better functions."

This statement is grounded in one of the fundamental challenges in evolutionary algorithms - premature convergence [1]. This occurs when an evolutionary algorithm converges to a suboptimal solution, losing the diversity necessary to explore the search space and find the global optimum.

An overly aggressive fine-tuning strategy can "overfit" current solutions, sacrificing the exploration needed for long-term discovery. This is a classic problem of over-exploitation at the expense of exploration. Our experiments confirmed this empirically. If the learning rate was set too high, the model stopped exploring and began repeating previous good solutions. The best program scores stagnated, and the discovery of new, unique solutions (measured by the number of unique scores) came to a halt. In these cases, the run with improper training was quickly surpassed by a baseline run with no training at all, demonstrating that naive fine-tuning can be detrimental.

This highlights that our contribution is not just in the fact that we finetune, but also in finding the right recipe for training. Our choice of a DPO algorithm with a forward KL regularizer preserved the diversity needed to improve top-performing solutions while guiding the search toward higher-scoring regions. For further evidence, we direct the reviewer to Appendix A.11, where we tried an alternative SFT-based training method, but it did not perform as well.

Thank you again for your valuable feedback.

[1] Affenzeller, M., Winkler, S., Wagner, S., & Beham, A. (2009). Genetic algorithms and genetic programming: Modern concepts and practical applications. CRC Press.

We thank the reviewer for their valuable insights. As the discussion period is coming to an end, we would appreciate it if the reviewer could kindly let us know whether their concerns have been adequately addressed and whether we could provide any clarifications if there are any outstanding concerns.

Objective and scope of our evaluation

We would like to clarify that the primary objective in this work is not to achieve state-of-the-art task-specific performance on combinatorial optimization benchmarks, but rather to use these tasks as testbeds for rigorously evaluating the effectiveness of our proposed EvoTune method. By focusing on controlled comparisons against FunSearch, we aim to isolate and demonstrate the practical impact of interleaving RL fine-tuning with evolutionary search in the context of algorithm discovery.

Broader perspective of the comparison to traditional solvers

While LLM-based evolutionary search is not intended to outright replace specialized classical solvers, it offers several advantages that we believe are complementary and valuable:

• Flexibility and generality: EvoTune and FunSearch can be applied to a very wide range of optimization problems, including those with complex or non-standard constraints, where it’s common to rely on hand-crafted heuristics or where solvers are not available at all.
• Scalability: EvoTune and FunSearch operate by searching over algorithmic function space, rather than solving large-scale optimization problems directly. As noted in the FunSearch paper, this leads to greater scalability on large instances where classical solvers struggle.
• Interpretability: The discovered solutions are algorithms rather than black-box numerical outputs. This makes it easier to identify patterns or structure in how solutions are formed - an insight that the FunSearch paper leveraged to restrict the search space and uncover even better solutions.

3. Evaluating the method on additional tasks

Reviewer rxQm: 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.

Reviewer YtJU: 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.

We appreciate the reviewers’ suggestion to evaluate our method on a broader set of tasks. While our current study focuses on three combinatorial optimization problems $-$ bin packing, traveling salesman, and flat pack $-$ we selected these tasks for their recognized significance and direct relevance to numerous real-world applications. For example, the Traveling Salesman Problem (TSP) is fundamental to areas such as logistics, network design, and resource allocation, while bin packing is applicable in operations research and industry settings.

To further address these concerns and strengthen our evaluation, we evaluated our method on:

• HashCode programming competition questions [7] inspired by real-world engineering challenges faced at Google (Figure 3 Top)
• LLM-SR [8] (Figure 3 Bottom)

Our expanded experiments are consistent with the results in the original submission, but they also expand the scope and provide additional evidence on the applicability and robustness of our method. We hope this addresses the reviewers’ concerns regarding the diversity and significance of the evaluation tasks.

[1] Dao, T. (2024). FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning. International Conference on Learning Representations.

[2] Luo, F., Lin, X., Liu, F., Zhang, Q., & Wang, Z. (2023). Neural combinatorial optimization with heavy decoder: Toward large scale generalization. Advances in Neural Information Processing Systems.

[3] Kwon, Y. D., Choo, J., Kim, B., Yoon, I., Gwon, Y., & Min, S. (2020). Pomo: Policy optimization with multiple optima for reinforcement learning. Advances in Neural Information Processing Systems.

[4] Kool, W., Van Hoof, H., & Welling, M. (2018). Attention, learn to solve routing problems!. arXiv preprint arXiv:1803.08475.

[5] Arnold, F., & Sörensen, K. (2019). Knowledge-guided local search for the vehicle routing problem. Computers & Operations Research

[6] Sui, J., Ding, S., Xia, B., Liu, R., Bu, D. (2024). NeuralGLS: Learning to guide local search with graph convolutional network for the traveling salesman problem. Neural Computing and Applications

[7] Veličković, P., Vitvitskyi, A., Markeeva, L., Ibarz, B., Buesing, L., Balog, M., & Novikov, A. (2024). Amplifying human performance in combinatorial competitive programming. arXiv preprint arXiv:2411.19744.

[8] 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.