Determinism and Flakiness in Agent Test Suites

A flaky test is one that passes or fails inconsistently with no change to the underlying code, a symptom of nondeterministic behavior rather than a bug in the test's own logic. The distinction tells an engineer where to look: not at the assertion, but at whatever is introducing variance underneath it. Bitrise's Mobile Insights 2025 report, built from an analysis of over 10 million builds, found that the share of teams experiencing flakiness climbed from 10% in 2022 to 26% in 2025. Atlassian put a number on what that costs at scale: over 150,000 developer hours burned every year across its own engineering organization. Industry-wide estimates frame flaky tests as a $512 million problem, with 59% of developers running into flakiness regularly and enterprise teams losing more than 8% of development time to test failures.

What makes this bearable, historically, is that the causes are known and fixable. Async and timing issues account for something like 45% of flaky tests, concurrency and resource contention around 20%, and test-order dependencies about 12%. Those are diagnosable categories, not mysteries. Better isolation, mocking of external dependencies, retry logic, and quarantine mechanisms all work here, because the system being tested is deterministic underneath the flakiness. The flake is a defect in test design or environment control. Teams that invest in isolation and mocking are, in effect, restoring the assumption that same input plus same code should equal same output every time.

That assumption is the whole foundation of conventional software QA, and it is about to stop holding.

How LLM nondeterminism is structurally different from timing bugs and race conditions

Setting temperature to zero is often treated as a guarantee of consistent output, but it isn't one. Temperature zero only forces greedy token selection: at each step, the model picks the single highest-probability token instead of sampling. It says nothing about whether that probability calculation comes out the same way twice.

It often doesn't, and the arithmetic itself explains why, as the reasons for the discrepancy can be traced directly through the calculations. Floating-point addition is not associative: the order operations happen in can change the result. GPU kernels' reduction order varies with input shape, including batch size, and batch shape on hosted APIs depends on concurrent traffic outside developer control. The consequence is that identical prompts can produce slightly different logits run to run. Most of the time this changes nothing, because one token is clearly ahead of the rest. But at the positions where the top two candidates are nearly tied, that tiny numerical wobble can flip which one wins, and autoregressive decoding takes that single flipped token and builds an entirely different continuation on top of it.

This isn't speculation. A peer-reviewed study presented at Eval4NLP 2025 in Mumbai, titled "Non-Determinism of 'Deterministic' LLM System Settings in Hosted Environments," found no LLM that consistently delivers the same outputs or accuracy on a given task, and pointed to input buffer packing across concurrent jobs as one likely source. The model providers themselves don't claim otherwise. Anthropic recommends sampling multiple times and cross-checking for consistency rather than trusting a single output. Google describes its outputs as "mostly" deterministic, a qualifier doing real work. OpenAI offers a seed parameter explicitly framed as something that will "further reduce," not eliminate, nondeterminism.

Reasoning models make the picture worse, not better. Systems that generate a hidden chain-of-thought before answering, OpenAI's o-series, Anthropic's Claude with extended thinking, and the reasoning-mode models that came out through 2025 and 2026, can take entirely different internal paths on separate runs at the same temperature setting, sometimes converging on the same final answer and sometimes not. The variance sits inside the reasoning process itself.

None of this is a defect to be patched. Sampling is the mechanism by which these models generalize to inputs they haven't seen framed exactly that way before; strip out the variance and capability degrades along with it. A race condition is an implementation mistake, something a more careful engineer could have avoided. LLM variance is a design property of the architecture. The standard fix repertoire, isolation, mocking, retries, is aimed at the wrong layer of the problem entirely.

Why nondeterminism compounds exponentially across agent chains

A single unreliable step is a nuisance. A chain of them is a different kind of problem altogether, and the math behind it is unforgiving. A June 2026 paper out of Alibaba Group, "Grounded Scaling: Why Agentic AI Needs Deterministic Environments" by Liang Ding and Xintong Wang, formalizes this: if each step in an agent's process succeeds with probability δ less than 1, a chain of k steps succeeds at rate δ raised to the k, an exponential decay, not a linear one.

Running the numbers makes the implication obvious fast. Every tool call, every routing decision, every model inference along the way is another multiplication against that shrinking probability, and no amount of per-step reliability fully rescues a long enough chain. This is not a hypothetical concern about deep pipelines somebody might build eventually. Independent evaluations on OSWorld and τ-bench already show long-horizon success rates for production agents sitting well below single-turn success rates, which is exactly the degradation curve the exponential model predicts. The paper names the production systems operating at this scale directly: Anthropic's Computer Use, OpenAI's Operator, and the open-source agents that followed them.

Inside a running agent, three separate sources of nondeterminism stack on top of each other, according to the Chronicle paper (arXiv:2609.20625). Inference itself isn't bitwise reproducible. Tools read external state that may have changed since the last run. And retries or routing logic change how many times a given step actually executes. None of these sources are visible from the outside as a single clean signal; they blend together into a trajectory that a re-run rarely reconstructs.

The security community, for what it's worth, hasn't caught up to any of this. The Crew Scaler study scored 16 agent frameworks against 193 threat items across 9 categories, and the Non-Determinism category came out with a mean score of just 1.231 across all 16 frameworks, weaker than any other category assessed. That's a significant gap. It means the field has not yet started treating nondeterminism as a threat surface, let alone worked out how to test against it.

Carrying forward into everything downstream, an agent failure is not one bad run to be dismissed and re-tried. It's a specific trajectory of model calls, tool calls, and routing decisions, and re-execution almost never walks that same path twice. That single fact is what makes turning an incident into a repeatable regression test so hard, and it's the problem the rest of this piece is really about.

Why the standard response (better isolation, retries, mocking) makes agent tests less useful, not more

Retrying a failed agent test doesn't reproduce the failure. It generates a new trajectory, one that may well pass, and the temptation is to read that pass as evidence the issue resolved itself. Retrying didn't reproduce the failure. Nondeterminism simply produced a different run, and the underlying failure mode is still sitting there, waiting for the trajectory that triggers it again.

Heavy mocking creates a related illusion. Swapping in hand-written stubs for real model and tool behavior means the test is now validating a developer's guess about what the system would do, not what it actually did. Chronicle's authors document this limitation directly: a change to a tool gate or a router can pass cleanly against mocks and still fail against real model output, because the mock never had to be right, only plausible.

Exact-match assertions fail for a more basic reason. A string-match assertion treats the difference as a failure, and worse, it manufactures false confidence in the other direction too: a lucky run that happens to match the expected string gets marked a pass, even if the underlying behavior is fragile and the next run won't match at all.

Tracing systems record what happened during a run. Evaluation frameworks score whether the final output was acceptable. But neither lets a developer take one recorded run, change a single component, and check whether that change fixes the failure while holding everything else constant. That capability, isolating one variable inside a fixed trajectory, is precisely what regression testing depends on in ordinary software, and it's missing here.

The numbers suggest this gap is not closing on its own. Documented AI incidents rose from 233 in 2024 to 362 in 2025, and hallucination rates measured across 26 leading models range anywhere from 22% to 94% depending on task. Agent quality is the actual bottleneck, and isolation, mocking, and retries, the tools built for a different kind of flakiness, are not touching it. Treating nondeterminism as noise to be suppressed misreads what it is. Agent architecture needs that variance to function at all; trying to stamp it out doesn't make the system more testable, it makes the system worse.

The first pillar of a new testing contract: separating deterministic logic from genuinely nondeterministic behavior

The traditional testing pyramid still applies here in structure, cheap and fast checks at the base, expensive and slow ones near the top, but the layers need to be reorganized around a different question: what in this agent is actually deterministic, and what isn't.

At the base sit ordinary unit tests: tool functions, parsers, prompt templates, argument parsing, response formatting, state machine transitions. None of this touches an LLM, none of it needs to, and all of it can run on every commit at essentially no cost. Above that come single-turn graded component tests, then multi-turn integration tests against real tools, then slow end-to-end agentic tasks, and at the very top, sampled human evaluation.

The discipline that makes this pyramid work is pushing as much verification as possible down into the deterministic base, and reserving the expensive, multi-run, LLM-graded evaluation for behavior that is genuinely probabilistic. It's a substantive constraint on resource allocation. It's a resource allocation decision, because LLM-graded tests cost real inference dollars and real wall-clock time, and running them against logic that was never nondeterministic in the first place is money spent testing something a plain assertion already covers.

A layer zero underneath the pyramid is required for any of it to work. Structured traces need to capture the prompt, the model, every tool call and response, the reasoning, the output, and the cost. Prompts, datasets, eval configurations, model identifiers, and tool specs all need version control. And the whole thing has to run inside a repeatable execution environment, whether that's CI, a laptop, or a scheduled job. Without those three things in place, per Chronicle (arXiv:2609.20625), there's no stable ground to build the rest of the pyramid on. The question to ask of any agent test suite is which parts of the system are nondeterministic. It obviously is. It's which parts are, and whether those specific parts are being tested with tools built for that kind of variance.

The second pillar: probabilistic assertions and statistical thresholds instead of pass/fail

Once the deterministic base is handled, what's left needs a different kind of assertion. Instead of running a prompt once and checking it against an expected string, run it some number of times, typically a small handful up to around ten, and report a mean and a standard deviation. The test suite now tracks variance as a number, rather than treating it as an inconvenience to explain away.

Under this model, passing means the mean outcome clears a set threshold and the variance stays inside an acceptable band, not that one particular run happened to match. Practitioners have converged on a rough industry benchmark for what "too flaky" looks like: a test exceeding a 2% nondeterministic failure rate gets flagged. For agent suites, that threshold can't be a one-time check. It needs continuous monitoring across execution histories, because any test exceeding a 2% nondeterministic failure rate is flagged as flaky and this threshold must not be spot-checked manually.

The assertions themselves need to change shape too, tolerating semantic equivalence rather than demanding byte-exact matches. Pinning temperature, seed, and model version narrows the space of possible outputs, but the assertion still has to accept a whole equivalence class of correct phrasings rather than a single expected string.

One way to stress-test these thresholds directly: stand up a second LLM as a user simulator, give it distinct personas and varying frustration thresholds, and run each scenario across multiple concurrent trials to build out confidence intervals and aggregate success distributions rather than reading a single pass or fail. This only means something, though, if it's run against a stable dataset. Skip the curated dataset and repeated runs just measure how much the prompt itself varies, which tells nobody anything about whether the agent is actually reliable.

The third pillar: boundary-record replay to turn incidents into repeatable regression tests

The hardest problem in all of this is the one already flagged earlier: re-running a failed agent doesn't reproduce the failure. Inference isn't bitwise reproducible, tools read state that's already changed, and retries reshuffle execution order, so the incident that showed up in production yesterday quietly vanishes the moment someone tries to reproduce it locally. Without reproduction, there's no regression test, and without a regression test, the same failure mode can resurface indefinitely with nobody able to prove whether it was ever actually fixed.

Chronicle, built by Tisha Chawla and Susheem Koul at Microsoft (arXiv:2609.20625), addresses this directly by recording an agent run at each of its nondeterministic boundaries, wrapping each one as an immutable envelope, and replaying the run from that record. The core operation is what the paper calls cut-point replay: a developer chooses a subset of boundaries to serve from the recorded envelopes, executes the remaining subset live against new code, and the recorded incident becomes a test that runs inside continuous integration. This is the capability tracing and evaluation tools were missing: changing one component of a recorded run and checking whether that change fixes the failure while everything else stays fixed.

The benchmark numbers back the approach up. Across 6 recorded failures with simulated model boundaries, recording overhead came to 23 microseconds per boundary crossing, about 0.008% of an assumed 300-millisecond model call. Full replay issued zero live model calls and stayed bit-stable across 20 repetitions. Cut-point tests failed on faulty code and passed on guarded, benign changes across all 6 incidents. In a mutation study, the cut-point tests caught every mutant that let an unsafe action slip through, while a baseline that stubbed every boundary using the same assertion logic caught none of them.

Existing tools each do a piece of this and stop short. Tracing platforms like Arize AI record what happened during a run, but recording isn't the same as making that run testable. Evaluation frameworks such as promptfoo score whether an output was acceptable, but don't support changing one component and re-testing against a fixed trajectory. Graph frameworks like LangChain's checkpointing resume or steer a live run in progress; Chronicle instead operates after the run has already finished, replaying against a past incident rather than steering a future one. Chronicle adapts that same selective-replay idea to agent boundaries specifically, indexing each crossing and letting the developer choose freely which parts run live.

What this replaces, structurally, is the hand-written mock. Instead of a stub built on a developer's guess about what a model would return, the test draws from an envelope recorded from an actual past run, exercising real behavior instead of an assumption about it.

The fourth pillar: behavior-level and trajectory validation instead of output matching

Judging an agent purely on its final answer misses most of what can go wrong along the way. Agents involve long chains of tool use, dynamic back-and-forth, and artifacts that need independent verification, and a judge that only reads the final output can be fooled by text that sounds plausible without checking that the underlying execution actually supports it. Research has a name for this failure mode: hallucinated correctness, an evaluation that scores a run as successful because the ending reads well, not because the work behind it held up.

Trajectory analysis is the corrective. Instead of grading only the terminal response, it evaluates the sequence of tool calls, routing decisions, and intermediate states that got the agent there. An agent that reaches the correct answer through a broken or fragile path is a reliability risk sitting quietly under a passing test, and only trajectory-level evaluation can tell that case apart from one that got the right answer the right way.

LLM-as-judge evaluation is one practical way to apply this at scale, running the same rubric against every single output rather than relying on inconsistent human reviewers. MLflow's evaluation layer documentation reports this approach reaching over 80% agreement with human evaluators, which is enough consistency to make automated rubric-based grading a real substitute for manual review across large test volumes. Behavior-level validation, in other words, is the only version of testing that actually matches what agents do. It's the only version of testing that actually matches what agents do.