Agent evaluation: state, trajectory, pass^k and release gates

Story

Hide story

Wick writes DONE beside the lamp in car nine and goes to find the kettle.

Twenty minutes later the lamp is dark again. “I wrote DONE,” he says, and he did. The notebook is a complete and honest record of what Wick did.

It says nothing about the lamp. How would anyone tell whether the job worked?

Concept#

The previous lesson (Multi-agent systems) was about choosing a structure and what it costs. This lesson is about finding out whether the structure you chose works, and whether it keeps working.

• Outcome: did the task succeed, judged from the state of the world.
• Trajectory: how the agent got there, judged from the run’s steps.
• Reliability: whether it succeeds every time you ask, judged from repeated runs.

Why It Matters#

“How would you evaluate an agent” questions test whether you measure the agent or trust it. An agent you cannot evaluate is an agent you cannot safely change, because you will not know whether the last prompt edit helped or hurt. And an agent that acts for real users, with real side effects, needs a written decision about when it is allowed to ship.

Mental Model#

Evaluation is a driving test, not an interview. You do not ask the driver whether they drove well. You watch the route (trajectory), check where the car ended up (state), and repeat the test on different days (reliability).

Technical Deep Dive#

Evaluating agents: outcomes and trajectories#

• Outcome evaluationOutcome gradingChecking the state of the world after an agent runs, such as the database row or passing tests, instead of trusting its final message.Open the glossary entryClose: did the task succeed? Check the state of the world, not the agent’s report. Did the database change correctly, do the tests pass, does the file exist? An agent can say “done” and be wrong. The tau-bench benchmark works this way: it compares the database at the end of a conversation with the annotated goal state (Yao et al., 2024).
• Trajectory evaluationTrajectory evaluationJudging the steps an agent took, such as tool choices, cost and risk, in addition to its final result.Open the glossary entryClose: how did it get there? Right tools, sensible order, no pointless calls, recovery from errors, step and cost counts. Two runs with the same final state can differ hugely in cost and risk.
• Safety evaluation: attempts at disallowed actions, resistance to injected instructions, staying inside the allowed scope.
• Failure taxonomy: label each failed run: wrong tool, bad arguments, wrong plan, stopped too early, looped, claimed success falsely, broke a policy. A tally by category tells you what to fix next. Pass rate alone does not.

Anthropic found end-state evaluation more practical than checking every turn for agents that change persistent state, a single LLM-judge prompt that output scores from 0.0 to 1.0 and a pass-fail grade to be the most consistent in their tests, and human testers still necessary because they find edge cases automation misses (Anthropic, 2025-06-13). Their setting was a research system, so test this on your own task.

Reliability: pass@k versus pass^k#

Run each task several times, because one run hides variance.

• pass@kpass@kThe chance that at least one of k runs succeeds. It hides run-to-run variance.Open the glossary entryClose: the task counts as solved if at least one of k attempts succeeds. The idea comes from code generation, where you may sample several solutions and keep one that passes the tests (Chen et al., 2021).
• pass^kpass^kThe chance that all k runs succeed. It is the right measure for an agent that must work every time.Open the glossary entryClose: the task counts as reliable only if all k attempts succeed. The tau-bench authors introduced it to measure how reliably an agent behaves over repeated trials (Yao et al., 2024). They report that even strong function-calling agents succeeded on fewer than half the tasks, and in the retail domain pass^8 was below 25% for gpt-4o (a 2024 model) (from the abstract, checked 2026-10-09).

Illustrative arithmetic. Suppose a task passes with probability 0.8 on each independent run and you take k = 5.

• pass@5 = 1 - 0.2^5 = 1 - 0.00032, about 0.9997. Looks great.
• pass^5 = 0.8^5 = 0.32768, about 0.33. A customer who tries five times will see at least one failure about two times in three.

Which one matters depends on the product. If a human can pick the best of several attempts, pass@k is meaningful. If the agent acts for a user once, such as issuing a refund, you need consistency, so pass^k is the honest number.

Graders, budgets and release gates#

• Graders: programmatic checks first (cheap, exact), then an LLM judge with a written rubric for what code cannot check, then humans on a sample to check the judge.
• Environments: sandboxed, resettable, as deterministic as possible. Mock tools for fast unit tests; a full sandbox for end-to-end runs.
• Run limits: per-run budgets for steps, tokens, time and money, so a bad run stops early (see the stopping controls in Agentic patterns).
• Operations: full traces so a failure can be replayed (prompt version, tool and arguments, result, tokens, latency and cost per step), a kill switch, and human approval before any irreversible action.
• Release gate: write thresholds before you look at results, for example a minimum pass^k on the core tasks, zero safety violations, and a cost ceiling per task. The numbers are your product’s choice, not a standard.

Diagram#

Diagram: Each task in the set runs k times in a sandbox.

Real-World Application#

A deep-research feature has an orchestrator, parallel searchers and a citation checker. Before launch, the team runs a fixed task set several times, grades by state where it can, uses a rubric judge for report quality, and has people read a sample of reports.

Interview Perspective#

Expect “how do you evaluate an agent”, “your agent is 80% on single runs, is it ready” and “how do you decide to ship”. A strong answer grades by state rather than by the agent’s message, adds trajectory metrics for cost and risk, reports repeated runs with pass^k for one-shot actions, and describes a gate with thresholds fixed in advance. Common mistakes: grading on the agent’s self-report, reporting one run, setting thresholds after seeing results, and ignoring cost and safety.

Practice Questions#

These are generated practice questions, not reported from any company.

• Basic: Why do you grade an agent on the state of the world and not on its final message?
• Intermediate: What does trajectory evaluation catch that state-based grading misses?
• Advanced: Why is pass^k more relevant than pass@k for an agent that acts once for a user?
• Product-Company: Design and evaluate a coding agent that fixes failing tests in a repository.

Activity#

A task passes with probability 0.7 on each independent run. Compute pass@3 and pass^3 by hand, then write one sentence on which of the two a one-shot refund agent should report and why. You should get pass@3 = 1 - 0.3^3 = 0.973 and pass^3 = 0.7^3 = 0.343.

Homework#

Write an eval plan for a booking agent. Include 20 tasks (some impossible, some adversarial), a state-based grader for each, trajectory metrics, k = 5 runs per task, a failure taxonomy, and release thresholds with your reason for each number. Say which graders are code, which are an LLM judge and which are human.

Quick Revision#

• Grade by final state and by trajectory, not by the agent’s claim.
• pass@k is “any of k”; pass^k is “all of k”. Production consistency needs pass^k.
• Programmatic graders first, then a rubric judge, then humans on a sample.
• Budgets, traces, a kill switch and approvals belong in the gate.
• Set thresholds before you look at results.

Check yourself#

• Checkpoint question: Your agent succeeds on 80% of single runs. Is it ready? What do you measure next?
• Independent re-test: Explain why an agent can pass every state check and still fail a release gate.
• Common misconception to avoid: “The agent said it finished, so the task passed.”

Related#

• Multi-agent systems: when to use them and what they cost
• Agentic patterns: ReAct, planning and memory
• Designing an agent product
• Evaluating LLM systems