Research map / Architectures and efficiency / Pruning and efficient tuning
TSENOR: Highly-Efficient Algorithm for Finding Transposable N:M Sparse Masks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes TSENOR, an entropy-regularized optimal-transport solver (Dykstra's algorithm plus GPU-vectorized greedy-and-local-search rounding) for transposable N:M sparse masks that scales to billion-parameter LLMs and plugs into Wanda, SparseGPT and ALPS.
Problem
Finding transposable N:M sparse masks, which preserve N:M structure in both a weight matrix and its transpose so backward passes are accelerated, is computationally infeasible at LLM scale with existing exact solvers, and heuristics or 2:4-only methods give suboptimal accuracy.
Approach
Reformulate per-M×M-block transposable mask selection as a capacitated optimal transport problem, solve its entropy-regularized relaxation with Dykstra's KL-projection algorithm, then round to a binary mask with a tensor-vectorized greedy selection plus swap-based local search, processing millions of blocks in parallel on GPU.
Key results
- TSENOR achieves roughly 1-10% relative error versus optimal masks, with 2-Approximation as the best competing heuristic, and up to 300x runtime speedup over exact network flow on 8192x8192 matrices.
- On LLaMA3.2-3B at 16:32 sparsity, TSENOR+ALPS reaches 58.06 zero-shot average versus 59.30 for non-transposable ALPS and 55.10 for TSENOR+SparseGPT.
- Transposable 16:32 sparsity with TSENOR+ALPS outperforms standard 2:4 SparseGPT-pruned models, per the paper's abstract claim.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use TSENOR+ALPS for transposable 16:32 instead of standard ALPS 16:32 | LLaMA3.2-3B · C4 | perplexity: 16.74 -> 18.03 | Hurt |
| Use TSENOR+ALPS for transposable 16:32 instead of standard ALPS 16:32 | LLaMA3.2-3B · zero-shot average | accuracy: 59.30 -> 58.06 | Hurt |
| Use TSENOR+ALPS for transposable 8:32 instead of standard ALPS 8:32 | LLaMA3.2-3B · C4 | perplexity: 80.12 -> 111.36 | Hurt |
| Add specialized greedy selection and local search to entropy-based mask rounding (ablation) | TSENOR mask generation · transposable N:M masks | relative error: reducing error by up to 10× | Helped |
| Add greedy selection to simple row-then-column rounding (ablation) | TSENOR mask generation · transposable N:M masks | relative error: 50-90% | Helped |
| Add local search after greedy rounding (ablation) | TSENOR mask generation · transposable N:M masks | relative error: up to an additional 50% | Helped |
| Apply rounding to the entropy-regularized approximate mask rather than directly to weight magnitudes (ablation) | TSENOR mask generation · transposable N:M masks | relative error: less than 5% error | Helped |
| Vectorize rounding on CPU (ablation) | TSENOR rounding · 8:16 mask generation | speedup: 8× | Helped |
| Run Dykstra on GPU rather than CPU (ablation) | TSENOR Dykstra method · 8:16 mask generation | speedup: up to 300× | Helped |
| Run rounding on GPU rather than baseline CPU (ablation) | TSENOR rounding · 8:16 mask generation | speedup: up to 3000× | Helped |
Surprising findings
- TSENOR+Wanda at transposable 16:32 collapses to perplexity 436 on C4, showing Wanda integration fails badly for transposable masks.
- Fine-tuning with Bi-NM performs slightly better than TSENOR+ALPS at M=4, so the advantage of the proposed approach only appears at larger M.
Limitations
- Transposable constraints degrade accuracy at small M (e.g., 8:32 TSENOR+ALPS trails non-transposable ALPS), and Wanda integration performs very poorly.
- The method does not find the globally optimal mask; the rounding is heuristic and the paper does not deliver an end-to-end training speedup.
- Evaluation of fine-tuning is limited to LLaMA3.2-1B and a single C4 shard.
Experimental setup
Datasets: C4 WikiText2 PTB LLaMA3 weight blocks
Benchmarks: WikiText2 PTB C4 PIQA HellaSwag ARC-E ARC-C Winogrande RTE OpenbookQA BoolQ
Metrics: relative error runtime (seconds) perplexity zero-shot accuracy speedup
Baselines: Network Flow cuPDLP 2-Approximation Bi-NM Max1000 SparseGPT ALPS Wanda
Builds on: Wanda SparseGPT ALPS Bi-NM cuPDLP
Closest papers by meaning
- BAME: Block-Aware Mask Evolution for Efficient N:M Sparse Training (ICML 2025 · similarity 0.86)
- 3BASiL: An Algorithmic Framework for Sparse plus Low-Rank Compression of LLMs (NeurIPS 2025 · similarity 0.86)
- Effective Interplay between Sparsity and Quantization: From Theory to Practice (ICLR 2025 · similarity 0.85)
- Sparse maximal update parameterization: A holistic approach to sparse training dynamics (NeurIPS 2024 · similarity 0.85)
- Sparsest Models Elude Pruning: An Exposé of Pruning’s Current Capabilities (ICML 2024 · similarity 0.85)
- Sparse Cocktail: Every Sparse Pattern Every Sparse Ratio All At Once (ICML 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.