Unstructured Pruning

Unstructured pruning operates at the finest granularity, targeting individual scalar weights anywhere in the network. This creates a highly irregular sparsity pattern where zeros are scattered randomly throughout the weight tensors. Unlike structured pruning, it does not remove coherent structures like entire filters or channels.

• Advantage: Offers the highest theoretical compression rate, as any single parameter can be removed.
• Challenge: The irregular memory access pattern makes efficient computation on standard dense hardware (GPUs/CPUs) difficult without specialized libraries.

The irregular sparsity from unstructured pruning does not align with the SIMD (Single Instruction, Multiple Data) architectures of standard GPUs, which excel at dense, regular computations. Executing a sparse model naively can be slower than its dense counterpart due to overhead from indexing zero values.

Efficient execution requires:

• Sparse Kernels: Specialized CUDA kernels or libraries like cuSPARSE that skip multiplications with zeros.
• Sparse Tensor Cores: Modern hardware (e.g., NVIDIA Ampere GPUs with 2:4 sparsity) provides dedicated support for specific, structured sparse patterns (N:M sparsity), which is a hardware-friendly subset of unstructured pruning.

The decision of which specific weights to remove is governed by a pruning criterion. The most common heuristic is:

• Magnitude-Based Pruning: Removes weights with the smallest absolute values (L1 norm), under the assumption they contribute least to the model's output. This is the foundation of the Iterative Magnitude Pruning (IMP) algorithm.

Other advanced criteria include:

• Gradient-Based (Movement Pruning): Removes weights based on how much their value changes during training.
• Saliency-Based (SNIP): Scores weights at initialization by their estimated effect on the loss function.

Unstructured pruning is rarely a one-step process. Aggressive pruning induces an accuracy drop. To recover performance, a cycle of pruning and retraining is used:

1. Prune a small percentage (e.g., 20%) of the smallest-magnitude weights.
2. Fine-tune the remaining sparse network on the training data.
3. Repeat steps 1 and 2 until the target sparsity (e.g., 90% zeros) is reached.

This iterative process allows the network to adapt and reallocate representational capacity to the remaining weights. Techniques like rewinding (resetting weights to an earlier training checkpoint) are often used during fine-tuning to improve recovery.

To realize memory savings, pruned models are stored using sparse matrix formats rather than dense arrays. Common formats include:

• COO (Coordinate Format): Stores tuples of (row, column, value) for each non-zero weight. Simple but can have high memory overhead for indices.
• CSR/CSC (Compressed Sparse Row/Column): Compresses row or column indices, reducing overhead. More efficient for computation.

These formats store only the non-zero values and their locations, but the indexing data creates a memory overhead. The compression ratio is the size of the dense format divided by the size of the sparse format.

Unstructured pruning is central to the Lottery Ticket Hypothesis. This research found that within a dense, randomly-initialized network, there exist sparse subnetworks ('winning tickets') that, when trained in isolation from their initial weights, can match the performance of the full network.

• Implication: Not all sparsity is equal. Pruning can find optimal sparse architectures, not just compress existing ones.
• Finding Winning Tickets: Requires the iterative magnitude pruning and rewinding process, highlighting the importance of the pruning schedule and weight resetting.

The most common and intuitive criterion, where weights with the smallest absolute values (L1 norm) are considered least important and pruned first. This heuristic is based on the assumption that small-magnitude weights contribute minimally to the network's output.

• Algorithm Example: Iterative Magnitude Pruning (IMP) applies this criterion in cycles of pruning and fine-tuning.
• Advantage: Simple to implement and computationally cheap.
• Limitation: May not always correlate with true saliency, as a small weight with a large input activation can still be significant.

These methods use gradient information—the sensitivity of the loss function to a weight—as an importance score. Weights with the smallest gradient magnitudes are pruned.

• Movement Pruning: Prunes weights based on how much their value changes during training, not their final magnitude. Weights that move little are removed.
• Advantage: Can capture importance more dynamically than static magnitude.
• Limitation: Requires maintaining and computing gradients, adding overhead during the pruning process.

Advanced single-shot methods that prune at initialization, before any training. They estimate a connection's importance by its effect on the loss.

• SNIP (Single-shot Network Pruning): Scores weights using the gradient of the loss with respect to the weight, multiplied by the weight itself (|gradient * weight|).
• GRASP (Gradient Signal Preservation): Extends this by considering how pruning a weight affects the gradient flow to other weights.
• Use Case: For rapid, training-free sparsification when retraining is not feasible.

Instead of post-hoc removal, these techniques encourage sparsity during training by adding a penalty term to the loss function.

• L1 Regularization: Adds a cost proportional to the sum of absolute weight values, pushing many weights toward zero.
• L0 Regularization: A more direct but non-differentiable sparsity penalty on the number of non-zero weights.
• Advantage: Produces models inherently robust to sparsity, integrating pruning into the learning objective.
• Result: The trained model is already sparse, often requiring less fine-tuning.

These algorithms do not make a single, irreversible pruning decision. They allow for the reactivation of weights.

• Dynamic Network Surgery: Iteratively cuts (prunes) and splices (re-grows) connections during training based on a real-time importance criterion.
• Advantage: More adaptive; can recover from erroneous pruning decisions.
• Iterative Magnitude Pruning (IMP): The canonical iterative algorithm: train → prune lowest-magnitude weights → retrain. Often coupled with rewinding, where weights are reset to an earlier training checkpoint before retraining.

While unstructured pruning is 'unstructured' by definition, some algorithms now target hardware-efficient sparse patterns to accelerate inference without specialized libraries.

• N:M Sparsity: A semi-structured pattern where in every block of M consecutive weights, at most N are non-zero (e.g., 2:4 sparsity). This pattern is natively supported on NVIDIA Ampere+ GPUs for 2x speedup.
• Algorithm Goal: Prune to meet this pattern while minimizing accuracy loss.
• Benefit: Bridges the gap between the high compression of unstructured pruning and the efficient execution of structured pruning.

Structured pruning removes entire, structurally coherent groups of weights—such as filters, channels, or attention heads—resulting in a smaller, dense model. Unlike unstructured pruning, it maintains hardware-friendly execution patterns, allowing for immediate speedups on standard hardware (CPUs/GPUs) without requiring specialized sparse kernels.

• Key Examples: Pruning entire convolutional filters or transformer attention heads.
• Primary Trade-off: Easier deployment but potentially greater loss of model capacity compared to fine-grained unstructured methods.

A sparsity pattern defines the specific locations of zero-valued weights within a pruned neural network. This pattern is the output of a pruning algorithm and determines the model's memory layout and computational requirements.

• In unstructured pruning, the pattern is irregular and random.
• In structured pruning (e.g., N:M sparsity), the pattern follows a predefined, hardware-friendly format.
• The pattern is often stored in a compressed format (like CSR or CSC) to avoid allocating memory for zeros.

N:M sparsity is a semi-structured sparsity pattern where, for every block of M consecutive weights (typically along the input or output dimension), at most N are non-zero. This balances the flexibility of unstructured pruning with the execution efficiency of structured pruning.

• Hardware Support: Efficiently executed on modern GPUs like NVIDIA's Ampere architecture using the Sparse Tensor Core feature.
• Example: 2:4 sparsity is common, where 50% of weights are pruned but with a regular pattern that allows for 2x theoretical speedup in matrix multiplication.

A pruning criterion is the metric or heuristic used to determine which weights or structures are least important and can be removed. The choice of criterion is fundamental to the pruning algorithm's effectiveness.

• Common Criteria for Unstructured Pruning:
  • Magnitude (L1/L2 Norm): Removes weights with the smallest absolute values.
  • Gradient-Based (e.g., Movement Pruning): Removes weights based on how their value changes during training.
  • Saliency (e.g., SNIP): Estimates a connection's effect on the loss function.
• The criterion directly influences the final sparsity pattern and the resulting accuracy drop.

Sparse fine-tuning is the process of retraining a pruned neural network on a task-specific dataset to recover the accuracy lost during the pruning process. The sparsity pattern (the locations of the zeros) is typically held fixed.

• Purpose: Allows the remaining weights to adapt and compensate for the removed connections.
• Contrast with Training from Scratch: The pruned subnetwork (the 'winning ticket' from the Lottery Ticket Hypothesis) often fine-tunes more efficiently than a randomly initialized sparse network.
• A critical step in iterative pruning pipelines like Iterative Magnitude Pruning (IMP).

Sparse matrix multiplication (SpMM) is the fundamental computational kernel for executing unstructured pruned models. It is optimized for multiplying matrices where a large proportion of elements are zero, skipping computations involving those zeros.

• Performance Challenge: Achieving speedups over dense multiplication requires the sparse pattern to be predictable enough for efficient memory access and parallelization.
• Hardware Support: Requires specialized libraries (e.g., cuSPARSE) or compiler optimizations. Pure unstructured sparsity often fails to achieve theoretical speedups on general-purpose hardware due to irregular memory access patterns.