{"id":"5308e675-db7c-4bd8-8947-ed83082dacf0","arxiv_id":"2501.04987","paper_version":3,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"TreeKV uses a cyclic pair-wise eviction tree with averaged attention scores to compress LLM KV caches, reporting SOTA perplexity on PG19/OpenWebText2 and best LongBench averages.","lead":"This paper introduces TreeKV, a training-free algorithm that compresses the key-value cache of large language models using a tree-like eviction pattern. It reports the best perplexity and long-context benchmark scores among tested compression methods at cache sizes up to 16x smaller than the full context.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"16k gains may be a position-encoding artifact: TreeKV re-assigns cached positions (Sec. 4.1) but the paper never states whether H2O/TOVA baselines are run with the same protocol; if they are not, Table 1/2 comparisons support cache-policy superiority only under mismatched position schemes.","rationale":"The reader's weakest_assumption points at the same Section 4.1 mechanism, but frames it as an internal degradation risk. My reading sharpens this into a baseline-comparison confound: unless H2O and TOVA are also run with re-assigned positions, Tables 1 and 2 are not apples-to-apples. This is more than a missing experimental detail because Llama-2-7B is 4k-trained; absolute positions beyond 4k are a known failure mode that StreamingLLM-style re-assignment specifically removes. The tree-policy advantage could therefore be an artifact of the position protocol. I do not see a reason to reject the method outright: the algorithm is clear, the wavelet observation is independent, and the ablation supports the tree's role. The correct outcome is the same CONDITIONAL verdict the reader reached, with the added explicit condition that the position-encoding protocol be controlled across baselines. If the controlled runs reproduce the reported margins, the central claim stands; if not, the paper's headline overstates what TreeKV contributes.","tokens_in":11789,"tokens_out":9789,"duration_ms":97251,"concrete_test":"On PG19, run two controlled comparisons. (1) TreeKV without position re-assignment (cached K/V keep absolute RoPE positions) at 16k with cache 1024; if perplexity rises from 6.91 toward TOVA's 7.15, the reported gain is attributable to re-assignment. (2) H2O and TOVA with StreamingLLM-style re-assignment identical to TreeKV at 8k/16k; if either matches or beats TreeKV, the claim that TreeKV's tree policy 'consistently surpasses all baseline models' is not supported. Report both sets of numbers in a revised table.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The empirical centerpiece is Tables 1 and 2: at 8k/16k context with a 1k cache, TreeKV reports lower perplexity than StreamingLLM, H2O, and TOVA. Section 4.1 says TreeKV re-assigns positional encodings after every eviction, following StreamingLLM, so cached keys are always treated as positions 0..c-1 rather than their true absolute positions. The paper does not report whether H2O and TOVA were given the same re-assignment. Llama-2-7B was trained with a 4k context, so true positions beyond 4k invoke untrained extrapolation; H2O/TOVA without re-assignment would be penalized at 8k/16k for reasons unrelated to which tokens are retained. If that is the setup, TreeKV's 6.88/6.91 vs TOVA's 7.06/7.15 at 8k/16k does not demonstrate that the tree eviction policy is better; it demonstrates that avoiding position extrapolation helps. Even if all baselines were aligned, the 'generalize to longer window' claim is weakened because no method in these tables ever attends over more than 1k effective positions; the 16k label refers to input length processed, not context attended. This makes the position-encoding protocol the load-bearing condition for the headline comparison.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12131,"tokens_out":5925,"duration_ms":55567,"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":[{"comment":"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.","section":"Section 4.1; Tables 1 and 2"},{"comment":"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":"Abstract and Section 5.2; Table 1"},{"comment":"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":"Section 5.2; Tables 1 and 2"},{"comment":"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.","section":"Section 5.2; Table 2"}],"minor_comments":[{"comment":"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":"Algorithm 1, line 16"},{"comment":"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.","section":"Section 5.3; Table 3 caption"},{"comment":"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":"Throughout"},{"comment":"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.","section":"Section 5.4; Figure 5"}],"recommendation":"major_revision","confidential_remarks":"The core idea is reasonable and the evaluation is broad, but the main language-modeling comparison needs a clear statement and, if necessary, a rerun under matched position-encoding protocols. The abstract overclaim and the effective-context-span issue are also fixable. I recommend major revision rather than rejection; if the authors confirm that all baselines used identical position re-assignment and update the claims accordingly, the paper could become acceptable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"TreeKV is worth a serious look. It is a training-free KV cache compression method that evicts tokens in a cyclic pairwise scope, using averaged attention weights to pick which of the two neighboring slots to drop. That eviction structure is new compared with H2O, TOVA, StreamingLLM, and SnapKV, and the ablation is well done: replacing the attention score with 'always keep the left token' changes perplexity little, which isolates the tree structure itself as the active ingredient. The method also works in both prefilling and decoding, which is not true of most baselines.\n\nThe empirical story is decent, but there is one load-bearing caveat. Section 4.1 says TreeKV re-assigns positional encodings after every eviction, following StreamingLLM, so all cached keys are treated as positions 0..c-1. The paper does not state whether H2O and TOVA were run with the same re-assignment. Llama-2-7B was trained on 4k context. At 8k/16k, a baseline keeping original positions would pay a penalty from untrained extrapolation, while TreeKV avoids that by construction. If the baselines were not given re-assignment, the 8k/16k gaps in Tables 1 and 2 do not show that the tree eviction policy is better; they show that position re-assignment helps. This is easy to fix: report the position protocol for every baseline, or rerun with matching protocols. Without that, the headline claim 'consistently surpasses' is not established.\n\nSmaller issues: the abstract overclaims on the 4k PG19 result (TOVA 7.00 vs TreeKV 7.02), OpenWebText2 has no variance reporting, and the prefilling block size b is undisclosed. The wavelet analysis is a nice motivation, but the method stands on its own. Positively, the algorithm is clearly specified, the code is released, and the LongBench comparison is thorough, including an honest note that TreeKV loses to SnapKV on some tasks at 2k. Nothing here is circular: the wavelet observation motivates the design, but no parameter is fitted to the test results.\n\nI would send this to a serious referee. The position-encoding protocol question is the crux; if the authors clarify it and make comparisons fair, the contribution is real. If they cannot, the long-context claims shrink to 'competitive with StreamingLLM-style position tricks.' Either way, this is a legitimate paper for the efficient-inference community.","headline":"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.","tokens_in":12677,"tokens_out":4189,"would_cite":true,"duration_ms":35069,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A tree-shaped KV cache beats attention baselines at 16x compression.","keywords":["KV cache compression","tree structure","streaming LLM","long-context generalization","wavelet analysis","attention importance","prefilling","language modeling"],"falsifier":"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.","tokens_in":11588,"feed_emoji":"🌳","tokens_out":5963,"duration_ms":55012,"temperature":0.7,"pith_summary":"TreeKV is a training-free cache-compression method for transformer LLMs that arranges retained key-value pairs in a tree-like structure: sparse coverage of distant context and dense coverage of recent context. A wavelet analysis of attention-weighted values motivates this layout, showing token contributions grow and diverge from neighbors as positions approach the end of the sequence. With a fixed cache of 1024, TreeKV lets Llama-2-7B (trained on 4k context) reach 16k sequences at lower perplexity than StreamingLLM, H2O, and TOVA on PG19 and OpenWebText2, a 16x cache reduction. The same mechanism applied to blocks compresses prompts during prefilling, and on Longbench TreeKV reports the best average among compression baselines at 2k and 8k cache sizes.","feed_headline":"Tree-shaped KV cache beats baselines at 16x compression","feed_subtitle":"Training-free TreeKV lets a 4k-context Llama-2 handle 16k text with the lowest perplexity and top Longbench scores.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the attention-sink baseline and the position re-assignment scheme TreeKV adopts after eviction.","marker":"[Xiao et al., 2023]"},{"why":"Provides H2O, the greedy heavy-hitter importance baseline TreeKV compares against and whose regional bias motivates the tree design.","marker":"[Zhang et al., 2024c]"},{"why":"Provides TOVA, the last-token-attention baseline used in language-modeling comparisons and the 10M-token test.","marker":"[Oren et al., 2024]"},{"why":"Supplies SnapKV, the observation-window and block-based prefilling baseline, plus the block-level selection idea TreeKV adapts.","marker":"[Li et al., 2024]"},{"why":"Supplies PG19, the long-book language-modeling test set for perplexity and the concatenated 10M-token sequence.","marker":"[Rae et al., 2019]"},{"why":"Supplies OpenWebText2 through the Pile dataset, the second language-modeling evaluation set.","marker":"[Gao et al., 2020]"},{"why":"Supplies Longbench, the 16-task benchmark used for long-context understanding evaluation.","marker":"[Bai et al., 2023]"},{"why":"Supplies Llama-2-7B, the base model used for all long-text generation experiments.","marker":"[Touvron et al., 2023]"}],"fun_headline_variants":["TreeKV: tree-structure eviction compresses KV cache 16x","Training-free TreeKV beats baselines with smooth tree eviction","Smooth tree eviction in TreeKV yields 16x cache reduction","TreeKV: from 4k to 16k context with 16x cache cut"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["TreeKV: tree-structure eviction compresses KV cache 16x","Training-free TreeKV beats baselines with smooth tree eviction","Smooth tree eviction in TreeKV yields 16x cache reduction","TreeKV: from 4k to 16k context with 16x cache cut"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000452,"raw_usage":{"total_tokens":2279,"prompt_tokens":953,"completion_tokens":1326,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":569,"completion_tokens_details":{"reasoning_tokens":1244}},"tokens_in":569,"tokens_out":1326,"duration_ms":10550,"temperature":1.0,"reasoning_tokens":1244,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:20:59.855691+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}