1 cumulative citations
View corpus contextReassigning budget by handing off populations, not individual calls, cuts inference cost while improving search: RelayEvolve uses cheap LLMs to explore and a Relay Gain–guided handoff into strong LLM refinement, outperforming baselines across four program-evolution benchmarks and three budgets.
Relay, Don't Route: Adaptive Population Handoff for Cost-Efficient LLM-Driven Evolution
RelayEvolve adaptively shifts inference budget from cheap to strong LLMs by handing off curated populations rather than routing individual calls, producing better cost–performance on four program-evolution benchmarks and achieving the best mean score in 11 of 12 budget–benchmark settings.
Citation observations
Cumulative provider counts captured on specific dates; providers are never combined.
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 \textit{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 \textbf{\model}, a training-free framework that shifts budget allocation from individual calls to evolving populations through adaptive \textit{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 benchmarks and three budgets, \model achieves the highest mean score in 11 of 12 settings, outperforming competitive baselines. Our results suggest that in stateful search, budget allocation should be organized around the population, not the individual call.
Summary
Main Finding
RelayEvolve — a training-free, population-handoff framework that schedules cheap-model exploration in short blocks and hands off a curated, quality-diverse seed population to a stronger model for refinement — yields substantially better cost–performance trade-offs for LLM-driven evolutionary program search. Across four benchmarks and three budget levels, RelayEvolve attains the highest mean score in 11 of 12 settings, demonstrating that inference-budget allocation should be organized around evolving populations (handoff) rather than individual model calls (routing).
Key Points
- Empirical trajectory patterns motivating the design
- Progress is strongly front-loaded: the first 20 generations contribute ≈76–79% of total best-so-far improvement.
- Breakthroughs are concentrated early and occur in a small number of discrete jumps (median ≈7 breakthroughs per run).
- Early trajectory quality is informative but noisy: Spearman ρ between early (K) and final (T=100) rankings is ≈0.28 at K=10, 0.32 at K=20, and 0.62 at K=50.
- Cheap models recover a large fraction of early gains: cheap/strong improvement ratios over first 20 gens were ≈0.82×, 1.01×, and 0.83× across tasks.
- RelayEvolve design (high level)
- Cheap model explores multiple trajectories in short fixed-length blocks.
- After each block, an online compact relay bank (size ≤ k) is updated and evaluated by Relay Gain.
- A Grow–Deepen bandit scheduler (recent-window UCB) chooses whether to start new trajectories (Grow) or extend existing ones (Deepen).
- Handoff is triggered when recent relative Relay Gain saturates (below threshold) or cheap-model budget exhausts.
- Offline greedy + local-search curation over the terminal candidate pool builds a seed set; a shared strong-model population refines these seeds with remaining budget.
- Relay objective and reward
- Relay value FC(S) = λ * Qr(S) + (1−λ) * Dq_C(S)
- Qr(S): average of top-r normalized qualities in S (encourages multiple high-quality anchors).
- Dq_C(S): quality-weighted facility-location coverage of pool C using combined code/text embeddings (encourages coverage of promising, diverse regions).
- Relay Gain (gt) = marginal increase in FC from a block; normalized to relative gain ρt for scheduling.
- Relay value FC(S) = λ * Qr(S) + (1−λ) * Dq_C(S)
- Practical advantages
- Training-free and model-agnostic (policy coordinates cheap/strong usage without learning a new model).
- Uses set-level, block-level rewards that explicitly credit population-level improvements and diversity, avoiding commitment to noisy early leaders.
- Provable approximation for seed selection: objective is monotone submodular; greedy + local search preserves (1−1/e) approximation guarantee.
Data & Methods
- Tasks and setup
- Four program-evolution / algorithm-discovery benchmarks: Circle Packing (Square and Rectangle variants), Transaction Scheduling (TXN), and Prism.
- Backend evolutionary harness: ShinkaEvolve (fixed population size, mutation templates, evaluator).
- Models and costs
- Cheap model: Qwen-3.5-Flash (mc).
- Strong model: Qwen-3.5-Plus (ms).
- Token prices used in experiments: Qwen-3.5-Flash $0.065 (input) / $0.26 (output) per million tokens; Qwen-3.5-Plus $0.26 / $1.56 per million tokens.
- Budgets and evaluation
- Total inference budget B and call budget N are constrained in experiments; actual token usage charged per call.
- RelayEvolve evaluated under three budget levels across four tasks; reported mean and std (over three runs for main experiments).
- Relatively large-scale trajectory analysis (for the empirical motivation) used 10 independent runs per task/model combination.
- Algorithmic parameters (not exhaustive)
- Cheap-phase blocks of h generations; bank size k; top-r and λ trade off quality vs coverage; Grow–Deepen bandit uses recent-window UCB with exploration parameter c and window w; handoff threshold ϵrel and patience p.
- Seed selection: greedy maximization of FC over the full terminal candidate pool Cτ, followed by local single-element swaps; final seeds S* initialize a single shared strong-model population.
- Main empirical results
- First 20 generations contributed 76.3% (cheap) and 79.1% (strong) of total improvement.
- RelayEvolve achieved the highest mean score in 11/12 benchmark–budget settings versus competitive baselines (including call-level routing and allocation baselines).
- Cheap models frequently capture most early gains at far lower per-call cost, motivating delayed use of strong-model budget for refinement.
Implications for AI Economics
- Budget allocation should be population-aware, not call-aware
- When search is stateful (each call affects the future search state), value accrues at the population level. Economic decisions (which model to execute next) should therefore be replaced or augmented by decisions about when to allocate budget to refine a population discovered cheaply.
- Value of cheap models and multi-tiered pricing
- Cheap LLMs can provide most early marginal value in stateful search tasks, implying substantial cost savings if platforms/operators support staged or relay-style workflows. This supports differentiated pricing tiers and product strategies that explicitly promote staged usage patterns (cheap exploration, paid refinement).
- Product design & platform orchestration
- Platform-level orchestration primitives (block scheduling, relay-bank APIs, bank-evaluation metrics like Relay Gain) would enable customers to get more value per dollar for stateful search and discovery workloads. Marketplaces could surface recommended multi-model workflows.
- Procurement and procurement metrics
- Procurement decisions for model access should consider interaction effects across calls and the marginal value of population refinement. Metrics like Relay Gain (set-level marginal improvement) are more informative for procurement ROI on stateful tasks than per-call accuracy or latency alone.
- Pricing, SLAs, and cost forecasting
- Because cheap-model exploration captures early gains at much lower token cost, SLAs and cost-forecasting models can be adapted to allocate predictable budgets for exploration vs refinement phases (reducing variance in expenditure).
- Broader economic impact
- Relay-style approaches could lower the effective price of tasks that rely on expensive models for iterative search (algorithm discovery, program synthesis, automated design), increasing accessibility and possibly accelerating innovation in such domains.
- Limitations & caution for economic adoption
- Evidence is from program-evolution benchmarks: generalization to other stateful LLM tasks (e.g., dialog systems with long-term memory, multi-step planning) needs evaluation.
- RelayEvolve depends on good embeddings and a suitable relay objective; platform vendors may need to provide well-calibrated embedding services and tooling to realize gains.
- Arrival-order sensitivity is mitigated by offline re-optimization, but real-world streaming workloads with continuous discovery may require different handoff policies.
In short: for LLM-driven, stateful search problems, organizing inference budgets around populations (relay/handoff) and leveraging cheap models for front-loaded exploration yields large cost-efficiency gains. This suggests product, pricing, and orchestration opportunities for model providers and platform designers to enable staged multi-model workflows and new ROI metrics tailored to stateful search.
Assessment
Paper Typeother
Evidence Strengthmedium — The paper provides empirical results across multiple benchmarks and budget settings showing consistent improvements, and it includes trajectory analyses motivating the method; however, experiments are limited to algorithm-discovery/program-evolution tasks, a single family of LLMs (Qwen-3.5 variants), few independent runs for the main comparisons, and no real-world economic outcomes, constraining confidence in broader claims.
Methods Rigormedium — The experimental design is well-motivated and includes multiple tasks, an explicit budget accounting, ablation-style analyses of trajectories, and comparisons to baselines; but it relies on a single backend and model family, uses a small number of independent runs for main reported results (three), and sensitivity to key hyperparameters (e.g., embedding choices, λ, k, block length h) and to different evaluator characteristics is not fully explored.
SampleEvaluation on four program-evolution/algorithm-discovery benchmarks (Circle Packing: Square and Rectangle, Transaction/Txn Scheduling, and Prism). Cheap model: Qwen-3.5-Flash; strong model: Qwen-3.5-Plus. Experiments use a common ShinkaEvolve backend, task-specific fitness evaluators, and fixed mutation templates; token pricing and per-call costs are reported; trajectory analyses used 10 runs per model per task (60 runs) for exploratory analysis, while main benchmark comparisons report means and stds over three independent runs per method across three budget levels.
Themesproductivity innovation
GeneralizabilityBenchmarks are synthetic program-evolution tasks and may not represent broader codebases or real-world software engineering or business workloads., Only one family of LLMs (Qwen-3.5 variants) and one evolutionary backend (ShinkaEvolve) were evaluated; results may differ with other models, architectures, or search harnesses., Sensitivity to hyperparameters (e.g., relay bank size, λ weighting, block length, embedding similarity metric) and evaluator noise is not fully characterized., Cost assumptions (token pricing, latency, evaluator cost) are contextual and may change across providers and deployment scenarios., Limited number of independent runs for main comparisons reduces robustness to variance and stochastic failure modes.
Claims (9)
| Claim | Direction | Outcome | Confidence & Evidence | Details |
|---|---|---|---|---|
| The first 20 generations account for 76.3% of the total best-so-far fitness improvement achieved by the cheap model. Output Quality | positive | Share of total best-so-far fitness improvement achieved during the first 20 generations |
Reading fidelity
high
Study strength
medium
|
n=30
76.3%
|
| The first 20 generations account for 79.1% of the total best-so-far fitness improvement achieved by the strong model. Output Quality | positive | Share of total best-so-far fitness improvement achieved during the first 20 generations |
Reading fidelity
high
Study strength
medium
|
n=30
79.1%
|
| Evolutionary search progress typically occurs through a small number of discrete breakthrough events rather than steady incremental gains. Output Quality | mixed | Number and temporal distribution of breakthrough events during evolutionary search |
Reading fidelity
high
Study strength
medium
|
n=60
median of seven breakthroughs per run
|
| Early cheap-model trajectory quality is informative about final performance but noisy: the pooled Spearman correlation is 0.28 at generation 10, 0.32 at generation 20, and 0.62 at generation 50. Output Quality | mixed | Correlation between early trajectory rankings and final trajectory rankings |
Reading fidelity
high
Study strength
medium
|
n=30
Spearman ρ = 0.28 at K = 10; ρ = 0.32 at K = 20; ρ = 0.62 at K = 50
|
| During the first 20 generations, the cheap model achieves 0.82 times the strong model's improvement on Circle Packing, 1.01 times on Transaction Scheduling, and 0.83 times on Prism. Output Quality | mixed | Best-so-far fitness improvement during the first 20 generations |
Reading fidelity
high
Study strength
medium
|
n=30
0.82×, 1.01×, and 0.83× the strong-model improvement
|
| RelayEvolve achieves the highest mean score in 11 of 12 benchmark–budget settings. Output Quality | positive | Mean benchmark fitness score under fixed inference budgets |
Reading fidelity
high
Study strength
low
|
n=12
11 of 12 settings
|
| RelayEvolve improves the cost–performance trade-off relative to baseline methods under fixed inference budgets. Output Quality | positive | Fitness performance as a function of inference cost |
Reading fidelity
high
Study strength
low
|
n=12
|
| RelayEvolve organizes budget allocation around populations transferred between model phases rather than individual model calls. Task Allocation | positive | Allocation of inference budget across evolutionary search phases |
Reading fidelity
high
Study strength
speculative
|
not reported
|
| The relay objective is monotone submodular, so greedy seed selection under a cardinality constraint achieves the standard (1 − 1/e) approximation guarantee. Other | positive | Approximation quality of relay-bank and seed-set selection |
Reading fidelity
high
Study strength
high
|
(1 − 1/e) approximation guarantee
|