# Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers

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

## Key facts

- Cited by 52 papers in the map (data through 14 Oct 2026).
- Builds on 66 of its 79 references that are in the map.
- First posted on arXiv 24 Jun 2024.

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

- [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)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Decoupled Weight Decay Regularization](https://mlsanity.com/paper/1711.05101/) (2017)
- [Pythia: A Suite for Analyzing Large Language Models Across Training and Scaling](https://mlsanity.com/paper/2304.01373/) (2023)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [Aligning Books and Movies: Towards Story-like Visual Explanations by Watching Movies and Reading Books](https://mlsanity.com/paper/1506.06724/) (2015)
- [What Does BERT Look At? An Analysis of BERT's Attention](https://mlsanity.com/paper/1906.04341/) (2019)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [RWKV: Reinventing RNNs for the Transformer Era](https://mlsanity.com/paper/2305.13048/) (2023)
- [Simplified State Space Layers for Sequence Modeling](https://mlsanity.com/paper/2208.04933/) (2022)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [Retentive Network: A Successor to Transformer for Large Language Models](https://mlsanity.com/paper/2307.08621/) (2023)
- [Gated Linear Attention Transformers with Hardware-Efficient Training](https://mlsanity.com/paper/2312.06635/) (2023)

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

- [Position: Episodic Memory is the Missing Piece for Long-Term LLM Agents](https://mlsanity.com/paper/2502.06975/) (2025)
- [Tracing the Representation Geometry of Language Models from Pretraining to Post-training](https://mlsanity.com/paper/2509.23024/) (2025)
- [Bidirectional Sparse Attention for Faster Video Diffusion Training](https://mlsanity.com/paper/2509.01085/) (2025)
- [On Efficient Variants of Segment Anything Model: A Survey](https://mlsanity.com/paper/2410.04960/) (2024)
- [Locret: Enhancing Eviction in Long-Context LLM Inference with Trained Retaining Heads on Consumer-Grade Devices](https://mlsanity.com/paper/2410.01805/) (2024)
- [When Precision Meets Position: BFloat16 Breaks Down RoPE in Long-Context Training](https://mlsanity.com/paper/2411.13476/) (2024)
- [CEReBrO: Compact Encoder for Representations of Brain Oscillations Using Efficient Alternating Attention](https://mlsanity.com/paper/2501.10885/) (2025)
- [E2LLM: Encoder Elongated Large Language Models for Long-Context Understanding and Reasoning](https://mlsanity.com/paper/2409.06679/) (2024)
- [ESPFormer: Doubly-Stochastic Attention with Expected Sliced Transport Plans](https://mlsanity.com/paper/2502.07962/) (2025)
- [A Survey of Scaling in Large Language Model Reasoning](https://mlsanity.com/paper/2504.02181/) (2025)
- [Hardware-aligned Hierarchical Sparse Attention for Efficient Long-term Memory Access](https://mlsanity.com/paper/2504.16795/) (2025)
- [LIFELONG SOTOPIA: Evaluating Social Intelligence of Language Agents Over Lifelong Social Interactions](https://mlsanity.com/paper/2506.12666/) (2025)
- [OrthoRank: Token Selection via Sink Token Orthogonality for Efficient LLM inference](https://mlsanity.com/paper/2507.03865/) (2025)
- [QuantSparse: Comprehensively Compressing Video Diffusion Transformer with Model Quantization and Attention Sparsification](https://mlsanity.com/paper/2509.23681/) (2025)
- [Attention Reveals More Than Tokens: Training-Free Long-Context Reasoning with Attention-guided Retrieval](https://mlsanity.com/paper/2503.09819/) (2025)
- [Spark Transformer: Reactivating Sparsity in FFN and Attention](https://mlsanity.com/paper/2506.06644/) (2025)
- [LOOM-Scope: a comprehensive and efficient LOng-cOntext Model evaluation framework](https://mlsanity.com/paper/2507.04723/) (2025)
- [Cost-Optimal Grouped-Query Attention for Long-Context Modeling](https://mlsanity.com/paper/2503.09579/) (2025)
- [Sparse-to-Dense: A Free Lunch for Lossless Acceleration of Video Understanding in LLMs](https://mlsanity.com/paper/2505.19155/) (2025)
- [APB: Accelerating Distributed Long-Context Inference by Passing Compressed Context Blocks across GPUs](https://mlsanity.com/paper/2502.12085/) (2025)
- [ConTextual: Improving Clinical Text Summarization in LLMs with Context-preserving Token Filtering and Knowledge Graphs](https://mlsanity.com/paper/2504.16394/) (2025)
- [ILRe: Intermediate Layer Retrieval for Context Compression in Causal Language Models](https://mlsanity.com/paper/2508.17892/) (2025)
- [Every Token Counts: Generalizing 16M Ultra-Long Context in Large Language Models](https://mlsanity.com/paper/2511.23319/) (2025)
- [Top-Theta Attention: Sparsifying Transformers by Compensated Thresholding](https://mlsanity.com/paper/2502.08363/) (2025)
- [Adaptive and Resource-efficient Agentic AI Systems for Mobile and Embedded Devices: A Survey](https://mlsanity.com/paper/2510.00078/) (2025)
- [Block Sparse Flash Attention](https://mlsanity.com/paper/2512.07011/) (2025)
- [RAM-Net: Linear-Time Sequence Modeling with Sparsely Addressable State](https://mlsanity.com/paper/2602.11958/) (2026)
- [Routing Absorption in Sparse Attention: Why Random Gates Are Hard to Beat](https://mlsanity.com/paper/2603.02227/) (2026)
- [Reorganizing attention-space geometry with expressive attention](https://mlsanity.com/paper/2407.18601/) (2024)
- [You Only Use Reactive Attention Slice For Long Context Retrieval](https://mlsanity.com/paper/2409.13695/) (2024)

## Abstract (arXiv)

Accommodating long sequences efficiently in autoregressive Transformers, especially within an extended context window, poses significant challenges due to the quadratic computational complexity and substantial KV memory requirements inherent in self-attention mechanisms. In this work, we introduce SPARSEK Attention, a novel sparse attention mechanism designed to overcome these computational and memory obstacles while maintaining performance. Our approach integrates a scoring network and a differentiable top-k mask operator, SPARSEK, to select a constant number of KV pairs for each query, thereby enabling gradient-based optimization. As a result, SPARSEK Attention offers linear time complexity and constant memory footprint during generation. Experimental results reveal that SPARSEK Attention outperforms previous sparse attention methods and provides significant speed improvements during both training and inference, particularly in language modeling and downstream tasks. Furthermore, our method can be seamlessly integrated into pre-trained Large Language Models (LLMs) with minimal fine-tuning, offering a practical solution for effectively managing long-range dependencies in diverse applications.