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

As large language models (LLMs) scale to longer contexts, the key-value (KV) cache grows linearly, necessitating compression techniques. Existing query-agnostic eviction methods focus on selecting the most important original KV pairs to retain. This paper asks: can we improve performance under aggressive compression by generating a small, learned complement to the retained cache, rather than relying solely on selection?

RestoreKV introduces a two-part strategy for compressed KV caches. First, it retains a subset of original KV pairs using any standard importance-based eviction rule. Second, it uses a small number of learnable 'restore tokens' that attend to the full context during a single, LoRA-adapted prefill pass. These tokens generate a compact, context-conditioned 'restore cache' that occupies the remaining portion of the fixed memory budget. The LoRA adapters are only active during this one-time construction phase, ensuring that subsequent query processing and decoding remain unchanged and computationally efficient.

RestoreKV consistently outperforms standalone eviction methods across four model backbones (Qwen3 and Llama-3.1 families) and four long-context benchmarks. By reserving a small fraction of the budget for generated restore states, the model effectively recovers information that would otherwise be lost to aggressive eviction. For example, on the Qwen3-4B model at a 5% budget, RestoreKV improved the accuracy of the KVzip baseline from 38.2 to 73.2 on the RULER-4K benchmark. The approach is highly compatible, showing consistent gains when applied to five different base eviction methods, and adds less than 0.5% overhead to the total cache construction time.

This work shifts the paradigm of KV cache compression from purely selective retention to a hybrid approach of selection and synthesis. By demonstrating that a shared, lightweight mechanism can learn to reconstruct context-specific information, RestoreKV provides a robust way to maintain high model performance in memory-constrained environments without requiring task-specific tuning or expensive decoding-time overhead.