How do you test a non-deterministic agent?

In this article

1. Before you start
2. Why interviewers ask this
3. Testing a non-deterministic agent from first principles
4. The Staff-level answer
5. The rubric
6. Three variants of this question
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one part of the AI agent architecture path and assumes the basics from prompt engineering.

Why interviewers ask this

An answer that treats an agent like ordinary code, one input and one expected output, fails this question in its first sentence. Candidates report the question in agent-focused rounds. It tests whether you know where the variance comes from, what to measure instead of exact output, and how to report reliability.

A weak answer says "set temperature to zero and assert on the output." A strong answer separates the final state of the world from the agent's words, repeats every task several times and names pass@k and pass^k. A Staff-level answer also tests the tests: a task that never passes is often a broken task rather than a broken agent, and a rigid grader can mark a valid solution as wrong. The question sits next to design questions such as how to design an AI agent system, because a loop you cannot test is a loop you cannot ship.

Testing a non-deterministic agent from first principles

Trial

A trial is one attempt by an agent at one task, started from a clean state, so running the same task several times gives several trials whose results can differ. Anthropic uses the word for each attempt at a task, and a test suite is built from many tasks with several trials each.

In plain words

Think of testing a new employee who books flights. You would not check that they use the same words on every call. You would check that the reservation exists afterwards. You would also watch several calls, because one good call proves little.

The analogy breaks in one place. A person improves with feedback, while an agent's chance of success stays the same until you change it. That is why repeated runs give a stable rate.

In one precise sentence, testing a non-deterministic agent means measuring a success rate over repeated runs, with graders that judge results rather than wording.

Test the deterministic parts with ordinary unit tests

Most of an agent is ordinary code, and ordinary code gets ordinary tests. Tool functions, argument parsers, permission checks and the control flow of the loop are deterministic, so write unit tests for them, with the model call replaced by a stub or a recorded response that returns a fixed tool call. Those tests run fast, fail the same way every time and belong in every build. Keep the repeated-trial evaluation for what only the model decides: which tool to call, with which arguments, and when to stop. That split keeps the expensive statistical runs small and stops a plain bug in a tool from being mistaken for model variance.

Step 1: Pin down the setup, and expect variance anyway

Pinning down the setup removes the variance you control, but not all of it. Fix the model version, the tool code and the starting data. Give every run a fresh copy of the environment so one run's leftovers cannot help the next; Anthropic's article recommends isolating trials from a clean environment (Anthropic, 2026).

In the tau-bench benchmark the database tools are deterministic Python functions and the starting data is the same each time. The agent ran at a temperature of 0.0 and the simulated user at 1.0, so sampled language still produced varied conversations. Even so, the best gpt-4o function-calling agent, with more than 60% average task success, dropped below 25% on pass^8 in the retail domain (Yao et al., 2024).

The paper does not say temperature zero is non-deterministic in general. It shows that results varied across trials. Expect variance and measure it. You now know why one run is not enough.

Where does the variance come from when temperature is zero?

Four sources add variance even when the agent's temperature is zero. First, the user: a simulated user sampled at a higher temperature, or a real person, words each request differently. Second, the hosted model: a temperature-zero call can return different text from one run to the next, because the numerical kernels can change with batch size and the server's load changes the batch; Thinking Machines Lab (2025) attributes run-to-run differences to batch-size-dependent kernels.

Third, provider updates: a model alias can start pointing at a new version, so pin a dated version where one exists. Fourth, tools that read live data or the clock return different results on different days. Tau-bench removes that last source with deterministic tools and fixed data, which is why its variance traces to sampled language.

Step 2: Run each task several times

Running each task several times turns one lucky or unlucky result into a rate. Anthropic puts it this way: "Because model outputs vary between runs, we run multiple trials to produce more consistent results" (Anthropic, 2026).

Each task runs several times in a fresh environment. The input is one task and its starting state. The output is a list of pass-or-fail results for that task, one per trial.

The tau-bench authors used at least 3 trials per task for their main results (Yao et al., 2024). The cost grows in proportion to the number of trials, so a team balances the number of tasks against the number of runs per task. You now have repeated results; the next step decides what counts as a pass.

Step 3: Grade the outcome with code

Code grades the outcome, the final environment state, rather than what the agent says. Anthropic defines the outcome as "the final state in the environment at the end of the trial." Its example: a flight-booking agent might say "Your flight has been booked," but the outcome is whether a reservation exists in the environment's Structured Query Language (SQL) database (Anthropic, 2026).

Tau-bench does exactly this: it compares the database at the end of each episode with an annotated expected state (Yao et al., 2024). That works because many different paths reach the same state, so the grader does not need to match the agent's wording or its exact steps.

Code graders are fast, cheap, objective and reproducible, but brittle to valid variations that do not match the expected pattern exactly. Input: the final state. Output: pass or fail.

Step 4: Grade the trace

A trace grader checks tool choice and policy by reading the whole record of a run. A trace is the end-to-end record of model calls, tool calls, guardrails and handoffs for one run (OpenAI, evaluate agent workflows). Trace grading assigns structured scores or labels to that record to assess correctness, quality or adherence to expectations (OpenAI, 2026). It can ask whether the agent picked the right tool and whether it violated an instruction or safety policy.

The reason is that a matching final state is necessary but not sufficient. The tau-bench authors note that an agent might issue a return without explicit user confirmation, which violates the policy (Yao et al., 2024).

Anthropic lists three grader types: code-based, model-based and human. A model-based grader, one run by a large language model (LLM), is flexible but non-deterministic, costs more than code and needs calibration with human graders (Anthropic, 2026).

Step 5: Report pass^k beside pass@k

pass^k reports reliability and pass@k reports best-case ability, so a good test reports both. pass@k is the chance that an agent gets at least one correct solution in k attempts (Anthropic, 2026). pass^k is the chance that all k trials succeed, averaged across tasks (Yao et al., 2024).

Take an illustrative per-run success of 0.75, with independent runs. Then pass^3 is 0.75 multiplied by itself three times, which is 0.4219, while pass@3 is one minus 0.25 cubed, which is 0.9844.¹ The report gives pass^k beside pass@k. pass^k falls as k grows while pass@k rises.

Use pass@k when one good attempt is enough, such as a search that allows retries. Use pass^k when the agent must work every time, such as customer service.

Text description of the diagram

• With 0.75 per-run success, pass^3 is 0.4219 and pass@3 is 0.9844.
• pass^k falls as k grows while pass@k rises.

How do you compute pass^k from a handful of runs?

The product of the per-run success rate is exact only if every task has the same success rate, which real suites do not. Tau-bench therefore averages per task. With n trials and c successes on a task, the unbiased estimate is C(c,k) / C(n,k), where C(a,b) counts the ways to choose b items from a (Yao et al., 2024).

Take an illustrative task with 5 trials and 4 successes. For k = 3, pass^3 is C(4,3) / C(5,3), which is 4 divided by 10, or 0.4. The matching pass@3 is 1, because only one trial failed, so any 3 of the 5 trials include at least one success.¹

The average matters. Four illustrative tasks with per-run success of 1.0, 0.9, 0.6 and 0.2 have a mean of 0.675, and 0.675 cubed is about 0.31. Averaging each task's own cube gives about 0.49.¹

All values in the table are computed from the illustrative inputs shown in each row.¹

1 · Pin the setup2 · Run trials3 · Grade the outcome4 · Grade the trace5 · ReportReplay

Step-by-step description

1. Fix model, tools and starting data.
2. Run each task several times, fresh state each time.
3. Code checks the final state.
4. A trace grader checks tools and policy.
5. Give pass^k beside pass@k.

• Each task runs several times in a fresh environment.
• Code grades the final environment state.
• A trace grader checks tool choice and policy.
• The report gives pass^k beside pass@k.

The Staff-level answer

What makes it Staff-level: it names where variance comes from, grades state before words, reports a reliability metric with its trade-off, and questions the test itself.

The rubric

Three variants of this question

How do you test an agent when the final answer is free text?

Use a model-based grader with a clear rubric, and calibrate it against human graders, since model graders are non-deterministic and need calibration for accuracy (Anthropic, 2026). Where part of the answer is checkable, such as a number or an id, grade that part with code.

How do you know a new prompt did not break the agent?

Keep a regression suite of tasks the agent already handles. Anthropic says regression evals ask whether the agent still handles all the tasks it used to and should have a nearly 100% pass rate (Anthropic, 2026). Run every task several times, since one pass can hide a drop in reliability.

Is pass@k or pass^k the right number for my agent?

It depends on whether one success is enough. If the user can retry and any good result helps, pass@k fits. If every conversation must go right, pass^k fits, because it falls as k grows and punishes inconsistency.

Common mistakes

• "I set temperature to zero, so my tests are repeatable." (wrong) Variance also comes from the simulated user, provider-side inference and any tool that reads live data; in tau-bench the agent ran at 0.0 and results still varied across trials. (right) "I pin what I can and still run several trials."
• "It passed once, so it works." (wrong) Anthropic notes a task that passed on one run might fail on the next. (right) "I report a rate over several trials."
• "The agent said 'booked', so the test passed." (wrong) The message is not evidence. (right) "I check that the reservation exists in the database."
• "I require the agent's steps to match one reference trajectory exactly." (wrong) Many valid paths exist, and code graders are brittle to valid variations. (right) "Many valid paths exist; I grade the end state and check the trace for required tools and policy, not for one exact sequence."
• "The eval failed, so the agent is bad." (wrong) The task may be ambiguous or the grader rigid. In Anthropic's account, Claude Opus 4.5 "failed" a tau2-bench flight task as written but found a better solution through a policy loophole. (right) "I read the failures before I trust the score."

Follow-up questions

How many times should you run each task?

There is no single correct number of trials. Tau-bench used at least 3 trials per task for its main results and more than 40 per task while looking for ambiguous tasks (Yao et al., 2024). More tasks and more runs narrow the uncertainty: for an illustrative 24 passes out of 30 runs, a Wilson interval, a standard confidence interval for a proportion, runs from about 0.63 to 0.90 at 95%.¹

How do you grade with an LLM judge when the judge is also non-deterministic?

Calibrate it against human graders, as Anthropic advises, and prefer code graders wherever the answer is checkable. For disputed cases, a practical step is to run the judge more than once and send disagreements to a human reviewer.

How do you test a conversational agent that talks to a user?

Use a second language model to play the user, as both Anthropic and tau-bench describe. In tau-bench the simulated user runs at a temperature of 1.0, so the same scenario produces varied but faithful dialogue, and the task is written so that only one final database state is valid (Yao et al., 2024).

What is the difference between a capability eval and a regression eval?

A capability eval starts at a low pass rate and measures what the agent can learn to do. A regression eval should pass nearly every time and guards against breakage. Anthropic describes capability tasks graduating into the regression suite once the agent masters them.

What happens to pass^k at 90% per-run success when k grows from 10 to 100?

It collapses. At 0.90 per-run success, pass^10 is 0.3487 and pass^100 is 0.0000266, and the same product rule applies to a chain of independent steps, which therefore needs a much higher per-step success rate.¹

Where does this fit in the wider evaluation of agents?

Repeated runs and grading are one part of agent evaluation; the wider topic, including trajectories and tool accuracy, is in evaluating agents. Where a wrong action is costly, a human in the loop reviews it before it runs, and the agentic AI interview questions list shows how these answers are asked.

Sources

1. tau-bench: A Benchmark for Tool-Agent-User Interaction in Real-World Domains (arXiv 2406.12045) — arXiv (Yao, Shinn, Razavi, Narasimhan), 17 Jun 2024
2. Demystifying evals for AI agents — Anthropic, 9 Jan 2026
3. Trace grading (undated documentation page; the date is the access date) — OpenAI API documentation, 26 Oct 2026
4. Evaluate agent workflows (undated documentation page; the date is the access date) — OpenAI API documentation, 26 Oct 2026
5. Defeating Nondeterminism in LLM Inference — Thinking Machines Lab, 10 Sep 2025