REVIEW 4 major objections 5 minor 29 references
GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction
T0 review · 4 major / 5 minor · reviewed 2026-08-05 · deepseek-v4-flash
Pith's one-line read GraphKV claims that a graph-based decay step after any token scoring method removes redundant high-scoring tokens and improves accuracy under the same cache budget.
desk verdict GraphKV is a simple, plausible diversity-promoting plug-in for KV cache eviction, but the core update rule is under-specified and the semantic-redundancy story is thin; still worth refereeing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the sparse token-similarity graph G = (O, E), built by connecting only the top-k source nodes to all other tokens through cosine similarity between their key vectors. The mechanism that carries the argument is decay-signal propagation: for T rounds, each source node sends its neighbors a multiplicative penalty of (1 - e_ij), so a token similar to several high-importance tokens loses score proportional to how redundant it is. This converts a one-shot static ranking into a dynamic, diversity-aware ranking while keeping extra computation linear in the number of tokens.
What would settle it
Give a long-context model a task whose correct answer requires aggregating repeated evidence, such as counting how many times a specific phrase appears. If GraphKV's decay suppresses the repeated, highly similar tokens and the model's count falls below the static top-k baseline, the redundancy assumption is false; if the count holds, the assumption is corroborated.
Extended reading notes
Core claim
The paper claims that static top-k selection in KV cache eviction keeps too many tokens that carry the same semantic content, and that this redundancy can be reduced without retraining by treating the cache as a graph. In GraphKV, each token is a node whose initial importance is whatever score any prior method assigns, and edges are cosine similarities between key vectors. The method selects the top-k scored tokens as source nodes, finds each source's top-m most similar neighbors, and multiplies those neighbors' scores by (1 minus cosine similarity) for several rounds. A token that resembles many strong sources is suppressed the most, so the final retained set is spread across diverse semant
Load-bearing premise
GraphKV assumes that key-vector cosine similarity is a reliable measure of semantic redundancy, so that suppressing tokens similar to high-scoring tokens removes only duplicate information and never information the model still needs.
Editorial extensions
If this is right
- Any existing eviction method can keep its own importance scores and gain from a post-processing diversity step, so GraphKV is a drop-in module rather than a competing selector.
- At a 512-token cache on Llama3-8B, GraphKV raises the LongBench average over Knorm by 45.88% and adds about 3% over SnapKV and PyramidKV.
- At a 128-token cache in the Needle-in-a-Haystack setup, the same integration lifts PyramidKV retrieval from 90.3% to 96.9% and SnapKV from 87.7% to 95.9%.
- Decoding latency does not grow; on QMSum it is roughly unchanged or lower for SnapKV and Knorm.
- The first propagation round supplies most of the gain; additional rounds can fluctuate slightly but stay above the no-propagation baseline.
Reading between the lines
- Because GraphKV is a post-processing layer on any importance score, it could also sit on top of scores from learned eviction policies or attention pooling, not just the hand-designed baselines tested here.
- The same multiplicative-decay update has a graph-diffusion reading: repeated rounds raise the rank of tokens with low similarity to the selected set, which suggests a testable connection to diversity-based sampling and determinantal point processes.
- A stress test on counting or aggregation tasks, where duplicated tokens carry separate evidence rather than redundant semantics, would define the boundary of the redundancy assumption; the paper's experiments do not include such tasks.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. GraphKV proposes a graph-based post-processing framework for KV cache eviction. Given importance scores from any existing eviction method, it treats prompt tokens as nodes, connects a small set of source tokens (top-k by initial score) to all others with edges equal to cosine similarity between key vectors, and over T rounds decays the scores of each source's top-m most similar neighbors using Eq. (5). The updated scores are then used to select the final budget of KV positions. Experiments on LongBench and Needle-in-a-Haystack report consistent but modest gains over SnapKV and PyramidKV at a 512-token cache, larger relative gains over KNorm, and latency reductions in some configurations. The authors present GraphKV not as a new importance score but as a plug-and-play selection layer applicable to prior eviction methods.
Significance. If the reported gains are reproducible, the paper makes a useful practical contribution: a simple, low-overhead selection adjustment with O(N) additional similarity computations, applicable on top of several existing eviction methods. The ablations over propagation rounds and signal types are informative, and the Needle-in-a-Haystack retrieval improvements are concrete. However, the core similarity-redundancy assumption is supported only by a single qualitative example, the algorithm as written omits a stated hyperparameter, and the evaluation lacks error bars and a clear separation between hyperparameter selection and final evaluation. These gaps currently prevent the strong plug-and-play and state-of-the-art claims from being fully supported.
major comments (4)
- [§4.3 (Eq. 4), Algorithm 2, §9] The decay rule is written s'_j = s_j − ·e_{ij}·s_j, and Algorithm 2 line 7 writes s_j^{(t)} ← s_j^{(t−1)}·(1−·e_{ij}). The centered dot before e_{ij} appears to be a missing decay-strength coefficient. Section 9 states that decay strength and propagation rounds are empirically determined, but no value or tuning range for the coefficient is given anywhere. As written, Eq. (5) is only executable under the implicit choice coefficient=1, which may not be the configuration used in Table 1. This is a direct reproducibility gap in the central mechanism.
- [§3, Fig. 2; §7.1, Fig. 8] The motivation for using key-vector cosine similarity as the edge weight is that it tracks semantic redundancy among important tokens. The evidence is visual inspection of one 128-token HotpotQA sample (Fig. 2). Section 7.1 then reports that query-to-key, query-to-query, key-to-value, and value-to-value similarities all improve performance. This is exactly what one would expect from a generic diversity penalty, and it does not discriminate between the proposed semantic-redundancy mechanism and a generic diversity prior. Please provide a quantitative test: for instance, compare key-similarity edges against random or degree-based edges with matched sparsity, or show that the specifically penalized tokens are the ones whose removal least degrades downstream generation.
- [§6, Figs. 5–6; Table 1] The three hyperparameters of GraphKV—source-node fraction k, neighborhood size m, and propagation rounds T—are selected via ablations on LongBench subsets (Figs. 5–6), and the final gains are reported on overlapping LongBench tasks in Table 1. Many of the improvements are below one average point (e.g., Llama2 SnapKV 31.95→32.35; PyramidKV 32.04→32.25). Without a held-out validation split, multiple seeds, or confidence intervals, these gains may reflect selection on the same test tasks. Please report error bars and fix the configuration on a separate validation set before computing the main table.
- [Table 1, KNorm rows] The KNorm baseline is far below the other eviction methods: for Llama2-7B the average is 13.03 versus 31.95 for SnapKV, and for Mistral-7B it is 14.91 versus 40.24 for SnapKV. This makes the abstract's headline claim of a 45.88% improvement over KNorm a comparison against an anomalously weak baseline rather than evidence of state-of-the-art performance. Please verify the KNorm implementation and re-report the relative gain against a correct KNorm score, or remove the headline claim.
minor comments (5)
- [§4.3, Algorithm 2] Typographical issues in the decay equations: 'refinded' should be 'refined', and the centered dot before e_{ij} (also in Algorithm 2 line 7) should be replaced with the explicit decay coefficient or removed.
- [§1, p.2] Typo: 'one all multiple times' should be 'one or multiple times'. Also, the method name KNorm is spelled inconsistently (KNorm vs Knorm).
- [References] The LongBench reference appears twice as Bai et al. 2023a and 2023b with identical content; merge into one entry.
- [Fig. 2 and Fig. 4] Figure 2 caption says Llama3-8B while the text says LLaMA-8B; Figure 4 mixes '8k' and '8,000' for the same context length. Please standardize.
- [§5.1, A.1] The implementation appendix does not report the exact values of k, m, and T used for each model and task in Table 1. Since these are empirically determined, please include the full configuration table.
Circularity Check
No significant circularity; GraphKV's graph-decay mechanism is an empirical heuristic, not a derivation that reduces to its inputs.
full rationale
The paper makes no first-principles claim; GraphKV is an algorithmic post-processing step on externally supplied importance scores. The load-bearing assumption—that key-vector cosine similarity (Eq. 1) indicates semantic redundancy—is justified empirically in Section 3 with a HotpotQA sample and tested in Section 7.1; an empirical motivation is not circular even if the proxy is imperfect. The decay update (Eq. 5) multiplies initial scores by a function of edge weights, so the final ranking is a deterministic transformation of the input scores and similarities, not a quantity that was defined to match the reported outcome. Hyperparameters (source fraction, neighbor count, propagation rounds, decay strength) are selected by ablation on LongBench subsets and later applied on LongBench; Section 9 candidly states they are empirically determined. This is an evaluation-leakage/reproducibility concern, not a circular derivation, because the reported accuracies are not fitted values that are then renamed predictions. No self-citation is load-bearing: references to SnapKV, PyramidKV, KNorm, CAKE, and H2O are external methods used as baselines or score sources. The paper is self-contained against external benchmarks, so the circularity score is 0.
Assumptions & free parameters
free parameters (4)
- k (number of source nodes) =
0.3 x cache budget
- m (number of adjacent neighbors per source) =
adaptive, min(predefined value, query length)
- T (propagation rounds) =
not fixed in text (e.g., T=3); ablation shows T=1 best
- alpha (decay strength) =
not reported
assumptions (4)
- domain assumption Cosine similarity between key vectors is a valid proxy for semantic redundancy among tokens.
- domain assumption High-importance tokens tend to be redundant, and moderate-importance dissimilar tokens carry unique semantic value.
- domain assumption Low-scoring tokens have minimal semantic relevance and can be ignored when building the graph.
- domain assumption The product form (1 - e_ij) in Eq. (5) correctly aggregates decay from multiple source nodes.
Cite this review
Pith. "Pith review of GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction." pith.science (2026). https://pith.science/paper/KUGDU2PM
@misc{pith2026250900388,
author = {Pith},
title = {Pith review of: GraphKV: Breaking the Static Selection Paradigm with Graph-Based KV Cache Eviction},
year = {2026},
howpublished = {\url{https://pith.science/paper/KUGDU2PM}},
note = {Machine review of arXiv:2509.00388}
}
read the original 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.
Figures
Figures from the paper (4 more)
Reference graph
Works this paper leans on
-
[1]
online" 'onlinestring :=
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint eprinttype howpublished institution journal key month note number organization pages publisher school series title type volume year doi pubmed url lastchecked label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block STRING...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023. Gpt-4 technical report. arXiv preprint arXiv:2303.08774
arXiv 2023
-
[4]
AI Anthropic. 2024. The claude 3 model family: Opus, sonnet, haiku. Claude-3 Model Card, 1:1
work page 2024
-
[6]
Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. 2023 b . Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308.14508
arXiv 2023
-
[7]
Zefan Cai, Yichi Zhang, Bofei Gao, Yuliang Liu, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Baobao Chang, Junjie Hu, et al. 2024. Pyramidkv: Dynamic kv cache compression based on pyramidal information funneling. arXiv preprint arXiv:2406.02069
arXiv 2024
-
[8]
Zhuoming Chen, Ranajoy Sadhukhan, Zihao Ye, Yang Zhou, Jianyu Zhang, Niklas Nolte, Yuandong Tian, Matthijs Douze, Leon Bottou, Zhihao Jia, et al. 2024. Magicpig: Lsh sampling for efficient llm generation. arXiv preprint arXiv:2410.16179
arXiv 2024
-
[9]
Wei-Lin Chiang, Zhuohan Li, Ziqing Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E Gonzalez, et al. 2023. Vicuna: An open-source chatbot impressing gpt-4 with 90\ See https://vicuna. lmsys. org (accessed 14 April 2023), 2(3):6
work page 2023
Show all 29 references
-
[10]
Alessio Devoto, Yu Zhao, Simone Scardapane, and Pasquale Minervini. 2024. A simple and effective l\_2 norm-based strategy for kv cache compression. arXiv preprint arXiv:2406.11430
2024 arXiv
-
[11]
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. 2019. Graph neural networks for social recommendation. In The world wide web conference, pages 417--426
2019
-
[12]
Suyu Ge, Yunan Zhang, Liyuan Liu, Minjia Zhang, Jiawei Han, and Jianfeng Gao. 2023. Model tells you what to discard: Adaptive kv cache compression for llms. arXiv preprint arXiv:2310.01801
2023 arXiv
-
[13]
Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. 2024. The llama 3 herd of models. arXiv preprint arXiv:2407.21783
2024 arXiv
-
[14]
Zhiyu Guo, Hidetaka Kamigaito, and Taro Watanabe. 2024. Attention score is not all you need for token importance indicator in kv cache reduction: Value also matters. arXiv preprint arXiv:2406.12335
2024 arXiv
-
[15]
Fengqing Jiang. 2024. Identifying and mitigating vulnerabilities in llm-integrated applications. Master's thesis, University of Washington
2024
-
[16]
Jia Li, Ge Li, Yongmin Li, and Zhi Jin. 2025. Structured chain-of-thought prompting for code generation. ACM Transactions on Software Engineering and Methodology, 34(2):1--23
2025
-
[17]
Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. 2024. Snapkv: Llm knows what you are looking for before generation. Advances in Neural Information Processing Systems, 37:22947--22970
2024
-
[18]
Aixin Liu, Bei Feng, Bin Wang, Bingxuan Wang, Bo Liu, Chenggang Zhao, Chengqi Dengr, Chong Ruan, Damai Dai, Daya Guo, et al. 2024. Deepseek-v2: A strong, economical, and efficient mixture-of-experts language model. arXiv preprint arXiv:2405.04434
2024 arXiv
-
[19]
Ziran Qin, Yuchen Cao, Mingbao Lin, Wen Hu, Shixuan Fan, Ke Cheng, Weiyao Lin, and Jianguo Li. 2025. Cake: Cascading and adaptive kv cache eviction with layer preferences. arXiv preprint arXiv:2503.12491
2025
-
[20]
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. 2008. The graph neural network model. IEEE transactions on neural networks, 20(1):61--80
2008
-
[21]
Prajwal Singhania, Siddharth Singh, Shwai He, Soheil Feizi, and Abhinav Bhatele. 2024. Loki: Low-rank keys for efficient sparse attention. arXiv preprint arXiv:2406.02542
2024 arXiv
-
[22]
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288
2023 arXiv
-
[23]
Zheng Wang, Boxiao Jin, Zhongzhi Yu, and Minjia Zhang. 2024. Model tells you where to merge: Adaptive kv cache merging for llms on long-context tasks. arXiv preprint arXiv:2407.08454
2024 arXiv
-
[24]
Jialong Wu, Zhenglin Wang, Linhai Zhang, Yilong Lai, Yulan He, and Deyu Zhou. 2024. Scope: Optimizing key-value cache compression in long-context generation. arXiv preprint arXiv:2412.13649
2024 arXiv
-
[25]
Lingfei Wu, Yu Chen, Kai Shen, Xiaojie Guo, Hanning Gao, Shucheng Li, Jian Pei, Bo Long, et al. 2023. Graph neural networks for natural language processing: A survey. Foundations and Trends in Machine Learning , 16(2):119--328
2023
-
[26]
Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. 2023. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309.17453
2023 arXiv
-
[27]
Dongjie Yang, XiaoDong Han, Yan Gao, Yao Hu, Shilin Zhang, and Hai Zhao. 2024. Pyramidinfer: Pyramid kv cache compression for high-throughput llm inference. arXiv preprint arXiv:2405.12532
2024 arXiv
-
[28]
Tianyi Zhang, Faisal Ladhak, Esin Durmus, Percy Liang, Kathleen McKeown, and Tatsunori B Hashimoto. 2024. Benchmarking large language models for news summarization. Transactions of the Association for Computational Linguistics, 12:39--57
2024
-
[29]
Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher R \'e , Clark Barrett, et al. 2023. H2o: Heavy-hitter oracle for efficient generative inference of large language models. Advances in Neural Information Proces...
2023
-
[30]
Yutao Zhu, Huaying Yuan, Shuting Wang, Jiongnan Liu, Wenhan Liu, Chenlong Deng, Haonan Chen, Zheng Liu, Zhicheng Dou, and Ji-Rong Wen. 2023. Large language models for information retrieval: A survey. arXiv preprint arXiv:2308.07107
2023
Reviewed August 5, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.