Repair stale key value caches faster using local contiguous edits
Contiguity, Not Importance: Budgeted Repair of Stale KV Caches After Document Edits
Artificial Intelligence
Summary
When computers use memory caches to speed up understanding or generating text, small changes in documents can cause parts of the cache to become outdated, leading to errors. The authors show that updating only the part of the cache closest to the change, rather than redoing the whole cache, keeps most answers accurate and is much faster. They found that spreading out updates to scattered parts of the cache is less effective because those parts can still be affected by stale information nearby. This approach works best when the important text stays next to the edited section.
What this means in practice
- •For machine learning engineers: Repair local cache states quickly after document edits to reduce costly full recalculations during model inference.
- •For software developers building ai assistants: Maintain consistency of cached knowledge in conversational agents by fixing only immediately adjacent stored states following user or knowledge updates.
Authors
Mingyang Mao, Wyatt Mackey, Xiaomin Lin
Abstract
KV-cache reuse can reduce inference cost in retrieval-augmented generation and agentic systems, but cached contexts may become stale when retrieved knowledge, working memory, or user state is edited. Under causal self-attention, even a local edit can affect downstream KV states. A full re-prefill reliably restores consistency but is costly, whereas refreshing only the edited span can leave downstream dependencies stale. We formulate in-place repair as budgeted recomputation and compare training-free position-selection policies on a factual RAG benchmark with matched direct and derived edits. Across three model families, all policies repair direct cases, but derived cases clearly separate them. At the primary budget, a contiguous edit-local window recovers at least 0.94 of the post-edit answer margin and substantially outperforms attention-based, KV-deviation, and structural selectors. Mechanistic analysis shows that position sets effective under clean-state transplantation can fail under actual recomputation because scattered positions inherit surrounding staleness. The edit-local advantage also depends on adjacency and largely disappears when the answer-bearing text moves downstream. Because answer-relevant edits almost always corrupt model behavior, failure severity is difficult to predict, and repair is 13-21 times faster than full re-prefill, our results support unconditional edit-local repair when the dependent text remains adjacent to the edit.