acceptodds
Under review as a conference paper at ICLR 2027

CarryKV: Logarithmic Branch Routing for Sparse Attention with Additive States on a Carry Forest

Abstract

Efficient hierarchical sparse attention requires identifying useful regions without scanning the full history. We introduce CarryKV, a training-free retriever with compact, mergeable branch summaries. Each branch partitions post-RoPE keys into cells storing counts and key sums; weighted log-sum-exp over cell means estimates attention mass. States merge additively in a persistent hierarchy, and final attention uses original K/V selected at the leaves. We cast HiP's implicit interval pruning and CarryKV's persistent hierarchy in a common bounded-refinement framework, exposing how branch information determines pruning quality. Multi-cell summaries weakly improve the one-sided mass estimate over a single mean, and lower residuals strengthen a same-frontier retained-mass guarantee. The remaining residual has a reverse-KL interpretation; a merge decomposition separates inherited residual from new readout error. Controlled branch experiments measure the resulting mass estimates and pruning decisions across scales. On Qwen3-8B at native 32K, CarryKV improves RULER by 13.37 points over HiP and 6.80 over InfiniteHiP. On Qwen3-1.7B, it outperforms InfiniteHiP on RULER and PG19 from 4K to 128K. At fixed budgets, routing requires work per query block and sparse-prefill retrieval requires work over a length- context.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Sparse attention for LLMs, Hierarchical retrieval, Logarithmic-time KV retrieval, Training-free sparse attention

Reviews

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

This paper proposes CarryKV, a training-free hierarchical retriever for sparse attention. It summarizes temporal branches using query-independent cell counts and key sums, estimates branch attention mass through a count-weighted log-sum-exp readout, and maintains these summaries in a persistent carry forest.

Critical strengths
  1. A coherent and interpretable approach to branch valuation.

  2. Meaningful improvements over the evaluated hierarchical baselines.

Critical weaknesses
  1. The experiments do not establish a compelling practical quality–efficiency operating point.

The improvements over hierarchical baselines coexist with substantial degradation relative to dense attention. On Qwen3-8B, CarryKV obtains RULER scores of 69.16, 51.76, and 27.41 at 32K, 64K, and 128K, compared with 88.28, 74.32, and 58.29 for Dense.

The empirical comparisons are also concentrated on HiP and InfiniteHiP. Relevant sparse-prefill alternatives such as FlexPrefill, XAttention, and FlashPrefill V2 should be considered when assessing practical competitiveness. Their published results cannot establish superiority under this paper’s settings, but their existence makes consistent, matched-quality or matched-latency comparisons important. Without budget sweeps and stronger baselines, it remains unclear whether CarryKV offers a favorable tradeoff rather than improving a restricted baseline configuration.

  1. The model coverage is too narrow to substantiate broad applicability to modern long-context inference.

All evaluated backbones belong to the Qwen3 Base family. Modern hybrid architectures provide a materially different setting: for example, Qwen3.5-9B interleaves three Gated DeltaNet layers with one full Gated Attention layer.

Questions for authors
  1. Can CarryKV achieve quality close to Dense attention while providing measurable end-to-end prefill acceleration, with quality, TTFT, and peak memory evaluated under the same configuration?

  2. Does CarryKV retain an advantage over InfiniteHiP at matched latency and over strong sparse-prefill alternatives such as FlexPrefill, XAttention, and FlashPrefill V2 using their supported accuracy-preserving mechanisms?

  3. Can CarryKV provide additional acceleration without substantial quality degradation when applied to the full-attention layers of modern hybrid models such as Qwen3.5?

3 comments

Thank you for recognizing our branch-mass formulation and highlighting the need for stronger practical evidence. We agree that its usefulness requires full-model evaluation. We have added latency/support-matched comparisons and a hybrid-model evaluation to address your questions.

Q1. Dense quality and end-to-end acceleration

CarryKV’s main contribution concerns branch valuation within HiP-style pruning. To examine its practical potential, we developed a GPU-oriented fixed-depth variant.

This changes the traversal, not merely the kernel: coarse scanning costs O(N/S) per query block and quadratic work over prefill at fixed span S and query-block width. The canonical O(log N) guarantee therefore does not apply. InfiniteHiP discusses a related parallelism–complexity trade-off (Infinitehip Appendix A.1). We will separate these new deployment results from the original algorithm’s guarantees.

On Qwen3-8B-Base at 64K/YaRN ×2, BF16, batch 1, A800, we evaluate 3,328 paired RULER examples (256 × 13 tasks). System results are means over the same fixed 10 independent sequences. Coarse branches cover 64 or 32 tokens and refine into 16-token nodes; Temporal-4 denotes four internal summary cells.

ConfigurationRULER (%)Mean TTFT (s)
Dense74.0810.857
Temporal-4, 64-token coarse span68.978.191
Temporal-4, 32-token coarse span75.2210.890

The 64-token variant reduces TTFT by 24.56% (1.325× speedup) with a 5.11-point lower score. The 32-token variant scores 1.14 points higher with 0.304% higher TTFT, approximately matching Dense latency. These offer different trade-offs; neither improves both metrics over Dense.

All three report 30.519 GiB mean peak allocated memory. CarryKV retains full-resolution K/V and adds routing summaries, without raw-cache eviction, compression, or offloading. We claim no peak-memory reduction; more efficient KV management remains future work.

Q2. InfiniteHiP and stronger sparse-prefill alternatives

To distinguish retrieval efficiency from implementation cost, we report both near-matched-latency and matched-support comparisons.

Near-matched latency. CarryKV’s 32-token variant achieves 75.22% at 10.890 s, versus InfiniteHiP’s 69.21% at 11.019 s: +6.01 points with 1.17% lower TTFT. InfiniteHiP uses remote budget 4,096, 32 sink tokens, and a 256-token local window. This is not a matched-support comparison.

Native and support-matched settings. Both CarryKV variants use 2,371.15 mean effective attention tokens. The corresponding baseline results are:

Baseline configurationMean supportRULER (%)TTFT (s)
FlexPrefill, γ=.9 / τ=.16,751.1574.167.924
XAttention, S16 / t=.9512,195.7874.588.939
FlexPrefill, support-matched≈2,371.1570.877.756
XAttention, support-matched≈2,371.1557.748.751

At matched mean support, CarryKV’s 32-token variant scores 4.35 points above FlexPrefill and 17.48 points above XAttention, but is slower. Its 64-token variant scores 11.23 points above support-matched XAttention with 6.40% lower TTFT.

The gains are not solely due to retaining more tokens. However, native FlexPrefill/XAttention remain faster than our higher-quality point. The advantage is therefore operating-point dependent.

Each method retains its supported accuracy-preserving mechanisms. Equal mean support does not imply equal per-query counts or search work; TTFT includes routing overhead. FlashPrefill V2’s released Hopper-only kernel is incompatible with A800, so we do not mix cross-hardware timings.

Q3. Hybrid architectures

We extend the evaluation to Qwen3.5-0.8B at 32K and 64K, with 3,328 examples per length (256 × 13). CarryKV replaces only full-attention layers; linear-attention components remain native. “Native” denotes the unmodified hybrid model.

Method32K RULER (%)32K TTFT (s)64K RULER (%)64K TTFT (s)
Native69.200.439470.651.1607
CarryKV70.150.529771.671.2264
FlexPrefill70.100.544169.841.5060
XAttention70.400.681070.541.9680

CarryKV scores 0.95 points above Native at 32K and 1.02 points above at 64K, but TTFT is 20.55% and 5.66% higher, respectively. Thus, these configurations do not accelerate Native.

At 64K, it scores 1.83 points above FlexPrefill with 18.57% lower TTFT, and 1.13 points above XAttention with 37.68% lower TTFT. These comparisons use each method’s evaluated settings rather than matched support.

This extends the evidence to a hybrid architecture, but we do not extrapolate from this small model to Qwen3.5-9B.

Overall, these experiments support specific practical benefits, not universal superiority. We will report both the gains and limitations, separately from the canonical algorithm’s theoretical guarantees.

Dear Reviewer,

A revised manuscript has been uploaded. We have made several changes to address your concerns:

  1. Method clarification (Sections 3.1–4.3): We clarified the relationship between HiP and CarryKV, explicitly defined temporal branches, query blocks, and joint attention mass, and distinguished summary cells from tree children.
  2. Revised Figures 1–2 and method description: Figure 1 contrasts HiP's center-key valuation with CarryKV's multi-cell scoring and illustrates a concrete pruning example. Figure 2, together with the revised method description, clarifies bottom-up summary construction, branch selection, and retrieval of original K/V.
  3. Algorithm specification (Appendix B.1): We expanded the notation and traversal details, including frontier sizes, pruning decisions, and the scope of the logarithmic routing bound.
  4. Additional experiments (Appendix D.5): We added full-model quality–latency evaluations and explicitly distinguished the GPU-oriented fixed-depth implementation from canonical logarithmic traversal.

We appreciate your detailed feedback, which helped us improve the clarity and technical presentation of the manuscript.

Thank you for the additional experiments addressing stronger baselines and hybrid architectures.

My main concern remains: the higher quality configuration provides no meaningful acceleration over Dense, while the faster configuration is both slower and less accurate than native FlexPrefill.

I am therefore keeping my original score.

Reviewer_PjVXOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper introduces CarryKV, an extension to hierarchical sparse-attention methods such as HiP. While HiP uses the center key of each interval to guide pruning, CarryKV proposes alternative representations, including the mean key of an interval and multiple group-wise means, to better estimate its attention mass. These summaries are maintained in a persistent hierarchical structure.

The paper provides theoretical guarantees on attention-mass estimation and the quality of branch selection at each level of the hierarchy, as well as an (O(\log N)) routing-time bound per query block under fixed budgets. The method is evaluated only in the sparse-prefill setting, with dense decoding, and experiments are limited to models from the Qwen3 family.

Critical strengths
  1. Improved retrieval quality: CarryKV achieves improvements over HiP and InfiniteHiP on several RULER settings.

  2. Efficient index maintenance: The persistent carry forest supports incremental updates through additive merging without rescanning previously indexed keys.

  3. Theoretical analysis: The paper provides theoretical guarantees on mass estimation, branch-selection quality, and routing complexity.

  4. GPU implementation: The authors provide a GPU implementation with custom kernels for branch scoring and sparse attention.

Critical weaknesses

TLDR

Based on the following, I really believe the current version of the paper is not ready for publication. It requires major changes to prepare it for submission. Specifically, on both the presentation and evaluation sides.

Weaknesses

W1. The motivation and the explanation of HiP are difficult to follow

The paper moves quickly from the sparse-prefill problem to branch valuation, frontiers, and carry forests without explaining HiP's search procedure clearly enough for a reader unfamiliar with it. In particular, Section 3.1 introduces Center-1 without a formal definition; the precise lower-midpoint scoring rule appears mainly in the appendix. It is also not sufficiently clear in the main text when the authors compare the Center-1 scoring rule on fixed candidate branches versus the complete HiP system. This makes it harder to understand what CarryKV changes relative to HiP and what additional costs those changes introduce.

How to address?

The introduction needs to be rewritten to better reflect the main story of the paper, gradually starting from high-level intuitions to the details. Give a short, self-contained explanation of HiP and define Center-1 explicitly in the main text. A small example distinguishing the fixed-frontier scoring comparison from full-system retrieval would also help.

W2. The novelty and related-work positioning are not convincing enough

Centroid-based KV retrieval and hierarchical centroid search have been studied before, including in Squeezed Attention. Also Louver uses key-cluster centers for a different, threshold-based retrieval objective. The use of several centroids per group and a count-weighted exponential mass estimate is also a relatively simple extension of a single-mean representation, so the paper needs to better separate established ingredients from its new contribution. In addition, the attention-output error bound in Section 3.2 follows directly from retained probability mass and has equivalents in earlier sparse-attention literature. The discussion still does not clearly establish the novelty of the specific combination of summaries, merging and retrieval w.r.t. these and other existing ideas.

Ref

How to address?

Discuss the closest missing prior work and clearly distinguish established centroid-based ideas and mass bounds from the new parts of CarryKV. A controlled comparison against simpler centroid-based designs would strengthen the novelty argument.

W3. Isolated important keys can be lost, and the guarantee is only local to a frontier

Hash-4 groups keys using only two query-independent sign projections, so a highly relevant key may be averaged with many irrelevant keys in the same cell. This can underestimate its branch's attention mass and cause irreversible pruning before the important key is examined. The main retained-mass guarantee compares the selected branches with exact top-B selection on the same frontier, rather than guaranteeing that globally important keys survive the entire hierarchy. The appendix does examine path survival, but it does not establish exact top-k recall guarantee.

W4. Temporal-4 outperforms Hash-4, so the choice of default method is unclear

On Qwen3-8B RULER, Temporal-4 scores 73.43 versus 69.16 for Hash-4 at 32K and 55.28 versus 51.76 at 64K. The paper also reports much less persistent routing memory for Temporal-4: 11.19 MB per layer instead of 56.17 MB for Hash-4 at 32K capacity. The authors acknowledge these results and report a separate fixed-state output-error advantage for Hash-4, but that does not clearly justify using Hash-4 as the main method (and as the main contribution).

W5. Important hyperparameters and the cost of deep GPU traversal are insufficiently studied

The experiments largely fix a 16-token leaf, beam size 64, branching factor four, Q64 query blocks and a roughly 1K remote-token budget without showing how these choices affect quality and performance. These parameters jointly determine selection granularity, hierarchy depth, frontier size and routing cost, so one default configuration does not establish a good operating point.

The paper provides custom GPU kernels and context-scaling measurements, but not a controlled depth or shallow-versus-parallel traversal comparison.

How to address?

Add sensitivity experiments for the main search parameters, preserving comparable token budgets where possible. Compare deep traversal with shallow or parallel alternatives and break down the GPU cost of the routing stages.

W6. The persistent index uses substantial additional memory without reducing the KV cache

CarryKV still stores the original keys and values for final attention, and its routing summaries require additional persistent memory. At 32K capacity for Qwen3-8B, the paper reports 128 MiB of original K/V plus 56.17 MB of Hash-4 routing state per layer. It also states that the index remains allocated during dense decoding, when it is not used for sparse retrieval. These costs may reduce available batch size or concurrent-serving capacity, but the experiments do not quantify that system-level tradeoff.

Experimental Setup

W7. Limited evaluation scope

The experiments cover only sparse prefill with dense decoding and two Qwen3 models, leaving generalization to other architectures and long-generation workloads untested.

W8. Degraded quality at longer contexts

At 128K, CarryKV loses its accuracy advantage over HiP and remains substantially worse than dense attention, raising concerns about its effectiveness at longer contexts.

W9. Missing end-to-end latency evaluation

The reported timings cover only the attention operator, excluding other model computations, so they do not establish full-model prefill or serving speedups (time-to-first-token).

W10. Limited efficiency compared with InfiniteHiP

CarryKV is substantially slower than InfiniteHiP, and the paper lacks quality–latency comparisons across different retrieval budgets to justify this overhead.

W11. Inconsistent quality and latency configurations

Quality experiments include sink and local attention tokens, while latency experiments exclude them, making it difficult to assess the actual quality–efficiency tradeoff.

Questions for authors

Please see Weaknesses

3 comments

Thank you for the careful review. We have clarified the method and figures and added full-model experiments on support budgets, end-to-end efficiency, and hybrid architectures. We address your concerns below.

W1. HiP and Center-1. Center-1 is HiP’s center-key valuation, not a separate retrieval method. For [l,r)[l,r), both use the lower-midpoint key ⌊(l+r−1)/2⌋\lfloor(l+r-1)/2\rfloor. Fixed-frontier comparisons use identical candidates; full-system comparisons run complete pipelines. Figure 1 illustrates the distinction.

W2. Novelty and related work. Cell means summarize temporal branches, not a clustering-based hierarchy. Section 2(revised version) contrasts this with Squeezed Attention’s clustering and Louver’s threshold retrieval. Our contribution concerns mergeable multi-cell valuation, residual-dependent selection and merge-error analysis—not centroids or the basic output bound individually. Mean-1 supplies a single-centroid control.

W3. Isolated keys and guarantees. HiP’s center key can miss isolated keys; a single mean can dilute them. Multi-cell summaries reduce dilution by preserving between-cell variation, while within-cell information loss remains. The same-frontier bound relates residuals to retained mass; path-survival experiments examine cumulative pruning loss.

W4. Partition choice. The quality and memory results favor Temporal-4, which we use in the new evaluations. Partition design remains open; neither instance is a separate contribution or a universal optimum. The designed variants in our manuscript is just a controlled comparsion to prove that multi-cells representation' s advantage over single representation(mean-1). Learned ranking or bucketing mechanism could address remaining selection losses.

W5. Sensitivity and GPU traversal. We compared coarse spans of 64 and 32 tokens and two 128K budgets; a broader sensitivity study remains future work. Fixed-depth retrieval changes traversal, not just the kernel: scanning costs O(N/S)O(N/S) per query block and quadratic prefill work at fixed coarse span SS. The canonical logarithmic guarantee does not apply. InfiniteHiP discusses a similar trade-off (Infinitehip Appendix A.1).

W6. Memory. Routing summaries are released before dense decoding, while raw K/V remains resident. Temporary summaries still contribute to prefill memory; Dense and both 64K variants have a mean peak allocation of 30.519 GiB.

W7. Coverage. We evaluated Qwen3.5-0.8B on 256 × 13 paired examples per length, replacing only full-attention layers:

Method32K RULER (%)TTFT (s)64K RULER (%)TTFT (s)
Native69.200.439470.651.1607
CarryKV70.150.529771.671.2264
FlexPrefill70.100.544169.841.5060
XAttention70.400.681070.541.9680

At 64K, CarryKV improves both metrics over these sparse baselines but is 5.66% slower than Native. Support is not matched; other families and long-generation workloads remain untested.

W8. Long-context degradation. At 128K/YaRN4, we evaluated Qwen3-8B-Base on 200 × 13 paired requests:

ConfigurationMean supportRULER (%)TTFT (s)
Dense64,875.7758.7235.0711
CarryKV2,394.0039.3317.9766
InfiniteHiP2,394.0030.6129.3842
FlexPrefill, matched2,394.0040.1215.6069
XAttention, matched2,394.0032.5321.0545
CarryKV4,387.0055.3320.9766
InfiniteHiP4,387.6949.5434.6719
FlexPrefill, adaptive9,904.0653.6118.3339
XAttention, adaptive S16/.9520,317.4155.1824.6666

Higher support raises CarryKV’s score by 16.00 points, reaching 3.39 points below Dense with 1.672× speedup. It scores similarly to adaptive XAttention with 14.96% lower TTFT.

W9. End-to-end latency. At 64K/YaRN2, we evaluated Qwen3-8B-Base on 256 × 13 paired examples (BF16, batch 1, A800):

ConfigurationRULER (%)Mean TTFT (s)
Dense74.0810.857
Temporal-4, coarse span 6468.978.191
Temporal-4, coarse span 3275.2210.890

The 64-token variant reduces TTFT by 24.56% with a 5.11-point lower score; the 32-token variant scores 1.14 points higher at approximately Dense latency. TTFT includes full-model prefill, routing and first-token selection.

W10. Baseline comparisons. At comparable 128K support (W8), CarryKV gains 8.72/5.79 points over InfiniteHiP with 38.82%/39.50% lower TTFT. At 2,394 tokens, it also gains 6.80 points over XAttention; FlexPrefill is faster and scores 0.79 points higher.

At approximately matched latency at 64K, CarryKV scores 75.22% at 10.890 s versus InfiniteHiP’s 69.21% at 11.019 s. Native FlexPrefill/XAttention score 74.16%/74.58% at 7.924/8.939 s, respectively, and remain faster at their larger supports.

W11. Consistent settings.
The original kernel-latency tests focused on remote retrieval, retaining the quality evaluations’ routing configurations while uniformly excluding sink/local additions. We apologize for not clarifying this distinction. Our new full-model evaluations use consistent quality and latency settings, including sink/local attention and accuracy-preserving mechanisms. For adaptive baselines, we additionally report support-matched variants as budget-controlled references, rather than latency-optimized configurations.

Dear Reviewer,

A revised manuscript has been uploaded. We have made several changes to address your concerns:

  1. Method clarification (Sections 3.1–4.3): We clarified the relationship between HiP and CarryKV, explicitly defined temporal branches, query blocks, and joint attention mass, and distinguished summary cells from tree children.
  2. Revised Figures 1–2 and method description: Figure 1 contrasts HiP's center-key valuation with CarryKV's multi-cell scoring and illustrates a concrete pruning example. Figure 2, together with the revised method description, clarifies bottom-up summary construction, branch selection, and retrieval of original K/V.
  3. Algorithm specification (Appendix B.1): We expanded the notation and traversal details, including frontier sizes, pruning decisions, and the scope of the logarithmic routing bound.
  4. Additional experiments (Appendix D.5): We added full-model quality–latency evaluations and explicitly distinguished the GPU-oriented fixed-depth implementation from canonical logarithmic traversal.

We appreciate your detailed feedback, which helped us improve the clarity and technical presentation of the manuscript.

Reviewer_jenQOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The authors propose an improvement on the HiP Attention algorithm by changing the way that keys are selected for computing attention. They appear to be selected based on how they hash with some pre-sampled vectors rather than where they land positionally in the sequence.

The authors compare against dense attention and two HiP attention variants, and show mostly consistent improvements in PPL, longbench, and RULER.

Critical strengths
  • The authors show mostly consistent results against two HiP attention variants.
  • The method seems to solve a problem in the ambiguousness of the HiP attention selection method. HiP attention naively partitions keys into blocks base on their position, which might not be ideal if they are not highly self-similar within a block.
Critical weaknesses
  • What is the variable uu that shows up in section 3.2. I do not see it defined anywhere. Section 3.2 is hard to understand without being able to assign a meaning to uu.

  • What is a block Q\mathcal{Q} of? If it is a block of keys, then what is the inner sum in the inline double sum in section 3.3?

  • I find it extremely hard to understand the description and the figures in the text.

    • The figures seem to show that each branch is the same size in figure 1? Is this true. If so, how do we narrow computation as we descend deeper?
    • am I correct in assuming that once a key is classified as being in one of four cells, it then gets subdivided into 4 more cells in the next level of the tree?
Questions for authors

Can you please re-write the method section and the figures to more clearly explain the method? I believe there is something interesting here, but unfortunately I cannot understand what is being presented even after reading the method section multiple times.

3 comments

We thank the reviewer for recognizing the improvements over HiP variants and for the detailed feedback on presentation. We agree that the method would benefit from a more accessible explanation. We clarify the main concepts and retrieval procedure below.

1. Temporal hierarchy versus hash-based summaries.

CarryKV does not replace HiP's temporal partitioning with hash-based retrieval. Both methods organize the original keys into contiguous temporal intervals and progressively refine selected branches.

The difference lies in how a temporal branch is evaluated. Whereas HiP uses a positional representative key, CarryKV uses compact statistics of the keys within that branch to estimate its attention mass.

Hashing is used only to construct the internal statistical representation of a temporal branch. It does not define the retrieval hierarchy or directly select the final keys.

2. Meaning of uu in Section 3.2.

The symbol uu denotes a temporal branch, equivalently the contiguous set of key positions covered by that branch.

Thus, i∈ui\in u means that key ii belongs to the interval, and nun_u is the number of keys it contains. The summation in Eq. (1) runs over the original keys within this temporal branch.

We will restate this definition directly before the equation.

3. Meaning of the query block and double summation in Section 3.3.

The symbol Q\mathcal Q denotes a block of queries sharing remote retrieval indices.

In the joint raw-mass expression, the outer summation over q∈Qq\in\mathcal Q aggregates the queries, while the inner summation over i∈ui\in u aggregates the original keys covered by temporal branch uu.

The resulting quantity is the joint unnormalized attention mass of the branch, not a summation over hash cells. Each query subsequently computes its own attention weights over the selected original K/V.

4. Relationship between the four cells and the four tree children.

These are two distinct concepts.

With the default configuration, each completed parent contains b=4b=4 temporal children. Separately, each node stores m=4m=4 internal cells, with each cell maintaining a key count and sum.

The four cells jointly produce one score for the temporal branch. They are not independently pruned tree nodes, nor are they recursively subdivided into additional hash cells.

A parent summary is constructed by adding corresponding cell statistics from its temporal children.

5. Branch sizes and bounded computation.

The equally sized glyphs in Figure 1 represent fixed-capacity summaries, not equal temporal coverage.

A complete node at level ℓ\ell covers CbℓCb^\ell original keys. Descending one level reduces the temporal span of each child by a factor of bb.

For example, with C=16C=16, b=4b=4, and a beam width of B=2B=2, a 256-key root expands into four 64-key candidates. Retaining two candidates leads to eight 16-key leaf candidates, of which at most two are retained for final expansion.

At each level, only surviving branches are expanded. The candidate frontier contains at most bB+b−1bB+b-1 nodes, including residual roots. Since the number of levels grows logarithmically, routing work remains logarithmic per query block under fixed budgets.

The savings arise from not visiting discarded subtrees, rather than requiring computation to decrease at every level.

6. Presentation improvements.

We will revise the method overview and figures to explicitly show temporal spans, distinguish internal cells from temporal children, and include a complete score–retain–expand example.

We appreciate the reviewer identifying where the current presentation obscures the distinction between branch organization and branch valuation.

Thank you for your response. I look forward to seeing the revised manuscript

Dear Reviewer,

A revised manuscript has been uploaded. We have made several changes to address your concerns:

  1. Method clarification (Sections 3.1–4.3): We clarified the relationship between HiP and CarryKV, explicitly defined temporal branches, query blocks, and joint attention mass, and distinguished summary cells from tree children.
  2. Revised Figures 1–2 and method description: Figure 1 contrasts HiP's center-key valuation with CarryKV's multi-cell scoring and illustrates a concrete pruning example. Figure 2, together with the revised method description, clarifies bottom-up summary construction, branch selection, and retrieval of original K/V.
  3. Algorithm specification (Appendix B.1): We expanded the notation and traversal details, including frontier sizes, pruning decisions, and the scope of the logarithmic routing bound.
  4. Additional experiments (Appendix D.5): We added full-model quality–latency evaluations and explicitly distinguished the GPU-oriented fixed-depth implementation from canonical logarithmic traversal.

We appreciate your detailed feedback, which helped us improve the clarity and technical presentation of the manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.