Efficient Benchmarking of AI Agents¶

🕒 Published (v1): 2026-03-24 22:17 UTC · Source: Arxiv · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

Full AI agent benchmark evaluation is prohibitively expensive (~$40K for one comprehensive leaderboard run) because each task requires interactive, multi-step rollouts. This paper shows that selecting only tasks with 30–70% historical pass rates reduces evaluation cost by 44–70% while preserving agent rank ordering (Spearman $\rho \geq 0.87$ worst-case), even under scaffold and temporal distribution shift.

Problem¶

Static benchmark-reduction techniques from NLP (e.g., anchor-point selection, IRT-based pruning) cannot be directly applied to agent benchmarks because agent performance depends not only on the underlying model but on the scaffold — the harness governing tool use, memory, retry logic, and execution flow. Reducing an agent benchmark must therefore generalize across both unseen scaffolds and future agent releases, not just unseen models. Additionally, agent benchmarks start small (dozens to hundreds of tasks) and each task costs a full agent loop rather than a single prompt–response pass, making naive reduction methods statistically fragile.

Method¶

The core proposal is the Mid-Range Difficulty Filter (MR): retain only tasks whose historical pass rate $p \in [0.30, 0.70]$. The motivation is Item Response Theory (IRT): under a Bernoulli response model with logistic link, the Fisher information about latent agent ability $\theta$ is $I(\theta) = p(1-p)$, maximized at $p=0.5$ and halved at $p \approx 0.15$ and $p \approx 0.85$. The 30–70% band is a practical tightening of the high-information region.

Task selection is deterministic and optimization-free — no training, no Ridge regression needed for ranking (only for score calibration). Evaluation uses five nested cross-validation protocols of increasing distributional shift: Within-Scaffold LOAO, LOAO, Random 80/20, LOSO (leave-one-scaffold-out), and Temporal expanding window. Competing strategies include Greedy forward selection (maximizing leave-one-agent-out $R^2$ under Ridge), random sampling, easiest-$k$, hardest-$k$, and stratified-$k$ — all matched to the same fold-specific budget $k$.

The key empirical finding exploited by the method: ranking fidelity (Spearman $\rho$, Kendall $\tau$) remains stable across distributional shift while score prediction ($R^2$) collapses, because affine distortions to the score scale leave orderings intact.

Key Contributions¶

Empirical demonstration of a robust asymmetry: $\rho = 0.90$–$0.96$ remains stable across all protocols while $R^2$ degrades from 0.90 to as low as 0.46 (average) under scaffold/temporal shift.
The Mid-Range Difficulty Filter (MR): a parameter-free, IRT-motivated task selection rule achieving highest mean $\rho = 0.94$ and worst-case $\rho = 0.87$ across 8 benchmarks and 5 evaluation protocols.
Reduction of evaluation task counts by 44–70% without meaningful loss of leaderboard rank fidelity.
Large-scale empirical study: 8 benchmarks, 33 scaffold types, 70+ model configurations, including Terminal-Bench 2.0 (101 agents, 23 scaffolds) and 7 HAL benchmarks.
Identification of why hard tasks are harmful: when agents universally fail, discrimination becomes impossible (Hardest-$k$: $\rho = 0.638$, $R^2 = -3.360$).

Results¶

MR achieves best or near-best ranking on 5 of 8 benchmarks across all protocols; mean $\rho = 0.94$, worst-case $\rho = 0.87$.
Greedy selection: mean $\rho = 0.842$, worst-case $\rho = 0.56$ — overfits and degrades under shift.
Random sampling: mean $\rho = 0.816$, worst-case $\rho = 0.54$ — high variance makes it unusable as a deployment strategy.
Hardest-$k$: catastrophic, $\rho = 0.638$, $R^2 = -3.360$.
Under LOSO (hardest shift), worst Kendall $\tau = 0.80$, meaning 90% of agent pairs are ranked correctly.
Per-benchmark MR $\rho$: Terminal-Bench 0.980, GAIA 0.946, SWE-bench 0.920, USACO 0.938, TAU-bench 0.944, CoreBench Hard 0.901, Online Mind2Web 0.921 (SciCode excluded: only 4 mid-range tasks).
Full HAL evaluation cost ~$46K total; per-agent cost median ~$800 across 8 benchmarks, up to $2,829 for GAIA with frontier models.

Limitations¶

MR requires sufficient historical pass-rate data to define the 30–70% band; benchmarks with few mid-range tasks (e.g., SciCode: 4 tasks) are excluded.
HAL benchmarks include only 2 scaffolds each, limiting scaffold-diversity evaluation on those datasets; most scaffold-shift evidence comes from Terminal-Bench.
Agent sample sizes on HAL are modest ($n = 13$–$38$), constraining statistical reliability of data-driven selection.
Score calibration ($R^2$) still degrades substantially under shift — MR only guarantees rank fidelity, not absolute score recovery.
The study does not address the cost of the initial full-benchmark run required to compute historical pass rates for bootstrapping.
Terminal-Bench cost data is not available at the same granularity as HAL, preventing cost estimation on that benchmark.

Relevance to Harnesses / Meta-Harnesses¶

This paper directly surfaces the scaffold (harness) as a first-class variable in agent evaluation, not a nuisance: the distribution shift problem is specifically scaffold-induced, meaning that a meta-harness governing tool use, retry logic, and execution flow has measurable, systematic effects on benchmark scores that are distinct from model capability. For researchers building or evaluating meta-harnesses, the finding that rank ordering is stable across scaffold changes (while absolute scores are not) provides a principled justification for lightweight comparative evaluation of harness designs using only mid-difficulty task subsets. The Greedy selection strategy's failure under scaffold shift is a concrete warning that task subsets optimized for one harness configuration may not transfer — a directly applicable constraint when designing harness-agnostic evaluation pipelines or when a meta-harness wraps multiple inner scaffolds.