# The Sparse Frontier: Sparse Attention Trade-offs in Transformer LLMs

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 46 of its 58 references that are in the map.
- First posted on arXiv 24 Apr 2025.

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

- [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)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [Efficient Streaming Language Models with Attention Sinks](https://mlsanity.com/paper/2309.17453/) (2023)
- [Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters](https://mlsanity.com/paper/2408.03314/) (2024)
- [Know What You Don't Know: Unanswerable Questions for SQuAD](https://mlsanity.com/paper/1806.03822/) (2018)
- [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)
- [Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference](https://mlsanity.com/paper/2406.10774/) (2024)
- [PyramidKV: Dynamic KV Cache Compression based on Pyramidal Information Funneling](https://mlsanity.com/paper/2406.02069/) (2024)
- [Native Sparse Attention: Hardware-Aligned and Natively Trainable Sparse Attention](https://mlsanity.com/paper/2502.11089/) (2025)
- [MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention](https://mlsanity.com/paper/2407.02490/) (2024)
- [Justice or Prejudice? Quantifying Biases in LLM-as-a-Judge](https://mlsanity.com/paper/2410.02736/) (2024)
- [Learn then Test: Calibrating Predictive Algorithms to Achieve Risk Control](https://mlsanity.com/paper/2110.01052/) (2021)
- [Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference](https://mlsanity.com/paper/2407.11550/) (2024)
- [QuALITY: Question Answering with Long Input Texts, Yes!](https://mlsanity.com/paper/2112.08608/) (2021)
- [InfLLM: Training-Free Long-Context Extrapolation for LLMs with an Efficient Context Memory](https://mlsanity.com/paper/2402.04617/) (2024)
- [PyramidInfer: Pyramid KV Cache Compression for High-throughput LLM Inference](https://mlsanity.com/paper/2405.12532/) (2024)
- [Observational Scaling Laws and the Predictability of Language Model Performance](https://mlsanity.com/paper/2405.10938/) (2024)
- [FlexPrefill: A Context-Aware Sparse Attention Mechanism for Efficient Long-Sequence Inference](https://mlsanity.com/paper/2502.20766/) (2025)
- [SparQ Attention: Bandwidth-Efficient LLM Inference](https://mlsanity.com/paper/2312.04985/) (2023)
- [A Comprehensive Survey on Long Context Language Modeling](https://mlsanity.com/paper/2503.17407/) (2025)
- [Dynamic Memory Compression: Retrofitting LLMs for Accelerated Inference](https://mlsanity.com/paper/2403.09636/) (2024)
- [MagicPIG: LSH Sampling for Efficient LLM Generation](https://mlsanity.com/paper/2410.16179/) (2024)
- [No Token Left Behind: Reliable KV Cache Compression via Importance-Aware Mixed Precision Quantization](https://mlsanity.com/paper/2402.18096/) (2024)
- [Model Tells You Where to Merge: Adaptive KV Cache Merging for LLMs on Long-Context Tasks](https://mlsanity.com/paper/2407.08454/) (2024)
- [A Simple and Effective L2 Norm-Based Strategy for KV Cache Compression](https://mlsanity.com/paper/2406.11430/) (2024)

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

- [Inference-Time Hyper-Scaling with KV Cache Compression](https://mlsanity.com/paper/2506.05345/) (2025)
- [Taming the Fragility of KV Cache Eviction in LLM Inference](https://mlsanity.com/paper/2510.13334/) (2025)
- [LoLA: Low-Rank Linear Attention With Sparse Caching](https://mlsanity.com/paper/2505.23666/) (2025)
- [Kinetics: Rethinking Test-Time Scaling Laws](https://mlsanity.com/paper/2506.05333/) (2025)
- [Draft-based Approximate Inference for LLMs](https://mlsanity.com/paper/2506.08373/) (2025)
- [SpotAttention: Plug-In Block-Sparse Routing for Pretrained Long-Context Transformers](https://mlsanity.com/paper/2606.22874/) (2026)
- [Switch Attention: Towards Dynamic and Fine-grained Hybrid Transformers](https://mlsanity.com/paper/2603.26380/) (2026)
- [DashAttention: Differentiable and Adaptive Sparse Hierarchical Attention](https://mlsanity.com/paper/2605.18753/) (2026)
- [Controllably Efficient Language Models](https://mlsanity.com/paper/2511.05313/) (2025)
- [AdaSplash-2: Faster Differentiable Sparse Attention](https://mlsanity.com/paper/2604.15180/) (2026)
- [Rethinking LLM Advancement: Compute-Dependent and Independent Paths to Progress](https://mlsanity.com/paper/2505.04075/) (2025)
- [Detecting Contextual Hallucinations in LLMs with Frequency-Aware Attention](https://mlsanity.com/paper/2602.18145/) (2026)
- [VFA: Relieving Vector Operations in Flash Attention with Global Maximum Pre-computation](https://mlsanity.com/paper/2604.12798/) (2026)
- [LiteTopK: Exploiting the Curse of Dimensionality for a Fused Indexer-TopK Kernel in Long-Context Sparse Attention](https://mlsanity.com/paper/2607.11976/) (2026)
- [Optimizing Native Sparse Attention with Latent Attention and Local Global Alternating Strategies](https://mlsanity.com/paper/2511.00819/) (2025)
- [Lifelong In-Context Learning with Transformers Requires Parametric Forms of Attention](https://mlsanity.com/paper/2606.25342/) (2026)
- [LOCKS: Page-Local Compact Key Summaries for Efficient Long-Context Decoding](https://mlsanity.com/paper/2607.24555/) (2026)
- [SCOUT: Toward Sub-Quadratic Attention via Segment Compression for Optimized Utility in Transformers](https://mlsanity.com/paper/2509.00935/) (2025)
- [Learning What Matters: Supervising Global Context Pruning with Causal Evidence Sets](https://mlsanity.com/paper/2607.21692/) (2026)
- [Beyond Sparse Weights: When Is Attention Compressible?](https://mlsanity.com/paper/2608.21541/) (2026)
- [CRISP: Cliff-awaRe Input-adaptive Sparse Prefilling with Structural-Mass-Motivated Routing](https://mlsanity.com/paper/2609.01925/) (2026)
- [Playing log(N)-Questions over Wikipedia Abstracts: How Per-Round Errors Compound Under Information Asymmetry](https://mlsanity.com/paper/2609.19113/) (2026)
- [Block-Sparse Attention with Semantic-Geometric Decoupled Routing](https://mlsanity.com/paper/2609.22884/) (2026)
- [Pre-registered tests of solid-state-physics-inspired LLM compression: a cluster-level negative result at small-language-model scale](https://mlsanity.com/paper/2609.34292/) (2026)
- [PulseInfer: I/O-Centric Sparse KV Cache Offloading for Efficient Long-Context LLM Decoding](https://mlsanity.com/paper/2609.34555/) (2026)
- [SparseEngine: Sparse-First Inference Engine](https://mlsanity.com/paper/2609.39068/) (2026)
- [CommunityKV: Efficient Long-Context Decoding via Graph Partitioning](https://mlsanity.com/paper/2610.00418/) (2026)
- [MOIRA: Mass-Oriented Indexing with Ragged Attention for Long-Context Decoding](https://mlsanity.com/paper/2610.04313/) (2026)
- [On the Trade-off Between Information Loss and Generalization in Sparse Attention](https://mlsanity.com/paper/2610.04424/) (2026)

## Abstract (arXiv)

Sparse attention offers a promising strategy to extend long-context capabilities in Transformer LLMs, yet its efficiency-accuracy trade-offs remain unclear due to the lack of comprehensive evaluation. We address this gap with the largest-scale empirical analysis to date of training-free sparse attention, evaluating six methods across multiple model families and sizes, sequences up to 128K tokens, and sparsity levels up to 0.95 (i.e., 1/20 attention budget) on nine diverse tasks. We first organise the rapidly evolving landscape of sparse attention methods into a taxonomy along four design axes. Our analysis then yields actionable insights: 1) sparse attention is effective: larger sparse models outperform smaller dense ones at equivalent cost, improving the Pareto frontier; 2) for the training-free methods we study, fine-grained per-query importance estimation during prefilling remains impractical-due to both the cost of estimation and the lack of sparse kernels that translate fine-grained sparsity into wall-clock gains-forcing a task-dependent choice between global-to-token and block-to-block selection. Instead, during decoding, token-to-page selection becomes feasible, enabling better generalisation and higher sparsity tolerance; 3) longer sequences tolerate higher sparsity, suggesting that fixed-budget methods in production are suboptimal. Together, these findings provide practical guidance for deploying sparse attention and methodological recommendations for future evaluations. Our code is available at https://github.com/PiotrNawrot/sparse-frontier.