B UDGET-AWARE LLM D ISCOVERY C ALIBRATED F RONTIER U TILITY
VIA
C OST-
Yansen Zhang1,∗ , Yilu Liu1 , Tianyu Liu2 , Jiamin Chen1 , Xiaokun Zhang1 , Kai Xie3 , Xue Liu2 , Chen Ma1,† , Yiyan Qi3,† 1 City University of Hong Kong 2 Mohamed bin Zayed University of Artificial Intelligence (MBZUAI) 3 International Digital Economy Academy (IDEA) [email protected], [email protected], [email protected]
arXiv:2607.26828v1 [cs.LG] 29 Jul 2026
A BSTRACT Large language models increasingly support scientific and algorithmic discovery through inference-time search over evaluated candidates. Existing adaptive discovery controllers assign credit based only on score progress, even though prompt length, retries, and guidance calls cause search actions to incur different token costs. We prove that cost-blind credit can forfeit all but a vanishing fraction of attainable quality as frontiers multiply and costs diverge. Under a fixed search-side token budget, the controller must decide which frontier is improving and whether its gain justifies the realized cost before the budget is exhausted. We introduce CostAda, a cost-calibrated adaptive controller built around cost-calibrated frontier utility. The utility values frontier progress relative to realized action cost and conditions that credit on the remaining budget. CostAda uses this signal to control local exploration intensity, frontier allocation, and budgeted tactic intervention. Cost and remaining budget therefore shape the search rather than serving only as accounting variables or a stopping rule. CostAda reaches the strongest baseline’s full-budget quality with at most half the budget on twelve of sixteen benchmark–backbone pairs while achieving the strongest mean final quality on all eight benchmarks under GLM-5 and GPT-5.4.
1
I NTRODUCTION
Large language models (LLMs) are increasingly used for scientific and algorithmic discovery through inference-time search, where candidate solutions are generated, evaluated, and refined sequentially. In mathematical optimization, algorithm design, and executable program discovery, deterministic evaluators provide repeatable quality signals for this search (Romera-Paredes et al., 2024; Novikov et al., 2025; Jiang et al., 2026; Cemri et al., 2026; Liu et al., 2026a). Once discovery becomes iterative, outcomes depend not only on model capability but also on how the controller spends its limited resources across competing search directions over time. Existing LLM discovery systems adapt their search strategies to observed progress (Romera-Paredes et al., 2024; Novikov et al., 2025; Jiang et al., 2026; Lange et al., 2025; Cemri et al., 2026; Liu et al., 2026a), yet their controllers still credit each iteration or search action according to score progress alone. As a result, a short refinement, an invalid-code retry, and a long-context step receive comparable credit when they yield comparable score progress, although they consume different shares of a fixed token budget. Under token-based API pricing, this mismatch matters because a single long-context guidance call can cost several times as much as a short refinement. Figure 1 illustrates why score progress alone is insufficient under a fixed token budget. Both actions improve the score by +0.03, but a short refinement costs one reference generation whereas a longcontext step costs six. Progress-only credit values the two actions equally, while cost-calibrated credit values the expensive gain less. Yet the long-context action may justify its six-generation cost * Work done as an intern at International Digital Economy Academy (IDEA). †
Corresponding authors: Chen Ma and Yiyan Qi.
1
Traditional Control
Search Actions
CostAda Control (Ours)
progress-only credit
A: Short refinement score +0.03 cost 1×
cost-calibrated credit
A B
B: Long-context step score +0.03 cost 6×
A B
higher lower
Figure 1: Cost-calibrated credit for equal-gain, unequal-cost actions. A short refinement and a long-context step both improve score by +0.03 but cost 1× and 6× a reference generation. Progressonly control assigns equal credit. Under a fixed budget, CostAda credits the expensive gain less. early in a run if it opens a productive frontier, even though the same action may be too expensive near the horizon. The remaining budget therefore determines both the action’s opportunity cost and the value of preserving resources for later search. Progress-only credit cannot represent this change because it measures neither return per realized cost nor how that return changes as the budget shrinks. Proposition 1 shows that, as frontier count and cost heterogeneity grow, a controller whose credit ignores realized cost can attain only a vanishing fraction of the optimal budgeted objective. Changing how progress is smoothed does not alter this separation under heterogeneous action costs. To address this gap, we introduce CostAda, a cost-calibrated adaptive controller for LLM discovery under explicit search-side token budgets. CostAda replaces progress-only credit with cost-calibrated frontier utility, which combines local frontier progress, global best-so-far improvement, realized action cost, and remaining budget. Because realized cost enters the utility as a divisor, the equal gains in Figure 1 no longer receive equal credit. With ample budget, the utility retains more weight on local development because a promising frontier still has time to reach the global best. As the ledger drains, CostAda shifts credit toward global improvement and penalizes costly steps more strongly. The same long-context step can therefore justify its cost early but receive less credit near the horizon. One principle drives all three control decisions of frontier-based search (Section 4). Local exploration intensity narrows sampling around strong candidates when a frontier returns progress efficiently and broadens the parent and context sets when utility is low. The remaining budget further suppresses expensive exploration near the horizon. Frontier allocation ranks frontiers by global gain per realized cost. Thus, a frontier that improves only against its own weak archive receives little allocation credit, while its exploration bonus shrinks with the remaining ledger. Budgeted tactic intervention purchases a higher-level guide only after local search stops converting budget into progress and the reserve can still support the generations needed to test it. CostAda treats realized action cost and remaining budget as control inputs, not as post-hoc statistics or a stopping rule. Contributions. (1) We formulate LLM discovery under explicit search-side token budgets, where cumulative realized LLM spending induces the search horizon, and prove that cost-blind credit can forfeit the budgeted objective (Proposition 1). (2) We introduce cost-calibrated frontier utility with remaining-budget conditioning as the core credit principle. (3) We instantiate this principle in CostAda, an adaptive controller that coordinates budget-gated local exploration, cost-aware frontier allocation, and budgeted tactic intervention. (4) Our multi-budget protocol shows that CostAda reaches the strongest baseline’s full-budget quality with at most half the budget in twelve of the sixteen benchmark–backbone pairs. Across GLM-5 and GPT-5.4, CostAda also records the strongest mean final quality on each of the eight benchmarks.
2
R ELATED W ORK
LLM-guided evolutionary search. LLM-guided evolutionary search uses an LLM as a semantic proposal operator inside a proposal–evaluation–refinement loop (Liu et al., 2024; Ye et al., 2024; Hemberg et al., 2024). Inference-time search improves LLM outcomes beyond a single generation (Yao et al., 2023; Zhou et al., 2024). Deterministic scoring supports this search paradigm in mathematical discovery, algorithm design, equation discovery, code evolution, metaheuristic generation, and prompt optimization (Romera-Paredes et al., 2024; Novikov et al., 2025; Liu et al., 2024; Ye et al., 2024; van Stein & Bäck, 2025; Shojaee et al., 2025; Hemberg et al., 2024; Assumpção et al., 2025; Lange et al., 2025; Yang et al., 2024; Guo et al., 2024; Fernando et al., 2024; Agrawal et al., 2025). Recent systems also adapt search strategy to observed progress through momentum-style 2
variation, adaptive local/global control, strategy evolution, and multi-agent open-ended discovery (Jiang et al., 2026; Cemri et al., 2026; Liu et al., 2026a; Hu et al., 2025; Qu et al., 2026). Closest to our allocation question, recent work allocates compute across evolutionary search branches with bandit strategies and accelerates program evolution for efficiency (Xing et al., 2026; Yang et al., 2026b). These systems adapt where compute goes, but they still count iterations or samples as comparable units. CostAda instead ranks frontiers by progress per unit of realized cost and lets the remaining budget govern the cost penalty. Budget-aware LLM systems. A parallel line makes budgets part of the decision process rather than only a post-hoc reporting statistic. The idea has classical roots in bandits with knapsacks, where budget-constrained selection concentrates on arms with the highest expected gain per unit cost (Badanidiyuru et al., 2013). Tool-use and multi-agent work expose remaining budget and explicit cost constraints to the agent (Liu et al., 2025; Yang et al., 2026a; Fang et al., 2026). Test-timecompute work studies token-budget-aware reasoning, adaptive token allocation, compute-optimal scaling, and tree-search policies aligned with fixed token budgets (Alomrani et al., 2025; Han et al., 2025; Li et al., 2025; Wen et al., 2025; Agarwal et al., 2025; Wang et al., 2025; Miyamoto et al., 2026). Evaluation-driven scaling for scientific discovery further shows the value of repeated evaluator-grounded generation (Ye et al., 2026). Existing budget-aware LLM methods allocate tokens within a single reasoning trajectory or among one agent’s tool calls. By contrast, CostAda allocates variable-cost actions across a population of competing search frontiers.
3
P ROBLEM F ORMULATION
We formalize this population-level allocation problem over a discrete space of executable candidates P. A deterministic task evaluator assigns each candidate a scalar score F : P → R, where higher is better. When an evaluator returns multiple metrics, or when the benchmark’s native objective is minimized, F denotes the direction-adjusted scalar proxy exposed to the controller. At iteration t, the controller proposes a candidate pt ∈ P, observes its score ft = F (pt ), and maintains the global best-so-far score yt = maxτ ≤t fτ . No other quality feedback enters the controller. The search state at iteration t contains Kt frontiers indexed by k ∈ {1, . . . , Kt }. Each frontier (k) (k) stores a local archive Dt ⊆ P with local best score bt = maxp∈D(k) F (p). At each step, the t controller selects a frontier kt , samples parent/context candidates from it, invokes the search-side LLM to generate a new candidate, evaluates it, and updates both local and global state. The frontier representation separates local progress from improvement in the global best-so-far solution. 3.1
S EARCH B UDGET AND O BJECTIVE
Unlike iteration-limited discovery, our setting defines the effective horizon by cumulative search-side LLM cost. Let B > 0 be the nominal budget for a run. The realized cost of search-side LLM calls at iteration t is ct , excluding deterministic evaluatorP execution (Appendix D). The controller tracks consumption through the cumulative cost Ct = s≤t cs and the remaining-budget ratio ρt = max(0, 1 − Ct /B) ∈ [0, 1]. The remaining-budget ratio decreases from one to zero as spending approaches the nominal budget. For scale-invariant control, the controller uses the normalized step cost c̃t = ct /(c̄ + ϵc ), where c̄ is a fixed reference generation cost within the benchmark family and ϵc > 0 is a stabilizer. Control decisions depend on this normalized cost rather than the raw price. The budgeted discovery objective is to maximize best-so-far quality before the search-side budget is exhausted: max E[yτB ], τB = max{t : Ct ≤ B}, π
where π is the controller policy that selects frontiers, sampling actions, and interventions, and τB is the last iteration whose cumulative cost stays within the budget. The objective is to obtain the strongest solution reachable within the budget-induced horizon, not global optimality over P. During execution, B is a nominal rather than a strictly enforceable limit. The cost of an LLM call is observed only after it returns, so truncating a run exactly at τB would change the action being evaluated. Accordingly, a run completes the first iteration that reaches the boundary, τ̂B = min{t : Ct ≥ B}, issues no further search-side calls, and is evaluated at that crossing. 3
score/update
Frontier Archive
sample
II II Frontier allocation
Context Builder I I Local intensity
prompt
Search-side LLM
ct cost
III
III Tactic intervention
CostAda Controller
candidate
signals
Deterministic Evaluator ft score
Budget/Credit State ct cost, ft score ρt budget; ut , rt credit
cost-calibrated credit; remaining-budget conditioning
Figure 2: The overall architecture of CostAda. The shared discovery loop returns the candidate score and realized LLM cost to the budget/credit state. CostAda uses cost-calibrated frontier utility and remaining-budget conditioning to control local exploration intensity, frontier allocation, and budgeted tactic intervention. Numerals mark each control and its target module.
3.2
FAILURE OF C OST-B LIND C REDIT
Call a controller cost-blind if its action distribution at every iteration depends only on the history of actions and observed scores, never on realized costs. Progress-only credit rules are cost-blind regardless of how the progress signal is smoothed or combined, and there are heterogeneous-cost instances on which this class provably forfeits the budgeted objective. Proposition 1 (Cost-blind control forfeits the budgeted objective) For every κ > 1 and K ≥ 2 there is a K-frontier instance with equal per-step gains, in which one frontier has per-selection search cost c and the others κc, such that as B/c → ∞ every cost-blind controller attains at most 1 1 K + κ (1 + o(1)) OPT in expectation, where OPT is the optimal budgeted objective value on the instance, whereas ranking frontiers by gain per realized cost attains (1 − o(1)) OPT. The proof is in Appendix A. The attainable fraction vanishes as frontiers multiply and action costs diverge, mirroring discovery runs in which short refinements and long-context guidance calls share one ledger. The proposition characterizes cost-blind controllers rather than CostAda itself. This separation motivates the cost-calibrated utility in Section 4, which restores cost-dependent credit and conditions subsequent decisions on the remaining budget.
4
M ETHOD
4.1
OVERVIEW
CostAda organizes three coupled controls around one credit principle. Throughout, cost is the realized search-side expenditure of an individual action, whereas budget is the finite ledger whose remaining balance sets that action’s opportunity cost. CostAda calibrates progress credit by realized action cost and conditions subsequent decisions on the remaining budget. This coupling makes the opportunity cost of each action explicit. A gain worth buying early can be too costly near the horizon. Figure 2 shows the overall architecture of CostAda. The upper loop passes a selected frontier through context construction, candidate generation, and deterministic evaluation. The resulting score and realized LLM cost update the lower budget/credit state, which supplies the three control signals. Frontier allocation chooses the next frontier, local exploration intensity sets its sampling breadth, and budgeted tactic intervention determines when higher-level guidance is worth its cost. Although they act at different points, the controls share one cost-calibrated credit principle. Pre-step control reads ρt−1 and stored credit because the action precedes its realized cost. Post-step credit uses ρt only after the cost is charged. This ordering prevents post-generation information from influencing the action that produced it, while keeping it available for future decisions. 4
4.2
C OST-C ALIBRATED F RONTIER U TILITY
For the candidate produced at iteration t on frontier kt , CostAda measures progress at two levels, a local gain and a global gain: ! (kt ) ft − bt−1 ft − yt−1 (kt ) δt = max , 0 , g = max , 0 , t (kt ) max(|ft |, |yt−1 |, 1) max(|ft |, |bt−1 |, 1) (k )
t where ft is the new candidate score, bt−1 is the local best of the selected frontier, and yt−1 is the global best-so-far score. The symmetric denominator keeps the gain scale stable when a benchmark starts from zero or its scores change sign or pass near zero. Local progress identifies frontiers still developing, while only global progress justifies repeated budget allocation.
The utility weights local and global gain according to the remaining budget. Early in a run, enough budget remains for a productive frontier to challenge the global best. Near the horizon, further work on a locally improving but globally weak frontier carries a greater opportunity cost. The global weight is λt = 1 − ρt , which rises from zero to one as the ledger drains. The credit mixture shifts from local development toward global best-so-far improvement as λt rises. A fresh run credits local progress almost entirely, while a nearly exhausted run credits only global improvement. Realized cost enters through the divisor dt = 1 + λct ϕt , where ϕt = log(1 + c̃t ) and c̃t is the normalized step cost from Section 3. The cost weight λct = max(λt , λmin ) floors λt at a fixed positive λmin , keeping cost penalization active early in a run. The logarithm preserves cost ordering while limiting the influence of rare, very expensive calls. As λct increases, costly low-gain steps receive progressively less utility while cheap steps keep nearly full credit. Combining remaining-budget-conditioned progress with the realized-cost divisor yields the costcalibrated utility (k ) λt gt + (1 − λt )δt t (k ) ut t = . (1) dt The denominator calibrates credit by realized action cost, while λt and λct condition the progress mixture and cost pressure on the remaining budget. Both gains are nonnegative and dt ≥ 1, so the utility is nonnegative and reduces to the plain progress mixture only for a zero-cost step. CostAda (k ) (kt ) (k ) smooths this utility with an exponential moving average Ht t = αHt−1 + (1 − α)ut t , where α ∈ (0, 1) is a fixed smoothing coefficient. The exponential average limits the influence of any (k) (k) single step and remains unchanged for unselected frontiers, Ht = Ht−1 . This statistic controls exploration intensity within a frontier, while allocation uses the reward defined below. 4.3
B UDGET-AWARE C ONTROL
CostAda uses the cost-calibrated frontier utility together with the remaining ledger state to choose future actions at the local, allocation, and intervention levels. Local exploration intensity. Because a newly opened frontier has too little evidence for its utility estimate to govern sampling, CostAda uses a short bootstrap stage before applying utility-controlled intensity. After bootstrap, the controller sets ρ (k ) q t−1 It t = Imin + (Imax − Imin ) · , (kt ) 1 + Ht−1 + ϵH where Imin and Imax are fixed lower and upper bounds on local sampling intensity and ϵH > 0 is a small stabilizer. High recent utility indicates that the selected frontier is producing useful progress per cost, so the controller moves toward lower-intensity refinement around strong candidates. Low recent utility raises intensity, broadening the parent and context set before abandoning the frontier. The multiplier ρt−1 suppresses expensive exploration as the remaining budget shrinks. The local sampler πlocal is a fixed distribution over action modes conditioned on this intensity. The sampled (k ) mode ãt ∼ πlocal (· | It t ) governs how broadly the parent candidate and context set are drawn from (kt ) the frontier archive Dt−1 for the search-side LLM. A broader context set costs more to prompt. 5
Frontier allocation. The allocation layer decides where future budget should be spent. For this purpose, CostAda uses only global gain per realized cost: gt (k ) rt t = . dt The allocation reward measures whether frontier kt advanced the overall best-so-far solution per realized cost. Local gain is excluded because improvement against a weak local archive does not by itself justify further global budget. CostAda maintains a smoothed allocation estimate (k )
(k )
(k )
t Rt t = γRt−1 + (1 − γ)rt t , where γ ∈ (0, 1) is a fixed smoothing coefficient. CostAda selects the next frontier using an upper-confidence allocation rule (Auer et al., 2002): r (k) log Nt kt+1 = arg max Rt + ρt cucb , (k)
nt +1
k
(k)
where cucb is a fixed optimism scale, Nt counts frontier-selection decisions, and nt counts selections of frontier k. The first term exploits frontiers with recent global progress per cost. The second preserves exploration of under-sampled frontiers in proportion to the remaining budget. CostAda explores low-evidence frontiers early in a run. Late in a run, allocation relies on observed global progress per cost rather than spending scarce budget on uncertainty alone. Budgeted tactic intervention. When local sampling and frontier allocation enter a low-yield regime, CostAda gates guide/tactic spending on three binary evidence predicates. The core criterion is It = At ∧ (Pt ∨ Yt ). The affordability predicate At holds when the remaining ledger can pay for the guide/tactic call and the ordinary generations needed to test its tactics. Pt holds after a sustained absence of meaningful global progress, with patience adapting to the remaining budget and the frontier count. Yt holds when low-yield spending accumulates before a long stagnation window forms, providing earlier evidence that local search is unproductive. The complete decision additionally requires that no consolidation window, active tactic batch, or backoff suppression is in effect (Appendix B.4). CostAda schedules a guide/tactic only when local search no longer converts budget into useful progress and the guide will not exhaust the remaining horizon. The intervention mode follows the same cost-aware principle. Before guidance has produced incumbent-level global progress, CostAda favors breakthrough tactics. After such progress appears, CostAda favors refinement tactics that preserve the productive direction. Guide calls stay on the same search-side ledger. Their credit is evaluated over the whole tactic cycle they induce rather than only the guide call. Successful cycles briefly consolidate search around the improving frontier. After an unproductive cycle, the controller requires fresh stagnation or low-yield evidence before another budgeted tactic intervention can proceed. 4.4
OVERALL P ROCEDURE
The controller starts iteration t by reading ρt−1 together with each frontier’s smoothed utility, allocation estimate, and selection count. Frontier allocation first chooses kt . The selected frontier’s smoothed utility determines local exploration intensity, which sets the sampling mode, parent, and context set. If It holds, the controller buys a guide/tactic instead of issuing an ordinary generation. On return, the realized cost enters the ledger and lowers ρt . The evaluator scores the candidate. CostAda then applies Eq. (1) to update the statistics used at the next step. The run ends at the first iteration whose cumulative cost reaches B. The controller constants are fixed within each benchmark family and are not retuned per benchmark. Appendix B gives the bootstrap action, progress predicates, guide-cycle bookkeeping, backoff rule, constants, and Algorithm 1. Appendix B.6 traces the same decisions on the run log used in the case study.
5
E XPERIMENTS
5.1
E XPERIMENTAL S ETUP
Benchmarks. We evaluate on the eight-benchmark suite used by recent SkyDiscover, AdaEvolve, and EvoX studies (Liu et al., 2026b; Cemri et al., 2026; Liu et al., 2026a), spanning geometric packing, 6
Table 1: Final benchmark quality at matched search budgets for GLM-5 and GPT-5.4. Arrows indicate the preferred direction. All strongest entries at the reported precision are bolded, and tied entries are bolded jointly. Human reference values follow prior benchmark reports (Novikov et al., 2025; Cemri et al., 2026; Liu et al., 2026a). Benchmark
Human
AdaEvolve
EvoX
CostAda
Mean ± Std
Best
Mean ± Std
Best
Mean ± Std
Best
Backbone: GLM-5 Circle Packing ↑ Circle Packing Rect ↑ Heilbronn Convex ↑ Heilbronn Triangle ↑ MinMaxDist (n=16, d=2) ↓ MinMaxDist (n=14, d=3) ↓ Third Autocorrelation ↓ Signal Processing ↑
2.6340 2.3640 0.0306 0.0360 12.89 4.17 1.4581 –
2.5617 ± 0.0773 2.2089 ± 0.1635 0.0229 ± 0.0015 0.0303 ± 0.0011 14.06 ± 1.30 4.38 ± 0.08 1.4685 ± 0.0014 0.6022 ± 0.0479
2.6224 2.3495 0.0247 0.0314 13.29 4.31 1.4674 0.6545
2.5717 ± 0.0752 2.1989 ± 0.2563 0.0235 ± 0.0012 0.0220 ± 0.0050 14.17 ± 1.92 4.20 ± 0.03 1.5481 ± 0.1308 0.6592 ± 0.0573
2.6181 2.3540 0.0245 0.0257 13.06 4.17 1.4720 0.7162
2.6306 ± 0.0054 2.3525 ± 0.0081 0.0263 ± 0.0018 0.0314 ± 0.0003 13.11 ± 0.29 4.17 ± 0.00 1.4658 ± 0.0037 0.7054 ± 0.0124
2.6360 2.3572 0.0280 0.0317 12.89 4.17 1.4620 0.7191
Backbone: GPT-5.4 Circle Packing ↑ Circle Packing Rect ↑ Heilbronn Convex ↑ Heilbronn Triangle ↑ MinMaxDist (n=16, d=2) ↓ MinMaxDist (n=14, d=3) ↓ Third Autocorrelation ↓ Signal Processing ↑
2.6340 2.3640 0.0306 0.0360 12.89 4.17 1.4581 –
2.6196 ± 0.0030 2.3148 ± 0.0357 0.0197 ± 0.0020 0.0307 ± 0.0008 13.00 ± 0.00 4.55 ± 0.15 1.5081 ± 0.0069 0.7011 ± 0.0128
2.6216 2.3501 0.0220 0.0314 13.00 4.46 1.5012 0.7107
2.5851 ± 0.0510 2.3474 ± 0.0011 0.0223 ± 0.0031 0.0263 ± 0.0035 13.00 ± 0.00 4.44 ± 0.02 1.4824 ± 0.0042 0.6161 ± 0.0561
2.6215 2.3487 0.0252 0.0304 13.00 4.42 1.4788 0.6808
2.6248 ± 0.0046 2.3577 ± 0.0050 0.0244 ± 0.0008 0.0330 ± 0.0009 12.93 ± 0.06 4.42 ± 0.08 1.4717 ± 0.0074 0.7965 ± 0.0346
2.6280 2.3621 0.0252 0.0337 12.89 4.32 1.4631 0.8268
extremal geometry, additive combinatorics, and executable program optimization. Benchmark definitions and score directions are given in Appendix C. Baselines. We compare CostAda with AdaEvolve (Cemri et al., 2026), the closest progress-aware baseline, and EvoX (Liu et al., 2026a), a strategy-evolution controller from a different design family. AdaEvolve already controls local exploration, frontier allocation, and high-level intervention from progress signals. Neither baseline conditions its decisions on the remaining budget. Within each setting, all methods share the benchmark evaluator, search scaffold, backbone, prices, and budget protocol, so the comparison isolates the controller. Backbones and budgets. We run the main comparisons with GLM-5 (Zeng et al., 2026) and GPT-5.4 (OpenAI, 2026), whose per-token prices differ by about fourfold on input and eightfold on output (OpenRouter, 2026a;b). The price gap motivates different nominal budgets and creates two distinct cost regimes. Appendix D lists the fixed OpenRouter prices and defines the shared cost ledger. Budgets are denominated in the provider-priced cost of input and output tokens rather than in raw token counts. In these dollar units, the nominal limit is B=1 for GLM-5 and B=5 for GPT-5.4. Runs stop under the crossing-completion convention of Section 3, at τ̂B . We allow at most 100 search iterations under either backbone, although many runs reach the budget boundary earlier. To measure early progress, we read the same runs at budget cutoffs q ∈ {0.25, 0.5, 0.75, 1.0}, each at τ̂qB . We repeat each benchmark–method setting three times independently. Metrics. Final quality is B EST S CORE @B UDGET, the best-so-far score yτ̂B at the budget crossing. At each cutoff, we report the benchmark objective, the headline value used in prior work (Liu et al., 2026b; Cemri et al., 2026; Liu et al., 2026a), with the units and score directions shown in Table 1. Because these objectives are not comparable across benchmarks, we record a direction-adjusted normalized score. We use normalized AUC to summarize the best-so-far normalized score over the full budget path and thus credit reaching a given quality level earlier (Appendix H). 5.2
F INAL Q UALITY U NDER E QUAL B UDGETS
Table 1 reports final solution quality at the same nominal budget in benchmark-objective units. Human values are listed for reference only. Because their search-side token budgets are unreported, the budget-matched comparison covers the three adaptive methods. 7
AdaEvolve
EvoX
CostAda
0.90
Normalized score
Normalized score
0.93
0.85 0.80
0.90 0.87 0.84
0.75 0.25
0.50 0.75 Budget fraction (GLM-5)
1.00
0.25
0.50 0.75 1.00 Budget fraction (GPT-5.4)
Figure 3: Quality along the budget path. Mean normalized score over the eight benchmarks at each cutoff, under GLM-5 (left) and GPT-5.4 (right). Points average the per-benchmark means of Appendix H. The panels use independent vertical scales. The dotted line marks the strongest baseline’s value at the full budget, which CostAda exceeds at a quarter of that budget. CostAda attains the strongest mean benchmark-objective value on all eight benchmarks and the strongest or tied single-run value at the reported precision in every setting. The only ties occur on MinMaxDist (n=14, d=3) under GLM-5 at 4.17 and on Heilbronn Convex under GPT-5.4 at 0.0252, both with EvoX. CostAda remains strictly strongest in the corresponding means. The stronger baseline changes across benchmarks. Under GLM-5, AdaEvolve holds the better mean on four benchmarks and EvoX on the other four. Under GPT-5.4, AdaEvolve leads on three and EvoX on four, and the two tie on MinMaxDist (n=16, d=2). CostAda’s mean lead therefore holds against whichever baseline is stronger for each benchmark. The result spans both score directions and all four benchmark families. This breadth shows that cost calibration preserves endpoint quality under matched budgets despite substantial differences in model pricing. Signal Processing gives the clearest separation between CostAda and the baselines. CostAda improves mean B EST S CORE @B UDGET by 7.0% under GLM-5 (0.7054 vs. EvoX 0.6592) and 13.6% under GPT-5.4 (0.7965 vs. AdaEvolve 0.7011). Under GPT-5.4, both baselines remain at 13.00 ± 0.00 on MinMaxDist (n=16, d=2), whereas CostAda reaches 12.93 ± 0.06. CostAda’s strongest single run reaches the human reference value of 12.89. Because the methods share one dollar ledger, CostAda’s endpoint advantage reflects spending allocation rather than a larger budget. Under GLM-5, CostAda also pairs the strongest mean with the smallest cross-run standard deviation on six of the eight benchmarks. On Circle Packing Rect under GLM-5, the two baselines report standard deviations of 0.1635 and 0.2563 against CostAda’s 0.0081. Under progress-only credit, an expensive branch that yields no global improvement can continue to absorb budget because local gain is credited without regard to realized cost. CostAda instead assigns the branch less credit and allocates future budget according to global gain per realized cost. Consistent with this allocation argument, component ablations show that removing cost calibration, remaining-budget conditioning, or intervention gating reduces quality at both budgets on three benchmarks under both backbones (Appendix G). The endpoint comparison establishes final quality, not the budget each controller needs. Section 5.3 measures that requirement. 5.3
Q UALITY U NDER PARTIAL B UDGETS
Final scores do not show how quality accumulates as the budget is spent, so we read the same runs at four cutoffs. Under GLM-5, CostAda leads or ties 30 of the 32 benchmark-objective cells (Appendix E). Under GPT-5.4, CostAda leads 29 of the 32 benchmark-objective cells. At half the budget, CostAda’s mean matches or exceeds the strongest baseline’s full-budget mean on five benchmarks under GLM-5 and seven under GPT-5.4. In total, CostAda reaches the same quality for at most half the search-side dollar cost on twelve of sixteen benchmark–backbone pairs. Figure 3 shows the aggregate pattern. At a quarter of the budget, CostAda averages 0.8753 under GLM-5 and 0.8859 under GPT-5.4. Both scores exceed the strongest baseline’s full-budget averages of 0.8725 and 0.8800. Over the full budget path, CostAda attains the highest normalized AUC on fifteen of the sixteen benchmark–backbone pairs. CostAda averages 0.8626 against the strongest 8
0.65
0.04
0.60 0.55 0.50 0.45 0.0 0.5 1.0 Cumulative cost / B
EvoX
0.03 0.02 0.01 0.00
CostAda
Cumulative cost / B
0.05 Step cost / B
composite score
AdaEvolve
0.70
15 30 45 60 75 Iteration
1.0 0.8 0.6 0.4 0.2 0.0
15 30 45 60 75 Iteration
Figure 4: Objective and cost trajectories for Signal Processing under GLM-5. The left panel plots best-so-far benchmark objective against cumulative realized search-side cost. The middle panel shows realized step cost, and the right panel shows cumulative realized cost, both against iteration. Costs are divided by the nominal budget B, whose boundary is marked by the dotted line at 1. Curves show one run per method at the same nominal budget.
baseline’s 0.8060 under GLM-5 and 0.8851 against 0.8437 under GPT-5.4. Together, the cutoff and AUC results show that CostAda reaches strong solutions early and maintains that advantage from the earliest cutoff through the full budget. The half-budget result also holds under two robustness checks. First, we run CostAda directly at B=0.5 rather than read the midpoint of a full-budget trajectory. These independently budgeted runs beat the strongest baseline mean in all 16 cells (Appendix F). Second, spending at the crossing remains closely matched. Because runs complete the crossing iteration, all three methods exceed the nominal budget by only 1.1–2.5% on average under both backbones (Appendix J). Across both checks, the efficiency gains reflect how CostAda allocates budget along the run rather than where the search stops or how much it spends at the crossing. 5.4
C ASE S TUDY
Aggregate tables do not show how each method spends its budget within a run. Figure 4 provides a single-run comparison on Signal Processing under the same nominal GLM-5 budget. The left panel compares methods by cumulative cost. In the run shown, CostAda surpasses both baselines’ final levels within roughly the first third of the budget and maintains that margin to the boundary. The early lead agrees with the aggregate result in Section 5.3, where CostAda’s quarter-budget mean on this benchmark (0.6210) already exceeds AdaEvolve’s full-budget mean (0.6022). The middle and right panels show that realized step costs vary several-fold. Consequently, the methods reach the same budget after different numbers of iterations. Appendices I and K provide the corresponding views for every benchmark and backbone, while Appendix B.6 traces the CostAda decisions behind this curve against the logged controller state. In this run, the cost-based view reveals a budget-efficiency difference that an iteration-indexed trajectory would hide.
6
C ONCLUSION
We presented CostAda, a cost-calibrated controller for LLM discovery under explicit search-side token budgets. Our analysis shows that cost-blind credit can be confined to a vanishing fraction of the budgeted objective on heterogeneous-cost instances. CostAda addresses this failure through cost-calibrated frontier utility and remaining-budget conditioning across local exploration, frontier allocation, and budgeted tactic intervention. With at most half the budget, CostAda reaches the strongest baseline’s full-budget quality in twelve of sixteen benchmark–backbone pairs. Across GLM-5 and GPT-5.4, CostAda also achieves the strongest mean final quality on all eight benchmarks. Together, these results show that CostAda improves budget efficiency while preserving final solution quality across two distinct backbone cost regimes. 9
E THICS S TATEMENT The authors affirm that this work adheres to the ICLR Code of Ethics. The study involves no human subjects or sensitive or private data, and all benchmarks are publicly available.
R EPRODUCIBILITY S TATEMENT The main text and appendix provide the proof, implementation details, controller settings, experimental setup, and evaluation procedures. The complete source code and experimental scripts are available at https://github.com/Forrest-Stone/CostAda.
AI U SE S TATEMENT OpenAI Codex was used to polish the language and presentation of this paper.
R EFERENCES Aradhye Agarwal, Ayan Sengupta, and Tanmoy Chakraborty. The art of scaling test-time compute for large language models. arXiv preprint arXiv:2512.02008, 2025. Lakshya A. Agrawal, Shangyin Tan, Dilara Soylu, Noah Ziems, Rishi Khare, Krista Opsahl-Ong, Arnav Singhvi, Herumb Shandilya, Michael J. Ryan, Meng Jiang, Christopher Potts, Koushik Sen, Alexandros G. Dimakis, Ion Stoica, Daniel Klein, Matei Zaharia, and Omar Khattab. GEPA: Reflective prompt evolution can outperform reinforcement learning. arXiv preprint arXiv:2507.19457, 2025. Mohammad Ali Alomrani, Yingxue Zhang, Derek Li, Qianyi Sun, Soumyasundar Pal, Zhanguang Zhang, Yaochen Hu, Rohan Deepak Ajwani, Antonios Valkanas, Raika Karimi, Peng Cheng, Yunzhou Wang, Pengyi Liao, Hanrui Huang, Bin Wang, Jianye Hao, and Mark Coates. Reasoning on a budget: A survey of adaptive and controllable test-time compute in llms. arXiv preprint arXiv:2507.02076, 2025. Henrique Assumpção, Diego Ferreira, Leandro Campos, and Fabricio Murai. CodeEvolve: An open source evolutionary coding agent for algorithm discovery and optimization. arXiv preprint arXiv:2510.14150, 2025. Peter Auer, Nicolò Cesa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47(2–3):235–256, 2002. doi: 10.1023/A:1013689704352. Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins. Bandits with knapsacks. In IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS), 2013. Mert Cemri, Shubham Agrawal, Akshat Gupta, Shu Liu, Audrey Cheng, Qiuyang Mang, Ashwin Naren, Lutfi Eren Erdogan, Koushik Sen, Matei Zaharia, Alex Dimakis, and Ion Stoica. AdaEvolve: Adaptive LLM driven zeroth-order optimization. arXiv preprint arXiv:2602.20133, 2026. Zhengru Fang, Senkang Forest Hu, Zhonghao Chang, Yu Guo, Yihang Tao, Hongyao Liu, Mengzhe Ruan, Jun Huang, and Yuguang Fang. Inference-time budget control for LLM search agents. arXiv preprint arXiv:2605.05701, 2026. Chrisantha Fernando, Dylan Sunil Banarse, Henryk Michalewski, Simon Osindero, and Tim Rocktäschel. Promptbreeder: Self-referential self-improvement via prompt evolution. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 13481–13544, 2024. Erich Friedman. Erich’s Packing Center. Online resource, 2025. URL https://erich-friedman. github.io/packing/. Qingyan Guo, Rui Wang, Junliang Guo, Bei Li, Kaitao Song, Xu Tan, Guoqing Liu, Jiang Bian, and Yujiu Yang. Connecting large language models with evolutionary algorithms yields powerful prompt optimizers. In International Conference on Learning Representations, 2024. 10
Tingxu Han, Zhenting Wang, Chunrong Fang, Shiyu Zhao, Shiqing Ma, and Zhenyu Chen. Tokenbudget-aware LLM reasoning. In Findings of the Association for Computational Linguistics: ACL 2025, pp. 24842–24855, 2025. Erik Hemberg, Stephen Moskal, and Una-May O’Reilly. Evolving code with a large language model. Genetic Programming and Evolvable Machines, 25(2):21, 2024. Shengran Hu, Cong Lu, and Jeff Clune. Automated design of agentic systems. In International Conference on Learning Representations, volume 2025, pp. 21344–21377, 2025. Jiachen Jiang, Tianyu Ding, and Zhihui Zhu. DeltaEvolve: Accelerating scientific discovery through momentum-driven evolution. arXiv preprint arXiv:2602.02919, 2026. Robert Tjarko Lange, Yuki Imajuku, and Edoardo Cetin. ShinkaEvolve: Towards open-ended and sample-efficient program evolution. arXiv preprint arXiv:2509.19349, 2025. Zheng Li, Qingxiu Dong, Jingyuan Ma, Di Zhang, Kai Jia, and Zhifang Sui. SelfBudgeter: Adaptive token allocation for efficient LLM reasoning. arXiv preprint arXiv:2505.11274, 2025. Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 32201–32223, 2024. Shu Liu, Shubham Agarwal, Monishwaran Maheswaran, Mert Cemri, Zhifei Li, Qiuyang Mang, Ashwin Naren, Ethan Boneh, Audrey Cheng, Melissa Z. Pan, Alexander Du, Kurt Keutzer, Alexandros G. Dimakis, Koushik Sen, Matei Zaharia, and Ion Stoica. EvoX: Meta-evolution for automated discovery. arXiv preprint arXiv:2602.23413, 2026a. Shu Liu, Mert Cemri, Shubham Agarwal, Alexander Krentsel, Ashwin Naren, Qiuyang Mang, Zhifei Li, Akshat Gupta, Monishwaran Maheswaran, Audrey Cheng, Melissa Z. Pan, Ethan Boneh, Kannan Ramchandran, Koushik Sen, Matei Zaharia, Alexandros G. Dimakis, and Ion Stoica. SkyDiscover: A flexible, adaptive framework for AI-driven scientific and algorithmic discovery. In Proceedings of the ACM Conference on AI and Agentic Systems, pp. 1223–1227, 2026b. Tengxiao Liu, Zifeng Wang, Jin Miao, I-Hung Hsu, Jun Yan, Jiefeng Chen, Rujun Han, Fangyuan Xu, Yanfei Chen, Ke Jiang, Samira Daruki, Yi Liang, William Yang Wang, Tomas Pfister, and Chen-Yu Lee. Budget-aware tool-use enables effective agent scaling. arXiv preprint arXiv:2511.17006, 2025. Sora Miyamoto, Daisuke Oba, and Naoaki Okazaki. Aligning tree-search policies with fixed token budgets in test-time scaling of LLMs. arXiv preprint arXiv:2602.09574, 2026. Alexander Novikov, Ngân Vu, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131, 2025. OpenAI. Gpt-5.4 thinking system gpt-5-4-thinking-system-card/, 2026.
card.
https://openai.com/index/
OpenRouter. Z.ai: GLM-5 api pricing and benchmarks. https://openrouter.ai/z-ai/glm-5, 2026a. OpenRouter. OpenAI: GPT-5.4 api pricing and benchmarks. https://openrouter.ai/openai/ gpt-5.4, 2026b. Ao Qu, Han Zheng, Zijian Zhou, Yihao Yan, Yihong Tang, Shao Yong Ong, Fenglu Hong, Kaichen Zhou, Chonghe Jiang, Minwei Kong, Jiacheng Zhu, Xuan Jiang, Sirui Li, Cathy Wu, Bryan Kian Hsiang Low, Jinhua Zhao, and Paul Pu Liang. CORAL: Towards autonomous multi-agent evolution for open-ended discovery. arXiv preprint arXiv:2604.01658, 2026. 11
Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M. Pawan Kumar, Emilien Dupont, Francisco J. R. Ruiz, Jordan S. Ellenberg, Pengming Wang, Omar Fawzi, Pushmeet Kohli, and Alhussein Fawzi. Mathematical discoveries from program search with large language models. Nature, 625(7995):468–475, 2024. Klaus F. Roth. On a problem of Heilbronn. Journal of the London Mathematical Society, 26:198–204, 1951. Asankhaya Sharma. OpenEvolve: an open-source evolutionary coding agent. GitHub repository, https://github.com/algorithmicsuperintelligence/openevolve, 2025. Belle A. Shenoi. Introduction to Digital Signal Processing and Filter Design, volume 169. John Wiley & Sons, 2005. Parshin Shojaee, Kazem Meidani, Shashank Gupta, Amir Barati Farimani, and Chandan Reddy. LLMSR: Scientific equation discovery via programming with large language models. In International Conference on Learning Representations, volume 2025, pp. 16054–16085, 2025. Niki van Stein and Thomas Bäck. LLaMEA: A large language model evolutionary algorithm for automatically generating metaheuristics. IEEE Transactions on Evolutionary Computation, 29(2): 331–345, 2025. Carlos Vinuesa del Rio. Generalized Sidon sets. PhD thesis, Universidad Autónoma de Madrid, 2010. Fali Wang, Hui Liu, Zhenwei Dai, Jingying Zeng, Zhiwei Zhang, Zongyu Wu, Chen Luo, Zhen Li, Xianfeng Tang, Qi He, and Suhang Wang. AgentTTS: Large language model agent for test-time compute-optimal scaling strategy in complex tasks. In Advances in Neural Information Processing Systems, volume 38, 2025. Hao Wen, Xinrui Wu, Yi Sun, Feifei Zhang, Liye Chen, Jie Wang, Yunxin Liu, Yunhao Liu, Ya-Qin Zhang, and Yuanchun Li. BudgetThinker: Empowering budget-aware LLM reasoning with control tokens. arXiv preprint arXiv:2508.17196, 2025. Sixue Xing, Haoyu He, Kerui Wu, Zhuo Yang, Haozheng Luo, Tianfan Fu, and Aarthy Nagarajan. Compute allocation in evolutionary search: From depth-breadth to multi-armed bandits. arXiv preprint arXiv:2605.29268, 2026. Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. In International Conference on Learning Representations, 2024. Liming Yang, Junyu Luo, Xuanzhe Liu, Yiling Lou, and Zhenpeng Chen. BAMAS: Structuring budget-aware multi-agent systems. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 40, pp. 29802–29810, 2026a. Yang Yang, Zining Zhong, Jindong Li, Jiemin Wu, Kaishen Yuan, Wenshuo Chen, Menglin Yang, and Yutao Yue. TurboEvolve: Towards fast and robust LLM-driven program evolution. arXiv preprint arXiv:2604.18607, 2026b. Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In Advances in Neural Information Processing Systems, volume 36, 2023. Haoran Ye, Jiarui Wang, Zhiguang Cao, Federico Berto, Chuanbo Hua, Haeyeon Kim, Jinkyoo Park, and Guojie Song. ReEvo: Large language models as hyper-heuristics with reflective evolution. In Advances in Neural Information Processing Systems, volume 37, 2024. Haotian Ye, Haowei Lin, Jingyi Tang, Yizhen Luo, Caiyin Yang, Chang Su, Rahul Thapa, Rui Yang, Ruihua Liu, Zeyu Li, Chong Gao, Dachao Ding, Guangrong He, Miaolei Zhang, Lina Sun, Wenyang Wang, Yuchen Zhong, Zhuohao Shen, Di He, Jianfeng Ma, Stefano Ermon, Tongyang Li, Xiaowen Chu, James Z. Wang, and Yuzhi Xu. Evaluation-driven scaling for scientific discovery. arXiv preprint arXiv:2604.19341, 2026. 12
GLM-5-Team: Aohan Zeng, Xin Lv, Zhenyu Hou, Zhengxiao Du, Qinkai Zheng, Bin Chen, Da Yin, Chendi Ge, Chenghua Huang, Chengxing Xie, Chenzheng Zhu, Congfeng Yin, Cunxiang Wang, Gengzheng Pan, Hao Zeng, Haoke Zhang, Haoran Wang, Huilong Chen, Jiajie Zhang, Jian Jiao, Jiaqi Guo, Jingsen Wang, Jingzhao Du, Jinzhu Wu, Kedong Wang, Lei Li, Lin Fan, Lucen Zhong, Mingdao Liu, Mingming Zhao, Pengfan Du, Qian Dong, Rui Lu, Shuang-Li, Shulin Cao, Song Liu, Ting Jiang, Xiaodong Chen, Xiaohan Zhang, Xuancheng Huang, Xuezhen Dong, Yabo Xu, Yao Wei, Yifan An, Yilin Niu, Yitong Zhu, Yuanhao Wen, Yukuo Cen, Yushi Bai, Zhongpei Qiao, Zihan Wang, Zikang Wang, Zilin Zhu, Ziqiang Liu, Zixuan Li, Bojie Wang, Bosi Wen, Can Huang, Changpeng Cai, Chao Yu, Chen Li, Chengwei Hu, Chenhui Zhang, Dan Zhang, Daoyan Lin, Dayong Yang, Di Wang, Ding Ai, Erle Zhu, Fangzhou Yi, Feiyu Chen, Guohong Wen, Hailong Sun, Haisha Zhao, Haiyi Hu, Hanchen Zhang, Hanrui Liu, Hanyu Zhang, Hao Peng, Hao Tai, Haobo Zhang, He Liu, Hongwei Wang, Hongxi Yan, Hongyu Ge, Huan Liu, Huanpeng Chu, Jia’ni Zhao, Jiachen Wang, Jiajing Zhao, Jiamin Ren, Jiapeng Wang, Jiaxin Zhang, Jiayi Gui, Jiayue Zhao, Jijie Li, Jing An, Jing Li, Jingwei Yuan, Jinhua Du, Jinxin Liu, Junkai Zhi, Junwen Duan, Kaiyue Zhou, Kangjian Wei, Ke Wang, Keyun Luo, Laiqiang Zhang, Leigang Sha, Liang Xu, Lindong Wu, Lintao Ding, Lu Chen, Minghao Li, Nianyi Lin, Pan Ta, Qiang Zou, Rongjun Song, Ruiqi Yang, Shangqing Tu, Shangtong Yang, Shaoxiang Wu, Shengyan Zhang, Shijie Li, Shuang Li, Shuyi Fan, Wei Qin, Wei Tian, Weining Zhang, Wenbo Yu, Wenjie Liang, Xiang Kuang, Xiangmeng Cheng, Xiangyang Li, Xiaoquan Yan, Xiaowei Hu, Xiaoying Ling, Xing Fan, Xingye Xia, Xinyuan Zhang, Xinze Zhang, Xirui Pan, Xu Zou, Xunkai Zhang, Yadi Liu, Yandong Wu, Yanfu Li, Yidong Wang, Yifan Zhu, Yijun Tan, Yilin Zhou, Yiming Pan, Ying Zhang, Yinpei Su, Yipeng Geng, Yong Yan, Yonglin Tan, Yuean Bi, Yuhan Shen, Yuhao Yang, Yujiang Li, Yunan Liu, Yunqing Wang, Yuntao Li, Yurong Wu, Yutao Zhang, Yuxi Duan, Yuxuan Zhang, Zezhen Liu, Zhengtao Jiang, Zhenhe Yan, Zheyu Zhang, Zhixiang Wei, Zhuo Chen, Zhuoer Feng, Zijun Yao, Ziwei Chai, Ziyuan Wang, Zuzhou Zhang, Bin Xu, Minlie Huang, Hongning Wang, Juanzi Li, Yuxiao Dong, and Jie Tang. Glm-5: from vibe coding to agentic engineering, 2026. Andy Zhou, Kai Yan, Michal Shlapentokh-Rothman, Haohan Wang, and Yu-Xiong Wang. Language agent tree search unifies reasoning, acting, and planning in language models. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pp. 62138–62160, 2024.
A
P ROOF OF P ROPOSITION 1
Instance. Fix g > 0, κ > 1, and K ≥ 2. Every frontier selection deterministically improves the global best score by g. The budgeted objective value is therefore g times the number of selections completed before cumulative search cost exceeds B. One frontier costs c per selection, while the other K − 1 frontiers cost κc per selection. The cheap frontier is placed adversarially and can be identified only from realized costs. Optimum. Selecting the cheap frontier at every step completes ⌊B/c⌋ selections, so OPT = g⌊B/c⌋. Upper bound for cost-blind controllers. Every selection returns the same gain g, so the action– score history visible to a cost-blind controller is identical under every placement of the cheap frontier. The controller’s possibly random selection sequence σ therefore has the same distribution under every placement. Condition on σ. For placement j, let Nj be the number of selections completed within budget, and let Vj (n) count selections of frontier j among the first n. The first n selections cost c (κn − (κ − 1)Vj (n)), so the ledger constraint at n = Nj rearranges to Nj ≤
B κ−1 + Vj (Nj ). κc κ
Every selection costs at least c, so Nmax = maxj Nj ≤ B/c. Each Vj is nondecreasing, and P V (N j max ) = Nmax . Averaging the display over the K placements gives j K
1 X B κ − 1 Nmax Nj ≤ + · ≤ K j=1 κc κ K 13
1 1 + κ K
B . c
The adversarial placement attains minj Nj , which is at most this average. Taking expectation over σ preserves the bound because it holds for every realization. Since the run value is g Nj , every 1 cost-blind controller attains at most K + κ1 (1 + o(1)) OPT in expectation. Achievability with cost-aware credit. Select every frontier once at total cost (1 + (K − 1)κ) c. The realized costs identify the cheap frontier, which is then selected for the remaining budget. This policy completes at least ⌊B/c⌋ − (K − 1)κ selections. Ranking by gain per realized cost therefore attains at least OPT − (K − 1)κg = (1 − o(1)) OPT as B/c → ∞ with K and κ fixed. □ Remarks. The construction uses equal gains deliberately. Credit based only on score progress receives no signal that separates the frontiers, whether the signal is raw, smoothed, or optimism adjusted. The failure therefore belongs to the cost-blind class rather than a particular rule. Observing the stopping event does not help because that signal arrives only after the budget is spent. The allocation question is related to bandits with knapsacks (Badanidiyuru et al., 2013), where budgetconstrained optimality also favors arms with high expected gain per unit cost. Our setting additionally includes frontier development, nonstationarity from growing archives, and intervention actions. The proposition isolates cost-blindness from these difficulties.
B
C OSTA DA C ONTROLLER D ETAILS
B.1
C ONTROLLER S TATE AND OVERALL L OOP
We specify the experimental loop, local-sampling bootstrap, frontier-allocation bookkeeping, and evidence rules needed to reproduce CostAda. The controller maintains the evidence state Et = (νt , Lt , Zt , ot , wt , κt , Gt ), where each component supports budgeted tactic intervention while sharing the same search-side ledger as local exploration and frontier allocation. Table 2 summarizes these state variables.
Table 2: CostAda evidence state. The state variables are used by the budgeted tactic intervention layer and are updated from realized score and cost evidence. State
Role
νt
Counts consecutive steps without meaningful global progress to detect global stagnation. Accumulates realized cost over consecutive low-utility and low-allocationreward steps. Records whether a guide/tactic cycle has produced incumbent-level global progress. Stores a temporary intervention-mode correction after a failed guide cycle. Stores the remaining consolidation window after successful incumbent evidence. Stores the frontier selected for consolidation while wt > 0. Stores the active guidance-cycle state, including its baseline score and remaining tactic batch.
Lt Zt ot wt κt Gt
B.2
L OCAL E XPLORATION C ONTROL
After a frontier has been selected, the local controller chooses the action used to sample parent and context candidates from that frontier. The short bootstrap stage below handles low-evidence frontiers before the intensity rule is applied. 14
Algorithm 1: CostAda control loop (k)
0 Input :Initial frontiers {D0 }K k=1 , evaluator F , budget B, reference cost c̄, controller constants Θ (Table 3), iteration cap Tmax Output :Best-so-far candidate p⋆ (k) (k) 1 Initialize global best y0 , local bests {b0 }, cumulative cost C0 ← 0, utility states {H0 ← 0}, (k) (k) allocation states {R0 ← 0}, visit counts {n0 ← 0}, and intervention evidence states 2 for t ← 1 to Tmax do // Remaining-budget conditioning: form the pre-step budget ratio // Allocation level: cost-aware frontier allocation 3 Form the pre-step budget state ρt−1 ← max(0, 1 − Ct−1 /B) and select frontier kt using the allocation statistic and optimism bonus // Local level: budget-gated exploration intensity 4 Choose local action at using limited-evidence bootstrap or the budget-gated intensity rule; (kt ) draw parent/context programs ppar t , Ct from Dt−1 Generate candidate pt using the selected context and any scheduled guide/tactic information; 5 evaluate pt and obtain scalar score ft // Charge realized search-side token cost to the shared ledger 6 Charge all search-side LLM calls in the step to obtain ct ; update Ct , ρt , and normalized cost c̃t // Cost-calibrated frontier utility: the core credit signal (k ) 7 Update local and global best scores and the best-so-far candidate p⋆ ; compute δt t , gt , λt , (k ) (k ) λct , dt , utility ut t , and allocation reward rt t (kt ) (kt ) 8 Update Ht , Rt , visit counts, and intervention evidence; carry forward states for unselected frontiers 9 Update active guidance-cycle credit if a guided step improves over its cycle baseline 10 Apply guide backoff if the active guidance cycle is exhausted without sufficient gain // Intervention level: budgeted tactic intervention 11 if It = 1 (Section B.4) then 12 Schedule a budgeted guide/tactic intervention with mode mt 13 When the guide is generated, open a guidance cycle with the current best score as baseline 14 end // Budget stop: halt at the first crossing of the token budget 15 if Ct ≥ B then 16 break 17 end 18 end ⋆ 19 Return p
B.2.1
B OOTSTRAP ACTION P (k) Let Nt−1 = k nt−1 be the total number of frontier selections before step t. The local action is exploration, Nt−1 = 0, (kt ) at ← balanced, Nt−1 > 0 ∧ nt−1 = 0, ã , otherwise, t (k )
where ãt ∼ πlocal (· | It t ) is sampled from the budget-gated intensity rule of Section 4. B.3
F RONTIER A LLOCATION C ONTROL
The allocation state records whether a frontier advances the global best solution per realized cost. Local-only improvement is excluded because progress inside a weak frontier does not by itself justify more global budget. CostAda updates the allocation state only for the selected frontier. For every 15
(k)
(k)
unselected frontier, Rt = Rt−1 . The controller uses the ordinary frontier allocation rule unless a consolidation window is active. During consolidation, CostAda selects the frontier κt defined below. B.4
B UDGETED TACTIC I NTERVENTION
The intervention decision It uses the evidence rules below to determine whether a guide/tactic call is worth purchasing, which mode to use, and when later calls should be suppressed. Successful and failed guide cycles also feed back into frontier allocation and local sampling. Appendix B.6 traces both trigger paths and both modes in a recorded run log. B.4.1
S TAGNATION AND L OW-Y IELD E VIDENCE
The global stagnation counter is updated after observing the realized global gain: 0, gt > ϵg , νt = νt−1 + 1, otherwise. The stagnation criterion compares this counter with a budget-adaptive patience requirement, Pt = [νt ≥ νreq (ρt , Kt )],
νreq (ρt , Kt ) = max (⌈ν0 (1 − ρt )⌉, 2Kt ) ,
where ν0 is the base patience scale. The term 2Kt requires evidence across roughly two active-frontier cycles and is determined by the number of active frontiers rather than tuned per benchmark. CostAda also accumulates the realized cost of consecutive steps whose cost-calibrated utility and allocation reward are both negligible: h i Lt−1 + ct , ℓt = 1, (k ) (k ) ℓt = ⊮ ut t ≤ ϵg ∧ rt t ≤ ϵg , Lt = 0, ℓt = 0, where ℓt flags a low-yield step and Lt accumulates realized cost over consecutive low-yield steps. The low-yield criterion is Yt = [ρt ≥ 1/2] ∧ [νt ≥ Kt ] ∧ [Lt ≥ ĉguide ]. The criterion permits an earlier intervention while at least half of the budget remains. A trigger requires one frontier cycle without global improvement and accumulated low-yield cost at least as large as an estimated guide call. By that point, the run has already spent intervention-scale budget without useful return. The stagnation path Pt remains available later in the run. B.4.2
P ROGRESS P REDICATES
CostAda uses the same realized global gain with two evidence levels: Progt = [gt > ϵg ],
Inct = [gt > ϵinc ],
ϵinc = 10ϵg .
The first predicate resets stagnation and low-yield evidence. The second predicate is used for successful-incumbent evidence, consolidation, and the refinement prior. B.4.3
G UIDANCE -C YCLE C REDIT AND M ODE S ELECTION
When a budgeted guide/tactic call is generated, CostAda opens a guidance cycle G. The cycle baseline G ybase is the global best before the generated tactic batch is consumed. Let Gt = 1 indicate that an active guide/tactic batch remains. Let guidedt = 1 indicate that step t uses a tactic from the active guidance cycle. The cycle includes every candidate generated with the new tactics, including a same-step guided candidate when applicable and subsequent guided steps before the batch is exhausted. The cycle-level normalized gain is ! G y − y t base gtG = max ,0 . G max(|yt |, |ybase |, 1) Successful-incumbent evidence is produced when a budgeted guide cycle yields incumbent-level global progress before the tactic batch is exhausted: ζt = ⊮ gtG > ϵinc ∧ guidedt = 1 . 16
The persistent incumbent state is Zt = max(Zt−1 , ζt ). The default intervention mode is breakthrough, Zt = 0, m0t = refinement, Zt = 1. When an intervention is scheduled, the active mode also accounts for the temporary mode-credit correction: ot−1 , ot−1 ̸= ∅, mt = m0t , otherwise. B.4.4
C ONSOLIDATION
After successful-incumbent evidence is observed (ζt = 1), CostAda consolidates around the improving frontier for one active-frontier cycle: Kt , ζt = 1, kt , ζt = 1, wt = κt = max(wt−1 − 1, 0), ζt = 0, κt−1 , ζt = 0, where wt is the remaining consolidation window and κt is the frontier held for consolidation. When wt > 0, frontier allocation returns κt , guide calls are suppressed, and the local controller uses exploitation-oriented sampling for the consolidation window. B.4.5
G UIDE BACKOFF AND M ODE -C REDIT C ORRECTION
A guide cycle exhausted without incumbent-level global progress indicates poor return on its cost. Let exhaustGt = 1 indicate that the active guidance cycle is exhausted at step t. The backoff signal is G Backoff t = ⊮ exhaustt = 1 ∧ max ζs = 0 . s∈G
When Backoff t = 1, CostAda resets νt and Lt before the next decision. A subsequent guide therefore requires fresh stagnation or low-yield evidence. The intervention-mode correction is updated as ∅, ζt = 1, breakthrough, Backoff t = 1 ∧ Zt−1 = 1 ∧ mt = refinement, ot = ∅, Backoff t = 1 ∧ ot−1 ̸= ∅, ot−1 , otherwise. A successful incumbent therefore gives refinement a prior. A failed refinement guide permits one breakthrough probe, while a failed alternative probe returns the controller to the incumbent prior. B.4.6
A FFORDABILITY AND F INAL I NTERVENTION D ECISION
The reserve criterion is At = [B − Ct ≥ ĉguide + c̄], which requires enough remaining budget for the guide/tactic call and a small ordinary-generation reserve. The reserve allows the generated tactics to be attempted. The full intervention decision output is (It , mt ), where It = [wt = 0] ∧ [Gt = 0] ∧ [Backoff t = 0] ∧ At ∧ (Pt ∨ Yt ) . The mode mt is ignored when It = 0 and attached to the scheduled guide/tactic call when It = 1. B.5
C ONTROLLER C ONSTANTS
Controller constants are fixed once per benchmark family and are not retuned per benchmark. CostAda’s cost-calibration rule uses ledger-derived quantities: realized step cost, normalized cost, cumulative spending, and remaining budget ratio. Table 3 summarizes the constants that appear in the controller definitions above and in Algorithm 1. 17
Table 3: CostAda controller constants. Constants are fixed within each benchmark family and are not retuned per benchmark. Symbols match the definitions above. Symbol
Role
Used for
Imin , Imax
Local intensity bounds
α γ
ν0
Utility smoothing rate Allocation smoothing rate Cost-penalty floor Optimism scale Meaningful-progress threshold Incumbent-level threshold Base patience scale
Lower and upper bounds for parent/context sampling breadth. (k) Exponential moving average for local utility Ht . Exponential moving average for allocation reward (k) Rt . Early-run lower bound on cost penalization in dt . Remaining-budget-gated frontier exploration bonus. Stagnation reset, low-yield evidence, and Progt .
ϵc , ϵH
Numerical stabilizers
ĉguide
Guide-cost estimate
λmin cucb ϵg ϵinc
B.6
Successful guide evidence, consolidation, and refinement prior, with ϵinc = 10ϵg . Remaining-budget-dependent stagnation requirement νreq (ρt , Kt ). Stabilize cost normalization and the local intensity denominator. Low-yield trigger and affordability reserve for guide/tactic calls.
C ONTROLLER T RACE FROM A RUN L OG
Table 4 reports the controller state over iterations 6–20 of the CostAda run plotted in Figure 4. The nominal search-side budget is B = 1, and the reference cost is c̄ = 0.01. The reported values come directly from the run log. The trace shows how cost-calibrated utility and remaining-budget conditioning govern local exploration intensity, frontier allocation, and budgeted tactic intervention as the budget state changes. The window covers three complete guide cycles. Table 4: Controller trace over iterations 6–20 of one run on Signal Processing under GLM-5. Recorded quantities are the selected frontier, local sampling mode with intensity in parentheses, realized step cost, post-step remaining-budget ratio, cost-calibrated utility of Eq. (1), and allocation reward. Guide/tactic calls are charged to the same ledger and included in the step cost of the iteration that issues them. A blank Event cell marks an iteration with no controller event. t
kt
Local action
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
1 2 2 2 1 1 1 2 1 2 2 2 1 1 1
exploration (0.46) balanced (0.46) exploitation (0.15) exploitation (0.15) exploration (0.44) exploration (0.42) exploration (0.42) exploration (0.41) balanced (0.40) balanced (0.40) exploitation (0.15) exploitation (0.15) exploration (0.38) exploration (0.37) exploration (0.37)
ct
ρt
ut
rt
0.0073 0.0179 0.0309 0.0266 0.0085 0.0160 0.0151 0.0313 0.0149 0.0255 0.0196 0.0081 0.0361 0.0146 0.0144
0.92 0.90 0.87 0.84 0.83 0.82 0.80 0.77 0.76 0.73 0.71 0.70 0.67 0.65 0.64
0.000 0.056 0.000 0.000 0.050 0.000 0.000 0.000 0.000 0.052 0.000 0.000 0.000 0.000 0.062
0.000 0.056 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.052 0.000 0.000 0.000 0.000 0.062
Event stagnation met, guide scheduled (breakthrough) guide charged $0.0084, consolidation opens consolidation consolidation local gain, no global gain stagnation met, guide scheduled (refinement) guide charged $0.0087 consolidation opens consolidation low-yield met, guide scheduled (refinement) guide charged $0.0116 consolidation opens
Realized action costs. Step costs inside this window range from $0.0073 to $0.0361, and the seven guide/tactic calls issued over the full run cost between $0.0074 and $0.0179 each. The observed cost range corresponds to the middle panel of Figure 4. The realized costs enter cost-calibrated utility through the divisor dt . The costliest step here is about five times the cheapest. 18
Local utility and allocation reward. Iteration 10 provides a clear example of the distinction between local and global progress. The step produces a normalized local gain of 0.0692 against its frontier archive but does not improve the global best. Equation (1) assigns a positive cost-calibrated utility of 0.050, while the allocation reward is zero because it uses only global gain per realized cost. The local controller therefore keeps the frontier available for refinement, but the allocation layer records no evidence for sending it more global budget. Iterations 7, 15, and 20 show the complementary case. Their gains are global, so utility and allocation reward coincide at 0.056, 0.052, and 0.062. Only these steps add evidence for sending the frontier more budget. Local control under a shrinking budget. Local intensity falls as the ledger drains, from 0.46 at ρt = 0.92 to 0.37 by the end of the displayed window. Later in the run, intensity reaches 0.26 at ρt = 0.32 and 0.15 at exhaustion. Consolidation creates sharper changes within this gradual decline. At iterations 8–9 and 16–17, intensity drops to 0.15 as CostAda switches to exploitation inside a consolidation window. Sampling returns to exploration when the window closes. The local rule therefore combines gradual budget-driven narrowing with an evidence-driven exploitation response. Intervention triggers and modes. At iteration 6, the global stagnation counter reaches its requirement of four. CostAda schedules a breakthrough guide because no earlier guide has produced incumbent-level progress. The guide is charged $0.0084 at iteration 7 and is followed by a normalized global gain of 0.0700, which opens a consolidation window. After this success, the guides scheduled at iterations 12 and 17 use refinement mode. The two guides rely on different evidence. Iteration 12 follows a stagnation trigger, whereas iteration 17 follows a low-yield trigger at ρt = 0.70. By iteration 17, the run has accumulated $0.0277 of low-yield spending, roughly two to three times the cost of one guide call. The stagnation counter is only two against a requirement of four, so the low-yield path intervenes before a longer stagnation window forms. Increasing cost pressure. The required stagnation count remains four throughout the displayed window. The requirement rises to five when ρt reaches 0.32 and to six by ρt = 0.16 because patience scales with 1 − ρt . Over the same span, the cost divisor dt grows from about 1.14 early in the run to 1.72, 2.01, and 2.48 as λct increases. The same realized cost is therefore penalized more heavily late in the run. Near the horizon, a guide requires more evidence and an expensive step earns less credit than it would near the start. The run ends at the budget crossing with cumulative search-side cost of $1.0090 against nominal B = 1, an overshoot of 0.90%. Summary. The trace shows how return per realized cost and remaining budget jointly govern all three control levels. Local sampling narrows as the ledger drains, guidance changes from breakthrough to refinement after incumbent-level progress, and the intervention threshold rises near the horizon. All three behaviors follow the same cost-calibrated credit principle under different budget states. Section 5.4 plots the same run against its baselines.
C
B ENCHMARK D ETAILS
We follow the benchmark definitions and evaluation setup used by SkyDiscover, AdaEvolve, and EvoX (Liu et al., 2026b; Cemri et al., 2026; Liu et al., 2026a). The underlying tasks and reference values draw on AlphaEvolve, packing records, Heilbronn’s problem, generalized Sidon sets, OpenEvolve, and standard signal-processing references (Novikov et al., 2025; Friedman, 2025; Roth, 1951; Vinuesa del Rio, 2010; Sharma, 2025; Shenoi, 2005). Table 5 lists each benchmark, its optimization direction, and the objective used in the result tables.
D
E XPERIMENTAL ACCOUNTING D ETAILS
D.1
S EARCH -S IDE C OST
If iteration t issues a set of search-side LLM calls Jt , its realized cost is X (µ ) (j) (µ ) (j) ct = pin j Tin + poutj Tout , j∈Jt
19
Table 5: Benchmark objectives and optimization directions. Rows state the benchmark objective and whether higher or lower values are preferred. Benchmark
Direction
Objective
Circle Packing Circle Packing Rect
↑ ↑
Heilbronn Triangle
↑
Heilbronn Convex
↑
MinMaxDist (n=16, d=2)
↓
MinMaxDist (n=14, d=3)
↓
Third Autocorrelation
↓
Signal Processing
↑
Pack 26 disjoint circles in a unit square and maximize the sum of radii. Pack 21 disjoint circles in a rectangle of perimeter 4 and maximize the sum of radii. Place 11 points in a unit area triangle and maximize the minimum area over all triangles formed by triples of points. Place 13 points in a unit area convex region and maximize the minimum triangle area induced by any three points. Place 16 points in two dimensions and minimize the ratio between maximum and minimum pairwise distance, following the reference squared-ratio convention (Novikov et al., 2025). Place 14 points in three dimensions and minimize the ratio between maximum and minimum pairwise distance, again using the reference squaredratio convention. Construct witness functions that improve the upper bound on the third autocorrelation constant C3 in additive combinatorics. Synthesize a causal online filtering program for noisy nonstationary time series, balancing fidelity, smoothness, lag, and false trend changes.
(j)
(j)
(µ )
where µj is the model used by call j, Tin and Tout are provider-reported billable tokens, and pin j , (µ ) poutj are the corresponding per-token prices. We use fixed OpenRouter prices for all methods. GLM-5 input/output prices are $0.60/$1.92 per million tokens (OpenRouter, 2026a), and GPT-5.4 prices are $2.50/$15.00 per million tokens (OpenRouter, 2026b). Search-side calls include ordinary candidate generation, recovery from failed generations, and guide/tactic generation. Deterministic evaluator execution is excluded. Budgets in Section 5 are denominated in this quantity. The normalized step cost c̃t uses reference generation costs of c̄=0.01 for GLM-5 and c̄=0.1 for GPT-5.4. We measured these values before the main comparisons as the average realized search-side cost of an ordinary generation call. The reference cost is fixed per backbone, shared across benchmarks, and used only for controller normalization rather than the evaluation ledger. D.2
S HARED E XPERIMENTAL S CAFFOLD
We instantiate all methods in the same discovery framework. Candidate-generation infrastructure, parsing, deterministic evaluator execution, and archive insertion are shared across methods. For the main comparisons, generator and guide model choices are fixed within each benchmark family, and the same pricing assumptions apply to every method in that family.
E
P ER -B ENCHMARK B UDGET-C UTOFF R ESULTS
The cutoff results below support the budget-path analysis in Section 5.3. Table 6 reports the GLM-5 ladder at B ∈ {0.25, 0.5, 0.75, 1}, while Table 7 gives the corresponding fractions of B = 5 under GPT-5.4. We evaluate all three methods at the same four cutoffs. We omit the B = 0 initialization because it precedes the first generated candidate and may not have a benchmark-objective value. The early-budget advantage in the main-text GLM-5 analysis also appears under GPT-5.4. In benchmark-objective units, CostAda leads 29 of the 32 cutoff cells and all eight benchmarks from 0.75B onward. The three non-leading cells occur at 0.25B and 0.5B on Circle Packing Rect and at 0.25B on MinMaxDist (n=16, d=2). With half of the budget, CostAda’s mean matches or exceeds the strongest baseline’s full-budget mean on seven of the eight benchmarks.
F
S MALL -B UDGET R ERUNS VERSUS C UTOFF E VALUATION
Table 8 compares two views of early-budget behavior under GLM-5. Within each benchmark block, the first three rows read nominal B=1 trajectories at the first completed iteration reaching each absolute budget. CostAdaB=0.5 instead reports three independent runs configured with nominal 20
Table 6: Benchmark objectives across GLM-5 budget cutoffs. The nominal budget is B = 1, so the columns correspond to cutoff costs 0.25, 0.5, 0.75, and 1.0 in ledger dollars. Entries report Mean ± Std at the first completed iteration reaching each cutoff, using the units and score directions of Table 1. Arrows indicate the preferred direction. Best entries within each benchmark and cutoff are bolded. Ties at the reported precision are jointly bolded. Benchmark
Method
B=0.25
B=0.5
B=0.75
B=1
Circle Packing ↑
AdaEvolve EvoX CostAda
1.8225 ± 0.2223 2.1815 ± 0.0801 2.5535 ± 0.0585
2.4690 ± 0.1562 2.5128 ± 0.1269 2.6016 ± 0.0335
2.5617 ± 0.0773 2.5717 ± 0.0752 2.6252 ± 0.0094
2.5617 ± 0.0773 2.5717 ± 0.0752 2.6306 ± 0.0054
Circle Packing Rect ↑
AdaEvolve EvoX CostAda
2.1182 ± 0.1146 2.1985 ± 0.2569 2.3478 ± 0.0081
2.2043 ± 0.1578 2.1989 ± 0.2563 2.3478 ± 0.0081
2.2089 ± 0.1635 2.1989 ± 0.2563 2.3478 ± 0.0081
2.2089 ± 0.1635 2.1989 ± 0.2563 2.3525 ± 0.0081
Heilbronn Convex ↑
AdaEvolve EvoX CostAda
0.0215 ± 0.0030 0.0203 ± 0.0036 0.0215 ± 0.0003
0.0215 ± 0.0030 0.0222 ± 0.0024 0.0250 ± 0.0030
0.0229 ± 0.0015 0.0234 ± 0.0012 0.0253 ± 0.0033
0.0229 ± 0.0015 0.0235 ± 0.0012 0.0263 ± 0.0018
Heilbronn Triangle ↑
AdaEvolve EvoX CostAda
0.0212 ± 0.0075 0.0149 ± 0.0027 0.0296 ± 0.0017
0.0283 ± 0.0020 0.0200 ± 0.0038 0.0296 ± 0.0017
0.0283 ± 0.0020 0.0200 ± 0.0038 0.0296 ± 0.0017
0.0303 ± 0.0011 0.0220 ± 0.0050 0.0314 ± 0.0003
MinMaxDist (n=16, d=2) ↓
AdaEvolve EvoX CostAda
14.59 ± 1.03 15.01 ± 1.69 13.62 ± 1.02
14.54 ± 1.02 14.37 ± 2.11 13.57 ± 1.07
14.06 ± 1.30 14.20 ± 1.90 13.15 ± 0.36
14.06 ± 1.30 14.17 ± 1.92 13.11 ± 0.29
MinMaxDist (n=14, d=3) ↓
AdaEvolve EvoX CostAda
4.57 ± 0.08 4.59 ± 0.37 4.31 ± 0.24
4.48 ± 0.13 4.34 ± 0.27 4.19 ± 0.04
4.38 ± 0.08 4.22 ± 0.06 4.18 ± 0.02
4.38 ± 0.08 4.20 ± 0.03 4.17 ± 0.00
Third Autocorrelation ↓
AdaEvolve EvoX CostAda
1.4711 ± 0.0040 1.5760 ± 0.1729 1.4858 ± 0.0256
1.4694 ± 0.0017 1.5719 ± 0.1658 1.4746 ± 0.0064
1.4694 ± 0.0017 1.5481 ± 0.1308 1.4679 ± 0.0054
1.4685 ± 0.0014 1.5481 ± 0.1308 1.4658 ± 0.0037
Signal Processing ↑
AdaEvolve EvoX CostAda
0.5330 ± 0.0436 0.4649 ± 0.0328 0.6210 ± 0.0860
0.5775 ± 0.0704 0.6454 ± 0.0789 0.6540 ± 0.0890
0.5759 ± 0.0731 0.6571 ± 0.0604 0.6717 ± 0.0609
0.6022 ± 0.0479 0.6592 ± 0.0573 0.7054 ± 0.0124
budget B=0.5 and evaluated at the same absolute budgets. These runs can adapt their search to the smaller horizon, whereas a cutoff only truncates a trajectory planned for B=1. The independently budgeted CostAdaB=0.5 runs outperform the strongest baseline mean in all 16 benchmark–budget cells. The reruns also match or improve on the corresponding cutoff values from nominal B=1 trajectories in 13 cells. The rerun results confirm that the early-budget advantage in Section 5.3 persists when CostAda plans directly for the smaller horizon.
G
C OMPONENT A BLATIONS
We study Circle Packing, Heilbronn Triangle, and Signal Processing under both backbones, covering packing, geometric point configuration, and executable program synthesis. The study compares Full CostAda with three variants. No cost calibration sets the cost denominator to one while retaining the remaining-budget and intervention rules. No remaining budget fixes the credit mixture and removes the remaining-budget factors from local intensity and frontier optimism, while leaving intervention gating unchanged. No intervention gating triggers guide/tactic intervention from stagnation evidence without the affordability and low-yield gates, while retaining guide backoff, consolidation, and the single-active-batch constraint. Together, the variants isolate cost calibration, remaining-budget conditioning, and intervention gating. We perform three independent runs per variant, backbone, and benchmark. The three runs support all metrics reported for that setting, while the benchmark, evaluator, backbone, nominal budget, and stopping rule remain fixed across variants. For each run, B EST S CORE @0.5B and B EST S CORE @B report the benchmark objective of the best candidate available at the first completed iteration that reaches the cutoff, with candidates ranked by normalized score. We compute normalized AUC by integrating the stepwise best-so-far normalized 21
Table 7: Benchmark objectives across GPT-5.4 budget cutoffs. The nominal budget is B = 5, so the columns correspond to cutoff costs 1.25, 2.5, 3.75, and 5.0. Entries report Mean ± Std at the first completed iteration reaching each cutoff. Arrows indicate the preferred direction. Best entries within each benchmark and cutoff are bolded. Ties at the reported precision are jointly bolded. Benchmark
Method
0.25B
0.5B
0.75B
1B
Circle Packing ↑
AdaEvolve EvoX CostAda
2.5632 ± 0.0784 2.5225 ± 0.0328 2.6143 ± 0.0140
2.5827 ± 0.0510 2.5441 ± 0.0609 2.6211 ± 0.0033
2.5865 ± 0.0535 2.5818 ± 0.0476 2.6218 ± 0.0044
2.6196 ± 0.0030 2.5851 ± 0.0510 2.6248 ± 0.0046
Circle Packing Rect ↑
AdaEvolve EvoX CostAda
2.2826 ± 0.0410 2.3221 ± 0.0428 2.2689 ± 0.0313
2.2910 ± 0.0507 2.3474 ± 0.0011 2.3111 ± 0.0462
2.3125 ± 0.0370 2.3474 ± 0.0011 2.3491 ± 0.0128
2.3148 ± 0.0357 2.3474 ± 0.0011 2.3577 ± 0.0050
Heilbronn Convex ↑
AdaEvolve EvoX CostAda
0.0187 ± 0.0007 0.0166 ± 0.0018 0.0234 ± 0.0010
0.0187 ± 0.0007 0.0197 ± 0.0026 0.0234 ± 0.0010
0.0187 ± 0.0007 0.0212 ± 0.0021 0.0244 ± 0.0008
0.0197 ± 0.0020 0.0223 ± 0.0031 0.0244 ± 0.0008
Heilbronn Triangle ↑
AdaEvolve EvoX CostAda
0.0280 ± 0.0003 0.0240 ± 0.0022 0.0288 ± 0.0039
0.0290 ± 0.0016 0.0254 ± 0.0019 0.0317 ± 0.0014
0.0299 ± 0.0014 0.0260 ± 0.0030 0.0329 ± 0.0012
0.0307 ± 0.0008 0.0263 ± 0.0035 0.0330 ± 0.0009
MinMaxDist (n=16, d=2) ↓
AdaEvolve EvoX CostAda
13.49 ± 0.85 13.00 ± 0.00 13.16 ± 0.20
13.37 ± 0.65 13.00 ± 0.00 12.98 ± 0.09
13.14 ± 0.24 13.00 ± 0.00 12.93 ± 0.06
13.00 ± 0.00 13.00 ± 0.00 12.93 ± 0.06
MinMaxDist (n=14, d=3) ↓
AdaEvolve EvoX CostAda
4.64 ± 0.15 4.64 ± 0.16 4.55 ± 0.15
4.61 ± 0.14 4.46 ± 0.01 4.42 ± 0.08
4.61 ± 0.14 4.44 ± 0.02 4.42 ± 0.08
4.55 ± 0.15 4.44 ± 0.02 4.42 ± 0.08
Third Autocorrelation ↓
AdaEvolve EvoX CostAda
1.5433 ± 0.0278 1.4899 ± 0.0028 1.4748 ± 0.0056
1.5157 ± 0.0079 1.4853 ± 0.0043 1.4738 ± 0.0048
1.5157 ± 0.0079 1.4838 ± 0.0029 1.4717 ± 0.0074
1.5081 ± 0.0069 1.4824 ± 0.0042 1.4717 ± 0.0074
Signal Processing ↑
AdaEvolve EvoX CostAda
0.5998 ± 0.0071 0.5156 ± 0.0441 0.6994 ± 0.0971
0.6400 ± 0.0886 0.5808 ± 0.0835 0.7681 ± 0.0434
0.6604 ± 0.0400 0.6159 ± 0.0570 0.7681 ± 0.0434
0.7011 ± 0.0128 0.6161 ± 0.0561 0.7965 ± 0.0346
score over [0, B], charging each action before its score takes effect. All standard deviations are sample standard deviations over the three runs. Tables 9 and 10 report the component ablations under GLM-5 at B=1 and GPT-5.4 at B=5. Full CostAda gives the strongest displayed mean for every benchmark–metric pair under both backbones. On GLM-5 Signal Processing, removing cost calibration lowers B EST S CORE @0.5B, B EST S CORE @B, and normalized AUC by 4.93%, 3.89%, and 3.45%, respectively. Removing either remaining-budget conditioning or intervention gating also lowers all displayed GLM-5 means. Under GPT-5.4, the full controller leads every reported column. The consistent ordering supports the contribution of all three components within the settings examined here.
H
N ORMALIZED S CORE R ESULTS
Benchmark objectives differ in units, magnitude, and direction across the eight benchmarks. We therefore use a normalized score for the cross-benchmark cutoff and AUC analyses in Section 5.3. The shared evaluator stack reports this direction-adjusted quality measure for every candidate. For benchmarks with a fixed reference value, the normalized score is the ratio between the achieved objective and that reference. We invert the ratio for minimization benchmarks so that higher is always better. Reference values follow prior benchmark reports (Novikov et al., 2025; Cemri et al., 2026; Liu et al., 2026a). A value of 1 matches the reference, values above 1 exceed it, and invalid candidates receive a score of zero. For Signal Processing, the evaluator already produces a bounded composite quality measure, so we use its overall program score in [0, 1]. Normalization constants are fixed per benchmark and shared by all methods. The fixed normalization preserves method rankings within each benchmark while placing scores from different benchmarks on a common scale. Tables 12 and 13 report best-so-far normalized scores at the same cutoffs as the benchmark-objective tables. Table 11 complements these cutoff tables with per-benchmark normalized AUC at the nominal budget, and its Average row gives the per-backbone values summarized in Section 5.3. Cutoff scores 22
Table 8: Independent GLM-5 small-budget runs versus cutoffs. The first three rows of each benchmark block evaluate nominal B=1 trajectories at absolute costs 0.25 and 0.5. CostAdaB=0.5 denotes runs configured with the smaller nominal budget. Entries are Mean ± Std in the objective units of Table 1. Arrows show direction, and boldface marks the best value per benchmark and cost, including ties. B=0.25
B=0.5
Circle Packing ↑
AdaEvolve EvoX CostAda CostAdaB=0.5
1.8225 ± 0.2223 2.1815 ± 0.0801 2.5535 ± 0.0585 2.6146 ± 0.0176
2.4690 ± 0.1562 2.5128 ± 0.1269 2.6016 ± 0.0335 2.6233 ± 0.0044
Circle Packing Rect ↑
AdaEvolve EvoX CostAda CostAdaB=0.5
2.1182 ± 0.1146 2.1985 ± 0.2569 2.3478 ± 0.0081 2.3404 ± 0.0008
2.2043 ± 0.1578 2.1989 ± 0.2563 2.3478 ± 0.0081 2.3404 ± 0.0008
Heilbronn Convex ↑
AdaEvolve EvoX CostAda CostAdaB=0.5
0.0215 ± 0.0030 0.0203 ± 0.0036 0.0215 ± 0.0003 0.0253 ± 0.0011
0.0215 ± 0.0030 0.0222 ± 0.0024 0.0250 ± 0.0030 0.0253 ± 0.0011
Heilbronn Triangle ↑
AdaEvolve EvoX CostAda CostAdaB=0.5
0.0212 ± 0.0075 0.0149 ± 0.0027 0.0296 ± 0.0017 0.0302 ± 0.0036
0.0283 ± 0.0020 0.0200 ± 0.0038 0.0296 ± 0.0017 0.0310 ± 0.0023
AdaEvolve EvoX MinMaxDist (n=16, d=2) ↓ CostAda CostAdaB=0.5
14.59 ± 1.03 15.01 ± 1.69 13.62 ± 1.02 13.41 ± 0.46
14.54 ± 1.02 14.37 ± 2.11 13.57 ± 1.07 13.13 ± 0.21
AdaEvolve EvoX MinMaxDist (n=14, d=3) ↓ CostAda CostAdaB=0.5
4.57 ± 0.08 4.59 ± 0.37 4.31 ± 0.24 4.23 ± 0.09
4.48 ± 0.13 4.34 ± 0.27 4.19 ± 0.04 4.17 ± 0.00
Benchmark
Method
Third Autocorrelation ↓
AdaEvolve EvoX CostAda CostAdaB=0.5
1.4711 ± 0.0040 1.5760 ± 0.1729 1.4858 ± 0.0256 1.4685 ± 0.0062
1.4694 ± 0.0017 1.5719 ± 0.1658 1.4746 ± 0.0064 1.4685 ± 0.0062
Signal Processing ↑
AdaEvolve EvoX CostAda CostAdaB=0.5
0.5330 ± 0.0436 0.4649 ± 0.0328 0.6210 ± 0.0860 0.6207 ± 0.0339
0.5775 ± 0.0704 0.6454 ± 0.0789 0.6540 ± 0.0890 0.7099 ± 0.0426
Table 9: Component ablations under GLM-5. Entries report Mean ± Std. Benchmark objectives are used for the two cutoff columns, and normalized AUC is higher-better. Arrows indicate the preferred objective direction, and the strongest entry in each benchmark–metric column is bolded. B EST S CORE @0.5B
B EST S CORE @B
Norm. AUC ↑
Full CostAda No cost calibration No remaining budget No intervention gating
2.6195 ± 0.0128 2.5389 ± 0.1153 2.6074 ± 0.0125 2.3594 ± 0.2251
2.6281 ± 0.0067 2.5738 ± 0.0554 2.6172 ± 0.0057 2.5291 ± 0.0949
0.9517 ± 0.0095 0.9053 ± 0.0376 0.9161 ± 0.0316 0.8478 ± 0.0642
Heilbronn Triangle ↑
Full CostAda No cost calibration No remaining budget No intervention gating
0.0306 ± 0.0009 0.0167 ± 0.0032 0.0212 ± 0.0048 0.0206 ± 0.0085
0.0313 ± 0.0004 0.0228 ± 0.0040 0.0251 ± 0.0049 0.0244 ± 0.0035
0.7831 ± 0.0486 0.4654 ± 0.0614 0.4073 ± 0.0426 0.4494 ± 0.1622
Signal Processing ↑
Full CostAda No cost calibration No remaining budget No intervention gating
0.6682 ± 0.0645 0.6352 ± 0.0200 0.6101 ± 0.0503 0.5986 ± 0.0142
0.7121 ± 0.0627 0.6844 ± 0.0601 0.6258 ± 0.0443 0.6938 ± 0.0691
0.6583 ± 0.0309 0.6355 ± 0.0200 0.6146 ± 0.0134 0.6336 ± 0.0214
Benchmark
Variant
Circle Packing ↑
23
Table 10: Component ablations under GPT-5.4. Entries report Mean ± Std. Benchmark objectives are used for the two cutoff columns, and normalized AUC is higher-better. Arrows indicate the preferred objective direction, and the strongest entry in each benchmark–metric column is bolded. B EST S CORE @0.5B
B EST S CORE @B
Norm. AUC ↑
Full CostAda No cost calibration No remaining budget No intervention gating
2.6197 ± 0.0080 2.5963 ± 0.0293 2.5898 ± 0.0421 2.5183 ± 0.0455
2.6212 ± 0.0073 2.6047 ± 0.0364 2.5942 ± 0.0458 2.5223 ± 0.0386
0.9825 ± 0.0050 0.9648 ± 0.0276 0.9673 ± 0.0079 0.9402 ± 0.0246
Heilbronn Triangle ↑
Full CostAda No cost calibration No remaining budget No intervention gating
0.0309 ± 0.0010 0.0252 ± 0.0021 0.0290 ± 0.0033 0.0266 ± 0.0009
0.0326 ± 0.0008 0.0274 ± 0.0018 0.0291 ± 0.0033 0.0268 ± 0.0007
0.7951 ± 0.0253 0.6748 ± 0.0459 0.7494 ± 0.0615 0.6949 ± 0.0259
Signal Processing ↑
Full CostAda No cost calibration No remaining budget No intervention gating
0.7838 ± 0.0870 0.5893 ± 0.0216 0.6906 ± 0.0956 0.6396 ± 0.0583
0.8161 ± 0.0908 0.6521 ± 0.0685 0.6734 ± 0.0559 0.7208 ± 0.0856
0.7019 ± 0.0480 0.6405 ± 0.0150 0.6557 ± 0.0192 0.6645 ± 0.0032
Benchmark
Variant
Circle Packing ↑
are taken from the first completed iteration that reaches each budget level. The common scale makes cells comparable across benchmarks and methods, with higher values preferred after normalization. Table 11: Normalized best-so-far AUC over the full budget. Entries give Mean ± Std of the average best-so-far normalized score over [0, B], with B=1 for GLM-5 and B=5 for GPT-5.4. Higher is better. Best entries within each benchmark and backbone are bolded. Ties at the reported precision are jointly bolded. The Average row reports the mean of the eight per-benchmark entries. GLM-5 (B=1)
Benchmark Circle Packing Circle Packing Rect Heilbronn Convex Heilbronn Triangle MinMaxDist (n=16, d=2) MinMaxDist (n=14, d=3) Third Autocorrelation Signal Processing Average
GPT-5.4 (B=5)
AdaEvolve
EvoX
CostAda
AdaEvolve
EvoX
CostAda
0.8341 ± 0.0273 0.9009 ± 0.0629 0.6812 ± 0.0840 0.6571 ± 0.0658 0.8864 ± 0.0588 0.9172 ± 0.0068 0.9820 ± 0.0027 0.5891 ± 0.0149
0.8752 ± 0.0289 0.8386 ± 0.1738 0.6579 ± 0.0560 0.4700 ± 0.0372 0.8530 ± 0.0907 0.9232 ± 0.0473 0.9177 ± 0.1009 0.5873 ± 0.0366
0.9295 ± 0.0134 0.9551 ± 0.0133 0.7606 ± 0.0700 0.7613 ± 0.0531 0.9241 ± 0.0370 0.9502 ± 0.0082 0.9658 ± 0.0050 0.6546 ± 0.0444
0.9668 ± 0.0197 0.9630 ± 0.0139 0.5896 ± 0.0243 0.7825 ± 0.0132 0.9556 ± 0.0343 0.8947 ± 0.0240 0.9311 ± 0.0102 0.6660 ± 0.0024
0.9548 ± 0.0172 0.9668 ± 0.0124 0.6103 ± 0.0645 0.6463 ± 0.0632 0.9651 ± 0.0165 0.9031 ± 0.0041 0.9609 ± 0.0041 0.6216 ± 0.0292
0.9771 ± 0.0096 0.9672 ± 0.0058 0.7499 ± 0.0144 0.8229 ± 0.0387 0.9654 ± 0.0098 0.9186 ± 0.0077 0.9776 ± 0.0081 0.7022 ± 0.0224
0.8060
0.7654
0.8626
0.8437
0.8286
0.8851
Under GLM-5, CostAda is best or tied in 30 of the 32 cutoff cells. The two exceptions are Third Autocorrelation at the first two cutoffs, matching the benchmark-objective analysis in Section 5.3. Under GPT-5.4, CostAda is best or tied in 29 of the 32 cutoff cells, consistent with the benchmarkobjective comparison in Appendix E. The ordering therefore does not depend on the reporting scale.
24
Table 12: Best-so-far normalized scores across GLM-5 budget cutoffs. The nominal budget is B=1, with the same budget fractions as Table 6. Best entries within each benchmark and cutoff are bolded. Ties at the reported precision are jointly bolded. Benchmark
Method
B=0.25
B=0.5
B=0.75
B=1
Circle Packing
AdaEvolve EvoX CostAda
0.6917 ± 0.0844 0.8279 ± 0.0304 0.9691 ± 0.0222
0.9370 ± 0.0593 0.9536 ± 0.0481 0.9873 ± 0.0127
0.9722 ± 0.0293 0.9760 ± 0.0285 0.9963 ± 0.0036
0.9722 ± 0.0293 0.9760 ± 0.0285 0.9983 ± 0.0021
Circle Packing Rect
AdaEvolve EvoX CostAda
0.8953 ± 0.0484 0.9293 ± 0.1086 0.9924 ± 0.0034
0.9317 ± 0.0667 0.9295 ± 0.1083 0.9924 ± 0.0034
0.9336 ± 0.0691 0.9295 ± 0.1083 0.9924 ± 0.0034
0.9336 ± 0.0691 0.9295 ± 0.1083 0.9944 ± 0.0034
Heilbronn Convex
AdaEvolve EvoX CostAda
0.6954 ± 0.0963 0.6556 ± 0.1173 0.6957 ± 0.0104
0.6954 ± 0.0963 0.7166 ± 0.0790 0.8096 ± 0.0974
0.7410 ± 0.0497 0.7563 ± 0.0372 0.8190 ± 0.1078
0.7410 ± 0.0497 0.7608 ± 0.0386 0.8496 ± 0.0575
Heilbronn Triangle
AdaEvolve EvoX CostAda
0.5816 ± 0.2042 0.4088 ± 0.0730 0.8098 ± 0.0452
0.7734 ± 0.0535 0.5488 ± 0.1039 0.8098 ± 0.0452
0.7734 ± 0.0535 0.5488 ± 0.1039 0.8098 ± 0.0452
0.8300 ± 0.0309 0.6024 ± 0.1364 0.8595 ± 0.0085
MinMaxDist (n=16, d=2)
AdaEvolve EvoX CostAda
0.8861 ± 0.0630 0.8657 ± 0.0957 0.9495 ± 0.0681
0.8891 ± 0.0626 0.9090 ± 0.1232 0.9540 ± 0.0721
0.9214 ± 0.0811 0.9179 ± 0.1138 0.9805 ± 0.0264
0.9214 ± 0.0811 0.9201 ± 0.1156 0.9838 ± 0.0212
MinMaxDist (n=14, d=3)
AdaEvolve EvoX CostAda
0.9119 ± 0.0170 0.9120 ± 0.0766 0.9685 ± 0.0522
0.9298 ± 0.0264 0.9612 ± 0.0568 0.9936 ± 0.0094
0.9512 ± 0.0168 0.9864 ± 0.0142 0.9964 ± 0.0045
0.9512 ± 0.0168 0.9909 ± 0.0076 0.9994 ± 0.0006
Third Autocorrelation
AdaEvolve EvoX CostAda
0.9895 ± 0.0027 0.9307 ± 0.0960 0.9799 ± 0.0167
0.9907 ± 0.0011 0.9326 ± 0.0927 0.9871 ± 0.0043
0.9907 ± 0.0011 0.9446 ± 0.0761 0.9916 ± 0.0036
0.9913 ± 0.0009 0.9446 ± 0.0761 0.9931 ± 0.0025
Signal Processing
AdaEvolve EvoX CostAda
0.5692 ± 0.0301 0.5122 ± 0.0177 0.6377 ± 0.0805
0.6126 ± 0.0161 0.6361 ± 0.0655 0.6924 ± 0.0536
0.6173 ± 0.0158 0.6429 ± 0.0544 0.7069 ± 0.0318
0.6393 ± 0.0240 0.6502 ± 0.0430 0.7222 ± 0.0127
25
Table 13: Best-so-far normalized scores across GPT-5.4 budget cutoffs. The nominal budget is B=5, with the same budget fractions as Table 7. Best entries within each benchmark and cutoff are bolded. Ties at the reported precision are jointly bolded.
I
Benchmark
Method
0.25B
0.5B
0.75B
1B
Circle Packing
AdaEvolve EvoX CostAda
0.9727 ± 0.0297 0.9573 ± 0.0125 0.9921 ± 0.0053
0.9801 ± 0.0194 0.9655 ± 0.0231 0.9947 ± 0.0012
0.9816 ± 0.0203 0.9798 ± 0.0181 0.9950 ± 0.0017
0.9941 ± 0.0011 0.9811 ± 0.0193 0.9961 ± 0.0017
Circle Packing Rect
AdaEvolve EvoX CostAda
0.9648 ± 0.0173 0.9815 ± 0.0181 0.9590 ± 0.0132
0.9684 ± 0.0214 0.9922 ± 0.0004 0.9769 ± 0.0195
0.9775 ± 0.0156 0.9922 ± 0.0004 0.9929 ± 0.0054
0.9784 ± 0.0151 0.9922 ± 0.0004 0.9966 ± 0.0021
Heilbronn Convex
AdaEvolve EvoX CostAda
0.6034 ± 0.0242 0.5353 ± 0.0594 0.7574 ± 0.0319
0.6034 ± 0.0242 0.6354 ± 0.0829 0.7574 ± 0.0319
0.6049 ± 0.0222 0.6840 ± 0.0663 0.7885 ± 0.0243
0.6376 ± 0.0640 0.7194 ± 0.1014 0.7885 ± 0.0243
Heilbronn Triangle
AdaEvolve EvoX CostAda
0.7654 ± 0.0088 0.6577 ± 0.0599 0.7897 ± 0.1072
0.7941 ± 0.0425 0.6940 ± 0.0507 0.8675 ± 0.0376
0.8183 ± 0.0382 0.7124 ± 0.0824 0.8997 ± 0.0334
0.8395 ± 0.0219 0.7205 ± 0.0956 0.9042 ± 0.0258
MinMaxDist (n=16, d=2)
AdaEvolve EvoX CostAda
0.9579 ± 0.0582 0.9915 ± 0.0000 0.9796 ± 0.0149
0.9653 ± 0.0453 0.9915 ± 0.0000 0.9929 ± 0.0065
0.9811 ± 0.0180 0.9915 ± 0.0000 0.9972 ± 0.0049
0.9914 ± 0.0002 0.9915 ± 0.0000 0.9972 ± 0.0049
MinMaxDist (n=14, d=3)
AdaEvolve EvoX CostAda
0.8980 ± 0.0305 0.8991 ± 0.0325 0.9156 ± 0.0305
0.9045 ± 0.0267 0.9347 ± 0.0018 0.9434 ± 0.0177
0.9045 ± 0.0267 0.9376 ± 0.0050 0.9434 ± 0.0177
0.9156 ± 0.0305 0.9376 ± 0.0050 0.9434 ± 0.0177
Third Autocorrelation
AdaEvolve EvoX CostAda
0.9434 ± 0.0169 0.9770 ± 0.0018 0.9870 ± 0.0038
0.9604 ± 0.0050 0.9801 ± 0.0028 0.9877 ± 0.0032
0.9604 ± 0.0050 0.9810 ± 0.0019 0.9891 ± 0.0050
0.9652 ± 0.0044 0.9820 ± 0.0028 0.9891 ± 0.0050
Signal Processing
AdaEvolve EvoX CostAda
0.6617 ± 0.0040 0.5890 ± 0.0447 0.7069 ± 0.0402
0.6739 ± 0.0145 0.6436 ± 0.0509 0.7289 ± 0.0262
0.7043 ± 0.0024 0.6644 ± 0.0299 0.7289 ± 0.0262
0.7182 ± 0.0137 0.6767 ± 0.0179 0.7672 ± 0.0292
O BJECTIVE AND C OST T RAJECTORIES ACROSS B ENCHMARKS
Figures 5–20 extend the main-text case study to all eight benchmarks under GLM-5 and GPT-5.4. The figures use actual iteration logs, with one run per method and one benchmark per figure under the same nominal budget. The left panel compares best-so-far benchmark objective with cumulative realized search-side cost. The middle panel shows realized step cost against iteration, and the right panel shows cumulative realized cost. Costs are divided by the nominal budget B, whose boundary is marked by the dotted line at 1.
2.6
2.2 2.0 1.8 1.6 0.0 0.5 1.0 Cumulative cost / B
0.10 Step cost / B
sum radii
2.4
EvoX
0.08 0.06 0.04 0.02 0.00
CostAda
Cumulative cost / B
AdaEvolve
15
30 45 Iteration
1.0 0.8 0.6 0.4 0.2 0.0
15
30 45 Iteration
Figure 5: Objective and cost trajectories for Circle Packing under GLM-5.
26
AdaEvolve
EvoX
CostAda
2.2
2.0
0.075 0.050 0.025
1.8
0.000
0.0 0.5 1.0 Cumulative cost / B
1.0
Cumulative cost / B
0.100
Step cost / B
radii sum
0.125
15
0.8 0.6 0.4 0.2 0.0
30 45 Iteration
15
30 45 Iteration
Figure 6: Objective and cost trajectories for Circle Packing Rect under GLM-5. AdaEvolve
EvoX
CostAda
0.020 0.015
Step cost / B
min. area
0.025
0.010
0.06 0.04 0.02 0.00
0.0 0.5 1.0 Cumulative cost / B
Cumulative cost / B
0.08
15
1.0 0.8 0.6 0.4 0.2 0.0
30 45 Iteration
15
30 45 Iteration
Figure 7: Objective and cost trajectories for Heilbronn Convex under GLM-5. AdaEvolve
0.010 0.005 0.0 0.5 1.0 Cumulative cost / B
Cumulative cost / B
0.015
Step cost / B
min. area
0.020
CostAda
0.15
0.030 0.025
EvoX
0.10
0.05
0.00
1.0 0.8 0.6 0.4 0.2 0.0
15 30 45 Iteration
15 30 45 Iteration
Figure 8: Objective and cost trajectories for Heilbronn Triangle under GLM-5. AdaEvolve
EvoX
CostAda
18 16 14 0.0 0.5 1.0 Cumulative cost / B
Cumulative cost / B
20
0.08 Step cost / B
1/min-max ratio
22
0.06 0.04 0.02 0.00
20
40 60 Iteration
80
1.0 0.8 0.6 0.4 0.2 0.0
20
40 60 Iteration
80
Figure 9: Objective and cost trajectories for MinMaxDist (n=16, d=2) under GLM-5.
27
5.5 5.0 4.5
CostAda
0.06 0.04 0.02 0.00
0.0 0.5 1.0 Cumulative cost / B
EvoX
Cumulative cost / B
6.0 Step cost / B
1/min-max ratio
AdaEvolve
15
1.0 0.8 0.6 0.4 0.2 0.0
30 45 60 Iteration
15
30 45 60 Iteration
Figure 10: Objective and cost trajectories for MinMaxDist (n=14, d=3) under GLM-5. AdaEvolve
EvoX
CostAda
2.4 Step cost / B
c3
2.0 1.8 1.6
Cumulative cost / B
0.125
2.2
0.100 0.075 0.050 0.025 0.000
0.0 0.5 1.0 Cumulative cost / B
15 30 Iteration
1.0 0.8 0.6 0.4 0.2 0.0
45
15 30 Iteration
45
Figure 11: Objective and cost trajectories for Third Autocorrelation under GLM-5.
0.04
0.60 0.55 0.50
EvoX
CostAda
Cumulative cost / B
0.05
0.65
Step cost / B
composite score
AdaEvolve
0.70
0.03 0.02 0.01
0.45
0.00
0.0 0.5 1.0 Cumulative cost / B
20
40 60 Iteration
1.0 0.8 0.6 0.4 0.2 0.0
80
20
40 60 Iteration
80
Figure 12: Objective and cost trajectories for Signal Processing under GLM-5. AdaEvolve
Cumulative cost / B
Step cost / B
sum radii
2.2
CostAda
0.125
2.6 2.4
EvoX
0.100 0.075 0.050 0.025
2.0 0.0 0.5 1.0 Cumulative cost / B
0.000
20
40 60 Iteration
80
1.0 0.8 0.6 0.4 0.2 0.0
20
40 60 Iteration
80
Figure 13: Objective and cost trajectories for Circle Packing under GPT-5.4.
28
AdaEvolve
EvoX
CostAda
0.08
2.325 2.300 2.275 2.250 0.0 0.5 1.0 Cumulative cost / B
Cumulative cost / B
Step cost / B
radii sum
2.350 0.06 0.04 0.02 0.00
20
40 60 Iteration
1.0 0.8 0.6 0.4 0.2 0.0
80
20
40 60 Iteration
80
Figure 14: Objective and cost trajectories for Circle Packing Rect under GPT-5.4. AdaEvolve
0.015
Cumulative cost / B
0.020
CostAda
0.10 Step cost / B
min. area
0.025
EvoX
0.08 0.06 0.04 0.02
0.010
0.00
0.0 0.5 1.0 Cumulative cost / B
15
1.0 0.8 0.6 0.4 0.2 0.0
30 45 60 Iteration
15
30 45 60 Iteration
Figure 15: Objective and cost trajectories for Heilbronn Convex under GPT-5.4. AdaEvolve
0.00 0.0 0.5 1.0 Cumulative cost / B
Cumulative cost / B
Step cost / B
min. area
0.01
CostAda
0.06
0.03 0.02
EvoX
0.04
0.02
0.00
20
1.0 0.8 0.6 0.4 0.2 0.0
40 60 Iteration
20
40 60 Iteration
Figure 16: Objective and cost trajectories for Heilbronn Triangle under GPT-5.4. AdaEvolve
16 15 14 13 0.0 0.5 1.0 Cumulative cost / B
Cumulative cost / B
17
CostAda
0.08 Step cost / B
1/min-max ratio
18
EvoX
0.06 0.04 0.02 0.00
20
40 60 Iteration
80
1.0 0.8 0.6 0.4 0.2 0.0
20
40 60 Iteration
80
Figure 17: Objective and cost trajectories for MinMaxDist (n=16, d=2) under GPT-5.4.
29
4.6 4.5 4.4
Step cost / B
1/min-max ratio
4.7
CostAda
0.06 0.04 0.02 0.00
0.0 0.5 1.0 Cumulative cost / B
EvoX
Cumulative cost / B
AdaEvolve
20
40 60 Iteration
1.0 0.8 0.6 0.4 0.2 0.0
80
20
40 60 Iteration
80
Figure 18: Objective and cost trajectories for MinMaxDist (n=14, d=3) under GPT-5.4.
AdaEvolve
EvoX
CostAda
c3
1.8 1.7 1.6
0.08 Step cost / B
1.9
Cumulative cost / B
2.0
0.06 0.04 0.02
1.5 0.00
0.0 0.5 1.0 Cumulative cost / B
15
30 45 Iteration
1.0 0.8 0.6 0.4 0.2 0.0
60
15
30 45 Iteration
60
Figure 19: Objective and cost trajectories for Third Autocorrelation under GPT-5.4.
AdaEvolve
0.6
0.02 0.01
0.5 0.0 0.5 1.0 Cumulative cost / B
0.00
CostAda
Cumulative cost / B
0.7
0.03 Step cost / B
composite score
0.8
EvoX
20
40 60 Iteration
1.0 0.8 0.6 0.4 0.2 0.0
20
40 60 Iteration
Figure 20: Objective and cost trajectories for Signal Processing under GPT-5.4.
J
B UDGET A DHERENCE D IAGNOSTICS
The budget protocol evaluates each run at the first completed iteration whose cumulative search-side cost reaches the nominal budget. Realized spending therefore includes the tail of the crossing iteration. A binary out-of-budget indicator is always one at this point and carries no information. We instead report the realized crossing cost AVG C OST and the relative excess OVERSHOOT R ATIO. Table 14 gives both statistics for each backbone and method. All three methods cross within 1.1–2.5% of the nominal budget on average, and no run exceeds it by more than 8.6%. Under GLM-5, CostAda has the smallest average crossing cost and overshoot. The closely matched realized spending rules out unequal cost at the measurement point as an explanation for the quality differences in Section 5.3. The residual excess reflects the tail of one crossing iteration. 30
Table 14: Realized spending at the nominal-budget crossing. AVG C OST reports Mean ± Std of the realized cumulative search-side cost at the first completed iteration reaching the nominal budget. OVERSHOOT R ATIO is the relative excess over that budget. GLM-5 and GPT-5.4 statistics each aggregate all eight benchmarks (24 runs per method). The table is a validity diagnostic for the budget-matched comparison rather than a performance ranking, so no entry is marked as best. Backbone
Method
AVG C OST
Mean OVERSHOOT R ATIO
Max OVERSHOOT R ATIO
GLM-5 (B=1)
AdaEvolve EvoX CostAda
1.021 ± 0.019 1.025 ± 0.022 1.017 ± 0.022
2.1% 2.5% 1.7%
8.0% 8.6% 7.1%
GPT-5.4 (B=5)
AdaEvolve EvoX CostAda
5.092 ± 0.068 5.053 ± 0.064 5.103 ± 0.081
1.8% 1.1% 2.1%
5.6% 6.2% 6.8%
K
M ARGINAL S TEP -E FFICIENCY D IAGNOSTICS
Figures 21 and 22 relate realized search-side spending to best-so-far normalized-score improvements. Unlike the cumulative trajectories, these diagnostics ask whether a method spends budget on steps that change the incumbent. A lower share indicates less spending without improvement. Across the single runs shown under GLM-5, CostAda spends the smallest share of normalized search cost on steps without a best-so-far improvement. The share is 0.84, compared with 0.87 for EvoX and 0.88 for AdaEvolve. CostAda also attains the highest total gain per unit of normalized budget at 0.63, compared with 0.54 for both baselines. Under GPT-5.4, CostAda again has the smallest no-improvement cost share at 0.88, compared with 0.91 for EvoX and 0.89 for AdaEvolve. CostAda’s total gain per unit of normalized budget is 0.53, compared with 0.54 for EvoX and 0.48 for AdaEvolve. Across both backbones, the no-improvement cost share provides the consistent separation among the three controllers. The plotted values diagnose individual runs rather than provide run-averaged estimates. The cutoff and normalized-AUC tables carry the aggregate budget-efficiency claim. In both figures, the left panel reports the share of realized search cost spent on steps without a best-so-far normalized-score improvement, where lower is better. The right panel reports total best-so-far normalized-score gain per unit of nominal budget, where higher is better. Because the panels compare point estimates rather than bar lengths, their labeled axes are zoomed to the range of the three method means to make the small between-method differences directly visible. No-improvement cost share ↓
Normalized score gain per budget ↑
0.870 0.855
0.630
0.64
0.869
Gain / budget
Cost share
0.8850.878
0.843
0.840
0.60 0.560.545
0.543
0.52 AdaEvolve
EvoX
CostAda
AdaEvolve
EvoX
CostAda
Figure 21: Step-level budget efficiency under GLM-5. Method means over eight benchmarks, with exact values annotated, from one run per benchmark at nominal budget B=1.
31
No-improvement cost share ↓
0.538
0.906 Gain / budget
Cost share
0.91
Normalized score gain per budget ↑
0.900.893 0.89
0.883
0.88 AdaEvolve
0.528
0.54 0.52 0.50
0.485
0.48 EvoX
CostAda
AdaEvolve
EvoX
CostAda
Figure 22: Step-level budget efficiency under GPT-5.4. Method means over eight benchmarks, with exact values annotated, from one run per benchmark at nominal budget B=5.
32