Same request. Same seed.
The cache is the input you didn't send.

Floating-point addition is not associative

When consecutive requests share a leading span of tokens, the server reuses the key and value tensors it already computed for that span instead of recomputing them. The tokens are the same either way. The arithmetic is not: reusing cached tensors changes the order in which floating-point accumulations happen, and floating-point addition does not give the same answer in a different order. The difference is tiny — far below anything you would call an error — and it only has to be large enough to reorder the two leading candidates for one token.

That is why quantization amplifies it. Coarser weights compress the gaps between competing token logits, so when candidates sit closer together a smaller numerical perturbation is enough to reorder them, and the same cache-induced difference flips more decisions. Note what this is not: every request in the study was issued serially at batch size one, so this is not the familiar batching non-determinism, and the cache itself was stored at 16 bits in every arm — the amplification comes from the weights.

Ten turns is all the leverage it needs

On single-turn maths at 16-bit, the cached and cold paths give different responses on 3.5% of items. That sounds ignorable. An agent episode chains about ten requests, and each one carries the whole conversation so far, so a single changed token propagates through every remaining turn. Drag the chain length and watch a 3.5% per-request rate become the measured 36.2% per-episode rate.

The compounding model is a rough one — it assumes each request diverges independently — but it lands close enough to the measured episode rate to make the point: nothing dramatic has to happen per request for an agent run to be irreproducible end to end.

Coarser weights, wider gap

Ten configurations, 80 episodes each, every arm run twice. An episode counts as divergent if any request differs or if the two runs issue a different number of steps. Step through the weight formats on Qwen2.5-7B under llama.cpp, the cell the study covers most fully.

The control is what gives the rest its force. With caching disabled, repeated execution was bit-identical in every configuration — zero divergences in 800 episodes, which puts a 95% upper bound of 0.5% on every other source of non-determinism in the setup. GPU scheduling, atomics, driver behaviour: all of it is bounded below half a percent, so the double-digit numbers above cannot be explained away as hardware noise.

Determinism given a state you cannot see

Three experiments pin down where the irreproducibility actually lives, and the answer is not the prefix cache under study. llama.cpp keeps a second cache above it: a host-memory store of whole conversation states, selected by longest-common-prefix similarity rather than by exact identity, evicted oldest-first. Which state you get depends on what the server handled before you.

The third experiment is the one that changes how you should think about this. Pin the cache state — cold before every recompute pass, warm before every cached pass, verified from the reported cached-token counts — and each path reproduces perfectly, 40 of 40 either way. They still disagree with each other on 14 of 40. So cached serving is not random. It is a deterministic function of the request and the cache state, and the cache state is a hidden input that the API does not accept, does not report, and does not reset.

Not worse. Just not repeatable. illustrative

The obvious next question is whether cached serving is simply worse, and the honest answer is no. On single-turn maths with 500 items, the two paths give different responses on 45.4% of them while accuracy moves 453 to 459 — and the 20 outcome flips pooled across configurations split 13 toward the cached path and 7 toward recompute, which is a coin. Your leaderboard number is unchanged. Which items you got right is substantially reshuffled.

Three things break as a result, and none of them is accuracy. A failure you saw once may not reproduce on replay, not because you captured the input wrong but because the server's cache state has moved on. An A/B comparison between two prompts run at different times against a shared endpoint is confounded by whatever else that endpoint served in between. And a system that has to be auditable cannot get that property from a cache-enabled endpoint at all.

What the paper actually reports