Contiguity, Not Importance: Budgeted Repair of Stale KV Caches After Document Edits
Mingyang Mao, Wyatt Mackey and Xiaomin Lin study how to repair a reused KV cache after a document edit with a limited recomputation budget, comparing training-free choices of which positions to recompute.
Ask this paper
Derived edits separate methods: Every policy repairs direct edits, but edits whose consequences appear later in the text distinguish them.
Contiguous window wins: At the main budget, recomputing a contiguous window around the edit recovers at least 0.94 of the post-edit answer margin and beats attention-based, KV-deviation and structural selectors.
Why scattered positions fail: Scattered positions inherit staleness from their neighbors during real recomputation; the advantage disappears when the answer text is far downstream, and repair is 13-21x faster than full re-prefill.
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.