Request Order Matters — History-dependent selective KV reuse — What does it mean?

The news. On October 5, 2026, researchers from Carnegie Mellon, Capital One, the University of Chicago, UC Berkeley, USC and the University of Washington posted Request Order Matters to arXiv. They ran a rolling-window financial agent on Qwen3-8B with LMCache and vLLM, replayed the same requests in five different orders, and measured how often the answers changed. At a matched 5% recomputation budget, answers disagreed in 69.0% of pairwise comparisons across the five orders with token top-k and 26.1% with document-aligned recomputation. Read the paper →

Picture a binder of 84 pages, each with a sticky note you wrote the last time you read it. Every hour you tear out the oldest page and add one at the back. The pages you kept did not change, but every note on them was written while different pages sat in front of them, so each note is a little off. You do not have time to re-read the whole binder, so you get a small budget to re-read some of it.

That is the exact situation of a long-running agent. Each call keeps most of its documents, evicts one and appends one, so every kept document shifts position and gets new preceding context. Prefix caching can only reuse an identical opening, so after the oldest document leaves, the shared prefix is little more than the fixed instruction. Non-prefix reuse loads each document's stored KV anyway, which is the sticky note: it skips the prefill work but lacks the cross-document attention a full prefill would compute.

The new finding is that the stale notes are not stale in a fixed way — how stale they are depends on the order earlier requests arrived. The cache persists between calls, so whichever request last stored a document's KV decides what the next request loads. Replay the same prompts in a shuffled order and the same prompt meets different cached state. The authors rule out ordinary noise: they ran with greedy decoding, issued one request at a time, and an independent repeat of the chronological order reproduced every answer exactly.

Now the re-read budget. Token top-k spends the budget on about 387 words spread across roughly 180 separate spots, each where your note disagrees most with the page; contiguous recomputation spends the same words on a few whole passages. In the paper's ablation every policy recomputed exactly the same number of tokens, yet under a shuffled order token top-k matched full prefill on 38.6% of requests while four different span-based policies reached 89.4–92.8%. The striking control: a policy that picked whole documents at random, ignoring the deviation score entirely, captured only 4.8% of the measured key deviation and still beat top-k by 50.8 percentage points. Top-k captured 99.7% of the deviation and lost.

The paper does not prove why scattered repair fails; it reports that contiguity, not document boundaries and not deviation ranking, is the property associated with robustness. One plausible reading, not the authors' claim: the selector picks positions once at one layer and reuses them for every later layer, and a lone recomputed token still attends to dozens of stale neighbours, while a recomputed passage refreshes a whole neighbourhood together.

Here is the worked example, with the model, the prompt length and the budget held fixed: Qwen3-8B, prompts of about 7.2K–7.7K tokens, an NVIDIA L4, and a 5% budget, which in the paper's 500-request ablation came to a median of 386–387 recomputed tokens per request. Full prefill took a median of 2,408 ms to the first token. Token top-k took 426 ms and document-aligned recomputation took 415 ms, so both are about 5.7× faster and their measured latencies are similar. In the ablation's shuffled-order run, the budget was a median of 387 tokens per request: top-k spread them across 180.5 separate regions, about two tokens per region, while document-aligned selection used six — whole document spans, plus one partial contiguous span if tokens were left over. Similar cost and similar TTFT, very different fidelity: across the four non-chronological orders in the main experiment it was 19.8–41.5% for top-k versus 54.3–91.7% for document-aligned.

Two limits matter before you change a serving config. First, the advantage showed up only under the tested persistent cache histories: the authors detected no statistically significant fidelity difference in chronological order (86.8% vs 85.4%) or in a 500-request control that reset the cache before every request (94.0% vs 92.6%). That means a reuse method that passes an isolated-request benchmark can still drift in production, where retries, branching agents and shared caches present the same prompt to different cache state — the same reuse trade-off prefix caching already forces you to measure. Second, this is one model, one workload — copying fields verbatim from financial records — and a reversed-order stress test still pulled document-aligned fidelity down to 54.3%. Contiguous repair is more robust, not immune.

Goes deeper in: LLM Serving → Prefix Caching & RadixAttention → Why Full-Prompt Hashing Fails

Related explainers

• Selective KV recomputation for RAG — how the repair step itself works on a single assembled prompt
• HEAR: workflow-aware KV caching — another case where agent request order changes what the cache holds