Sparse Attention

A local attention pattern where each query attends only to a fixed number of keys within a local window centered around its position. This mimics the local receptive fields of convolutional neural networks and is highly effective for tasks with strong local dependencies, such as character-level language modeling or genomic sequence analysis.

• Key Mechanism: Computes attention over W tokens to the left and right of the query position.
• Complexity: Reduces from quadratic O(N²) to linear O(N*W).
• Hardware Efficiency: Enables regular, predictable memory access patterns, making it highly amenable to kernel optimization.

A pattern that sparsifies the attention matrix by having queries attend to keys at regularly spaced intervals, skipping intermediate tokens. This creates a 'dilated' receptive field that captures longer-range dependencies than a simple sliding window without a full quadratic cost.

• Key Mechanism: For a dilation d, a query at position i attends to keys at positions i - d, i - 2d, ... and i + d, i + 2d, ....
• Use Case: Effective in models like Longformer for document-level tasks, where it combines local window attention with a few global dilated positions.
• Trade-off: Can miss fine-grained local context between the strided positions.

A hybrid pattern that designates a small set of global tokens (e.g., [CLS], special separator tokens) that attend to all tokens in the sequence and are attended to by all tokens. The remaining tokens use a local pattern like sliding window attention.

• Key Mechanism: Introduces a few 'summary' tokens with a full, dense attention view of the sequence.
• Complexity: The global component is O(G*N), where G is the small number of global tokens, keeping overall complexity near-linear.
• Application: Foundational to architectures like Longformer and BigBird, enabling tasks requiring a global context (e.g., question answering, classification) while processing very long sequences.

A structured sparsity pattern that partitions the sequence into contiguous blocks and defines a sparse connectivity graph between these blocks. Attention is computed only for query-key pairs where their respective blocks are connected.

• Key Mechanism: The attention matrix is divided into a grid of sub-blocks, only a subset of which are computed. Common graphs include 2D grid or random block patterns.
• Hardware Advantage: The regular, block-wise structure (e.g., N:M sparsity at the block level) can be efficiently mapped to hardware like Sparse Tensor Cores on modern GPUs.
• Example: Used in models like Sparse Transformer to achieve O(N√N) complexity.

A pattern where each query attends to a randomly selected, fixed set of keys across the entire sequence. This stochastic connectivity helps the model build a 'small-world' network, providing shortcuts for information flow that can improve modeling of long-range dependencies.

• Key Mechanism: For each query, a subset of r key positions is sampled uniformly at random.
• Theoretical Basis: Inspired by the theory of random graphs; a small amount of random connectivity can dramatically reduce the graph's diameter.
• Implementation: Often combined with local window attention in models like BigBird, where it complements local and global patterns.

Patterns where the sparsity structure is not predefined by a fixed rule but is parameterized and learned during training. The model learns which query-key pairs are most important for the downstream task.

• Key Mechanism: Uses a lightweight, trainable routing network or differentiable sampling (e.g., REINFORCE, Gumbel-Softmax) to generate a binary mask over the attention matrix.
• Advantage: Can discover task-optimal and data-optimal sparsity patterns that outperform hand-designed heuristics.
• Challenge: Introduces training overhead and requires careful design to maintain differentiability and efficiency. Frameworks like Routing Transformers and Sinkhorn Attention explore this paradigm.

Multi-modal models that fuse video, audio, and text must align information across very long, heterogeneous sequences. Sparse, cross-modal attention is key to feasibility.

• Allows video-language models to reason over minute-long clips by attending to key frames and relevant transcript segments.
• Supports embodied AI agents that process continuous sensor streams (LIDAR, camera) with natural language instructions for real-time navigation and manipulation.
• Reduces latency in interactive AI assistants that must process past conversation context while generating responsive dialogue.

The primary driver for sparse attention in industry is enabling large language models (LLMs) to run on smartphones, IoT devices, and other hardware with strict memory and power budgets.

• Mobile AI assistants (e.g., on-device chatbots) use sparse attention to maintain conversation history without cloud dependency.
• Keyword spotting and always-on audio sensing use efficient attention to detect wake words or specific sounds with minimal battery drain.
• Enables privacy-preserving AI by keeping sensitive data (personal messages, health data) from leaving the device.

A family of data structures for efficiently storing and operating on tensors where most elements are zero. Instead of storing all values, they encode only the non-zero values and their indices. Common formats include:

• CSR (Compressed Sparse Row): Optimized for row-wise operations.
• CSC (Compressed Sparse Column): Optimized for column-wise operations.
• COO (Coordinate Format): Stores simple (index, value) tuples. The choice of format critically impacts the performance of sparse kernels like SpMM by dictating memory access patterns.

The fundamental computational kernel for sparse inference, which multiplies a sparse matrix by a dense matrix. It is the workhorse operation for sparse linear layers and attention in transformers. Efficient SpMM kernels implement zero-skipping to avoid unnecessary multiplications. Performance is dominated by:

• Memory bandwidth: Efficiently streaming non-zero data.
• Load balancing: Distributing irregular work across parallel threads.
• Gather-scatter overhead: The cost of collecting data from and writing to non-contiguous memory addresses.

Two primary approaches to inducing sparsity in neural network weights.

Unstructured Pruning removes individual weights based on a saliency criterion (e.g., magnitude), creating irregular, fine-grained sparsity. While it achieves high compression rates, it requires specialized kernels and hardware for acceleration.

Structured Pruning removes entire structural components like neurons, channels, or layers. This results in regular, coarse-grained sparsity (e.g., removing entire columns of a weight matrix), which is easier to accelerate on standard hardware but may lead to greater accuracy loss.

A form of fine-grained structured sparsity where, in every block of M consecutive weights (e.g., 4), only N are allowed to be non-zero (e.g., 2). This creates a predictable, regular pattern that can be efficiently encoded with a small bitmask. Modern GPU Sparse Tensor Cores (e.g., NVIDIA Ampere architecture and later) natively support 2:4 sparsity, allowing them to skip computations on zeros and effectively double theoretical compute throughput for eligible layers.

A software runtime or framework component specifically designed to load and execute sparse neural network models. It contains optimized kernels (like SpMM) tailored for target hardware (CPUs, GPUs, NPUs). Key responsibilities include:

• Parsing sparse model formats and metadata.
• Mapping sparse operations to efficient kernels.
• Managing the pruning mask during execution to skip zeroed weights.
• Potentially fusing adjacent sparse operations (e.g., linear + ReLU) to reduce overhead. Examples include specialized backends in TensorFlow Lite and PyTorch.

The observed performance difference between the theoretical speedup predicted by the reduction in FLOPs (Floating-Point Operations) and the actual speedup achieved on hardware. A model with 50% weight sparsity reduces FLOPs by half, but real-world speedup may be only 1.2x. This gap is caused by overheads inherent to sparse computation:

• Kernel Overhead: Index decoding, pointer chasing, conditional branches.
• Memory Access Irregularity: Poor cache utilization from gather-scatter patterns.
• Load Imbalance: Threads with varying amounts of non-zero work. Closing this gap is a primary goal of sparse kernel and hardware design.