Agent Trajectory Evaluation: How to Judge Multi-Step AI Agents with Real Users (2026)

Short answer: Agent trajectory evaluation scores the entire path an AI agent takes to a result - every reasoning step, tool call, error recovery, and message back to the user - instead of only grading the final answer. It matters because a multi-step agent can land on the correct outcome through an unsafe, expensive, or unrepeatable route, and outcome-only scoring is blind to all three. The strongest programmes pair automated step-level checks with human participants who can say what the agent actually did to them.

Single-turn AI evaluation is a solved shape: you have an input, an output, and a rubric. Agents broke that shape. An agent booking a return, reconciling an invoice, or refactoring a file takes ten, thirty, or a hundred steps, and the interesting failures live in the middle of that sequence - not at the end.

This guide covers how to evaluate trajectories properly: the failure classes to score against, how to build a step-level rubric, where automated judges stop working, and how to bring real users into the loop.

Why outcome scoring quietly fails

The most cited evidence for this comes from tau-bench, the tool-agent-user benchmark from Shunyu Yao, Noah Shinn, Pedram Razavi, and Karthik Narasimhan at Sierra. Two findings from that work reframed how teams evaluate agents.

First, on realistic multi-step retail and airline tasks, even state-of-the-art function-calling agents "succeed on <50% of the tasks." Second, and more damning, the authors report that pass^8 - the probability an agent solves the same task correctly on all eight of eight attempts - is under 25% in the retail domain.

That gap between single-run pass rate and eight-run consistency is the whole argument for trajectory evaluation. An agent with a 50% pass rate and a 25% pass^8 is not half-competent; it is unreliable in a way that a single-run outcome metric structurally cannot show you. Your users experience pass^k, not pass^1, because they run the same task repeatedly.

The successor benchmark, tau-squared-bench, added a further complication: a dual-control environment where both the agent and the user act on shared state. Performance drops significantly when agents move from acting alone to guiding a user, and the authors separate reasoning errors from communication and coordination failures. That distinction matters enormously for product teams, because a coordination failure is invisible to any evaluation that does not include a human.

The four classes of trajectory failure

Score against these four classes explicitly. Most teams only instrument the second.

The fourth class is where most production complaints originate and where almost no evaluation budget goes. An agent that completed the task but told the user it had done something slightly different has failed, and no state-diff check will ever catch it.

Process reward vs outcome reward

Two scoring philosophies:

• Outcome reward assigns one score to the end state. Cheap, objective, and unable to tell you why a run failed.
• Process reward assigns a score to each step. Expensive, harder to define, and the only way to localise a failure to the step that caused it.

The practical answer is both: outcome scoring as your regression gate, process scoring on the subset of runs that fail, plus a rotating sample of runs that pass (to catch right-answer-wrong-path cases).

Step labelling is genuinely hard even for humans. AgentProcessBench, a 2026 benchmark for step-level process quality in tool-using agents, was built from 1,000 trajectories and 8,509 human-labelled step annotations, reaching 89.1% inter-annotator agreement. Its headline finding is a warning for anyone planning to automate this: current models struggle to distinguish neutral actions from erroneous ones, and weaker agents show inflated ratios of correct steps simply because they terminate early. An agent that gives up quickly can look clean on a naive step-accuracy metric.

Building a trajectory rubric

A workable rubric scores each step on three axes and the run as a whole on two.

Per-step:

Per-run:

Score goal satisfaction and policy adherence as a conjunction - a run counts as passing only if both pass. This is the design tau-bench uses, and it prevents the common failure of shipping an agent that is helpful and non-compliant.

Add severity to every identified failure. Without severity, a rubric produces a flat list of 200 issues and no prioritisation. Use a four-level scale: cosmetic, degraded, blocking, harmful.

Where humans are non-negotiable

Automated trajectory checks cover deterministic questions. Human evaluation covers four things they cannot:

1. Did the user understand what the agent was doing? Legibility is a property of the trajectory, not the outcome.
2. Was the hand-back at the right moment? Agents ask too early (annoying) or too late (dangerous). Only the person on the other end can say which.
3. Would the user trust it again? Trust after a recovered failure is a different measurement from trust after a clean run.
4. What did the user do next? Silent workarounds are the strongest signal that a trajectory is broken, and they never appear in your logs as errors.

The evidence that this gap is real and widening: the 2025 Stack Overflow Developer Survey found 66% of developers cite AI solutions that are "almost right, but not quite" as their top frustration, and 45% say debugging AI-generated code takes longer than writing it themselves. Those are trajectory complaints, not outcome complaints. A near-miss passes most outcome checks and costs the user more time than no help at all.

How to run trajectory evaluation with Koji

Traditional approach: recruit participants, schedule moderated sessions, watch each one attempt the agent task, transcribe, tag steps by hand, and synthesise. Fifteen sessions is roughly two weeks of researcher time and produces a sample too small to compare builds.

The AI-native approach compresses that to days:

1. Run the task, then interview immediately. Participants complete the real agent task. Koji picks up the moment they finish, while the trajectory is still fresh, and an AI moderator interviews each participant about the specific step that went wrong. The moderator asks genuine follow-ups - "you said it looked like it had booked it; what made you think that?" - which is exactly the probe a static post-task survey cannot produce.

2. Capture comparable step-level scores with structured questions. Koji supports six structured question types, and trajectory evaluation uses nearly all of them:

The structured types give you a comparable numeric series across builds. The open-ended responses give you the reasoning behind the numbers. See the structured questions guide for how to combine them in one study.

3. Cluster automatically. Koji thematic analysis groups hundreds of open-ended trajectory complaints into named failure modes without manual tagging, and each theme stays linked to the verbatim quotes and the participants who raised it - so an engineer can trace a theme back to a specific run.

4. Re-run as a regression gate. Because the study is a reusable artifact rather than a scheduling exercise, you can run the identical trajectory evaluation against every candidate build. That is what turns human evaluation from a one-off exercise into a gate, and it is the practical reason AI-moderated research changes agent development economics: 40 participant interviews in 48 hours is a different product decision from 12 interviews in three weeks.

You do not need a PhD in evaluation methodology to do this well. You need a fixed task set, a rubric with severity, and a repeatable way to talk to the people who ran it.

Sampling and cadence

For the regression gate, build the set the same way you would build any evaluation dataset - production-representative, edge, adversarial, and replayed past failures - and hold it stable so that movement in the pass rate means something. The golden set guide covers the sizing maths and the confidence intervals in detail.

Five mistakes to avoid

1. Reporting pass^1 only. Report pass^k as well. Consistency is the metric your users feel.
2. Letting the judge see the outcome before scoring steps. Outcome knowledge contaminates step-level judgement. Score steps blind.
3. Treating early termination as clean. An agent that quits fast scores well on step accuracy and terribly on usefulness. Always pair process scores with goal satisfaction.
4. Skipping the user hand-back class. It is the largest source of production complaints and the easiest to omit because logs do not capture it.
5. Changing the golden set and the model in the same week. You will not be able to attribute the movement to either.

Where this is heading

Regulatory pressure is arriving on the same axis. The EU AI Act obliges providers of high-risk systems to report serious incidents, which requires knowing not just that a system failed but how it failed - a trajectory question, not an outcome question. Teams that already keep step-level evidence with participant testimony attached will find that reporting burden manageable. Teams with only pass/fail logs will not.

Agent evaluation is converging on the same conclusion user research reached decades ago: the artifact tells you what happened, and only the person tells you what it meant.

Frequently asked questions

What is an agent trajectory? The full ordered sequence an agent produces while completing a task: intermediate reasoning, every tool call, the results returned, recovery attempts, and every message sent to the user. Outcome evaluation looks only at the final state; trajectory evaluation looks at the whole path.

Why is outcome-only evaluation not enough? Agents can reach the right answer by a wrong path - for example issuing a destructive write and then undoing it. Outcome scoring also cannot distinguish a competent run from a lucky one, which is why consistency metrics like pass^8 collapse even when single-run pass rates look acceptable.

What is the difference between process reward and outcome reward? Outcome reward scores the end state only. Process reward scores each intermediate step, localising the failure to the step that caused it. Process scoring gives far more debugging signal but costs more, because every step needs a label.

Can an LLM judge evaluate trajectories on its own? Only partially. Automated judges handle deterministic checks well - required tool called, forbidden action taken, final state matched. They are weak at separating neutral steps from erroneous ones, and they cannot tell you whether the user felt informed or misled.

How many trajectories do I need? Roughly 30-50 per critical task family for a directional read on a release; 100-500 in a fixed golden set for a stable regression gate.

How does Koji help? Koji runs the human half at scale: participants complete the real task, an AI moderator interviews each one about the exact moment it went wrong, structured questions capture comparable step-level scores, and thematic analysis clusters hundreds of trajectory complaints into named failure modes automatically.

Related Resources

• Human Evaluation of AI Outputs - the foundational guide to scoring AI quality with people
• LLM-as-a-Judge vs. Human Evaluation - when automated scoring is trustworthy and when it is not
• Evaluation Datasets and Golden Sets - how to build the fixed set your regression gate depends on
• AI Red Teaming with Real Users - finding harms before your users do
• Structured Questions in AI Interviews - the six question types and when to use each
• The EU AI Act and User Research - what AI-moderated research actually requires
• AI Governance for Customer Research - ISO 42001, the NIST AI RMF, and procurement

---

Sources: Yao, Shinn, Razavi & Narasimhan, tau-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains (arXiv:2406.12045); tau-squared-Bench: Evaluating Conversational Agents in a Dual-Control Environment (arXiv:2506.07982); Fan et al., AgentProcessBench: Diagnosing Step-Level Process Quality in Tool-Using Agents (arXiv:2603.14465); 2025 Stack Overflow Developer Survey; EU AI Act Article 73.