Evaluating tool-using agents: outcomes, trajectories, state diffs and pass^k

A tool-using agent that books a refund, edits a spreadsheet or files a ticket is judged by what it leaves behind in the world, how it got there, and whether it would do it again tomorrow. This note covers the main design choices in agent evaluation: scoring the outcome or the trajectory, when partial credit helps and when it misleads, how environment flakiness contaminates results, why reliability metrics such as pass^k fall off a cliff with task length, and how to check the final state with a diff instead of trusting the agent's own report. Every number below comes from seeded simulations we ran for this note.

Two agents, four scoreboards#

Start with a concrete case. A customer-operations task requires an agent to make four specific changes to a record store: update an address, cancel one order, issue a refund, add a note. Along the way it reads, searches and writes, and every action carries some risk of touching something it should not. We simulated 20,000 episodes each for two agents:

Careful gets each of the four target edits right 86% of the time and makes an unintended write on 0.4% of actions. Aggressive gets each target edit right 93% of the time but makes an unintended write on 6% of actions, and is more willing to announce success when it has not finished. Here is how each agent scores under four common grading schemes.

Aggressive leaves an unintended change behind in 33.1% of episodes, against 2.4% for Careful. Three of the four scoreboards cannot see that, and they rank Aggressive first by 7 to 24 points. The only scheme that matches what a customer would experience reverses the ranking. Everything else in this note is about building evaluations that land on the last row.

Outcome scoring and trajectory scoring#

Outcome scoring inspects the end state of the environment: database rows, files, sent messages. It allows any valid path to the goal, which matters because agents find routes the task author never imagined. τ-bench compares the database at the end of a conversation with an annotated goal state [1]; AppWorld runs state-based unit tests that accept different ways of completing a task while also checking for unexpected changes, which its authors call collateral damage [2]. SWE-bench runs the repository's tests after the agent's patch [3]. The weakness of outcome scoring is everything the end state does not record: a confirmation the agent should have asked for, a policy it broke on the way, a sensitive record it read but did not need.

Trajectory scoring inspects the sequence of actions. It catches process violations (acting without required confirmation, calling a forbidden tool, leaking data into a log) and it is the only way to grade efficiency. Its weakness is that a reference trajectory punishes valid alternatives, and an LLM judge reading long traces inherits all the biases of LLM judges. In practice the two are complementary: score the outcome with deterministic checks, and score the trajectory only for a short, explicit list of process rules that the end state cannot reveal.

Partial credit#

Long tasks with a single pass/fail outcome produce mostly zeros, which makes progress hard to see. Checkpoint-based partial credit fixes the signal problem: TheAgentCompany awards points for intermediate checkpoints alongside full completion [4], and AgentBoard proposes a progress rate for multi-turn tasks [5]. Partial credit is useful for development, where you want a gradient. It is risky for go/no-go decisions, because it compresses differences between agents (86.0% against 92.8% above) and can reward an agent for making most of the changes and leaving the record in an inconsistent state. A half-issued refund is often worse than no refund. Report partial credit next to full-completion rates, never instead of them.

State-diff checking#

The full-diff row in the table is easy to implement once the environment can be snapshotted. Take the state before the episode $S_0$ and after it $S_1$, and compute the set of changed keys $\Delta =\mathrm{diff}(S_0,S_1)$. The task specification lists required changes $R$ (key and expected value) and allowed side effects $A$, such as audit logs or timestamps. The episode passes when

Here $\Delta$ is every key whose value changed, $R$ the required changes with their target values, $A$ the keys allowed to change, and $\setminus$ set difference. The first condition says the agent did the job; the second says it did nothing else. The second condition is what separates the last two rows of the table.

def state_diff(before: dict, after: dict) -> dict:
    keys = before.keys() | after.keys()
    return {k: after.get(k) for k in keys if before.get(k) != after.get(k)}

def grade(before, after, required: dict, allowed: set) -> dict:
    d = state_diff(before, after)
    missing = {k: v for k, v in required.items() if d.get(k, before.get(k)) != v}
    collateral = set(d) - set(required) - allowed
    return {"pass": not missing and not collateral,
            "missing": missing, "collateral": sorted(collateral),
            "partial": 1 - len(missing) / max(len(required), 1)}

from math import comb
def pass_hat_k(n: int, c: int, k: int) -> float:
    # unbiased estimate of p^k from c successes in n trials (requires n >= k)
    return comb(c, k) / comb(n, k)

Two practical details decide whether this works. Keys must be canonical (normalise whitespace, number formats and ordering inside lists) or the diff will flag cosmetic changes as collateral. And "allowed" should be as narrow as possible; a wildcard on a whole table hides exactly the damage you are trying to see.

Reliability compounds: the step model#

Why do agents that look competent on short tasks fall apart on long ones? A simple model explains most of it. If each of $n$ steps succeeds independently with probability $r$, the episode succeeds with probability

$r$ is per-step reliability and $n$ the number of steps that must all go right. A per-step reliability of 0.99 sounds excellent, and gives 81.8% on a 20-step task. At 0.98 the same task succeeds 66.8% of the time. Many agents can notice some of their own mistakes (a failed API call, an empty search) and repair them. If a fraction $\rho$ of step errors are caught and fixed, the effective per-step success becomes

with $\rho$ the recovery rate. Recovery is powerful: at $r=0.97$ and $n=20$, raising $\rho$ from 0 to 0.5 lifts success from 54.4% to 73.9%. That is why evaluating recovery behaviour directly (inject a tool error, see what the agent does) is often more informative than another pass over the happy path.

pass^k: will it work every time?#

For a deployed agent the question is not whether it can succeed but whether it succeeds every time a user asks. τ-bench introduced pass^k for this [1]: the probability that all $k$ independent trials of the same task succeed, averaged over tasks. For a task with success probability $P$ it is $P^k$, and the contrast with the familiar pass@k (which we covered for reasoning-model evaluation) is stark:

The expectation runs over tasks. pass@k asks whether any of $k$ attempts succeeds and rises with $k$; pass^k asks whether all do and falls with $k$. Under the step model a single task's pass^k is $s^{nk}$: repeating a task $k$ times is, for reliability purposes, the same as making it $k$ times longer. At $r=0.99$ and $n=20$, pass^8 is 20.0% while pass@8 is above 99.9%.

The surface makes the engineering target concrete. Solving $s^{nk}=0.9$ gives the per-step reliability needed for 90% pass^k, $r=0.9^{1/(nk)}$ when there is no recovery. For pass^1 on a 20-step task that is 0.9947. For pass^8 it is 0.9993 on 20 steps, 0.9987 on 10 steps and 0.9997 on 50 steps. Each extra "nine" of per-step reliability buys roughly ten times the task length at the same reliability. No amount of averaging over trials substitutes for that.

Real tasks are not identical, and that helps#

The step model with one $r$ and one $n$ is pessimistic about pass^k, because real task suites mix easy and hard tasks and the successes concentrate on the easy ones. By Jensen's inequality $\mathbb{E}[P^k]\ge (\mathbb{E}[P]{)}^k$, so raising the average pass^1 to the $k$-th power understates pass^k. We simulated a suite of 120 tasks with between 4 and 30 steps (mean 16.8) and task-specific per-step reliabilities averaging 0.966, then ran each task 8 times.

True pass^1 is 62.1% (estimated 61.3% from the trials). True pass^8 is 12.2%, and the unbiased estimate $\left(\genfrac{}{}{0ex}{}{c}{k}\right)/\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ from 8 trials gives 10.0%, with a standard deviation of 2.6 points across repeated experiments. The naive $({\text{pass}}^1{)}^8$ gives 2.0%, and a homogeneous step model with the average $r$ and average $n$ gives 0.9%. Only 10.0% of tasks succeeded in all 8 trials and 2.5% failed all 8, so most of the suite is in the unreliable middle. If you want pass^k, measure it with repeated trials; do not compute it from pass^1.

Environment non-determinism#

Agents run against environments that fail on their own: a tool call times out, a page renders differently, a rate limit triggers, a simulated user model says something unexpected. Self-hosted environments such as WebArena exist partly to make web tasks reproducible [6], and OSWorld runs tasks inside resettable virtual machines [7]. When infrastructure fails independently of the agent with probability $f$ per episode, the measured success and reliability are

where $P$ is the agent's true success and $f$ the infrastructure failure rate. A 5% flake rate costs only 5% of pass^1 but multiplies pass^8 by $0.95^8=0.66$. We checked this with 4,000 simulated suites of 200 tasks, each task with true success 0.70 and 8 trials.

The fix is to make infrastructure failure a distinct, detectable outcome. Tag every episode with an infra status (tool timeouts, HTTP 5xx, sandbox crashes), retry infra-failed episodes up to a fixed limit, and report the infra failure rate separately. With up to three retries on detectable infra errors, the last column recovers the true value to three significant figures. What you must not do is retry on any failure: that converts pass^k into something closer to pass@k and hides exactly the inconsistency you set out to measure.

A second source of non-determinism is deliberate: simulated users. τ-bench uses a language model to play the customer [1], which makes conversations realistic and also makes the same task differ between trials. That variance is part of what pass^k measures, so fix the user-simulator model and its sampling settings across the agents you compare, and report them.

Design checklist#

Failure modes#

Checks that only test the targets. The most common bug in agent benchmarks is a grader that confirms the required fields and never looks anywhere else. It ranked the wrong agent first in our example.

Graders that the agent can see. If test files or expected outputs are readable from inside the sandbox, a capable agent can satisfy the check without doing the task. Keep graders outside the agent's file system and permissions.

Too few trials for pass^k. With $n=k$ trials, the estimator $\left(\genfrac{}{}{0ex}{}{c}{k}\right)/\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is the indicator "all $n$ succeeded", which is unbiased but noisy. For pass^8 on 120 tasks we saw a 2.6-point standard deviation. Small suites need more trials than $k$ to say anything useful.

Benchmarks that drift. Live websites and APIs change. A result is only reproducible if the environment version is pinned and reported.

Comparing agents with different budgets. An agent allowed 50 steps and one allowed 15 are not doing the same task. Fix step, token and time budgets, or report success as a function of budget [8].

What this simulation does not capture#

The step model treats steps as independent with a single reliability, while real errors cluster: one misunderstanding early in a conversation poisons every later step. The scoring simulation uses a fixed number of target edits and a constant per-action collateral rate; real collateral depends on the tools the agent is given. Infrastructure failures are modelled as independent and detectable, and in practice some are silent. The qualitative conclusions (score the full diff, measure pass^k with repeated trials, separate infra failures) do not depend on these simplifications, but your numbers will.

Frequently asked questions#

Sources#

1. Shunyu Yao, Noah Shinn, Pedram Razavi, Karthik Narasimhan. τ-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains, 2024. arxiv.org
2. Harsh Trivedi, Tushar Khot, Mareike Hartmann, et al.. AppWorld: A Controllable World of Apps and People for Benchmarking Interactive Coding Agents, 2024. arxiv.org
3. Carlos E. Jimenez, John Yang, Alexander Wettig, et al.. SWE-bench: Can Language Models Resolve Real-World GitHub Issues?, 2023. arxiv.org
4. Frank F. Xu, Yufan Song, Boxuan Li, et al.. TheAgentCompany: Benchmarking LLM Agents on Consequential Real World Tasks, 2024. arxiv.org
5. Chang Ma, Junlei Zhang, Zhihao Zhu, et al.. AgentBoard: An Analytical Evaluation Board of Multi-turn LLM Agents, 2024. arxiv.org
6. Shuyan Zhou, Frank F. Xu, Hao Zhu, et al.. WebArena: A Realistic Web Environment for Building Autonomous Agents, 2023. arxiv.org
7. Tianbao Xie, Danyang Zhang, Jixuan Chen, et al.. OSWorld: Benchmarking Multimodal Agents for Open-Ended Tasks in Real Computer Environments, 2024. arxiv.org
8. Sayash Kapoor, Benedikt Stroebl, Zachary S. Siegel, Nitya Nadgir, Arvind Narayanan. AI Agents That Matter, 2024. arxiv.org