PaperlayerView exact revision on arXiv

Source-linked AI summary

EarlyEval: Cheaper Agent Evaluation via Early Outcome Prediction

Yuling Shi, Zhensu Sun, Junsen Dong, Chengcheng Wan, David Lo, Xiaodong Gu

arXiv:2609.02783v1cs.CL

TL;DR

Agentic benchmark evaluation is expensive, and benchmark distillation does not reduce the cost of each retained task. EarlyEval predicts outcomes from intermediate trajectories with LightGBM classifiers and calibrated halting, reducing execution and token costs across three benchmarks while keeping outcome fidelity close to full evaluation.

  • Problem

    Benchmark distillation reduces task counts but leaves the computational and financial cost of executing each retained task unchanged.

  • Method

    EarlyEval uses LightGBM success and failure classifiers over behavioral, textual, and reference-solution features, halting runs when a calibrated confidence threshold is crossed.

  • Results

    Across three benchmarks, EarlyEval reduces execution steps by 13%-26% and input tokens by up to 44.1%, with minimal per-agent resolve-rate distortion.

  • Takeaways & Limitations

    Early outcome prediction provides a complementary within-task efficiency axis that can reduce evaluation cost while largely preserving benchmark outcomes and rankings.

  • Takeaways & Limitations

    EarlyEval relies significantly on redundant behavioral and textual features, although benchmarks without ground-truth reference patches can disable the reference-solution feature family with minimal performance degradation.

Abstract

from arXiv · show

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.

I. INTRODUCTION

LLM-agent evaluation is costly because repeated benchmark runs can reach hundreds or thousands of dollars, while benchmark distillation leaves retained tasks' execution costs unchanged. EarlyEval addresses this within-task cost by predicting outcomes from intermediate behavior and halting runs early.

  • Motivation: Repeated agent evaluation can cost hundreds to thousands of dollars per benchmark pass, creating a resource barrier for development.SWE-bench Verified costs several hundred dollars per frontier-model pass, while longer-rollout benchmarks can reach thousands.
  • Motivation: Benchmark distillation reduces the number of tasks but leaves the execution cost of each retained task unchanged.The remaining tasks therefore remain computationally and financially expensive to run.
  • Approach: Early outcome prediction reduces evaluation cost within individual tasks by terminating an agent rollout once its outcome becomes predictable.It complements rather than replaces benchmark distillation.
  • Approach: EarlyEval predicts outcomes from behavioral trajectories, textual context, and reference-solution metadata using LightGBM success and failure classifiers.A calibrated threshold-based halting rule adds negligible per-step inference overhead.
  • Results: Across SWE-bench Verified, TerminalBench, and Toolathlon, EarlyEval reduces execution steps and token consumption while largely preserving resolve rates and leaderboard rankings.The evaluation uses leave-one-agent-out testing so each held-out agent is unseen during predictor training.

A. Agentic Benchmarks are Expensive

Agentic benchmarks are expensive because each task requires many model calls across a multi-step rollout. Repeated evaluations during agent development multiply the cost and can place frequent benchmarking beyond many practitioners' reach.

  • Cost drivers: Every rollout step issues at least one model call, and a single task can run for dozens of steps.Reading files, running commands, calling tools, and revising failed approaches make agentic benchmarks faithful to real use but costly.
  • Cost drivers: A single frontier-model evaluation pass can cost several hundred dollars on SWE-bench Verified and more on benchmarks with longer rollouts.The cited costs are for one evaluation of one agent configuration.
  • Development impact: Dozens of repeated runs across prompt, scaffold, model, and baseline changes can place frequent evaluation beyond many practitioners' reach.Iterative development multiplies the cost of each benchmark pass into a substantial total.

B. Outcomes are Often Foreseeable Early

An agent's final outcome can become clear before a multi-step run ends. In a 45-step OpenHands trajectory, the correct one-line fix appeared at step 23, allowing the same outcome to be recorded at roughly half the cost.

  • Example: A real OpenHands trajectory spans 45 steps and ends with a resolving patch, although its substantive work finishes earlier.The example concerns a path utility that returned backslashes instead of a forward-slash relative path.
  • Example: By step 20 the agent reproduced the bug, and at step 23 it applied the sole source-code modification normalizing path separators.The agent continued testing without making further source changes.
  • Implication: Stopping after the correct fix at step 23 would preserve the identical evaluation outcome at roughly half the cost.The example illustrates why intermediate behavior can make final outcomes foreseeable before natural completion.

A. Problem Definition

Early outcome prediction infers an agent's final benchmark score from a partial run before completion, allowing the remaining steps to be skipped. A predictor may halt at any intermediate step when its confidence is sufficient and substitute its prediction for the true outcome.

  • Definition: Early outcome prediction infers an agent's final score from its partial run before completion.The purpose is to avoid executing the remaining steps once the outcome can be inferred.
  • Conventional evaluation: A conventional evaluation assigns a binary success or failure score only after the agent completes its full trajectory.The trajectory contains actions and resulting observations through total step count T.
  • Early stopping: An early-outcome predictor can issue a binary prediction at any step k < T and halt the run when confidence is sufficient.If confidence is insufficient, execution continues to the next step; when the predictor fires, its output becomes the task score.

B. Overview

EarlyEval infers an agent’s final benchmark outcome from its partial trajectory and halts execution when success or failure confidence crosses a threshold. It otherwise allows the run to continue until completion.

  • EarlyEval extracts multimodal features from each accumulated partial trajectory to predict the task’s eventual outcome.The evolving trajectory is processed step by step during agent-environment interaction.
  • A dual-threshold mechanism immediately stops execution when either success or failure confidence reaches its designated threshold.If neither threshold is crossed, the run continues and its full-run outcome is recorded upon completion.
  • Historical, fully evaluated agent runs provide labeled trajectories for training separate success and failure predictors over trajectory prefixes.Each complete trajectory supplies supervision, and prefixes train classifiers for recognizing emerging success or failure evidence.

C. Processing Training Data

EarlyEval converts historical trajectories into labeled prefixes, represents them with behavioral and textual features, and applies calibrated success/failure predictors at every step. Threshold decisions halt confident runs while ambiguous runs continue, with metrics measuring decision quality, compute savings, and fidelity.

  • Processing Training Data: Historical trajectories are assigned binary terminal labels, expanded into prefixes, and used to derive fixed-length feature vectors.Trajectories shorter than 10 steps are discarded before optimization.
  • Feature Families: Behavioral features capture progression, pacing, milestones, errors, tests, stalling, and premature submission patterns.These signals are extracted from the agent’s interaction trajectory and environment feedback.
  • Feature Families: Textual features encode the task prompt, action history, recent action, environment feedback, and recent feedback as separate semantic blocks.The feature design separates trajectory language into independently represented context blocks.
  • Prediction Model: For each benchmark, agent-agnostic LightGBM success and failure ensembles score several-hundred-dimensional prefix vectors in well under one millisecond per CPU-core evaluation.This enables rescoring at every execution step with negligible overhead.
  • Prediction Model: The success and failure predictors use the same representation but inverted targets, creating specialized detectors for trajectories converging toward each outcome.An explicit low-confidence region lets execution continue when neither predictor is confident.
  • Training and Calibration: Prefixes remain on the same side of the train-validation split as their source trajectory, while validation data calibrates predictor probabilities.Prefix weighting by 1/(T + 1) ensures each trajectory contributes equal total objective mass regardless of length.
  • Training and Calibration: Platt scaling rescales raw ensemble scores so confidence thresholds have consistent meaning without changing predictor rankings or AUC.A separate calibrator is fitted for each predictor within each cross-validation fold.
  • Evaluation Metrics: EarlyEval evaluates decision quality, eliminated steps and tokens, and fidelity through resolve-rate deviations, rank correlation, and rank shifts.Coverage measures the proportion of trajectories halted early, while negative relative changes indicate resources eliminated.

A. RQ1: Prediction Accuracy and Compute Savings

Across three benchmarks, EarlyEval reduces execution and token costs while maintaining prediction quality and benchmark fidelity. Thresholds expose a tunable trade-off: lower thresholds increase savings but also increase resolve-rate distortion, and predictor reliability varies by benchmark and split.

  • RQ1 Results: 23.0% fewer execution steps on Toolathlon at threshold 0.90 accompanies ∆|Pass@1| of 0.9%.The reported absolute resolve-rate deviation remains approximately one percentage point.
  • Threshold Trade-off: 63.4% fewer SWE-bench Verified steps at threshold 0.75 increases ∆|Pass@1| distortion relative to 26.0% fewer steps at threshold 0.95.Lowering the threshold systematically exchanges metric fidelity for greater computational savings.
  • Predictor Reliability: Success-predictor precision ranges from 88.3% to 93.9% on SWE-bench Verified but falls to 61.4%–69.0% on TerminalBench and has near-zero coverage on Toolathlon at higher thresholds.The failure predictor is more consistent, reaching 96.7% on SWE-bench, 89.4%–96.6% on TerminalBench, and 96.6%–99.4% on Toolathlon at designated operating points.
  • Predictor Reliability: Withholding the TerminalBench scaffold lowers peak success precision from 82.7% to 69.0% and dual step reduction from 25.4% to 17.7%.The comparison is between no-same-model and no-same-scaffold settings.
  • RQ1 Results: 29.2%–44.1% of input tokens and 17.4%–29.4% of output tokens are eliminated, while absolute resolve-rate deviation stays within 2.1 percentage points.This cross-benchmark result is reported under the leave-one-agent-out evaluation protocol.

B. RQ2: Preservation of Per-Agent Rankings

EarlyEval preserves the relative ordering of evaluated agents across benchmark settings, with high rank correlations and substantial exact-rank retention. Fidelity is assessed against full-run leaderboards at benchmark-specific operating points.

  • Evaluation Setup: Early-stopped leaderboards are evaluated against full-run ground truth using benchmark-specific operating points selected in RQ1.Thresholds are 0.95 for SWE-bench Verified, 0.90 for Toolathlon and TerminalBench’s no-same-model split, and 0.85 for its no-same-scaffold split.
  • Evaluation Metrics: Ranking fidelity is measured with Spearman’s rank correlation and the fraction of agents whose exact ordinal positions are preserved.Table IV reports top-3 agents and global leaderboard statistics for each setting.
  • Results: Spearman’s ρ ranges from 0.959 to 0.994 across evaluation targets, reaching 0.991 on SWE-bench Verified and 0.994 on Toolathlon.The TerminalBench no-same-scaffold split also reaches 0.994.
  • Results: 59%–81% of evaluated agents retain their exact ordinal positions under early stopping.The exact-rank fraction is lowest on the TerminalBench no-same-model split and highest on SWE-bench Verified.

C. RQ3: Robustness to Feature Availability

EarlyEval remains robust when feature families are unavailable: removing individual groups mainly reduces early-stopping coverage and compute savings without materially degrading decision quality.

  • Feature-family ablations: Removing the Reference-Solution family marginally reduces coverage to 32.1% and step savings to 24.7%.This supports use on benchmarks without ground-truth reference patches.
  • Feature-family ablations: Textual feature removals change coverage and accuracy by at most 0.5 percentage points, leaving early-stopping dynamics virtually unchanged.
  • Robustness conclusion: EarlyEval’s predictive signals are redundantly distributed across and within feature families.Omitting a family or subgroup primarily scales down coverage and compute savings rather than compromising decision quality.

D. RQ4: Architectural Ablation

The architectural ablation compares LightGBM with neural, linear, and LLM-judge backbones under a fixed leave-one-agent-out evaluation. LightGBM provides the strongest combined accuracy, coverage, and step-savings trade-off while preserving evaluation fidelity.

  • Backbone comparison: LightGBM achieves 34.8% coverage, 95.0% accuracy, and 26.0% step reduction with 1.1 percentage points of metric distortion.It defines the Pareto frontier across the evaluated accuracy–efficiency axes.
  • Alternative backbones: The Direct MLP reaches 26.9% coverage and 87.9% accuracy, saving 20.0% of execution steps with 3.3 points of metric distortion.
  • Alternative backbones: The TF-IDF logistic regression triggers on only 2.4% of trajectories, producing 2.0% step reduction despite 0.3 points of distortion.Its high 79.5% accuracy reflects passivity because it rarely intervenes.
  • LLM judge baseline: The fine-tuned Qwen judge achieves 90.7% accuracy and 18.7% coverage, but saves 17.9% of steps versus LightGBM’s 26.0%.Its per-step model forward passes can offset intended computational savings, whereas LightGBM runs in sub-millisecond CPU time.
  • Applicability boundary: EarlyEval requires completed, outcome-labeled trajectories on the target benchmark to train its predictors.The evaluation uses public baseline runs and leaderboard submissions for established benchmarks.
Loading 2609.02783v1…