Paper deep dive

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

Sichun Luo, Yi Huang, Guanzhi Deng, Haibo Wang, Haochen Luo, Lei Li, Zefa Hu, Junlan Feng, Qi Liu

Year: 2026Venue: arXiv preprintArea: cs.CLType: PreprintEmbeddings: 46

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%

Last extracted: 8/8/2026, 3:35:04 AM

Summary

The paper introduces RelayEvolve, a training-free framework for cost-efficient LLM-driven evolutionary search. It addresses the high cost of using strong Large Language Models (LLMs) throughout long evolutionary runs by proposing an adaptive population handoff strategy. The framework uses a cheap model to explore multiple trajectories in short blocks, guided by a bandit scheduler that optimizes 'Relay Gain'—a metric measuring the marginal improvement of a compact, quality-diverse candidate bank. When exploration saturates, the curated candidates are handed off to a strong model for focused refinement. Empirical results across four benchmarks show RelayEvolve outperforms baselines in 11 of 12 settings, demonstrating that budget allocation should be organized around the evolving population rather than individual model calls.

Entities (10)

RelayEvolve · framework · 98%Relay Gain · metric · 92%Grow-Deepen Bandit Scheduler · algorithm · 90%Relay Bank · data-structure · 90%Circle Packing · benchmark · 88%PRISM · benchmark · 88%Transaction Scheduling · benchmark · 88%qwen-3.5-flash · model · 85%Qwen-3.5-Plus · model · 85%ShinkaEvolve · backend · 80%

Relation Signals (10)

RelayEvolve → uses → Relay Gain

confidence 95% · RelayEvolve first uses a cheap model to explore multiple trajectories in short blocks... The scheduler is guided by Relay Gain

RelayEvolve → employs → Grow-Deepen Bandit Scheduler

confidence 92% · A cheap model explores multiple trajectories in short blocks allocated by a bandit scheduler.

Relay Gain → measures → marginal improvement

confidence 92% · Relay Gain, defined as the marginal improvement of a compact, quality-diverse candidate bank

Qwen-3.5-Flash → is → cheap model

confidence 90% · we independently run a cheap model (Qwen-3.5-Flash...)

Qwen-3.5-Plus → is → strong model

confidence 90% · and a strong model (Qwen-3.5-Plus...)

RelayEvolve → outperforms → competitive baselines

confidence 90% · RelayEvolve achieves the highest mean score in 11 of 12 settings, outperforming competitive baselines.

RelayEvolve → evaluateson → PRISM

confidence 85% · We evaluate RelayEvolve on four program evolution benchmarks... Prism

RelayEvolve → evaluateson → Circle Packing

confidence 85% · We evaluate RelayEvolve on four program evolution benchmarks... Circle Packing

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

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 \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.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

44,578 characters extracted from source content.

Expand or collapse full text

Relay, Don’t Route: Adaptive Population Handoff for Cost-Efficient LLM-Driven Evolution Sichun Luo1, Yi Huang2, Guanzhi Deng3, Haibo Wang4 Haochen Luo1, Lei Li1, Zefa Hu2, Junlan Feng2, Qi Liu1 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 RelayEvolve, 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 benchmarks and three budgets, RelayEvolve 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. Introduction Evolutionary search driven by large language models (LLMs) has emerged as a powerful paradigm for algorithm discovery (Romera-Paredes et al. 2024; Liu et al. 2024) and program optimization (Luo et al. 2026b; Liu et al. 2026a). These methods iteratively generate, evaluate, and refine candidate programs, with LLMs acting as mutation operators guided by fitness feedback. Although strong LLMs enable effective mutation, repair, and refinement, relying on them throughout long evolutionary runs is expensive due to the many sequential calls required. This raises a central question: how should a fixed inference budget be allocated over the course of LLM-driven evolution? Combining cheap and strong models under a fixed inference budget is a natural approach to reduce cost. Prior work has explored cost-aware routing at the request level and model selection within evolutionary search (Ding et al. 2024; Ong et al. 2025; Lange, Imajuku, and Cetin 2026; Ray et al. 2026; Tanveer 2026). However, these approaches primarily optimize model selection for individual calls or mutation decisions, without explicitly considering how candidates are accumulated and transferred across evolutionary phases. This local view overlooks a key property of evolutionary search: model calls are state-coupled, because each proposal changes the population inherited by future calls. Therefore, the key question is not which model should make the next call, but when a cheap search phase has produced a population worth handing off to a stronger model. To understand how inference budgets should be allocated, we analyze LLM-driven evolutionary trajectories and identify three patterns. First, fitness improvement is strongly front-loaded, and breakthrough events are concentrated early in the search. Second, early trajectory quality provides useful but noisy signals, suggesting that it alone is insufficient for reliable allocation. Third, cheap models capture a substantial fraction of the early progress achieved by strong models with much lower cost. These observations motivate population handoff rather than call-level model selection: a cheap model explores multiple trajectories and constructs a compact, quality-diverse candidate bank, which is then handed to a stronger model for focused refinement. In this paper, we propose RelayEvolve, a training-free framework for cost-efficient LLM-driven evolution under a fixed inference budget. RelayEvolve first uses a cheap model to explore multiple trajectories in short blocks, with a Grow–Deepen bandit scheduler allocating search effort across trajectories. The scheduler is guided by Relay Gain, defined as the marginal improvement of an online relay bank that balances solution quality and coverage. When exploration saturates, RelayEvolve curates a compact seed set from the candidate pool using greedy submodular selection. The selected seeds initialize a shared strong model population for focused refinement. In this way, the relay objective connects trajectory allocation, handoff timing, seed selection, and strong model refinement. We evaluate RelayEvolve on four program evolution benchmarks under different budget settings. Our experiments show that RelayEvolve improves the cost–performance trade-off over baseline methods. Our contributions are summarized as follows: • We empirically characterize LLM-driven evolutionary trajectories. We find that progress is strongly front-loaded, early trajectory quality provides useful but noisy signals, and cheap models capture a substantial fraction of early search progress with lower cost. • We introduce RelayEvolve, a training-free population handoff framework that uses Relay Gain to coordinate trajectory allocation and handoff timing. A block-level Grow–Deepen bandit scheduler explores multiple trajectories, while greedy submodular curation selects a compact and complementary seed population for strong model refinement. • Across four program evolution benchmarks and three budget levels, RelayEvolve demonstrates the effectiveness of population handoff, producing improved cost–performance trajectories and achieving the highest mean score in 11 of 12 benchmark–budget settings. Related Work LLM-driven evolutionary search. Large language models have been used as semantic variation operators for prompt, heuristic, and program search (Guo et al. 2024; Ye et al. 2024; Agrawal et al. 2026; Yan et al. 2026; Qu et al. 2026; Luo et al. 2026a). FunSearch paired an LLM with automated evaluation and population-based selection to discover mathematical constructions and algorithms (Romera-Paredes et al. 2024), while AlphaEvolve extended this paradigm to larger codebases and a broader range of scientific and systems problems (Novikov et al. 2025). Subsequent frameworks improve the evolutionary harness through mechanisms such as adaptive parent sampling, novelty rejection, archive management, and reflective mutation (Lange, Imajuku, and Cetin 2026; Assumpção et al. 2025). These works establish increasingly capable search operators and population-management mechanisms. Our focus is instead on how a fixed inference budget should be allocated between cheap and strong models over the course of a stateful evolutionary search. Cost-aware LLM routing and evolutionary search allocation. Cost-aware LLM systems allocate inference across models with different capabilities and costs. FrugalGPT constructs request-level model cascades (Chen, Zaharia, and Zou 2023), while RouteLLM learns to route individual queries between weaker and stronger models (Ong et al. 2025). Multi-model allocation has also been explored within evolutionary search: ShinkaEvolve uses a bandit-based LLM ensemble selector (Lange, Imajuku, and Cetin 2026), AdaptEvolve escalates individual refinement steps according to generation confidence (Ray et al. 2026), and LEVI routes different mutation roles to different model classes (Tanveer 2026). A related line of work allocates computation across search processes rather than models. Hyperband uses successive halving to distribute resources among configurations (Li et al. 2018), while AdaEvolve adaptively allocates computation across evolving populations based on search progress (Cemri et al. 2026). These approaches primarily optimize local decisions: selecting a model for an individual step or allocating additional computation to a search process. In contrast, RelayEvolve optimizes the population transferred between model phases: a cheap model constructs a compact candidate bank, and its marginal set-level improvement jointly guides trajectory allocation, stopping, and the eventual handoff to a shared strong model population. Empirical Motivation We examine how LLM-driven evolutionary search progresses over a fixed horizon of T=100T=100 generations. We consider three tasks: Circle Packing (Square), Transaction Scheduling, and Prism (Liu et al. 2026c). For each task, we independently run a cheap model (Qwen-3.5-Flash (OpenRouter 2026a)) and a strong model (Qwen-3.5-Plus (OpenRouter 2026b)) using the same ShinkaEvolve backend (Lange, Imajuku, and Cetin 2026). We conduct ten independent runs for each combination of model and task, resulting in 60 runs in total. Figure 1: (a) Fraction of each run’s eventual best-so-far fitness improvement contributed by each ten-generation bin. (b) Fraction of breakthrough events occurring in each bin. Bars show means over three tasks and ten independent runs per model. Error bars denote 95% bootstrap confidence intervals. The shaded region marks the first 20 generations. Figure 2: (a) Spearman correlation between cheap model trajectory ranks at generation K and their final ranks at generation 100. Early signals are informative but task-dependent and noisy. (b) Ratio of cheap to strong model improvement over the first 20 generations. Error bars denote 95% bootstrap confidence intervals. Finding 1: Search progress is strongly front-loaded. For each run, we divide the trajectory into ten-generation bins and measure the fraction of total best-so-far improvement contributed by each bin. We also measure the temporal distribution of breakthrough events. As shown in Figure 1(a), the first 20 generations account for 76.3%76.3\% and 79.1%79.1\% of the total improvement achieved by the cheap and strong models, respectively. Figure 1(b) shows that breakthrough events are also concentrated early in the search. Moreover, each run contains a median of only seven breakthroughs, indicating that progress typically occurs through a small number of discrete jumps rather than through steady incremental gains. Finding 2: Early cheap model trajectories are partially predictive but noisy. Within each task, we rank the ten cheap model trajectories by their best-so-far fitness at generation K and compute the Spearman correlation with their rankings at generation T. As shown in Figure 2(a), early trajectory quality provides a weak signal of final performance. The pooled correlation is ρ=0.28ρ=0.28 at K=10K=10 and ρ=0.32ρ=0.32 at K=20K=20, increasing to ρ=0.62ρ=0.62 at K=50K=50. However, the task-level correlations vary substantially and can even be negative at early horizons. Early fitness should therefore be treated as a soft allocation signal rather than as a criterion for committing to a single trajectory. Finding 3: The cheap model captures substantial early progress. We compare the best-so-far improvement achieved by the cheap and strong models during the first 20 generations. As shown in Figure 2(b), the ratio of cheap model to strong model improvement is 0.82×0.82×, 1.01×1.01×, and 0.83×0.83× on Circle Packing, Transaction Scheduling, and Prism, respectively. Although the cheap model does not uniformly match the strong model, it captures a substantial fraction of early progress at lower inference cost. This suggests that strong model calls need not be used uniformly from the beginning of the search. Figure 3: Overview of RelayEvolve. A cheap LLM explores multiple trajectories in short blocks allocated by a Grow–Deepen bandit, whose reward is the Relay Gain of an online quality-diverse bank. Cheap model evolution stops when Relay Gain saturates or its budget is exhausted. RelayEvolve then reruns greedy submodular curation on the full candidate pool and hands the resulting compact seed set to a shared strong LLM population for focused refinement with the remaining budget. Implications for RelayEvolve. These findings motivate a population handoff strategy. The rapid decline in improvement motivates short-block scheduling and adaptive stopping. The instability of early rankings motivates maintaining multiple trajectories rather than committing to one early leader. The substantial early progress achieved by the cheap model motivates reserving strong model budget for later refinement. RelayEvolve therefore evaluates cheap model actions through the marginal improvement of a compact relay bank that balances quality and coverage. This signal determines whether to start a new trajectory or extend an existing one, as well as when to terminate cheap model search. The same objective form is then used to select a complementary seed population for subsequent strong model evolution. Problem Formulation We consider an LLM-driven evolutionary search that maximizes a task-specific fitness function f. At each generation, an LLM mutates a previously evaluated program, and an external evaluator scores the resulting candidate. Let tC_t denote the set of valid programs discovered after t model calls, and let ft∗=maxx∈t⁡f(x)f_t^*= _x _tf(x) denote the best fitness obtained up to that point. We have access to a cheap model mcm_c and a strong model msm_s. Their realized inference costs depend on token usage, but calls to mcm_c are substantially cheaper in expectation. In addition to the monetary inference budget, we impose a maximum number of model calls to account for the computational cost of candidate evaluation. Given a total inference budget B and a call budget N, our objective is maxπ⁡[fT∗]s.t.∑t=1Tct≤B,T≤N, _π\ E[f_T^*] .t. _t=1^Tc_t≤ B, T≤ N, (1) where ctc_t is the realized inference cost of the model called at step t, and π denotes a search policy that governs model usage and resource allocation throughout the evolutionary process. Method Overview of RelayEvolve Figure 3 illustrates RelayEvolve, a training-free framework that allocates a fixed inference budget through adaptive population handoff. Instead of selecting a model independently for each mutation, RelayEvolve first uses a cheap model to explore multiple trajectories in short, fixed-length blocks. After each block, it updates an online relay bank containing a compact set of high-quality and complementary candidates. We define Relay Gain as the marginal improvement of the relay bank. A Grow–Deepen bandit scheduler uses this block-level reward to decide whether to start a new trajectory or extend an existing one. The handoff from cheap model exploration to strong model refinement is triggered either by persistent low Relay Gain or by exhaustion of the cheap model budget. At handoff, RelayEvolve re-optimizes the same relay objective over the complete cheap model candidate pool to construct a compact seed population. The selected seeds initialize a single shared strong model population, which uses the remaining budget for refinement. Thus, the same population-level objective coordinates three decisions: how to allocate cheap model search, when to terminate cheap model exploration, and which candidates to hand off to the strong model. Relay Objective and Relay Gain Cheap model search proceeds in fixed-length blocks, with each block advancing one trajectory for h generations. Before the t-th block, RelayEvolve maintains a set of active trajectories ℐtI_t, a deduplicated candidate pool tC_t containing all candidates discovered so far, and an online relay bank St⊆tS_t _t with |St|≤k|S_t|≤ k. The relay bank is a compact population intended for downstream handoff. To define how a relay bank is evaluated, consider any fixed candidate pool C and a bank S⊆S . Motivated by the quality-diversity principle of maintaining high-performing yet diverse solution sets (Mouret and Clune 2015; Pugh, Soros, and Stanley 2016), we score S according to two complementary properties: the top-r quality of its selected candidates and its diversity coverage of promising regions in C. Top-r quality. Let q(x)∈[0,1]q(x)∈[0,1] denote the task-specific normalized fitness of candidate x, with higher values indicating better solutions. Let q(j)(S)q_(j)(S) be the j-th largest normalized quality in S, with q(j)(S)=0q_(j)(S)=0 for j>|S|j>|S|. We define Qr(S)=1r∑j=1rq(j)(S).Q_r(S)= 1r _j=1^rq_(j)(S). (2) This term rewards banks containing multiple high-quality anchors without requiring every bank slot to contain one of the highest-scoring candidates. Diversity coverage. Each program candidate x is represented using a code embedding ecode(x)e_code(x) and a textual metadata embedding etext(x)e_text(x). We combine the two views through sim⁡(x,x′)=clip(ηcos(ecode(x),ecode(x′))+(1−η)cos(etext(x),etext(x′)),0,1), splitsim(x,x )&=clip (η\, \! (e_code(x),e_code(x ) )\\ &+(1-η)\, \! (e_text(x),e_text(x ) ),0,1 ), split (3) where η∈[0,1]η∈[0,1] controls the contribution of the code view. For a fixed candidate pool C, we define the quality-weighted diversity coverage of bank S as Dq(S)=∑v∈q(v)maxx∈S⁡sim⁡(v,x)∑v∈q(v).D_C^q(S)= _v q(v) _x∈ Ssim(v,x) _v q(v). (4) We set Dq(S)=0D_C^q(S)=0 when ∑v∈q(v)=0 _v q(v)=0, and define the maximum over an empty bank as zero. This facility-location term favors banks that cover the high-quality mass of the candidate pool. Weighting candidates by q(v)q(v) prevents limited bank capacity from being spent primarily on diverse but low-quality outliers. Relay objective. The relay value of S with respect to reference pool C is F(S)=λQr(S)+(1−λ)Dq(S),λ∈[0,1].F_C(S)=λ Q_r(S)+(1-λ)D_C^q(S), λ∈[0,1]. (5) The first term retains high-quality anchors, while the second encourages coverage of complementary high-quality regions. For a fixed reference pool, both terms are monotone submodular, and therefore F_C is also monotone submodular. Online bank update. Suppose block t produces a set XtX_t of valid candidates. We first update the deduplicated reference pool: t+1=Dedup⁡(t∪Xt),C_t+1=Dedup (C_t∪ X_t ), (6) where DedupDedup removes duplicate programs from the pool. Starting from StS_t, we process candidates in XtX_t in generation order. A candidate is added directly if the bank is not full. Otherwise, it replaces the bank element whose removal yields the largest increase in Ft+1F_C_t+1, provided that the replacement strictly improves the objective. The resulting bank is denoted by St+1S_t+1. We define the Relay Gain of block t as gt=Ft+1(St+1)−Ft+1(St)≥0.g_t=F_C_t+1(S_t+1)-F_C_t+1(S_t)≥ 0. (7) Both banks are evaluated against the same updated reference pool t+1C_t+1. This ensures that gtg_t measures improvement of the population available for handoff rather than a change in the underlying reference pool. Relay Gain is therefore a block-level and set-level reward. Unlike immediate best-fitness improvement, it credits a block for adding either higher-quality candidates or candidates that complement the current handoff population. Adaptive Cheap Model Search Grow–Deepen actions. Cheap model search proceeds in blocks of h generations. Each block applies one of two actions: • Grow starts a new trajectory from the common initial program and executes its first block. • Deepen(i)(i) resumes an existing trajectory i for one additional block. Independent model sampling creates variation across Grow trajectories despite their shared initialization. We limit both the total number of active trajectories and the horizon of each trajectory, preventing a single search region from consuming the entire cheap model budget. Because the significance of a fixed absolute gain depends on the current relay bank value, we normalize gtg_t into a bounded relative Relay Gain: ρt=clip⁡(gtmax⁡Ft+1(St),ϵF,0,1), _t=clip ( g_t \F_C_t+1(S_t), _F \,0,1 ), (8) where ϵF>0 _F>0 is a stabilizing floor. We use gtg_t to report absolute bank improvement and ρt _t as the reward for scheduling and adaptive handoff. Grow–Deepen bandit scheduler. We treat Grow as a shared meta-arm and associate one Deepen arm with each active trajectory. Search begins with a small number of independent Grow blocks that initialize the trajectory set and relay bank. Their rewards are excluded from the scheduler history because gains observed while filling an initially empty bank are strongly affected by candidate arrival order. After initialization, a Grow reward updates the shared Grow statistics and provides the initial utility estimate for the new trajectory. A Deepen(i)(i) reward updates only the statistics of trajectory i. Because the utility of a trajectory can change as search progresses, we use a recent-window UCB-style score (Besbes, Gur, and Zeevi 2014). Let na(t)n_a(t) be the number of reward observations associated with action a, and let μ^arecent(t) μ^\,recent_a(t) be the mean of its most recent w rewards. We define Ua(t)=+∞,na(t)=0,μ^arecent(t)+clog⁡(max⁡2,t+1)na(t),na(t)>0,U_a(t)= cases+∞,&n_a(t)=0,\\[5.69054pt] μ^\,recent_a(t)+c \! ( \2,t+1\ )n_a(t),&n_a(t)>0, cases (9) where c controls exploration. At each block, RelayEvolve selects the available action with the largest score. Grow becomes unavailable after the trajectory limit is reached, and Deepen(i)(i) becomes unavailable once trajectory i reaches its horizon. All actions use the same cheap model and block length, so the scheduler does not further normalize rewards by nominal action cost. Realized generation and embedding costs are nevertheless charged to the global inference budget. Adaptive handoff. Relative Relay Gain also determines when cheap model exploration terminates. Let ϵrel _rel be a saturation threshold and p a patience window. We trigger handoff when maxj=t−p+1,…,t⁡ρj<ϵrel. _j=t-p+1,…,t _j< _rel. (10) Thus, handoff is triggered only when every block in the recent window contributes less than the required relative improvement. The cheap phase also terminates if its stage budget BcB_c is exhausted. Population Handoff and Strong Model Refinement The online relay bank provides efficient streaming rewards, but its contents can depend on candidate arrival order. Let τ denote the block at which cheap model exploration terminates. At handoff, RelayEvolve therefore re-optimizes the relay objective over the complete and fixed terminal candidate pool τC_τ. We first obtain an offline seed set by greedy maximization followed by objective-improving single-element swaps: Sg=LocalSearch⁡(GreedySelect⁡(τ,Fτ,k)).S_g=LocalSearch (GreedySelect (C_τ,F_C_τ,k ) ). (11) We also apply the same local search to the terminal online bank: So=LocalSearch⁡(Sτ).S_o=LocalSearch(S_τ). (12) The final handoff population is S∗=arg⁡maxS∈Sg,So⁡Fτ(S).S^*= _S∈\S_g,S_o\F_C_τ(S). (13) The offline initialization removes arrival-order dependence, while the online initialization preserves candidates accumulated under the streaming policy. Because FτF_C_τ is monotone submodular, greedy selection under the cardinality constraint |S|≤k|S|≤ k achieves the standard (1−1/e)(1-1/e) approximation guarantee (Nemhauser, Wolsey, and Fisher 1978). Subsequent objective-improving swaps and the final comparison do not decrease the objective, so S∗S^* preserves this guarantee. After handoff, all candidates in S∗S^* initialize a single shared strong model evolutionary population. They are not assigned separate inference budgets or evolved as independent searches. Instead, the strong model evolutionary process can select seeds or their descendants as parents, allowing discoveries originating from different cheap-model trajectories to interact within a common population. The strong model uses the remaining inference budget, and RelayEvolve returns the best valid program found across both cheap and strong phases. Experiments Method Circle Packing (Square) Circle Packing (Rect) TXN Scheduling Prism Avg Best Avg Best Avg Best Avg Best Budget: 50% All-cheap 2.3214±0.1660_ 0.1660 2.5059 2.2649±0.0936_ 0.0936 2.3471 3873.89±129.43_ 129.43 3984.06 26.2440±0.0110_ 0.0110 26.2560 All-strong 2.4084±0.0237_ 0.0237 2.4347 2.3471±0.0120_ 0.0120 2.3580 3606.28±52.11_ 52.11 3636.36 26.0920±0.2490_ 0.2490 26.2560 Fixed-switch 2.3346±0.2266_ 0.2266 2.4769 2.2681±0.0674_ 0.0674 2.3425 3703.94±36.47_ 36.47 3745.32 26.0110±0.2560_ 0.2560 26.2010 Random 2.3531±0.1001_ 0.1001 2.4637 2.3207±0.0588_ 0.0588 2.3564 3765.18±77.17_ 77.17 3816.79 26.1620±0.0680_ 0.0680 26.2390 Bandit 2.2661±0.0158_ 0.0158 2.2819 2.3293±0.0195_ 0.0195 2.3501 3584.00±147.46_ 147.46 3731.34 26.0580±0.2690_ 0.2690 26.2410 LEVI 2.3627±0.1238_ 0.1238 2.4598 2.2573±0.0380_ 0.0380 2.2977 3697.17±196.03_ 196.03 3831.42 25.5628±0.5708_ 0.5708 26.2218 RelayEvolve 2.4136±0.1228_ 0.1228 2.5364 2.3599±0.0069_ 0.0069 2.3648 3875.09±153.52_ 153.52 4000.00 26.2408±0.0131_ 0.0131 26.2560 Budget: 75% All-cheap 2.3214±0.1660_ 0.1660 2.5059 2.2649±0.0936_ 0.0936 2.3471 3873.89±129.43_ 129.43 3984.06 26.2440±0.0110_ 0.0110 26.2560 All-strong 2.4400±0.0184_ 0.0184 2.4611 2.3471±0.0120_ 0.0120 2.3580 3716.89±147.91_ 147.91 3802.28 26.0930±0.2490_ 0.2490 26.2560 Fixed-switch 2.3662±0.1897_ 0.1897 2.4980 2.2814±0.0597_ 0.0597 2.3502 3708.46±31.92_ 31.92 3745.32 26.1910±0.1130_ 0.1130 26.2560 Random 2.4295±0.0764_ 0.0764 2.5006 2.3227±0.0606_ 0.0606 2.3590 3783.72±59.20_ 59.20 3831.42 26.1950±0.0780_ 0.0780 26.2560 Bandit 2.3504±0.0422_ 0.0422 2.3952 2.3382±0.0233_ 0.0233 2.3540 3606.01±157.82_ 157.82 3773.58 26.1840±0.0910_ 0.0910 26.2410 LEVI 2.4144±0.0415_ 0.0415 2.4598 2.2573±0.0380_ 0.0380 2.2977 3697.17±196.03_ 196.03 3831.42 25.5628±0.5708_ 0.5708 26.2218 RelayEvolve 2.5246±0.0408_ 0.0408 2.5581 2.3616±0.0040_ 0.0040 2.3648 3875.09±153.52_ 153.52 4000.00 26.2484±0.0131_ 0.0131 26.2560 Budget: 100% All-cheap 2.3214±0.1660_ 0.1660 2.5059 2.2649±0.0936_ 0.0936 2.3471 3873.89±129.43_ 129.43 3984.06 26.2440±0.0110_ 0.0110 26.2560 All-strong 2.4453±0.0290_ 0.0290 2.4769 2.3471±0.0120_ 0.0120 2.3580 3721.72±152.27_ 152.27 3816.79 26.1040±0.2580_ 0.2580 26.2560 Fixed-switch 2.3926±0.2108_ 0.2108 2.5349 2.2814±0.0597_ 0.0597 2.3502 3780.98±123.49_ 123.49 3921.57 26.1910±0.1130_ 0.1130 26.2560 Random 2.4558±0.0400_ 0.0400 2.5006 2.3565±0.0030_ 0.0030 2.3590 3818.38±95.06_ 95.06 3906.25 26.2020±0.0820_ 0.0820 26.2560 Bandit 2.4084±0.0817_ 0.0817 2.5006 2.3451±0.0114_ 0.0114 2.3540 3663.03±159.10_ 159.10 3846.15 26.1940±0.0810_ 0.0810 26.2480 LEVI 2.4144±0.0415_ 0.0415 2.4598 2.2573±0.0380_ 0.0380 2.2977 3697.17±196.03_ 196.03 3831.42 25.5628±0.5708_ 0.5708 26.2218 RelayEvolve 2.5364±0.0218_ 0.0218 2.5581 2.3616±0.0040_ 0.0040 2.3648 3942.61±50.29_ 50.29 4000.00 26.2484±0.0131_ 0.0131 26.2560 Table 1: Performance across four program evolution benchmarks. All methods report mean score and standard deviation over three runs. Best denotes the best score achieved. Best results in each budget–benchmark column are bolded. Experimental Setup Similar to prior work (Cemri et al. 2026; Liu et al. 2026b), we evaluate on four algorithm discovery and system optimization tasks: Circle Packing (Square), Circle Packing (Rectangle), TXN Scheduling, and Prism (Liu et al. 2026c). We use Qwen-3.5-Flash as the cheap model mcm_c and Qwen-3.5-Plus as the strong model msm_s. The input/output prices are $0.065/$0.26 per million tokens for Qwen-3.5-Flash and $0.26/$1.56 per million tokens for Qwen-3.5-Plus. Every model call is charged according to its actual input and output token usage. All methods use the same ShinkaEvolve backend (Lange, Imajuku, and Cetin 2026), evaluator, mutation template, population size, and context budget. We report the mean and standard deviation over three independent runs. All methods operate under the same total budget B=βBall-strongB=β\,B_all-strong, where Ball-strongB_all-strong is the measured cost of a standard 100 generation all-strong run on each task and β∈0.5,0.75,1.0β∈\0.5,0.75,1.0\. To control the computational overhead of evolutionary evaluation, we cap each run at N=200N=200 generations, following the generation budget constraint in Eq. (1). A run terminates when it exhausts either its budget or the generation cap. In particular, a full 200 generation cheap run costs less than 0.5Ball-strong0.5\,B_all-strong, so All-cheap results coincide across budget levels. Baseline Methods We compare RelayEvolve against several representative baselines. All-cheap and All-strong use the cheap and strong models, respectively, throughout the entire search. Fixed-switch begins with a fixed cheap model exploration phase and then switches to the strong model for the remainder of the search (Bhan, Nobili, and Langer 2026). Random independently selects between the cheap and strong models at each generation. Bandit treats the two models as arms of a multi-armed bandit and uses the realized improvement in best-so-far fitness as the reward for model selection (Lange, Imajuku, and Cetin 2026). LEVI assigns different mutation roles to different model classes through a predefined role-based routing strategy (Tanveer 2026). We exclude AdaptEvolve (Ray et al. 2026) because its model-selection mechanism requires access to token-level logits, which are unavailable through the online API services used in our experiments. All evaluated methods share the same evolutionary backend and are subject to the same inference cost and model call constraints. Main Results Table 1 summarizes performance across four tasks and three budget levels. RelayEvolve achieves the highest mean score in 11 of the 12 benchmark–budget settings and attains or ties the best single-run score on every benchmark. The only non-best mean occurs on Prism at the lowest budget, where most methods are already near saturation and the gap is negligible. The single-model baselines exhibit complementary strengths: All-strong performs better on Circle Packing, whereas All-cheap is more competitive on TXN Scheduling and Prism. This task dependence makes a single predetermined allocation unreliable. By adapting the handoff to the evolving candidate population, RelayEvolve matches or outperforms the stronger single-model baseline in most settings. It also outperforms Fixed-switch throughout, indicating that the appropriate transition point depends on search progress rather than a fixed schedule. Bandit routing is less consistent, suggesting that immediate call-level fitness improvements can be a myopic signal of a candidate’s downstream value in stateful evolutionary search. Figure 5 illustrates this behavior on two representative tasks. RelayEvolve initially follows the rapid progress of All-cheap, then continues improving after handing the curated population to the strong model. The resulting trajectory supports the central design of RelayEvolve: cheap models are effective for broad early exploration, while strong models provide greater value when refining a compact population of promising and complementary candidates. Figure 4: Ablation studies on Circle Packing (Square) at the 100% budget level. From left to right: (a) relay mechanism (relay-gain allocation and stopping vs. random allocation and no stopping); (b) curation objective (full Q+DQ+D vs. quality-only, diversity-only, and random seeds); (c) model cascade direction; (d) sensitivity to the strong model budget reserve. Bars show means over three runs, and error bars denote standard deviations. Figure 5: Cost–performance comparison on Circle Packing (Rect) and TXN Scheduling. Results are averaged over three independent runs, with shaded regions denoting ±1 standard deviation. The vertical dashed line indicates RelayEvolve’s model handoff point. Ablation Study As shown in Figure 4, we conduct ablations on Circle Packing (Square), where the optimization landscape is sufficiency challenging to reveal the effect of different design choices. Effect of the relay mechanism. We first isolate the contribution of the relay-gain mechanism that jointly controls allocation and stopping decisions. Removing relay-gain based control consistently reduces performance, while replacing Grow/Deepen decisions with random choices or removing relay-based stopping leads to further degradation. These results support our design choice of using a shared marginal reward signal to coordinate online computation allocation and termination. Effect of relay curation. We next ablate the final seed selection objective. The full quality-diversity objective outperforms using only quality, only diversity, or random selection. Quality-only selection tends to concentrate on redundant high-performing regions, while diversity-only selection may preserve low-quality candidates. Combining quality and diversity therefore provides a more reliable trade-off between exploitation and coverage for strong model refinement. Effect of the model cascade. We compare different model usage schedules to study the importance of the cheap-to-strong cascade. Both strong-only and cheap-only evolution are inferior to the adaptive cascade, while reversing the cascade direction causes a substantial performance drop. This confirms that cheap models are more effective for broad early exploration, whereas strong models provide greater value for later refinement of promising regions. Sensitivity to budget split. Finally, we vary the fraction of budget reserved for strong-model evolution. The default split of 0.85 achieves the best performance, while allocating either more or less budget to strong model refinement reduces the final score. This indicates that both candidate discovery and downstream refinement are necessary: insufficient cheap model exploration weakens the relay population, whereas excessive exploration reduces the budget available for strong model refinement. In a nutshell, these ablations show that RelayEvolve’s gains arise from the interaction of relay-based control, quality-diversity curation, and the cheap-to-strong cascade rather than from any single component alone. Conclusion We introduced RelayEvolve, a training-free framework that formulates cost-efficient LLM-driven evolution as a population handoff problem under a fixed inference budget. Motivated by the observations that search progress is front-loaded, early trajectory quality provides an imperfect and noisy signal, and a cheap model captures much of the early progress, RelayEvolve explores multiple trajectories before transferring a compact candidate population to a strong model. Relay Gain measures the marginal improvement of this population and coordinates trajectory allocation, handoff timing, and population selection. The curated relay population then initializes the strong model evolution phase for focused refinement. Across four program evolution benchmarks and three budget levels, RelayEvolve achieves the highest observed mean score in 11 of 12 settings. These results suggest that budget-aware evolutionary search benefits from optimizing the population passed between model phases, rather than only selecting the model for the next call. References Agrawal et al. (2026) Agrawal, L. A.; Tan, S.; Soylu, D.; Ziems, N.; Khare, R.; Opsahl-Ong, K.; Singhvi, A.; Shandilya, H.; Ryan, M. J.; Jiang, M.; Potts, C.; Sen, K.; Dimakis, A.; Stoica, I.; Klein, D.; Zaharia, M.; and Khattab, O. 2026. GEPA: Reflective Prompt Evolution Can Outperform Reinforcement Learning. In The Fourteenth International Conference on Learning Representations. Assumpção et al. (2025) Assumpção, H.; Ferreira, D.; Campos, L.; and Murai, F. 2025. Codeevolve: An open source evolutionary coding agent for algorithm discovery and optimization. arXiv preprint arXiv:2510.14150. Besbes, Gur, and Zeevi (2014) Besbes, O.; Gur, Y.; and Zeevi, A. 2014. Stochastic multi-armed-bandit problem with non-stationary rewards. Advances in neural information processing systems, 27. Bhan, Nobili, and Langer (2026) Bhan, J.; Nobili, N.; and Langer, P. 2026. New Bounds for Zarankiewicz Numbers via Reinforced LLM Evolutionary Search. arXiv preprint arXiv:2605.01120. Cemri et al. (2026) Cemri, M.; Agrawal, S.; Gupta, A.; Liu, S.; Cheng, A.; Mang, Q.; Naren, A.; Erdogan, L. E.; Sen, K.; Zaharia, M.; Dimakis, A.; and Stoica, I. 2026. AdaEvolve: Adaptive LLM Driven Zeroth-Order Optimization. arXiv:2602.20133. Chen, Zaharia, and Zou (2023) Chen, L.; Zaharia, M.; and Zou, J. 2023. Frugalgpt: How to use large language models while reducing cost and improving performance. arXiv preprint arXiv:2305.05176. Ding et al. (2024) Ding, D.; Mallick, A.; Wang, C.; Sim, R.; Mukherjee, S.; Rühle, V.; Lakshmanan, L. V.; and Awadallah, A. H. 2024. Hybrid llm: Cost-efficient and quality-aware query routing. In The Twelfth International Conference on Learning Representations. Guo et al. (2024) Guo, Q.; Wang, R.; Guo, J.; Li, B.; Song, K.; Tan, X.; Liu, G.; Bian, J.; and Yang, Y. 2024. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. In International Conference on Learning Representations, volume 2024, 34133–34156. Lange, Imajuku, and Cetin (2026) Lange, R. T.; Imajuku, Y.; and Cetin, E. 2026. ShinkaEvolve: Towards Open-Ended and Sample-Efficient Program Evolution. In The Fourteenth International Conference on Learning Representations. Li et al. (2018) Li, L.; Jamieson, K.; DeSalvo, G.; Rostamizadeh, A.; and Talwalkar, A. 2018. Hyperband: A novel bandit-based approach to hyperparameter optimization. Journal of machine learning research, 18(185): 1–52. Liu et al. (2026a) Liu, F.; Huang, Y.; Luo, S.; Wang, Y.; Yang, Y.; Li, X.; Hu, Z.; Feng, J.; and Liu, Q. 2026a. Cognitive alpha mining via llm-driven code-based evolution. In Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), 11715–11749. Liu et al. (2024) Liu, F.; Xialiang, T.; Yuan, M.; Lin, X.; Luo, F.; Wang, Z.; Lu, Z.; and Zhang, Q. 2024. Evolution of Heuristics: Towards Efficient Automatic Algorithm Design Using Large Language Model. In International Conference on Machine Learning, 32201–32223. PMLR. Liu et al. (2026b) Liu, S.; Agarwal, S.; Maheswaran, M.; Cemri, M.; Li, Z.; Mang, Q.; Naren, A.; Boneh, E.; Cheng, A.; Pan, M. Z.; Du, A.; Keutzer, K.; Cheung, A.; Dimakis, A. G.; Sen, K.; Zaharia, M.; and Stoica, I. 2026b. EvoX: Meta-Evolution for Automated Discovery. arXiv:2602.23413. Liu et al. (2026c) Liu, S.; Cemri, M.; Agarwal, S.; Krentsel, A.; Naren, A.; Mang, Q.; Li, Z.; Gupta, A.; Maheswaran, M.; Cheng, A.; Pan, M.; Boneh, E.; Ramchandran, K.; Sen, K.; Zaharia, M.; Dimakis, A. G.; and Stoica, I. 2026c. SkyDiscover: A Flexible, Adaptive Framework for AI-Driven Scientific and Algorithmic Discovery. In Proceedings of the ACM Conference on AI and Agentic Systems, CAIS ’26, 1223–1227. New York, NY, USA: Association for Computing Machinery. ISBN 9798400724152. Luo et al. (2026a) Luo, H.; Huang, Y.; Luo, S.; Liu, F.; Li, L.; Hu, Z.; Feng, J.; and Liu, Q. 2026a. Harness-Aware Self-Evolving: Co-Evolving Model Weights, Harness, and Task Solutions. arXiv preprint arXiv:2607.03935. Luo et al. (2026b) Luo, S.; Huang, Y.; Luo, H.; Liu, F.; Deng, G.; Li, L.; Yao, Q.; Hu, Z.; Feng, J.; and Liu, Q. 2026b. SeaEvo: Advancing Algorithm Discovery with Strategy Space Evolution. arXiv preprint arXiv:2604.24372. Mouret and Clune (2015) Mouret, J.-B.; and Clune, J. 2015. Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909. Nemhauser, Wolsey, and Fisher (1978) Nemhauser, G. L.; Wolsey, L. A.; and Fisher, M. L. 1978. An analysis of approximations for maximizing submodular set functions—I. Mathematical programming, 14(1): 265–294. Novikov et al. (2025) Novikov, A.; Vũ, N.; Eisenberger, M.; Dupont, E.; Huang, P.-S.; Wagner, A. Z.; Shirobokov, S.; Kozlovskii, B.; Ruiz, F. J. R.; Mehrabian, A.; Kumar, M. P.; See, A.; Chaudhuri, S.; Holland, G.; Davies, A.; Nowozin, S.; Kohli, P.; and Balog, M. 2025. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv:2506.13131. Ong et al. (2025) Ong, I.; Almahairi, A.; Wu, V.; Chiang, W.-L.; Wu, T.; Gonzalez, J. E.; Kadous, M. W.; and Stoica, I. 2025. RouteLLM: Learning to Route LLMs from Preference Data. In The Thirteenth International Conference on Learning Representations. OpenRouter (2026a) OpenRouter. 2026a. Qwen: Qwen3.5-Flash. https://openrouter.ai/qwen/qwen3.5-flash-20260224. OpenRouter (2026b) OpenRouter. 2026b. Qwen: Qwen3.5-Plus 2026-02-15. https://openrouter.ai/qwen/qwen3.5-plus-20260216. Pugh, Soros, and Stanley (2016) Pugh, J. K.; Soros, L. B.; and Stanley, K. O. 2016. Quality diversity: A new frontier for evolutionary computation. Frontiers in Robotics and AI, 3: 40. Qu et al. (2026) Qu, A.; Zheng, H.; Zhou, Z.; Yan, Y.; Tang, Y.; Ong, S. Y.; Hong, F.; Zhou, K.; Jiang, C.; Kong, M.; et al. 2026. Coral: Towards autonomous multi-agent evolution for open-ended discovery. arXiv preprint arXiv:2604.01658. Ray et al. (2026) Ray, P.; Brahma, P. P.; Liu, Z.; and Barsoum, E. 2026. AdaptEvolve: Improving Efficiency of Evolutionary AI Agents through Adaptive Model Selection. In Findings of the Association for Computational Linguistics: ACL 2026, 40625–40633. Romera-Paredes et al. (2024) Romera-Paredes, B.; Barekatain, M.; Novikov, A.; Balog, M.; Kumar, M. P.; Dupont, E.; Ruiz, F. J. R.; Ellenberg, J. S.; Wang, P.; Fawzi, O.; Kohli, P.; and Fawzi, A. 2024. Mathematical discoveries from program search with large language models. Nature, 625(7995): 468–475. Tanveer (2026) Tanveer, T. 2026. LEVI: Stronger Search Architectures Can Substitute for Larger LLMs in Evolutionary Search. arXiv preprint arXiv:2605.09764. Yan et al. (2026) Yan, M.; Peng, B.; Coleman, B.; Chen, Z.; Xie, Z.; Chen, S.; He, Z.; Sachdeva, N.; Ye, I.; Wang, W.; et al. 2026. Pacevolve: Enabling long-horizon progress-aware consistent evolution. arXiv preprint arXiv:2601.10657. Ye et al. (2024) Ye, H.; Wang, J.; Cao, Z.; Berto, F.; Hua, C.; Kim, H.; Park, J.; and Song, G. 2024. Reevo: Large language models as hyper-heuristics with reflective evolution. Advances in neural information processing systems, 37: 43571–43608.

Instant research discovery