# Evolution or Illusion? Rethinking Evaluation in LLM Evolutionary Search

> Single-point budget evaluations of LLM evolutionary search yield unreliable rankings, as optimal seed-iteration splits and even winner identities invert with budget.

- **Source:** [arXiv](https://arxiv.org/abs/2609.19799)
- **Published:** 2026-09-19
- **Permalink:** https://picx.dev/p/XYy3wt
- **Whiteboard:** https://picx.dev/p/XYy3wt/image

## Summary

## Summary (Overview)

- This paper challenges the common practice of evaluating LLM-driven evolutionary search algorithms at a single budget point (e.g., one seed, fixed iterations), showing that this approach can lead to incorrect conclusions about method performance.
- The authors evaluate three evolutionary search strategies (EvoX, OpenEvolve, AdaEvolve) on five optimization tasks across a full grid of 40 seeds × 200 iterations, using exact order statistics on logged trajectories.
- Key finding: The optimal split between width (number of seeds) and depth (iterations per seed) depends on the strategy, task, and total budget.
- Critical finding: Strategy rankings invert with budget—on one task, the strategy that ranks worst at one seed becomes the best at forty seeds.
- The paper proposes a measurement protocol: report the seeds-by-iterations frontier and optimal split at each budget, rather than a single score.

## Introduction and Theoretical Foundation

### Background
LLM-driven evolutionary search pairs a large language model proposer with an evaluator in an evolutionary loop. Notable examples include:
- **FunSearch** (Romera-Paredes et al., 2024): discovered new mathematical constructions
- **AlphaEvolve** (Novikov et al., 2025): extended to algorithms and hardware kernels
- **OpenEvolve** (Sharma, 2025): open-source engine reproducing the loop

### The Problem
The execution of these methods is determined by two dimensions:
- **Width (k)**: number of independent seeds launched; best result over seeds is kept
- **Depth (t)**: number of iterations each seed runs

The total budget is $B = k \times t$ (proposal budget). Common practice reports a single point (usually one seed, sometimes up to three, for a fixed number of iterations) and ranks methods from that single point. The authors argue this is insufficient, drawing on prior work on the noise of individual runs (Henderson et al., 2018).

### Theoretical Foundation
The paper formalizes the evaluation as follows:

For seed $i$ at depth $t$, the running best is:

$$
M_{i}(t) = \max_{1 \leq s \leq t} f(x_{i,s}).\tag{1}
$$

Launching $k$ seeds and keeping the best gives:

$$
\mathcal{B}_{k}(t) = \max_{1 \leq i \leq k} M_{i}(t),\tag{2}
$$

where the budget is $B = k \cdot t$.

The key insight: since individual runs are noisy, a best-of-$k$ score inherently scales with $k$ (Smith and Winkler, 2006). The paper connects this to the width-versus-depth tradeoff.

## Methodology

### Budget Grid Protocol
From logged trajectories of $n = 40$ seeds, the authors compute for every split $(k, t)$ the expected best score $\mathbb{E}[\mathcal{B}_k(t)]$ over random size-$k$ subsets of the 40 observed seeds. This uses **exact order statistics** on per-seed values $\{M_i(t)\}$, so there is no resampling noise.

Three analytical axes are examined:
1. **Width marginal**: $\mathbb{E}[\mathcal{B}_k(T)]$ against $k$ at full depth $T = 200$
2. **Depth marginal**: $\mathbb{E}[\mathcal{B}_1(t)]$ against $t$ for one seed
3. **Frontier**: For each total budget $B$, the best expected score over all splits with $kt \leq B$, and the split $(k, t)$ that reaches it

### Ranking Reversion Analysis
To quantify how often partial budgets name the wrong order, the authors bootstrap the seeds: for each of 2,000 resamples, they rank strategies by best-of-seeds score at a budget point and at the full budget, recording whether the orders differ. The **reversion probability** is the share of resamples that differ.

### Experimental Setup
- **Engine**: ADRS engine with gpt-5-mini (model, objective, evaluator identical across strategies)
- **Strategies**: OpenEvolve (islands + archive, population 40), EvoX (co-evolving selection rule), AdaEvolve (adaptive variant)
- **Budget**: 8,000 proposals (40 × 200) for equal comparison
- **Tasks**: Three ADRS-Bench system tasks (PRISM scheduler, Cloudcast broadcast planner, transaction scheduling) plus two math tasks (Circle Packing, Heilbronn in appendix)
- **Objective**: Native combined_scores with validity checks; transaction scheduling re-evaluated to remove single-draw noise

## Empirical Validation / Results

### Optimal Split Depends on Strategy, Task, and Budget

**Table 1: Optimal budget split (k, t) with $kt \leq B$ at full and ≈10% budgets**

| Task | Strategy | Full (k,t) | 10% (k,t) |
|------|----------|------------|-----------|
| PRISM | EvoX | (32,60) | (4,196) |
| PRISM | OpenEvolve | (32,171) | (36,22) |
| PRISM | AdaEvolve | (40,136) | (7,115) |
| Cloudcast | EvoX | (40,134) | (6,134) |
| Cloudcast | OpenEvolve | (40,158) | (5,162) |
| Cloudcast | AdaEvolve | (40,83) | (7,114) |
| Txn | EvoX | (40,158) | (4,198) |
| Txn | OpenEvolve | (40,159) | (13,60) |
| Txn | AdaEvolve | (38,40) | (19,40) |

Key patterns:
- **Divergent allocations**: On PRISM at 10% budget, EvoX is best deep and narrow (4 seeds, 196 iterations) while OpenEvolve is best wide and shallow (36 seeds, 22 iterations)
- **Depth saturates early**: AdaEvolve on transaction scheduling peaks at 40 iterations; EvoX on PRISM at 60 iterations. Further depth wastes proposals better spent on seeds

### Ranking Inversion with Budget

**Table 2: Expected best combined_score at one and forty seeds (full depth), with rank in parentheses**

| Task | Strategy | 1 seed | 40 seeds |
|------|----------|--------|----------|
| PRISM | EvoX | 26.254 (2) | 26.256 (2) |
| PRISM | OpenEvolve | 26.240 (3) | 26.256 (2) |
| PRISM | AdaEvolve | 26.285 (1) | 26.788 (1) |
| Cloudcast (×10⁻³) | EvoX | 1.19 (3) | 1.82 (1) |
| Cloudcast (×10⁻³) | OpenEvolve | 1.33 (2) | 1.52 (3) |
| Cloudcast (×10⁻³) | AdaEvolve | 1.50 (1) | 1.59 (2) |
| Txn | EvoX | 4255 (2) | 4386 (3) |
| Txn | OpenEvolve | 4229 (3) | 4973 (2) |
| Txn | AdaEvolve | 4766 (1) | 21277 (1) |

Critical findings:
- **Cloudcast**: EvoX is last at one seed but first at forty seeds; OpenEvolve moves from second to last
- **Transaction scheduling**: EvoX and OpenEvolve swap second and third places
- **PRISM**: Single-seed scores are within 0.03 (near tie) but at forty seeds AdaEvolve leads by 0.53

The ranking reversion probability analysis (Figure 3) shows that small budgets yield unreliable rankings. More depth corrects the order late, while more seeds fix it steadily. On every task, a large part of the budget is needed before the order is reliable.

## Theoretical and Practical Implications

### Theoretical Implications
- **Evaluation methodology matters**: Single-point evaluation can name the wrong winner in LLM evolutionary search, echoing broader concerns about noisy evaluation in ML research
- **Width-depth tradeoff is non-trivial**: The optimal allocation is not universal but depends on strategy characteristics, task properties, and total budget
- **Best-of-k scaling**: The inherent scaling of best-of-$k$ scores with $k$ must be accounted for in comparisons

### Practical Implications
- **Reporting protocol**: Report the seeds-by-iterations frontier and the optimal split at each budget, not a single score
- **Seed count**: Run several seeds, since single-seed rankings are unreliable
- **Depth tuning**: Tune depth per strategy and task rather than fixing iterations by habit
- **Cost efficiency**: All three recommendations follow from replaying logged trajectories, so they cost no extra runs
- **Validator flaws**: More seeds can expose validator exploits (e.g., an AdaEvolve program scoring over 4× any prior result on transaction scheduling, which was a partial-schedule exploit, not a better scheduler)

## Conclusion

The paper concludes that evaluating LLM evolutionary search at one budget point is insufficient. The best split between seeds and iterations, and even which method wins, depends on the strategy, the task, and the total budget.

**Recommended practices:**
1. Report the seeds-by-iterations frontier and the optimal split at each budget
2. Run several seeds, since single-seed rankings are unreliable
3. Tune depth per strategy and task rather than fixing iterations by habit

**Limitations acknowledged:**
- The protocol imposes a higher computational and financial barrier (more LLM API calls per assessment)
- The budget-grid protocol is an offline evaluation tool for post-hoc ranking; predicting the optimal split without first exploring the grid remains an open question

The paper's core message is practical: the field needs rigorous, multi-point evaluation to correctly assess progress in LLM-driven evolutionary search.

---

_Markdown view of https://picx.dev/p/XYy3wt, served by PicX — AI-generated visual whiteboard summaries of research papers._