- 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
- 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.
- 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
- 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.
- 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
- 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?
- Are there tasks other than Circle Packing where RelayEvolve shows a clear improvement over the strongest baseline?
2 comments
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 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.
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.
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.
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.40 per million input/output tokens as the cheap model and GLM-4.7 [4] priced at \0.60/2.20 per million tokens as the strong model across seven independent seeds per method. Following our standard protocol, per-task budgets B were set to the mean cost of 100-generation All-strong runs: \1.0455onE−GraphExtraction,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.
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:
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.