Cheng Tan

Replay Comes Back

A debugging framework for AI agents, and why it has to reach all the way down to the kernels

· systemsaiverification ·中文

An agent ran a task yesterday and it worked. It ran the same task today and did something else. Which of the two runs should you trust, and what exactly was different?

Right now nobody can answer that. The best practice is: run it again and hope. That was tolerable when models wrote poems, and it is not tolerable now that agents hold shell access. In our own measurements across 17 models and 10 system-administration tasks, pass rates routinely exceed 80%, yet two runs of the same task agree on the sequence of state-modifying actions only about 39% of the time. We have also watched runs diverge on nothing more than a clock: the same task, the same model, a different timestamp visible in the environment, and the agent takes another path.

This is not new to systems people. It is called non-determinism, and the systems community has been grappling with it for decades. What is different today is that the AI stack amplifies non-determinism across many layers.

Three layers of non-determinism

Unlike in traditional systems, where non-determinism is often contained within an abstraction layer, in AI stacks it can silently propagate upward and affect higher layers.

Non-determinism enters an agent run at three layers---tensor, token, and trace. Record every value the run could not have predicted, and you can replay it, free one layer to find the culprit, or change one value and watch the path fork.

Tensor. The arithmetic itself. Most inference kernels lack batch invariance: a reduction is carried out differently depending on how many requests are batched together, so a request’s output depends on the server’s load at the moment it arrived. Batch-invariant kernels remove this variation, at the cost of roughly 1.6x the latency. Underneath sit the slower drifts—a different GPU, a different library version—which vendors are explicit about: cuBLAS promises bitwise reproducibility only on the same architecture with the same number of SMs, and never across toolkit versions.

Token. Sampling. Temperature, top-p, and the RNG that draws from the distribution. This layer is the one everybody knows about and the only one with a user-facing knob, and even that knob is weak: the seed parameter is documented as a best-effort promise that determinism is “not guaranteed,” and it is now being deprecated.

Trace. The world. Timestamps, PIDs, file listings, network responses, tool output, and whatever another process did to the machine between two runs. This layer has a property the other two do not: the agent changes it. The run modifies the state that the next step reads.

Moreover, the layers compose upward: a tie broken differently in a reduction becomes a different token, which becomes a different shell command, which becomes a different sequence of actions. Noise at the bottom is behavior at the top. That is why a debugger for agents cannot live at the framework boundary.

TTTR: record, replay, and steer

TTTR is Tensor-Token-Trace-level Replay: record a run’s non-determinism at all three layers, and replay it.

Record. Capture every value the run could not have predicted—the batch composition or the kernel outputs at the tensor layer, the sampled tokens and seeds at the token layer, the clock, PIDs, and tool results at the trace layer. This is an old idea with a long systems pedigree: ReVirt logged beneath an untrusted OS, R2 let the programmer choose where to cut, and rr made record-replay cheap enough to use every day.

Replay. Run it back and get the same execution. Here the classic literature supplies a warning worth taking: ODR gave up on reproducing the identical execution and guaranteed only the same output, because inferring an exact schedule is ruinously expensive. For agents, bit-identical replay is likewise the wrong bar. What you want is a replay that reaches the same decisions.

Selective replay. This is the point of the whole exercise. Pin two layers and let the third float. Or replay everything faithfully except one recorded value—advance the clock by a second, hand back a different tool result, flip one sampled token—and watch where the trajectory forks. The systems precedent is mutable replay, which replays a recording against modified code; TTTR generalizes it from code mutation to any single source of non-determinism. And it turns delta debugging—Zeller’s method of binary-searching the minimal failure-inducing change, from the paper titled “Yesterday, my Program Worked. Today, it Does Not. Why?”—into something you can run across layers rather than within one input.

What you would do with it

Locate the layer. The agent worked yesterday and fails today. Replay today’s run with the tensor layer pinned to yesterday’s recorded values: if the failure disappears, the arithmetic moved under you. Pin the trace layer instead: if it disappears, the environment changed. This is triage that currently does not exist, and it answers the question every on-call engineer actually has—not “what did the agent do” but “what is different.”

Run the counterfactual. Change exactly one thing and hold everything else. Would the agent still have killed the process if the port had been free? Does this task depend on the date? Today those questions are answered with anecdotes and re-runs, which confound every variable at once. Replay converts them into controlled experiments with a single independent variable. A recent preprint on causal attribution for agent failures does this statistically, by intervening on a step and re-sampling; a replay system would let you do it mechanically, which is both cheaper and sharper.

Report honest numbers. Pass rate hides everything this post is about. With replay you can hold the lower layers fixed and measure how much of a benchmark difference is the model and how much is noise—a variance decomposition for agent evaluation. A benchmark delta of two points means nothing if two runs of the same agent agree only 39% of the time on what they did.

Determinism was always engineered

Determinism was never a property computers had naturally. It was built, at considerable cost, and then quietly relied on by everyone who ever attached a debugger. Threads eroded it, and the record-replay literature spent decades winning it back. Agents have now removed it again.

We are on our way to recovering determinism in AI. This time the payoff reaches past debugging: the group that built batch-invariant kernels found that once inference was deterministic their reinforcement learning became genuinely on-policy, the divergence between sampler and trainer sitting flat at zero. A system you can replay is a system you can check, and a system you can check is one you can train against. We gave up reproducibility at precisely the moment we started running programs whose behavior we cannot predict.

References