# Request Order Matters: Cache-History Sensitivity in Selective KV-Cache Reuse for Rolling Agents

arXiv: https://arxiv.org/abs/2610.05833 · HTML: https://mlsanity.com/paper/2610.05833/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Agent memory systems, one of 16 directions in LLM agents and tool use.
- Builds on 7 of its 11 references that are in the map.
- First posted on arXiv 5 Oct 2026.

## Placed in

- LLM agents and tool use / [Agent memory systems](https://mlsanity.com/agents/agent-memory-systems/)
- Efficient LLM inference and serving / [Efficient reasoning and agent inference](https://mlsanity.com/inference/efficient-reasoning-and-agent-inference/)

## Builds on (most cited first, 7 of 7)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [CacheBlend: Fast Large Language Model Serving for RAG with Cached Knowledge Fusion](https://mlsanity.com/paper/2405.16444/) (2024)
- [KVLink: Accelerating Large Language Models via Efficient KV Cache Reuse](https://mlsanity.com/paper/2502.16002/) (2025)
- [EPIC: Efficient Position-Independent Caching for Serving Large Language Models](https://mlsanity.com/paper/2410.15332/) (2024)
- [ProphetKV: User-Query-Driven Selective Recomputation for Efficient KV Cache Reuse in Retrieval-Augmented Generation](https://mlsanity.com/paper/2602.02579/) (2026)
- [An experimental study of KV cache reuse strategies in chunk-level caching systems](https://mlsanity.com/paper/2603.20218/) (2026)

## Abstract (arXiv)

Long-running agents repeatedly call an LLM while retaining most of their document window, evicting old documents, and appending new ones. These rolling updates break exact prefix caching and motivate non-prefix KV-cache reuse with selective recomputation. We show that persistent KV-cache reuse with selective recomputation can be history-dependent: in our rolling-agent workload, an unchanged prompt can produce different answers depending on the requests processed before it. At a matched 5% recomputation budget, document-aligned recomputation reduces answer variation across request orders from 69.0% with CacheBlend's token top-k policy to 26.1%. When each prompt is evaluated after a different sequence of preceding requests, document-aligned recomputation improves fidelity to full prefill by 34.5-52.5 percentage points over token top-k, while both policies achieve approximately 5.7× median TTFT speedup. Our ablation study shows that, in our rolling-agent workload, contiguity is the main factor associated with robust selective recomputation.