Trajectory Evals for Multi-Step Agent Runs

Two runs, one answer, and only one of them was safe

Every scoring method you have so far grades one output against one expected answer. An agent does not produce an output, it produces a path: a sequence of tool calls, each with arguments, each of which changed the world. Two runs can land on an identical final answer by wildly different routes.

task: "refund order 88213 and tell the customer"

run A                                        run B
  lookup_order(88213)      ok                  lookup_order(88213)      ok
  check_policy(88213)      refundable          refund(88213, 240.00)    ok
  refund(88213, 240.00)    ok                  lookup_order(88213)      ok
  send_email(cust, ...)    ok                  check_policy(88213)      refundable
                                               refund(88213, 240.00)    ok
                                               lookup_order(88213)      ok
                                               send_email(cust, ...)    ok
                                               send_email(cust, ...)    ok

final answer, both runs   "Your refund of $240.00 is on its way."
answer-match score        1.0                  1.0

Run B refunded twice, emailed twice, checked the policy after moving the money rather than before, and spent 8 tool calls against run A's 4. An answer-match eval sees none of it, because it reads the last line and nothing else. Worse, run B is the run that reaches the right answer by accident after taking a destructive action, and an output-only gate will happily ship the model that produces it.

Trajectory evaluation is the discipline that scores the path. It has its own vocabulary, and almost nobody arrives at an interview holding it.

The artifact is an ordered list, and most of it is programmatic

The thing you evaluate is the trajectory: the ordered list of (tool, arguments, result) the run produced, plus the final answer and the run's cost. If you did the tracing work, you already have it, because that list is exactly what the span tree holds, which is why production traces and eval cases are the same object viewed twice.

What makes trajectory eval cheap is that most of what you want to assert about that list is programmatic, and therefore deterministic, free, and trustworthy. The tool names are a closed set. The arguments are typed. The results carry a status. No model is needed to notice that refund appears twice with the same order id, and no model should be asked to.

The metric family

Table

Eight numbers, and the first one is the only one an output-only eval already gives you. Every other row is a property of the path, computable from the trajectory with no model in the loop.

Metric	Definition	What it catches that task success misses
Task success	The final state matches the required end state	Nothing new. This is the number you already have
Tool-selection precision	Correct calls divided by total calls	Guessing, thrash, and tools called outside their purpose
Tool-selection recall	Required calls made divided by required calls	A mandatory step silently skipped, like a policy check
Redundant-step rate	Repeated (tool, args) pairs divided by total calls	Loops, re-queries, and duplicated side effects
Error-recovery rate	Runs that recover divided by runs that hit a tool error	Brittleness that only appears when a dependency is flaky
Steps to completion	Tool calls per successful run, p50 and p99	The long tail that eats the budget while the median looks fine
Cost per success	Total spend divided by successful runs	A change that gets cheaper by failing more often
Wall clock	First call to final answer, p50 and p99	What the person on the other end is actually waiting through

Cost per success, not cost per run. A change that reduces the bill by failing more often improves every per-attempt number and degrades the only one that describes work getting done. The same reasoning applies to steps and to wall clock: divide by successes, because a run that failed fast is not a run that went well.

pass@k and pass^k, which is why this lesson exists

Two metrics that look like notation variants ask opposite questions.

pass@k asks whether the agent solved the task at least once in k tries. pass^k asks whether it solved the task every time in k tries.

Which one is correct depends entirely on how many attempts your user gets. A code assistant that shows five suggestions and lets a human pick the good one is a pass@k system, and improving pass@k genuinely improves it. A support agent that issues one refund is a pass^k system, and a model that solves the task 4 times out of 8 is not 50 percent good, it is unusable, because you cannot tell your customer which four.

Independence is the optimistic case, and real agents are not independent. The tau-bench work measured this directly: a leading tool-calling agent succeeded on fewer than half the tasks and its pass^8 in the retail domain came in under 25 percent. Run the independence arithmetic on that and the numbers do not reconcile at all. At a 50 percent per-run rate, independence predicts 0.5 to the eighth, which is 1 in 256, under half a percent. The measured figure is dozens of times higher.

The direction of that gap is not an accident and it is worth understanding, because it generalizes. Averaged over a task set, pass^k is the mean of each task's own success rate raised to the k, and that is always at least the mean rate raised to the k. Difficulty is spread unevenly across tasks: some are solved every single time and some are never solved, and it is the always-solved fraction that survives eight repetitions. So the failures cluster on particular tasks rather than scattering randomly across runs, which is genuinely good news for debugging, because a task that fails 6 times out of 8 has a deterministic bug wearing a probabilistic costume and is worth reading. It is bad news for any metric that rewards solving something at least once.

Grade against invariants, not against a golden path

The obvious next move is to record a reference trajectory and compare against it. It over-penalizes immediately, because there is usually more than one correct path. Run A above could have looked up the order and checked the policy in either order and been equally right, and an exact path match would fail one of those two arbitrarily.

Assert invariants instead. They are the properties that must hold on every correct path rather than one path that happened to be correct.

ordering      check_policy(id) precedes refund(id) for the same id
arguments     refund is never called with a null, zero, or negative amount
prohibition   delete_account never appears in a run whose task was a refund
cardinality   at most one successful refund per order id per run
termination   the run ends by answering, not by hitting the step cap
grounding     every order id in the final answer appeared in a tool result

Six assertions over a list. They run in milliseconds, they need no model, they never flake, and each one names a specific way a run can be wrong while still producing the right sentence. Write these first, and reach for a judge only for what an assertion cannot express.

What a judge may score, and what it may not

You already know a judge scales where human labeling cannot, and that it carries biases toward longer answers, toward its own style, and toward position. Over a trajectory the division of labor gets sharper.

A judge can reasonably score whether the plan made sense, whether a tool choice was defensible given only what the agent knew at that step, and whether the final answer is actually supported by what the tools returned. A judge must not be asked whether the run stayed under budget, made fewer than twelve calls, or called refund twice, because those are arithmetic over a list, and a program gets them right every time for free while a judge gets them mostly right for money.

One number is worth sharpening because it changes a practice rather than an opinion. The MT-Bench study measured position bias directly by swapping the two candidate answers and re-asking: the strongest judge in that study was consistent on 65.0 percent of pairs. Roughly a third of its verdicts flipped on the ordering alone. The operational answer is to run both orderings and count a disagreement as a tie, which converts an invisible bias into a visible abstention. It also doubles your judge spend, which is exactly why it belongs on the golden-set cadence rather than on every commit. The same study raised that consistency to 77.5 percent with few-shot examples, at roughly four times the prompt cost, which is the same trade paid in a different currency.

An eval without error bars is an anecdote

Your eval set is a sample, so the rate it reports is not the true rate, only a nearby one. The standard error is roughly how far apart those two can be: it is the typical distance between the number you measured on these items and the number you would get on every item you will ever serve. Small set, wide gap.

binary metric, n items, observed rate p
  standard error = sqrt(p * (1 - p) / n)
  near p = 0.5 that is about 0.5 / sqrt(n)

  n =  100    SE = 0.0500    95% interval about +/- 10 points
  n =  400    SE = 0.0250    95% interval about +/-  5 points
  n = 1600    SE = 0.0125    95% interval about +/-  2.5 points

so   72% on 100 items against 78% on 100 items is not a result
and  cutting the interval to a quarter costs 16 times the items

That last line is why sample size is not the lever people reach for twice. Two moves buy far more than more items does.

Paired analysis. When you compare two models, run both on the same items and analyze the per-item difference rather than the two rates. The intuition first: most of the wobble in a score comes from which items happened to land in the set, and if both models face the same items, that wobble hits both of them the same way and cancels when you subtract. The formal version is that the variance of a difference is the sum of the variances minus twice the covariance, where covariance is just how much the two scores rise and fall together, and on a shared item set it is large and positive because an item that is hard for one model is usually hard for the other. Subtracting it removes most of the noise. This is the single biggest sample-size saving available in eval, and an unpaired comparison throws it away for nothing in return.

Clustered standard errors. When items share a passage, a document, or a customer context, they are not independent observations. Ten questions about one document are closer to one observation than to ten, and treating them as ten understates your error bars. That is how a confident three-point improvement survives review and then fails to appear in production. Cluster the standard errors on whatever the items share.

Simulated users, a resettable world, and a holdout you never publish

Multi-turn agent eval needs a counterparty and a world, and both cost real engineering. The counterparty is a simulated user: a model given a persona and a goal, supplying the turns your agent has to handle, including the ones where the customer changes their mind halfway. The world is a resettable environment where the tools have real state, so a refund actually moves a balance and the next call sees the new one. Budget for both explicitly, because the alternative is stopping at single-turn eval and finding out in production that your agent cannot handle a follow-up. Anything the model can execute belongs in a sandbox; a framework such as Inspect AI, from the UK AI Security Institute, gives you the dataset, solver, and scorer split plus sandboxed execution of untrusted model code, so you do not build that twice.

Then keep a private holdout, and keep it private. A public benchmark score is not a measurement of your system if the model has seen the benchmark, and contamination is now the default assumption at the frontier rather than an edge case worth mentioning. Your holdout does not need to be large. It needs to be unpublished, which also means never pasting it into a provider whose retention terms you have not read.

Interview nuance: production traces are the eval set. The strong answer describes the pipeline from a failed run to a regression case (find it by trace id, replay its inputs, freeze it as a case with its invariants attached) and names the order of work: error analysis on real traces first, automated metrics second. Read fifty failed runs and label what actually went wrong before writing a single scorer, because the metric you would have written from intuition is almost never the one the failures ask for. And validate any judge you build against held-out human labels on true-positive and true-negative rate rather than on raw agreement. A judge that says "pass" to everything scores 90 percent agreement on a set where 90 percent pass, and catches nothing at all.

Recap: score the path, not just the destination, because two runs with the same answer can differ by a duplicated refund; compute the programmatic metrics first (tool-selection precision and recall, redundant steps, recovery rate, steps and cost per success) and reserve the judge for plan quality and support; use pass^k when the user gets one attempt and pass@k only when they genuinely get k; grade against ordering, argument, prohibition, and cardinality invariants rather than a golden path; and put error bars on every comparison, buying precision with paired analysis and clustered standard errors before buying it with sample size.

Sources: tau-bench and the pass^k metric · Adding Error Bars to Evals · Judging LLM-as-a-Judge with MT-Bench · LLM Evals FAQ