Paper Walkthrough: EarlyEval — Making Agent Evaluation Cheaper by Stopping Early

One evaluation pass over an agentic benchmark costs hundreds of dollars. EarlyEval exploits the fact that an agent's ending is legible from its middle, halting runs to cut 13–26% of steps. Mechanism, numbers, and limits, straight from the paper.

EarlyEval: Cheaper Agent Evaluation via Early Outcome Prediction

The problem: evaluation got too expensive

The paper's original title is "EarlyEval: Cheaper Agent Evaluation via Early Outcome Prediction" (Yuling Shi, Zhensu Sun, Junsen Dong, Chengcheng Wan, David Lo, Xiaodong Gu / arXiv:2609.02783 / September 2, 2026).

Here is what the abstract claims. Evaluating LLM agents is essential for steering their development, yet it has become prohibitively expensive. Prior work has concentrated on benchmark distillation, which cuts the number of tasks but leaves the cost of executing each surviving task untouched. This paper proposes a complementary axis, early outcome prediction, which cuts cost within each task. The key insight: an agent's final outcome is often evident from its intermediate behavior well before execution finishes. EarlyEval instantiates this as a pair of LightGBM classifiers — one for success, one for failure — over behavioral, textual, and reference-solution features, and halts a run the moment either classifier crosses a calibrated confidence threshold. Across three benchmarks it 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.

The paper puts numbers on the pain (§II-A). Drawing on the OpenHands Index as of June 2026, a single pass over SWE-bench Verified (500 tasks) cost $715 with Claude 5, $760 with GPT-5.5, and $935 with Gemini 3.1 Pro. Benchmarks with longer rollouts run higher: SWE-bench Multimodal reaches $2,270 for the most expensive model. That is the price of measuring one agent configuration once — and you pay it again every time you touch a prompt or a scaffold.

Is the ending really legible from the middle?

Think of a forced mate in chess. Once the correct checkmating move goes down, the remaining moves are bookkeeping. The result is settled; playing it out only confirms what is already true. EarlyEval is trying to skip the bookkeeping.

The paper grounds this in a real trajectory (§II-B). A publicly released OpenHands run, tianocore__edk2-pytool-library-372, fixes a genuine bug where a path utility documented to return a forward-slash relative path returned backslashes instead. The run spans 45 steps and ends with a patch that resolves the task. But by step 20 the agent has written a reproduction script, and at step 23 it makes its single source-code change — normalizing the separators in one line — after which it never touches the source again. An observer holding the reference solution could call the task resolved at step 23. The identical evaluation outcome, at roughly half the cost.

Intuition: appoint two referees

The obvious design is one classifier that predicts the final score from the partial run. EarlyEval deliberately does not do that. It trains a success referee $h_+$ and a failure referee $h_-$ separately (§III-D), because the two outcomes announce themselves in completely different ways. Success shows up as positive evidence — the right file was edited, the tests turned green. Failure shows up as deadlock — the agent retries the same edit against an error message that never changes.

Splitting the referees buys a second thing: an explicit uncertain region where neither is confident. While both confidences stay low, the agent keeps running. A run is cut short only when one referee is willing to commit. Each referee's raw score is squashed through a logistic function into a probability before it is compared against a threshold.

The halting rule, and how the referees are trained

Write a trajectory as $\tau=(e_1,\dots,e_T)$, where $e_k$ records the action taken at step $k$ together with the resulting observation, and $T$ is the number of steps until the agent halts on its own. At termination the benchmark assigns a binary score $y\in\{0,1\}$, with $1$ for success. Getting $y$ the conventional way requires executing all $T$ steps (§III-A).

EarlyEval's rule is:

Here $\tau_{:k}$ is the prefix consisting of the first $k$ steps, $p_+$ and $p_-$ are the two referees' confidences, and $s$ and $f$ are their thresholds. Put in words, it says: stop at the first step where either referee crosses its line. In the rare case both cross on the same step, the chronologically earlier crossing wins (§III-E).

The confidences are not raw model outputs. Regularized tree ensembles distort probability scales, so the paper recalibrates with Platt scaling:

$\hat{s}$ is the raw ensemble score, $\sigma$ is the logistic function, and $a,b$ are two scalars fitted on a held-out validation split. Stated in words, this makes the number 0.95 mean the same thing for both referees and across every fold. Because the transformation is monotonic, it changes no rankings and no AUC — it only fixes the scale.

The practical payoff of calibrating is that the threshold becomes an operational dial. Raise it and you halt fewer runs, get more of them right, and save less. Lower it and everything moves the other way. How far that exchange rate actually goes is what the experiments measure.

So how are the referees trained? Training data is built by expanding each trajectory into all its prefixes $k=0,1,\dots,T$ and labeling every prefix with the trajectory's final outcome $y$ — you paste the ending onto every snapshot of the middle. Trajectories shorter than 10 steps are discarded as too weak in signal, each prefix is weighted by $1/(T+1)$ so long runs cannot dominate the loss, and the split is by task, with all prefixes from one trajectory forced to the same side, to prevent leakage (§III-C, §III-D).