Reformulating KV Cache Eviction Problem for Long-Context LLM Inference (LaProx)

Abstract

"Large language models (LLMs) support long-context inference but suffer from substantial memory and runtime overhead due to Key-Value (KV) Cache growth. Existing KV Cache eviction methods primarily rely on local attention weights, neglecting the influence of value representations, output projection, and inter-head interactions. In this work, we reformulate KV Cache eviction from a conventional head-wise, weight-averaging approach into an output-aware, layer-wise matrix multiplication approximation problem. We introduce LaProx, a novel eviction strategy that explicitly models the multiplicative interaction between attention maps and projected value states to accurately quantify token contributions while accounting for inter-head dependencies. Building on this metric, we propose the first unified eviction strategy that assigns globally comparable importance scores to tokens, enabling model-wide selection instead of local, head-wise decisions. Experimental results across 19 datasets on long-context benchmarks LongBench and Needle-In-A-Haystack demonstrate that our approach maintains model performance with only 5% of the KV cache and consistently outperforms prior works across all configurations. Notably, our method achieves up to 2× accuracy loss reduction under extreme compression scenarios compared to existing state-of-the-art baselines with minimal overhead."

Key Contributions

• Reformulation: KV eviction as an output-aware, layer-wise matrix-multiplication approximation — accounting for value representations, output projection, and inter-head interactions that head-wise attention-weight methods ignore.
• LaProx metric: models the multiplicative interaction between attention maps and projected value states to quantify each token's true contribution.
• First unified, globally-comparable importance score → model-wide token selection instead of local per-head decisions.

Results

• Maintains model performance at only 5% KV-cache retention across 19 datasets (LongBench + Needle-In-A-Haystack).
• Up to 2× accuracy-loss reduction vs prior SOTA under extreme compression, with minimal overhead.
• Outperforms prior eviction methods across all tested configurations.

Methodology

Replaces the standard head-wise, attention-weight-averaging eviction score with a layer-wise approximation of the actual attention-output matrix product, capturing value-state and cross-head effects; ranks tokens on a single global scale so eviction is decided model-wide rather than per head.

Limitations

• Eviction (dropping tokens) is lossy by construction; 5% retention is aggressive and task-dependent.
• Reported on LongBench / NIAH families; reasoning-heavy or agentic long-context workloads not separately characterized.
• Overhead is "minimal" but the exact score-computation cost vs simpler heuristics needs the full text.

Why it matters (ai lens)

Broadens the KB's KV-cache lane beyond compression (VeriCache) into eviction with a fundamentally different framing — global, output-aware scoring rather than local attention weights. The 5%-retention result is a concrete magnitude for the memory-bound-inference thesis: long-context KV can be cut ~20× with bounded accuracy loss, easing the exact HBM-capacity pressure the hardware topic tracks. Files into [kv-cache].

Source: Reformulating KV Cache Eviction / LaProx (arXiv:2605.07234), submitted 2026-05-08, Tho Mai & Joo-Young Kim. Ingested 2026-07-24 at abstract + reported-metrics grade. Provenance [preprint].