EarlyEval: Cheaper Agent Evaluation via Early Outcome Prediction

AI summary

Overview

• Research area: LLM agent evaluation, benchmark efficiency, and cost reduction for agentic AI systems (Natural Language Processing / software engineering agents).
• Technical level: Intermediate. The framing is accessible, but the method assumes familiarity with LLM agents, benchmark scoring, gradient-boosted trees, and probability calibration.
• Scope: The paper introduces and evaluates EarlyEval, a framework that predicts an agent's final benchmark outcome from a partial trajectory and halts execution early, tested across three agentic benchmarks with more than 21,000 outcome-labeled trajectories from 75 agent configurations.

What This Paper Is About

Running an agentic benchmark is expensive: an agent takes many steps per task, every step issues at least one model call, and a single evaluation pass of a frontier model can cost hundreds to thousands of dollars. Prior work attacked this cost by benchmark distillation, which shrinks the number of tasks but leaves the cost of each retained task unchanged.

EarlyEval instead attacks the cost inside each task. Its core premise is that an agent's final outcome is usually evident from its intermediate behavior long before the run finishes, so the run can be stopped and the outcome predicted rather than executed to completion.

Key Contributions

1. A new efficiency axis called early outcome prediction. Rather than reducing the number of evaluation tasks, the paper formalizes inferring a final binary outcome from a partial trajectory so remaining steps need not be run. The authors position this as complementary to, not a replacement for, benchmark distillation.

2. EarlyEval, a lightweight plug-and-play framework. It trains a pair of LightGBM classifiers — a success predictor and a failure predictor — over a feature space spanning behavioral trajectory signals, textual context, and reference-solution metadata, and halts a run the moment either classifier crosses a calibrated confidence threshold.

3. A calibrated dual-threshold halting rule. Raw ensemble scores are recalibrated with Platt scaling so that success and failure thresholds carry comparable meaning, with thresholds that expose a tunable accuracy-versus-savings knob. The authors state this adds negligible per-step inference overhead.

4. Rigorous leave-one-agent-out evaluation on three benchmarks. SWE-bench Verified, TerminalBench, and Toolathlon were used, collecting more than 21,000 outcome-labeled trajectories from 16, 37, and 22 distinct agents respectively, with leakage controls for TerminalBench's heterogeneous scaffold/model pool.

Main Findings

• Substantial step and token savings. Across the three benchmarks, EarlyEval eliminates 13%–26% of agent steps and up to 44.1% of input tokens and 29.4% of output tokens, at 89%–97% prediction accuracy, while perturbing per-agent resolve rates by only one to two percentage points on average (Abstract).

• SWE-bench Verified at threshold 0.95. EarlyEval halts roughly 35% of runs at 95% prediction accuracy, eliminating 26% of execution steps along with 33% of input and 29% of output tokens, shifting each agent's measured resolve rate by 1.1 percentage points on average. The results table reports the same operating point as −26.0% steps, −32.7% input tokens, −28.7% output tokens, and |ΔPass@1| of 1.1%.

• Toolathlon at threshold 0.90. Step reduction of 23.0% with an absolute resolve-rate deviation of 0.9 percentage points.

• Rankings largely survive early stopping. On SWE-bench Verified, Spearman's ρ = 0.991 over all 16 agents, with 81% of agents unchanged in rank and only three adjacently ranked agents shifting by a single rank. TerminalBench achieved ρ = 0.959 (no same model in training; 59% unchanged) and ρ = 0.994 (no same scaffold in training; 70% unchanged). Toolathlon achieved ρ = 0.994 (70% unchanged). The Abstract summarizes this as ρ ≥ 0.959 across the non-SWE-bench benchmarks.

• Thresholds trade fidelity for savings monotonically. On SWE-bench Verified, lowering the threshold from 0.95 to 0.75 raises dual step reduction from 26.0% to 63.4% while |ΔPass@1| distortion grows from 1.1% to 4.1%.

• The failure predictor is the more robust of the two. At designated operating points, failure-predictor precision reaches 96.7% on SWE-bench, 89.4%–96.6% on TerminalBench, and 96.6%–99.4% on Toolathlon. The success predictor is highly reliable only on SWE-bench Verified (precision 88.3%–93.9% across thresholds), drops to 61.4%–69.0% on TerminalBench under the no-same-scaffold split, and its coverage collapses toward zero on Toolathlon at higher thresholds. Consequently, the paper ranks agents with the full dual mechanism on SWE-bench but with the failure predictor alone on TerminalBench and Toolathlon.

• The two predictors almost never fire on the same run. At nearly every operating point the dual step reduction equals the sum of the success-only and failure-only reductions (for example, −10.6% + (−15.4%) = −26.0% on SWE-bench Verified at 0.95), which the authors interpret as positive and negative evidence rarely coinciding within one trajectory.

• Unseen scaffolds are harder to model than unseen models. Withholding the held-out agent's scaffold degrades the success predictor more than withholding its base model: peak precision falls from 82.7% (no same model) to 69.0% (no same scaffold), and attainable dual step reduction shrinks from 25.4% to 17.7%. The authors attribute this to scaffolds dictating the structural rhythm of a trajectory.

• Behavioral signals carry most of the weight. The paper states that ablations show the framework leans primarily on reference-free behavioral signals, allowing it to operate on benchmarks that release no gold solutions — TerminalBench and Toolathlon both omit reference solutions, so the reference-solution feature family is disabled there.

• The motivating cost figures. Drawing on the OpenHands Index (figures retrieved June 2026), one evaluation pass over SWE-bench Verified's 500 tasks costs $715 (Claude 5), $760 (GPT-5.5), and $935 (Gemini 3.1 Pro). SWE-bench Multimodal's 517 tasks cost $2,270, $1,453, and $641 respectively — exceeding $2,200 for the most costly model and surpassing $1,000 for two of the three models.

• A concrete illustration of early predictability. In the OpenHands trajectory tianocore__edk2-pytool-library-372, the run spans 45 steps; the agent wrote a bug-reproducing script by step 20 and made its sole source-code fix at step 23. An observer with the ground truth could conclude success at step 23, recording the identical outcome at roughly half the cost.

• Not reported in the available content. The paper lists RQ3 (robustness to omitting specific feature families) and RQ4 (LightGBM versus alternative architectures on the cost–fidelity trade-off) as research questions, but the provided text is truncated before their results. No dollar-denominated savings from EarlyEval itself are reported; savings are expressed as percentages of steps and tokens.

Methodology in Plain English

The setup. An agent is defined as a scaffolding harness paired with a base LLM. For each benchmark, the authors collected complete historical trajectories from many such agents, each labeled with its ground-truth outcome (resolved or not).

Turning trajectories into training examples. Every trajectory is chopped into prefixes — the events from step 1 up to step k — and each prefix is paired with that trajectory's final label. So the model learns, from many partial runs, which partial states precede success and which precede failure. Trajectories shorter than 10 steps are discarded.

What the model looks at. Each prefix is converted into a fixed-length feature vector in three families:

• Behavioral features describe how the run is progressing — action counts at two granularities, properties of the most recent step, when key events (first edit, first test, first error) occurred, working-pattern signals such as reads-per-edit ratios and stalling or premature-submission indicators, and error/test status indicators. These are the reference-free signals the framework leans on most.
• Textual features encode the task description, the action history and latest action, and all environment feedback plus the latest feedback. Each block is vectorized separately with TF-IDF over word unigrams and bigrams and compressed with Truncated SVD: 64 dimensions for the prompt, 128 for actions, 128 for feedback.
• Reference-solution features apply only when a benchmark publishes gold patches (SWE-bench Verified). They describe the gold patch and measure how far the agent has converged toward it, via Jaccard overlap and hit counts on files, API symbols, and test names.

Two classifiers, not one. EarlyEval trains two LightGBM ensembles on the same features but inverted targets: one targets success (y=1), the other targets failure (1−y=1). The authors argue this lets positive and negative evidence accumulate independently, because success and failure are signaled by asymmetric behaviors, and it creates an explicit "unconfident" region where both outputs are low and the agent continues. Gradient-boosted trees were chosen because they can score a several-hundred-dimensional vector in well under a millisecond on a single CPU core — an LLM-based judge would cost as much as the execution being saved.

Calibration and halting. At each step of a new run, features are extracted and fed to both ensembles. Raw scores are recalibrated with Platt scaling — a one-dimensional logistic regression mapping the raw score to a calibrated probability — fitted on a held-out validation split. The run stops at the first step where the calibrated success probability reaches threshold s or the calibrated failure probability reaches threshold f. If both cross simultaneously, the chronologically earlier crossing wins. Calibration is monotonic, so it preserves ranking and AUC and only makes thresholds comparable.

Guarding against leakage. Trajectory pools are split by task, never by prefix, so all prefixes from one trajectory stay on the same side. Longer trajectories are down-weighted by 1/(T+1) so no trajectory dominates the loss. Most importantly, evaluation uses a leave-one-agent-out protocol: predictors for a held-out agent are trained only on the other agents' trajectories. For TerminalBench, where the pool is heterogeneous, two additional split settings are evaluated — one that removes every training trajectory sharing the held-out agent's base model, and one that removes every trajectory sharing its scaffold.

Implementation. Python on scikit-learn and LightGBM. TF-IDF uses a minimum document frequency of 5 and a vocabulary capped at 30,000 terms. Both predictors share a regularized configuration: learning rate 0.03, 31 leaves, maximum depth 6, minimum child samples 200, row and feature subsampling of 0.75 and 0.70, L1/L2 regularization weights of 0.5 and 10.0, up to 2,000 boosting rounds with early stopping after 50 rounds without validation improvement. A 15% validation split drives early stopping and calibration. A fixed random seed of 42 is used throughout.

Why This Matters

Impact on research. The paper opens an axis of evaluation efficiency that is orthogonal to benchmark distillation: distillation removes tasks, EarlyEval removes steps within tasks. If the method generalizes, the same benchmark, with the same scoring semantics, becomes materially cheaper to run — which directly affects how often researchers can iterate.

Real-world applications.

• Agentic regression testing in CI. Teams that re-run benchmarks after every prompt or scaffold change could cut between 13% and 26% of steps per run while keeping measured resolve rates within roughly two percentage points.
• Leaderboard and benchmark operations. With ρ of 0.991, 0.959, 0.994, and 0.994 across the evaluated settings, early-stopped leaderboards can largely reproduce full-run orderings at a fraction of the cost, and benchmark maintainers could offer capped-budget evaluation tiers.
• Evaluating expensive or proprietary benchmarks. Benchmarks with long rollouts and no public gold solutions can still be accelerated, since EarlyEval disables reference features on TerminalBench and Toolathlon and still works.
• Resource-constrained labs and academic groups. The paper explicitly frames several-hundred-dollar single-pass costs as putting frequent evaluation out of reach for many practitioners; a lower per-pass cost widens participation.

Industry relevance. The threshold parameter is a direct cost-versus-fidelity dial that a team can set to fit a budget, and the framework is described as plug-and-play with negligible per-step inference overhead because it runs on CPU-resident tree ensembles rather than an LLM judge. One practical caveat the paper surfaces for industry adoption: at most operating points the failure predictor, not the success predictor, is doing the reliable work — so a deployment that only watches for early success will capture much less of the savings, especially on non-SWE-bench workloads.

Future Directions

• Improving the success predictor outside SWE-bench. Its precision falls to 61.4%–69.0% on TerminalBench under the no-same-scaffold split and its coverage collapses toward zero on Toolathlon, which is why the authors fall back to failure-only ranking there. Closing this gap would unlock the dual mechanism's full

Authors’ abstract

Evaluating LLM agents is essential for guiding their development, yet it has grown prohibitively expensive: a single pass of a frontier model over an agentic benchmark can cost hundreds to thousands of dollars, a price paid repeatedly across iterative development cycles. Prior efforts, centered on benchmark distillation, reduce the number of evaluation tasks but leave the cost of executing each retained task untouched. In this work, we introduce early outcome prediction, a complementary axis of efficiency that instead cuts cost within each task. Our key insight is that an agent's final outcome is often evident from its intermediate behavior well before execution completes. We instantiate this idea in EarlyEval, a lightweight framework that trains a pair of LightGBM success and failure classifiers over behavioral, textual, and reference-solution features, and halts an agent run the moment either classifier crosses a calibrated confidence threshold, adding negligible per-step overhead. Across three benchmarks, SWE-bench Verified, TerminalBench, and Toolathlon, EarlyEval can eliminate 13%-26% of agent steps and up to 44.1% input tokens and 29.4% output tokens at 89%-97% prediction accuracy, while perturbing per-agent resolve rates by only one to two percentage points on average.