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

• URL: http://arxiv.org/abs/2509.00388v1
• Date: Sat, 30 Aug 2025 06:56:28 GMT
• Title: GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction
• Abstract summary: GraphKV is a graph-based framework that redefines token selection for KV cache compression.<n>It can be seamlessly utilized in existing KV cache eviction methods such as SnapKV and PyramidKV in a plug-and-play manner.
• Score: 9.309829912599367
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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-and-play manner. Codes will be released on Github.

Related papers

• Self-Pruned Key-Value Attention: Learning When to Write by Predicting Future Utility [31.124813359673073]
  We introduce Self-Pruned Key-Value Attention (SP-KV), a mechanism designed to predict future KV utility.<n>A lightweight utility predictor scores each key-value pair, and while recent KVs are always available via a local window, older pairs are written in the cache.<n>The mechanism adapts to the input and typically reduces the KV cache size by a factor of $3$ to $10times$.
  arXiv  Detail & Related papers  (2026-05-13T18:58:16Z)
• Make Each Token Count: Towards Improving Long-Context Performance with KV Cache Eviction [65.710271475739]
  We introduce a global retention-based KV eviction method that learns each token's future utility under a unified memory budget.<n>We show that our method substantially reduces KV memory while matching or surpassing full-cache inference.<n>These results suggest that learned, globally calibrated KV eviction is not only a compression technique, but also a mechanism for improving long-context reasoning.
  arXiv  Detail & Related papers  (2026-05-10T16:47:50Z)
• DeltaKV: Residual-Based KV Cache Compression via Long-Range Similarity [50.52392445266824]
  We propose a residual-based KV cache compression framework motivated by long-range inter-token similarity and highly shared latent components in KV representations.<n>Instead of discarding tokens, DeltaKV encodes semantic residuals relative to retrieved historical references, preserving fidelity while substantially reducing storage.<n>Experiments show that DeltaKV reduces KV cache memory to 29% of the original while maintaining near-lossless accuracy on LongBench, SCBench, and AIME.
  arXiv  Detail & Related papers  (2026-02-08T15:14:36Z)
• G-KV: Decoding-Time KV Cache Eviction with Global Attention [57.47409249054187]
  Large language models (LLMs) excel in complex tasks but encounter significant computational and memory challenges due to long sequence lengths.<n> KV cache compression has emerged as an effective approach to greatly enhance the efficiency of reasoning.<n>We propose G-KV, a KV cache eviction method that employs a global scoring mechanism, combining local and historical attention scores to more accurately assess token importance.
  arXiv  Detail & Related papers  (2025-11-29T14:21:33Z)
• KVCompose: Efficient Structured KV Cache Compression with Composite Tokens [7.922206020386125]
  Large language models (LLMs) rely on key-value (KV) caches for efficient autoregressive decoding.<n>We propose a simple, yet effective, KV cache compression framework based on attention-guided, layer-adaptive composite tokens.<n>Our method achieves significant memory reduction while preserving accuracy, consistently outperforming prior structured and semi-structured methods.
  arXiv  Detail & Related papers  (2025-09-05T14:58:24Z)
• Graph-KV: Breaking Sequence via Injecting Structural Biases into Large Language Models [63.64507678113921]
  We introduce Graph-KV, which governs interaction through structural inductive biases.<n>In this framework, 'target' segments selectively attend only to the KV-cache of their designated'source' segments.<n>We evaluate Graph-KV across three scenarios: (1) seven RAG benchmarks spanning direct inference, multi-hop reasoning, and long-document understanding; (2) Arxiv-QA, a novel academic paper QA task with full-text scientific papers structured as citation ego-graphs; and (3) paper topic classification within a citation network.
  arXiv  Detail & Related papers  (2025-06-09T00:30:08Z)
• SentenceKV: Efficient LLM Inference via Sentence-Level Semantic KV Caching [5.545249777535219]
  SentenceKV is a novel KV caching approach designed to enhance inference efficiency while preserving semantic coherence.<n>We show that SentenceKV significantly outperforms state-of-the-art methods in both efficiency and memory usage, without compromising model accuracy.
  arXiv  Detail & Related papers  (2025-04-01T17:08:57Z)
• ChunkKV: Semantic-Preserving KV Cache Compression for Efficient Long-Context LLM Inference [61.412894960600205]
  Large Language Models (LLMs) require significant GPU memory when processing long texts.<n>ChunkKV reimagines KV cache compression by treating semantic chunks as basic compression units.<n>Result: ChunkKV outperforms state-of-the-art methods by up to 8.7% in precision.
  arXiv  Detail & Related papers  (2025-02-01T03:49:47Z)
• More Tokens, Lower Precision: Towards the Optimal Token-Precision Trade-off in KV Cache Compression [71.42818367729573]
  In large language models (LLMs), the memory usage of KV cache has become a critical bottleneck during inference.<n>The mainstream KV compression methods, including KV pruning and KV quantization, primarily focus on either token or precision dimension separately.<n>In this paper, we comprehensively investigate the token-precision trade-off in KV cache compression.
  arXiv  Detail & Related papers  (2024-12-17T09:20:31Z)
• Compressing KV Cache for Long-Context LLM Inference with Inter-Layer Attention Similarity [24.118503938098307]
  textscPoD allocates memory according to token importance.<n>textscPoD reduces KV cache memory usage by up to 35% without compromising performance.
  arXiv  Detail & Related papers  (2024-12-03T08:29:27Z)
• Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs [82.08922896531618]
  We introduce adaptive KV cache compression, a plug-and-play method that reduces the memory footprint of generative inference for Large Language Models (LLMs) We conduct targeted profiling to discern the intrinsic structure of attention modules. Based on the recognized structure, we then construct the KV cache in an adaptive manner: evicting long-range contexts on attention heads emphasizing local contexts, discarding non-special tokens on attention heads centered on special tokens, and only employing the standard KV cache for attention heads that broadly attend to all tokens.
  arXiv  Detail & Related papers  (2023-10-03T05:17:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.