Sparse Attention

Unlike standard self-attention where memory and time scale quadratically (O(n²)) with sequence length, sparse attention achieves linear (O(n)) or O(n√n) complexity. This is achieved by restricting each token to attend to a fixed number of other tokens rather than the entire sequence. For example, a 32k-token document becomes computationally tractable instead of requiring prohibitive GPU memory.

Each token attends only to a fixed-size window of neighboring tokens (e.g., ±512 positions). This local pattern captures short-range dependencies efficiently and is used in models like Longformer and Mistral. Key characteristics:

• Window size w determines the receptive field
• Complexity reduces to O(n × w)
• Multiple stacked layers expand the effective context through information propagation
• Works well for tasks where local context dominates, such as NER and syntactic parsing

Extends the sliding window by introducing gaps (dilation) between attended tokens, similar to dilated convolutions. A dilation rate d means tokens attend to every d-th neighbor within the window. This increases the receptive field without increasing computation. For instance, with window size 512 and dilation 2, a token covers a span of 1024 tokens while still computing only 512 attention scores. Longformer and Sparse Transformer employ this technique.

Designated global tokens (such as [CLS], [SEP], or task-specific markers) attend to all tokens in the sequence, and all tokens attend to them. This creates information bottlenecks that propagate long-range signals across the entire document. Use cases:

• Classification tasks where [CLS] must aggregate full-document context
• Question answering where question tokens need global visibility
• Symmetric global attention ensures bidirectional information flow

The attention matrix is divided into fixed-size blocks, and only selected blocks are computed based on a predefined sparsity mask. This pattern is hardware-friendly because it maps efficiently to GPU tensor cores. BigBird uses a combination of:

• Random blocks for stochastic long-range connections
• Local sliding windows for nearby context
• Global tokens for sequence-wide information This hybrid approach provably approximates full attention while maintaining linear complexity.

Tokens attend to positions at regular intervals across the sequence. A stride s means token i attends to positions i+s, i+2s, etc., plus local neighbors. This creates a sparse grid that captures both local and long-range structure. The Sparse Transformer introduced strided patterns for image and audio generation, where grid-like dependencies align naturally with the data structure. For text, strided attention can model periodic document structure like headers or section boundaries.

Extends sliding window attention by introducing gaps between attended tokens, analogous to dilated convolutions. A dilation factor d means the head attends to every d-th token within a range.

• Exponentially increases the receptive field without adding compute
• Often combined with local windows in hybrid patterns
• Key component in Longformer's attention scheme for capturing distant context

Designates a small set of predefined tokens (e.g., CLS, SEP, or task-specific markers) that attend to the entire sequence and are attended to by all tokens. This creates information bottlenecks that propagate global context.

• Used in BigBird and Longformer for classification tasks
• Adds only O(n) complexity for the global tokens
• Enables sequence-level representations without dense attention

Divides the input sequence into contiguous blocks and computes attention only between selected block pairs based on a predefined sparsity mask. This maps efficiently to GPU tensor cores.

• Implemented in Sparse Transformers (OpenAI) with strided and fixed patterns
• Reduces memory footprint by avoiding materialization of the full N×N matrix
• Well-suited for data with inherent block structure, like images or code

The core problem sparse attention solves: standard self-attention computes an N × N attention score matrix, requiring O(n²) memory and time. For a 100K-token document, this demands ~40GB of memory in float32.

• Makes processing long sequences (legal docs, genomes) infeasible
• Sparse patterns trade full attention for linear or near-linear scaling
• The choice of sparsity pattern directly impacts the model's effective context