REVIEW 4 major objections 4 minor 19 references
TreeKV: Smooth Key-Value Cache Compression with Tree Structures
T0 review · 4 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash
Pith's one-line read A tree-shaped KV cache beats attention baselines at 16x compression.
desk verdict Solid training-free KV cache compression with a genuinely ablated tree structure, but the long-context gains may hinge on an undocumented position-encoding asymmetry. 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 mechanical heart is the cyclically advancing eviction scope $\{idx, idx+1\}$ over cached positions, paired with an importance score $S$ formed by averaged attention weights. When the cache reaches capacity $c$, the algorithm evicts the lower-scored token inside the current two-slot scope and advances $idx$ modulo $c$; this repeated pair-wise merging produces the tree hierarchy and enforces the sparse-left and dense-right distribution. After eviction, positional encodings are re-assigned to the surviving tokens following StreamingLLM. In the prefilling stage the same machinery is applied to blocks of size $b$, with the final block acting as the observation window that supplies attention weights. Wavelet decomposition of attention-weighted values provides the motivating evidence: higher-frequency components grow as positions approach the sequence end.
What would settle it
Run TreeKV on 16k PG19 sequences with a 1024-token cache but keep the original absolute positions of retained tokens instead of re-assigning them; if perplexity rises substantially relative to the re-assigned version, the position-encoding assumption is carrying the result.
Extended reading notes
Core claim
The paper's central claim is that smooth, hierarchical eviction beats both position-only retention and global importance scoring. Instead of keeping fixed initial and recent regions or greedily selecting globally high-attention tokens, TreeKV walks an eviction scope of two adjacent cache slots from left to right, evicting the lower-scored member at each step while assigning scores as averaged attention weights. The pointer cycles across the cache, so evictions repeatedly merge pairs into a tree that is sparse on the left and dense on the right. The authors argue this structure preserves a global view of the context while prioritizing recent information, and their ablation, in which the left token is always evicted, shows the tree structure rather than score-based selection accounts for most of the gain. Both decoding and prefilling use the same policy, with prefilling operating on blocks.
Load-bearing premise
The load-bearing premise is that re-assigning positional encodings after each eviction does not distort the model's use of retained tokens, even when a 4k-trained model is pushed to 16k context; if the renumbered positions break the model's attention patterns, the reported long-context perplexity would not transfer to real use.
Editorial extensions
If this is right
- A 4k-context Llama-2-7B can serve 8k and 16k sequences with a 1024-token cache, with perplexity below StreamingLLM, H2O, and TOVA at the longer lengths.
- TreeKV compresses prompts during prefilling and generated context during decoding with one policy, so long-form generation and long-context understanding can share a single cache budget.
- On Longbench, TreeKV improves over H2O and SnapKV at cache sizes 2048 and 8192, and the gap to full attention narrows as the budget grows.
- The ablation indicates that the tree-shaped eviction order, not attention-score selection, is the main source of the gains, so simpler importance criteria may retain most of the benefit.
Reading between the lines
- A natural extension is to make the tree depth or block size adaptive: the wavelet observation predicts steeper frequency growth near the sequence end, so inputs with flatter attention profiles might do better with a taller tree or larger blocks.
- If position re-assignment is truly benign, TreeKV should also work with relative-position or RoPE models at longer contexts without additional tuning; testing that would separate the tree mechanism from the positional fix inherited from StreamingLLM.
- The prefilling block size $b$ and the tree height (cache size) are not independently tuned in the paper; per-dataset tuning could close the remaining gap to full attention on summarization tasks.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes TreeKV, a training-free fixed-size KV cache compression method. TreeKV organizes eviction as a tree-like scheme: after the cache is full, an eviction scope consisting of two adjacent cache positions cycles from distant to recent contexts, and the token with the lower average attention weight in that scope is evicted. Positional encodings are re-assigned after eviction following StreamingLLM. The method is applied both during decoding (token-level eviction) and during prefilling (block-level eviction). The authors report perplexity results on PG19 and OpenWebText2 for 4k/8k/16k input lengths with a 1k cache, a 10M-token stress test, and LongBench results at cache sizes 2048 and 8192, together with an ablation intended to isolate the role of the tree structure.
Significance. If the reported comparisons are reproduced under matched conditions, TreeKV would be a practically useful contribution: it is training-free, handles both prefilling and decoding, maintains a fixed cache size, and the authors release code. The 10M-token stress test and the ablation showing that the tree structure matters more than the attention-based selection rule are useful additions. The wavelet analysis is motivational rather than used to fit results, so I do not see a circularity problem. However, the headline empirical claim is currently not fully established because the position-encoding protocol for the baselines in the main language-modeling tables is not specified, and the stated claim of consistent superiority is contradicted by one reported result. The effective attention span in the long-context comparisons is also smaller than the 'longer window' wording implies.
major comments (4)
- [Section 4.1; Tables 1 and 2] The paper states in Section 4.1 that TreeKV re-assigns positional encodings after every eviction, following StreamingLLM, but it does not state whether H2O and TOVA in Tables 1 and 2 use the same protocol. If those baselines keep absolute positions, their 8k/16k results are penalized by untrained RoPE extrapolation independent of which tokens are retained, so the lower perplexity of TreeKV would reflect the positional encoding scheme rather than the eviction policy. Please specify the position protocol for every method in these tables and, if the protocols differ, rerun the baselines with the same re-assignment procedure.
- [Abstract and Section 5.2; Table 1] The abstract and the contributions state that TreeKV 'consistently surpasses all baseline models,' but Table 1 reports TOVA at 7.00 and TreeKV at 7.02 for PG19 with 4k context. The text in Section 5.2 acknowledges this result, but the abstract and contribution bullet do not qualify the claim. The claim should be revised to match the reported data.
- [Section 5.2; Tables 1 and 2] The phrase 'generalize to longer window' overstates what is actually measured. With a cache size of 1024, every method attends over at most 1024 effective positions, and the '16k' label denotes the input length processed, not the context attended. This distinction should be stated explicitly in the text and abstract, and the effective attention span should be reported.
- [Section 5.2; Table 2] The OpenWebText2 evaluation uses 100 randomly selected samples, but no variance, standard errors, or multiple subsets are reported. Several differences in Table 2 are small (for example, 5.45 vs. 5.50 at 8k), so it is important to establish that the reported ordering is not due to sampling noise. Please provide confidence intervals or results over multiple random subsets.
minor comments (4)
- [Algorithm 1, line 16] The update 'idx = (idx + 1) mod c + 1' does not produce the cycle described in the text and in Figure 3: for c=4, it advances from 1 to 3, then to 4, then to 2, rather than 1,2,3,4. The likely intended formula is 'idx = idx mod c + 1'.
- [Section 5.3; Table 3 caption] The caption states that H2O was implemented by the authors rather than run with its official release. Please use the official implementation if available, or justify the reimplementation and describe any changes.
- [Throughout] There are several typographical issues: 'TOVA' is inconsistently typeset as 'TOV A', 'langauge' appears in the contributions, 'orthognal' appears in Section 2, and 'scaler' should be 'scalar' in Section 4.1.
- [Section 5.4; Figure 5] The ablation in Figure 5 does not report the cache size or other hyperparameters used; please state them so the ablation can be related to the settings in Tables 1 and 2.
Circularity Check
No significant circularity: TreeKV's tree design is motivated by a wavelet observation but its reported gains come from held-out benchmark comparisons against standard baselines; the few self-citations are contextual, not load-bearing.
full rationale
TreeKV's central claims are empirical: it reports perplexity/NLL on PG19 and OpenWebText2 and Longbench scores against standard baselines with fixed cache sizes. The wavelet analysis in Sec. 3.3 is a motivating observation, not a fitted input that determines the reported numbers; the method is then evaluated on held-out benchmarks, and no parameter is fitted to make a benchmark result true by construction. The position-encoding re-assignment in Sec. 4.1 is a potential protocol confound for the 8k/16k comparisons, but it is not a case where an output is equivalent to an input by definition, and the paper's stated method is what is being evaluated. The few self-citations (He et al. 2023; 2024) are contextual and not load-bearing: they are cited for prior spectral analysis and for a multi-scale tree for encoder models, and the paper does not rely on a self-cited uniqueness or impossibility theorem. The ablation comparing TreeKV with a left-token variant is an internal causal test, not a circular derivation. Accordingly, no step in the claimed derivation chain reduces to its own inputs, and the circularity burden is low.
Assumptions & free parameters
free parameters (5)
- cache size c =
1024 (language modeling), 2048/8192 (LongBench)
- cache composition: 4 sinks + 508 recent + 512 method-selected =
4+508+512 for c=1024
- block size b for prefilling =
not reported
- importance criterion: averaged attention weight =
S/C (average), chosen over accumulated and normalized variants
- observation window (last block of prompt) =
not reported
assumptions (5)
- standard math Standard transformer attention computation and KV cache growth equations (Section 3.1).
- standard math Multi-level Haar wavelet decomposition and reconstruction preserve the signal exactly (Section 3.2).
- domain assumption Attention scores computed with the already-compressed cache are reliable enough to guide token eviction (Algorithm 1, lines 6-8).
- domain assumption Re-assigning positional encodings after eviction does not degrade attention (Section 4.1, Position Encoding).
- domain assumption Sliding-window perplexity with stride 2048/1024 is a valid measure of long-context ability (Section 5.1).
Cite this review
Pith. "Pith review of TreeKV: Smooth Key-Value Cache Compression with Tree Structures." pith.science (2026). https://pith.science/paper/FODICPAH
@misc{pith2026250104987,
author = {Pith},
title = {Pith review of: TreeKV: Smooth Key-Value Cache Compression with Tree Structures},
year = {2026},
howpublished = {\url{https://pith.science/paper/FODICPAH}},
note = {Machine review of arXiv:2501.04987}
}
read the original abstract
Efficient key-value (KV) cache compression is critical for scaling transformer-based Large Language Models (LLMs) in long sequences and resource-limited settings. Existing methods evict tokens based on their positions or importance scores, but position-based strategies can miss crucial information outside predefined regions, while those relying on global importance scores resulting in strong regional biases, limiting the KV cache's overall context retention and potentially impairing the performance of LLMs on complex tasks. Our wavelet analysis reveals that as tokens approach the end of sequence, their contributions to generation gradually increase and tends to diverge more from neighboring tokens, indicating a smooth transition with increasing complexity and variability from distant to nearby context. Motivated by this observation, we propose TreeKV, an intuitive, training-free method that employs a tree structure for smooth cache compression. TreeKV maintains a fixed cache size, allowing LLMs to deliver high-quality output even in long text scenarios. Unlike most compression methods, TreeKV is applicable to both the generation and prefilling stages. TreeKV consistently surpasses all baseline models in language modeling tasks on PG19 and OpenWebText2, allowing LLMs trained with short context window to generalize to longer window with a 16x cache reduction. On the Longbench benchmark, TreeKV achieves the best performance with only 6\% of the budget at optimal efficiency.
Figures
Figures from the paper (2 more)
Reference graph
Works this paper leans on
-
[1]
Longbench: A bilingual, multitask benchmark for long context understanding
[Bai et al., 2023] Yushi Bai, Xin Lv, Jiajie Zhang, Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, et al. Longbench: A bilingual, multitask benchmark for long context understanding. arXiv preprint arXiv:2308.14508,
arXiv 2023
-
[5]
Fovea transformer: Efficient long- context modeling with structured fine-to-coarse attention
[He et al., 2024] Ziwei He, Jian Yuan, Le Zhou, Jingwen Leng, and Bo Jiang. Fovea transformer: Efficient long- context modeling with structured fine-to-coarse attention. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 12261–12265. IEEE,
work page 2024
-
[6]
Snapkv: Llm knows what you are looking for before generation
[Li et al., 2024] Yuhong Li, Yingbing Huang, Bowen Yang, Bharat Venkitesh, Acyr Locatelli, Hanchen Ye, Tianle Cai, Patrick Lewis, and Deming Chen. Snapkv: Llm knows what you are looking for before generation. arXiv preprint arXiv:2404.14469,
arXiv 2024
-
[7]
[Liu et al., 2024] Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang, Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. Scissorhands: Ex- ploiting the persistence of importance hypothesis for llm kv cache compression at test time. Advances in Neural Information Processing Systems, 36,
work page 2024
-
[8]
Transformers are multi-state rnns
[Oren et al., 2024] Matanel Oren, Michael Hassid, Yossi Adi, and Roy Schwartz. Transformers are multi-state rnns. arXiv preprint arXiv:2401.06104,
arXiv 2024
-
[9]
Efficiently scaling transformer inference
[Pope et al., 2022] Reiner Pope, Sholto Douglas, Aakanksha Chowdhery, Jacob Devlin, James Bradbury, Anselm Lev- skaya, Jonathan Heek, Kefan Xiao, Shivani Agrawal, and Jeff Dean. Efficiently scaling transformer inference. corr, abs/2211.05102 (2022),
arXiv 2022
-
[12]
Llama 2: Open foundation and fine-tuned chat models
[Touvron et al., 2023] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint arXiv:2307.09288,
arXiv 2023
-
[13]
XL3M: A Training-free Framework for LLM Length Extension Based on Segment-wise Inference
[Wang et al., 2024] Shengnan Wang, Youhui Bai, Lin Zhang, Pingyi Zhou, Shixiong Zhao, Gong Zhang, Sen Wang, Renhai Chen, Hua Xu, and Hongwei Sun. Xl3m: A training-free framework for llm length exten- sion based on segment-wise inference. arXiv preprint arXiv:2405.17755,
work page Pith review arXiv 2024
Show all 19 references
-
[14]
Emergent abilities of large language models
[Wei et al., 2022] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yo- gatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint arXiv:2206.07682,
2022 arXiv
-
[15]
Efficient stream- ing language models with attention sinks
[Xiao et al., 2023] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient stream- ing language models with attention sinks. arXiv preprint arXiv:2309.17453,
2023 arXiv
-
[16]
Pyramidinfer: Pyra- mid kv cache compression for high-throughput llm infer- ence
[Yang et al., 2024] Dongjie Yang, XiaoDong Han, Yan Gao, Yao Hu, Shilin Zhang, and Hai Zhao. Pyramidinfer: Pyra- mid kv cache compression for high-throughput llm infer- ence. arXiv preprint arXiv:2405.12532,
2024 arXiv
-
[17]
Wordcraft: story writing with large language models
[Yuan et al., 2022] Ann Yuan, Andy Coenen, Emily Reif, and Daphne Ippolito. Wordcraft: story writing with large language models. In Proceedings of the 27th International Conference on Intelligent User Interfaces, pages 841–852,
2022
-
[18]
Pyramidkv: Dynamic kv cache compression based on pyramidal information funneling
[Zhang et al., 2024b] Yichi Zhang, Bofei Gao, Tianyu Liu, Keming Lu, Wayne Xiong, Yue Dong, Baobao Chang, Junjie Hu, Wen Xiao, et al. Pyramidkv: Dynamic kv cache compression based on pyramidal information funneling. arXiv preprint arXiv:2406.02069,
-
[19]
Fine-and coarse- granularity hybrid self-attention for efficient bert
[Zhao et al., 2022] Jing Zhao, Yifan Wang, Junwei Bao, Youzheng Wu, and Xiaodong He. Fine-and coarse- granularity hybrid self-attention for efficient bert. arXiv preprint arXiv:2203.09055, 2022
2022 arXiv
-
[2019]
Dct-former: Ef- ficient self-attention with discrete cosine transform
[Scribano et al., 2023] Carmelo Scribano, Giorgia Fran- chini, Marco Prato, and Marko Bertogna. Dct-former: Ef- ficient self-attention with discrete cosine transform. Jour- nal of Scientific Computing, 94(3):67,
2023
-
[2020]
Lm-infinite: Zero-shot extreme length generalization for large language models
[Han et al., 2024] Chi Han, Qifan Wang, Hao Peng, Wenhan Xiong, Yu Chen, Heng Ji, and Sinong Wang. Lm-infinite: Zero-shot extreme length generalization for large language models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Compu- ...
2024
-
[2022]
Compressive trans- formers for long-range sequence modelling.arXiv preprint arXiv:1911.05507,
[Rae et al., 2019] Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, and Timothy P Lillicrap. Compressive trans- formers for long-range sequence modelling.arXiv preprint arXiv:1911.05507,
2019 arXiv
-
[2023]
The pile: An 800gb dataset of diverse text for language modeling
[Gao et al., 2020] Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. The pile: An 800gb dataset of diverse text for language modeling. arXiv preprint arXiv:2101.00027,
2020 arXiv
-
[2024]
Fourier transformer: Fast long range mod- eling by removing sequence redundancy with fft operator
[He et al., 2023] Ziwei He, Meng Yang, Minwei Feng, Jingcheng Yin, Xinbing Wang, Jingwen Leng, and Zhouhan Lin. Fourier transformer: Fast long range mod- eling by removing sequence redundancy with fft operator. In The 61st Annual Meeting Of The Association For Com- putational ...
2023
Reviewed August 10, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.