Paper of the Week — Contiguity, Not Importance: Budgeted Repair of Stale KV Caches After Document Edits
KV-cache repair after edits: a new paper shows patching only contiguous changed blocks beats importance-scoring by 2–3× on latency with near-zero quality loss.
Contiguity, Not Importance: Budgeted Repair of Stale KV Caches After Document Edits
Mingyang Mao, Wyatt Mackey, Xiaomin Lin. Published 2026-09-16. arXiv:2609.17983
One sentence summary
When a retrieved document or memory chunk is edited, recomputing only the contiguous span of KV states starting at the edit point — rather than scoring and selecting “important” tokens globally — delivers the best latency-quality tradeoff under a compute budget.
Why this paper
KV-cache reuse is now standard practice in RAG pipelines and long-context agentic systems, but almost nobody has a principled story for what to do when the cached context changes mid-session. As systems like Claude Fable 5.1 and GPT-6 Astra push toward persistent memory and background agents that update their working state continuously, stale-cache handling is becoming a real production problem, not an academic edge case.
What they did
The authors studied what happens under causal self-attention when a local edit (a fact correction, a policy update, a tool result) invalidates some prefix of a cached context: because each token attends to everything before it, even a small change can corrupt all downstream KV states. They compared three repair strategies under a fixed recompute budget — full re-prefill, importance-scored selective recomputation, and contiguous repair (recompute from the edit point forward, stop when the budget is exhausted). They evaluated these across RAG benchmarks with realistic edit patterns and measured both output quality and wall-clock latency.
Key findings
- Contiguous repair matches or beats importance-scoring on output quality across every benchmark tested, despite being conceptually simpler
- Importance-scoring incurs significant overhead from the scoring pass itself, eating into the compute budget that should go toward actual repair
- Full re-prefill is the quality ceiling but 3–5× slower than contiguous repair at typical edit sizes
- The quality gap between contiguous repair and full re-prefill narrows quickly as edit size shrinks — for single-sentence edits, contiguous repair recovers >95% of full re-prefill quality
- Random token selection (the naïve baseline) degrades significantly on multi-hop reasoning questions, confirming that edit locality matters
Why it matters for practitioners
If you’re building any system that reuses KV caches — RAG with document versioning, agentic loops with mutable working memory, or chat sessions where system prompt sections get updated — you now have a concrete, low-complexity repair strategy that outperforms fancier alternatives. The implication is that you should structure your context so editable regions are localized toward the end of the prefix, maximizing the portion of the cache you can preserve untouched.
What you can use today
- Architect your prompt layout so stable content (instructions, static context) comes first and mutable content (retrieved chunks, tool results, user state) comes last — this minimizes how many downstream KV states an edit invalidates
- When a cache miss or staleness is detected, implement contiguous repair by re-prefilling from the first changed token forward until your latency budget is consumed, rather than building an importance scorer
- If you’re using a framework with explicit KV-cache management (vLLM’s prefix caching, SGLang’s RadixAttention), track edit offsets alongside cache keys so you can trigger targeted repair rather than full eviction