Pith. sign in

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 →

arxiv 2509.00388 v1 pith:KUGDU2PM submitted 2025-08-30 cs.CL

classification cs.CL
keywords KVcacheevictiongraph-basedtokenselectiondecaysignalpropagationredundancylong-contextLLMinferenceLongBenchNeedleinaHaystack
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

GraphKV is a plug-in framework for KV cache eviction in long-context LLM inference. It claims that static top-k selection keeps many high-importance tokens that are semantically similar to one another, wasting cache budget on redundancy. To fix this, it models tokens as graph nodes and key-vector cosine similarity as edges, then propagates a decay signal from the top-k source nodes to their most similar neighbors, lowering those neighbors' scores before final selection. This re-ranking preserves both representative and diverse tokens under the same cache budget. The paper reports that the mechanism integrates with existing eviction methods and improves accuracy across LongBench and long-context retrieval tasks.

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.

Watch

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

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 5 minor

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)
  1. [§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.
  2. [§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.
  3. [§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.
  4. [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)
  1. [§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.
  2. [§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).
  3. [References] The LongBench reference appears twice as Bai et al. 2023a and 2023b with identical content; merge into one entry.
  4. [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. [§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

0 steps flagged · score 0.0 of 10

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 4 free parameters · 4 assumptions · 0 invented entities

The central claim rests on a small set of tuned hyperparameters (k, m, T, alpha) and a few domain assumptions about token similarity as a redundancy signal. No new physical or conceptual entities are introduced. The hyperparameters are selected on the evaluation benchmark itself, which raises the bar for reproducibility.

free parameters (4)
  • k (number of source nodes) = 0.3 x cache budget
    Selected via ablation (Fig. 5a, Table 6) as the best proportion of the KV budget; used in Eq. (2) to define source nodes.
  • m (number of adjacent neighbors per source) = adaptive, min(predefined value, query length)
    The predefined value is unspecified; ablation in Fig. 5b shows adaptive is better than fixed, but the actual value used for main results is not reported.
  • T (propagation rounds) = not fixed in text (e.g., T=3); ablation shows T=1 best
    Section 4.3 says 'T rounds (e.g., T=3)', but Fig. 6 shows T=1 gives the largest gain; the main table likely uses one specific but unreported value.
  • alpha (decay strength) = not reported
    Appears as a blank multiplier in Eq. (4) and Algorithm 2; Section 9 explicitly says decay strength is an empirically determined hyperparameter without giving its value.
assumptions (4)
  • domain assumption Cosine similarity between key vectors is a valid proxy for semantic redundancy among tokens.
    Section 3 observes high similarity among important tokens in one HotpotQA sample and uses this as the basis for edges in Eq. (1). No formal or broad empirical justification beyond this single observation supports the general claim.
  • domain assumption High-importance tokens tend to be redundant, and moderate-importance dissimilar tokens carry unique semantic value.
    Section 3 presents this as the key insight, but it is derived from a truncated 128-token visualization on one dataset. The entire decay propagation is built on this premise.
  • domain assumption Low-scoring tokens have minimal semantic relevance and can be ignored when building the graph.
    Section 4.2 states this when isolating low-scoring nodes by removing their edges, but the method actually only restricts edges to source nodes, so this assumption affects which tokens can ever be suppressed.
  • domain assumption The product form (1 - e_ij) in Eq. (5) correctly aggregates decay from multiple source nodes.
    The paper proposes multiplying the decay factors without deriving or testing whether this is a principled update. Table 2 only compares signal types, not aggregation rules.

how reviews work

0 comments
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 reproduced from arXiv: 2509.00388 by the authors.

Figure 1
Figure 1. Overview of GraphKV. Tokens are defined as nodes with their initial importance scores. The co￾sine similarity between tokens is defined as the edges. GraphKV aims to firstly identify K most important nodes (e.g., “love”, K=1), and then propagate decay signal to their most adjacent tokens (e.g., “like” and “great”) to obtain diverse retained KV. This propagation can be performed one or multiple times. computational o… view at source ↗
Figure 2
Figure 2. Cosine similarity of keys and the frequency distribution of cosine similarity, measured using Llama3-8B [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. The pipeline of GraphKV. (I) Initiate Importance Score: We initialize importance scores for each token with any importance scoring function. (II) Build Graph: We select tokens with the highest importance scores as source nodes and compute the key cosine similarity between source nodes and other nodes, retaining the highest similarity values as edges in the graph. (III) Decay Signal Propagation: After constructing th… view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Results of the Fact Retrieval Across Context Lengths (“Needle In A HayStack”) test in LlaMa-3-8B [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]
Figure 5
Figure 5. Figure 5: Impact of the number of adaptive source nodes [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]
Figure 7
Figure 7. Figure 7: PCA visualizations in two dimensions of Keys with normalized importance scores for GraphKV across [PITH_FULL_IMAGE:figures/full_fig_p008_7.png]
Figure 8
Figure 8. Figure 8: Performance comparison of GraphKV across datasets with different similarity graph edges. [PITH_FULL_IMAGE:figures/full_fig_p008_8.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

29 extracted references · 8 canonical work pages

  1. [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. [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. [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

  4. [4]

    AI Anthropic. 2024. The claude 3 model family: Opus, sonnet, haiku. Claude-3 Model Card, 1:1

  5. [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

  6. [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

  7. [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

  8. [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

Show all 29 references
  1. [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

  2. [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

  3. [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

  4. [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

  5. [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

  6. [15]

    Fengqing Jiang. 2024. Identifying and mitigating vulnerabilities in llm-integrated applications. Master's thesis, University of Washington

  7. [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

  8. [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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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

  15. [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

  16. [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

  17. [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

  18. [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

  19. [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

  20. [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...

  21. [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

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.