HHR: Hierarchical Hash Retrieval for Efficient LLM Generation

Lianjun Liu; Tiantian Zheng; You Huang; Weiqi Yan; Mingte Qiu; Huazhong Liu; Xiaofeng Zhu; Yunshan Zhong

cs.AIOct 1, 2026

HHR: Hierarchical Hash Retrieval for Efficient LLM Generation

Authors: Lianjun Liu, Tiantian Zheng, You Huang, Weiqi Yan, Mingte Qiu, Huazhong Liu, Xiaofeng Zhu, Yunshan Zhong

Organizations: Hainan University, Haikou, China · Xiamen University, Xiamen, China · Zhejiang Normal University, Jinhua, China

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.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

\operatorname{sign}(\cdot)

, together with the corresponding Query-Key logits.

Figure 3 : Distribution of keys before and after applying the learned transformation $R_{h}$ . (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 $R_{h}$ .

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
Model	Method	QA	QA	Summarization	Few-shot	Synthetic	Code	Mean
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.

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
$\lambda_{1}$	$\mathcal{L}_{\mathrm{precision}}$	$0.05$
$\lambda_{2}$	$\mathcal{L}_{\mathrm{align}}$	$0.25$
$\lambda_{3}$	$\mathcal{L}_{\mathrm{orth}}$	$0.02$
$\lambda_{4}$	$\mathcal{L}_{\mathrm{decor}}$	$0.02$
$\lambda_{5}$	$\mathcal{L}_{\mathrm{bal}}$	$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 $\mathcal{L}_{\mathrm{precision}}$	32.06	50.51	47.48	43.35
w/o $\mathcal{L}_{\mathrm{align}}$	31.71	49.87	46.91	42.83
w/o $\mathcal{L}_{\mathrm{orth}}$	32.23	50.82	47.71	43.59
w/o $\mathcal{L}_{\mathrm{decor}}$	32.26	50.78	47.67	43.57
w/o $\mathcal{L}_{\mathrm{bal}}$	32.39	51.07	47.91	43.79

Appendix

Table 7: Ablation study of different loss terms in HHR.

Method	QMSum	RepoBench-P	SAMSum
QUEST	22.52	45.84	41.59
GKR	23.17	46.41	42.22
LHP	23.68	46.99	42.73
HHR	24.34	47.62	43.38

Appendix

Table 8: Stage-wise ablation study of HHR.

Explore similar work

Training-Free Hashing-Based Attention via Binary Principal Components
Aug 5, 2026Daohai Yu, Zhanpeng Zeng, Keyu Chen +6Dynamic Sparse Attention Block Sparse Flash Attention
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.
Hierarchical Sparse Attention Done Right: Toward Infinite Context Modeling
Jul 3, 2026Xiang Hu, Xinyu Wei, Hao Gu +10Efficient Long-Context Inference Dynamic Sparse Attention
Tencent HY Team · ShanghaiTech University · The Hong Kong University of Science and Technology +1
RaBitQCache: Rotated Binary Quantization for KVCache in Long Context LLM Inference
Jun 30, 2026Wenhao Li, Jinhao Dong, Hailin Zhang +3LLM Inference Optimization Dynamic Sparse Attention
School of Information, Renmin University of China, Beijing, China · Peking University, Beijing, China

Aug 5, 2026, cs.LGJ/K move · Enter open · S save

Training-Free Hashing-Based Attention via Binary Principal Components

Daohai Yu, Zhanpeng Zeng, Keyu Chen, Wenhao Li+5

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.

Dynamic Sparse Attention Block Sparse Flash Attention Efficient Long-Context Inference Locality-Sensitive Hashing Training-Free Principal Component Analysis

Open paper AskPDF arXiv

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

\times

over the FlashAttention kernel. Our code is available at https://github.com/yudaohai666/BPC.

Abstract

Explore similar work

Training-Free Hashing-Based Attention via Binary Principal Components

Hierarchical Sparse Attention Done Right: Toward Infinite Context Modeling

RaBitQCache: Rotated Binary Quantization for KVCache in Long Context LLM Inference