acceptodds
Under review as a conference paper at ICLR 2027

Relay, Don’t Route: Adaptive Population Handoff for Cost-Efficient LLM-Driven Evolution

Abstract

Large language model (LLM)-driven evolution has shown promise for program search and algorithm discovery, but relying on strong models throughout long evolutionary runs is costly. A natural alternative is to combine cheap and strong models under a fixed inference budget. However, existing approaches typically allocate models at the level of individual queries or mutation steps, overlooking that evolutionary search is stateful: each generated candidate changes the population from which subsequent mutations are produced. We empirically analyze LLM-driven evolutionary trajectories and find that search progress is strongly front-loaded, early trajectory performance is informative but noisy, and cheap models recover much of the early progress achieved by strong models at lower cost. Motivated by these findings, we propose \model, a training-free framework that shifts budget allocation from individual calls to evolving populations through adaptive population handoff. A cheap model explores multiple trajectories in short blocks allocated by a bandit scheduler. Relay Gain, defined as the marginal improvement of a compact, quality-diverse candidate bank constructed for handoff, serves as the scheduler reward and determines when to hand off. The curated candidates initialize a shared strong model population for refinement. Across four program-evolution benchmarks, \model remains competitive with the strongest baselines despite task-dependent differences in which single model performs best, with its clearest gains on Circle Packing (Square). Our results suggest that in stateful search, budget allocation should be organized around the population, not the individual call.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM-driven evolution, program evolution, cost-efficient inference

Reviews

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

The paper proposes RelayEvolve, a training-free method that uses a cheap LLM to explore multiple search trajectories before handing a selected population to a stronger LLM for refinement. Relay Gain measures improvements in the quality and coverage of the handoff population and guides search allocation and handoff timing. Across four program-evolution benchmarks, the method remains competitive with the evaluated baselines under matched cost budgets, with the clearest gains on Circle Packing

Critical strengths
  1. The population-handoff formulation is a meaningful contribution to cost-aware evolutionary search. A shared objective connects trajectory allocation, handoff timing, and seed selection, providing a coherent mechanism for preserving useful candidates across model stages.
  2. The cost-matched comparisons and targeted ablations provide evidence for the method’s effectiveness, particularly on Circle Packing. Replacing Relay Gain with immediate best-fitness improvement lowers the mean score from 2.5364 to 2.4479, supporting the value of the proposed reward beyond the full-system comparison.
Critical weaknesses
  1. The clearest gains are on Circle Packing, which is also the only task used for the key ablations and the experiments with different models and backends. The gains on the other tasks are smaller, so it remains unclear whether these mechanisms are similarly effective on different types of problems.
  2. The all-cheap baseline reaches the 200-call cap before spending half of its dollar budget, so it cannot continue searching even when more budget is available. It is therefore unclear how much of the relay strategy’s advantage comes from better budget allocation and how much depends on this call limit.
Questions for authors
  1. How does RelayEvolve compare with the all-cheap baseline when both are allowed to spend the same dollar budget, rather than stopping at the 200-call cap?
  2. Are there tasks other than Circle Packing where RelayEvolve shows a clear improvement over the strongest baseline?
2 comments
AuthorsOpenReview ↗

Response to Reviewer ToDV [1/2]

Thank you for recognizing population handoff as a meaningful contribution to cost-aware evolutionary search, and for highlighting how a shared objective connects trajectory allocation, handoff timing, and seed selection. Below we address your Weaknesses and Questions.


[W1 & Q2]: Clear improvements, key ablations, and multi-model validation on additional tasks

Generalization across three new external benchmarks. To evaluate RelayEvolve beyond the original four tasks and increase statistical power, we added three external benchmarks: E-Graph Extraction and Crew Pairing from HeuriGym [1], and Job Shop Scheduling from CO-Bench [2]. Following the same budget protocol as the main paper, we ran nine independent seeds per method with Qwen-3.5-Flash and Qwen-3.5-Plus, selecting programs on development instances and evaluating them on disjoint held-out test instances. As shown in the following table, RelayEvolve achieves the highest held-out mean score on all three benchmarks, significantly outperforming All-cheap (200 gen), All-cheap (same budget without the 200-call cap), LEVI, and Fixed-switch under a two-sided exact task-stratified rank permutation test. Crew Pairing shows the clearest single-task margin over the strongest baseline, where RelayEvolve reaches 0.8152 compared with 0.7896 for All-cheap (same budget) and 0.7498 for All-strong.

MethodE-Graph ExtractionCrew PairingJob Shop Schedulingpp-value
RelayEvolve0.8587 ± 0.03650.8152 ± 0.07920.8017 ± 0.0135—
Fixed-switch0.8393 ± 0.02530.7755 ± 0.09800.7907 ± 0.01650.0314
LEVI0.8335 ± 0.02220.5336 ± 0.39910.7917 ± 0.01710.0131
All-strong0.8523 ± 0.03570.7498 ± 0.07940.7983 ± 0.01460.0720
All-cheap (same budget)0.8342 ± 0.02920.7896 ± 0.09400.7632 ± 0.03580.0062
All-cheap (200 gen)0.8130 ± 0.01470.6589 ± 0.27280.6739 ± 0.21281.67×10−61.67 \times 10^{-6}

Cross-family generalization with GLM-4.7. To test generalization to a distinct model family, we evaluated GLM-4.7-Flash [3] priced at \0.07/0.07/\\0.40 per million input/output tokens as the cheap model and GLM-4.7 [4] priced at \0.60/0.60/\\2.20 per million tokens as the strong model across seven independent seeds per method. Following our standard protocol, per-task budgets BB were set to the mean cost of 100-generation All-strong runs: \1.0455onE−GraphExtraction,1.0455 on E-Graph Extraction, \\1.5875 on Crew Pairing, and \$0.9398 on Job Shop Scheduling. As shown in the following table, RelayEvolve achieves the highest mean on Crew Pairing and Job Shop Scheduling while nearly tying Fixed-switch on E-Graph Extraction within 0.0007, whereas every baseline suffers substantial degradation on at least one task.

MethodE-Graph ExtractionCrew PairingJob Shop Scheduling
RelayEvolve0.8265 ± 0.00670.8244 ± 0.09520.7731 ± 0.0193
Fixed-switch0.8272 ± 0.00570.6732 ± 0.32560.7452 ± 0.0572
LEVI0.7840 ± 0.06330.5948 ± 0.40810.5111 ± 0.3513
All-strong0.7657 ± 0.13780.7772 ± 0.11490.7686 ± 0.0514
All-cheap (200 gen)0.8243 ± 0.01310.4168 ± 0.32690.7444 ± 0.0145

Key reward and curation ablations across new problem types. We also extended our scheduler-reward and curation ablations to all three new benchmarks over nine seeds per method, holding the Grow–Deepen action space, stopping rule, and budgets fixed:

BenchmarkRelayEvolve (Relay Gain)Best-Fitness RewardQuality-Only Curation
Circle Packing (Square)2.5364 ± 0.02182.4479 ± 0.02772.5109 ± 0.0418
E-Graph Extraction0.8587 ± 0.03650.8260 ± 0.03600.8453 ± 0.0267
Crew Pairing0.8152 ± 0.07920.7894 ± 0.14090.8058 ± 0.1170
Job Shop Scheduling0.8017 ± 0.01350.7999 ± 0.02730.8012 ± 0.0155

Across all four benchmarks, set-level Relay Gain consistently outperforms immediate best-fitness reward in mean score while substantially reducing variance on Crew Pairing and Job Shop Scheduling, and full quality–diversity curation provides modest, consistent improvements over quality-only selection on three of four tasks while matching on the fourth.

AuthorsOpenReview ↗

Response to Reviewer ToDV [2/2]

[W2 & Q1]: Comparison with All-cheap under the same dollar budget without the 200-call cap

Matched-dollar comparison without the 200-call cap. To isolate the benefit of cross-model budget allocation from the 200-call cap, we included All-cheap (same budget) without the 200-call cap across all three new benchmarks in the nine-seed Qwen-3.5 evaluation above. Removing the call cap allowed All-cheap (same budget) to run for 323 to 641 generations until exhausting the full dollar budget, substantially improving its scores over All-cheap (200 gen) from 0.8130 to 0.8342 on E-Graph Extraction, from 0.6589 to 0.7896 on Crew Pairing, and from 0.6739 to 0.7632 on Job Shop Scheduling.

Consistent gains over unbounded-call cheap search. Even when All-cheap (same budget) spends the entire dollar budget across hundreds of additional generations, RelayEvolve outperforms it on each benchmark, yielding p=0.0062p = 0.0062 under the two-sided exact task-stratified rank permutation test. This confirms that RelayEvolve's advantage stems from population handoff and strong-model refinement rather than the 200-call cap. We will incorporate these matched-dollar comparisons, multi-task ablations, and GLM-4.7 results into the revised manuscript.


References

[1] Chen, Hongzheng, et al. "HeuriGym: An agentic benchmark for LLM-crafted heuristics in combinatorial optimization." ICLR 2026.

[2] Sun, Weiwei, et al. "Co-bench: Benchmarking language model agents in algorithm search for combinatorial optimization." AAAI 2026.

[3] https://huggingface.co/zai-org/GLM-4.7-Flash

[4] https://huggingface.co/zai-org/GLM-4.7

Reviewer_zHv7OpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes RelayEvolve, a training-free method for splitting a fixed budget between cheap and strong LLMs in program evolution. A 60-run Qwen-3.5-Flash/Plus motivation study reports that the first 20 of 100 generations give 76.3% (cheap) and 79.1% (strong) of total improvement, that early ranks are weakly predictive, and that the cheap model recovers 0.82-1.01x of the strong model's early gain. RelayEvolve runs cheap trajectories in 5-generation blocks scheduled by a Grow-Deepen bandit, rewards blocks by Relay Gain (marginal gain of a quality-diversity bank), and hands 15 submodular-curated seeds to a strong-model population with an 85% budget reserve. On a ShinkaEvolve backend with four tasks, six baselines and three runs, the clearest gain is on Circle Packing (Square).

Critical strengths

The experiment setup is fair and clear.

Critical weaknesses

The biggest concern is that outside one task the method does not clearly beat the baselines, and the motivation gives little reason to expect it would.

Finding 1 measures each bin's share of gain over the initial program; from a seed far from the optimum I would expect early fixes to dominate that ratio for any optimizer, so it says little about the tail where capability matters (Square's target is 2.635; no Table 1 run exceeds 2.5581).

Finding 2 reports that early ranks are a weak signal (pooled ρ = 0.32 at K = 20, −0.226 on TXN), yet cheap trajectories are capped at 20 generations, so every deepen decision is made inside that regime. The paper itself calls several random-allocation and no-stopping gaps in Figure 3(a) comparable to run-to-run variation.

The diversity term embeds code and mutation text, which I doubt separates constructors that differ in a few constants but land in different basins; ShinkaEvolve already has islands, an archive and novelty rejection. Handoff timing, which the paper calls the key question, is also mostly a hyperparameter: the strong reserve is fixed at 85%, cheap generation is 11-13% of spend (Table 6), and the split sweep in Figure 3(d) moves the score more than the allocation and stopping ablations.

Questions for authors

The experiments need more evidence to separate gains from noise.

3 comments
AuthorsOpenReview ↗

Response to Reviewer zHv7 [1/3]

Thank you for acknowledging the clarity and fairness of our experimental setup, and for your detailed comments regarding statistical evidence, trajectory dynamics, and mechanism attribution. Below we address your Weaknesses and Question.


[W1 & Q1]: Evidence separating gains from noise beyond Circle Packing

Generalization across three new external benchmarks. To evaluate RelayEvolve beyond the original four tasks and increase statistical power, we added three external benchmarks: E-Graph Extraction and Crew Pairing from HeuriGym [1], and Job Shop Scheduling from CO-Bench [2]. Following the same budget protocol as the main paper, we ran nine independent seeds per method with Qwen-3.5-Flash and Qwen-3.5-Plus, selecting programs on development instances and evaluating them on disjoint held-out test instances. As shown in the following table, RelayEvolve achieves the highest held-out mean score on all three benchmarks, significantly outperforming All-cheap (200 gen), All-cheap (same budget without the 200-call cap), LEVI, and Fixed-switch under a two-sided exact task-stratified rank permutation test.

MethodE-Graph ExtractionCrew PairingJob Shop Schedulingpp-value
RelayEvolve0.8587 ± 0.03650.8152 ± 0.07920.8017 ± 0.0135—
Fixed-switch0.8393 ± 0.02530.7755 ± 0.09800.7907 ± 0.01650.0314
LEVI0.8335 ± 0.02220.5336 ± 0.39910.7917 ± 0.01710.0131
All-strong0.8523 ± 0.03570.7498 ± 0.07940.7983 ± 0.01460.0720
All-cheap (same budget)0.8342 ± 0.02920.7896 ± 0.09400.7632 ± 0.03580.0062
All-cheap (200 gen)0.8130 ± 0.01470.6589 ± 0.27280.6739 ± 0.21281.67×10−61.67 \times 10^{-6}

Cross-family generalization with GLM-4.7. To test generalization to a distinct model family, we evaluated GLM-4.7-Flash [3] priced at \0.07/0.07/\\0.40 per million input/output tokens as the cheap model and GLM-4.7 [4] priced at \0.60/0.60/\\2.20 per million tokens as the strong model across seven independent seeds per method. Following our standard protocol, per-task budgets BB were set to the mean cost of 100-generation All-strong runs: \1.0455onE−GraphExtraction,1.0455 on E-Graph Extraction, \\1.5875 on Crew Pairing, and \$0.9398 on Job Shop Scheduling. As shown in the following table, RelayEvolve achieves the highest mean on Crew Pairing and Job Shop Scheduling while nearly tying Fixed-switch on E-Graph Extraction within 0.0007, whereas every baseline suffers substantial degradation on at least one task.

MethodE-Graph ExtractionCrew PairingJob Shop Scheduling
RelayEvolve0.8265 ± 0.00670.8244 ± 0.09520.7731 ± 0.0193
Fixed-switch0.8272 ± 0.00570.6732 ± 0.32560.7452 ± 0.0572
LEVI0.7840 ± 0.06330.5948 ± 0.40810.5111 ± 0.3513
All-strong0.7657 ± 0.13780.7772 ± 0.11490.7686 ± 0.0514
All-cheap (200 gen)0.8243 ± 0.01310.4168 ± 0.32690.7444 ± 0.0145

Explaining smaller margins on Prism and TXN Scheduling. In our original Table 1 benchmarks, five of seven methods reached the identical top score of 26.2560 on Prism due to ceiling saturation, while on TXN Scheduling All-cheap (200 gen) already exceeded All-strong in mean score at 3873.89 versus 3721.72, leaving limited refinement headroom for the stronger model. Across unsaturated benchmarks where the strong model provides genuine refinement capability, our nine-seed and seven-seed held-out evaluations clearly separate RelayEvolve's gains from run-to-run noise.

[W2]: Interpretation of Finding 1 and tail capability near the optimum

Absolute tail gaps alongside early gain shares. We agree that starting from a weak seed naturally concentrates relative gain shares early in search, and that model capability matters critically in the tail. In the revision, we will report absolute best-so-far scores and remaining gaps to task reference ceilings alongside relative gain shares in Section 3. Single-model development trajectories across the three new tasks illustrate this tail gap directly:

TaskStrong Minus Cheap at Gen 20Strong Minus Cheap at Gen 100Remaining Gap at Gen 100 (Cheap / Strong)
E-Graph Extraction+0.082+0.0280.064 / 0.036
Crew Pairing+0.080+0.0390.147 / 0.109
Job Shop Scheduling+0.349+0.2540.453 / 0.199
AuthorsOpenReview ↗

Response to Reviewer zHv7 [2/3]

Why tail difficulty motivates cheap-to-strong handoff. Across all three tasks, the strong model finishes closer to the reference ceiling at generation 100. Because strong-model capability is most needed to close this tail gap, spending expensive strong-model calls on early structural improvements that the cheap model recovers at much lower cost could be a waste of budget; reserving strong-model budget for later refinement directly targets the tail, whereas reversing the schedule to Strong-to-Cheap causes a sharp drop in Figure 3c. On Circle Packing (Square), the remaining gap from 2.5581 (versus 2.4769 for All-strong) to the 2.635 reference in Table 1 reflects the shared ShinkaEvolve search backend under that budget rather than a limitation of handoff: when paired with the stronger AdaEvolve backend in Appendix D.5 Figure 8, RelayEvolve reaches 2.6206 under a $0.50 budget.

[W3]: Deepen decisions inside the 20-generation horizon

Allocating exploration through set-level Relay Gain. We agree that the 20-generation trajectory cap places Deepen decisions inside the weak rank-correlation regime identified in Finding 2. Finding 2 measures how poorly a trajectory's current scalar best score predicts its final rank at generation 100. Rather than predicting which single trajectory will win, the scheduler uses Relay Gain to credit each five-generation block for its marginal addition to the shared size-15 handoff bank, rewarding blocks that contribute top-rr quality anchors or complementary coverage even when the global best score remains unchanged.

Multi-task reward ablation against greedy best-fitness. While the three-run allocation and stopping variants in Figure 3a had differences comparable to run-to-run variance, we tested the shared Relay Gain signal with higher statistical power across all three new benchmarks over nine seeds, holding the Grow–Deepen action space, stopping rule, curation stage, and budgets fixed:

BenchmarkRelayEvolve (Relay Gain)Best-Fitness RewardQuality-Only Curation
Circle Packing (Square)2.5364 ± 0.02182.4479 ± 0.02772.5109 ± 0.0418
E-Graph Extraction0.8587 ± 0.03650.8260 ± 0.03600.8453 ± 0.0267
Crew Pairing0.8152 ± 0.07920.7894 ± 0.14090.8058 ± 0.1170
Job Shop Scheduling0.8017 ± 0.01350.7999 ± 0.02730.8012 ± 0.0155

Replacing Relay Gain with immediate best-fitness improvement lowers mean held-out performance across all four benchmarks and substantially increases variance on Crew Pairing and Job Shop Scheduling. These results show that guiding short-block exploration and handoff through a shared population-level reward provides a more reliable signal inside the 20-generation horizon than tracking scalar global-best improvements.

[W4]: Role of code and mutation-text embeddings versus ShinkaEvolve's internal diversity

Cross-trajectory curation versus within-run diversity. ShinkaEvolve's islands, archive, and novelty rejection operate within an ongoing evolutionary run. During the cheap phase, however, RelayEvolve explores up to 20 separate trajectories that do not share an archive. Therefore, offline curation is required at handoff to compress the pooled candidates across trajectories into 15 seeds for the shared strong-model population.

Structural diversity scope and multi-task curation ablation. We agree that AST code and mutation-text embeddings capture algorithmic and structural differences rather than separating constructors that share the same code structure while differing only in numerical constants. In RelayEvolve, this design discourages the 15-seed handoff bank from being dominated by near-identical structural variants from the same trajectory, leaving constant-level and local basin tuning to the downstream strong-model refinement phase at negligible embedding overhead (0.11% of budget in Table 6). Across our four-task curation ablations in the table above, retaining the diversity term consistently yields modest mean gains over Quality-only selection on Circle Packing (2.5364 vs. 2.5109), E-Graph Extraction (0.8587 vs. 0.8453), and Crew Pairing (0.8152 vs. 0.8058) while matching Job Shop Scheduling (0.8017 vs. 0.8012). We will clarify this structural scope and report the multi-task curation ablations in the revised paper.

AuthorsOpenReview ↗

Response to Reviewer zHv7 [3/3]

[W5]: Adaptive handoff timing versus the 85% strong-model budget reserve

Empirical trigger rates under the default reserve. The 85% strong-model reserve defines a nominal 15% cheap-phase budget cap checked between five-generation blocks, while Relative Relay Gain triggers early handoff whenever recent blocks saturate. In Table 6, recorded cheap generation spend averages 11.33% to 13.42% across the four original tasks. Among the nine retained default-reserve runs per task, the stopping logs record adaptive saturation as the handoff trigger in 9/9 Job Shop Scheduling runs, 6/9 Crew Pairing runs, and 2/9 E-Graph Extraction runs. The remaining runs stopped at the nominal 15% cheap-phase budget cap.

Interaction between budget reserve and adaptive stopping. To examine how the reserve cap interacts with adaptive stopping, we swept the strong-model reserve across 70%, 85%, and 95% on Crew Pairing and Job Shop Scheduling over three seeds per setting:

Strong ReserveNominal Cheap CapCrew Pairing MeanJob Shop MeanObserved Handoff Trigger
70%30%0.7710.779Adaptive saturation in 6 of 6 runs (10.1%–20.6% spend)
85%15%0.8170.809Adaptive saturation in majority of runs
95%5%0.7220.780Cheap budget cap in 6 of 6 runs

When the cheap cap is relaxed to 30% under the 70% reserve, all six runs still stop adaptively via Relay Gain saturation well before exhausting the cheap allowance, whereas tightening the reserve to 95% forces premature handoff at the 5% cap and degrades held-out scores. These results show that the macro-level reserve determines the maximum cheap-phase budget, while the online Relay Gain saturation rule can trigger handoff earlier when additional exploration yields diminishing returns. They provide two distinct levels of control over handoff timing. Separately, our main evaluations show that the default RelayEvolve configuration matches or exceeds Fixed-switch across the evaluated tasks under both Qwen-3.5 and GLM-4.7 model families. We will report the stopping-trigger breakdowns and reserve-sweep results in the revised paper.


References
[1] Chen, Hongzheng, et al. "HeuriGym: An agentic benchmark for LLM-crafted heuristics in combinatorial optimization." ICLR 2026.
[2] Sun, Weiwei, et al. "Co-bench: Benchmarking language model agents in algorithm search for combinatorial optimization." AAAI 2026.
[3] https://huggingface.co/zai-org/GLM-4.7-Flash
[4] https://huggingface.co/zai-org/GLM-4.7

Reviewer_8aYuOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the LLM-driven evolutionary search, arguing that because evolution is stateful, the relevant decision is when to hand off a population explored by a cheap model to a stronger one, not which model handles each call. The trajectory analysis supports this framing: progress is heavily front-loaded, early quality rankings are noisy but informative, and cheap models capture a substantial share of early progress at lower cost. Their proposed framework, RELAYEVOLVE, is training-free and combines a Grow–Deepen bandit scheduler over multiple trajectories guided by Relay Gain, followed by greedy submodular selection to curate a compact, diverse seed set for strong-model refinement. Across four program-evolution benchmarks the method remains competitive with baselines, however, benefits are not uniform across cheap/strong model pairs, and identifying when handoff actually pays off is left as future work.

Critical strengths

The method is motivated by trajectory analysis (front-loaded progress, ~76–79% of gains in the first 20 generations; noisy-but-informative early rankings; cheap models capturing substantial early progress).

RELAYEVOLVE requires no training and targets a fixed inference budget, using a Grow–Deepen bandit scheduler plus Relay Gain to allocate exploration and time handoff.

Greedy submodular selection yields a compact, diverse seed set to initialize the strong-model phase, addressing quality–coverage balance directly.

Critical weaknesses

The strongest baseline varies by task, and benefits differ across cheap/strong model pairs, so the advantage is task- and pairing-dependent rather than broadly dominant.

Early rank correlation with final performance is low and only solidifies later, making early allocation decisions inherently noisy.

When a handoff actually pays off is explicitly left as future work, meaning the central scheduling decision is not fully characterized.

Evaluation is confined to four program-evolution benchmarks and a limited set of cheap/strong model pairs, limiting claims about generalization.

Questions for authors

See above

2 comments
AuthorsOpenReview ↗

Response to Reviewer 8aYu [1/2]

Thank you for recognizing our empirical trajectory analysis, our training-free Grow–Deepen scheduling with Relay Gain, and our submodular quality–diversity seed curation. Below we address your Weaknesses and Questions.


[W1 & W4]: Task- and pairing-dependent gains, benchmark breadth, and generalization

Generalization across three new external benchmarks. To evaluate RelayEvolve beyond the original four tasks and increase statistical power, we added three external benchmarks: E-Graph Extraction and Crew Pairing from HeuriGym [1], and Job Shop Scheduling from CO-Bench [2]. Following the same budget protocol as the main paper, we ran nine independent seeds per method with Qwen-3.5-Flash and Qwen-3.5-Plus, selecting programs on development instances and evaluating them on disjoint held-out test instances. As shown in the following table, RelayEvolve achieves the highest held-out mean score on all three benchmarks, significantly outperforming All-cheap (200 gen), All-cheap (same budget without the 200-call cap), LEVI, and Fixed-switch under a two-sided exact task-stratified rank permutation test.

MethodE-Graph ExtractionCrew PairingJob Shop Schedulingpp-value
RelayEvolve0.8587 ± 0.03650.8152 ± 0.07920.8017 ± 0.0135—
Fixed-switch0.8393 ± 0.02530.7755 ± 0.09800.7907 ± 0.01650.0314
LEVI0.8335 ± 0.02220.5336 ± 0.39910.7917 ± 0.01710.0131
All-strong0.8523 ± 0.03570.7498 ± 0.07940.7983 ± 0.01460.0720
All-cheap (same budget)0.8342 ± 0.02920.7896 ± 0.09400.7632 ± 0.03580.0062
All-cheap (200 gen)0.8130 ± 0.01470.6589 ± 0.27280.6739 ± 0.21281.67×10−61.67 \times 10^{-6}

Cross-family generalization with GLM-4.7. To test generalization to a distinct model family, we evaluated GLM-4.7-Flash [3] priced at \0.07/0.07/\\0.40 per million input/output tokens as the cheap model and GLM-4.7 [4] priced at \0.60/0.60/\\2.20 per million tokens as the strong model across seven independent seeds per method. Following our standard protocol, per-task budgets BB were set to the mean cost of 100-generation All-strong runs: \1.0455onE−GraphExtraction,1.0455 on E-Graph Extraction, \\1.5875 on Crew Pairing, and \$0.9398 on Job Shop Scheduling. As shown in the following table, RelayEvolve achieves the highest mean on Crew Pairing and Job Shop Scheduling while nearly tying Fixed-switch on E-Graph Extraction within 0.0007, whereas every baseline suffers substantial degradation on at least one task.

MethodE-Graph ExtractionCrew PairingJob Shop Scheduling
RelayEvolve0.8265 ± 0.00670.8244 ± 0.09520.7731 ± 0.0193
Fixed-switch0.8272 ± 0.00570.6732 ± 0.32560.7452 ± 0.0572
LEVI0.7840 ± 0.06330.5948 ± 0.40810.5111 ± 0.3513
All-strong0.7657 ± 0.13780.7772 ± 0.11490.7686 ± 0.0514
All-cheap (200 gen)0.8243 ± 0.01310.4168 ± 0.32690.7444 ± 0.0145

Robustness when the strongest baseline shifts by task. Across both model families and three evaluated benchmarks, no single baseline is uniformly reliable: under Qwen-3.5, All-strong is competitive on E-Graph Extraction and Job Shop Scheduling but drops to 0.7498 on Crew Pairing, whereas under GLM-4.7, All-strong drops to 0.7657 on E-Graph Extraction and Fixed-switch drops to 0.6732 on Crew Pairing. Without knowing beforehand which single model a task favors, RelayEvolve consistently matches or exceeds the strongest task-specific baseline.

[W2]: Noisy early trajectory rankings and reliability of early allocation decisions

Allocating exploration through set-level Relay Gain. Finding 2 shows that early trajectory rankings provide a noisy basis for committing to a single leader. RelayEvolve therefore maintains candidates across multiple trajectories and evaluates each five-generation block by its contribution to the shared handoff bank. A block earns Relay Gain when it improves the bank's top-rr quality term or quality-weighted coverage, even when the global best score remains unchanged. At handoff, submodular curation selects candidates to initialize a shared strong-model population. Appendix D.3 illustrates the value of retaining multiple candidates: the run's best final Circle Packing solution descended from a cheap-phase candidate ranked ninth by quality. That candidate also belonged to the mandatory top-10 quality anchors, so the example supports population handoff while the controlled curation ablation evaluates the diversity term's additional contribution.

AuthorsOpenReview ↗

Response to Reviewer 8aYu [2/2]

Multi-task reward ablation against greedy best-fitness. To verify empirically that set-level Relay Gain handles noisy early dynamics better than scalar best-fitness rewards, we replaced Relay Gain with immediate best-fitness improvement while holding the Grow–Deepen scheduler, stopping rule, curation stage, and budgets fixed across Circle Packing and all three new benchmarks over nine seeds.

BenchmarkRelay GainBest-Fitness Reward
Circle Packing (Square)2.5364 ± 0.02182.4479 ± 0.0277
E-Graph Extraction0.8587 ± 0.03650.8260 ± 0.0360
Crew Pairing0.8152 ± 0.07920.7894 ± 0.1409
Job Shop Scheduling0.8017 ± 0.01350.7999 ± 0.0273

Across all four benchmarks, Relay Gain consistently achieves higher mean scores than immediate best-fitness reward while substantially reducing variance on Crew Pairing and Job Shop Scheduling. These results provide consistent evidence that population-level marginal rewards offer a more effective signal for guiding early exploration than immediate best-fitness improvement, despite noisy single-trajectory rankings.

[W3]: Characterizing when population handoff pays off

Diagnostic screening criteria for handoff payoff. Instead of leaving this question solely to future work, we combined diagnostics from our original four tasks with a five-task development-set screening study to establish observable conditions for when population handoff pays off.

TaskStrong / Cheap Dev MeanDiagnostic ScreenRelayEvolve Held-Out Outcome
E-Graph Extraction0.964 / 0.953Pass: headroom and strong leadBest held-out mean: 0.8587
Crew Pairing0.891 / 0.879Pass: headroom and moderate gapBest held-out mean: 0.8152
Job Shop Scheduling0.801 / 0.570Pass: headroom and large gapBest held-out mean: 0.8017
Operator Scheduling0.995 / 0.995Saturated early by both modelsCeiling reached without handoff
Polyomino Packing0.557 / 0.519Fail: strong ahead in 1 of 3 seedsNo consistent refinement advantage

Two actionable conditions governing payoff. First, handoff requires unsaturated optimization headroom: when single-model runs rapidly hit the benchmark ceiling, as on Prism where five of seven methods reach 26.2560, stage handoff has minimal room to separate methods. Second, handoff is more likely to yield substantial gains when the strong model exhibits a consistent refinement advantage: when the strong model does not reliably outperform the cheap model, as on TXN Scheduling where All-cheap (200 gen) exceeds All-strong at 3873.89 versus 3721.72 or on Polyomino Packing, reserving budget for strong refinement offers smaller gains, although RelayEvolve still prevents degradation on TXN at 3942.61. Whenever cheap search discovers viable stepping stones and the strong model holds genuine refinement headroom, RelayEvolve delivers clear gains. We will add this diagnostic characterization to the revised paper.


References
[1] Chen, Hongzheng, et al. "HeuriGym: An agentic benchmark for LLM-crafted heuristics in combinatorial optimization." ICLR 2026.
[2] Sun, Weiwei, et al. "Co-bench: Benchmarking language model agents in algorithm search for combinatorial optimization." AAAI 2026.
[3] https://huggingface.co/zai-org/GLM-4.7-Flash
[4] https://huggingface.co/zai-org/GLM-4.7

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Rebuttal

Dear Reviewers, AC, SAC, and PC,

We sincerely appreciate the time and effort you devoted to reviewing our work and your insightful feedback, which has significantly strengthened our paper. Below, we summarize the progress so far.


We are encouraged that the reviewers recognized several key strengths of our work:

  • Principled population-handoff formulation: Framing budget-aware LLM evolution around population handoff rather than isolated call routing is a meaningful contribution, with Relay Gain coherently connecting trajectory allocation, handoff timing, and submodular seed selection. (Reviewer 8aYu, ToDV)
  • Empirical grounding in trajectory dynamics: Our 60-run analysis revealing front-loaded progress, noisy early rankings, and strong early recovery by cheap models motivates multi-trajectory cheap exploration followed by strong-model refinement. (Reviewer 8aYu, zHv7)
  • Fair cost-matched setup and targeted ablations: The fixed-budget protocol across single- and mixed-model baselines is clear and fair, with controlled ablations confirming the value of Relay Gain over best-fitness rewards. (Reviewer zHv7, ToDV)

During the rebuttal phase, we conducted extensive additional experiments and analyses:

  • Generalization on three new external benchmarks: We added E-Graph Extraction and Crew Pairing from HeuriGym and Job Shop Scheduling from CO-Bench on disjoint held-out test sets over nine seeds with Qwen-3.5-Flash and Qwen-3.5-Plus. RelayEvolve achieves the highest mean on all three tasks, significantly outperforming All-cheap (200 gen) with p=1.67×10−6p = 1.67 \times 10^{-6}, All-cheap (same budget) with p=0.0062p = 0.0062, LEVI with p=0.0131p = 0.0131, and Fixed-switch with p=0.0314p = 0.0314 under exact task-stratified rank permutation tests. (Reviewer 8aYu, zHv7, ToDV)
  • Cross-family validation with GLM-4.7: Using GLM-4.7-Flash and GLM-4.7 over seven seeds on all three new tasks, RelayEvolve achieves the highest mean on Crew Pairing at 0.8244 versus 0.7772 and on Job Shop Scheduling at 0.7731 versus 0.7686 while nearly tying Fixed-switch on E-Graph Extraction within 0.0007. These results further show that the strongest single-model baseline varies across tasks, while RelayEvolve maintains top-tier performance across the three external benchmarks. (Reviewer 8aYu, zHv7, ToDV)
  • Matched-dollar All-cheap without the 200-call cap: Removing the call cap let All-cheap (same budget) run 323 to 641 generations to exhaust the full dollar budget, yet RelayEvolve still outperforms it on every task with p=0.0062p = 0.0062, confirming our gains do not rely on the call cap. (Reviewer ToDV, 8aYu, zHv7)
  • Multi-task reward and curation ablations: Across nine independent seeds per method on Circle Packing and the three new tasks, Relay Gain achieves higher mean scores than the best-fitness reward on all four benchmarks, while exhibiting lower run-to-run standard deviation on three. Quality–diversity curation also yields modest mean-score improvements over quality-only selection on three of the four tasks, while matching its performance on the fourth. (Reviewer 8aYu, zHv7, ToDV)
  • Diagnostic screening and stopping-trigger analysis: A five-task development-set screening study identifies two factors associated with larger handoff gains: sufficient optimization headroom and a consistent strong-model refinement advantage. Stopping logs and reserve sweeps across 70%, 85%, and 95% confirm the reserve sets a macro cap while Relay Gain saturation triggers early handoff in 9/9 Job Shop and 6/9 Crew Pairing default runs, and in 6/6 runs under a 70% reserve. (Reviewer 8aYu, zHv7)

We also clarified several key points:

  • Robustness to shifting single-model regimes: Since the best single model varies sharply across tasks and model pairs, RelayEvolve provides reliable top-tier performance without prior model selection. (Reviewer 8aYu, zHv7, ToDV)
  • Absolute tail gaps: Strong models finish closer to task ceilings at generation 100 across the new benchmarks, motivating cheap early search to save strong budget for tail refinement. (Reviewer zHv7)
  • Cross-trajectory curation scope: Offline curation compresses up to 20 separate cheap trajectories that do not share ShinkaEvolve's internal archive, with dual-view embeddings acting as a lightweight structural redundancy heuristic while leaving constant tuning to strong refinement. (Reviewer zHv7)

Once again, we sincerely thank all reviewers for their valuable suggestions. We believe that these additional experiments and clarifications substantially strengthen the empirical evidence for RelayEvolve and directly address the reviewers' main concerns regarding generalization, statistical robustness, and mechanism attribution. We sincerely hope the additional evidence will be considered in the final assessment of our submission.

Sincerely,

Authors

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.