🤖 machine learning

A Simple Plug-in for Improving Eviction-Based KV Cache Compression

The paper introduces VECTOR, a plug-in for eviction-based KV cache compression that enhances long-context LLM inference by implementing a three-way token routing strategy (retention, approximation, and eviction) to recover reconstructable value information and improve quality-memory trade-offs.

Original authors: Yuping Lin, Jiayuan Ding, Yue Xing, Pengfei He, Jiliang Tang, Subhabrata Mukherjee

Published 2026-05-25

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yuping Lin, Jiayuan Ding, Yue Xing, Pengfei He, Jiliang Tang, Subhabrata Mukherjee

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a Large Language Model (LLM) as a brilliant but forgetful librarian trying to answer a question based on a massive, endless book. To do its job, the librarian keeps a "scratchpad" (called the KV Cache) of the most important parts of the book it has read so far.

The problem? As the book gets longer, this scratchpad gets huge. Eventually, the librarian runs out of desk space (memory), and they have to throw pages away to make room for new ones.

The Old Way: The "All-or-Nothing" Trash Can

Previously, librarians used a simple rule: "If a page isn't super important right now, throw it in the trash forever."

The Problem: This is like throwing away a page just because you aren't looking at it this second. Even if you don't need it immediately, that page might contain a fact you can easily guess or reconstruct later. By throwing it away completely, you lose that information forever.

The New Way: VECTOR (The "Three-Drawer" System)

The paper introduces VECTOR, a new system that gives the librarian three different drawers instead of just "Keep" or "Trash."

The "Keep" Drawer (Retention): For the most critical pages (like the main character's name or the plot twist), the librarian keeps the original, perfect copy.
The "Trash" Drawer (Eviction): For pages that are truly irrelevant (like a random ad in the middle of a chapter), they get thrown away completely.
The "Sketch" Drawer (Approximation): This is the magic new step. For pages that are somewhat important but not critical, the librarian doesn't throw them away. Instead, they throw away the full text but keep a simple sketch or a mathematical hint that allows them to redraw the page later if needed.

How Does the "Sketch" Work?

The paper explains that in these AI models, the "Key" (the label on the page) and the "Value" (the actual content) are mathematically linked, like a lock and its key.

The Insight: The "Key" is very sensitive; if you mess it up, the librarian gets confused about where to look. But the "Value" (the content) is more forgiving.
The Trick: VECTOR keeps the "Key" safe. Then, it uses a pre-calculated math formula (called OLS) to guess what the "Value" should look like based on that Key.
The Result: If the guess is good (which the paper proves it usually is), the librarian saves massive amounts of space by storing just the Key and the formula, rather than the full heavy text. If the guess is bad, they keep the full text.

The "Three-Way" Decision Process

When the librarian needs to make space, VECTOR asks two questions for every page:

Is this page important? (If No $\rightarrow$ Trash it).
If it is important, can we easily redraw it from its label?
- If Yes (Easy to redraw) $\rightarrow$ Put it in the Sketch Drawer (Save space).
- If No (Hard to redraw) $\rightarrow$ Keep the Full Copy (Save accuracy).

What Did They Find?

The authors tested this on several AI models with very strict memory limits (like trying to fit a whole encyclopedia into a shoebox).

The Result: By using this "Sketch Drawer," the models performed much better than before, especially when memory was extremely tight. They could remember more details and answer questions more accurately without needing more computer memory.
The Catch: It works best when the librarian isn't already being super picky about what to keep. If the librarian is already keeping only the most perfect pages, there isn't much room to use the "Sketch" trick.

In a Nutshell

VECTOR is a smart upgrade for AI memory management. Instead of just deciding "Keep" or "Toss," it adds a middle option: "Keep a hint so we can rebuild it later." This lets AI models handle longer stories and complex tasks without running out of memory, simply by being smarter about what they throw away.

Technical Summary: VECTOR

Problem Statement

Large Language Models (LLMs) face a critical bottleneck in long-context inference due to the linear growth of Key-Value (KV) cache memory with sequence length. This memory cost restricts practical deployment in applications requiring long context windows, such as retrieval-heavy QA, agent workflows, and multi-turn reasoning.

Existing KV cache compression methods generally fall into two categories, both of which have limitations:

Importance-based Eviction: Methods like SnapKV and KeyDiff score tokens and permanently discard low-scoring entries. While efficient, this binary decision (retain or evict) is irreversible. Under tight memory budgets, this can lead to substantial performance degradation by discarding tokens that are not critical for exact retention but are still reconstructable.
Representation Approximation: Methods like AQUA-KV and EliteKV compress KV representations via quantization or projection. However, many require architectural modifications, retraining, or expensive online computation (e.g., retrieval-based reconstruction).

Furthermore, existing multi-state allocation methods (e.g., ARKV, D2O) improve upon binary eviction but rely solely on token importance signals. They fail to explicitly model reconstructability—whether a token's KV representation can be accurately recovered from other available information with limited error. Additionally, while prior work notes that values (V) are generally more tolerant to approximation than keys (K) due to the non-linear amplification of errors in the softmax attention mechanism, most token-level compression methods do not explicitly exploit this asymmetry in memory allocation.

Methodology: VECTOR

The authors propose VECTOR (Value Estimation via Collinearity and Three-way Orthogonal Routing), a plug-and-play augmentation for eviction-based pipelines. VECTOR introduces a three-way token routing mechanism: Retention, Approximation, and Eviction.

Core Mechanisms

Asymmetric Treatment (K vs. V):
- Keys (K): Retained exactly for all tokens in the candidate pool. This preserves the integrity of the attention routing mechanism, as perturbations in keys are exponentially amplified by the softmax function.
- Values (V): Subject to a three-way decision.
  - Retain: Exact storage for high-importance or hard-to-reconstruct tokens.
  - Approximate: Discarded and reconstructed on-the-fly for tokens with high reconstructability.
  - Evict: Permanently removed for low-importance tokens.
Reconstructability via OLS:
- The method leverages the intrinsic low-rank structure shared by K and V (both linear projections of the same hidden state).
- It employs an Ordinary Least Squares (OLS) regression model, calibrated offline, to predict V from K ( $V \approx W_{OLS}K$ ).
- To handle Rotary Position Embedding (RoPE), the method applies an inverse rotation to keys before reconstruction, decoupling positional information to allow a static $W_{OLS}$ matrix to work across all positions.
Three-Way Allocation Pipeline:
Given a target compression ratio $p_c$ and an approximation ratio $p_a$ :
- Step 1 (Budget Relaxation): The base eviction algorithm identifies an expanded candidate pool of size $1 - p_c + p_a$ .
- Step 2 (Residual Evaluation): For each token in this pool, the reconstruction error $\epsilon_i = \|V_i - W_{OLS}K_i\|^2$ is computed.
- Step 3 (Asymmetric Truncation):
  - Keys for all $1 - p_c + p_a$ tokens are retained.
  - The $2p_a$ tokens with the lowest reconstruction errors have their values discarded and reconstructed via $W_{OLS}K$ .
  - The remaining $1 - p_c - p_a$ tokens retain both exact K and V.
- This ensures the total memory footprint matches the target budget of $1 - p_c$ full KV pairs.

Key Contributions

Reconstructability-Aware Allocation: The paper reframes KV compression as a unified retain-approximate-evict problem, jointly considering token importance and reconstructability, rather than a binary decision.
Lightweight K→V Reconstruction: A one-time offline OLS calibration enables online value reconstruction from stored keys with negligible inference-time overhead and no model retraining.
Plug-and-Play Integration: VECTOR can be attached to existing token-importance eviction methods (both query-aware and query-agnostic) with minimal adaptation.
Theoretical Analysis: The authors derive conditions under which expanding the approximation tier reduces information loss, linking the required OLS prediction quality ( $R^2_{approx}$ ) to the skewness of the importance score distribution.

Experimental Results

Experiments were conducted on LongBench (16 tasks) and Needle-in-a-Haystack (NIAH) using Llama-3.1-8B, Qwen3-14B, and Qwen3-0.6B.

High-Compression Gains: VECTOR consistently improves downstream performance in high-compression regimes ( $p_c \in \{0.75, 0.90\}$ $p_{c} \in {0.75, 0.90}$ ).
- Query-Agnostic Baselines: The most significant gains were observed with KeyDiff and KVzip. For example, on Qwen3-14B with KeyDiff, VECTOR improved average scores by +7.03 at $p_c=0.50$ , +9.15 at $p_c=0.75$ , and +9.73 at $p_c=0.90$ .
- Query-Aware Baselines: Improvements with SnapKV and PyramidKV were more modest, particularly at moderate compression, as these methods already retain the most pertinent tokens, leaving less "headroom" for approximation. However, consistent gains were observed at $p_c=0.90$ .
Robustness (NIAH): In NIAH stress tests at $p_c=0.90$ , VECTOR consistently improved retrieval quality. It transformed failure patterns from large contiguous low-score regions to more localized difficult cells, indicating improved robustness.
Sensitivity: Performance peaks at a moderate approximation ratio ( $p_a$ ). If $p_a$ is too low, recoverable information is lost; if too high, the retention tier shrinks, forcing hard-to-reconstruct tokens into approximation.

Significance and Claims

The paper claims that VECTOR demonstrates a promising direction for long-context inference systems by combining importance-aware eviction with reconstructability-aware approximation.

Efficiency: It recovers useful value information that would otherwise be irreversibly lost under binary eviction, while preserving key vectors for attention stability.
Practicality: The method requires no architectural changes or retraining, making it a practical augmentation for existing systems.
Trade-off Optimization: Under strict memory budgets, VECTOR achieves better quality-memory trade-offs, particularly for methods that rely solely on context-intrinsic scoring (query-agnostic) where importance and reconstructability capture orthogonal dimensions of utility.

The authors acknowledge limitations, noting that the approximation ratio $p_a$ is currently set via an empirical formula rather than dynamic optimization, and gains over query-aware baselines are limited by the high baseline performance of those methods. Future work could explore adaptive allocation strategies.