EarlyEval: Cheaper Agent Evaluation via Early Outcome Prediction

Summary

The paper tackles the cost of LLM-agent benchmarking not by shrinking benchmarks but by stopping individual runs early once their outcome becomes predictable. EarlyEval trains, per benchmark, a pair of LightGBM classifiers — one for impending success, one for impending failure — over prefix features drawn from historical, outcome-labeled trajectories: behavioral statistics, TF-IDF/SVD text embeddings, and (on SWE-bench Verified only) reference-solution overlaps. At every step of a new agent's run, calibrated probabilities are compared to fixed thresholds; crossing either halts the run and records the predicted score. Evaluation uses leave-one-agent-out across SWE-bench Verified (16 agents, 7,805 trajectories), TerminalBench (37, 6,757), and Toolathlon (22, 7,116). At tuned thresholds the method cuts 13%–26% of steps, up to 44.1% input and 29.4% output tokens (Toolathlon, 0.90 threshold), with absolute resolve-rate deviation within ~2.1 pp and Spearman ρ 0.959–0.994. Savings derive almost entirely from the failure predictor: success coverage collapses to near zero on Toolathlon. Feature ablations show behavioral features dominate and textual ones add almost nothing. Limitations: no confidence intervals or significance tests; operating points tuned on the same data used to report fidelity; task-level reuse means per-benchmark retraining; and a small systematic under-crediting of agents persists.