Sparse Attention

This pattern restricts each token's attention to a fixed, contiguous local window of neighboring tokens. It is based on the locality prior, the assumption that nearby tokens are most relevant.

• Mechanism: A sliding window of fixed size w. Token i attends to tokens in the range [i-w, i+w].
• Complexity: Reduces from O(n²) to O(n * w), becoming linear when w is constant.
• Use Case: Fundamental building block in models like Longformer and BigBird for processing long documents. It is highly effective for text where local context (e.g., a sentence or paragraph) is primary.
• Limitation: Cannot model long-range dependencies directly; requires stacking many layers or combining with a global pattern.

This pattern attends to tokens at regular intervals (strides), simulating a dilated convolutional operation over the sequence. It provides a broader view with fewer connections.

• Mechanism: For a stride s and dilation d, token i attends to tokens at positions i, i ± d, i ± 2d, ... up to a window limit, skipping intermediate tokens.
• Complexity: Similar to fixed patterns but with a wider effective receptive field per layer.
• Use Case: Used in Sparse Transformer and Image Transformer to efficiently capture periodic or regularly spaced structures. Effective for audio, time-series, and image data where relevant features recur at intervals.
• Benefit: Achieves a long receptive field faster than stacking many local layers.

This pattern designates a small set of global tokens that attend to all tokens in the sequence and are attended to by all tokens. They act as a communication bottleneck for long-range information.

• Mechanism: A subset of tokens (e.g., the [CLS] token, sentence separators, or learned task tokens) are given full attention connectivity.
• Complexity: Adds O(n * g) cost, where g is the small, fixed number of global tokens.
• Use Case: A core component in BigBird and Longformer. Essential for question answering and summarization, where a query token needs to aggregate information from the entire document.
• Hybrid Use: Almost always combined with a local or random pattern to create a block-sparse pattern (local + global + random).

This pattern allows each token to attend to a random subset of other tokens across the sequence. It introduces non-local connections to help information flow across long distances.

• Mechanism: For each token i, a set of r random token indices is sampled. Attention is computed only for these pairs.
• Complexity: O(n * r), linear when r is fixed.
• Use Case: Used in Sparse Transformer and BigBird. It provides a small-world network property, ensuring that any two tokens are connected via a short path of random edges, which is provably necessary for maintaining model expressivity.
• Theoretical Basis: Inspired by the Erdős–Rényi random graph model and Johnson–Lindenstrauss lemma for dimensionality reduction.

This is the most common practical pattern, combining two or more simpler patterns (e.g., Local + Global + Random) into a single, composite attention mask. It balances efficiency with model capacity.

• Mechanism: The attention matrix is partitioned into blocks. Specific blocks are activated according to the chosen sub-patterns.
• Complexity: The sum of the complexities of its constituent patterns.
• Use Case: The BigBird model uses a block-sparse pattern with local, global, and random attention. This architecture is a universal approximator of sequence functions and is formally as expressive as the original Transformer.
• Implementation: Efficiently computed using block-sparse matrix multiplication kernels in libraries like Triton or specialized CUDA code.

This pattern does not use a fixed heuristic. Instead, the sparsity structure itself is parameterized and learned during training, allowing the model to discover optimal attention connectivity for a given task.

• Mechanisms:
  • Routing Networks: A lightweight network predicts a sparse set of relevant tokens for each query.
  • Differentiable Masking: The attention mask is generated via a differentiable function (e.g., using Gumbel-Softmax), allowing gradient-based learning of the pattern.
• Complexity: Introduces overhead for computing the pattern, but the resulting attention computation remains sparse.
• Use Case: Research architectures like Routing Transformer and Reformer (using learned locality-sensitive hashing). Aimed at domains where the optimal attention pattern is not obvious (e.g., code, structured data).
• Challenge: Balancing the cost of pattern computation with the savings from sparse attention.

Sparse attention is indispensable in scientific domains with extreme sequence lengths:

• Genomic Sequence Analysis: DNA sequences can be millions of base pairs long. Models like Hyena and others use long convolutions or sparse attention to identify regulatory elements and predict mutations across megabase scales.
• High-Resolution Image Generation: Generating 1024x1024+ images requires modeling millions of pixels. Sparse Transformers and Masked Generative Image Transformers use 2D factorized patterns to make this tractable.
• Financial Time Series: Analyzing years of high-frequency tick data requires modeling very long temporal dependencies for forecasting and anomaly detection.

A class of attention mechanisms that reformulate the standard softmax operation using kernel feature maps to achieve linear computational complexity O(N) with respect to sequence length, rather than quadratic. It is a foundational approach for enabling efficient long-context processing.

• Core Idea: Approximates the exponential in softmax via a kernel function, allowing the attention matrix to be decomposed into a product of feature maps.
• Trade-off: Many linear attention variants are approximations of standard attention, potentially sacrificing some expressiveness for massive efficiency gains on extremely long sequences.
• Example: Models like Linformer and Performer use different kernel strategies (e.g., random Fourier features) to enable this linear scaling.

An IO-aware, exact attention algorithm that optimizes memory reads/writes between GPU memory hierarchies (HBM vs. SRAM). It recomputes attention scores on-the-fly during the backward pass to avoid storing the massive N×N attention matrix, enabling faster training and inference for long sequences.

• Key Innovation: Uses tiling to keep small blocks of data in fast SRAM, minimizing slow HBM accesses. This makes it a hardware-level optimization.
• Relationship to Sparse Attention: FlashAttention accelerates full attention. It is often combined with sparse patterns (like in FlashAttention-2 with block-sparsity) to achieve even greater speedups on supported hardware.
• Impact: Has become a standard library (e.g., in PyTorch via torch.nn.functional.scaled_dot_product_attention) for training state-of-the-art LLMs.

A neural network architecture composed of many specialized sub-networks (experts) and a gating network that dynamically routes each input token to a small subset of relevant experts. This is a form of conditional computation.

• Sparsity Connection: In a Sparse MoE, the gating network activates only a fixed, small number of experts (e.g., top-2) per token. This creates a sparse activation pattern across parameters, analogous to how sparse attention creates a sparse interaction pattern across tokens.
• Scalability Benefit: Allows model parameter counts to scale into the trillions while keeping the FLOPs per token constant, as only a few experts are active for any given input.
• Example: Models like Switch Transformers and Mixtral 8x7B are Sparse MoE architectures.

A broad paradigm in deep learning where a model dynamically activates or selects different subsets of its parameters or computational pathways based on the input. This avoids the cost of evaluating the entire network for every sample.

• Umbrella Term: Encompasses techniques like Sparse MoE, Adaptive Computation Time (ACT), and Dynamic Filter Networks.
• Core Principle: Enables models to have a very large capacity (total parameters) but a manageable activity (parameters used per forward pass).
• Relationship: Sparse attention is a specific instantiation of conditional computation applied to the attention mechanism itself, conditionally computing interactions between tokens.

A mechanism for recurrent neural networks that allows the model to dynamically decide how many computational steps (or "ponder" time) to devote to processing each input element before producing an output. It introduces a halting probability at each step.

• Dynamic Depth: ACT creates models with variable per-token computational depth, a form of conditional computation across time.
• Conceptual Parallel: While designed for RNNs, the core idea of allocating more compute to "harder" inputs is related to the motivation behind sparse attention, which can allocate attention bandwidth more efficiently across a sequence.
• Modern Relevance: The principle inspires adaptive mechanisms in transformers, such as early exit strategies or dynamic layer skipping.

A model parallelism strategy specifically designed for training and serving large Mixture of Experts (MoE) models. It involves placing different experts on different devices (GPUs) and routing tokens across the device network as determined by the gating function.

• System Challenge: The sparse, conditional activation of experts in MoE models creates unique communication patterns. Expert parallelism optimizes for this by sharding experts across devices.
• Infrastructure Link: Efficient sparse attention mechanisms also require careful system design to handle irregular memory access and communication. Both fields push the boundaries of distributed model serving.
• Enabling Technology: Allows for the practical training of models with hundreds of billions to trillions of parameters, like Google's Switch Transformer, by distributing the massive parameter count.