acceptodds
Under review as a conference paper at ICLR 2027

HHR: Hierarchical Hash Retrieval for Efficient LLM Generation

Abstract

Efficient long-context inference is essential for large language models (LLMs), yet it poses a severe computational bottleneck. Hash-based retrieval offers an efficient alternative by encoding queries and keys into binary codes and using Hamming distance for key selection. However, this leads to a critical mismatch between Hamming distance and attention relevance. Query-Key logits depend jointly on directional similarity and feature magnitudes, whereas hash binarization discards magnitude information, causing both false-positive retrieval of low-logit keys and false-negative omission of high-logit keys. To address these failures, we propose Hierarchical Hash Retrieval (HHR), a coarse-to-fine framework that progressively improves retrieval accuracy through Geometry-Aware Key Routing (GKR) and Learned Hash Projection (LHP). GKR learns a head-wise orthogonal transformation to redistribute feature magnitudes and derive more discriminative page-level logit bounds, enabling effective pruning of low-logit keys while preserving important candidates. LHP then learns a head-wise projection space that aligns Hamming distance with the true Query-Key relevance ranking for fine-grained retrieval. By combining GKR and LHP, HHR suppresses false positives and recovers false negatives, substantially improving the fidelity of hash-based sparse attention. Extensive experiments across diverse LLMs and benchmarks demonstrate that HHR achieves superior performance over existing methods. For example, on LongBench, HHR improves the average score by 1.10 points and, at a context length of 128K, achieves up to a 3.30× decoding speedup and a 2.83× end-to-end speedup for Llama-3.1-8B-Instruct.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Hash, Sparse Attention

Reviews

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

This paper proposes Hierarchical Hash Retrieval (HHR), a learned sparse-attention method for efficient long-context generation. HHR uses Geometry-Aware Key Routing (GKR) for page-level pruning and Learned Hash Projection (LHP) for fine-grained hash retrieval. The method is evaluated on LongBench, RULER, and LongBench-v2, with additional ablation and efficiency experiments.

Critical strengths

1. Well-motivated method design. HHR provides a clear coarse-to-fine framework combining page-level pruning and fine-grained hash retrieval.

2. Interesting analysis of hash-retrieval errors. The paper identifies the mismatch between Hamming distance and QK relevance caused by discarded magnitude information, which provides a reasonable motivation for the proposed method.

Critical weaknesses

1. The empirical evaluation is incomplete and does not sufficiently validate HHR across the intended task settings. The RULER and LongBench evaluations use incomplete benchmark subsets, while most ablation studies are conducted only on a few selected subtasks. In addition, the evaluation is dominated by long-input/short-output workloads and does not include long-generation reasoning tasks such as AIME or MATH-500, which are particularly relevant for decoding-time sparse attention. Together, these limitations make it difficult to assess whether HHR generalizes reliably across tasks and generation regimes.

2. The efficiency and baseline comparisons are not strong enough to substantiate the claimed practical advantage. The paper reports speedups over an unspecified “Dense” baseline without clarifying whether it uses eager attention, SDPA, FlashAttention, etc., and provides little information about the implementation of HHR, batch size, component-wise latency, memory overhead, or batched decoding. Moreover, HHR is a learned sparse-attention method, but it is not compared against recent training-based baselines such as SeerAttention-R [1]. These omissions make it difficult to determine whether HHR offers a clear practical advantage over strong contemporary alternatives.

[1] Gao Y, Guo S, Cao S, et al. Seerattention-r: Sparse attention adaptation for long reasoning[J]. arXiv preprint arXiv:2506.08889, 2025.

Questions for authors

1. Efficiency setup. What implementation is used for the “Dense” baseline in Fig. 7, and how is HHR implemented? Please also clarify the batch size and whether batched decoding is supported.

2. Efficiency breakdown. Can the authors report the latency breakdown of GKR, LHP/hash retrieval, Top-K selection, and sparse attention, as well as the additional memory overhead?

3. Benchmark coverage. Why are only 11 RULER tasks and 16 LongBench datasets reported? Can the authors provide results on the full standard benchmark suites?

4. Ablation coverage. Can the main ablations be reported on the full benchmark, or at least on a fixed representative set of tasks rather than different selected subtasks?

5. Long-generation evaluation. Can the authors evaluate HHR on long-generation reasoning tasks such as AIME or MATH-500?

6. Training-based baselines. Why are recent learned sparse-attention methods such as SeerAttention-R not included in the comparison?

6 comments
AuthorsOpenReview ↗

Response for W1

W1. The empirical evaluation is incomplete and does not sufficiently validate HHR across the intended task settings.

A1. Thank you for the constructive feedback. Below, we clarify the benchmark coverage and report additional experiments on the contributions of GKR and LHP, performance across model sizes, sensitivity to the token budget, and long-generation reasoning.

Evaluation coverage. We evaluate 11 representative subtasks from RULER. HATA likewise reports results on a subset of RULER subtasks. On LongBench, as stated in the manuscript, we evaluate 16 English datasets spanning six categories: single-document QA, multi-document QA, summarization, few-shot learning, synthetic tasks, and code completion. We will explicitly list the evaluated RULER subtasks and LongBench datasets, along with their task categories, in the revised manuscript.

Additional experiments. We use two representative datasets, 2WikiMQA and MultiFieldQA-en, to evaluate the contributions of GKR and LHP, compare HHR with full attention across model sizes, and measure sensitivity to the token retention budget.

1. Contributions of GKR and LHP

We replace the learned transformation matrix RR in GKR or the learned projection matrix WW in LHP with a random matrix while retaining the learned parameters of the other stage. We also evaluate GKR-only and LHP-only variants to assess the contribution of combining the two stages.

Configuration2WikiMQA ↑MultiFieldQA-en ↑Mean ↑
Full HHR (learned RR + learned WW)47.3445.1046.22
Random RR + learned WW44.8243.9044.36
Learned RR + random WW46.7444.3045.52
GKR only45.7142.0343.87
LHP only45.2144.9045.06

Randomizing RR or WW reduces the mean score by 1.86 and 0.70 points, respectively. The ranking of the single-stage variants changes across datasets. Full HHR achieves the highest score on both datasets and improves the mean score by 2.35 points over GKR only and 1.16 points over LHP only. These results support combining page-level routing with token-level retrieval.

2. Performance Across Model Sizes

We compare HHR with full attention (Dense) using Qwen3-4B, Qwen3-8B, and Qwen3-14B.

Model2WikiMQA (Dense / HHR)MultiFieldQA-en (Dense / HHR)
Qwen3-4B43.58 / 43.1450.60 / 50.79
Qwen3-8B42.79 / 42.8447.05 / 46.96
Qwen3-14B54.28 / 54.0142.49 / 42.03

Across all three model sizes, HHR achieves an average score over the two datasets comparable to that of full attention.

3. Sensitivity to the Top-K Retention Ratio

We vary the final token retention ratio across 1%, 2%, 5%, 10%, and 20% and compare HHR with StreamingLLM, SnapKV, Loki, and HATA at each budget.

2WikiMQA

Method1%2%5%10%20%
HHR45.6947.3447.2747.5247.49
StreamingLLM7.2312.6915.5417.6824.35
SnapKV42.6546.0445.6046.9346.70
Loki2.6111.8629.8543.9445.49
HATA44.6945.7445.7346.1846.28

MultiFieldQA-en

Method1%2%5%10%20%
HHR45.5245.3545.1844.7845.49
StreamingLLM14.1516.1920.5523.2529.82
SnapKV32.4835.0638.7341.4342.95
Loki8.5020.7641.8844.1144.96
HATA42.2743.4244.6845.1844.78

HHR achieves the highest score in 9 of the 10 dataset–budget combinations. At both the 1% and 2% retention ratios, it outperforms all four baselines on both datasets.

4. Long-Generation Reasoning

Our original long-context experiments primarily cover long inputs with short outputs. To examine sparse attention during long reasoning trajectories, we use Qwen3-4B on MATH-500, AIME 2024, and AIME 2025. These benchmarks typically have short prompts, but the model can generate substantially longer intermediate reasoning sequences. For this evaluation, we use a fixed budget of 2K KV tokens during decoding, following the budget setting used by SeerAttention-R.

MethodMATH-500 ↑AIME 2024 ↑AIME 2025 ↑
Dense93.9371.2566.41
SeerAttention-R92.2055.4245.73
HHR92.2562.4050.21

Results. HHR and SeerAttention-R achieve similar scores on MATH-500 (92.25% vs. 92.20%). With the same 2K decoding-time attention budget, HHR scores 6.98 and 4.48 percentage points higher than SeerAttention-R on AIME 2024 and AIME 2025, respectively. The largest gap between HHR and full attention is 16.20 percentage points on AIME 2025.

AuthorsOpenReview ↗

Response for W2

W2. The efficiency and baseline comparisons are not strong enough to substantiate the claimed practical advantage.

A2. We thank the reviewer for the feedback. We clarify the Dense baseline implementation, provide additional single-layer and whole-model timing comparisons with HATA, and include SeerAttention-R as a learned sparse-attention baseline on six LongBench datasets.

1. Dense baseline and implementation. The Dense baseline in the original manuscript uses Eager Attention. We select HATA as a representative learned hash-based retrieval method and use its official kernels. We benchmark Dense, HATA, and HHR in vLLM under the same hardware and request configurations.

2. Single-layer and whole-model efficiency. We benchmark single-layer decoding with Llama-2-7B on an RTX6000D GPU using a 32K-token input, a batch size of 8, and FP16 precision. The sparse methods use 128-bit hashes and a token budget of approximately 1.5%.

MethodDecode latency (ms/step) ↓Speedup over Dense ↑
Dense3.75721.000×
HATA1.15273.259×
HHR0.90594.147×

HHR supports batched decoding when requests share the same configuration and achieves a 1.272× single-layer decoding speedup over HATA.

For the whole-model evaluation, we use Llama-2-7B-32K-Instruct on an RTX6000D GPU with FP16 precision, a batch size of 1, and a page size of 128. We run one warm-up request and one timed request per configuration.

Input / Output lengthMethodTime to first decode (s) ↓Decode time (s) ↓End-to-end time (s) ↓Decode speedup ↑End-to-end speedup ↑
36K / 3.6KDense8.15399.821107.9741.000×1.000×
HATA8.18559.88168.0671.667×1.586×
HHR8.18258.07766.2591.719×1.630×
72K / 7.2KDense26.032309.875335.9071.000×1.000×
HATA26.078139.874165.9522.215×2.024×
HHR26.068137.066163.1342.261×2.059×

In these two single-request measurements, HHR achieves end-to-end speedups of 1.630× and 2.059× over Dense, comparable to HATA's 1.586× and 2.024×, respectively. 3. Comparison with SeerAttention-R. We evaluate a decoding adaptation of SeerAttention-R on six representative LongBench datasets. HHR and Oracle Top-K both use a 1.5% retrieval budget.

MethodNarrativeQA ↑2WikiMQA ↑QMSum ↑TREC ↑PassageRetrieval-en ↑LCC ↑
Dense30.0146.7025.3072.5099.5052.48
Oracle Top-K29.7146.2025.5272.5099.5051.91
SeerAttention-R28.1146.0823.7870.0099.2549.76
HHR30.8347.3424.3473.0099.0050.49

HHR outperforms SeerAttention-R on five of the six datasets and achieves the highest scores among the evaluated methods on NarrativeQA, 2WikiMQA, and TREC. Response A1 also reports long-generation reasoning results on MATH-500 and AIME.

AuthorsOpenReview ↗

Response for Q1-Q6

Thank you for these detailed questions. We will incorporate the implementation details and supplementary results below into the revised manuscript.

Q1. Efficiency setup.

A1. The Dense baseline in Fig. 7 uses eager attention. HHR performs the same attention computation over the KV entries selected by its two-stage retrieval pipeline. Both retrieval stages use custom CUDA operators to accelerate retrieval and reduce intermediate buffer allocations. The results in Fig. 7 were obtained with a batch size of 1. HHR also supports homogeneous batched decoding with a batch size greater than 1.

Q2. Efficiency breakdown.

A2. We thank the reviewer for this suggestion. We provide additional whole-model and single-layer benchmarks to quantify HHR’s decoding latency and GPU memory usage relative to HATA.

Whole-model evaluation. In our comparison, HATA uses its official CUDA kernels, and HHR uses custom CUDA kernels that we implemented. We benchmark Dense, HATA, and HHR with Llama-2-7B-32K-Instruct on the same RTX 6000 GPU in FP16, using a batch size of 1 and matched input and output lengths. All speedups are relative to Dense.

MethodPrefill time (s) ↓Decode time (s) ↓End-to-end time (s) ↓Decode speedup ↑End-to-end speedup ↑GPU memory (GiB) ↓
Dense8.15399.821107.9741.000×1.000×50.81
HATA8.18554.88163.0671.819×1.712×53.14
HHR8.18253.07761.2591.881×1.763×53.38

Single-layer evaluation. We benchmark single-layer decoding with Llama-2-7B on an RTX 6000 GPU in FP16, using a 32K-token input and a batch size of 8. HHR and HATA both use 128-bit hashes and a token budget of approximately 1.5%.

MethodDecode latency (ms/step) ↓Speedup over Dense ↑Peak GPU memory (GiB) ↓
Dense3.75721.000×4.88
HATA1.15273.259×5.08
HHR0.90594.147×5.11

With our custom CUDA kernels, HHR achieves lower decoding latency than HATA in both benchmarks with comparable GPU memory usage. HHR uses only 0.24 GiB more GPU memory in the whole-model benchmark and 0.03 GiB more peak GPU memory in the single-layer benchmark. HHR also achieves higher accuracy than HATA in the comparisons reported in Tables 1 and 2.

Q3. Benchmark coverage.

A3. We evaluate 11 representative RULER subtasks. HATA also reports results on a subset of RULER. Our LongBench evaluation covers 16 English datasets across six task categories, including single-document question answering, multi-document question answering, summarization, few-shot learning, synthetic tasks, and code completion.

Q4. Ablation coverage.

A4. We conduct the main supplementary ablations on two representative datasets, 2WikiMQA and MultiFieldQA-en, and use the same samples across configurations. See W1 (A1) for the experimental settings and results.

Q5. Long-generation evaluation.

A5. We added long-generation reasoning evaluations on MATH-500, AIME 2024, and AIME 2025. See W2 (A2) for the evaluation settings and results.

Q6. Training-based baselines.

A6. Our original comparison of learned sparse-attention methods focused on trainable hashing approaches such as HATA. SeerAttention-R uses learned block-level gating. We have extended the evaluation to include a direct comparison with SeerAttention-R. See W2 (A2) for the results.

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

This paper proposes HHR, a coarse-to-fine retrieval framework for sparse attention in long-context LLM inference. GKR learns an orthogonal transformation to improve page-level pruning, while LHP learns a projection for binary token retrieval within the retained pages. Experiments on LongBench and RULER benchmark show accuracy improvement over existing sparse attention baselines. The paper also reports up to 3.30× decoding and 2.83× end-to-end speedups over full attention at 128K context length.

Critical strengths
  • The paper addresses an important problem: improving retrieval quality under tight sparse attention budgets.
  • The coarse-to-fine design is well motivated. GKR provides a method to adapt page-level bounds without changing exact attention logits.
  • The evaluation covers multiple model families and long-context benchmarks.
Critical weaknesses
  • The novelty relative to existing learned-hashing methods is insufficiently established. HashAttention [1] already learns binary representations for important-token retrieval, and Spotlight Attention [2] explicitly optimizes top-k versus non-top-k separation. Although HATA is included, direct comparisons with these closely related methods are missing.
  • The efficiency evaluation only compares HHR against full attention. Without runtime comparisons against competitive sparse-attention baselines, the reported speedups do not establish a comparative efficiency advantage.
  • Accuracy and efficiency are not evaluated jointly at the headline operating points. RULER accuracy is reported at 32K, while the strongest speedups occur at 64K and 128K. It remains unclear whether the reported quality retention and acceleration hold simultaneously.
  • The training and calibration protocols are insufficiently specified to assess reproducibility and comparability. In particular, it is unclear whether HHR and HATA use comparable training data, optimization budgets, and tuning effort. HHR’s additional calibration and tuning requirements should also be clarified when comparing with training-free methods.
  • The models evaluated are relatively small. It is questionable whether the proposed solution performs well in larger models.

[1] Desai A, Yang S, Cuadron A, et al. Hashattention: Semantic sparsity for faster inference[J]. arXiv preprint arXiv:2412.14468, 2024.

[2] Li W, Zhang Y, Luo G, et al. Spotlight attention: Towards efficient llm generation via non-linear hashing-based kv cache retrieval[J]. Advances in Neural Information Processing Systems, 2025

Questions for authors
  1. How does HHR compare with HashAttention and Spotlight Attention under comparable training and retrieval budgets?
  2. What calibration data, optimization schedules, and tuning budgets are used for HHR and HATA?
  3. How does HHR’s latency compare with competitive sparse baselines when all routing, selection, and cache-update costs are included?
  4. Can accuracy and latency be reported jointly at 64K and 128K using the same model and retrieval configurations?
7 comments
AuthorsOpenReview ↗

Response for W1-W3

We sincerely thank the reviewer for the constructive feedback and for the encouraging comments on our HHR, including remarks on important problem, well motivated, and evaluation covering multiple model families and long-context benchmarks. The raised issues are addressed below.


W1. The novelty relative to existing learned-hashing methods is insufficiently established. HashAttention [1] already learns binary representations for important-token retrieval, and Spotlight Attention [2] explicitly optimizes top-k versus non-top-k separation. Although HATA is included, direct comparisons with these closely related methods are missing.

A1. Thank you! We select HATA as our primary competitor since it is the strongest hash-based method currently, and we use its official CUDA kernels to ensure fair comparison.

Existing binary hashing approaches primarily approximate attention relevance through hash similarity, which may lose magnitude information and lead to retrieval errors. To address this limitation, HHR introduces a complementary two-stage framework. First, GKR constructs magnitude-sensitive page-level logit upper bounds using unnormalized keys, enabling coarse-grained candidate selection. Subsequently, LHP learns hash projections aligned with the original Query–Key relevance ranking for fine-grained retrieval.


W2. The efficiency evaluation only compares HHR against full attention. Without runtime comparisons against competitive sparse-attention baselines, the reported speedups do not establish a comparative efficiency advantage.

A2. We thank the reviewer for this suggestion. Both Spotlight Attention and HATA employ hashing-based sparse attention. To provide a direct and reproducible efficiency comparison, we conducted additional experiments against HATA, a representative learned-hashing baseline with optimized CUDA kernels.

We use HATA’s official configuration and optimized CUDA implementation under identical hardware and evaluation settings. Whole-model experiments are conducted using Llama-2-7B-32K-Instruct on RTX6000 GPUs with FP16 precision and batch size 1, covering long-context generation workloads.

MethodPrefill (s)Decode (s)E2E (s)Dec. SpeedupE2E SpeedupMemory
Dense8.15399.821107.9741.000×1.000×50.81 GiB
HATA8.18554.88163.0671.819×1.712×53.14 GiB
HHR8.18253.07761.2591.881×1.763×53.38 GiB

Compared with Dense Attention, HHR achieves 1.881× decoding speedup and 1.763× end-to-end speedup. Compared with HATA, HHR achieves comparable inference efficiency, with slightly lower decoding latency (3.29%) and end-to-end latency (2.87%), at the cost of only 0.24 GiB additional peak memory. Moreover, as shown in Tables 1 and 2, HHR achieves better accuracy than HATA.


W3. Accuracy and efficiency are not evaluated jointly at the headline operating points. RULER accuracy is reported at 32K, while the strongest speedups occur at 64K and 128K. It remains unclear whether the reported quality retention and acceleration hold simultaneously.

A3. We thank the reviewer for highlighting this concern. We agree that evaluating accuracy and efficiency at matched context lengths is important for assessing practical performance.

Our existing experiments report both accuracy and efficiency at the 32K context length. On RULER-32K with Llama-3.1-8B-Instruct, HHR achieves an average accuracy of 85.05, compared with 85.89 for Full Attention. We also report 1.28× decoding speedup and 1.88× end-to-end speedup at the same model scale and context length.

To further address this concern, we conducted additional accuracy evaluations on RULER at 64K and 128K context lengths, alongside corresponding efficiency measurements. The results are summarized below:

TaskContext LengthDenseHHR
MV64K93.7591.25
MV128K91.0088.50
MQ64K98.2594.75
MQ128K97.2595.75

Under the same evaluation settings, HHR achieves 1.35× and 1.48× speedups over Dense Attention at 64K and 128K, respectively.

These results demonstrate that HHR maintains competitive accuracy at longer context lengths while providing substantial inference acceleration, further supporting its effectiveness beyond the original 32K evaluation.


AuthorsOpenReview ↗

Response for W4-W5

W4. The training and calibration protocols are insufficiently specified to assess reproducibility and comparability. In particular, it is unclear whether HHR and HATA use comparable training data, optimization budgets, and tuning effort. HHR’s additional calibration and tuning requirements should also be clarified when comparing with training-free methods.

A4. We thank the reviewer for this suggestion. For efficiency comparisons, we adopt HATA’s official configuration and optimized CUDA kernels under identical hardware and evaluation settings to ensure fairness.

HHR only requires offline training of GKR and LHP parameters, without fine-tuning the original LLM. On a single NVIDIA A800 GPU, the cumulative training time for two HHR configurations is approximately 50 minutes, compared with approximately 30 minutes for HATA in our measurements.

Unlike training-free methods, HHR requires additional one-time offline calibration. However, no retraining is required during inference, and this offline cost is excluded from the reported inference speedups. We will further clarify the training configurations, calibration requirements, and computational costs in the revised manuscript to improve transparency and reproducibility.


W5. The models evaluated are relatively small. It is questionable whether the proposed solution performs well in larger models.

A5. We thank the reviewer for this valuable suggestion. Due to limited computational resources, our original experiments did not sufficiently evaluate the scalability of HHR to larger models. To address this concern, we have conducted additional experiments on Qwen3-32B to further investigate the generalization capability of HHR at larger model scales.

Under a 1.5% Top-K token budget, HHR maintains performance close to Full Attention on Qwen3-32B. The results are summarized below:

Method2WikiMQA ↑TREC ↑
Dense54.0567.50
HHR53.9268.00

As shown above, HHR achieves a score only 0.13 points lower than Full Attention on 2WikiMQA, while outperforming it by 0.50 points on TREC. These results demonstrate that HHR maintains near-Full-Attention task performance even when scaling to 32B parameters under a highly constrained token budget, providing further evidence of its generalization capability across model scales.


AuthorsOpenReview ↗

Response for Q1-Q4

Q1. How does HHR compare with HashAttention and Spotlight Attention under comparable training and retrieval budgets?

A1. We thank the reviewer for this question. Previously, due to the substantial training cost of Spotlight Attention and our limited computational resources at that time, we were unable to complete its reproduction. To further address the reviewer's concern, we selected six representative datasets from different LongBench categories and compared HHR with Spotlight Attention and HashAttention under the same 1.5% Top-K retrieval budget. The results are summarized below:

MethodNarrativeQA2WikiMQAQMSumTRECPassageRetrieval-enLCC
Dense30.0146.7025.3072.5099.5052.48
Oracle Top-K29.7146.2025.5272.5099.5051.91
HashAttention26.6242.7324.7268.0098.0050.50
Spotlight Attention28.5145.7624.7272.0099.0049.02
HHR30.8345.5224.3473.0099.0050.49

Under the same retrieval budget, HHR outperforms Spotlight Attention and HashAttention on three and four of the six datasets, respectively, demonstrating the effectiveness of our proposed method.


Q2. What calibration data, optimization schedules, and tuning budgets are used for HHR and HATA?

A2. We thank the reviewer for this question. For HATA, we follow its official training configuration. HHR uses the same calibration dataset as HATA but adopts different optimization objectives. Specifically, HHR employs the AdamW optimizer for 20 epochs, with a learning rate of 5e-5 and weight decay of 1e-5. On a single NVIDIA A800 GPU, the cumulative training time for two HHR configurations is approximately 50 minutes, compared with approximately 30 minutes for HATA in our measurements. HHR requires only one-time offline optimization without fine-tuning the original LLM, and introduces no additional training overhead during inference. We will further clarify these training configurations and computational costs in the revised manuscript.


Q3. How does HHR's latency compare with competitive sparse baselines when all routing, selection, and cache-update costs are included?

A3. We thank the reviewer for this question. Please refer to our detailed response in A2 of the Critical Weaknesses, where we provide additional end-to-end efficiency comparisons with HATA under identical hardware and evaluation settings, accounting for the overall inference pipeline.


Q4. Can accuracy and latency be reported jointly at 64K and 128K using the same model and retrieval configurations?

A4. We thank the reviewer for this question. Please refer to our detailed response in A3 of the Critical Weaknesses, where we provide additional accuracy and efficiency evaluations at both 64K and 128K context lengths.


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

This paper proposes HHR to accelerate long-context generation for large language models. It first uses GKR to filter out historically less important keys at the page level, then leverages hash codes learned via LHP to select a small subset of keys from the remaining candidates for attention computation. The method requires training additional matrices for retrieval, but no fine-tuning of the original language model. The authors evaluate three models on LongBench and RULER, and report speedups for long-context generation.

Critical strengths
  • The problem is well-motivated. Hash codes enable fast lookup but discard magnitude information, while true attention scores depend on both direction and magnitude of query-key pairs. The paper clearly articulates this mismatch.

  • The two-stage retrieval design is sensible. GKR narrows down the search space first, followed by fine-grained token selection with LHP. The learned orthogonal transformation improves page-level estimation accuracy while preserving the original query–key dot product.

  • The empirical results are reasonably convincing. HHR outperforms the other sparse methods compared in the paper across three models on LongBench, and ablation studies validate the individual contributions of both components. Under a 128K context window, the paper reports a 3.30× decoding speedup relative to full attention.

Critical weaknesses
  • The claim of resolving magnitude loss is overstated. LHP ultimately computes hash codes from the sign of linearly projected vectors: two keys pointing in the same direction but with different magnitudes will produce identical hashes. GKR may help distinguish them at the page level, but LHP itself cannot tell them apart if they reside within the same retained page.

  • Keys discarded in the first stage cannot be recovered in the second. While page-level scores serve as an upper bound for dot products, selection is still constrained by the candidate budget. The paper should separately report how many truly important keys are dropped by GKR versus LHP, to pinpoint the source of errors.

  • Efficiency comparisons are incomplete. The reported 3.30× speedup is measured against full attention. For a work focused on efficient generation, I would like to see latency and memory comparisons against prior sparse methods such as HATA and MagicPIG under identical hardware and generation settings, alongside the overhead of training and maintaining the extra index structures.

  • The “near full attention” behavior does not hold universally. For instance on RULER with Mistral-7B, HHR reaches 76.23 while full attention achieves 83.26, leaving a roughly 7-point gap. The authors should more clearly identify which tasks suffer the largest performance degradation.

Questions for authors
  1. With the final candidate budget set to roughly 30%, what fraction of the true top-K keys are retained by GKR, and how many are subsequently lost after LHP filtering? Can these numbers be broken down by model, layer, and task?
  2. For keys sharing the same direction but with substantially different magnitudes, which stage of HHR is responsible for distinguishing them? What happens if these keys fall into the same page?
  3. How exactly is the page selection threshold or Top-B budget determined? How do different page sizes and candidate ratios affect recall and speed?
  4. Under matched hardware, input length, output length, and batch size, what are the end-to-end latency and peak memory usage of HHR compared with other sparse attention approaches?

I appreciate the motivation and empirical results of this work, but more direct mechanistic analysis and fair, comprehensive efficiency comparisons are needed. I would consider raising my score if the authors provide these missing pieces of evidence.

7 comments
AuthorsOpenReview ↗

Response for W1-W3

We sincerely thank the reviewer for the constructive feedback and for the encouraging comments on our HHR, including remarks on well-motivated, sensible, and convincing empirical results. The raised issues are addressed below.


W1. The claim of resolving magnitude loss is overstated. LHP ultimately computes hash codes from the sign of linearly projected vectors: two keys pointing in the same direction but with different magnitudes will produce identical hashes. GKR may help distinguish them at the page level, but LHP itself cannot tell them apart if they reside within the same retained page.

(A1). We thank the reviewer for this important point. LHP cannot distinguish keys of different magnitudes from sign hashes, even within the same retained page. This is an inherent limitation of sign hashing.

We would like to clarify that we do not claim that LHP recovers magnitudes from hash codes. Our claim is narrower: GKR performs magnitude-aware page-level routing before LHP, mitigating magnitude-loss-induced retrieval errors under a fixed candidate budget.

Specifically, GKR uses page-level logit upper bounds with a logit-preserving orthogonal transformation to reduce the risk of excluding pages containing high-magnitude, attention-relevant keys. LHP then retrieves within the retained pages. As shown in Table 8, GKR alone yields consistent gains over QUEST (0.65/0.57/0.63 gains on QMSum/RepoBench-P/SAMSum), confirming the contribution of GKR's magnitude-aware page routing.

To the best of our knowledge, our HHR is the first LLM sparse attention framework to explicitly incorporate magnitude information into hash-based KV retrieval.

We will revise all related claims and explicitly discuss the same-page limitation.


W2. Keys discarded in the first stage cannot be recovered in the second. While page-level scores serve as an upper bound for dot products, selection is still constrained by the candidate budget. The paper should separately report how many truly important keys are dropped by GKR versus LHP, to pinpoint the source of errors.

(A2). We thank the reviewer for this suggestion. We conducted an experiment on NarrativeQA using Llama-3.1-8B-Instruct, and the results confirm that both stages contribute to the recall loss: with a 30% candidate budget, GKR retains 66.20% of the exact Top-KK keys (losing 33.80%), and LHP subsequently achieves a 42.08% final recall (losing an additional 24.12%).

Crucially, despite these budget-induced losses, HHR preserves the most attention-relevant information, achieving a 29.83 F1 score (vs. 30.1 for Full Attention).


W3. Efficiency comparisons are incomplete. The reported 3.30× speedup is measured against full attention. For a work focused on efficient generation, I would like to see latency and memory comparisons against prior sparse methods such as HATA and MagicPIG under identical hardware and generation settings, alongside the overhead of training and maintaining the extra index structures.

(A3). Thank you! We select HATA as our primary competitor since it is the strongest hash-based method currently, and we use its official CUDA kernels to ensure fair comparison.

1. Single-layer:

We benchmark single-layer decoding using Llama-2-7B (on RTX6000 GPUs) with a 32K input length, batch size 8, FP16 precision, 128-bit hashes, and a ~1.5% token budget. As shown below, HHR achieves a 4.148× speedup over Dense and a further 1.272× speedup over HATA with negligible extra memory (5.11G vs. 5.08G).

MethodDecode (ms/step) ↓\downarrowSpeedupMemory
Dense3.75721.000$\times$4.88G
HATA1.15273.260$\times$5.08G
HHR0.90594.148$\times$5.11G

2. Whole-model:

We evaluate Llama-2-7B-32K-Instruct on RTX6000 GPUs (FP16, batch size 1). The input lengths are 36K and 72K tokens, with fixed output lengths of 3.6K and 7.2K. HHR achieves the best speedup and very close memory usage.

MethodPrefill (s)Decode (s)E2E (s)Dec. SpeedupE2E SpeedupMemory
Dense8.15399.821107.9741.000$\times$1.000$\times$50.81G
HATA8.18554.88163.0671.819$\times$1.712$\times$53.14G
HHR8.18253.07761.2591.881$\times$1.763$\times$53.38G

Training and Index Overhead. The training time of GKR and LHP is only 18.93 and 28.45 minutes (Fig. 5), incurring minimal training overhead. The extra index structures are extremely lightweight: as shown in the whole-model results above, the extra memory is only 0.24G, incurring just 0.45% extra memory overhead compared to HATA.

AuthorsOpenReview ↗

Response for W4, Q1-Q4

W4. The “near full attention” behavior does not hold universally. For instance, on RULER with Mistral-7B, HHR reaches 76.23 while full attention achieves 83.26, leaving a roughly 7-point gap. The authors should more clearly identify which tasks suffer the largest performance degradation.

(A4). We thank the reviewer for pointing out this limitation. We agree that our original claim was over-generalized. It primarily holds for LongBench (Section 4.2). We will revise the manuscript to clarify this claim.

Specifically, we identify that the degradation on RULER is mainly concentrated in three tasks: CWE, MK2, and MV, where the extreme 1.5% Top-K budget becomes the primary bottleneck. (Notably, as shown in Table 2, even the perfect Oracle Top-K at a 1.5% budget suffers an ~8-point drop on MK2). To verify this, we additionally conducted experiments on these tasks by increasing the Top-K budget to 10%. The results are compared below:

TaskFull AttentionHHR (1.5%, Original)HHR (10%, New)
CWE73.1853.5672.62
MK284.6064.8083.80
MV96.4087.3096.25

Compared with the original 1.5% results, the new 10% results show substantial improvements on CWE (+19.06), MK2 (+19.00), and MV (+8.95), reducing their gaps to Full Attention to within 0.80 points. These findings suggest that the aggressive Top-K budget, rather than the HHR mechanism itself, contributes substantially to the observed performance degradation. We will add a discussion of this task-specific gap and the trade-off with aggressive sparsity in the revised paper.


Q1. With the final candidate budget set to roughly 30%, what fraction of the true top-K keys are retained by GKR, and how many are subsequently lost after LHP filtering? Can these numbers be broken down by model, layer, and task?

(A5). We thank the reviewer for this suggestion. As discussed in (A2), we provide the breakdown of Top-KK key retention. For example, using NarrativeQA and Llama-3.1-8B-Instruct with a 30% candidate budget, GKR retains 66.20% of the global exact Top-KK keys. After LHP selects the final 1.5% of tokens, the recall reaches 42.08%, corresponding to losses of 33.80% (GKR) and 24.12% (LHP), respectively.

In addition, we conducted experiments using Llama-3.1-8B-Instruct on PG-19. Similarly, GKR retains 63.65% of the exact Top-KK keys, and LHP achieves a final recall of 35.71%, corresponding to losses of 36.35% (GKR) and 27.94% (LHP), respectively.

Owing to the limited time and resources available for the rebuttal, we are able to provide only the results above currently. Additional results (numbers will be broken down by model, layer, and task) will be included in the revised paper. We kindly ask for the reviewer's understanding.


Q2. For keys sharing the same direction but with substantially different magnitudes, which stage of HHR is responsible for distinguishing them? What happens if these keys fall into the same page?

(A6). GKR is responsible for distinguishing them at the page level. If two same-direction keys with different magnitudes fall into different pages, the page containing the high-magnitude key will yield a larger magnitude-sensitive upper bound and is more likely to be retained.

However, as discussed in (A1), if they fall into the same retained page, neither GKR (which operates at the page level) nor LHP (which relies on sign hashing) can distinguish them. This is a fundamental limitation of sign-based hashing.

To the best of our knowledge, HHR is the first framework to incorporate magnitude information into hash-based KV retrieval (overlooked by prior methods) via GKR. In future work, we will explore token-level magnitude-aware mechanisms to further address this within-page limitation.


Q3. How exactly is the page selection threshold or Top-B budget determined? How do different page sizes and candidate ratios affect recall and speed?

(A7). Threshold / Top-B Determination. The page selection threshold chc_h is determined to retain the Top-30% candidate pages. The final Top-KK budget (1.5%) follows common evaluation settings for fair comparison.

Effect of Page Size. We use a page size of 32. A smaller page size yields tighter bounds and higher recall but increases the number of pages, leading to higher overhead. Conversely, larger pages reduce overhead but produce looser bounds, causing lower recall. We find page size 32 to be the optimal balance.

Effect of Candidate Ratio. Increasing the candidate ratio directly improves the intermediate recall but increases the computation overhead for subsequent LHP. As shown in Appendix Fig. 9, 30% provides a favorable accuracy-efficiency trade-off.


Q4. Under matched hardware, input length, output length, and batch size, what are the end-to-end latency and peak memory usage of HHR compared with other sparse attention approaches?

Please see our response in (A3).

Thank you for the clarifications and additional experiments.

W1&Q2

Thank you for explicitly acknowledging the same-page limitation. This clarification addresses my concern. Please incorporate the narrower claim and this limitation into the manuscript.

W2&Q1

The stage-wise recall breakdown clarify the contributions of GKR and LHP to retrieval loss and address my main concern. Please include this analysis and its implications in the revised manuscript.

W3 & Q4

I still have a few remaining questions. The authors report the speed ratio between HHR and HATA, but the corresponding performance metrics are missing. Using the same model and retrieval configuration, at comparable context lengths is necessary. If matching results are already available, please point to them; otherwise, results on a representative task would help establish the accuracy–latency trade-off.

In the whole-model table, two context lengths are listed, yet only one set of results is provided. Are these values averaged across the two lengths?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.