# RestoreKV: Recovering Full-Cache Behavior Under Aggressive Query-Agnostic KV Cache Eviction > RestoreKV generates a small, context-conditioned restore cache via LoRA-adapted tokens to complement evicted KV pairs, boosting RULER accuracy by up to 35 points at 5% budget with negligible overhead. - **Source:** [arXiv](https://arxiv.org/abs/2608.01247) - **Published:** 2026-08-22 - **Permalink:** https://picx.dev/p/cccHxl - **Whiteboard:** https://picx.dev/p/cccHxl/image ## Summary ## Summary (Overview) - **RestoreKV** introduces a novel complementary restoration perspective to query-agnostic KV cache eviction: instead of only learning *which* original KV pairs to retain, it learns a shared mechanism that generates a compact, context-conditioned **restore cache** to complement the retained context cache under the same total KV budget. - The method uses **8 learnable restore tokens** that attend to the full KV cache in a **single LoRA-adapted pass** after context prefill, generating context-conditioned KV pairs that are combined with the base evictor's retained states. - RestoreKV is trained via **self-distillation from a frozen full-cache teacher**, optimizing only **0.4% of parameters** (restore-token embeddings + LoRA adapters) with no task-specific tuning. - Across **4 backbones, 4 benchmarks, and 5 base eviction methods**, RestoreKV substantially reduces compression-induced degradation. On Qwen3-4B at a 5% budget, it improves KVzip from 38.2 to 73.2 on RULER-4K; applied to KVzip+, it reaches **86.4 RULER accuracy at 16× compression** on the KVPress Benchmark. - The method adds **less than 0.5% one-time cache-construction overhead** (0.03–0.04 s and 84 MB) in a 32K-context evaluation, with **no query-time KV-memory or decoding cost**. --- ## Introduction and Theoretical Foundation ### Background Large language models increasingly rely on long contexts, but their key–value (KV) caches grow linearly with sequence length. KV cache eviction reduces this cost by retaining only a subset of cached KV pairs. **Query-agnostic eviction methods** compress a context once before future queries are known and reuse the resulting cache across arbitrary subsequent requests. ### The Selection-Based Formulation Recent query-agnostic methods (KVzip, KVzip+, ContrastKV) largely follow the same formulation: **select a better subset of the original KV pairs**. The resulting cache remains composed only of retained original states. The central question has been *which KV pairs should survive under a fixed budget*. ### Key Insight > Although the information lost through eviction is context-specific, the mechanism for generating its compact complement can be shared across contexts. This motivates a complementary question: rather than relying only on a better subset, can we generate a small context-conditioned complement *before* eviction to preserve behavior that would otherwise be lost? ### Theoretical Foundation Consider a decoder-only Transformer $f_\theta$ with L layers and H KV heads. Given a context $x_{1:T}$, the prefill stage produces a full KV cache $\mathcal{C}$ containing $TLH$ KV pairs. At KV budget ratio $r$, the total KV budget is: $$ B = \lfloor r T L H \rfloor.\tag{1} $$ The retained context cache is: $$ \mathcal{C}' = \operatorname{Evict}(\mathcal{C}, \mathbf{s}, B),\tag{2} $$ where $|\mathcal{C}'| = B$ and Evict follows the layer- and head-wise allocation rule of the underlying method. --- ## Methodology ### 3.1 Restore-Cache Generation with LoRA RestoreKV introduces $n$ learnable restore-token embeddings: $$ E = [e_1, \ldots, e_n] \in \mathbb{R}^{n \times d},\tag{3} $$ where $d$ is the hidden dimension. After context prefill, the restore tokens are processed at positions $T+1, \ldots, T+n$ with causal access to the full KV cache $\mathcal{C}$. A single LoRA-adapted restore pass generates the context-conditioned restore cache: $$ \mathcal{C}_{\mathrm{res}} = \operatorname{Restore}_{\theta, \phi}(E \mid \mathcal{C}),\tag{4} $$ where $\theta$ denotes the frozen backbone parameters and $\phi$ denotes the LoRA parameters. For each adapted linear projection W, LoRA applies: $$ \Delta W = \frac{\alpha}{r_{\mathrm{LoRA}}} B_\phi A_\phi, \qquad W_{\mathrm{res}} = W + \Delta W,\tag{5} $$ where $r_{\mathrm{LoRA}}$ is the LoRA rank, $\alpha$ is the scaling factor, and $A_\phi$, $B_\phi$ are trainable low-rank matrices. ### 3.2 Budget Matching To preserve the query-time KV budget, RestoreKV reserves $nLH$ of the $B$ cache slots for $\mathcal{C}_{\mathrm{res}}$ and lets the base evictor fill the remaining $B - nLH$ slots: $$ \widetilde{\mathcal{C}} = \operatorname{Concat}\left(\operatorname{Evict}(\mathcal{C}, \mathbf{s}, B - nLH), \mathcal{C}_{\mathrm{res}}\right), $$ $$ |\widetilde{\mathcal{C}}| = (B - nLH) + nLH = B = |\mathcal{C}'|.\tag{6} $$ Retained context KV pairs preserve their original RoPE phases, while restore tokens occupy positions $T+1, \ldots, T+n$ and future queries begin at position $T+n+1$. ### 3.3 Self-Distillation Training Objective Given a training context $x_{1:T}$ and query $q = (q_1, \ldots, q_Q)$, the full-cache teacher first generates an answer $y = (y_1, \ldots, y_M)$. The teacher and student then evaluate the same answer: $$ p_i^{\text{full}}(\cdot) = p_\theta(\cdot \mid q, y_{