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

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 largestscale empirical analysis to date of trainingfree 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 wallclock gains-forcing a task-dependent choice between global-to-token and block-to-block selection.Instead, during decoding, token-topage 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.