Sparse Attention: Definition and Examples

Sparse Attention is an optimization of the standard attention mechanism used in Transformer architectures. In classic attention (so-called 'dense' or 'full attention'), each token in a sequence computes an attention score with every other token, resulting in quadratic complexity O(n²) with respect to sequence length. Sparse Attention solves this problem by computing attention only on a carefully selected subset of token pairs.

Several strategies exist to determine which tokens should 'observe' each other. The most common patterns include local attention (each token only looks at its immediate neighbors), fixed-block attention, dilated attention (skipping tokens at regular intervals), and hybrid approaches combining local and global attention. The Longformer model, for example, uses a combination of sliding local attention and global attention on certain key tokens.

The main advantage of Sparse Attention is enabling models to process much longer sequences. Where dense attention becomes prohibitive beyond a few thousand tokens, Sparse Attention can handle contexts of tens or even hundreds of thousands of tokens, with complexity reduced to O(n√n) or even O(n log n) depending on implementation.

This technique was popularized by works such as Sparse Transformer (OpenAI, 2019), Longformer, BigBird, and more recently in architectures like Mistral that use Sliding Window Attention. It has become an essential component for building models capable of handling long documents, entire codebases, or lengthy conversations.