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:
- Initial Importance Scoring: The framework begins with importance scores generated by an underlying eviction method (e.g., SnapKV or PyramidKV).
- 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.
- 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.
- 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