acceptodds
Under review as a conference paper at ICLR 2027

ExpEvolve: Structuring and Reusing Experience for Evolutionary Open-Ended Discovery

Abstract

Evolutionary coding agents such as AlphaEvolve are one of the notable successes in using Large Language Models (LLMs) to build AI Scientists. These agents tackle open-ended scientific problems by iteratively improving and evolving programs, leveraging the prior knowledge and reasoning capabilities of LLMs. Despite their success, mutations over programs are mostly low-level upon surface heuristics, without a persistent unit of control. In contrast, science compounds through ideas. In this work, we propose ExpEvolve, which injects idea-level extraction and control into evolution: it discovers and leverages the high-level factors from programs that explain scoring differences among different programs. We characterize theoretical conditions on when discovery with idea factors improves sample efficiency. We also build a practical framework to show that the extracted high-level idea factors are helpful for guiding exploitation from experience and exploration when discovery comes to a plateau. Across 11 open-ended mathematical tasks, ExpEvolve significantly improves the final performance and sample efficiency up to 5.0×. The improvements also transfer to 4 other LLMs and to 6 machine learning tasks from MLS-Bench. Analysis shows that ExpEvolve can discover idea-level factors to provide better exploration and exploitation for evolutionary discovery.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Evolution, LLMs, Scientific discovery, Causality

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_qwM3OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes ExpEvolve, an add-on for LLM evolutionary coding agents that turns the archive of scored programs into explicit idea factors Factors are mined from program pairs that the current factors misrank and then used as ADD/REMOVE-style edit actions chosen by a bandit, while a plateau mode steers the search away from factors shared by the incumbent family. Built on SCS, the method is evaluated on 11 math discovery tasks. It reports better final scores than baselines on most tasks and 1.7x to 26.2x fewer evaluations to reach SCS’s final score on four tasks.

Critical strengths
  • Mining factors from misranked pairs and turning them into bandit-controlled edits is a concrete alternative to reusing raw programs or free-form summaries, and the resulting memory can be inspected. This is the main reason I find the paper interesting, since it gives a handle on what the agent has actually learned.

  • Consistent gains over its own backbone at a matched evaluation budget. In Table 1, ExpEvolve is better than or tied with SCS in mean on all 22 task/configuration pairs. It also stays stable when the budget is split into more, smaller generations, where SCS drops noticeably on some tasks (e.g., Hadamard)

Critical weaknesses
  • The gains are not attributed to idea-level reuse. Apart from an SCS+meta comparison shown on one task, there is no ablation of ExpEvolve's own components. So the idea-guided actions are not separated from the other prompt changes it makes, such as a warm-up instruction asking the LLM to list well-known approach families. The three largest speedups in Table 9, including the 26.2x, are reached within the first 5 to 13 evaluations, inside warm-up and before the factor machinery has had a chance to act. The factors also cut against the paper's own thesis: several top-weight factors in Fig. 8(b) are implementation details (a fixed random seed, precomputed triplet indices). In the showcased SumDiff run, four of the six idea-guided new bests come from one action that removes a low explicit time limit. Thm. 3.1 does not fill this gap, since it compares a known faithful representation against fully unrelated programs, which is not the SCS setting

  • Efficiency is counted only in evaluator calls, and the broader claims are thin. All factor-related LLM calls sit outside the budget and are not reported, even though each discovery round re-annotates the whole archive. Most evaluators here are capped at 60s, so LLM cost is likely the real budget, and a cost-matched SCS is missing. The cross-LLM result is a single task with no seed variation shown (DeepSeek-v4-pro stays behind SCS for most of the run), and the MLS-Bench gains are 3-seed means without variance. This matters because the paper is motivated by expensive-evaluation science, but the experiments neither test that regime nor show a total-cost advantage in the cheap one.

Questions for authors

Can you add one-component-off ablations at the same budget, including an SCS run that receives the same warm-up diversification prompt? This is the main evidence that could move my rating.

What are the total LLM tokens and wall-clock per run for ExpEvolve versus SCS, and how does SCS do with a matched LLM budget (e.g., more evaluations)?

What drives the Table 9 gap within the first 5 to 13 evaluations? Does it survive if the metric averages over all seeds instead of only seeds with a successful program? Also, where does the abstract’s 5.0x come from, given Table 9 reports 1.7x to 26.2x?

How well do admitted factors predict the order of programs generated after their admission?

7 comments
AuthorsOpenReview ↗

Response to Reviewer qwM3 [1/5]

Thank you for your time and the careful reading of our work! Please find our detailed responses to each of your concerns.

W1.1 & Q1 One-component-off ablations, including SCS with the same warm-up prompt.

First of all, we need to clarify that, diversified exploration is a critical condition for the success of open-ended discovery, as implied by our Theorem 3.3. Specifically, Thm. 3.3 shows that when the evaluated programs agree on an idea, its role cannot be identified with any number of evaluations. The discovery of idea factors therefore needs an archive in which the ideas vary. The warm-up instruction hence serves as initial exploration of varying ideas.

Before showing one-off ablation results including the warm-up instructions, we list components in which ExpEvolve differs from SCS:

  • Diversified initial exploration: the warm-up instruction above.
  • Idea factors: they are discovered from the pairs of programs that the current factors fail to order, annotated on every program, and summarized in the prompt of every slot.
  • Idea-guided actions: a bandit assigns slots to ADD, REMOVE, and SET actions on the factors, each with example programs in the target state.
  • Idea-guided exploration at plateaus: the factors shared by the top programs are identified, and the search is steered away from them.

Next, we provide two types of ablations to show the effectiveness of design components in ExpEvolve. We begin by showing view 1: one-off ablations over whole runs, where we run different ablation variants with one component off across 4 tasks with the same budget setting of 10 generations of 20 programs.

MethodHadamard ↑SumDiff ↑Heilbronn ↑Min overlap ↓
SCS0.8349 ± 0.10081.1161 ± 0.00510.03356 ± 0.000640.38107 ± 0.00020
SCS + warm-up instruction0.8078 ± 0.08981.1182 ± 0.00110.03457 ± 0.001610.38102 ± 0.00004
ExpEvolve w/o idea factors0.8468 ± 0.12871.1189 ± 0.00050.03495 ± 0.001840.38106 ± 0.00008
ExpEvolve w/o idea-guided actions0.8596 ± 0.00001.1202 ± 0.00340.03564 ± 0.000100.38123 ± 0.00023
ExpEvolve w/o exploration at plateaus0.8801 ± 0.03551.1208 ± 0.00160.03587 ± 0.000160.38102 ± 0.00008
ExpEvolve w/o warm-up instruction0.9211 ± 0.00001.1195 ± 0.00200.03598 ± 0.000440.38098 ± 0.00001
ExpEvolve0.9259 ± 0.00841.1222 ± 0.00070.03584 ± 0.000720.38098 ± 0.00004

It can be found that, SCS with the warm-up instruction stays below ExpEvolve on all four tasks, implying that warm-up instruction alone does not explain the improvements of ExpEvolve. In addition, the ablations by removing the other components also cause performance decreases, implying the necessity of each component.

We further extend the SCS with warm-up instruction to more tasks with the budget setting of 20 generations of 10 programs:

TaskSCSSCS + warm-up instructionExpEvolve
Hadamard ↑0.6641 ± 0.16930.9006 ± 0.03550.9211 ± 0.0000
Pack ↑2.6170 ± 0.02782.6307 ± 0.00702.6354 ± 0.0010
Linprog ↑2.6354 ± 0.00102.5443 ± 0.00182.6354 ± 0.0010
SumDiff ↑1.1109 ± 0.00081.1129 ± 0.00521.1161 ± 0.0057
Heilbronn ↑0.0313 ± 0.00260.0321 ± 0.00270.0353 ± 0.0009
Min overlap ↓0.38156 ± 0.000530.38121 ± 0.000220.38097 ± 0.00003
Kissing ↑413 ± 23452 ± 114526 ± 97
Second autocorr. ↑0.8398 ± 0.01630.8661 ± 0.00270.8825 ± 0.0000
First autocorr. ↓1.5235 ± 0.01061.5232 ± 0.00741.5113 ± 0.0021
Max-min ↓12.9338 ± 0.077213.0000 ± 0.000012.9262 ± 0.0640

It can be found that, although the warm-up instruction sometimes helps SCS, SCS with warm-up instruction still underperforms ExpEvolve. Hence, warm-up instruction does not account for the improvement of ExpEvolve.

AuthorsOpenReview ↗

Response to Reviewer qwM3 [2/5]

View 2: one-step sampling from a shared archive. To separate the effect of a prompt component from the variation across runs, we fixed the archive and sampled new programs from it under different prompts. For each run of ExpEvolve, we took two archive states, an earlier and a later one, and sampled 20 programs using SCS prompt and the idea-guided bandit slot in ExpEvolve.

TaskStateSCS promptExpEvolve slots
Linprog ↑Earlier2.5067 ± 0.17572.6287 ± 0.0059
Linprog ↑Later2.5723 ± 0.13332.6277 ± 0.0064
SumDiff ↑Earlier1.1055 ± 0.02571.1144 ± 0.0031
SumDiff ↑Later1.1175 ± 0.00331.1196 ± 0.0012
Heilbronn ↑Earlier0.02711 ± 0.007230.03040 ± 0.00231
Heilbronn ↑Later0.03055 ± 0.011830.03625 ± 0.00041
Min overlap ↓Earlier0.38692 ± 0.012750.38344 ± 0.00536
Min overlap ↓Later0.38182 ± 0.001970.38118 ± 0.00020
First autocorr. ↓Earlier1.6213 ± 0.18601.5648 ± 0.0180
First autocorr. ↓Later1.5673 ± 0.03671.5519 ± 0.0235
Max-min ↓Earlier12.942 ± 0.05712.911 ± 0.046
Max-min ↓Later12.941 ± 0.05712.919 ± 0.052
Hermite ↓Earlier4.577 ± 3.4251.370 ± 2.401
Hermite ↓Later5.917 ± 2.3660.728 ± 1.647

It can be found that, from the same archive, the slots that ExpEvolve allocates produce better programs than the prompt of SCS, showing the benefits of idea factor guidance.

W1.2 & Q3 The gap in Table 9 within the first 5 to 13 evaluations, averaging over all seeds, and the origin of 5.0x.

Thank you for the careful check. Due to the variations in evolutionary open-ended discovery and diversified instructions, the first generations may obtain higher results in ExpEvolve. The original 5.0x is the median of the eight ratios in Table 9 of the submission. "up to" was a wording error, which we have corrected in the abstract and the introduction.

To further compare the sample efficiency of ExpEvolve against SCS, we perform finegrained investigation:

(1) We report the number of evaluations that SCS and ExpEvolve need to reach the final performance of SCS, computed on the mean over all seeds, in the table below:

TaskSCS, 10 × 20ExpEvolve, 10 × 20Fewer evaluationsSCS, 20 × 10ExpEvolve, 20 × 10Fewer evaluations
Hadamard18610 †18.6x1315 †26.2x
Pack173622.8x1438 †17.9x
Linprog1584 †39.5x1291021.3x
SumDiff180812.2x181971.9x
Heilbronn199523.8x16927 †6.3x
Min overlap141841.7x14413 †11.1x
Kissing–––182613.0x
Second autocorr.–––748 †9.3x
First autocorr.150443.4x153354.4x
Max-min1542 †77.0x19528 †7.0x
Hermite69561.2x1411231.1x

†: reached no later than the last generation with the warm-up instruction. –: both methods reach the same final score within the first three generations.

It can be found that across the majority of settings, ExpEvolve reaches the final performance of SCS in generations after the warm-up, and in these settings it needs 2.4x fewer evaluations than SCS on average.

AuthorsOpenReview ↗

Response to Reviewer qwM3 [3/5]

(2) To get rid of the influence of warm-up instructions, we further compare sample efficiency between ExpEvolve w/o warm-up instructions and SCS.

SettingSCSExpEvolve w/o warm-up instructionFewer evaluations
Hadamard, 10 × 20186920.7x
Hadamard, 20 × 10131294.5x
SumDiff, 10 × 20180762.4x
SumDiff, 20 × 10181267.0x
Heilbronn, 10 × 20199742.7x
Heilbronn, 20 × 10169266.5x
Min overlap, 10 × 20141751.9x
Min overlap, 20 × 10144720.6x

It can be found that ExpEvolve w/o warm-up instruction reaches the final mean of SCS with 1.9x to 20.7x fewer evaluations than SCS in all eight settings of Table 9, including the three settings with the largest ratios.

(3) In our response to W2.1&Q2, we continue running SCS until it consumes the same number of tokens as ExpEvolve with 200 programs, which takes on average 380 programs on Hadamard, 360 on SumDiff and Heilbronn, and 293 on Min overlap. With these budgets, SCS still stays below ExpEvolve with 200 programs.

(4) In our response to Reviewer C4Hb, W3 & Q2, we also extend the comparison to DeepSeek-v4-pro across the four tasks with three seeds. We can observe consistent improvements in sample efficiency.

W1.3 & Q4 Do the admitted factors predict the order of later programs? Implementation-level factors and the SumDiff showcase.

We need to clarify that the idea factors are meant to explain the programs that have already been evaluated in the experience archive. In each discovery round, they are fit to the differences among the evaluated programs, and the pairwise ranker only selects the pairs that the current factors fail to explain. The exploitation of factors are further determined by the multi-armed bandit and the LLMs. The ranker is never used to predict or filter new programs. The two factors that you mention, the fixed seed on Hermite and the precomputed indices on Heilbronn, were not selected by any idea-guided action in their runs.

Furthermore, in Fig. 8(b), the factors with shadow background are those we identify at the plateaus, which we need to mask out and explore alternatives in the future rounds. To further understand which types of factors lead to improvements, we labeled every discovered factor with a type using an LLM. On the four tasks, Hadamard, SumDiff, Heilbronn, and Min overlap, 35 new best programs come from idea-guided slots, and for each of them we look at the type of the factor that its action targets:

Type of factorExample (task)Discovered factorsNew best programs from idea-guided slots
Search strategyuses_randomized_greedy_selection (Kissing)462 (40%)12
Constructionuses_gf27_paley_construction (Hadamard)273 (24%)4
Implementation detailprecomputed_basis_cache (Hermite)183 (16%)10
Restatement of task constraintsboundary_margin_constraint (Pack)81 (7%)4
Computational resource or timetime_limit_and_early_stopping (Pack)72 (6%)4
Numerical method or libraryuses_linear_programming_optimization (Pack)70 (6%)0
Misc12 (1%)1

Search strategies and constructions account for 64% of the factors and for 16 of the 35 new best programs. Implementation details account for 16% of the factors and for 10 of them.

The run in Fig. 8(c) is not typical and is the only run in which a single action produces more than half of the new best programs from idea-guided slots. In the other two runs of the same setting, the new best programs also come from actions on the search itself, e.g., remove::uses_random_search_with_large_max_val (1.1120 to 1.1172) and set::initial_set_diversity=greedy_single (1.1172 to 1.1204 and then to 1.1214) in one run.

Reviewer_1UYROpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a method for program mutation in LLM-based algorithm discovery. Existing approaches to program-level improvement tend to repeatedly make minor modifications, such as parameter tuning, which often do not lead to substantial performance gains. To address this limitation, the authors focus on changes at the idea level. They formulate the algorithm discovery process as a POMDP by representing the discovery workflow as a graphical model.

Critical strengths
  • The idea of formulating the problem using a structural causal model is interesting.

  • The paper is theoretically convincing. The authors theoretically demonstrate that leveraging structures shared across programs can significantly reduce the number of evaluations required to discover an optimal program. Applying a structural causal model is also a theoretically natural approach, making the argument persuasive.

  • The experimental results are also strong. (However, I have some concerns, as discussed in the weaknesses section).

Critical weaknesses
  • I have concerns about the fixed budget used in the experiments. The authors define the fixed budget as the number of programs multiplied by the number of generations, but this does not represent a computational budget in terms of FLOPs or token costs. Ultimately, algorithm discovery is a search problem, and allocating more computational resources (token costs or FLOPs) generally allows better solutions to be found. However, even with the same number of generations, the actual computational budget may differ. Therefore, the results in Table 1 may not represent a fair comparison. The paper would be improved by comparing methods based on actual API token consumption or FLOPs.
Questions for authors

n/a

6 comments
AuthorsOpenReview ↗

Response to Reviewer 1UYR

Thank you for your time and constructive comments! Our detailed responses are as follows.

W1 The budget counts programs, which is not a computational budget in tokens or FLOPs.

Following your suggestions, we continue SCS beyond 200 programs. Since the LLMs are accessed through APIs, FLOPs are not available to us for these models and we use token costs as a alternative measure. Specifically, we consider four tasks below and allocate more evaluation budgets to SCS until the cumulative token costs reach the overall token costs of ExpEvolve, including those used for idea discovery, annotation, and exploitation.

Hadamard ↑SumDiff ↑Heilbronn ↑Min overlap ↓
Programs of SCS at the token target (mean)380360360293
SCS at 200 programs0.8349 ± 0.10081.1161 ± 0.00510.03356 ± 0.000640.38107 ± 0.00020
SCS at the token target0.8665 ± 0.01181.1191 ± 0.00250.03547 ± 0.001000.38099 ± 0.00002
ExpEvolve at 200 programs0.9259 ± 0.00841.1222 ± 0.00070.03584 ± 0.000720.38098 ± 0.00004

At the matched token cost, SCS remains below ExpEvolve with 200 programs on Hadamard and SumDiff, and is comparable on Heilbronn and Min overlap.

Furthermore, we also extend the analysis to frontier reasoning models, i.e., DeepSeek-v4-pro, and record the token costs.

TaskMethodScore at 200 programsMutator tokensIdea-factor tokensTotal tokensAPI cost (USD)
Max-min ↓SCS12.9883 ± 0.02044.91M04.91M9.40
Max-min ↓ExpEvolve12.9631 ± 0.06403.67M0.74M4.41M6.67
Hermite ↓SCS0.3538 ± 0.00675.68M05.68M10.83
Hermite ↓ExpEvolve0.3482 ± 0.00004.52M0.92M5.44M8.26
Linprog ↑SCS2.6194 ± 0.01415.72M05.72M10.18
Linprog ↑ExpEvolve2.6284 ± 0.01304.31M0.82M5.13M7.51

Interestingly, with DeepSeek-v4-pro, ExpEvolve uses fewer tokens than SCS while reaching better performance. The reason is that the programs proposed by ExpEvolve are generically less complicated, and the mutator also spends fewer tokens on reasoning over instructions given by ExpEvolve.

Please feel free to let us know if you have any other questions. Thank you again for your time and effort in reviewing our work!

Dear Reviewer 1UYR,

Thank you again for your time in reviewing our paper.

As the discussion period is ending soon, could you let us know whether this addresses your concern? We are happy to provide any further clarification in the remaining time.

Best regards, Authors

Reviewer_1UYROpenReview ↗

Thank you for the additional experiments.

Thank you for the additional experiments. The comparison under an equal LLM token budget partially addresses my concerns, but I remain unconvinced about the generality of the results. The equal-budget comparison covers only four tasks. Could you explain why these four were selected from the eleven tasks in the paper?

Reviewer_C4HbOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes ExpEvolve, an evolutionary LLM-based search method. The main feature of the method is the extraction of so-called high-level ideas from the evaluated programs and the use of these ideas to guide the search. The authors provide a causality-based perspective on the evolutionary discovery process and, in their framework, show that the policy that reuses historical experience converges faster than one without history, while also posing the identifiability problem, i.e., determining which ideas actually caused improvement or degradation. They employ the discovery loop from the COAT framework, with a memory bank for ideas and a fitted pairwise ranker on the idea factors. Unexplained pairs with large gaps trigger a new idea to explain the difference. Multi-armed bandits paired with some random exploration following SCS are used for exploiting the ideas. In general, ExpEvolve outperforms SCS and ShinkaEvolve baselines on 11 open-ended mathematical discovery tasks and improves OpenRSI on MLS-Bench.

Critical strengths
  • Causal formulation of discovery. The paper offers an interesting attempt to formalize evolutionary discovery in the language of causality. It connects the identification of factors behind performance differences with the need to explore programs where those factors vary, providing a principled motivation for structured experience reuse and continued exploration.
Critical weaknesses
  • Missing comparisons and novelty positioning. My main concern is the limited comparison with methods that extract structured knowledge from an agent’s experience. Although the paper includes ShinkaEvolve and SCS+meta, approaches such as the reasoning strategies in ReasoningBank and the strategic principles in EvolveR are not considered. Their memory mechanisms seem to be similar to the ideas of ExpEvolve when adapted to the same evolutionary search setting. The paper should position its novelty more carefully against these methods and clarify what the proposed factor representation and search control add beyond extracting and reusing insights.
  • Limited connection between theory and method. The theory is interesting, but its connection to the implemented method remains limited. The actual method must discover and annotate the factors using an LLM, and the theory imposes no constraints on the method, only inspires it. It does not establish when the proposed extraction procedure identifies useful factors or how imperfect factors affect search.
  • Dependence on the evaluation budget. Figure 7 suggests that the advantage depends on the model and evaluation budget. With DeepSeek-v4-pro, ExpEvolve trails SCS for much of the run and overtakes it only near the 200-program endpoint; with GLM-5.2, the curves are close after the initial stage. Around 100 evaluations, these panels do not show a clear advantage. This makes the sample-efficiency claim less consistent across models.
Questions for authors
  1. Can the authors provide a comparison against an adapted structured memory baseline, like ReasoningBank or EvolveR, using the same model and evaluation budget?
  2. Could you report performance at several evaluation budgets, with uncertainty across repeated runs, and explain the choice of 200 evaluations?
9 comments
AuthorsOpenReview ↗

Response to Reviewer C4Hb [1/4]

Thank you for your time and constructive comments! Below, we provide detailed responses to your questions.

W1 & Q1 Comparison with structured memory baseline.

Thank you for bringing us the two relevant works, ReasoningBank[1] and EvolveR[2]. We have added both works to the related work (Sec. 2). Below, we first clarify how ExpEvolve differs from them and how the difference relates to our analysis, and then report the empirical comparisons:

The extraction and exploitation of experience in ExpEvolve is relatively more controlled than that in ReasoningBank[1] and EvolveR[2]. The following table lists the dimensions where ExpEvolve differs from [1,2]:

ReasoningBank [1]EvolveR [2]ExpEvolve
Extraction
Unit of experienceMemory item (text)Principle (text)Idea factor, a variable annotated on every program in the archive
Extracted fromSuccessful and failed trajectories, one at a timeSuccessful and failed trajectories, one at a timeThe pairs of programs that the current factors fail to rank [3]
Checked against other experienceNoSimilar principles are mergedAssociation with the score, measured on the whole archive; factors merged wrt. similar annotations
Exploitation
How it is usedThe most similar item is added to the promptThe most similar principles are added to the promptCompiled into edit actions (ADD, REMOVE, SET), with demonstration programs
Feedback on its usefulnessNoneSuccess rate of the trajectories that retrieved the principleBandit reward, relative to random exploration in the same generation
At a plateauNo specific stepNo specific stepExplores away from the factors shared by the top programs

Specifically, both [1,2] distill the successful and failed trajectories into pieces of text by LLMs. Since it’s an uncontrolled process, LLM-based summarization may not properly identify the high-level strategies that sufficiently explain the contrast between successful and failed trajectories, while being prone to:

  • Hallucinated patterns. On Max-min, the principles distilled by [1,2] may state that a squared ratio of 13 is the known optimum (e.g., "known optimal ratio is sqrt(13)"), which is not true.
  • Insufficient summarization. Each item is distilled from a single program and is not compared with the other programs. Items within the same run therefore contradict each other. On Heilbronn, one principle of EvolveR says "always focusing perturbations on vertices of the current smallest triangle", and another says "do not exclusively perturb points from the current smallest triangles".
  • Repetitive items. In EvolveR, 84% of the pairs of principles from the same generation are judged as synonyms, so each run adds only 5 to 13 different principles to its prompts, and on Heilbronn the three most frequent ones account for 58% to 82% of all additions. In ReasoningBank, the 20 prompts of a generation use 4.9 different records on average.

In contrast, ExpEvolve uses pairwise ranking to ensure the explainability of the extracted factors, which can discover more sufficient factors with certain guarantees. The annotations in ExpEvolve can also be used to avoid repetition.

In addition, the exploitation of experience in [1,2] relies on LLMs’ particular summarization, and the execution is also bottlenecked by LLMs’ own instruction following. In contrast, ExpEvolve compiles idea factors into edit actions of a multi-arm bandit, where a factor that does not help therefore receives fewer slots. When an idea factor is executed, demonstrations will also be provided in ExpEvolve to better enforce the execution.

AuthorsOpenReview ↗

Response to Reviewer C4Hb [2/4]

Empirical comparison. To compare the empirical effectiveness between ExpEvolve and [1,2], we follow their official codes and adapt them into the SCS backbone, where each program is now a trajectory for experience or principle extraction by [1,2]. Due to the resource constraints, we consider five tasks:

MethodMax-min ↓Heilbronn ↑Hermite ↓Linprog ↑Pack ↑
SCS12.9808 ± 0.03320.0336 ± 0.00060.3596 ± 0.00502.5516 ± 0.00562.6230 ± 0.0110
ReasoningBank (adapted)12.9613 ± 0.06250.0347 ± 0.00021.9722 ± 1.61342.6078 ± 0.03022.6303 ± 0.0015
EvolveR (adapted)13.0000 ± 0.00000.0351 ± 0.00131.3237 ± 1.62842.5838 ± 0.04052.6296 ± 0.0050
ExpEvolve12.8892 ± 0.00000.0358 ± 0.00070.3509 ± 0.00242.6354 ± 0.00102.6350 ± 0.0017

ExpEvolve obtains the best mean on all five tasks. In addition, we also count the token cost for [1,2]. Shown as below, ExpEvolve uses fewer tokens per run in total than ReasoningBank and EvolveR, but achieves better performances.

MethodMutatorExperience, LLM callsExperience, embedding callsTotal
ReasoningBank (adapted)4.16M0.82M2.76M7.74M
EvolveR (adapted)3.74M0.82M1.39M5.96M
ExpEvolve3.10M1.19M04.29M

W2 Connection between theory and method, and imperfect factors.

Following your suggestion, we incorporate additional theoretical discussions to strengthen the connections between our theory and method, in particular when with imperfect factors:

  • The theoretical results motivate the design principles of ExpEvolve. For example, Thm 3.1 implies the necessity of explicitly identifying factors; Thm 3.3 implies the necessity of sufficient exploration.
  • The guarantee of factor discoveries follows the convergence guarantees in Proposition 2.5 of COAT[3], with assumptions on LLMs’ capabilities in understanding the codes in our case.
  • For the influence of imperfectly identified factors, we develop a new Proposition 3.4 based on our simplified model: Let γ\gamma be the largest gap between the score and the best linear function of the factors, which is nonzero when some relevant ideas are not yet discovered or when the factors are annotated with errors. Proposition 3.4 shows that the same policy with the same number of evaluations, finds a program within ϵ+2(1+d)γ\epsilon + 2(1+\sqrt{d})\gamma of the optimum. Imperfect factors therefore cost precision and not sample efficiency, and the loss grows only linearly with γ\gamma.
  • To verify the effectiveness of ExpEvolve with imperfect factors, we run ExpEvolve with 30% of the annotations flipped at random:
MethodHeilbronn ↑Linprog ↑Pack ↑
SCS0.0336 ± 0.00062.5516 ± 0.00562.6230 ± 0.0110
ExpEvolve0.0358 ± 0.00072.6354 ± 0.00102.6350 ± 0.0017
ExpEvolve, 30% of the annotations flipped0.0359 ± 0.00102.5773 ± 0.02672.6332 ± 0.0019

It can be found that even with noisy annotations, ExpEvolve still preserves the advantages over SCS across the three compared tasks.

AuthorsOpenReview ↗

Response to Reviewer C4Hb [3/4]

W3 & Q2 Dependence on the evaluation budget (Fig. 7), performance at several budgets, and the choice of 200 evaluations. We need to clarify that, in open-ended discovery, the performances naturally depend on the evaluation budget. Without sufficient exploration, the agent may not even be able to explore the underlying design space to obtain sufficiently good results, which is also aligned with our theoretical discussions. We choose 200 as the budget of evaluations to align with the settings in SCS[4]. To address your questions, we further report performance at 40, 80, 120, 160, and 200 programs with the standard deviation over 3 seeds, for all 11 tasks.

TaskMethod40 programs80 programs120 programs160 programs200 programs
Hadamard ↑SCS0.5047 ± 0.01130.6446 ± 0.18660.6494 ± 0.18280.7144 ± 0.15020.8349 ± 0.1008
Hadamard ↑ExpEvolve0.8801 ± 0.03550.9211 ± 0.00000.9259 ± 0.00840.9259 ± 0.00840.9259 ± 0.0084
Pack ↑SCS2.60036 ± 0.037292.60307 ± 0.039202.60423 ± 0.040162.61452 ± 0.025692.62305 ± 0.01100
Pack ↑ExpEvolve2.62275 ± 0.008202.62721 ± 0.005672.63201 ± 0.000902.63499 ± 0.001692.63499 ± 0.00169
Linprog ↑SCS2.52974 ± 0.015792.54272 ± 0.002252.54672 ± 0.006122.55161 ± 0.005602.55161 ± 0.00560
Linprog ↑ExpEvolve2.63043 ± 0.009622.63435 ± 0.002822.63542 ± 0.000982.63542 ± 0.000982.63542 ± 0.00098
SumDiff ↑SCS1.10981 ± 0.000231.10990 ± 0.000091.11387 ± 0.004731.11564 ± 0.004971.11608 ± 0.00510
SumDiff ↑ExpEvolve1.11026 ± 0.001021.11364 ± 0.004701.11948 ± 0.002201.12089 ± 0.000651.12224 ± 0.00073
Heilbronn ↑SCS0.0310 ± 0.00250.0325 ± 0.00030.0326 ± 0.00050.0331 ± 0.00020.0336 ± 0.0006
Heilbronn ↑ExpEvolve0.0315 ± 0.00080.0349 ± 0.00120.0350 ± 0.00140.0354 ± 0.00140.0358 ± 0.0007
Min overlap ↓SCS0.38141 ± 0.000290.38114 ± 0.000170.38108 ± 0.000190.38107 ± 0.000200.38107 ± 0.00020
Min overlap ↓ExpEvolve0.38109 ± 0.000120.38107 ± 0.000100.38101 ± 0.000070.38098 ± 0.000040.38098 ± 0.00004
Kissing ↑SCS564 ± 3582 ± 0582 ± 0582 ± 0582 ± 0
Kissing ↑ExpEvolve578 ± 6582 ± 0582 ± 0582 ± 0582 ± 0
Second autocorr. ↑SCS0.8825 ± 0.00000.8825 ± 0.00000.8825 ± 0.00000.8825 ± 0.00000.8825 ± 0.0000
Second autocorr. ↑ExpEvolve0.8825 ± 0.00000.8825 ± 0.00000.8825 ± 0.00000.8825 ± 0.00000.8825 ± 0.0000
First autocorr. ↓SCS1.5674 ± 0.00561.5626 ± 0.00761.5549 ± 0.01651.5508 ± 0.01131.5508 ± 0.0113
First autocorr. ↓ExpEvolve1.5528 ± 0.01131.5316 ± 0.02331.5217 ± 0.00931.5216 ± 0.00911.5195 ± 0.0055
Max-min ↓SCS14.8410 ± 1.564613.8205 ± 1.421213.0557 ± 0.096512.9808 ± 0.033212.9808 ± 0.0332
Max-min ↓ExpEvolve12.8892 ± 0.000012.8892 ± 0.000012.8892 ± 0.000012.8892 ± 0.000012.8892 ± 0.0000
Hermite ↓SCS1.14201 ± 1.250890.35956 ± 0.005030.35956 ± 0.005030.35956 ± 0.005030.35956 ± 0.00503
Hermite ↓ExpEvolve0.39730 ± 0.069570.35841 ± 0.005030.35738 ± 0.006590.35117 ± 0.002030.35089 ± 0.00238

It can be found that, across different budgets, ExpEvolve performs no worse than SCS, including the first 100 programs. After sufficient exploration, ExpEvolve finally outperforms SCS. Our results in the response to Reviewer 1UYR also show that, even allocating much more evaluation budgets to SCS, SCS may still lag behind ExpEvolve, which again confirms the advantages of ExpEvolve.

Comments on the paper

3 comments

Dear Reviewers,

The authors have posted their responses. Please take a look and respond to the authors.

Best, AC

AuthorsOpenReview ↗

General Response

We thank all reviewers for their time and constructive comments. We have uploaded a revised paper, in which the changes are marked in color. Below, we summarize the main additions and where to find them. The details are given in the individual responses.

New experiments

  • Ablations (Reviewer qwM3). One-component-off ablations of ExpEvolve and SCS with the warm-up instruction on four tasks, SCS with the warm-up instruction on ten tasks, and one-step sampling from a shared archive (Fig. 6(b), Appendix J.1). The warm-up instruction alone does not account for the improvement of ExpEvolve.
  • Sample efficiency (Reviewers qwM3 and C4Hb). The number of evaluations needed to reach the final performance of SCS in all 2020 settings, the same comparison for ExpEvolve without the warm-up instruction, and the performance at 4040 to 200200 programs on all 1111 tasks (Appendix J, Tables 7 to 11). On average, ExpEvolve needs 4545 evaluations where SCS needs 159159, i.e., 3.5×3.5\times fewer.
  • Token cost (Reviewers 1UYR and qwM3). When SCS is continued until it consumes the same number of tokens as ExpEvolve (293293 to 380380 programs), it remains below ExpEvolve with 200200 programs on Hadamard and SumDiff, and is comparable on Heilbronn and Min overlap (Appendix J.2, Table 15). With DeepSeek-v4-pro as the mutator, ExpEvolve uses fewer tokens than SCS on all four tasks (Table 16).
  • Structured-memory baselines (Reviewer C4Hb). ReasoningBank and EvolveR adapted to the SCS backbone on five tasks (Fig. 7(d), Appendix J.4). ExpEvolve obtains the best mean on all five tasks with fewer tokens in total.
  • Robustness (Reviewers C4Hb and qwM3). ExpEvolve with 30%30\% of the annotations flipped at random (Appendix J.5), DeepSeek-v4-pro as the mutator with 33 seeds on four tasks (Fig. 7(c), Appendix J.6), and the variation over seeds on MLS-Bench (Table 26).
  • Analysis of the idea factors (Reviewer qwM3). The types of the discovered idea factors and of the idea factors behind the new best programs, with more example runs (Appendix J.3).

Revisions

  • Theory (Reviewers C4Hb and qwM3). Theorem 3.1 is presented as the motivation of the method, a new proposition covers imperfectly identified idea factors (Sec. 4, Appendix E.4), and the relation to the guarantees of COAT is stated (Sec. 4.1, Appendix H.5).
  • Claims (Reviewer qwM3). "Up to 5.0x" is corrected in the abstract and the introduction, which now report the average reduction in the number of evaluations over all tasks (3.5×3.5\times).
  • Related work (Reviewer C4Hb). ReasoningBank and EvolveR are discussed (Sec. 2, Appendix J.4).
  • Implementation details (Reviewer qwM3). The warm-up instruction, the sampling of the example programs, and the components in which ExpEvolve differs from SCS are described (Appendix H.3, Appendix I.2, Appendix J.1), and all prompts are given in Appendix K.
  • Per-seed results (Reviewer C4Hb). The score of each seed is reported for Table 1 (Tables 5 and 6), and the rerun seed of SCS on Second autocorrelation from our follow-up response is marked in Tables 6 and 8.

We hope that our responses address your concerns, and we are happy to answer any further questions.

Dear Reviewers,

The authors have posted their responses. Please take a look and respond to the authors.

Best, AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.