GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction

Xuelin Li, Xiaopeng Jin, Linfeng Zhang2025 · DOI

Abstract

As Large Language Models (LLMs) are increasingly deployed for long-context tasks, the memory overhead of the Key-Value (KV) cache has become a critical bottleneck. Traditional eviction strategies rely on static selection—retaining tokens based on fixed importance scores—which often results in a cache filled with semantically redundant information. We present GraphKV, a "plug-and-play" framework that treats tokens as nodes in a graph. By utilizing a decay signal-propagation mechanism, GraphKV identifies and removes redundant tokens, ensuring a more diverse and representative cache. Our results show that GraphKV enhances the performance of existing eviction methods like SnapKV and PyramidKV by up to 3% on LongBench and significantly improves retrieval accuracy in "Needle In A Haystack" tests, all while operating within a 10% cache budget.

Introduction

The ability of Large Language Models to process long sequences, often exceeding 128K tokens, is hindered by the linear growth of the Key-Value (KV) cache. This cache stores the hidden states of previous tokens to accelerate generation, but its size quickly exhausts hardware memory limits. To mitigate this, researchers have developed "eviction" strategies to prune the cache. However, current state-of-the-art methods, such as SnapKV and H2O, typically rely on static selection paradigms. These methods calculate importance scores—often based on attention weights—and retain the top-$K$ tokens.

The fundamental flaw in this approach is redundancy. High-importance tokens frequently share near-identical semantic meanings. Retaining multiple tokens that convey the same information is an inefficient use of limited cache space. GraphKV addresses this by moving beyond static selection to a dynamic, diversity-aware pruning strategy.

The Redundancy Problem in Static Selection

In standard LLM inference, tokens with the highest attention scores often exhibit extremely high cosine similarity (approaching 1.0). Static selection methods keep all these high-scoring tokens, effectively crowding out "moderate-score" tokens that might provide unique semantic diversity necessary for complex reasoning or retrieval. The authors argue that a slightly less "important" but unique token is often more valuable for model performance than a redundant "high-importance" token.

The GraphKV Framework

GraphKV is designed as a modular framework that can be integrated into existing eviction pipelines without requiring model retraining. The process follows four primary stages:

  1. Initial Importance Scoring: The framework begins with importance scores generated by an underlying eviction method (e.g., SnapKV or PyramidKV).
  2. Sparse Graph Construction: Tokens are modeled as nodes. The algorithm identifies a small set of "source nodes" (the most important tokens) and calculates the cosine similarity between these sources and all other tokens in the sequence. These similarities define the edges of a sparse graph.
  3. Decay Signal Propagation: This core innovation involves rounds of "decay propagation." If a token is found to be highly similar to a previously selected source node, its importance score is "decayed" or reduced. This mechanism penalizes redundancy by lowering the priority of tokens that do not add new information.
  4. Dynamic Selection: The KV cache is pruned based on these updated, diversity-aware scores.

Crucially, because GraphKV only computes similarities for a small subset of tokens ($K \ll N$), the computational overhead remains linear $O(N)$. This ensures that the framework is latency-neutral or even latency-positive by preventing the generation of repetitive, unnecessary output.

Experimental Results

GraphKV was evaluated using LLaMA-3-8B across several rigorous benchmarks, including LongBench (a suite of 16 tasks covering QA, summarization, and code generation) and the "Needle In A Haystack" retrieval test.

Accuracy and Retrieval

On the LongBench QA tasks, GraphKV improved the performance of SnapKV and PyramidKV by approximately 3%. The impact was even more pronounced in retrieval tasks. In the "Needle In A Haystack" test (up to 8K tokens), adding GraphKV to PyramidKV raised retrieval accuracy from 90.3% to 96.9%. For SnapKV, accuracy improved from 87.7% to 95.9%.

Efficiency and Latency

GraphKV allows models to maintain high performance while utilizing only 10% of the full KV cache budget. Furthermore, despite the additional graph-based calculations, the authors observed that GraphKV often reduced total decoding latency. By selecting more diverse and relevant tokens, the model was less likely to fall into repetitive generation loops, leading to more concise and accurate responses.

Limitations and Future Directions

While GraphKV represents a significant step forward, several areas for improvement remain. The effectiveness of the decay mechanism is currently sensitive to hyperparameters, such as decay strength and the number of propagation rounds, which lack a rigorous theoretical selection method. Additionally, the current evaluation focused on 8B parameter models; the behavior of GraphKV on frontier-scale models (e.g., 70B+) is yet to be fully characterized. Finally, future iterations could explore more complex edge definitions beyond cosine similarity to capture non-linear token relationships.

Conclusion

GraphKV breaks the static selection paradigm by introducing a dynamic, graph-based approach to KV cache eviction. By prioritizing semantic diversity over raw importance scores, it enables LLMs to handle long contexts more efficiently and accurately. As a plug-and-play framework, it offers a practical solution for deploying long-context models on memory-constrained hardware.

Summary updated

Abstract

Efficient Key-Value (KV) cache management is essential for processing long text sequences in large language models (LLMs), where memory constraints often limit performance.Conventional KV eviction strategies, such as top-k selection based on attention scores, depend on static heuristics that fail to capture the evolving implicit dependencies among tokens during inference.To overcome this, we propose GraphKV, a graph-based framework that redefines token selection for KV cache compression.In GraphKV, tokens are modeled as nodes with importance scores, and edges represent their similarity relationships.Through a decay-signal-propagation mechanism, token importance is dynamically updated by propagating information across the graph, enabling adaptive retention of the most contextually significant tokens.GraphKV can be seamlessly utilized in existing KV cache eviction methods such as SnapKV and PyramidKV in a plug-andplay manner.Our code is publicly available at GitHub.
BibTeX
@misc{li2025graphkv,
  author = {Xuelin Li and Xiaopeng Jin and Linfeng Zhang},
  title = {{GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction}},
  year = {2025},
  doi = {10.18653/v1/2025.emnlp-main.1112},
}
Figure