Sparse Attention Mechanisms are the architectural modifications to the standard Transformer self-attention that replace the O(N²) full attention matrix with structured sparsity patterns — computing attention only between selected token pairs rather than all pairs — enabling processing of sequences with 100K to 1M+ tokens while maintaining the ability to capture both local context and long-range dependencies.

The Full Attention Bottleneck

Standard self-attention computes QK^T for all N² token pairs, requiring O(N²) memory and compute. For a 128K-token context: 128K² = 16.4 billion attention scores per layer per head. At FP16, the attention matrix alone requires 32 GB — exceeding single-GPU memory.

Sparse Attention Patterns

• Sliding Window (Local) Attention: Each token attends only to W neighbors (W/2 left, W/2 right). Complexity: O(N×W). Captures local context well but cannot model dependencies beyond window size W. Used in Mistral (W=4096) and as a base pattern in hybrid approaches.

• Global + Local (Longformer): Combine sliding window attention for most tokens with global attention for a few special tokens ([CLS], question tokens in QA). Global tokens attend to all positions and are attended by all positions. Complexity: O(N×W + N×G) where G is the number of global tokens. Enables document-level reasoning through global token aggregation.

• BigBird: Combines three patterns: (1) sliding window (local), (2) global tokens, (3) random attention (each token attends to R random positions). The random connections ensure the attention graph has short average path length, theoretically preserving the ability to propagate information between any two tokens in O(log N) layers.

• Dilated Attention: Like dilated convolutions — attend to every k-th token within a window. Exponentially increasing dilation across heads or layers captures multi-scale dependencies. LongNet uses dilated attention to scale to 1B tokens.

• Block Sparse Attention: Divide the sequence into blocks. Compute full attention within blocks and sparse attention between selected block pairs (e.g., every m-th block attends to every n-th block). Efficient GPU implementation using block-sparse matrix operations.

Hybrid Approaches (Production Models)

Modern long-context models combine dense and sparse attention:

• Sliding Window + Global Sink: Mistral/Mixtral use sliding window attention with attention sinks (the first few tokens always attended to, as they accumulate global information). Effective to 32K+ tokens.
• Layer-Wise Mixing: Dense attention in some layers (for global reasoning) and sparse attention in others (for local processing). Different layers serve different computational roles.

Alternative Efficiency Approaches

• Flash Attention: Not sparse — computes exact full attention but with IO-aware tiling that reduces HBM reads/writes. O(N²) compute but practical speedup of 2-4× and O(N) memory. The dominant approach for sequences up to ~128K tokens.
• Ring Attention: Distributes the sequence across multiple GPUs, each computing attention on its local segment while passing KV blocks in a ring topology. Enables arbitrary context length limited only by aggregate GPU memory.

Sparse Attention Mechanisms are the architectural innovations that extend Transformer capabilities to document-scale and beyond — replacing the quadratic bottleneck with structured sparsity patterns that preserve the attention mechanism's core strength of dynamic information routing while making million-token contexts computationally feasible.