RestoreKV: Recovering Full-Cache Behavior Under Aggressive Query-Agnostic KV Cache Eviction

The Problem: KV Cache Compression Breaks Under Tight Budgets

Large language models store key-value pairs from every token in the context during inference. This "KV cache" is memory-intensive, so researchers use query-agnostic eviction—compressing the cache once and reusing it for all future queries. The catch: when memory budgets are severe (5% of original), performance collapses. Existing methods try to pick which KV pairs to keep. This paper shows that's not enough.

RestoreKV: Filling Gaps Instead of Just Selecting

Rather than only improving which pairs to retain, the authors introduce learned restoration—generating synthetic KV pairs to fill in what was evicted, within the same total budget. The insight is clever: while the information lost depends on the specific context, the process of creating a compact replacement can be learned once and reused everywhere.

Here's how it works in practice. After the model finishes loading and encoding the full context (the "prefill" phase), RestoreKV runs a single forward pass with a small set of "restore tokens." These tokens attend to the entire original KV cache using LoRA adapters (a parameter-efficient tuning method). They generate a compact, context-conditioned "restore cache"—effectively learning what information matters most to synthesize for later queries. Once this restore cache is built, the adapters are switched off and never used again during decoding.

The training is efficient: it fine-tunes only 0.4% of model parameters via self-distillation from a frozen full-cache model, with no task-specific tuning needed.

Why It Matters: Substantial Gains Across Settings

The results are striking. On Qwen3-4B, RestoreKV improves 59 out of 60 paired comparisons across five different base eviction methods—showing it works as a universal complement. Most concretely, when using the KVzip eviction method at just 5% budget (95% compression), RestoreKV boosts accuracy from 38.2 to 73.2 on the RULER-4K benchmark. At 16× compression on the KVPress benchmark, RestoreKV+KVzip+ achieves 86.4% RULER accuracy.

The overhead is minimal: less than 0.5% added latency per context (measured on 32K sequences), making it practical. The method generalizes across four model backbones and four long-context benchmarks, suggesting the learned restoration mechanism truly captures a general principle rather than fitting one dataset.

The key contribution is conceptual: query-agnostic KV eviction has been framed purely as a selection problem—pick the right pairs to keep—but RestoreKV shows that generation of missing information is equally valuable and can be done efficiently. This shifts the optimization space and recovers performance that selection-only methods cannot reach, even under 16× compression.