- 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
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.
| Task | State | SCS prompt | ExpEvolve slots |
|---|---|---|---|
| Linprog ↑ | Earlier | 2.5067 ± 0.1757 | 2.6287 ± 0.0059 |
| Linprog ↑ | Later | 2.5723 ± 0.1333 | 2.6277 ± 0.0064 |
| SumDiff ↑ | Earlier | 1.1055 ± 0.0257 | 1.1144 ± 0.0031 |
| SumDiff ↑ | Later | 1.1175 ± 0.0033 | 1.1196 ± 0.0012 |
| Heilbronn ↑ | Earlier | 0.02711 ± 0.00723 | 0.03040 ± 0.00231 |
| Heilbronn ↑ | Later | 0.03055 ± 0.01183 | 0.03625 ± 0.00041 |
| Min overlap ↓ | Earlier | 0.38692 ± 0.01275 | 0.38344 ± 0.00536 |
| Min overlap ↓ | Later | 0.38182 ± 0.00197 | 0.38118 ± 0.00020 |
| First autocorr. ↓ | Earlier | 1.6213 ± 0.1860 | 1.5648 ± 0.0180 |
| First autocorr. ↓ | Later | 1.5673 ± 0.0367 | 1.5519 ± 0.0235 |
| Max-min ↓ | Earlier | 12.942 ± 0.057 | 12.911 ± 0.046 |
| Max-min ↓ | Later | 12.941 ± 0.057 | 12.919 ± 0.052 |
| Hermite ↓ | Earlier | 4.577 ± 3.425 | 1.370 ± 2.401 |
| Hermite ↓ | Later | 5.917 ± 2.366 | 0.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:
| Task | SCS, 10 × 20 | ExpEvolve, 10 × 20 | Fewer evaluations | SCS, 20 × 10 | ExpEvolve, 20 × 10 | Fewer evaluations |
|---|---|---|---|---|---|---|
| Hadamard | 186 | 10 † | 18.6x | 131 | 5 † | 26.2x |
| Pack | 173 | 62 | 2.8x | 143 | 8 † | 17.9x |
| Linprog | 158 | 4 † | 39.5x | 129 | 102 | 1.3x |
| SumDiff | 180 | 81 | 2.2x | 181 | 97 | 1.9x |
| Heilbronn | 199 | 52 | 3.8x | 169 | 27 † | 6.3x |
| Min overlap | 141 | 84 | 1.7x | 144 | 13 † | 11.1x |
| Kissing | – | – | – | 182 | 61 | 3.0x |
| Second autocorr. | – | – | – | 74 | 8 † | 9.3x |
| First autocorr. | 150 | 44 | 3.4x | 153 | 35 | 4.4x |
| Max-min | 154 | 2 † | 77.0x | 195 | 28 † | 7.0x |
| Hermite | 69 | 56 | 1.2x | 141 | 123 | 1.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.
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.
| Setting | SCS | ExpEvolve w/o warm-up instruction | Fewer evaluations |
|---|---|---|---|
| Hadamard, 10 × 20 | 186 | 9 | 20.7x |
| Hadamard, 20 × 10 | 131 | 29 | 4.5x |
| SumDiff, 10 × 20 | 180 | 76 | 2.4x |
| SumDiff, 20 × 10 | 181 | 26 | 7.0x |
| Heilbronn, 10 × 20 | 199 | 74 | 2.7x |
| Heilbronn, 20 × 10 | 169 | 26 | 6.5x |
| Min overlap, 10 × 20 | 141 | 75 | 1.9x |
| Min overlap, 20 × 10 | 144 | 7 | 20.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 factor | Example (task) | Discovered factors | New best programs from idea-guided slots |
|---|---|---|---|
| Search strategy | uses_randomized_greedy_selection (Kissing) | 462 (40%) | 12 |
| Construction | uses_gf27_paley_construction (Hadamard) | 273 (24%) | 4 |
| Implementation detail | precomputed_basis_cache (Hermite) | 183 (16%) | 10 |
| Restatement of task constraints | boundary_margin_constraint (Pack) | 81 (7%) | 4 |
| Computational resource or time | time_limit_and_early_stopping (Pack) | 72 (6%) | 4 |
| Numerical method or library | uses_linear_programming_optimization (Pack) | 70 (6%) | 0 |
| Misc | 12 (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.
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.
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:
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.
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:
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.