Contiguity, Not Importance: Budgeted Repair of Stale KV Caches After Document Edits
Mingyang Mao, Wyatt Mackey, Xiaomin Lin
cs.AI
Quick verdict
Contiguous edit-local recomputation repairs stale KV caches 13-21x faster than re-prefill; solid controlled evidence, but the win reflects benchmark adjacency design.
Summary
The paper formulates stale KV-cache repair after a document edit as budgeted recomputation: the known edit span is always refreshed, and a policy selects K additional downstream positions to recompute under a matched budget. On a synthetic benchmark of ~5,000-token HotpotQA background contexts with length-preserving factual edits, each item pairs a direct condition (answer inside the edited span) with a derived condition (answer in unchanged downstream text reachable through the edited fact). Across Llama-3.1-8B, Qwen3-8B, and Mistral-7B, all policies saturate on direct items, while a contiguous edit-local window dominates at K=32 on derived items, recovering 0.94-1.01 of the post-edit margin versus at most 0.53 for attention-based, KV-deviation, and structural selectors. Mechanistic experiments show transplant-ranked 'important' positions repair well when clean states are copied but fail when actually recomputed from stale neighbors (0.92-0.97 vs 0.01-0.21 at K=8). The advantage is adjacency-dependent: moving the answer text 250 tokens downstream collapses edit-local recovery to 0.01-0.09. Because answer-relevant edits break the cache in at least 98.8% of cases, severity is hard to predict (best rho=0.17), and repair runs 13-21x faster than re-prefill, the authors recommend unconditional edit-local repair. Limitations include the fully synthetic edit design, three ~8B dense models, batch-1 single-GPU timing, Llama sample attrition, and a post-hoc structural stopping rule.
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
5 strengths · 4 weaknesses · 5 author questions
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- At matched budget K=32, a contiguous edit-local window recovers 0.94-1.01 of the post-edit answer margin on derived questions across three model families, beating attention-based, KV-deviation, and structural selectors by 0.46-1.00 (Holm-corrected p <= 3e-9).
- Position sets that repair well under clean-state transplantation fail under actual recomputation (0.918-0.969 vs 0.008-0.209 at K=8) because scattered recomputed positions read stale surrounding states.
- The edit-local advantage depends on adjacency: moving the answer-carrying text 250 tokens downstream drops recovery to 0.01-0.09, leaving stale-query attention useful only on Llama.
- Answer-relevant edits break the stale cache in >=98.8% of items, severity is poorly predictable (best out-of-fold Spearman rho=0.17), and repair is 13-21x faster than full re-prefill, so unconditional edit-local repair is the practical policy when dependencies stay adjacent.
Strengths
Rigorous paired experimental design
Direct and derived conditions share documents, insertion point, subject, value pair, and query, differing only in where the answer sits relative to the edit; build-time filters enforce matched relative edit position within 3%, and all policies get the identical repair operator and matched K budget, isolating the selection rule as the only variable.
Novel operator distinction with quantitative support
Separating transplant from recomputation is the paper's most interesting result: identical position sets recover 0.918-0.969 margin under transplant but only 0.209/0.011/0.008 under recomputation at K=8, worse on every held-out item, with the gap specific to scattered sets (EditLocal/Random differ <0.02 between operators). This is a reusable methodological warning for the KV-editing literature.
Pre-specified, well-controlled statistics
Transparent boundary and sanity reporting
Honest cost accounting
Weaknesses
Headline conclusion is partly baked into benchmark geometry
Fully synthetic edits limit external validity
Narrow model and serving scope
Sample attrition and post-hoc analysis choices
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
- All 5 strengths & 4 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is stale KV cache repair after a document edit?
When an LLM reuses a cached key-value (KV) context for a retrieved document and the source document is later edited, the cached tensors encode the old text while downstream states depend on it. Repair means selectively recomputing some cached entries from the edited text instead of re-prefilling the whole context. This paper shows the most effective training-free strategy is to recompute a contiguous window starting at the edit span, which is 13-21x faster than full re-prefill.
How much faster is edit-local KV repair than re-prefilling?
In this paper's measurements on one RTX 5090 at batch 1 with ~8B models, repairing the edit span plus 32 downstream positions takes about 28-45 ms versus 374-884 ms for a full re-prefill at 4K-8K context, a 13-21x speedup. The advantage grows with context length because repair cost is independent of total context size.
Does edit-local KV cache repair always work?
No. It works almost perfectly (0.94-1.01 margin recovery) when the text that depends on the edit sits immediately downstream of the edit, e.g., a lookup table right after an edited alias. When the answer-carrying text moves 250 or more tokens downstream, edit-local repair collapses to near-random performance, and even a perfectly placed contiguous window recovers only part of the margin on some models. The paper recommends unconditional edit-local repair only within the block adjacent to the edit.
Why is a contiguous window better than recomputing the 'most important' KV positions?
Because of how recomputation differs from transplanting clean states. A recomputed position must read its still-stale neighbors as input, so scattered high-importance positions inherit surrounding staleness and fail; the same positions work well if you copy clean states from a fully correct cache. A contiguous window rebuilds the causal dependency chain in order, so each recomputed position reads already-repaired predecessors.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1-3 are available only as captions plus in-text numbers; visual patterns (e.g., selection maps in Fig. 2a, curve shapes in Fig. 3) could not be independently inspected.
- The supplementary appendix (full construction rules, cost decomposition, edge-case scoring, cohort details) is not included in the extracted text, so several reproducibility-critical details could only be judged from main-text summaries.
- Some cross-references are garbled in extraction (e.g., 'Section reports both', 'variant in Section is exploratory'), suggesting minor content loss around section numbers.
- All quantitative judgments rely on author-reported numbers; no code or data release is stated in the provided text, so independent verification was not possible.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.