# HashAttention: Semantic Sparsity for Faster Inference

arXiv: https://arxiv.org/abs/2412.14468 · HTML: https://mlsanity.com/paper/2412.14468/

## Key facts

- Cited by 24 papers in the map (data through 14 Oct 2026).
- Builds on 34 of its 45 references that are in the map.
- First posted on arXiv 19 Dec 2024.

## Builds on (most cited first, 30 of 34)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Mistral 7B](https://mlsanity.com/paper/2310.06825/) (2023)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [SnapKV: LLM Knows What You are Looking for Before Generation](https://mlsanity.com/paper/2404.14469/) (2024)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs](https://mlsanity.com/paper/2310.01801/) (2023)
- [Scissorhands: Exploiting the Persistence of Importance Hypothesis for LLM KV Cache Compression at Test Time](https://mlsanity.com/paper/2305.17118/) (2023)
- [MT-Bench-101: A Fine-Grained Benchmark for Evaluating Large Language Models in Multi-Turn Dialogues](https://mlsanity.com/paper/2402.14762/) (2024)
- [LongT5: Efficient Text-To-Text Transformer for Long Sequences](https://mlsanity.com/paper/2112.07916/) (2021)
- [Retrieval Augmented Generation or Long-Context LLMs? A Comprehensive Study and Hybrid Approach](https://mlsanity.com/paper/2407.16833/) (2024)
- [RetrievalAttention: Accelerating Long-Context LLM Inference via Vector Retrieval](https://mlsanity.com/paper/2409.10516/) (2024)
- [Dive into Deep Learning](https://mlsanity.com/paper/2106.11342/) (2021)
- [MagicPIG: LSH Sampling for Efficient LLM Generation](https://mlsanity.com/paper/2410.16179/) (2024)
- [Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS)](https://mlsanity.com/paper/1405.5869/) (2014)
- [Loki: Low-rank Keys for Efficient Sparse Attention](https://mlsanity.com/paper/2406.02542/) (2024)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [Training-Free Long-Context Scaling of Large Language Models](https://mlsanity.com/paper/2402.17463/) (2024)
- [Squeezed Attention: Accelerating Long Context Length LLM Inference](https://mlsanity.com/paper/2411.09688/) (2024)

## Built on by (most cited first, 24 of 24)

- [Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention](https://mlsanity.com/paper/2502.11089/) (2025)
- [Barbarians at the Gate: How AI is Upending Systems Research](https://mlsanity.com/paper/2510.06189/) (2025)
- [Mixture of Sparse Attention: Content-Based Learnable Sparse Attention via Expert-Choice Routing](https://mlsanity.com/paper/2505.00315/) (2025)
- [Sol-Attn: Accelerating Video Generation Inference via On-the-Fly Attention Sparsification](https://mlsanity.com/paper/2607.24027/) (2026)
- [HATA: Trainable and Hardware-Efficient Hash-Aware Top-k Attention for Scalable Large Model Inference](https://mlsanity.com/paper/2506.02572/) (2025)
- [Trainable Dynamic Mask Sparse Attention](https://mlsanity.com/paper/2508.02124/) (2025)
- [vAttention: Verified Sparse Attention](https://mlsanity.com/paper/2510.05688/) (2025)
- [Adaptive Computation Pruning for the Forgetting Transformer](https://mlsanity.com/paper/2504.06949/) (2025)
- [Overcoming Long-Context Limitations of State-Space Models via Context-Dependent Sparse Attention](https://mlsanity.com/paper/2507.00449/) (2025)
- [SOCKET: SOft Collision Kernel EsTimator for Sparse Attention](https://mlsanity.com/paper/2602.06283/) (2026)
- [CSAttention: Centroid-Scoring Attention for Accelerating LLM Inference](https://mlsanity.com/paper/2604.08584/) (2026)
- [Optimizing Native Sparse Attention with Latent Attention and Local Global Alternating Strategies](https://mlsanity.com/paper/2511.00819/) (2025)
- [PrefixWall: Mitigating Prefix Caching Side Channels in Shared LLM Systems](https://mlsanity.com/paper/2603.10726/) (2026)
- [Sparse Attention as a Range Searching Problem: Towards an Inference-Efficient Index for KV Cache](https://mlsanity.com/paper/2605.06763/) (2026)
- [Positional LSH: Binary Block Matrix Approximation for Attention with Linear Biases](https://mlsanity.com/paper/2605.09472/) (2026)
- [Elastic Threshold Attention: Learned Contextual Sparsity for Long-Context Decoding](https://mlsanity.com/paper/2609.20888/) (2026)
- [Inference Time Context Sparsity: Illusion or Opportunity?](https://mlsanity.com/paper/2605.24168/) (2026)
- [Training-Free Hashing-Based Attention via Binary Principal Components](https://mlsanity.com/paper/2608.04405/) (2026)
- [Beyond Sparse Weights: When Is Attention Compressible?](https://mlsanity.com/paper/2608.21541/) (2026)
- [Self-Indexing Attention for Compression-Compatible Sparse Long-Context LLM Inference](https://mlsanity.com/paper/2609.13205/) (2026)
- [CoWindow Attention: Full Causal Coverage Is a Collective Property](https://mlsanity.com/paper/2609.32704/) (2026)
- [PQ-HSA: Reusing Product-Quantized Scores for Hybrid Sparse-Approximate Attention](https://mlsanity.com/paper/2609.33746/) (2026)
- [The Evolution of Attention in Large Language Models: Mechanisms, Trade-offs, and Emerging Trends](https://mlsanity.com/paper/2609.39661/) (2026)
- [HHR: Hierarchical Hash Retrieval for Efficient LLM Generation](https://mlsanity.com/paper/2610.01230/) (2026)

## Abstract (arXiv)

Leveraging long contexts is crucial for advanced AI systems, but attention computation poses a scalability challenge. While scaled dot-product attention (SDPA) exhibits token sparsity, i.e. only a few pivotal tokens significantly contribute to output, exploiting this sparsity remains challenging. Existing methods either suffer from quality degradation or require substantial additional resources. We show that identifying pivotal tokens is a Maximum Inner Product Search (MIPS) problem. However, existing MIPS solutions are not well-suited for SDPA, as they are not GPU-friendly and often underperform due to the separated query and key distributions. This paper introduces HashAttention, framing pivotal token identification as a recommendation problem. Given a query, HashAttention encodes keys and queries in Hamming space, capturing the required semantic similarity, using learned mapping functions. HashAttention efficiently identifies pivotal tokens for a given query using bitwise operations and computes attention using only these tokens, improving the overall attention efficiency. Trained on generic data, HashAttention reduces tokens used by up to 16× with minimal quality loss, requiring only 32 bits of auxiliary memory per token. Sparsity can be further improved to 32× through task-specific fine-tuning. On A100 GPU, at 32× sparsity, incorporating HashAttention reduces attention latency by up to 4.3× in GPT-FAST and 2.54× in FlashDecode, and achieves up to 3.12× higher throughput for GPT-FAST.