Sparse Attention

Each token attends only to a fixed number of preceding tokens within a local window. This pattern mimics a convolutional operation over the sequence.

• Mechanism: A token at position i can attend to tokens in the range [i-w, i], where w is the window size.
• Complexity: Reduces from O(n²) to O(n * w), enabling linear scaling for long documents.
• Use Case: Foundation for models like Longformer and is critical for processing sequences longer than the training context (e.g., legal documents, books).

A hybrid pattern where most tokens use local (sliding window) attention, but a small set of predefined global tokens attend to all tokens and are attended to by all tokens.

• Global Tokens: Often special tokens (e.g., [CLS]) or user-specified tokens (e.g., question markers). They act as information aggregation hubs.
• Architectural Impact: Provides a path for long-range information flow without full quadratic cost. Used in BigBird.
• Example: In question answering, the question tokens can be made global, allowing the answer generation to consider the entire context.

A token attends to others at fixed intervals, creating a 'dilated' pattern that captures long-range dependencies with fewer connections.

• Pattern: At a given layer, token i attends to tokens i - s, i - 2s, i - 4s,... where s is the stride or dilation rate.
• Benefit: Efficiently increases the receptive field without expanding the window size. Often used in a hierarchical or alternating fashion with local windows.
• Analogy: Similar to dilated convolutions in computer vision, trading off fine-grained local context for broader coverage.

The attention matrix is divided into contiguous blocks. Attention is only computed within a subset of these blocks, often along a band around the diagonal.

• Structure: The n x n attention matrix is tiled into blocks of size b x b. Computation is restricted to a band of blocks, e.g., the main diagonal and k bands above/below it.
• Efficiency: Highly amenable to optimized GPU kernels for block-sparse matrix multiplication.
• Application: Used in models like Sparse Transformer for image generation and raw audio modeling, where data has a grid-like structure.

Each token attends to a random subset of other tokens. This pattern is theoretically inspired by the Erdős–Rényi random graph model.

• Implementation: For each query, a set of r random keys is selected. This can be fixed per layer or dynamic.
• Theoretical Basis: Helps ensure that the graph of token connections has small average path lengths, facilitating information mixing.
• Role in Practice: Rarely used alone. It is a key component in the BigBird model, combined with window and global attention to satisfy theoretical requirements for universal approximation.

The attention connectivity pattern is not fixed by a heuristic but is learned during training, allowing the model to discover optimal sparse structures for a given domain.

• Methods: Can be implemented via differentiable masks, where a parameterized router learns to select relevant key-value pairs for each query.
• Advantage: Maximizes the utility of each attention computation for the specific task (e.g., code, scientific text).
• Challenge: Introduces training overhead and requires careful design to remain efficient. Represents the frontier of adaptive sparse attention research.

The most common sparse pattern, where each token attends only to a fixed number of neighboring tokens within a local window. This reduces complexity from O(n²) to O(n * w), where w is the window size.

• Key Mechanism: A sliding window moves across the sequence.
• Example: In a text document, a word primarily interacts with the words immediately before and after it.
• Use Case: Foundation of models like Longformer and BigBird for processing long documents.
• Limitation: Cannot capture long-range dependencies without additional mechanisms.

A hybrid pattern that combines local windows with a small set of global tokens that attend to all tokens and are attended to by all tokens.

• Key Mechanism: Designates specific tokens (e.g., [CLS], question tokens) as global.
• Function: Provides a computational shortcut for information to flow across the entire sequence.
• Example: In Longformer, the global token for a question-answering task can aggregate context from the entire document.
• Impact: Enables tasks requiring whole-sequence understanding, like classification or QA, without quadratic cost.

A stochastic pattern where each token attends to a random subset of other tokens across the sequence. Often used in combination with local and global attention.

• Key Mechanism: Randomly sampled attention edges create a small-world network effect.
• Theoretical Basis: Inspired by graph theory; a few random connections dramatically reduce the path length between any two nodes (tokens).
• Implementation: Used in the BigBird model, which combines local, global, and random attention.
• Benefit: Helps propagate information across the sequence and improves modeling capacity beyond strict locality.

A pattern where a token attends to others at fixed intervals (strides) or with gaps (dilation), expanding the receptive field without a full local window increase.

• Key Mechanism: Similar to dilated convolutions in computer vision.
• Example: With a stride of 2, token t attends to tokens t-2, t-4, t-6, etc.
• Use Case: Effective for capturing periodic patterns or structures, such as in code or genomic sequences.
• Advantage: Provides a broader context view with a minimal increase in computed attention pairs.

Attention is computed only between predefined blocks of tokens, rather than between all individual tokens. This is highly efficient on hardware like GPUs and TPUs.

• Key Mechanism: The sequence is divided into contiguous blocks. Attention is computed within each block and between a select few blocks.
• Hardware Alignment: Matrices remain dense within blocks, allowing for optimized kernel operations.
• Framework Example: Used extensively in Google's JAX/Flax libraries for efficient large-model training.
• Application: Enables training of massive models (e.g., GPT-3-scale) on extremely long sequences by making the attention computation manageable.

Patterns where the sparsity structure is not fixed by a heuristic but is learned during training, allowing the model to discover optimal token interactions for a given task or dataset.

• Key Mechanism: Uses a routing network or differentiable masking to determine which attention edges are important.
• Example: The Routing Transformer employs k-means clustering over token embeddings to group tokens into clusters; attention is computed within clusters.
• Advantage: Adapts sparsity to data, potentially discovering more efficient and effective patterns than human-designed ones.
• Challenge: Introduces additional complexity in training and may require more memory to store the routing parameters.

A binary matrix applied during a transformer's self-attention computation that controls which tokens in the input sequence are allowed to attend to which other tokens. It is the fundamental mechanism for enforcing sparse attention patterns.

• Causal Masking: Ensures a token can only attend to previous tokens (for autoregressive generation).
• Padding Masking: Prevents the model from attending to padding tokens in batched inputs.
• Custom Sparse Masks: Manually defined to implement patterns like sliding windows or block-local attention.

A specific sparse attention pattern where each token can only attend to a fixed number of preceding tokens within a local window. This reduces computational complexity from O(n²) to O(n * w), where w is the window size.

• Key Benefit: Enables processing of sequences far longer than the model's original training context.
• Example: In a 100k-token sequence with a 4k window, token 50,001 attends only to tokens 46,002–50,000.
• Use Case: Foundational to models like Longformer and used in extended-context inference for very long documents.

A transformer optimization that stores computed key and value vectors for previous tokens during autoregressive generation. For sparse attention, the KV cache management is critical.

• Function: Eliminates redundant computation of keys/values for tokens that have already been processed.
• Sparse Interaction: With patterns like sliding windows, the cache can be pruned, evicting key-value pairs for tokens that have fallen outside the current attention window.
• Impact: Drastically improves inference speed and memory efficiency, especially for long-generation tasks.

Neural architectures that provide a dynamic, addressable memory mechanism beyond a fixed context window. They represent an alternative or complementary approach to sparse attention for long-range dependency modeling.

• External Memory: Uses a separate, often large, key-value store that the model can read from and write to.
• Different Paradigm: Unlike the monolithic context of a transformer, these networks can selectively retrieve relevant information from a vast memory.
• Examples: Neural Turing Machines and Differentiable Neural Computers. Modern Retrieval-Augmented Generation (RAG) systems are a form of memory augmentation.

A context compression technique that identifies and removes duplicate or highly similar information within the context window. It is often used in conjunction with sparse attention to maximize the utility of the attended tokens.

• Goal: Free up token budget for more diverse and critical information.
• Methods: Can involve hashing, embedding similarity checks, or learned models to detect semantic overlap.
• Synergy with Sparse Attention: By first eliminating redundant tokens, the remaining sparse connections can be more informationally efficient.

Refers to systems or model architectures where the effective context window size or the information retained within it can adapt at runtime. Sparse attention mechanisms are a primary enabler of this capability.

• Adaptive Patterns: The model can decide which tokens to attend to based on content, rather than using a fixed, predetermined pattern.
• Runtime Efficiency: Allows the model to focus compute on the most relevant parts of a very long sequence.
• Example: BigBird uses a combination of global, random, and local (sliding window) attention to create a dynamic, content-aware context.