Where Should the Evaluation Budget Go in LLM-Driven Agent Scaffold Evolution?

Sichun Luo; Yi Huang; Mukai Li; Haochen Luo; Guanzhi Deng; Haibo Wang; Jian Xu; Zefa Hu

cs.LGOct 27, 2026

Where Should the Evaluation Budget Go in LLM-Driven Agent Scaffold Evolution?

Authors: Sichun Luo, Yi Huang, Mukai Li, Haochen Luo, Guanzhi Deng, Haibo Wang, Jian Xu, Zefa Hu,

Organizations: The University of Hong Kong · JIUTIAN Research, China Mobile · City University of Hong Kong · Carnegie Mellon University ·

Abstract

Large language model (LLM)-driven agent scaffold evolution improves agent workflows through iterative candidate generation and evaluation. Evaluation both guides subsequent search and determines the final scaffold, but evaluating every candidate on the full task set incurs substantial execution costs. We investigate how evaluation budgets can be allocated across these two roles. Our experiments show that sparse feedback can sustain productive evolution, while additional targeted evaluation improves final selection. Replay analyses further show that shared informative items and a common scoring reference support comparisons among closely matched candidates. Motivated by these findings, we propose \method, an evaluation allocation framework that combines sparse search-time feedback with targeted final confirmation. A short fully evaluated warm-up establishes a shared informative core and calibrates a response model whose item parameters remain fixed during search. After search, \method refits the model and applies paired successive halving, reusing accumulated observations and executing only missing evaluations. Across four benchmarks and two evolution frameworks, \method achieves higher mean performance than full evaluation in most settings while using approximately half as many evaluation cells.

Figures & tables

Benchmark	SEARCH	DEV	TEST
HotpotQA	300	150	300
HoVer	300	150	300
DROP	300	150	300
IFBench	300	150	294

Table 1. Benchmark splits. SEARCH is used by the evaluators during evolution and selection, DEV only for the audit, and TEST only to score the selected programs.

Figure 1. Evolution trajectories under different evaluation strategies on DROP and HotpotQA. Curves show mean candidate scores on a shared audit set over successive 10-generation windows.

Figure 2. Effect of search-time feedback and final selection on DROP and HotpotQA. We compare the native selection rule with successive halving (SH) across three search strategies. Percentages indicate the additional evaluation cost of SH relative to the full-evaluation budget.

Figure 3. Overview of EvalAlloc . The framework consists of three stages: (1) core calibration using fully evaluated warm-up candidates, (2) sparse search-time evaluation with a shared informative core and fixed response model, and (3) warm-started successive halving that reuses accumulated observations for final scaffold selection.

Framework	Method	DROP		HotpotQA		HoVer		IFBench		Average
Framework	Method	Score $\uparrow$	Cost $\downarrow$	Score $\uparrow$	Cost $\downarrow$	Score $\uparrow$	Cost $\downarrow$	Score $\uparrow$	Cost $\downarrow$	Score $\uparrow$	Cost $\downarrow$
ShinkaEvolve	Skip Eval	$0.7674_{\pm 0.1046}$	0.0	$0.4633_{\pm 0.4014}$	0.0	$0.3933_{\pm 0.0961}$	0.0	$0.3917_{\pm 0.0741}$	0.0	$0.5039$	0.0
	Successive Halving	$0.8738_{\pm 0.0248}$	22.1	$0.7089_{\pm 0.0139}$	22.0	$0.6844_{\pm 0.0948}$	22.5	$0.4433_{\pm 0.0098}$	21.2	$0.6776$	22.0
	Random	$0.8629_{\pm 0.0083}$	42.5	$0.7244_{\pm 0.0158}$	45.6	$0.7156_{\pm 0.0443}$	43.8	$0.4603_{\pm 0.0332}$	37.7	$0.6908$	42.4
	Cascade	$0.8643_{\pm 0.0139}$	39.6	$0.7178_{\pm 0.0135}$	53.3	$\mathbf{0.7289}_{\pm 0.0375}$	54.8	$0.4683_{\pm 0.0214}$	38.5	$0.6948$	46.6
	Full	$0.8832_{\pm 0.0155}$	77.1	$0.7133_{\pm 0.0067}$	92.5	$0.7267_{\pm 0.0176}$	92.5	$0.4660_{\pm 0.0290}$	75.4	$0.6973$	84.4

Table 3. Test performance of the program selected under each evaluation strategy. For each benchmark, Score reports the TEST mean over three seeds, with standard deviation shown as a subscript. Cost (%) is the evaluation spent during search and final selection, as a share of evaluating every proposal on all 300 search items (

80\times 300

cells for ShinkaEvolve,

81\times 300

for AdaEvolve); programs that fail to load or error on every evaluated item cost nothing. Average reports the unweighted mean over the four benchmarks. The highest Score per benchmark and on average within each framework is bold.

Figure 4. Effect of warm-up length on DROP with ShinkaEvolve under a fixed search-stage budget. Left: evaluation cost breakdown for different numbers of fully evaluated warm-up candidates. Right: corresponding performance, with Full and Random shown as references.

Figure 5. Effect of search-time evaluation budget on DROP with ShinkaEvolve. Left: evaluation cost breakdown across warm-up, sparse search, and final selection. Right: Performance versus total evaluation cost under different search budgets.

Figure 6. Effect of final selection strategies on TEST performance and evaluation cost across four benchmarks and their average. We compare selection without SH, SH over the top 30 candidates, and SH over all candidates, using the same search runs. Full evaluation is shown as a reference.

Method	ShinkaEvolve		AdaEvolve
Method	Cells	Tokens	Cells	Tokens
Full	100.00%	100.00%	100.00%	100.00%
Successive Halving	26.26%	27.50%	23.26%	15.10%
Random	50.44%	55.18%	49.69%	43.66%
Cascade	54.83%	66.32%	56.47%	54.50%
EvalAlloc	52.13%	64.76%	46.83%	45.47%

Table 5. Evaluation-cell and executor-token (prompt and completion) costs of search and final selection, relative to Full (100%). Each entry averages the per-benchmark shares over the four benchmarks; programs that fail to load or error on every evaluated item cost nothing.

Figure 7. Performance with alternative proposer and executor models on ShinkaEvolve. Left: IFBench with a gpt-oss-120b proposer. Right: DROP with a Llama-3.1-8B-Instruct executor. Bars show the mean over three seeds, with standard deviation as error bars. Percentages indicate evaluation cost relative to the nominal full budget.

LLM Agent Evaluation

Large language model agent evaluation measures whether tool-using systems complete tasks reliably, safely, and efficiently.

See all 1,217 papers

RoboPhD: Evolving Diverse Complex Agents Under Tight Evaluation Budgets
Apr 6, 2026Andrew Borthwick, Stephen Ash, Anthony GalczakLLMs for Evolutionary Optimization Large Language Model-Guided Optimization
Independent Researchers
EvalBuilder: Can LLMs Build Efficient Benchmarks?
Oct 14, 2026Huaisheng Zhu, Hangfan Zhang, Teng Xiao +5Benchmark Construction AI Agent Benchmarks
Meituan · Pennsylvania State University · Allen Institute for AI (AI2) +2
EvoProbe: Evaluation-Driven Benchmark Evolution for LLM Agents
Oct 14, 2026Qianhong Guo, Wei Xie, Xiaofang Cai +3LLM Agent Evaluation AI Agent Benchmarks
College of Computer Science and Technology, National University of Defense Technology · Institute of Information Engineering, Chinese Academy of Sciences

Apr 6, 2026J/K move · Enter open · S save

RoboPhD: Evolving Diverse Complex Agents Under Tight Evaluation Budgets

Andrew Borthwick, Stephen Ash, Anthony Galczak

Independent Researchers

LLMs for Evolutionary Optimization Large Language Model-Guided Optimization Self-Evolving Agents AI Agent Benchmarks

Open paper AskPDF arXiv

2026 has brought an explosion of interest in LLM-guided evolution of agentic artifacts, with systems like GEPA and Autoresearch demonstrating that LLMs can iteratively improve prompts, code, and agent architectures across diverse domains. As adoption accelerates, a central question emerges: given the same information, the same seed agent, and the same objective, which optimization algorithm yields the best results under the same evaluation budget? This question becomes critical when evaluations are expensive, such as when they require human judgment or multiple LLM calls. We present the first systematic comparison of three optimization paradigms -- Elo tournament selection (RoboPhD), Pareto-based selection (GEPA), and greedy hill-climbing (Autoresearch) -- across four benchmarks spanning abstract reasoning, cloud scheduling, SQL generation, and financial QA, all under a fixed budget of 1,500 evaluations. RoboPhD introduces validation-free evolution: instead of splitting the budget between training and validation, it uses Elo competition on training data to simultaneously evaluate agents and drive evolution. All three systems receive seed agents with diagnostic print() statements that evolution can grow, enabling self-instrumenting agents that develop increasingly informative diagnostics for the benefit of their evolutionary successors. Using a single default configuration, RoboPhD outperforms both GEPA and Autoresearch on three of four benchmarks, losing only on the simplest task, where the winning solution (from our Autoresearch adaptation) required under 90 lines of code. On ARC-AGI, RoboPhD evolves a 22-line seed agent into a 1,013-line multi-strategy system, improving accuracy from 27.8% to 65.8% using Gemini 3.1 Flash Lite as the solver. We release RoboPhD as a versatile toolkit under the MIT license with a simple optimize_anything() API for evolving diverse complex agents.

Abstract

LLM Agent Evaluation

Explore similar work

RoboPhD: Evolving Diverse Complex Agents Under Tight Evaluation Budgets

EvalBuilder: Can LLMs Build Efficient Benchmarks?

EvoProbe: Evaluation-Driven Benchmark Evolution for LLM Agents