HyperAttention: Long-context Attention in Near-Linear Time

2023/10/09 by In‐Su Han, Insu Han, Rajesh Jayaram +10 · 1 voice · 25 citations
Computer Science · Mathematics · #Advanced Neural Network Applications #Algorithm #Artificial intelligence #Computer science #Context (archaeology) #Domain Adaptation and Few-Shot Learning #Hash function #Inference #Mathematics #Matrix (chemical analysis) #Matrix completion #Multimodal Machine Learning Applications #Parallel computing #Quadratic equation #Rank (graph theory) #Speedup #Theoretical computer science #Time complexity #cs.AI #cs.LG

paper · pdf · doi:10.48550/arxiv.2310.05869

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2023/10/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers
• Express Language Modeling
• Unifying Learning Dynamics and Generalization in Transformers Scaling Law
• Hold Onto That Thought: Assessing KV Cache Compression On Reasoning
• Even Faster Kernel Matrix Linear Algebra via Density Estimation
• End-to-End Multi-Modal Diffusion Mamba
• vAttention: Verified Sparse Attention
• RACE Attention: A Strictly Linear-Time Attention Layer for Training on Outrageously Large Contexts
• Towards Sampling Data Structures for Tensor Products in Turnstile Streams
• Fast attention mechanisms: a tale of parallelism
• Optimally detecting uniformly-distributed ℓ₂ heavy hitters in data streams
• DySK-Attn: A Framework for Efficient, Real-Time Knowledge Updating in Large Language Models via Dynamic Sparse Knowledge Attention
• Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
• DistrAttention: An Efficient and Flexible Self-Attention Mechanism on Modern GPUs
• SAS: Simulated Attention Score
• PERK: Long-Context Reasoning as Parameter-Efficient Test-Time Learning
• Two Heads Are Better than One: Simulating Large Transformers with Small Ones
• Curse of High Dimensionality Issue in Transformer for Long-context Modeling
• MonarchAttention: Zero-Shot Conversion to Fast, Hardware-Aware Structured Attention
• L-MTP: Leap Multi-Token Prediction Beyond Adjacent Context for Large Language Models
• Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse
• Subquadratic Algorithms and Hardness for Attention with Any Temperature
• Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
• Efficient Attention via Pre-Scoring: Prioritizing Informative Keys in Transformers
• Tokenize Image Patches: Global Context Fusion for Effective Haze Removal in Large Images

Discussions

• HyperAttention: Long-Context Attention in Near-Linear Time [hn, 73 points, 13 comments]

Related

• HSR-Enhanced Sparse Attention Acceleration
• SampleAttention: Near-Lossless Acceleration of Long Context LLM Inference with Adaptive Structured Sparse Attention
• Squeezed Attention: Accelerating Long Context Length LLM Inference
• Ltri-LLM: Streaming Long Context Inference for LLMs with Training-Free Dynamic Triangular Attention Pattern
• BLASST: Dynamic BLocked Attention Sparsity via Softmax Thresholding