EarlyEval: Cheaper Agent Evaluation via Early Outcome Prediction
Yuling Shi, Zhensu Sun, Junsen Dong, Chengcheng Wan, David Lo, Xiaodong Gu
cs.CL
2026-09-03
Paired LightGBM heads halt agent rollouts early. On three benchmarks they cut 13–26% of steps and up to 44.1% input tokens, with 1–2pp Pass@1 drift and rank ρ ≥ 0.959.
A full pass of a frontier model on an agent benchmark now costs hundreds to thousands of dollars. On the OpenHands Index, SWE-bench Verified sits around $715 to $935 per pass; SWE-bench Multimodal reaches $2,270. Teams re-run these suites after every prompt or scaffold tweak, so the bill becomes a brake on iteration.
Prior work distills the benchmark: keep fewer tasks, still run each retained task to the end. EarlyEval cuts cost inside a task. The claim is that success or failure is often readable from the partial trajectory. Once the agent lands the correct one-line fix, later test churn is wasted. Once it retries the same edit against an unchanged error, failure is already on the page.
Offline, EarlyEval trains a pair of LightGBM classifiers on historical trajectories. Online, it scores every step and stops when either head crosses a calibrated threshold. Features come in three families:
TerminalBench and Toolathlon ship no gold patches, so those runs drop the reference family. Success and failure heads are trained separately because the evidence is asymmetric; if both stay low, the agent continues. Raw scores are Platt-scaled. Higher thresholds wait longer and miss less. Tree inference is sub-millisecond on CPU.
The pool exceeds 21,000 labeled trajectories: 16 agents and 7,805 runs on SWE-bench Verified; 37 configurations and 6,757 on TerminalBench; 22 models and 7,116 on Toolathlon. Evaluation is leave-one-agent-out. TerminalBench adds two leakage walls: no same base model in training, or no same scaffold.
The recommended operating point is the most aggressive threshold that keeps mean |Pass@1| distortion near two points.
| Setting | Steps saved | Input tokens | Output tokens | Δ\ | Pass@1\ | Spearman ρ | |
| SWE-bench Verified @0.95 | 26.0% | 32.7% | 28.7% | 1.1pp | 0.991 | ||
| Toolathlon @0.90 | 23.0% | 44.1% | 29.4% | 0.9pp | 0.994 | ||
| TerminalBench, no same model @0.90 | 25.4% | 42.7% | 27.9% | 2.1pp | 0.959 | ||
| TerminalBench, no same scaffold @0.85 | 17.7% | 29.2% | 17.4% | 2.0pp | 0.994 |
The failure head is stable: 96.7% precision on SWE-bench, 96.6% on Toolathlon. The success head is reliable only on SWE-bench (about 88%–94%). On Toolathlon it barely fires at high thresholds; on TerminalBench without the same scaffold, precision falls to about 69%. Dual-threshold step savings almost equal the sum of the two heads, so they rarely fire on the same run.
Ablating the behavioral family drops coverage from 34.8% to 23.4% and step savings from 26.0% to 16.4%. Dropping reference features barely hurts. LightGBM beats an MLP, linear models, and a LoRA-tuned Qwen-0.5B judge. The judge saves 17.9% of steps at 90.7% accuracy, but a model forward pass at every step eats the compute EarlyEval is trying to recover.
This is a second knife next to "evaluate fewer tasks": the tasks you keep can still stop early. Rankings hold. On SWE-bench, 81% of 16 models keep their exact rank. If a benchmark already has a public submission pool, the classifiers are cheap to train and cheap to run.
Failure is easier to call than success. For leaderboard audits, using the failure head to cut doomed rollouts is the practical default.
A cold benchmark with no historical trajectories cannot train the classifiers. Scaffolds generalize worse than base models; a new orchestration rhythm shifts the behavioral features. The success head mostly sits out on gold-free, messier tool-use suites, so deployed systems will mostly stop failures.
The authors block leakage with task-partitioned leave-one-agent-out. External validity still depends on trajectory format matching the training distribution. Token bills are not linear in steps, though input-token savings exceed step savings, which matches truncating bloated tails.
Thresholds are chosen after seeing the trade-off. Treat them as a knob, not as a hyperparameter-free plug-in.