Reservoir of Importance: Learning Semi-Structured Sparsity with Differentiable Masking¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/havisdino/roi
Area: Model Compression
Keywords: Semi-Structured Pruning, N:M Sparsity, Differentiable Subset Sampling, Reservoir Sampling, LLM Compression
TL;DR¶
To eliminate the combinatorial parameter and memory overhead of modeling full categorical distributions in learnable N:M pruning, RoI formulates mask learning as differentiable subset sampling via Weighted Reservoir Sampling and Gumbel-Top-K relaxation, reducing trainable parameters from \(O(\binom{M}{N})\) to \(O(M)\) while achieving superior perplexity and downstream accuracy across Qwen2.5 and Gemma-2.
Background & Motivation¶
Deploying large language models (LLMs) in resource-constrained environments demands aggressive post-training compression to mitigate substantial memory footprints and compute costs. Post-training pruning typically follows three primary paradigms: unstructured pruning, structured pruning, and semi-structured pruning. While unstructured pruning preserves representational fidelity by pruning individual weights flexibly, the absence of hardware-aligned sparsity patterns impedes practical runtime acceleration. Conversely, structured pruning eliminates coarse-grained components such as entire attention heads or MLP channels, yet frequently triggers severe degradation and catastrophic knowledge forgetting. Semi-structured pruning, specifically fine-grained N:M sparsity natively supported by modern accelerator architectures (such as NVIDIA Ampere, Hopper, and Blackwell GPUs), achieves an optimal compromise by enforcing that exactly \(N\) out of every \(M\) contiguous weights are non-zero. Early semi-structured approaches rely on static saliency heuristics—such as activation-magnitude metrics in Wanda or second-order Hessian approximations in SparseGPT. Although computationally lightweight, their efficacy hinges heavily on handcrafted criteria and limited calibration samples, which often fail to capture complex inter-layer dynamics and result in suboptimal sparsity patterns.
To overcome the inherent limitations of static heuristics, recent literature has shifted toward learnable-mask frameworks (notably MaskLLM and HyperPrune) that optimize N:M sparsity masks directly via gradient descent on calibration corpora. However, the fundamental bottleneck in existing learnable-mask strategies stems from combinatorial parameterization. These methods model each contiguous group of \(M\) weights as a categorical distribution across all \(\binom{M}{N}\) feasible binary configurations. When moving toward more aggressive or flexible sparsity patterns—such as 4:8 (70 configurations) or 2:8 (28 configurations)—or scaling up to larger base LLMs, the auxiliary parameters and optimizer states explode exponentially. For instance, achieving 2:4 sparsity requires \(1.5\times\) additional parameters relative to the base model, while 2:8 sparsity necessitates \(3.5\times\), imposing prohibitive memory traffic and GPU VRAM overhead during optimization.
Resolving this tension requires rethinking the fundamental formulation of mask learning: selecting \(N\) non-zero weights within a group does not inherently require maintaining joint discrete probabilities across the entire combinatorial configuration space, but can instead be treated as a sequential sampling-without-replacement process over the local weight pool. Grounded in stochastic variational optimization and a rigorous equivalence proof, the objective can be rewritten into a compact, linear formulation. Core idea: discard the combinatorial categorical distribution over all feasible N:M configurations in favor of a compact \(M\)-dimensional logit vector, leveraging Weighted Reservoir Sampling and Gumbel-Top-K continuous relaxation to perform differentiable subset sampling without replacement, thereby slashing learnable mask complexity from \(O(\binom{M}{N})\) to \(O(M)\).
Method¶
Overall Architecture¶
The objective of RoI (Reservoir of Importance) is to discover optimal N:M sparsity masks on calibration data via gradient descent while keeping all pre-trained LLM weights strictly frozen. The pipeline decouples into a differentiable continuous exploration phase during training and a discrete projection phase during inference. During training forward passes, each group of \(M\) contiguous weights is parameterized by a compact learnable logit vector \(\phi \in \mathbb{R}^M\). Gumbel perturbations are added to these logits to generate stochastic keys, followed by \(N\) sequential sampling steps based on Weighted Reservoir Sampling principles. At each step, a temperature-scaled Softmax produces a relaxed one-hot indicator, and an accumulated logarithmic correction removes the selected probability mass from subsequent steps. The resulting \(N\) relaxed one-hot vectors are summed into a soft N-hot mask, which multiplies the frozen weight group to compute the training cross-entropy loss. Gradients flow directly back to the logit parameters. During inference, the continuous relaxation is discarded, and an exact argtopK selection is applied directly to the trained logits to extract hardware-aligned, deterministic binary N:M masks.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input: Contiguous M Weight Group & Frozen Base LLM"] --> B["Compact Logit Variational Parameterization<br/>Assign size-M learnable logit vector"]
B --> C["Weighted Reservoir Sampling Objective<br/>Without-replacement decomposition & Theorem 1 equivalence"]
C --> D["Gumbel-Top-K Sequential Continuous Relaxation<br/>N-step iterative probability subtraction for soft N-hot mask"]
D --> E["Dual-Temperature Exponential Annealing<br/>Balance early stochastic exploration and late convergence"]
E --> F["End-to-End Backpropagation<br/>Update mask logits via causal LM loss, weights frozen"]
F --> G["Inference Output: Hardware-aligned deterministic binary N:M mask"]
Key Designs¶
1. Compact Logit Variational Parameterization: Eliminating Combinatorial Parameter Explosion In conventional categorical mask learning approaches, each pruning group must parameterize every feasible configuration independently, requiring \(\binom{M}{N}\) scalar logits. For 2:4 sparsity, this demands 6 logits per 4 weights (\(1.5\times\) relative to base parameters); for 2:8 sparsity, it explodes to 28 logits per 8 weights (\(3.5\times\)). RoI re-parameterizes the problem from a stochastic variational optimization perspective. Instead of allocating parameters over the configuration space, RoI assigns a single compact logit vector \(\phi_i = [\phi_{i1}, \dots, \phi_{iM}]\) of length \(M\) to each weight group. Each logit represents the unnormalized importance score of its corresponding weight parameter. This compact parameterization bounds the learnable degrees of freedom strictly to \(O(M)\), maintaining an invariant \(1\times\) ratio relative to the base model size regardless of the sparsity ratio or group length, completely dismantling the combinatorial memory bottleneck.
2. Weighted Reservoir Sampling Objective: Preserving Objective Equivalence and Inductive Bias Reducing the parameter space to \(O(M)\) could theoretically risk limiting representational expressiveness. To address this, the authors mathematically prove that modeling mask probabilities via Weighted Reservoir Sampling (WRS) yields an identical expected loss to sampling from the true target mask distribution (Theorem 1). Let \(S_{m_i}\) denote the collection of ordered subsets whose one-hot indicators sum to the binary mask \(m_i\). The mask probability decomposes as:
Because standard matrix operations in LLMs are invariant to the internal permutation order of non-zero entries, summing the subset probabilities preserves variational bounds without discrepancy. Crucially, this parameterization induces an advantageous inductive bias for gradient updates:
Whereas categorical methods update only one isolated mask state per gradient step, each item logit \(\phi_j\) in RoI participates in multiple feasible subset combinations. Consequently, gradient signals aggregate feedback across a combinatorial family of masks simultaneously, drastically enhancing sample efficiency and speeding up convergence on large token corpora.
3. Gumbel-Top-K Sequential Continuous Relaxation: Differentiable Subset Sampling without Replacement Discrete subset selection via argtopK is non-differentiable. RoI circumvents this via the continuous Gumbel-Top-K reparameterization trick. Independent standard Gumbel noise \(g_{ij} \sim \text{Gumbel}(0, 1)\) is added to the scaled logits to form initial stochastic keys:
Let \(\alpha_i^{(1)} = [\kappa_{i1}, \dots, \kappa_{iM}]\) be the adjusted keys at the first step. Over \(N\) sequential iterations, relaxed one-hot indicator vectors \(\mu_i^{(k)}\) are generated via temperature-scaled Softmax:
To simulate sampling without replacement, the probability mass of the selected element is iteratively subtracted from the keys using a logarithmic penalty: \(\alpha_i^{(k+1)} = \alpha_i^{(k)} + \log(1 - \mu_i^{(k)})\). Summing these relaxed indicators across all \(N\) steps produces a soft N-hot mask \(m_i = \sum_{k=1}^N \mu_i^{(k)}\). Because every mathematical operation in this formulation is smooth and continuous, loss gradients backpropagate smoothly from the objective function down to the mask logits \(\phi_i\).
4. Dual-Temperature Exponential Annealing: Balancing Exploration and Discrete Convergence In continuous relaxation frameworks, improper temperature settings can lead either to premature convergence onto suboptimal local minima or to severe train-test discrepancy. RoI decouples the stochasticity into two dedicated hyperparameters: sampling temperature \(\lambda\), which governs the magnitude of Gumbel noise perturbation and exploration breadth, and Softmax temperature \(\tau\), which controls the sharpness of the relaxed one-hot approximations. RoI deploys synchronized exponential decay schedules over the first \(T_{\text{anneal}}\) steps:
In standard runs, \(\tau\) decays exponentially from \(1.0\) down to \(0.05\), while \(\lambda\) decays from \(1.0\) down to \(0.002\) across the initial 1500 steps. This dynamic ensures broad combinatorial space exploration during early training and sharp convergence toward near-discrete binary states by the end of optimization, virtually eliminating discretization error during deployment.
Loss & Training¶
During the entire optimization phase, all underlying model parameters \(W\) are kept frozen, and only the variational mask parameters \(\Phi = \{\phi_1, \dots, \phi_G\}\) are optimized:
The calibration set \(\mathcal{D}\) comprises approximately 2 billion tokens sampled from the clean Nemotron-CC-v2 pre-training dataset. Training is conducted for 2,000 steps with a batch size of 256 and a sequence length of 4096. Logits are initialized from \(\mathcal{N}(0, 0.01)\). The optimization uses the AdamW optimizer (\(\beta_1=0.9, \beta_2=0.95\)) with a weight decay of \(0.05\) and a learning rate linearly decayed from \(1\times 10^{-3}\) to \(1\times 10^{-4}\). No auxiliary regularization losses or hyperparameter balancing terms are required.
Key Experimental Results¶
Main Results¶
RoI was evaluated across the Qwen2.5 model family (0.5B, 1.5B, 3B, 7B) under the hardware-native 2:4 sparsity pattern, benchmarked against Magnitude, Wanda, SparseGPT, ProxSparse, and MaskLLM across WikiText-2 perplexity and seven zero-shot commonsense reasoning tasks.
| Model Size | Pruning Method | W/U | WikiText-2 PPL ↓ | ARC-C | ARC-E | BoolQ | HellaSwag | PIQA | RACE | SciQ | 7-Task Avg ACC ↑ |
|---|---|---|---|---|---|---|---|---|---|---|---|
| Qwen2.5-0.5B | Dense Base | - | 18.45 | 29.01 | 64.48 | 61.80 | 40.54 | 70.51 | 34.74 | 92.90 | 56.28 |
| Magnitude | ✗ | 3.0E+4 | 19.11 | 31.19 | 38.38 | 26.65 | 54.13 | 23.06 | 43.40 | 33.70 | |
| Wanda | ✗ | 159.05 | 19.80 | 42.85 | 56.82 | 28.93 | 59.03 | 26.70 | 83.20 | 45.33 | |
| SparseGPT | ✓ | 73.78 | 19.97 | 47.22 | 59.85 | 30.80 | 60.12 | 27.85 | 84.30 | 47.16 | |
| ProxSparse | ✗ | 146.42 | 21.42 | 46.63 | 61.63 | 32.00 | 61.63 | 29.09 | 79.80 | 47.46 | |
| MaskLLM | ✗ | 35.16 | 22.16 | 54.02 | 62.10 | 32.28 | 63.41 | 30.19 | 85.90 | 50.01 | |
| RoI (Ours) | ✗ | 32.63 | 23.63 | 54.97 | 60.95 | 32.34 | 63.82 | 31.00 | 87.20 | 50.56 | |
| Qwen2.5-1.5B | Dense Base | - | 12.59 | 41.55 | 75.21 | 72.48 | 50.18 | 75.52 | 36.65 | 94.20 | 63.68 |
| Magnitude | ✗ | 5.2E+3 | 20.48 | 32.74 | 39.42 | 27.20 | 57.07 | 24.59 | 60.10 | 37.37 | |
| Wanda | ✗ | 67.97 | 24.06 | 51.26 | 63.64 | 32.36 | 62.46 | 29.28 | 88.30 | 50.19 | |
| SparseGPT | ✓ | 38.95 | 28.33 | 56.69 | 62.66 | 34.54 | 65.07 | 33.49 | 89.00 | 52.83 | |
| ProxSparse | ✗ | 28.68 | 29.25 | 59.55 | 42.87 | 39.61 | 67.25 | 32.73 | 89.80 | 51.58 | |
| MaskLLM | ✗ | 21.90 | 29.45 | 63.51 | 61.33 | 39.10 | 69.07 | 32.51 | 89.90 | 54.98 | |
| RoI (Ours) | ✗ | 21.27 | 29.37 | 63.01 | 61.93 | 39.29 | 69.31 | 32.44 | 89.90 | 55.04 | |
| Qwen2.5-3B | Dense Base | - | 12.32 | 44.62 | 77.57 | 77.22 | 55.04 | 78.29 | 38.47 | 95.90 | 66.73 |
| Magnitude | ✗ | 1.6E+6 | 23.81 | 24.66 | 37.83 | 25.98 | 51.96 | 20.77 | 18.50 | 29.07 | |
| Wanda | ✗ | 37.31 | 27.13 | 60.02 | 62.26 | 35.88 | 67.14 | 34.35 | 91.00 | 53.97 | |
| SparseGPT | ✓ | 22.82 | 31.40 | 66.12 | 62.66 | 41.05 | 69.75 | 35.12 | 92.50 | 56.94 | |
| ProxSparse | ✗ | - | - | - | - | - | - | - | - | - | |
| MaskLLM | ✗ | 19.85 | 32.95 | 66.42 | 65.11 | 43.18 | 70.44 | 35.35 | 93.00 | 58.06 | |
| RoI (Ours) | ✗ | 19.37 | 32.08 | 66.71 | 65.26 | 43.30 | 70.57 | 35.22 | 93.00 | 58.02 | |
| Qwen2.5-7B | Dense Base | - | 9.03 | 48.21 | 80.43 | 84.65 | 59.98 | 78.78 | 41.91 | 96.60 | 70.08 |
| Magnitude | ✗ | 6.5E+3 | 24.40 | 38.34 | 64.16 | 30.05 | 55.60 | 23.25 | 74.30 | 44.30 | |
| Wanda | ✗ | 20.87 | 38.99 | 72.18 | 73.21 | 44.53 | 71.87 | 35.79 | 94.50 | 61.58 | |
| SparseGPT | ✓ | 16.44 | 39.65 | 73.54 | 75.83 | 45.89 | 73.38 | 36.67 | 94.80 | 62.82 | |
| ProxSparse | ✗ | 14.91 | 38.69 | 74.46 | 74.77 | 48.63 | 73.22 | 36.08 | 95.60 | 63.06 | |
| MaskLLM | ✗ | 14.91 | 39.27 | 73.68 | 81.55 | 49.12 | 74.88 | 37.46 | 95.10 | 64.44 | |
| RoI (Ours) | ✗ | 14.89 | 38.14 | 74.20 | 82.14 | 49.04 | 75.35 | 37.80 | 95.10 | 64.54 |
Ablation Study¶
The evaluation investigates extreme 2:8 sparsity stress tests, parameter efficiency across configurations, temperature annealing schedules, and straight-through estimators.
1. Scalability and Failure Regime under 2:8 Sparsity
| Method | 2:4 Trainable Params | 2:8 Trainable Params | 0.5B PPL (2:8) ↓ | 1.5B PPL (2:8) ↓ | 3B PPL (2:8) ↓ | 7B PPL (2:8) ↓ | 7B Avg ACC (2:8) ↑ |
|---|---|---|---|---|---|---|---|
| Dense Base | - | - | 18.45 | 12.59 | 12.32 | 9.03 | 73.73 |
| Magnitude | 0 (0×) | 0 (0×) | 1.5E+7 | 1.0E+7 | 6.6E+7 | \(\infty\) | 32.50 |
| Wanda | 0 (0×) | 0 (0×) | 8.1E+5 | 1.0E+6 | 3.2E+6 | 4.7E+4 | 33.42 |
| SparseGPT | 0 (0×) | 0 (0×) | 1.1E+4 | 4.0E+4 | 257.22 | 158.70 | 46.33 |
| MaskLLM | 9.8B (1.5×) | 22.8B (3.5×) | 63.11 | 38.14 | 38.89 | 34.72 | 52.83 |
| RoI (Ours) | 6.5B (1.0×) | 6.5B (1.0×) | 61.89 | 36.87 | 37.72 | 32.33 | 53.07 |
2. Annealing Schedule and Estimator Ablations (Qwen2.5-1.5B Backbone)
| Dimension | Configuration | WikiText-2 PPL ↓ | ARC-C | BoolQ | HellaSwag | PIQA | Avg ACC ↑ |
|---|---|---|---|---|---|---|---|
| Annealing Schedule | Exponential \((\lambda=0.001, \tau=0.05)\) | 21.57 | 28.50 | 62.75 | 40.06 | 70.67 | 55.53 |
| Exponential \((\lambda=0.002, \tau=0.05)\) (Default) | 21.27 | 29.37 | 61.93 | 39.29 | 69.31 | 55.04 | |
| Exponential \((\lambda=0.003, \tau=0.05)\) | 22.29 | 29.18 | 63.85 | 39.24 | 68.55 | 54.97 | |
| Linear \((\lambda=0.001, \tau=0.05)\) | 26.80 | 28.18 | 61.70 | 38.42 | 68.21 | 53.84 | |
| Linear \((\lambda=0.002, \tau=0.05)\) | 27.04 | 27.59 | 62.11 | 37.64 | 67.53 | 53.51 | |
| Estimator Type | Straight-Through Estimator (w STE) | 30.58 | - | - | - | - | 53.10 |
| Soft Continuous Relaxation (w/o STE, RoI) | 21.27 | - | - | - | - | 55.04 |
Key Findings¶
- Collapse of Saliency Heuristics under Extreme Sparsity: In the aggressive 2:8 regime, static pruning baselines fail catastrophically (Magnitude and Wanda produce perplexities exceeding tens of thousands or infinity). Even SparseGPT degenerates severely to a PPL of 158.70 on the 7B model. Only learnable-mask strategies (RoI and MaskLLM) preserve usable capacity (PPL of 32.33 vs. 34.72), demonstrating the indispensability of gradient-based mask learning in high-sparsity scenarios.
- Dramatically Lower Optimization Footprint: In 2:4 sparsity, RoI cuts trainable parameters by 33% relative to MaskLLM (\(1.0\times\) vs. \(1.5\times\)). In 2:8 sparsity, MaskLLM's parameter overhead expands to \(3.5\times\) (22.8B auxiliary parameters on Qwen2.5-7B), whereas RoI remains strictly fixed at \(1.0\times\) (6.5B parameters, an absolute reduction of 16.3B parameters). Consequently, RoI cuts 7B training time from 55.39 to 46.10 GPU hours on NVIDIA B300.
- Superiority of Soft Continuous Relaxation over STE: Combining argtopK forward passes with backward soft relaxations (w STE) hampers optimization, driving Qwen2.5-1.5B perplexity from 21.27 up to 30.58. Premature discretization injects high estimator bias, whereas pure soft relaxation paired with annealing yields smoother optimization landscapes.
- Architectural Generalization and Serving Speedup: On Gemma2-9B under 2:4 sparsity, RoI delivers a PPL of 16.30 and 64.08% zero-shot accuracy, outperforming MaskLLM (17.25 PPL, 63.73% ACC). Furthermore, real-world deployment via vLLM on a single NVIDIA B300 GPU delivers \(1.3\times\) and \(1.27\times\) end-to-end decoding throughput acceleration for Qwen2.5-3B and 7B models, respectively.
Highlights & Insights¶
- Revisiting Mask Learning through Reservoir Sampling: Rather than treating N:M mask selection as an intractable combinatorial partition, RoI shows that sampling without replacement via Weighted Reservoir Sampling satisfies variational expectation equivalence, reducing mask parameterization to an elegant \(O(M)\) footprint.
- Implicit Gradient Sharing Across Configurations: Because each weight logit is tied directly to an individual parameter rather than an isolated configuration, gradient updates aggregate across all sampled subsets containing that weight, endowing RoI with superior statistical sample efficiency over large token budgets.
- Decoupled Dual-Temperature Dynamics: Formally separating the noise scale \(\lambda\) (governing state exploration) from the Softmax temperature \(\tau\) (governing discrete indicator peakedness) establishes a robust template for training discrete combinatorial structures with neural networks.
Limitations & Future Work¶
- Hardware Acceleration Dependency Beyond 2:4 Sparsity: While RoI readily scales algorithmically to arbitrary N:M configurations (e.g., 1:4, 2:8, 4:8), physical deployment speedups remain tightly coupled to vendor-specific kernel acceleration (principally NVIDIA Ampere/Hopper/Blackwell 2:4 Sparse Tensor Cores). The absence of dedicated hardware kernels for other patterns limits practical latency gains.
- Scope of Evaluation Architectures: The empirical analysis focuses on dense autoregressive English LLMs; evaluating RoI across Mixture-of-Experts (MoE) architectures, multimodal foundation models, and multilingual reasoning domains remains open for exploration.
- Joint Weight-Mask Co-Optimization: RoI freezes base weights throughout training. Exploring alternating optimization schemes between mask logits and low-rank weight adapters (e.g., LoRA) could recover additional accuracy margins under extreme sparsity regimes.
Related Work & Insights¶
- vs Saliency-Based Pruning (Wanda / SparseGPT): Saliency methods use zero-shot heuristics or local second-order approximations that are fast but fragile under aggressive sparsity; RoI utilizes data-driven mask learning that consistently maintains robust language generation quality even under 2:8 sparsity.
- vs MaskLLM: Both learn N:M masks via variational optimization, but MaskLLM parameterizes the full categorical configuration space (\(\binom{M}{N}\) parameters), which suffers severe memory bottlenecks under large \(M\); RoI leverages Weighted Reservoir Sampling to achieve \(O(M)\) complexity, reducing GPU training hours and scaling more favorably with training tokens.
- vs ProxSparse: ProxSparse employs deterministic proximal regularization, which converges rapidly early on but quickly suffers optimization plateaus and struggles to support 2:8 patterns; RoI uses stochastic continuous relaxations that sustain continuous exploration and monotone perplexity reduction as training data scales.
Rating¶
- Novelty: ⭐⭐⭐⭐ [Replaces combinatorial mask modeling with an elegant Weighted Reservoir Sampling formulation]
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Extensive multi-scale evaluations on Qwen2.5 and Gemma-2, 2:8 failure analysis, real vLLM throughput, and meticulous ablations]
- Writing Quality: ⭐⭐⭐⭐⭐ [Clear mathematical derivations, thorough optimization insights, and cohesive prose structure]
- Value: ⭐⭐⭐⭐⭐ [Substantially lowers the memory and parameter hurdles for scalable semi-structured LLM pruning]