acceptodds
Under review as a conference paper at ICLR 2027

Bridges over Heavy Hitters: A Causal-HITS Theory and Counterfactual Benchmark for Attention-Graph KV-Cache Compression

Abstract

Training-free KV-cache compression decides which past tokens a long-context language model may forget. Heavy-hitter methods retain tokens with large accumulated attention, whereas Stream-Influence scores tokens by centrality in the sparse causal attention graph. We show that Stream-Influence is a one-pass causal form of Kleinberg's HITS: a token's authority is the attention it receives from later tokens, weighted by their hub scores. Without normalisation, attention sinks make the recursion diverge, and we give a bounded alternative. On bridge-chain graphs, sparsified centrality recovers every bridge once the budget exceeds the chain length, while accumulated attention keeps only a prefix proportional to the budget, because causal mass makes early tokens heavy hitters regardless of content. A symmetry theorem then shows that if several structurally identical chains are present and only the question identifies the gold chain, every score depending on the question through a single hop assigns the same value to a gold bridge and its twin. This class includes H2O, SnapKV, StreamingLLM and Stream-Influence. BridgeBench instantiates both regimes with known bridges. Physical eviction on models from 3B to 14B confirms the obstruction: unseeded scores retain at most 8% of full-cache accuracy at a 10% budget and 21% at 20%. A beam-restricted walk seeded at the question over coreference heads recovers the gold chain, retaining 55% and 81% at these budgets against 10% and 25% for the best baseline. The same heads, transferred without re-calibration, keep 74% of the gold sentences on HotpotQA, where SnapKV keeps 12%.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Keywords KV cache compression, KV cache eviction, long-context LLMs, attention graph, graph centrality, HITS, multi-hop reasoning, benchmark, efficient inference

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_KyoxOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

Leveraging ideas from retrieval and graph diffusion theory, this paper identifies limitations of various existing KV cache compression and eviction methods. It proposes a new method based on seeded sparse propagation. The paper provides theoretical analyses and empirical evaluations to motivate and validate the proposed approach.

Critical strengths

S1. The paper presents insightful theoretical analyses disclosing the limitations of previous KV compression methods via the graph lens.

S2. Empirical studies demonstrate the effectiveness of the proposed approach, with diverse and in-depth analyses.

Critical weaknesses

The presentation still needs non-trivial improvement. Notably, the narrative connecting various contributions is not sufficiently clear, making the paper less accessible to the readers. Other related issues include unclear or confusing notations, e.g., equation (2); tt is both used for node index and time.

Questions for authors

N.A.

3 comments
AuthorsOpenReview ↗

Response to Reviewer

We thank the reviewer for the positive assessment of the theory and experiments. We revised the presentation along the two lines the reviewer raised. All changes are in blue in the revised PDF.

Narrative connecting the contributions. The four contributions are steps of one argument, and the revised introduction now says so before listing them (§1, paragraph "This paper"):

  1. What the score computes (§4.1–4.2). Stream-Influence (SI) is a causal HITS. Its score factorises into sparsified accumulated attention times a hub term.
  2. When it must fail (§4.3–4.4). Sparsification lets SI recover a single bridge chain where accumulated attention cannot (Theorem 7). But no unseeded score, SI included, can distinguish two structurally identical chains (Theorem 9).
  3. Measuring that regime (§5). Public benchmarks do not annotate which tokens matter, so they cannot show whether a policy failed for this reason. BridgeBench builds the twin-chain case of Theorem 9 and labels the bridge tokens.
  4. Escaping it (§5.1). Theorem 9 says the missing ingredient is a seed. SSP adds the question as the seed and propagates from it, and the experiments (§6) check each prediction: SI beats H2O on single chains, every unseeded score fails on twin chains, and seeding fixes it.

Each subsection of §4 and §6 now opens with one sentence naming which of these steps it serves (§5 and §5.1 already did).

Notation.

  • Index tt in Eq. (2). Token tt enters the graph at step tt, so the same index denotes the newest token and the current time. In Sj(t)S_j(t), jj is the key being scored and tt is the newest query. We now state this directly below Eq. (3) (§3). The unrolled form (4) uses t′t' for earlier queries.
  • λ\lambda had two meanings. It was both SI's recursion weight (0.5) and SSP's hop discount (0.7). The discount is now η\eta throughout the text, tables and appendix.
  • β\beta had two meanings. It was both PyramidKV's ratio (β=20) and the background bound in Proposition 11. The latter is now κ\kappa.
  • The symbols used later (B=ρLB=\rho L, KK, M(t)M(t), Aˉ\bar A) are collected at the end of §3.

We also tightened the statement of Theorem 7(a) and added baselines and analyses in response to the other reviewers (see the general response). We hope the revised version is easier to follow, and we are happy to fix any remaining unclear passage the reviewer points to.

Thank you for your response, which has addressed my concerns.

Thank you for reading our response and for the positive assessment. We are glad the revision addressed your concerns.

Reviewer_4FEfOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper investigates KV cache compression in multi-hop reasoning scenarios. First, it interprets the existing Stream-Influence method as a Causal HITS graph centrality algorithm and analyzes its numerical divergence and positional bias toward heavy hitters. It then establishes a symmetry theorem showing that single-hop attention scoring struggles to identify critical bridge nodes in structurally similar reasoning chains. Based on these findings, the paper introduces BridgeBench, a benchmark for evaluating bridge preservation, and proposes Seeded Sparse Propagation (SSP), which constructs a chunk graph using coreference heads and performs sparse multi-hop propagation seeded by the question to preserve critical evidence. Experiments across multiple models and both synthetic and natural language datasets validate the proposed approach.

Critical strengths
  1. Meaningful Theoretical Analysis. The paper interprets Stream-Influence from the perspective of Causal HITS and analyzes its numerical stability, positional bias toward heavy hitters, and the symmetry limitations of single-hop scoring. These analyses provide valuable insights into evidence loss in KV cache compression.
  2. Controlled Evaluation and Empirical Analysis. BridgeBench provides known critical evidence and reasoning chains, and evaluates compression effectiveness through actual KV cache eviction. The experiments cover multiple models, baselines, and ablation settings, with SSP achieving substantial improvements on controlled multi-hop reasoning tasks.
Critical weaknesses
  1. Limited External Validity of BridgeBench. BridgeBench-Real primarily consists of fixed templates and structurally similar entity chains, which closely align with SSP's coreference-based propagation mechanism. Although the authors include experiments on public benchmarks, it remains unclear whether BridgeBench adequately represents the diverse and complex multi-hop dependencies found in real-world long-context scenarios, raising concerns about its generalizability.

  2. Limited Practical Benefits of Multi-hop Propagation. The substantial advantages of the full SSP method are mainly observed on synthetic or procedurally generated tasks. On HotpotQA, MuSiQue, and LongBench, multi-hop propagation does not consistently outperform SSP-1hop and even degrades performance in some settings. This suggests that the practical gains may primarily come from coreference head selection, while the generalizable benefits of the core multi-hop propagation mechanism remain insufficiently validated.

  3. Insufficient End-to-end Efficiency Evaluation. Although SSP's standalone scoring overhead is relatively low, attention extraction significantly increases prefill costs in the experiments. The authors discuss potential implementation optimizations but do not provide corresponding end-to-end efficiency evaluations. Furthermore, experiments on extremely long contexts and streaming eviction are lacking, leaving the practical deployment benefits unclear.

Questions for authors
  1. Section 5.1 symmetrizes the chunk graph as W+W⊤W + W^\top. Does Beam Walk include a mechanism to prevent revisiting previously selected chunks? If revisits are allowed, how does the method prevent propagation scores from repeatedly accumulating between neighboring nodes?

  2. SSP retains entire chunks, while the actual cache budget is measured in tokens. How does the algorithm handle a chunk when the remaining budget is insufficient to accommodate it? Is partial retention allowed, and how would this affect evidence integrity?

4 comments
AuthorsOpenReview ↗

Response to Reviewer

We thank the reviewer for the focused questions. Both have concrete answers, and we added experiments for them. All numbers are Qwen2.5-7B, physical eviction, matched memory.

Q1. Does the beam walk prevent revisits on W+W⊤W+W^\top? In the submitted code it did not. The walk could step back to the previous chunk. Accumulation is still bounded, because the beam renormalises after pruning and the scores are discounted by ηh\eta^h (η\eta=0.7, HH=4). We implemented an explicit visited mask and report both variants:

recall (ρ=0.1 / 0.3)BridgeBench-Real bridgeHotpotQA gold chunk
default (revisits allowed)0.82 / 0.930.65 / 0.93
visited mask0.81 / 0.930.56 / 0.87

The mask makes no difference on BridgeBench-Real and hurts on HotpotQA, where stepping back lets the beam recover from a wrong first hop. Observation 10 assumes the mask, and A.9 now says this and reports both variants.

Q2. Chunks vs. a token budget. SSP ranks chunks and broadcasts the chunk score to its tokens, then fills the token budget in that order. The last chunk can therefore be cut at a token boundary, and the budget is never exceeded. We added an atomic variant that keeps a chunk only if it fits whole and otherwise tries the next one:

retention (ρ=0.1 / 0.2)BridgeBench-RealHotpotQA
SSP (partial last chunk)58 / 9286 / 100
SSP, atomic chunks54 / 8888 / 101

Partial retention changes results by at most 4 points, so it does not affect evidence integrity in a measurable way.

W1. External validity of BridgeBench. We agree that templates favour SSP's linking. We tested this directly with a shared-entity chunk graph, which links facts by string match only.

  • On BridgeBench-Real it beats SSP (95% vs. 58% at ρ=0.1), confirming that the benchmark rewards lexical linking.
  • On HotpotQA it drops to 66% (SSP 86%).

We now state in the paper that BridgeBench-Real is a controlled test of the obstruction (twin chains, question names only the first hop) and not a proxy for natural multi-hop QA.

W2. Practical value of propagation. We agree, and the revised paper says so more directly. A new audit replaces our earlier explanation, which was wrong.

  • Only 15% of HotpotQA and under 1% of MuSiQue questions name all intermediate entities.
  • Propagation does not help on these datasets because the question's attention already separates the gold chain from its distractors, even when we insert twin chains (see our follow-up to VU93). In about half the questions the question already attends to every gold chunk, and in the rest the attention graph does not lead to the missing chunk either (recall 0.48 with propagation vs. 0.51 without).

The practical gains on natural text therefore come from coreference-head seeding (SSP-1hop). Propagation helps only in the twin-chain regime that the theorem describes (BridgeBench-Real, RULER-VT).

W3. End-to-end efficiency. SSP does not need eager attention. We implemented a blockwise harvest that recomputes QK⊤QK^\top for the 32 selected heads in query blocks inside an SDPA prefill and keeps only column sums. It matches dense fp32 softmax to a relative error of 2⋅10−72\cdot10^{-7}.

LSDPA prefill+ blockwise harvestpeak memory vs. SDPAeager attention
2k0.10 s0.14 s+0 GiB0.51 s, 7.2 GiB vs. 0.7 GiB
4k0.17 s0.22 s+0 GiBOOM*
8k0.44 s0.68 s+0 GiBOOM*
16k0.76 s1.55 s+0 GiBnot run (≈460 GiB est.)
32k1.87 s4.99 s+0 GiBnot run (≈1.8 TiB est.)

*Eager attention used 7.2 GiB extra at 2k and grows as L2L^2 (≈29 GiB at 4k, ≈115 GiB at 8k). It ran out of memory from 4k on, on a GH200 (96 GB) shared with other jobs; we did not run it at 16k and 32k.

The time overhead grows from 1.5× to 2.7× and peak memory equals plain SDPA. Decoding cost is unchanged, because after eviction every policy decodes over the same number of entries. We added a streaming-eviction test (chunked prefill, per-head pruning after every 512-token chunk, LongBench HotpotQA, Qwen2.5-3B-Instruct, 200 questions). Per-head SnapKV retains 63% / 78% of full-cache F1 at ρ=0.1 / 0.2 and per-head Stream-Influence 55% / 61%, so the one-shot ordering holds. SSP needs the question and therefore applies once the question is in the prefill, as in the one-shot setting. Accuracy at more than 8k tokens remains untested, and we say so in the limitations.

AuthorsOpenReview ↗

Follow-up for Reviewer 4FEf: accuracy beyond 8k tokens

Our response above left accuracy beyond 8k tokens untested. We have now run it. Setup: LongBench examples whose context exceeds 8k tokens, no truncation (prompts of 8.1k to 17.9k tokens, median 16k), Qwen2.5-7B, physical eviction, matched memory. HotpotQA and MuSiQue use 150 questions each; 2WikiMQA has only 61 examples above 8k. Numbers are F1 retention relative to the full cache, at ρ=0.1 / 0.2.

policyHotpotQA2WikiMQAMuSiQue
SnapKV (official)101 / 102100 / 10394 / 95
per-head Stream-Influence92 / 9391 / 9676 / 80
SSP-1hop98 / 100104 / 10691 / 97
SSP (4 hops)100 / 97104 / 10593 / 96

Every SSP vs. SnapKV difference lies within the paired-bootstrap 95% interval (largest gap 2.5 F1 points). This repeats our 4.5k–7.7k result: on natural multi-hop QA, SSP matches a strong baseline but does not beat it, and the unseeded per-head score falls 7–18 retention points behind SnapKV. Propagation adds nothing over SSP-1hop on these datasets, as the question audit predicts.

To restate the W2 point: SSP-1hop is part of SSP. It keeps the question seed and the coreference-head selection and drops only the multi-hop walk. Its gains on natural text are therefore gains of the proposed method. Propagation is the component that the twin-chain regime of Theorem 9 needs.

Script: experiments/iclr_longbench_evict.py --min-ctx 8000. Results: experiments/results/rebuttal_long/. Both are now included in the supplementary material.

Thanks for the author's rebuttal response. The new experiment clarified the applicable conditions of Multi-hop Propagation, but I still have concerns about its actual incremental value in natural reasoning tasks. I maintain my score.

Thank you for the follow-up and for the careful review.

Reviewer_VU93OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
3
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies graph-based KV-cache compression, focusing on whether attention centrality preserves the tokens needed for multi-hop reasoning. It interprets Stream-Influence as a causal, max-aggregated analogue of HITS, analyzes instability and bridge-chain selection, and proposes a symmetry obstruction for question-local scoring rules. It introduces BRIDGEBENCH, a controlled benchmark with known evidence chains, and seeded sparse propagation (SSP), which propagates question attention over a chunk graph constructed from calibrated coreference heads. Evaluation includes physical KV eviction on multiple model families, natural-text QA, and synthetic reasoning benchmarks.

Critical strengths
  1. A useful diagnostic perspective and controlled evaluation. The paper asks a substantive question about what graph-based cache scores actually preserve, rather than relying only on aggregate downstream scores. BRIDGEBENCH exposes bridge and evidence annotations, while physical eviction connects selection quality to model behavior. The distinction between sparsification, hub amplification, head selection, and propagation is informative.

  2. Substantial experimental material and transparent negative results. The study covers several model families and scales, multiple datasets, and relevant ablations. It explicitly reports that propagation does not help on most natural-text evaluations and that the one-hop variant is often stronger. The supplementary material includes experimental scripts and per-instance outputs; rerunning the table-generation script reconstructs the main reported tables. This is valuable transparency, although regenerating tables from supplied outputs is not an independent reproduction of the model experiments.

Critical weaknesses
  1. The central theoretical guarantees are not established as stated. In Theorem 7(a), the proof bounds each background token by assuming it is selected by at most K background rows in expectation under random tie-breaking, then uses this as a deterministic bound for every token. For a fixed early token j, even uniform random tie-breaking gives an expected selection count proportional to K times the sum of 1/(t-1), rather than at most K. The theorem also does not specify random tie-breaking. A deterministic tie-break that repeatedly favors the same background tokens produces a direct counterexample: with L=1000, K=2, c=0.5, gamma=0.999, lambda=0, bridges at 200, 400, and 600, and pinned positions 1 and 1000, a budget B=5=n+w can retain no bridges. The non-pinned background token at position 10 scores approximately 2.19, rather than satisfying the claimed bound 2/999. Separately, Appendix A.9 invokes a visited mask to exclude the previous hop in the proof of Proposition 10, but the released propagation function does not apply that mask. On a symmetrized chain, backtracking can prevent the implemented beam walk from reaching later gold chunks. These issues affect two central arguments connecting the theory to the proposed method.

  2. The baseline implementations and transfer interpretation leave important uncertainty about the empirical conclusions. The released SnapKV scorer takes the maximum over observation-window query rows and then broadcasts maxima over disjoint fixed blocks. The official SnapKV implementation instead sums attention over query rows and applies sliding pooling, with head-specific selection. The per-head variant in the supplement still uses the former maximum-based aggregation, and PyramidKV also uses that scorer. These changes can alter rankings and require validation against the original implementations before attributing the reported failures to the proposed obstruction. In addition, Table 2 shows that full SSP matches SnapKV on HotpotQA F1 retention at 10% budget (89% each) and is slightly below it on MuSiQue (89% versus 91%); the strongest natural-text gains come from SSP-1hop. The explanation that these questions name every hop is not demonstrated by a dataset audit and is not generally true of bridge questions. The evidence supports a useful head-selection component and a propagation advantage in particular controlled settings, but does not yet fully validate the proposed explanation of when propagation helps.

Questions for authors
  1. Theorem 7: How is the per-background-token O(K/L) bound derived from random top-K tie-breaking? Please address the harmonic expected selection count and deterministic repeated-selection counterexample above. What additional assumptions are needed, and does the revised theorem still guarantee complete bridge retention at B=n+w?

  2. Proposition 10: Where is the visited-mask exclusion assumed in Appendix A.9 applied in the experimental implementation? The released function initializes visited but never uses it. Does enforcing the exclusion change the reported results, including the finding that propagation hurts on natural-text QA?

  3. Baseline fidelity: Can the authors report results using the original SnapKV aggregation and sliding pooling, including faithful per-head SnapKV and PyramidKV implementations under matched total cache memory? How sensitive are the main conclusions to the current reimplementation choices?

  4. Natural-text mechanism: What fraction of the evaluated HotpotQA and MuSiQue examples explicitly name all intermediate entities? Can performance be stratified by that property and by the question's direct attention coverage of gold chunks? This would help distinguish the proposed explanation from alternative effects such as contextualized question representations, pinned titles, or propagation noise.

  5. Positioning and distinct contribution: Could the paper more explicitly distinguish its contribution from the cited GraphKV and retrieval-head methods, and discuss related controlled studies of attention routing under KV compression? A comparison with a simple shared-entity chunk graph on BRIDGEBENCH would also help establish the value of extracting the graph from calibrated attention heads.

[1] Official SnapKV implementation: https://github.com/FasterDecoding/SnapKV/blob/main/snapkv/monkeypatch/snapkv_utils.py

[2] GraphKV (already cited by the submission): https://aclanthology.org/2025.emnlp-main.1112/

[3] HotpotQA, particularly the bridge-reasoning examples in Table 3: https://aclanthology.org/D18-1259.pdf

[4] Related controlled attention-routing study: https://arxiv.org/abs/2603.01426

9 comments
AuthorsOpenReview ↗

(1/2) Theorem 7(a), visited mask and baseline fidelity

We thank the reviewer for checking the proofs and the released code line by line. Both theoretical issues are real. We have fixed them in the revised PDF and re-ran the affected experiments. All numbers below are Qwen2.5-7B, physical eviction, matched total cache memory.

Q1. Theorem 7(a). The reviewer is right. The per-token bound O(K/L)O(K/L) holds only in expectation under uniform tie-breaking, and even then token jj's expected in-degree is ≈Kln⁡(L/j)\approx K\ln(L/j), not KK. The theorem also did not state a tie-breaking rule. We reproduced the counterexample: token 10 scores 2.19 and B=n+wB=n+w retains no bridge.

Repair (Theorem 7(a) and App. A.6). We now bound the total background mass instead of each token. Row tt keeps at most KK entries, each non-bridge entry has weight ≤1/(t−1)\le 1/(t-1), and the normalised hub score is ≤1+λ\le 1+\lambda. Hence, for any tie-breaking rule, ∑j∈bgSj≤K(1+λ)HL−1,HL−1≤1+ln⁡L.\textstyle\sum_{j\in\text{bg}} S_j \le K(1+\lambda)H_{L-1},\qquad H_{L-1}\le 1+\ln L. Every bridge scores ≥cε\ge c\varepsilon, so at most Nbg=K(1+λ)HL−1/(cε)=O(Klog⁡L)N_{bg}=K(1+\lambda)H_{L-1}/(c\varepsilon)=O(K\log L) background tokens can out-rank a bridge. Bridge recall is therefore 1 at B≥n+w+NbgB\ge n+w+N_{bg}.

  • To the direct question: no, B=n+wB=n+w is not guaranteed. The revised guarantee is B=n+w+O(Klog⁡L)B=n+w+O(K\log L), and the counterexample shows the log⁡L\log L term cannot be dropped without a tie-breaking assumption.
  • The separation from H2O survives: O(Klog⁡L)O(K\log L) extra slots against Θ(L)\Theta(L) for accumulated attention (part (b) is unchanged).
  • Numerically (L∈{103,4⋅103,1.6⋅104}L\in\{10^3, 4\cdot10^3, 1.6\cdot10^4\}, random, recency and a greedy adversarial tie-breaking), at most 3 background tokens exceed the weakest bridge, well inside the bound Nbg≤82N_{bg}\le 82.

Q2. Visited mask in Observation 10 (Proposition 10 in the submission). Correct. The released walk initialises visited but never uses it, so it can step back on Wˉ+Wˉ⊤\bar W+\bar W^\top. Proposition 10 describes the masked walk, and A.9 now says so explicitly. We implemented the mask (seeded_beam_norevisit) and report both variants (new Table in A.9):

recall (ρ=0.1 / 0.3)BridgeBench-Real bridgeHotpotQA gold chunk
SSP, default (revisits)0.82 / 0.930.65 / 0.93
SSP, visited mask0.81 / 0.930.56 / 0.87

On BridgeBench-Real the two are within 2 points. On HotpotQA the mask hurts, because stepping back lets the beam recover from a wrong first hop. The finding that propagation does not help on natural text is therefore unchanged by the mask.

Q3. Baseline fidelity. We implemented the official SnapKV scorer (sum over window queries, average pooling with kernel 5) head-averaged and per KV head, official PyramidKV on that scorer, and per-head Stream-Influence. New Table (App. "Question audit, baseline fidelity"), retention of full-cache accuracy:

policyBB-Real ρ=0.1ρ=0.2HotpotQA ρ=0.1ρ=0.2
SnapKV (our max-pooled)6189398
SnapKV official, head-avg1228797
SnapKV official, per head5139698
PyramidKV official018791
SSP589286100

The obstruction on BridgeBench-Real does not depend on the implementation choices: every unseeded variant stays at or below 22% at ρ=0.2. On HotpotQA, official per-head SnapKV beats full SSP at ρ=0.1 (96% vs. 86%), and we now state that propagation has no F1 advantage on natural text. Seeded selection without propagation (SSP-1hop) ties it on HotpotQA (96% vs. 96%, paired F1 −0.1 [−3.8, 3.6]) while keeping 75% of gold chunks vs. 3%, and leads on MuSiQue (103% vs. 89%, +5.1 [1.6, 8.8]). We report this baseline in the main text.

AuthorsOpenReview ↗

(2/2) Question audit, positioning and entity-graph control

Q4. Do natural questions name every hop? They do not. That sentence in the paper was wrong, and we thank the reviewer for asking for the audit. Only 46/300 HotpotQA bridge questions contain both gold titles, and only 1/300 MuSiQue questions contain all intermediate answers. Stratifying gives a different explanation:

  • The better predictor is whether the question's own attention already reaches every gold chunk (SSP-1hop gold recall = 1). This holds for 146/300 HotpotQA and 134/300 MuSiQue questions at ρ=0.1, and there SSP-1hop retains 106% F1.
  • On the remaining questions, propagation does not find the missing chunk: HotpotQA gold-chunk recall is 0.48 with H=4 vs. 0.51 with H=0, and MuSiQue 0.38 vs. 0.43.
  • Without twin chains, the attention graph adds neighbours of the seed rather than the missing hop.

We rewrote the explanation in §6.2, the introduction and the conclusion. The claim is now that propagation helps when the seed is ambiguous between structurally identical chains. Natural benchmarks rarely contain such chains, and we no longer claim that the questions name every hop.

Q5. Positioning, and the entity-graph control. We added the comparison the reviewer suggested: a seeded walk over a shared-entity chunk graph (IDF-weighted capitalised spans, in the spirit of HippoRAG).

  • On BridgeBench-Real it beats SSP (95% vs. 58% at ρ=0.1), because every hop there is a verbatim entity repeat.
  • On HotpotQA it drops to 66% (SSP 86%), because natural bridges are often paraphrases, pronouns or title mentions.

We report this openly. It shows that BridgeBench-Real rewards lexical linking, and that the attention graph is the more general source. Related work now separates SSP from GraphKV (KV-similarity graph, unseeded, hence 1-local by our theorem), retrieval heads and HeadKV (heads used to size budgets, not to build a graph), and HippoRAG (graph extracted offline, not read from the model). We also added the controlled attention-routing study [4] (Ananthanarayanan et al., 2026). It measures where routing breaks under compression on synthetic entity-tracking, coreference and multi-hop tasks, and links failure to the global eviction of answer-critical tokens. Our work asks which scores can keep the route, and Theorem 9 shows when no unseeded score can.

Summary of changes: Theorem 7(a) restated with a proof that holds for any tie-breaking rule; Observation 10 scoped to the masked walk, with both variants reported; official SnapKV and PyramidKV baselines; the "names every hop" claim replaced by an audit; an entity-graph control.

Thanks for the revisions and for showing where the simpler baseline does better. I still think a few points could be clearer:

  1. The new argument in Theorem 7(a) addresses my original counterexample, but Appendix A.7 still uses the old per-token bound. Could you update that proof too? Also, the counterexample shows that some extra slots are needed, and the new proof shows that a logarithmic allowance is enough. I don’t think either result shows that logarithmically many slots are necessary.

  2. Could you clarify what “the best baseline” refers to in the abstract? The new shared-entity graph does better than SSP on BridgeBench-Real in the Qwen2.5-7B comparison. It would also help to say that the 74% HotpotQA evidence-retention result comes from SSP-1hop. The audit shows that extra hops didn’t recover the missing evidence on the natural-text examples tested. The lack of structurally identical distractor chains could explain that, but the current experiment doesn’t tell us whether that’s the reason.

Reviewer_x5JFOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper analyzes Stream-Influence, the token-scoring rule of CentralKV, and argues theoretically that any score using the question only through its direct attention cannot retain multi-hop evidence when the context contains structurally identical distractor chains. The authors introduce the BridgeBench benchmark and propose SSP, which propagates the question's signal over a sentence graph built from selected coreference heads. On BridgeBench-Real, SSP retains 55% of full-cache accuracy at a 10% budget versus 10% for the best baseline, and the paper also tests transfer to natural-text QA.

Critical strengths
  1. Identifies a shared failure of existing KV eviction methods: multi-hop evidence is not retained. Existing methods depend on the question through at most one hop, so when the question names only the first hop, they cannot keep the later hops. The paper formalizes this in Theorem 9 and provides empirical evidence
  2. Proposes a useful dataset. BridgeBench-Real uses fictional entities with known bridges and answers and includes twin distractor chains. Combined with the physical-eviction protocol, it isolates how well a method retains multi-hop evidence.
  3. Stable ablations. The contributions of propagation, the beam, and head selection are each isolated, and the ranking is consistent across five models and two budgets and replicates on 32B.
Critical weaknesses

W1 . The reproduction of CentralKV does not match the original configuration. The paper runs Stream-Influence on a single global graph built from attention averaged over all heads, whereas CentralKV builds its graph per head, and its own ablation shows that switching to a global graph costs 4.4 F1; the paper's Appendix E also observes that the score stays bounded with a single head. Conclusions such as "indistinguishable from random eviction", "λ has no effect", and "the recursion diverges" therefore apply only to the paper's variant, and the LongBench results that contradict CentralKV's reported gains are left unexplained. I suggest adding experiments with the per-head version.

W2. Gains from propagation appear only on synthetic data and are unstable. Propagation helps only on BridgeBench-Real and RULER-VT, and the gain varies widely with model and budget: at a 10% budget it is +35 points for Qwen-3B but only +7 for Llama-8B, and on RULER-VT it helps only at a 2% budget. On HotpotQA, MuSiQue, LongBench, and BABILong, propagation brings no gain or even hurts, and full SSP matches or slightly trails SnapKV in F1. The authors attribute this to natural questions "naming every hop", but MuSiQue and bAbI by construction do not name the later hops, and they show no gain either.

W3. The theory contains a misstated result and overstates its scope. The proof of Theorem 7(a) uses the positions of the bridges to bound early background tokens, yet in Figure 1(b) the first few background tokens already score higher than the first bridge, so the theorem needs to be restated. Theorem 9 requires the question's attention to land only on the gold chain, but H2O and SnapKV operate on dense attention and are therefore not covered as stated; moreover, "unseeded scores perform at chance" cannot be distinguished from the trivial explanation that a question-agnostic score cannot know which chain is being asked about. In addition, Prop. 1, Cor. 2, and Prop. 10 are largely restatements and do not support the "Causal-HITS Theory" in the title.

W4. Insufficient scale and cost analysis. All decoding experiments use contexts under 8k tokens. SSP needs the full attention of 32 heads, which the paper obtains with eager attention, making prefill 2–3× slower; memory grows quadratically with length and reaches about 1 TB at 128k. The reported 14% overhead excludes this cost, and the fused kernel mentioned in the paper is not implemented.

W5. Missing related work. HeadKV (ICLR 2025) likewise calibrates heads on synthetic data before compressing the KV cache, and HippoRAG (NeurIPS 2024) seeds multi-hop propagation with question entities. Both are closely related to the proposed method but are neither cited nor compared.

Questions for authors

How does Stream-Influence perform on BridgeBench-Real and LongBench when run per head, as in CentralKV? Can you reproduce CentralKV's reported results? (W1)

3 comments
AuthorsOpenReview ↗

(1/3) Per-head Stream-Influence as in CentralKV

We thank the reviewer for the careful reading, in particular for pointing out the per-head configuration of CentralKV. We ran every experiment requested. All numbers are Qwen2.5-7B, physical eviction, matched total cache memory, unless stated otherwise.

W1 / Q1. Stream-Influence per head, as in CentralKV. We implemented one Stream-Influence graph per (layer, KV head), with CentralKV's defaults (K=8, γ=0.998, λ=0.5, sinks excluded). Each head keeps its own top-B set and the cache is pruned per head at the same total memory. Retention of full-cache accuracy (%):

policyBB-Real ρ=0.1ρ=0.2HotpotQA ρ=0.1ρ=0.2
Random (main-paper runs)374656
SI, global graph (submitted)454555
SI, per-head graphs (CentralKV)6137988
SnapKV official, per head5139698
SSP589286100

On MuSiQue (300 questions, 2/3/4 hops), per-head SI retains 69% / 79% of full-cache F1 at ρ=0.1 / 0.2, against 43% / 52% for the global graph (main-paper run), 89% / 96% for per-head official SnapKV and 90% / 102% for SSP (SSP − per-head SI: +7.6 F1 points at ρ=0.1, 95% CI [+3.3, +12.0]).

LongBench (200 questions per subset), F1 retention (%) at ρ=0.1 / 0.2:

policyHotpotQA2WikiMQAMuSiQueQasper
Random69 / 7574 / 8647 / 7561 / 66
SI, global graph (submitted)70 / 7771 / 8255 / 6457 / 65
SI, per-head graphs (CentralKV)92 / 9393 / 9793 / 9977 / 87
SnapKV98 / 10196 / 9795 / 9993 / 97
SSP97 / 100100 / 10195 / 10595 / 96

The per-head row comes from a new run with its own full-cache and SnapKV reference; its retention is computed against that run's full cache.

What changes and what does not:

  • The per-head version is much better than our global variant on natural text (+34 points on HotpotQA at ρ=0.1, and 33 points above random), consistent with CentralKV's own ablation. It remains below SnapKV (79% vs. 96%). We now use it as the CentralKV baseline in the main text and no longer describe Stream-Influence as random-level on natural text.
  • On BridgeBench-Real it is still near the random rate (6% / 13%, bridge recall 0.01 / 0.06). The obstruction of Theorem 9 does not depend on how the graph is built, because every per-head score is still 1-local.
  • The divergence result is about the head-averaged recursion with a persistent sink. As Appendix E notes, a single head stays bounded (max score ≤ 20), because its top-K set changes from query to query. §4.2, the abstract, the introduction and the conclusion now restrict "the recursion diverges" to the head-averaged graph.
  • The sentences "indistinguishable from random eviction" and "λ has no effect" now refer explicitly to the head-averaged variant. We also ran the λ ablation per head (LongBench HotpotQA, Qwen2.5-3B, 200 questions): λ=0.5 vs. λ=0 differs by +1.0 F1 at ρ=0.1 ([−1.2, +3.2]) and +1.0 at ρ=0.2 ([−0.4, +2.6]). With per-head graphs, the gain over the head-averaged variant therefore comes from sparsifying each head separately, and the hub term adds about one point.
  • On the size of the drop: CentralKV's ablation reports that a global graph costs 4.4 F1, while in our runs the global graph is 22 (LongBench HotpotQA) to 34 (HotpotQA) retention points below per-head graphs. The protocols differ: we evict physically at matched total memory, once after prefill, and with one shared keep-set for the global variant, so a token ranked low by the averaged graph is removed from every head. We have not isolated which of these differences causes the larger drop. Either way, the revision uses the per-head version as the CentralKV baseline throughout.
AuthorsOpenReview ↗

(2/3) CentralKV on LongBench and streaming eviction; propagation gains

On reproducing CentralKV's LongBench gains: in part. The per-head graph closes most of the gap to SnapKV that our global variant left (+15 to +38 retention points at ρ=0.1), which explains the LongBench contradiction the reviewer pointed out. It does not overtake SnapKV in our setting (Qwen2.5-7B, contexts truncated to 7.5k tokens, one eviction after prefill, matched memory). The paired F1 difference to SnapKV in the same run at ρ=0.1 is −3.7 (HotpotQA, 95% CI [−7.1, −0.3]), −2.5 (2WikiMQA, [−5.9, +0.8]), −1.8 (MuSiQue, [−5.3, +1.6]) and −6.8 (Qasper, [−10.0, −3.7]).

Closer to CentralKV's own setting (Llama-3.1-8B-Instruct, ρ=0.2, same protocol), the gap nearly closes. Paired F1 difference of per-head SI to SnapKV:

HotpotQA2WikiMQAMuSiQueQasper
ρ=0.2−1.1 [−3.1, +0.9]−1.1 [−3.8, +1.6]−1.5 [−4.1, +1.2]−6.6 [−9.4, −4.0]
ρ=0.1−2.6 [−6.2, +1.0]−2.9 [−6.0, −0.2]−4.4 [−7.3, −1.8]−11.2 [−14.4, −8.3]

On the three multi-hop sets at ρ=0.2 the intervals contain zero, so per-head SI is statistically tied with SnapKV there. The remaining difference from CentralKV's report is small on multi-hop QA and depends on model and budget. We did not run its 18-task suite. The revised §6.2 and Appendix H report all these numbers.

Our main results do not depend on CentralKV losing to SnapKV. They rest on BridgeBench-Real, where per-head SI and SnapKV are both near the random rate as Theorem 9 predicts, and on the divergence and separation results.

One-shot eviction lets SnapKV see the question, which CentralKV's online setting does not. We therefore also ran streaming eviction: chunked prefill (512 tokens), per-head physical pruning to the budget after every chunk (12.6 evictions per prompt), and online per-head SI updates with CentralKV's defaults. LongBench HotpotQA, Qwen2.5-3B-Instruct, 200 questions (full-cache F1 41.3):

policy (streaming)F1 retention ρ=0.1ρ=0.2answer-token recall ρ=0.1ρ=0.2
SI, per-head graphs (CentralKV)55610.070.13
SnapKV, head-averaged60710.120.27
SnapKV official, per head63780.090.23

The paired F1 difference of per-head SI to per-head SnapKV is −3.6 [−8.4, +1.2] at ρ=0.1 and −6.9 [−12.5, −1.3] at ρ=0.2. Streaming makes both policies worse but does not reverse their order. The question is in the last chunk, so SnapKV's final eviction still uses it, while SI has discarded tokens before the question arrives. We could not run the 7B model in this setting because of GPU memory shared with other jobs. We have not isolated the cause of the difference from CentralKV's reported numbers and say so in the paper.

W2. Propagation gains are limited to twin-chain data. We agree, and the revised paper says so directly. The reviewer is right that MuSiQue and bAbI do not name the later hops. Our earlier explanation was wrong, and an audit replaces it:

  • Only 46/300 HotpotQA bridge questions contain both gold titles, and 1/300 MuSiQue questions contain all intermediate answers.
  • The better predictor is whether the question's own attention already reaches every gold chunk. This holds for 49% (HotpotQA) and 45% (MuSiQue) of the questions at ρ=0.1, where SSP-1hop retains 106% of full-cache F1.
  • On the rest, propagation does not find the missing chunk (HotpotQA gold-chunk recall 0.48 with H=4 vs. 0.51 with H=0, MuSiQue 0.38 vs. 0.43). These contexts have no twin chains, so the attention graph leads to neighbours of the seed, not to the next hop. The same holds for bAbI, where every fact names the person asked about.

The revised claim is narrower: propagation helps when the seed is ambiguous between structurally identical chains (BridgeBench-Real, RULER-VT at tight budgets). On natural QA the useful component is the coreference-head seed. On BridgeBench-Real the propagation gain at ρ=0.1 varies by model (+36 Qwen-3B, +31 Qwen-7B, +22 Mistral-7B, +12 Qwen-14B, +7 Llama-8B), but it is positive for every model. We report the per-model gains in the main text instead of only the mean.

AuthorsOpenReview ↗

(3/3) Theory, cost and scale, HeadKV and HippoRAG

W3. Theory.

  • Theorem 7(a). The reviewer is right, and Reviewer VU93 found the same issue in the proof. The revised theorem bounds the total background mass instead of each token, for any tie-breaking rule: ∑j∈bgSj≤K(1+λ)HL−1\sum_{j\in bg} S_j \le K(1+\lambda)H_{L-1}. At most O(Klog⁡L)O(K\log L) background tokens can out-rank a bridge, so bridge recall is 1 at B≥n+w+O(Klog⁡L)B \ge n+w+O(K\log L). This matches Figure 1(b), where a few early background tokens score above the first bridge. The separation from H2O, which needs Θ(L)\Theta(L) extra slots, is unchanged.
  • Theorem 9 and dense attention. We extended the theorem (App. A.8). A 1-local score has the form Sv=fv(G∖{q},Aq,v)S_v = f_v(G\setminus\{q\}, A_{q,v}). For H2O and SnapKV, ff is 1-Lipschitz in the question's attention, so ∣Sv−Sπ(v)∣≤∣Aq,v−Aq,π(v)∣|S_v - S_{\pi(v)}| \le |A_{q,v} - A_{q,\pi(v)}|. The twins are tied whenever the question attends to them equally, and the gap shrinks in proportion to the asymmetry otherwise. The obstruction no longer requires the question's attention to land only on the gold chain.
  • "Question-agnostic scores cannot know the chain." For H2O, StreamingLLM and SI, this is exactly what the theorem says, and we agree it is the easy part. The content is in the question-dependent 1-local scores. SnapKV and SSP-1hop do read the question and do find the anchor fact (evidence recall 34–55% vs. 11% random). Yet they cannot rank the second hop above its twin. The theorem identifies one-hop dependence, not question-agnosticism, as the barrier, and the per-head and official-SnapKV results above confirm it.
  • Prop. 1, Cor. 2, Prop. 10. We agree these are short consequences of the definitions. The revision labels them Observations 1, 2 and 10 (numbering unchanged) and keeps "theorem" for Theorems 7 and 9. If the AC agrees, we will change the title to "A Causal-HITS View" for the camera-ready.

W4. Cost and scale. SSP does not need eager attention. We implemented a blockwise harvest inside an SDPA prefill: for the 32 selected heads it recomputes QK⊤QK^\top in query blocks and keeps only chunk-level sums. It matches dense fp32 softmax to a relative error of 2⋅10−72\cdot10^{-7}.

LSDPA prefill+ blockwise harvestpeak memory vs. SDPAeager attention
2k0.10 s0.14 s+0 GiB0.51 s
8k0.44 s0.68 s+0 GiBOOM*
32k1.87 s4.99 s+0 GiBnot run (≈1.8 TiB est.)

*Eager attention used 7.2 GiB extra at 2k and grows as L2L^2 (≈115 GiB at 8k). From 4k on it ran out of memory on a GH200 (96 GB) shared with other jobs.

No L×LL\times L tensor is stored, so the 1 TB figure no longer applies, and the overhead is 1.5–2.7× prefill time with no extra memory. Decoding cost is the same for every policy after eviction. Accuracy beyond 8k tokens is not yet tested, and we state this in the limitations.

W5. HeadKV and HippoRAG. Both are now cited and compared in related work. HeadKV scores heads on synthetic retrieval and reasoning data, as we do, but uses the scores to size per-head budgets. SSP uses the selected heads to build a graph and walk it from the question. HippoRAG runs personalised PageRank from question entities over an offline knowledge graph. As a direct control, we ran a seeded walk on a shared-entity chunk graph (IDF-weighted capitalised spans, HippoRAG-style). It beats SSP on BridgeBench-Real (95% vs. 58% at ρ=0.1), where every hop is a verbatim entity repeat, and drops to 66% on HotpotQA (SSP 86%), where bridges are paraphrases, pronouns or titles. We report both results: the benchmark rewards lexical linking, and the attention graph transfers better to natural text.

Comments on the paper

2 comments
AuthorsOpenReview ↗

(1/2) Summary of revisions and responses to shared concerns

We thank all reviewers. The reviews led to corrections, new baselines and a narrower, better-supported claim. All changed or added text in the revised PDF is in blue, and the list at the end gives the location of every change. Numbers are Qwen2.5-7B, physical eviction and matched cache memory unless stated otherwise.

1. Theory corrections (VU93, x5JF).

  • Theorem 7(a) (§4.3, proof in App. A.6). The per-token bound held only in expectation under one tie-breaking rule. The revised theorem bounds the total background mass by K(1+λ)HL−1K(1+\lambda)H_{L-1} for any tie-breaking rule, so bridge recall is 1 at B=n+w+O(Klog⁡L)B=n+w+O(K\log L). The separation from accumulated attention (Θ(L)\Theta(L)) is unchanged.
  • Observation 10 (§4.4, App. A.9, Table 3; Proposition 10 in the submission). The released walk did not apply its visited mask. Observation 10 now states that it assumes the mask, and we report both variants. They differ by at most 1 point on BridgeBench-Real, and the mask lowers HotpotQA gold-chunk recall (0.65 to 0.56 at ρ=0.1).
  • Theorem 9 (App. A.8). Extended from sparse to dense question attention, with a Lipschitz bound for H2O and SnapKV.
  • Framing (§4.1, §4.4). Proposition 1, Corollary 2 and Proposition 10 are now labelled Observations 1, 2 and 10; "theorem" is kept for Theorems 7 and 9.

2. Faithful baselines (VU93, x5JF). We added official SnapKV (head-averaged and per KV head), official PyramidKV and per-head Stream-Influence as in CentralKV (App. L, Table 20). Retention of full-cache accuracy at ρ=0.1:

policyBridgeBench-RealHotpotQA
SI, per-head (CentralKV)679
SnapKV official, per head596
PyramidKV official087
SSP5886

Every unseeded policy stays at or below 22% on BridgeBench-Real at ρ=0.2. On HotpotQA, per-head SnapKV is best at ρ=0.1, and the main text now says so (§6.2). On LongBench, per-head SI retains 77–93% of full-cache F1 at ρ=0.1, 2–7 F1 points below SnapKV. On Llama-3.1-8B at ρ=0.2, closer to CentralKV's setting, the multi-hop gap shrinks to 1.1–1.5 points with intervals containing zero (App. H, "Per-head Stream-Influence on LongBench"). The divergence result is now stated for the head-averaged graph only; single heads stay bounded (§4.2). Under streaming eviction (chunked prefill, per-head pruning after every 512-token chunk, HotpotQA, Qwen2.5-3B), the order holds: per-head SnapKV retains 63% / 78% at ρ=0.1 / 0.2 and per-head SI 55% / 61% (App. H, "Streaming eviction").

3. Why propagation does not help on natural text (VU93, 4FEf, x5JF). Our earlier explanation, that natural questions name every hop, was wrong. An audit (App. L, "Do natural questions name every hop?") shows that only 46/300 HotpotQA and 1/300 MuSiQue questions do. In about half the questions, the question's attention already reaches every gold chunk. In the rest, propagation does not find the missing chunk either (HotpotQA recall 0.48 with propagation vs. 0.51 without). Natural benchmarks contain no twin chains, which is the case Theorem 9 is about. We revised the claim in §1, §6.2, App. H and §7: coreference-head seeding is what transfers, and propagation helps only when the seed is ambiguous between identical chains (BridgeBench-Real, RULER-VT).

4. Is BridgeBench-Real too favourable to SSP? (4FEf, VU93). A shared-entity chunk graph (string matching, in the spirit of HippoRAG) beats SSP on BridgeBench-Real (95% vs. 58%) and loses on HotpotQA (66% vs. 86%) (App. L, "Attention graph vs. entity graph", Table 20). We now describe BridgeBench-Real as a controlled test of the obstruction and not as a proxy for natural multi-hop QA.

5. Efficiency (4FEf, x5JF). SSP does not need eager attention. A blockwise harvest inside SDPA prefill reaches 32k tokens with no extra peak memory and 1.5× to 2.7× prefill time (App. N). Decoding cost is the same for all policies at equal budget.

6. Presentation (Kyox). The introduction states how the four contributions form one argument (§1, "This paper"), each subsection of §4 and §6 opens with its role in that argument, the index tt in Eq. (2) is explained (§3), and conflicting symbols were renamed: SSP's discount is now η\eta (§5.1, Fig. 2 caption, Tables 17–19) and the bound in Proposition 11 is now κ\kappa (App. A.7).

7. Related work (x5JF, VU93). Added HeadKV, HippoRAG and the attention-routing study of Ananthanarayanan et al. (2026) (§2), with the distinction that SSP reads a seeded graph from the model at inference time. Retrieval heads and GraphKV were already discussed in §2.

AuthorsOpenReview ↗

(2/2) Location of every change in the revised PDF

LocationChangePoint
AbstractDivergence scoped to the head-averaged recursion; Theorem 7 budget "by a logarithmic margin"1, 2
§1"This paper" paragraph links the four contributions; contribution (2) budget is O(Klog⁡L)O(K\log L); natural-text explanation replaced1, 3, 6
§2HeadKV, HippoRAG, Ananthanarayanan et al. (2026)7
§3Meaning of the index tt in Sj(t)S_j(t)6
§4.1Observations 1 and 2 (formerly Proposition 1, Corollary 2); opening sentence1, 6
§4.2Divergence scoped to the head-averaged graph; per-head score stays ≤20\le 202
§4.3Theorem 7(a) restated for any tie-breaking rule; remark on the O(log⁡L)O(\log L) term1
§4.4Observation 10 (formerly Proposition 10); opening sentence1, 6
§5.1, Fig. 2 captionSSP discount renamed λ→η\lambda\to\eta6
§6.1Results scoped to the head-averaged SI; per-head SnapKV and per-head SI on BridgeBench-Real; SSP-1hop loss per model2
§6.2Per-head SI and official SnapKV on HotpotQA/MuSiQue/LongBench; corrected explanation of why propagation does not help2, 3
§7Conclusion and Limitations updated (no gain from propagation on natural QA; streaming tested on one model)3
App. A.6New proof of Theorem 7(a) with numerical check of the bound1
App. A.7β→κ\beta\to\kappa in Proposition 116
App. A.8Theorem 9 extended to dense question attention; why the obstruction is not trivial1
App. A.9, Table 3Visited mask: proof scope and both variants1
App. HPer-head SI on LongBench (Qwen2.5-7B, Llama-3.1-8B), λ=0\lambda{=}0 ablation; streaming eviction2
App. K, Tables 17–19λ→η\lambda\to\eta6
App. L, Table 20 (new)Question audit, official baselines, entity-graph control, atomic chunks2, 3, 4
App. NBlockwise harvest: memory and time from 2k to 32k tokens5

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.