Training-Free Hashing-Based Attention via Binary Principal Components
Daohai Yu, Zhanpeng Zeng, Keyu Chen, Wenhao Li, Zhifeng Shen, Luxi Lin, Ruizhi Qiao, Xing Sun, Rongrong Ji
cs.LG, cs.AI, cs.CL
Submitted: 2026-08-05
Comments: ICML 2026
Code: https://github.com/yudaohai666/BPC
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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
Terminology
Abstract
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.
Sources
- GPT-4 Technical Report
- Training Verifiers to Solve Math Word Problems
- CompressKV: Semantic Retrieval Heads Know What Tokens are Not Important Before Generation
- Transformers are Multi-State RNNs
- HATA: Trainable and Hardware-Efficient Hash-Aware Top-k Attention for Scalable Large Model Inference
- The Llama 3 Herd of Models
- FastDecode: High-Throughput GPU-Efficient LLM Serving using Heterogeneous Pipelines
- Mistral 7B
- Qwen3 Technical Report
- Qwen2.5-1M Technical Report
- $\infty$Bench: Extending Long Context Evaluation Beyond 100K Tokens
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks