Sparsity Pattern

The fundamental distinction in sparsity patterns is between structured and unstructured sparsity.

• Unstructured Sparsity: Individual weights are pruned anywhere in the network, creating an irregular, random-like pattern of zeros. While highly flexible and capable of high sparsity rates, it requires specialized software libraries (e.g., cuSPARSELt) or hardware support for efficient computation, as standard dense matrix multiplication cannot skip the zeros.
• Structured Sparsity: Entire, coherent groups of weights are removed together. Common patterns include:
  • Filter/Channel Pruning: Removing entire 3D filters from a convolutional layer or channels from a feature map.
  • Attention Head Pruning: Removing entire heads in a transformer's multi-head attention block.
  • Block Sparsity: Pruning contiguous blocks of weights (e.g., 4x4 blocks within a weight matrix). Structured patterns result in a smaller, dense model that can run efficiently on standard hardware but offers less fine-grained control over which specific parameters are removed.

The practical utility of a sparsity pattern is determined by how well it maps to hardware capabilities. A key innovation is N:M Sparsity (e.g., 2:4 or 4:8), a semi-structured pattern.

• In an N:M pattern, for every block of M consecutive weights (often along the input channel dimension), at most N are non-zero. For example, in a 2:4 pattern, a block of 4 weights must have 2 zeros.
• This pattern is hardware-friendly because it allows for compression in memory and enables the use of specialized sparse tensor cores, like those in NVIDIA's Ampere and Hopper architectures. These cores can skip the multiplication of the zero elements, providing a theoretical 2x speedup for 2:4 sparsity without requiring a complete redesign of the computational units.
• The pattern balances the high compression of unstructured sparsity with the execution efficiency of structured sparsity.

Granularity refers to the smallest unit of weights that the sparsity pattern can independently target for pruning. It exists on a spectrum:

• Fine-Grained (Element-wise): The pattern can specify the sparsity of individual scalar weights. This is the granularity of unstructured pruning. It offers maximum flexibility but the most challenging execution overhead.
• Vector/Group Granularity: The pattern prunes groups of weights, such as all weights connected to a single input feature (a column) or all weights in a small 1D vector. This is more structured than element-wise.
• Kernel/Filter Granularity: The pattern removes entire 2D kernels in a convolutional layer. This is a common form of structured pruning.
• Channel/Layer Granularity: The coarsest granularities, where entire 3D channels or whole network layers are removed. This drastically alters the model architecture but guarantees efficient dense execution. The choice of granularity is a trade-off between the potential compression ratio and the ease of achieving hardware acceleration.

Sparsity patterns can be fixed at compile-time or change during runtime.

• Static Sparsity: The pattern of zeros is determined once during the pruning/fine-tuning phase and remains fixed for all inputs during inference. This is the most common approach. The zero locations are known ahead of time, allowing for:
  • Model compression (storing only non-zero values and their indices).
  • Kernel optimization and pre-computation of execution plans.
  • Examples include patterns from iterative magnitude pruning or N:M constrained pruning.
• Dynamic Sparsity: The pattern of active (non-zero) weights varies for each input sample during inference. This is inherent in Mixture of Experts (MoE) models, where a router network dynamically selects a subset of experts for each token. The computational graph changes per input.
  • While powerful, dynamic sparsity introduces overhead for routing logic and can complicate batching and memory allocation, making it more challenging to optimize for peak throughput.

The sparsity pattern directly defines two critical inference costs: memory footprint and computational workload.

• Memory Layout: A sparse model must store both the non-zero weight values and their indices (the sparsity pattern). Efficient formats like Compressed Sparse Row (CSR) or Compressed Sparse Column (CSC) are used. Hardware-friendly patterns like N:M use more efficient metadata (e.g., bitmasks). The pattern determines the compression ratio and the overhead of the index data.
• Computational Kernels: The pattern dictates the type of matrix multiplication kernel used:
  • Dense GEMM: Used for structured patterns that result in smaller, dense matrices.
  • Sparse GEMM (SpGEMM): Required for unstructured patterns. Performance depends heavily on the regularity of the pattern; highly irregular patterns cause thread divergence and poor cache utilization on GPUs.
  • Structured Sparse GEMM: Specialized kernels for patterns like N:M that can leverage tensor cores. The optimal pattern minimizes the FLOPs * (1/Efficiency) product, where Efficiency is the hardware's utilization rate when executing that specific pattern.

Not all sparsity patterns are equally benign to model accuracy. The pattern imposes a constraint on the model's learning capacity.

• Accuracy Recovery Difficulty: After applying a pruning pattern, the network is fine-tuned to recover accuracy. Highly restrictive patterns (e.g., very coarse-grained structured pruning) may permanently remove necessary representational capacity, leading to an unrecoverable accuracy ceiling. More flexible patterns (fine-grained unstructured) are typically easier to recover from.
• Pattern-Aware Training: Modern techniques like Pruning-Aware Training or Gradual Pruning incorporate the target sparsity pattern (or its constraints) into the training loop itself. This allows the network to adapt its learning to the forthcoming structural limitations, often yielding better final accuracy than applying the pattern post-training.
• Layer-Wise Sensitivity: The optimal sparsity pattern often varies per layer. Convolutional layers may tolerate different patterns (e.g., channel pruning) compared to transformer attention layers (e.g., head pruning). Sensitivity analysis is used to apply more aggressive patterns to robust layers and more conservative ones to sensitive layers.

Unstructured sparsity removes individual weights based on an importance criterion (e.g., smallest magnitude), creating an irregular, random-like pattern of zeros. This is the most flexible form of pruning, often achieving the highest theoretical compression rates.

• Key Characteristic: Irregular, fine-grained zeros scattered throughout weight tensors.
• Hardware Challenge: Standard dense matrix multiplication hardware (like GPUs) cannot efficiently skip zero computations, often negating theoretical speedups without specialized libraries (e.g., cuSPARSE) or sparsity-aware kernels.
• Use Case: Primarily for reducing model size for storage and transmission. Real inference acceleration typically requires 90%+ sparsity to overcome overhead.

N:M sparsity is a hardware-friendly, semi-structured pattern where for every block of M consecutive weights (e.g., within a single vector), at most N are non-zero. A common format is 2:4 sparsity (50% sparse).

• Key Characteristic: Coarse-grained, predictable pattern enforced at a small block level.
• Hardware Advantage: Directly supported by modern NVIDIA Ampere/Ada/Hopper GPUs via Sparse Tensor Cores. These units can skip zero multiplications, delivering up to 2x theoretical throughput for matrix operations.
• Use Case: The standard for production inference optimization where latency and throughput are critical, balancing flexibility with guaranteed hardware acceleration.

This is a form of coarse-grained structured pruning. Entire filters (in convolutional layers) or channels/neurons (in fully-connected layers) are removed, resulting in a smaller, dense model.

• Key Characteristic: Removes entire structural units, altering the layer's output dimensions.
• Result: Produces a genuinely smaller, dense network. The pruned model requires no special sparse software or hardware; it uses standard, highly optimized dense kernels.
• Use Case: Ideal for edge deployment on hardware without sparse acceleration support. Simplifies the deployment pipeline but offers less granular compression than fine-grained methods.

A transformer-specific structured pruning technique that removes entire multi-head attention units. This reduces the computational complexity of the quadratic self-attention operation.

• Key Characteristic: Prunes at the level of attention heads, which are largely independent computational pathways.
• Impact: Directly reduces the dimensions of the Query, Key, and Value projection matrices and the subsequent computation in the attention mechanism.
• Use Case: Optimizing transformer models (e.g., BERT, GPT variants) for inference. Research shows many heads are redundant, and selective pruning can maintain accuracy while improving latency.

A generalization of structured sparsity where weights are grouped into larger, contiguous blocks (e.g., 4x4, 8x8 sub-matrices), and entire blocks are pruned based on a collective importance score.

• Key Characteristic: Mid-grained sparsity that balances regularity and flexibility.
• Advantage: More efficient than unstructured sparsity on CPUs and some accelerators, as blocked formats reduce metadata overhead for tracking zeros.
• Use Case: Effective in software-based inference runtimes (e.g., ONNX Runtime, XNNPACK) where custom kernels can leverage the block structure for vectorized operations.

In computer vision, especially for convolutional neural networks (CNNs), patterns can be designed to align with the data's spatial structure.

• Examples:
  • Kernel Pattern: Pruning specific weights within a convolutional kernel (e.g., creating a cross-shaped or center-focused pattern).
  • Feature Map Pattern: Pruning entire feature maps (channels) that contribute least to the final output.
• Rationale: Exploits the spatial locality and translation invariance inherent in images. Certain patterns may be more resilient to accuracy loss than random unstructured pruning.
• Use Case: Optimizing CNNs for mobile vision tasks where both accuracy and efficiency are paramount.

Unstructured pruning removes individual weights based on an importance criterion like magnitude, creating an irregular sparsity pattern. This results in maximum theoretical compression but requires specialized software libraries (e.g., cuSPARSELt) or hardware support for sparse tensor cores to achieve speedups, as standard dense matrix multiplication is inefficient.

Structured pruning removes entire groups of weights—such as filters, channels, or attention heads—resulting in a regular, coarse-grained sparsity pattern. This produces a smaller, dense model that maintains hardware-friendly execution patterns on standard GPUs and CPUs without requiring specialized sparse kernels, often at the cost of less fine-grained compression.

The fundamental computational kernel for executing models with unstructured sparsity patterns. It skips multiplications involving zero values. Efficiency depends entirely on the sparsity pattern and hardware support:

• Structured patterns (e.g., N:M) enable predictable memory access and vectorized instructions.
• Irregular patterns require indirect indexing and compression formats like CSR (Compressed Sparse Row) or CSC (Compressed Sparse Column), adding overhead.

The algorithm that determines which weights become zeros, thus defining the sparsity pattern. Common criteria include:

• Magnitude-based: Prune smallest absolute values (L1 norm).
• Gradient-based (Movement Pruning): Prune weights that change the least during training.
• Saliency-based (SNIP): Prune connections with the smallest estimated effect on the loss. The choice directly impacts the final pattern's efficiency and the model's recoverable accuracy.

A neural network where a significant proportion of parameters are exactly zero, forming its sparsity pattern. This is the end product of pruning or sparsification. Key characteristics:

• Storage: Uses compressed formats (e.g., COO, CSR) to save memory.
• Computation: Requires inference engines with sparse-aware runtimes.
• Goal: To reduce the model's FLOPs (Floating Point Operations) and memory footprint without proportionally degrading task accuracy.