TSENOR: Highly-Efficient Algorithm for Finding Transposable N:M Sparse Masks

• URL: http://arxiv.org/abs/2505.23949v1
• Date: Thu, 29 May 2025 18:59:43 GMT
• Title: TSENOR: Highly-Efficient Algorithm for Finding Transposable N:M Sparse Masks
• Authors: Xiang Meng, Mehdi Makni, Rahul Mazumder,
• Abstract summary: Network pruning reduces the computational requirements of large neural networks.<n>N:M sparsity retains only N out of every M consecutive weights.<n>Transposable N:M sparsity has been proposed to address this limitation.
• Score: 12.33715367032615
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Network pruning reduces the computational requirements of large neural networks, with N:M sparsity -- retaining only N out of every M consecutive weights -- offering a compelling balance between compressed model quality and hardware acceleration. However, N:M sparsity only accelerates forward-pass computations, as N:M patterns are not preserved during matrix transposition, limiting efficiency during training where both passes are computationally intensive. While transposable N:M sparsity has been proposed to address this limitation, existing methods for finding transposable N:M sparse masks either fail to scale to large models or are restricted to M=4 which results in suboptimal compression-accuracy trade-off. We introduce an efficient solver for transposable N:M masks that scales to billion-parameter models. We formulate mask generation as optimal transport problems and solve through entropy regularization and Dykstra's algorithm, followed by a rounding procedure. Our tensor-based implementation exploits GPU parallelism, achieving up to 100x speedup with only 1-10% error compared to existing methods. Our approach can be integrated with layer-wise N:M pruning frameworks including Wanda, SparseGPT and ALPS to produce transposable N:M sparse models with arbitrary N:M values. Experiments show that LLaMA3.2-8B with transposable 16:32 sparsity maintains performance close to its standard N:M counterpart and outperforms standard 2:4 sparse model, showing the practical value of our approach.

Related papers

• MaskPro: Linear-Space Probabilistic Learning for Strict (N:M)-Sparsity on Large Language Models [53.36415620647177]
  Semi-structured sparsity offers a promising solution by strategically retaining $N$ elements out of every $M$ weights.<n>Existing (N:M)-compatible approaches typically fall into two categories: rule-based layerwise greedy search, which suffers from considerable errors, and gradient-driven learning, which incurs prohibitive training costs.<n>We propose a novel linear-space probabilistic framework named MaskPro, which aims to learn a prior categorical distribution for every $M$ consecutive weights and subsequently leverages this distribution to generate the (N:M)-sparsity throughout an $N$-way sampling
  arXiv  Detail & Related papers  (2025-06-15T15:02:59Z)
• Two Sparse Matrices are Better than One: Sparsifying Neural Networks with Double Sparse Factorization [0.0]
  We present Double Sparse Factorization (DSF), where we factorize each weight matrix into two sparse matrices. Our method achieves state-of-the-art results, enabling unprecedented sparsification of neural networks.
  arXiv  Detail & Related papers  (2024-09-27T15:48:39Z)
• Bypass Back-propagation: Optimization-based Structural Pruning for Large Language Models via Policy Gradient [57.9629676017527]
  We propose an optimization-based structural pruning on Large-Language Models. We learn the pruning masks in a probabilistic space directly by optimizing the loss of the pruned model. Our method operates for 2.7 hours with around 35GB memory for the 13B models on a single A100 GPU.
  arXiv  Detail & Related papers  (2024-06-15T09:31:03Z)
• Efficient N:M Sparse DNN Training Using Algorithm, Architecture, and Dataflow Co-Design [15.47240906902083]
  This paper presents a computation-efficient training scheme for N:M sparse DNNs using algorithm, architecture, and dataflow co-design. At the algorithm level, a bidirectional weight pruning method, dubbed BDWP, is proposed to leverage the N:M sparsity of weights. At the architecture level, a sparse accelerator for DNN training, namely SAT, is developed to support both the regular dense operations and the computation-efficient N:M sparse operations.
  arXiv  Detail & Related papers  (2023-09-22T17:26:19Z)
• Bi-directional Masks for Efficient N:M Sparse Training [64.9617631724811]
  We present a novel method of Bi-directional Masks (Bi-Mask) with its two central innovations. It disentangles the forward and backward weight sparsity and overcomes the very dense gradient. Compared with existing uni-directional scenario that applies a transposable mask and enables backward acceleration, our Bi-Mask is experimentally demonstrated to be more superior in performance.
  arXiv  Detail & Related papers  (2023-02-13T02:32:02Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Sample-Then-Optimize Batch Neural Thompson Sampling [50.800944138278474]
  We introduce two algorithms for black-box optimization based on the Thompson sampling (TS) policy. To choose an input query, we only need to train an NN and then choose the query by maximizing the trained NN. Our algorithms sidestep the need to invert the large parameter matrix yet still preserve the validity of the TS policy.
  arXiv  Detail & Related papers  (2022-10-13T09:01:58Z)
• LUT-GEMM: Quantized Matrix Multiplication based on LUTs for Efficient Inference in Large-Scale Generative Language Models [9.727062803700264]
  We introduce LUT-GEMM, an efficient kernel for quantized matrix multiplication. LUT-GEMM eliminates the resource-intensive dequantization process and reduces computational costs. We show experimentally that when applied to the OPT-175B model with 3-bit quantization, LUT-GEMM substantially accelerates token generation latency.
  arXiv  Detail & Related papers  (2022-06-20T03:48:17Z)
• Mixed Precision Low-bit Quantization of Neural Network Language Models for Speech Recognition [67.95996816744251]
  State-of-the-art language models (LMs) represented by long-short term memory recurrent neural networks (LSTM-RNNs) and Transformers are becoming increasingly complex and expensive for practical applications. Current quantization methods are based on uniform precision and fail to account for the varying performance sensitivity at different parts of LMs to quantization errors. Novel mixed precision neural network LM quantization methods are proposed in this paper.
  arXiv  Detail & Related papers  (2021-11-29T12:24:02Z)
• NxMTransformer: Semi-Structured Sparsification for Natural Language Understanding via ADMM [16.464030458567187]
  We introduce a new learning framework, called NxMTransformer, to induce NxM semi-structured sparsity on pretrained language models. We propose to formulate the NxM sparsity as a constrained optimization problem and use Alternating Direction Method of Multipliers (ADMM) to optimize the downstream tasks. Our proposed method is able to achieve 1.7 points higher accuracy in GLUE score than current practices.
  arXiv  Detail & Related papers  (2021-10-28T17:43:06Z)
• 8-bit Optimizers via Block-wise Quantization [57.25800395197516]
  Statefuls maintain statistics over time, e.g., the exponentially smoothed sum (SGD with momentum) or squared sum (Adam) of past values. This state can be used to accelerate optimization compared to plain gradient descent but uses memory that might otherwise be allocated to model parameters. In this paper, we develop first gradients that use 8-bit statistics while maintaining the performance levels of using 32-bit gradient states.
  arXiv  Detail & Related papers  (2021-10-06T15:43:20Z)
• n-hot: Efficient bit-level sparsity for powers-of-two neural network quantization [0.0]
  Powers-of-two (PoT) quantization reduces the number of bit operations of deep neural networks on resource-constrained hardware. PoT quantization triggers a severe accuracy drop because of its limited representation ability. We propose an efficient PoT quantization scheme that balances accuracy and costs in a memory-efficient way.
  arXiv  Detail & Related papers  (2021-03-22T10:13:12Z)
• Accelerated Sparse Neural Training: A Provable and Efficient Method to Find N:M Transposable Masks [28.498176073737422]
  Recently, researchers proposed pruning deep neural network weights (DNNs) using an $N:M$ fine-grained block sparsity mask. We propose a novel transposable-fine-grained sparsity mask where the same mask can be used for both forward and backward passes. Our experiments suggest 2x speed-up with no accuracy degradation over vision and language models.
  arXiv  Detail & Related papers  (2021-02-16T12:44:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.