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.30x decoding speedup and a 2.83x end-to-end speedup for Llama-3.1-8B-Instruct. The code is publicly available at https://github.com/lianjunl13-sudo/HHR.
Figures & tables
Figure 1 : Overview of Hierarchical Hash Retrieva (HHR).
Figure 2 : Distribution of Hamming distances obtained using a random orthogonal projection followed by sign(⋅) , together with the corresponding Query-Key logits.
Figure 3 : Distribution of keys before and after applying the learned transformation Rh . (a) Original key distribution across 128 dimensions for 64 consecutive keys. (b) The same keys after applying a random orthogonal rotation. (c) The same keys after applying the learned orthogonal matrix Rh .
Figure 4 : Top-10% key recall from layer 25, KV head 4 of Llama-3.1-8B-Instruct.
Model
Method
Single-Doc
Multi-Doc
Summarization
Few-shot
Synthetic
Code
Mean
QA
QA
Llama- 3.1-8B- Instruct
Full Attention
40.56
44.37
29.18
69.28
54.19
50.80
47.51
TopK (Oracle)
40.93
44.33
28.98
69.37
53.53
50.59
47.44
MagicPIG
38.04
43.55
27.46
68.09
53.37
46.94
45.75
SnapKV
31.14
42.49
20.23
58.94
54.17
48.30
41.46
StreamingLLM
14.95
10.37
13.61
32.96
1.25
48.98
19.76
Table 1 : Evaluation results on LongBench.
Model
Method
S1
S2
S3
MK1
MK2
MV
MQ
CWE
FWE
QA1
QA2
Mean
Llama-3.1-8B-Instruct
Full Attention
93.60
100.00
99.80
99.60
86.80
99.30
100.00
37.88
86.00
80.40
61.40
85.89
TopK (Oracle)
98.40
100.00
98.60
99.40
96.00
97.40
99.75
28.26
73.40
76.80
60.80
84.44
StreamingLLM
0.80
1.20
2.00
2.00
1.20
2.50
1.75
0.72
49.07
22.20
25.40
9.89
SnapKV
99.40
95.60
0.00
97.40
18.20
43.95
83.45
10.44
48.27
78.20
61.40
57.85
MagicPIG
79.60
85.60
69.20
88.00
72.40
66.25
68.10
18.52
84.60
70.80
61.00
69.46
Loki
93.80
98.00
99.40
95.00
71.20
97.90
98.15
55.06
58.60
72.40
61.20
81.88
Table 2 : Evaluation results on RULER with a context length of 32K. S1–S3 denote NIAH Single 1–3; MK1–MK2 denote NIAH Multi-key 1–2; MV and MQ denote NIAH Multi-value and NIAH Multi-query; CWE and FWE denote Common Words Extraction and Frequent Words Extraction; QA1 and QA2 denote question answering on SQuAD and HotpotQA, respectively.
Figure 7Figure 8
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Model
Configs
Values
Llama-3.1-8B-Instruct
#Layer
32
#Attention Heads
32
#KV Heads
8
Hidden Size
4096
Max Context Length
131072
Mistral-7B-Instruct
#Layer
32
Appendix
Table 3: Configurations of the models used for evaluation.
Method
Settings
StreamingLLM
Streaming KV cache compression with 4 attention sink tokens and a retained cache ratio of 1.5% .
MagicPIG
Hash-based sparse attention with K=8 , L=40 , 4 sink tokens, and a local window size of 64 , resulting in an effective candidate ratio of approximately 1.5% , comparable to TopK- 1.5% .
Loki
PCA-based Top- k attention with 32 selected channels and a Top- k ratio of 1.5% .
HATA
Hash-based Top- k attention with trained hash weights and a hash length of 128 bits.
HHR (Ours)
Hierarchical hash-based retrieval with geometry-aware key routing and learned hash projection, using 128 -bit hash codes.
Appendix
Table 4: Configurations of the evaluated baseline methods.
Coefficient
Corresponding loss
Value
λ1
Lprecision
0.05
λ2
Lalign
0.25
λ3
Lorth
0.02
λ4
Ldecor
0.02
λ5
Lbal
0.02
Appendix
Table 5: Loss coefficients used in our method.
Model
Method
Easy Avg.
Hard Avg.
Overall
Llama-3.1-8B-Instruct
Full Attention
31.74
28.67
29.84
TopK (Oracle)
29.47
28.89
29.11
HATA
31.90
29.17
30.21
HHR (Ours)
32.25
29.24
30.39
Mistral-7B-Instruct-v0.3
Full Attention
30.36
28.97
29.50
TopK (Oracle)
32.61
27.42
29.40
Appendix
Table 6: Evaluation results on LongBench-v2.
Figure 9 : Comparison of model performance under different candidate ratios.
Figure 10 : Sensitivity analysis of the number of hash bits.
Setting
GovReport
HotpotQA
LCC
Avg.
HHR (Ours)
32.92
51.66
48.49
44.36
w/o Lprecision
32.06
50.51
47.48
43.35
w/o Lalign
31.71
49.87
46.91
42.83
w/o Lorth
32.23
50.82
47.71
43.59
w/o Ldecor
32.26
50.78
47.67
43.57
w/o Lbal
32.39
51.07
47.91
43.79
Appendix
Table 7: Ablation study of different loss terms in HHR.
Long-context large language models (LLMs) are increasingly deployed in real-world applications, yet self-attention remains a major efficiency bottleneck -- especially during decoding -- due to the necessity of repeatedly processing ever-growing key-value (KV) caches. Existing sparse attention reduce computation by attending to fewer KV pairs, but often suffer from substantial accuracy degradation, require additional training, or rely on expensive hashing. In this work, we present BinaryPC, a training-free, data-aware hashing-based sparse attention for long-context LLMs. BinaryPC constructs compact binary hash codes and corresponding hash function by computing binary principal components of data. Unlike Locality-Sensitive Hashing (LSH) with data-independent random projections or learned non-linear hashing methods, BinaryPC constructs binary codes that explicitly preserve the structural information of data without requiring gradient-based training. Comprehensive experiments across multiple model families and long-context benchmarks show that BinaryPC preserves accuracy relative to full attention while achieving superior performance among sparse and hashing-based baselines. On modern GPUs, BinaryPC improves end-to-end decoding throughput by 3.56× over the FlashAttention kernel. Our code is available at https://github.com/yudaohai666/BPC.
Daohai Yu, Zhanpeng Zeng, Keyu Chen +6
Key Laboratory of Multimedia Trusted Perception and Efficient Computing, Ministry of Education of China, Xiamen University, 361005, P.R. China. · Tencent YouTu Lab, Shenzhen, China · Sino-Russian Research Center for Digital Economy.
Scaling modern large language models (LLMs) to long contexts is limited by the quadratic computation cost, and poor length extrapolation of dense attention. Chunk-wise sparse attention offers a promising alternative, but all existing methods fall short of full attention because of their inaccurate chunk selection. We propose Hierarchical Landmark Sparse (HiLS) Attention, a chunk-wise sparse attention mechanism that learns chunk selection end-to-end under the language-modeling (LM) loss. HiLS factorizes attention hierarchically: each query performs attention independently with each retrieved chunk to extract chunk-specific information, and the resulting outputs are fused according to chunk retrieval scores. By incorporating retrieval scores into the forward attention computation, HiLS optimizes them directly with the LM loss, enabling end-to-end retrieval learning and native sparse training. Experimental results show that HiLS-Attention achieves performance comparable to, and in some cases better than, full attention at in-domain context lengths. Meanwhile, HiLS-Attention extrapolates more than 64× the training context length with 90% retrieval accuracy, far beyond full attention. Moreover, existing full-attention models can be converted to HiLS-Attention with lightweight continued pretraining, preserving in-domain performance while acquiring ultra-long-context extrapolation. Together with its sparse KV access and computation, HiLS-Attention breaks the usual efficiency-performance trade-off, enabling long-context LLMs that are both more efficient and more effective on general long-context tasks than their full-attention counterparts.
Xiang Hu, Xinyu Wei, Hao Gu +10
Tencent HY Team · ShanghaiTech University · The Hong Kong University of Science and Technology +1
Long-context Large Language Model inference is severely bottlenecked by the massive Key-Value (KV) cache, yet existing sparse attention methods often suffer from static fixed-budget (Top-k) retrieval or rely on proxy scores that are computationally expensive and biased. To address these limitations, we propose RaBitQCache, a novel sparse attention framework that utilizes randomized rotated binary quantization and high-throughput binary-INT4 arithmetic to efficiently estimate attention weights. Our proxy score serves as an unbiased estimator with a proven error bound, enabling adaptive Top-p retrieval that dynamically adjusts the token budget based on actual attention sparsity. We further implement a hardware-aware system with asynchronous pipelining and lazy updates to mask overhead. Evaluations demonstrate that RaBitQCache significantly accelerates inference and reduces memory I/O while preserving generation quality compared to state-of-the-art baselines. Code is available at https://github.com/Sakuraaa0/RaBitQCache.git.
Wenhao Li, Jinhao Dong, Hailin Zhang +3
School of Information, Renmin University of China, Beijing, China · Peking University, Beijing, China