Source-linked AI summary
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, Junlan Feng, Qi Liu
TL;DR
Evaluating every candidate scaffold on the full task set is costly, even though evaluation guides both evolution and final selection. The paper proposes EvalAlloc, which combines sparse search-time feedback with targeted final confirmation; across four benchmarks and two frameworks, it reports competitive performance at about half the evaluation-cell cost of Full.
Problem
Full evaluation across many candidate scaffolds is costly, while evaluation must both guide subsequent search and determine which scaffold is returned.
Source: §1 · p. 1Method
EvalAlloc uses a shared informative core and fixed search-time response model, then reuses observations in warm-started paired successive halving for final selection.
Source: §1 · pp. 1–2Results
Takeaways & Limitations
Evaluation effort can be allocated according to its distinct roles in search and final selection.
Source: §7 · p. 8
Abstract
from arXiv · showhide
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.
1 Introduction
Scaffold evaluation is costly and serves two distinct roles: guiding evolution and choosing the final scaffold. The paper studies how to allocate a limited budget across these roles, then proposes EvalAlloc to combine sparse search feedback with targeted final selection.
1 Introduction
- Evaluating every candidate across the full task set is costly, while search feedback and final selection require different kinds of evaluation evidence.Search needs inexpensive, comparable feedback; final selection needs reliable discrimination among competitive candidates.Source: §1 · p. 1
- Sparse evaluation can sustain productive evolution, but removing feedback substantially degrades search quality; shared informative items and a common scoring reference improve comparisons among closely matched candidates.Search gains concentrate in early iterations, while final selection remains sensitive to uncertainty among top candidates.Source: §1 · p. 1
- EvalAlloc combines a shared informative core and fixed search-time response model with warm-started paired successive halving for final selection.It reuses search observations and executes only missing evaluations; after search, it refits the response model.Source: §1 · pp. 1–2
- Across four benchmarks and two evolution frameworks, EvalAlloc uses approximately half as many evaluation cells as Full while achieving competitive or higher mean performance.Ablations identify informative item allocation and final selection as its main contributors.Source: §1 · pp. 1–2
2 Related Work
Prior work studies automated scaffold and workflow evolution, efficient LLM evaluation, and sequential candidate selection. This paper focuses on how limited evaluation resources serve both feedback-driven evolution and final scaffold selection.
LLM-Driven Agent and Program Evolution
- ADAS, AFlow, ShinkaEvolve, and AdaEvolve [4] automate agent or workflow design, with the latter approaches using evaluation feedback to refine programs.The paper shifts attention from candidate generation and evolutionary optimization to evaluation for both evolutionary decisions and final selection.Source: §2 · p. 2
Efficient LLM Evaluation
Evaluation Allocation and Candidate Selection
- Successive halving, Hyperband, irace, and common random numbers motivate sequential allocation and shared-condition comparisons.The paper applies these ideas across two stages: inexpensive comparable feedback during evolution and reuse of observations for final selection.Source: §2 · p. 2
3 Problem Formulation
The formulation distinguishes search-time evaluation, which informs evolution, from final selection, which chooses a scaffold and may gather more observations. It frames allocation as a policy over evaluation cells and the returned scaffold's expected outcome.
Benchmark Splits
- In Table 1, SEARCH is used by evaluators during evolution and selection, DEV only for the audit, and TEST only to score the selected programs.Source: Table 1 · p. 2
Agent Scaffold Evaluation
- Each scaffold–item execution is an evaluation cell, and evaluating each benchmark item once yields the full-set reference score.The passage defines expected fitness and the full-set reference score, though the displayed expressions are not fully present here.Source: §3 · p. 2
LLM-Driven Agent Scaffold Evolution
- Search-time evaluation supplies candidate fitness feedback for archive updates and subsequent proposals, while final selection chooses a scaffold from the generated candidates and may collect additional observations.Search observations can be reused during final selection.Source: §3 · p. 2
Cost–Performance Objective
- The allocation policy governs observations in both stages, and total evaluation cost counts executed cells; the expectation covers candidate-generation, evaluation, and allocation randomness.The objective is framed under a given evaluation budget.Source: §3 · p. 2
4 Investigation
Across four benchmarks and two evolution frameworks, the investigation finds that sparse feedback can sustain search, but reliable final selection and archive decisions require targeted comparison under comparable scoring.
4.1 Setup
- The study uses four benchmarks, two evolution frameworks, and 80 proposals per run, with three seeds per setting; SEARCH supports evolution and selection, while TEST is reserved for selected scaffolds.The benchmarks are HotpotQA, HoVer, DROP, and IFBench.Source: §4.1 · p. 2
4.2 Search Needs Feedback, but Not Full Evaluation
- Without feedback, candidate quality remains low with limited improvement, while random partial evaluation keeps it close to Full on DROP and HotpotQA.The trajectories show that full evaluation of every candidate is not necessary to sustain improvement.Source: §4.2 · p. 3, Figure 1 · p. 3
- Search improvements concentrate in early iterations, motivating early calibration and sparse feedback afterward without establishing that this temporal allocation is optimal.Source: §4.2 · p. 3
4.3 Comparability Depends on Shared Informative Observations
- Shared informative items improve close-candidate comparisons over random or unshared informative items, where close-pair agreement is lower and archive regret higher.The replay uses a 10-candidate fully evaluated warm-up, then 60 of 300 SEARCH items per candidate under matched budgets; Table 2 averages 24 trajectories and three replays each.Source: §4.3 · p. 3, Table 2 · p. 4
- A fixed response model places sparse and warm-up candidates on a common full-SEARCH scale, reducing archive regret even when raw means have similar Spearman correlation to model-completed scores.Raw means can therefore rank individual candidates similarly while producing less reliable archive decisions.Source: §4.3 · p. 3
4.4 Final Selection Needs Confirmation
- Successive halving improves final performance most when search feedback is absent; gains are smaller and less consistent with random partial evaluation, and limited after full evaluation.The comparison uses the same candidate pools under different search-time strategies.Source: Figure 2 · p. 3, §4.4 · p. 4
5 Method
EvalAlloc separates inexpensive, comparable search-time feedback from precise final selection, reusing observations across both stages. It establishes a shared reference with a fully evaluated warm-up, then concentrates additional evaluation on final scaffold selection.
5 Method
- EvalAlloc splits evaluation between sparse search-time feedback and a separate selection stage that reuses search observations, while leaving the native framework’s proposal and archive policies unchanged.The framework has three stages: core calibration, shared-core evolution, and warm-started selection.Source: §5 · p. 4, Figure 3 · p. 5
5.1 Core Calibration
- A fully evaluated warm-up identifies informative items and calibrates a response model; its item parameters and candidate prior stay fixed during search to preserve a common scoring reference.The warm-up also supplies directly observed full-set scores, while item-level outcomes form the calibration matrix.Source: §5.1 · p. 4
5.2 Shared-Core Evolution
- Each search candidate is evaluated on a shared informative core plus candidate-specific items, and observed outcomes update the adaptive-item statistics without changing the core.The fixed response model predicts unobserved outcomes to estimate full-set fitness on the native framework’s scoring scale; observed outcomes are cached for selection.Source: §5.2 · pp. 4–5
5.3 Warm-Started Selection
- Warm-started successive halving reuses cached search observations and executes only missing items, progressively concentrating evaluation on surviving candidates.After the first round, regression-adjusted scores address differing item difficulty; cross-fitting refits the response model, and the final pick uses observed full-set outcomes.Source: §5.3 · pp. 5–6
6 Experiments
The experiments compare evaluation-budget strategies, test EvalAlloc’s components, and examine how budget choices affect search, final selection, and execution cost. Across benchmarks and evolution frameworks, EvalAlloc achieves similar or better mean TEST performance than Full with roughly half the evaluation cells.
6.1 Setup
- EvalAlloc’s default assigns 30% of the full budget to search, with 10 fully evaluated warm-up candidates, then uses four successive-halving rounds for final selection.Baselines include no evaluation, final-only SH, random 50% sampling, cascade promotion, and Full evaluation of all SEARCH items.Source: §6.1 · p. 6
6.2 Main Results
- Across both evolution frameworks and all four benchmarks, EvalAlloc matches or slightly exceeds Full’s mean TEST score while using approximately half as many evaluation cells.Source: §6.2 · pp. 6–7
6.3 Ablation Study
- Ablations identify informative-item selection and final confirmation as the main contributors; random items hurt most, while removing the response model has smaller, less consistent effects.Source: §6.3 · p. 7, Table 4 · p. 7
6.4 Analysis
- With a fixed search-stage budget on DROP, the default 10-candidate warm-up has the highest mean, but differences are within seed variation and longer warm-ups can thin later feedback.Source: §6.4 · p. 7, Figure 4 · p. 8
- On DROP, the 30% search budget has the highest observed mean TEST performance, while 20% costs less with comparable performance; more search evaluation does not consistently help.Source: §6.4 · p. 7, Figure 5 · p. 8
- Across four benchmarks, successive halving improves TEST performance over direct selection; applying it to the top 30 candidates captures most gains at lower cost.Source: §6.4 · p. 7, Figure 6 · p. 8
- On ShinkaEvolve, EvalAlloc uses 52.13% of Full’s cells but 64.76% of its tokens; higher-scoring candidates and high-variability items tend to consume more tokens.Source: §6.4 · pp. 7–8, Table 5 · p. 8
- With alternative proposer or executor models, EvalAlloc remains competitive with fewer evaluation cells, though strategy performance varies across model configurations.The alternatives are a gpt-oss-120b proposer on IFBench and a Llama-3.1-8B-Instruct executor on DROP.Source: Figure 7 · p. 8, §6.4 · p. 8
7 Conclusion
EvalAlloc allocates evaluation effort differently for evolutionary search and final scaffold selection. Across four benchmarks and two frameworks, it achieves competitive performance with about half the evaluation cells used by Full.
- Sparse informative feedback and shared items with a stable scoring reference support comparable decisions during scaffold evolution.Source: §7 · p. 8
- Across four benchmarks and two evolution frameworks, EvalAlloc achieves competitive performance while using approximately half as many evaluation cells as Full.Source: §7 · p. 8
- The results support allocating evaluation effort according to its distinct roles in search and final selection.Source: §7 · p. 8