Summary (Overview)

• EarlyEval introduces a novel paradigm for reducing LLM agent evaluation costs by predicting outcomes during execution rather than after completion, complementing existing benchmark distillation approaches that only reduce the number of tasks.
• The framework trains LightGBM-based success and failure classifiers over behavioral, textual, and reference-solution features extracted from partial trajectories, halting agent runs the moment either classifier crosses a calibrated confidence threshold.
• Across three benchmarks (SWE-bench Verified, TerminalBench, Toolathlon), EarlyEval eliminates 13%–26% of agent steps and up to 44.1% input tokens and 29.4% output tokens at 89%–97% prediction accuracy.
• Per-agent resolve rates are perturbed by only 1–2 percentage points on average, and leaderboard rankings are preserved with Spearman's ρ ≥ 0.959 across all benchmarks.
• The framework operates effectively even on benchmarks without reference solutions, relying primarily on reference-free behavioral signals.

Introduction and Theoretical Foundation

The Cost Problem in Agent Evaluation

Modern agentic benchmarks evaluate models through multi-step rollouts—reading files, running commands, calling tools, and revising approaches. This fidelity to real-world use makes evaluation prohibitively expensive:

• A single pass of a frontier model over SWE-bench Verified costs several hundred dollars
• Benchmarks with longer rollouts reach thousands of dollars per pass
• Development cycles involve dozens of iterative runs, multiplying costs substantially

Table I: Cost of one evaluation pass (OpenHands Index)

Key Insight

The central observation is that an agent's final outcome is often evident from intermediate behavior well before execution completes. For example, in a real trajectory from tianocore/edk2-pytool-library, the agent applies the correct one-line fix at step 23 of a 45-step run; an observer with access to the reference solution could confidently declare the task resolved at that point, halving the cost.

Prior work focused exclusively on benchmark distillation (selecting fewer tasks), which leaves per-task execution costs untouched. EarlyEval addresses this complementary axis: reducing cost within each task.

Methodology

Problem Definition

For an agent $\mathcal{A}$ running on task $t$ producing trajectory $\tau = (e_1, e_2, \dots, e_T)$ with binary outcome $y \in \{0, 1\}$, an early-outcome predictor may issue prediction $\hat{y}$ at any step $k < T$ and halt the run.

Architecture Overview

Stage 1 (Offline): Historical trajectories are decomposed into prefixes $\tau_{:k} = (e_1, \ldots, e_k)$ for $k = 0, 1, \ldots, T$, each paired with the final outcome label $y$. Each prefix maps to a fixed-length feature vector $\phi(\tau_{:k}) \in \mathbb{R}^d$.

Stage 2 (Online): At each step, features are extracted and fed into dual predictors. If either confidence threshold is breached, execution halts with a predicted outcome.

Feature Engineering

Table II: Feature families extracted from partial runs

Training

Two separate LightGBM ensembles are trained:

• Success predictor $h_+$: targets $y = 1$
• Failure predictor $h_-$: targets $1 - y = 1$ (i.e., $y = 0$)

Each prefix instance is weighted by $1/(T+1)$ to prevent long trajectories from dominating. Data is split by task to prevent leakage.

Calibration and Decision Rule

Raw scores are recalibrated using Platt scaling:

$$p = \sigma (a \logit (\hat{s}) + b)$$

where $a, b$ are fitted on a held-out validation split. The decision rule halts a run at the first step where $p_+ \geq s$ (success threshold) or $p_- \geq f$ (failure threshold).

Empirical Validation / Results

RQ1: Prediction Accuracy and Compute Savings

Table III highlights (optimal operating points):

• SWE-bench Verified (threshold 0.95): 26.0% step reduction, 32.7% input token reduction, 28.7% output token reduction, 1.1% ∆|Pass@1|
• TerminalBench no-same-model (threshold 0.90): 25.4% step reduction, 42.7% input token reduction, 27.9% output token reduction, 2.1% ∆|Pass@1|
• TerminalBench no-same-scaffold (threshold 0.85): 17.7% step reduction, 29.2% input token reduction, 17.4% output token reduction, 2.0% ∆|Pass@1|
• Toolathlon (threshold 0.90): 23.0% step reduction, 44.1% input token reduction, 29.4% output token reduction, 0.9% ∆|Pass@1|

Key findings:

• The failure predictor shows robust precision across all benchmarks (89.4%–99.4%)
• The success predictor is reliable only on SWE-bench Verified (88.3%–93.9% precision)
• Dual step reduction equals the sum of success-only and failure-only reductions, indicating the two predictors rarely fire on the same trajectory

RQ2: Ranking Preservation

Table IV: Leaderboard fidelity at optimal operating points

RQ3: Feature Robustness

Table V: Feature ablation on SWE-bench Verified

The Behavioral family is the primary driver of early stopping, but signals are redundantly encoded across sub-features, enabling robust operation across benchmarks with heterogeneous feature availability.

RQ4: Architectural Ablation

Table VI: Backbone comparison on SWE-bench Verified

LightGBM defines the Pareto frontier, achieving the highest coverage, accuracy, and step reduction with sub-millisecond CPU inference per step, whereas the LLM judge's per-step forward passes offset the computational savings.

Theoretical and Practical Implications

Complementarity with Existing Approaches

EarlyEval introduces a new axis of evaluation efficiency—reducing cost within tasks—that complements rather than replaces benchmark distillation. These approaches can be combined: distillation reduces the number of tasks, while EarlyEval reduces the cost of each retained task.

Practical Applicability

• Requirement: A pool of completed, outcome-labeled trajectories on the target benchmark (satisfied by established benchmarks with public leaderboards)
• Target use case: Iterative development cycles where teams re-evaluate evolving agents against stable benchmarks
• Not intended for: Producing canonical, citable benchmark scores—full execution should still be used for final leaderboard entries

Design Principles

1. Reference-free operation: EarlyEval works on benchmarks without gold solutions by relying primarily on behavioral signals
2. Lightweight inference: Tree ensembles evaluate features in well under a millisecond on a single CPU core
3. Tunable trade-off: Thresholds expose a knob for balancing accuracy against computational savings

Conclusion

EarlyEval demonstrates that early outcome prediction is a viable and effective strategy for reducing LLM agent evaluation costs. By training dual LightGBM classifiers over behavioral, textual, and reference-solution features, the framework:

• Reduces execution steps by 13%–26% across three diverse benchmarks
• Cuts input tokens by up to 44.1% and output tokens by up to 29.4%
• Maintains prediction accuracy of 89%–97%
• Perturbs per-agent resolve rates by only 1–2 percentage points
• Preserves leaderboard rankings with ρ ≥ 0.959

Future directions include extending the framework to new benchmark types, exploring adaptive threshold selection, and investigating whether the approach can be applied to other multi-step evaluation settings beyond LLM agents.

The code and experimental data are available at: https://github.com/inphotoo/earlyeval