# EarlyEval: Cheaper Agent Evaluation via Early Outcome Prediction

> EarlyEval predicts agent outcomes mid-execution with LightGBM classifiers, halting runs early to cut 13-26% of steps and up to 44% tokens while preserving leaderboard rankings.

- **Source:** [arXiv](https://arxiv.org/abs/2609.02783)
- **Published:** 2026-09-04
- **Permalink:** https://picx.dev/p/NR2dJW
- **Whiteboard:** https://picx.dev/p/NR2dJW/image

## Summary

## 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)**

| Benchmark | #Tasks | Claude 5 | GPT-5.5 | Gemini 3.1 Pro |
|-----------|--------|----------|---------|----------------|
| SWE-bench Verified | 500 | $715 | $760 | $935 |
| SWT-bench | 500 | $735 | $460 | $810 |
| Commit0 | 54 | $674 | $300 | $64 |
| GAIA | 165 | $1,305 | $122 | $297 |
| SWE-bench Multimodal | 517 | $2,270 | $1,453 | $641 |

### 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**

| Family | Feature group | # | Description |
|--------|--------------|---|-------------|
| Behavioral | Activity counts | 37 | Cumulative counts of steps, actions, tool calls, edit operations, test executions, etc. |
| Behavioral | Last step | 11 | Properties of the most recent step (action category, tool calls, error signals) |
| Behavioral | Event timing | 18 | Temporal structure of key events (first occurrence, elapsed since last) |
| Behavioral | Working pattern | 32 | Rhythm ratios, stalling indicators, repeated actions, submission patterns |
| Behavioral | Error & test status | 17 | Error types observed, test outcomes, failure count trends |
| Textual | Task prompt | 64 | SVD embedding of TF-IDF representation of issue description |
| Textual | Action text | 128 | SVD embeddings of full action history and most recent action |
| Textual | Feedback text | 128 | SVD embeddings of all environment feedback and most recent feedback |
| Reference | Gold descriptors | 28 | Attributes of reference solution (patch size, files changed, test counts) |
| Reference | Prefix-gold overlap | 54 | Jaccard overlap between agent's touched files/symbols/tests and gold solution |

### 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**

| Setting | ρ | % Exact Rank | ∆Steps |
|---------|---|-------------|--------|
| SWE-bench Verified (16 agents) | 0.991 | 81% | -26.0% |
| TerminalBench no-same-model (37 agents) | 0.959 | 59% | -24.6% |
| TerminalBench no-same-scaffold (37 agents) | 0.994 | 70% | -12.7% |
| Toolathlon (22 agents) | 0.994 | 70% | -23.0% |

### RQ3: Feature Robustness

**Table V: Feature ablation on SWE-bench Verified**

| Feature set | Coverage | Accuracy | ∆Steps | ∆\|Pass@1\| |
|-------------|----------|----------|--------|-------------|
| Full (all features) | 34.8% | 95.0% | -26.0% | 1.1% |
| w/o Behavioral | 23.4% | 94.7% | -16.4% | 0.8% |
| w/o Textual | 35.9% | 94.5% | -26.5% | 1.2% |
| w/o Reference | 32.1% | 93.9% | -24.7% | 1.2% |

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**

| Variant | Coverage | Accuracy | ∆Steps | ∆\|Pass@1\| |
|---------|----------|----------|--------|-------------|
| LightGBM (ours) | 34.8% | 95.0% | -26.0% | 1.1% |
| Direct MLP | 26.9% | 87.9% | -20.0% | 3.3% |
| Linear (dense LR) | 9.7% | 43.8% | -7.7% | 5.5% |
| Linear (TF-IDF LR) | 2.4% | 79.5% | -2.0% | 0.3% |
| Local LLM judge (Qwen LoRA) | 18.7% | 90.7% | -17.9% | 0.8% |

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

---

_Markdown view of https://picx.dev/p/NR2dJW, served by PicX — AI-generated visual whiteboard summaries of research papers._