# HyperAttention: Long-context Attention in Near-Linear Time

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

## Key facts

- Cited by 85 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 40 references that are in the map.
- First posted on arXiv 9 Oct 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [End-to-End Object Detection with Transformers](https://mlsanity.com/paper/2005.12872/) (2020)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting](https://mlsanity.com/paper/2012.07436/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNet](https://mlsanity.com/paper/2101.11986/) (2021)
- [GLM: General Language Model Pretraining with Autoregressive Blank Infilling](https://mlsanity.com/paper/2103.10360/) (2021)
- [Textbooks Are All You Need II: phi-1.5 technical report](https://mlsanity.com/paper/2309.05463/) (2023)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [LongNet: Scaling Transformers to 1,000,000,000 Tokens](https://mlsanity.com/paper/2307.02486/) (2023)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [SMYRF: Efficient Attention using Asymmetric Clustering](https://mlsanity.com/paper/2010.05315/) (2020)
- [Kernel Density Estimation through Density Constrained Near Neighbor Search](https://mlsanity.com/paper/2011.06997/) (2020)
- [ViTALiTy: Unifying Low-rank and Sparse Approximation for Vision Transformer Acceleration with a Linear Taylor Attention](https://mlsanity.com/paper/2211.05109/) (2022)
- [Learning the Positions in CountSketch](https://mlsanity.com/paper/2007.09890/) (2020)
- [Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling](https://mlsanity.com/paper/2007.03927/) (2020)
- [Heavy hitters via cluster-preserving clustering](https://mlsanity.com/paper/1604.01357/) (2016)
- [Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time](https://mlsanity.com/paper/2202.04515/) (2022)

## Built on by (most cited first, 30 of 85)

- [Efficient Large Language Models: A Survey](https://mlsanity.com/paper/2312.03863/) (2023)
- [SeerAttention: Learning Intrinsic Sparse Attention in Your LLMs](https://mlsanity.com/paper/2410.13276/) (2024)
- [Model Compression and Efficient Inference for Large Language Models: A Survey](https://mlsanity.com/paper/2402.09748/) (2024)
- [Human-inspired Episodic Memory for Infinite Context LLMs](https://mlsanity.com/paper/2407.09450/) (2024)
- [SampleAttention: Near-Lossless Acceleration of Long Context LLM Inference with Adaptive Structured Sparse Attention](https://mlsanity.com/paper/2406.15486/) (2024)
- [Tensor Product Attention Is All You Need](https://mlsanity.com/paper/2501.06425/) (2025)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [Training Tensor Attention Efficiently: From Cubic to Almost Linear Time](https://mlsanity.com/paper/2405.16411/) (2024)
- [HashAttention: Semantic Sparsity for Faster Inference](https://mlsanity.com/paper/2412.14468/) (2024)
- [Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time](https://mlsanity.com/paper/2408.13233/) (2024)
- [SubGen: Token Generation in Sublinear Time and Memory](https://mlsanity.com/paper/2402.06082/) (2024)
- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [Scaling TabPFN: Sketching and Feature Selection for Tabular Prior-Data Fitted Networks](https://mlsanity.com/paper/2311.10609/) (2023)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [L-MTP: Leap Multi-Token Prediction Beyond Adjacent Context for Large Language Models](https://mlsanity.com/paper/2505.17505/) (2025)
- [What Can We Learn from State Space Models for Machine Learning on Graphs?](https://mlsanity.com/paper/2406.05815/) (2024)
- [Locality-Sensitive Hashing-Based Efficient Point Transformer with Applications in High-Energy Physics](https://mlsanity.com/paper/2402.12535/) (2024)
- [NoMAD-Attention: Efficient LLM Inference on CPUs Through Multiply-add-free Attention](https://mlsanity.com/paper/2403.01273/) (2024)
- [A Training-free Sub-quadratic Cost Transformer Model Serving Framework With Hierarchically Pruned Attention](https://mlsanity.com/paper/2406.09827/) (2024)
- [Addax: Utilizing Zeroth-Order Gradients to Improve Memory Efficiency and Performance of SGD for Fine-Tuning Language Models](https://mlsanity.com/paper/2410.06441/) (2024)
- [Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolation](https://mlsanity.com/paper/2502.00500/) (2025)
- [Streaming Attention Approximation via Discrepancy Theory](https://mlsanity.com/paper/2502.07861/) (2025)
- [Inference-time sparse attention with asymmetric indexing](https://mlsanity.com/paper/2502.08246/) (2025)
- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [BUZZ: Beehive-structured Sparse KV Cache with Segmented Heavy Hitters for Efficient LLM Inference](https://mlsanity.com/paper/2410.23079/) (2024)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [xT: Nested Tokenization for Larger Context in Large Images](https://mlsanity.com/paper/2403.01915/) (2024)
- [The Expressibility of Polynomial based Attention Scheme](https://mlsanity.com/paper/2310.20051/) (2023)
- [Low-Rank Thinning](https://mlsanity.com/paper/2502.12063/) (2025)

## Abstract (arXiv)

We present an approximate attention mechanism named HyperAttention to address the computational challenges posed by the growing complexity of long contexts used in Large Language Models (LLMs). Recent work suggests that in the worst-case scenario, quadratic time is necessary unless the entries of the attention matrix are bounded or the matrix has low stable rank. We introduce two parameters which measure: (1) the max column norm in the normalized attention matrix, and (2) the ratio of row norms in the unnormalized attention matrix after detecting and removing large entries. We use these fine-grained parameters to capture the hardness of the problem. Despite previous lower bounds, we are able to achieve a linear time sampling algorithm even when the matrix has unbounded entries or a large stable rank, provided the above parameters are small. HyperAttention features a modular design that easily accommodates integration of other fast low-level implementations, particularly FlashAttention. Empirically, employing Locality Sensitive Hashing (LSH) to identify large entries, HyperAttention outperforms existing methods, giving significant speed improvements compared to state-of-the-art solutions like FlashAttention. We validate the empirical performance of HyperAttention on a variety of different long-context length datasets. For example, HyperAttention makes the inference time of ChatGLM2 50% faster on 32k context length while perplexity increases from 5.6 to 6.3. On larger context length, e.g., 131k, with causal masking, HyperAttention offers 5-fold speedup on a single attention layer.