Research map / Learning theory and algorithms / Matrix and tensor methods

HyperAttention: Long-context Attention in Near-Linear Time

ICLR 2024 · Learning theory and algorithms › Matrix and tensor methods · approach: Structured low-rank learning · 9 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes HyperAttention, a near-linear-time approximate attention mechanism combining sortLSH-based large-entry detection with uniform column sampling and a recursive causal-masking extension, applied to pretrained LLMs without fine-tuning.

Problem

Quadratic cost of exact softmax attention for long contexts; prior provable subquadratic methods assume bounded entries or low stable rank and do not support causal masking, and KDE-based approaches are impractical.

Approach

Find large attention entries with Hamming-sorted LSH blocks, estimate the softmax normalizer D by combining exact masked row sums with uniform column sampling, and approximate the product with values via row-norm sampling; the guarantee relies on two fine-grained parameters (max column norm of D^-1 A and ratio of row norms after removing heavy entries) rather than bounded entries. Causal attention

Key results

• ChatGLM2-6B-32k with 32k context: attention layers about 50% faster while perplexity rises from 5.6 to 6.3 (abstract).
• Single attention layer at n=131k: up to 54x faster forward+backward without causal masking and 5.4x with causal masking vs FlashAttention 2.
• Summarization and code completion LongBench tasks are more robust to replacement than question answering; half of layers patched keeps most tasks within 13% degradation.

Measured effects reported in the paper

Surprising findings

• Summarization barely degrades under partial HyperAttention patching while single/multi-document QA drops sharply.
• Unlike the vision model, the first columns of D^-1 A in chatglm2 contain heavy entries, so alpha was computed excluding the first 32 columns.

Limitations

• Assumption that alpha (max squared column norm of softmax matrix) is n^{o(1)} is verified only empirically and only on limited models.
• Performance degrades substantially when many layers are replaced (e.g., 21+ layers in chatglm2 for QA tasks).
• Causal masking speedup is much smaller than non-causal because of partitioning and merging overhead.

Experimental setup

Datasets: LongBench ImageNet

Benchmarks: LongBench ImageNet

Metrics: perplexity speedup task-specific LongBench scores wall-clock time

Baselines: FlashAttention 2 KDEFormer

Builds on: KDEFormer FlashAttention 2 Hamming sorted LSH Approximate matrix multiplication via row norm sampling

Closest papers by meaning

• ReAttention: Training-Free Infinite Context with Finite Attention Scope (ICLR 2025 · similarity 0.89)
• Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Models (ICML 2024 · similarity 0.89)
• DuoAttention: Efficient Long-Context LLM Inference with Retrieval and Streaming Heads (ICLR 2025 · similarity 0.88)
• A Training-Free Sub-quadratic Cost Transformer Model Serving Framework with Hierarchically Pruned Attention (ICLR 2025 · similarity 0.88)
• Efficient Low Rank Attention for Long-Context Inference in Large Language Models (NeurIPS 2025 · similarity 0.88)
• Scaling Stick-Breaking Attention: An Efficient Implementation and In-depth Study (ICLR 2025 · similarity 0.88)