Global Importance Estimation for KV Cache Eviction

Seojin Kim, Noseong ParkarXiv 2026 · arXiv

TL;DR

PRKV is a training-free KV cache eviction method that uses Personalized PageRank (PPR) to identify "globally important" tokens by analyzing multi-hop attention paths. By propagating importance beyond immediate recency or local attention, PRKV enables up to 90% cache compression with minimal performance loss, significantly reducing the memory bottleneck for long-context LLM inference.

What Problem Does This Paper Address?

Large Language Models (LLMs) are increasingly used for long-context tasks, but they face a major hardware hurdle: the Key-Value (KV) cache. During autoregressive decoding, the model stores "keys" and "values" for every token in the sequence to avoid recomputing them. This cache grows linearly with sequence length, quickly exhausting GPU memory.

To manage this, researchers use eviction policies to decide which tokens to keep and which to throw away. Most existing methods rely on "local" signals:

  1. Recency: Keep the most recent tokens.
  2. Instantaneous Attention: Keep tokens that the current query is looking at right now.

The authors argue that these signals are too narrow. An important token might not be the one being looked at right now, but one that influences many other important tokens down the line. They frame KV eviction as a global influence estimation problem, looking for tokens that are central to the overall "flow" of information in the model's attention graph.

Methods

The core idea of PRKV is to treat self-attention as a directed, weighted graph where tokens are nodes and attention weights are edges.

Figure 1: Overview of PRKV. PRKV propagates token influence over an attention-induced transition graph to se- lect globally important KV states.

To find the most influential nodes in this graph, the authors apply Personalized PageRank (PPR). Standard PageRank ranks web pages by how many other pages link to them; PPR does the same for tokens, but "personalizes" the walk to favor recent context.

The paper introduces two scalable variants of this approach:

  • PRKV (Node-based): Uses a small set of "landmark" tokens from the distant past plus a window of recent tokens to build a sparse graph. This creates sharp, localized relevance paths.
  • PRKV-GLB (Global co-attention): Builds a transition operator based on key-key similarity (co-attention). This allows for smoother, more global importance propagation across the entire sequence.

Finally, they use Value-aware importance scaling. They don't just look at the PPR score; they multiply it by the L2 norm of the token's value vector. This ensures that tokens with "high-magnitude" representations—which have a larger impact on the model's hidden state—are prioritized for retention.

Datasets

The authors evaluated PRKV across multiple LLM families (Llama-3.1, Qwen3, Gemma-3, DeepSeek-R1) using a wide array of benchmarks:

  • Long-context Understanding: LongBench (16 tasks) and RULER (13 tasks).
  • Sparse Retrieval: Needle-in-a-Haystack (NIAH).
  • Reasoning: AIME25 and MATH-500 (benchmarking long chain-of-thought decoding).

Key Insights and Ideas

  • Multi-hop is better than one-hop: The "aha moment" is that propagating attention signals through the graph (multi-hop) is a much better predictor of future token usage than just looking at the current attention weights.
  • Rapid Stability: PPR scores don't need hundreds of iterations to be useful. The authors found that the rankings stabilize after just a few propagation steps, making the method computationally efficient.
PPR scores rapidly stabilize within a few propagation steps.
  • Complementary Strengths: The two variants serve different needs. Node-based PRKV is better when relevance paths are "clean" and direct, while the Global (GLB) variant shines in sparse or distributed contexts where it can aggregate weak signals from across the entire cache.
  • Value Norm Matters: Simply knowing a token is "attended to" isn't enough. Scaling by the value norm is crucial because it accounts for the actual numerical impact a token has on the residual stream.

Key Results

PRKV consistently outperforms or matches strong baselines like SnapKV and TOVA, especially at aggressive compression ratios.

  • 90% Compression: On the RULER benchmark, PRKV variants maintained significantly higher accuracy than baselines when only 10% of the KV cache was retained.
  • Superior Retrieval: In Needle-in-a-Haystack tests, PRKV-GLB showed much more stable retrieval across all "needle" positions compared to methods that rely more heavily on local windows.
  • Minimal Overhead: Despite the graph math, PRKV is fast. It adds less than 1% to 3% to the total end-to-end generation time, a small price to pay for massive memory savings.
PPR recovers stable high-importance tokens and shows stronger alignment with downstream attention.

Limitations and Future Work

The authors acknowledge a few key limitations:

  • Initial Signal Dependency: Like all attention-based methods, PRKV's quality depends on the "fidelity" of the initial attention weights it uses to build its graph.
  • Computational Cost: While low, there is still a non-zero cost for the PPR iterations. The authors suggest that future work could involve developing more optimized kernel-level implementations (e.g., in vLLM).
  • Theoretical Gaps: While they provide a perturbation bound for their approximation, tighter theoretical bounds that directly predict downstream task performance remain an open research question.

Summary updated

Abstract

Memory consumption of the key-value (KV) cache remains a central bottleneck for long-context LLM inference. We introduce PRKV, a training-free KV eviction method that estimates multi-hop global token importance by applying Personalized PageRank over attention-induced transition graphs. This enables importance propagation beyond recency or instantaneous attention, without modifying the model. We benchmark PRKV on long-context understanding, sparse retrieval, and chain-of-thought reasoning tasks using multiple LLM families. Under moderate to aggressive compression ratios, including up to 90%, PRKV achieves competitive task performance against established eviction baselines while reducing peak memory usage with low end-to-end overhead. These results demonstrate that multi-hop global influence estimation yields a favorable accuracy--memory trade-off for scalable long-context inference.
BibTeX
@misc{kim2026global,
  author = {Seojin Kim and Noseong Park},
  title = {{Global Importance Estimation for KV Cache Eviction}},
  year = {2026},
  eprint = {2611.24969},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.24969},
}
Figure