TSENOR: Highly-Efficient Algorithm for Finding Transposable N:M Sparse Masks
Authors: Xiang Meng
Mehdi Makni
Rahul Mazumder
Venue: NeurIPS 2025 poster ()
Keywords: large language models
network pruning
N:M sparsity
optimization
entropy regularization
optimal transport
Primary area: optimization

Abstract: Network pruning reduces 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 100× 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.  Our code is available at https://github.com/mazumder-lab/TSENOR.

TSENOR: Highly-Efficient Algorithm for Finding Transposable N:M Sparse Masks
Xiang Meng
Mehdi Makni
Operations Research Center Massachusetts Institute of Technology mengx@mit. edu
Operations Research Center
Massachusetts Institute of Technology mmakni @mi ioritt.a edu
Rahul Mazumder
Operations Research Center
Massachusetts Institute of Technology rahulmaz@mit edu
Abstract
Network pruning reduces computational requirements of large neural networks, with N:M sparsity-retaining only N out of every M consecutive weights-offering compelling balance between compressed model quality and hardware accelera- tion. However, N:M sparsity only accelerates forward-pass computations, N:M patterns are not preserved during matrix transposition, limiting efficiency during training where both passes 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-accuray trade-off. We introduce efficient solver for transposable N:M masks that scales to billion billion-parameteo parameter models. We formulate mask generation as optimal transport problems and solve through entropy regularization and Dykstra's 's algorithm, followed by rounding procedure. Our tensor-ban tensor-based implementation exploits GPU parallelism, achieving up 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.22811 with transposable 16:32 sparsity maintains performance close its standard N:M counterpart and outperforms standard 2:4 sparse model, showing the practical value of our approach. Our code is available at //tttss://githhii com/mazunder lab/TSENOR
Introduction
Deep neural networks (DNNs) have become ubiquitous across multiple fields, notably in natural language processing, speech recognition, and autonomous systems [Brown et al.) 2020 Radford al. 2023 Chen et al.) 2024 While these models achieve remarkable performance, they come with substantial computational and storage requirements. State-of-the-art models, such as GPT-4
Achiam al. (2023 and LLaMA3 Dubey et al. [2024), contain hundreds of billions of parameters, necessitating multiple high-end GPUs for both training and inference. This massive scale poses significant challenges for real-world deployment and increases energy consumption [Wu et al. 2022
To address these challenges, various model compression techniques have been proposed, including quantization [Lin al.] 2023b Dettmers et al. 2023], knowledge distillation [Gou et al.) [021]
and network pruning [[an et al. 2013 Cheng et al. 2024 Network pruning reduces model size
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

by eliminating redundant or less important weights and can be categorized into unstructured and structured approaches. Unstructured pruning (Benbaki et al. 2023 Frantar and Alistarh| [023] and related variants Meng et al. [2024b] removes individual weights regardless of their position, achieving high compression ratios with minimal accuracy degradation. However, often fails to deliver practical acceleration on commodity hardware due to irregular memory access patterns and the overhead of encoding sparse structures (Zhu et al. 2019 Tang et al. 2021]. In contrast, structured pruning [Wen] et al. 2016 He et al. 2017 Meng et al.] removes entire structural components (channels, filters, heads) and is more hardware- friinddll but typically results in greater accuracy loss at high sparsity levels.
N:M sparsity- where only N out of every M consecutive weights are retained offers compelling middle ground. This fine- tne-grained structured sparsity maintains unstructured pruning benefits while
enabling hardware acceleration NNvidia 2020 Lin et al.
2023a Despite advances N:M sparsity
methods [Mishra et al. 2022 Zhou et al. [022 Lu et al. 2023 Sun et al., [023] Meng et al., 2024a
Bambhaniya et al. |024]LLucas Lucas and Mazumder], a eritical limitation persists: they accelerate only
forward-pass operations (Y W X) but not backward-pass operations (0L/0X = W aL/OY)
as N:M sparsity patterns are not preserved during matrix transposition. Consequently, N:M sparsity only provide partial acceleration during training, where both forward and backward passes are computationally intensive.
Transposable N:M sparsity addresses this by designing patterns that maintain N:M structure in both a matrix and its transpose. Despite its usefulness and promise, finding transposable N:M sparse masks presents significant algorithmic challenges. Due to lack of efficient algorithms, the full potential of transposable N:M sparsity perhaps remains to be realized a key motivation of our work. Interesting prior works include: Hubara et al.] [2021a] compute the transposable mask via minimum-cos flow. which is computationally expensive and does not scale to LLMs with billions of parameters; HHu et al. 2024 solve the special case of transposable 2:4 masks for transformers efficiently through exhaustive search, but their method cannot be generalized to larger M values (28) as the size of search space grows exponentially fast. Transposable 2:4 sparsity imposes strong structural constraints that can adversely affect model accuracy compared to larger N:M values.
T In this paper, we introduce T transposable N:M sparsity that scales to I.LMs. We formulate optimal mask selection as an integer program and observe a novel connection to optimal transport. Leveraging this connection, we solve the relaxed problem using entropy regularization and Dykstra's 's algorithm. This is followed by a new rounding procedure to recover binary masks. Our approach efficiently handles arbitrary N:M patterns, which is crucial as larger M values significantly reduce performance we compare con-transposable to transposable sparsity. Our method's tensor-based implementation enables seamless integration with existing layerwise pruning frameworks-thh accelerates both forward and backward passes while preserving model quality. Our contributions include:
a novel algorithmic framework for finding binary masks with
esspeiiall when
1. We formulate transposable N:M sparse mask generation as multiple optimal transport problems with capacity constraints, and solve them simultancously by entropy regularization and Dykstra's algorithm. This approach is highly parallelizable and efficiently handles arbitrary N:M patterns.
2. The solutions obtained from Dykstra's ' algorithm are fractional and cannot be directly used as binary masks. To this end, we propose a GPU-optimized rounding procedure that converts fractional solutions to high-quality binary masks through greedy selection and local search. Our based implementation can process millions of blocks simultaneously, achieving up to 103 times speedup over vanilla approach.
3. We show the integration of TSENOR with existing layer-wise N:M pruning frameworks to generate transposable N:M sparse networks. Specifically, we incorporate it as a plug-in in procedure into leading pruning approaches such as Wanda (Sun et al. 2023], SparseGPT [Frantar and Alistarh 2023]. and ALPS [Meng et al. 2024a]. For ALPS, we provide novel convergence guarantees for the resulting framework.
4. Experimental results show that our method generates masks with 1-10% less relative error com- pared to existing heuristies and runs up to 102 times faster. We demonstrate that transitioning from -on-traasposable to transposable sparsity with larger M values (16:32) results in only 12% of the performance loss compared to smaller M values (2:4). Moreover, models with transposable
Traaspossabee N.M Sparsity with ENtropy regularization and Optimized Rounding
2

---

16:32 sparsity outperform those with non-transposable 2:4 sparsity, confirming the importance of our efficient solver for arbitrary (especially large M) transposable patterns. Our code is publicly available at: https:: /ttpss//////bt.....// www.tth......uuumeetecoc http://aaudeer-aab/aaaaa
2 Preliminaries and related work
Network pruning with N:M sparsity Techniques for obtaining N:M sparse networks fall into four categories: (i) Sparse training methods that mitigate performance degradation induced by N:M
sparsity through carefully designed training strategies [Mishra et al. 2021 Zhou et al. 2021 Lu
ctt al, 2023 Bambhaniya et al. 2024]; ; (ii) Pruning approaches that identity high-quality sparse
masks for given N:M patterns by minimizing layerwise reconstruction
calibration samples
[Frantar and Alistarb 2023 Meng et al., 2024aa or estimating weight importance [Sun et al., 2023];
(iii) Configuration search methods that determine layer-specific N:M sparsity patterns [Sun et al.)
2021 Huang et al. 2024]; and (iv) Methods performing channel permutation on the weight matrix to
improve pruned N:M sparse model performance (Pool and Yu 2021 Mahajan et al., [222]]
Transposable N:M sparsity Transposable N:M sparsity remains relatively unexplored compared to its non-transposable counterpart. [Hbbar et al. [2021a] first proposed transposable N:M masks to accelerate both forward and backward passes during training, introducing the minimum-cost flow method as well greedy heuristic for mask generation. Huu et al. [2024] developed a highly efficient vectorized approach specifically for transposable 2:4 mask generation. Alternatively. Zhang et al. (2023) proposed training non- transposabble N:M sparse networks using gradients approximated by applying transposable N:M sparse masks during the backward pass.
Hardware implementation of N:M sparse networks NVIDIA's Sparse Tensor Cores in the Ampere
GPU architecture NNiida (2000] support 2:4 sparsity acceleration. [astro et al. 2023) introduces Spatha sparse library, enabling arbitrary N:M patterns on Sparse Tensor Cores. Alternative approaches like nmSPARSE [Lin et al., 2023a] and NM-SPMM [Ma et al. 2025) design GPU kernels with memory access optimization and blocking mechanism support arbitrary N:M patterns without requiring specialized hardware, Fang et al. [2023] designed computation-effiiiaa training through
Algorithm-architecttue-- ceniteetuur-datafllin co-design, while Liu et al. 2025 proposed transposable block wise
N:M sparsity with dedicated tensor cores.
GPU-accelerated optimization Our approach formulates transposable N:M mask generation as solving millions of small-scale optimal transport problems, efficiently parallelized using GPU ac- celeration. In contrast, most existing GPU-accelerated optimization methods focus on solving single large-scale problem. Examples include efficient GPU implementations of linear programming solvers (Lu and Yang 2023 Pacaud al. 2024 and parallelizable approaches for large-scale optimal
transport problems (Cuturi 2013 Mai al. 2021].
3 Computing high-quality transposable N:M mask efficiently
Given a weight matrix W, the core problem in transposable N:M sparsity is to determine a binary mask that maximally preserves the magnitude of weights in W under the transposable N:M constraint. This can be formulated as:
maxs Σ Siy Wayl
s.t.
is a binary mask with transposable N:M sparsity,
(1)
The primary challenge in solving ①I is computational efficiency. While optimal solutions can be obtained through mixed -ittger programming (c.g., Gurobi [2022) or network flow algorithms [Hubara et al. 202 these approaches become computationally prohibitive for practical LLMs (c.g.. LLaMA3 Dubey ct al. 2024)) where weight matrices contain billions of elements. Furthermore, as discussed in Section problem (I] appears subproblem in each iteration of some pruning methods (e.g.. [Meng et al. 2024a amplifying the computational demands.
We address this challenge by developing algorithms that can fully leverage GPU parallelization. Our method begins by partitioning the weight matrix into MxM blocks and reformulating problem
①1 optimal transport problem with capacity constraints for each block. We then introduce entropy regularization and derive a solution using Dykstra's 's algorithm, followed by a vectorized rounding procedure that converts fractional solutions to feasible binary masks. Figure illustrates
3

---

Solutions with entropy regularization
Rounding (Secioon 33
Dykstra method
(Section X2
Weight matrix W
Entropy regularization parameter
Transposable 4:8 masks
Figure 1: Efficient GPU-accelerated pipeline for transposable N:M masks generation. The weight matrix is partitioned into M blocks and simultaneously processed through our entropy-regularized solver and rounding procedure, leveraging tensor operations for GPU parallelization.
complete methodology. Our key innovation lies in the careful design of all algorithmic components to enable tensor-basee operations, allowing simultaneous processing of millions of blocks on GPUs. This parallel implementation achieves up to two orders magnitude speedup compared to existing methods, making approach practical for billion-parameta language models.
3.1
An optimal transport reformulation
The transposable N:M sparsity constraint applies independently each MxM submatrix of Consequently, problem ( is separable, and reduces to the following problem for each MxM block:
max SE(0.1)MxA
Σ Sty W
s.t.
S. = N.j E [M]. Σ
S = NVI E [M]. (2)
By leveraging bipartite matching polytope theory (Schrijver et al.] 2003 Chapter 18], we can relax
the binary variables Syj to lie in the interval [0. 1] without altering the optimal value of problem (2).
Notably, any basic feasible solution of the resulting relaxed linear program corresponds to integral optimal solution of the original problem. The relaxed problem can be expressed in matrix notation as:
maxş (S, W)) s.t. S1 Nl S NIM, 0 SSSI.
We make the novel observation that problem (3) can be viewed as a capacitated optimal transport problem [Villani 2008), where S [0, 1 represents the transport plan between rows and columns. Each row and column must send and receive exactly N units of mass, as enforced by the constraints S1M M N1 M and T 1M N... The objective is maximize the total transported value weighted by |W] This connection allows us to leverage tools from optimal transport to solve the relaxed problem efficiently, detailed in the next subsection.
3.2 Entropy Regularization
In practical neural network pruning scenarios, we need to efficiently solve millions of instances of problem (3) simultaneously. To enhance computational tractability, introduce entropy regularization term to the objective [Cuturi 2013). reformulating the problem as:
max (S, (|) - H() s.t. S1 N1M, s 1 N1M, 0 OSS<1. (4)
S
where HSS) Exj=1 Si (S denotes the Shannon entropy and
0 controls the regular-
ization strength.
This entropy term serves two critical functions: (i) promotes exploration by distributing "mass" more uniformly across feasible entries, preventing premature convergence to suboptimal solutions; and most importantly. (ii) enables efficient computation via matrix-scaling algorithms that are highly parallelizable and have been GPU-accelerated in optimal transport literature [Cuturi] 2013) making them particularly suitable for our large-scale optimization requirements.
From optimization perspective, the entropy-regularize problem can be interpreted computing the Bregman projection of matrix W- = exp(r|W]) onto the intersection of three constraint sets:
C (S S1 N1v), C2 (S| S 1M N1 Ca (S S < 1}
(5)
with respect to the Kullback-Leebllrr divergence. solve this projection problem efficiently, we employ Dykstra's 's algorithm [Benamou et al. 2015). which iteratively projects onto each constraint

---

binary mask obtained set, as detailed in Algorithm [ (see Appendix[A. |.] for detailed derivation). Critically, here each update involves only matrix-vector multiplications and element-wise operations, enabling full vectorization across millions of weight blocks and leveraging GPU acceleration.
The selection of regularization parameter impacts performance. A small value of 7 yields solutions that poorly approximate the original problem (see Fig D. while excessively large values impede convergence. In practice, we select to balance solution quality and computational efficiency. Furthermore, the entropy-regularized problem ( only gives fractional solutions. We develop in Section 3.3 a specialized rounding procedure that can convert the approximate fractional solution into a hugh-quality feasible binary mask.
Algorithm 1 Dykstra's is algorithm for solving entropy-regularized optimal transport problem
Input: Weight matrix W, regularization parameter >> 0, and maximum iterations T Output: Solution S to problem (4)
I: Initialize ( exp(r) WI), and dual variable (()) 1MxxMM
2: for t = 0, 1.......... T T
do
3:
((t) + Diag (NV g(
Projection onto C
4: ((t) + ( (S (M))
Projection onto C2
5: S(++1) - min (s (+) 1)
Projection onto C3
6:
Q(++1) + Q o (S 1(++))
b Update dual variable
7:
return S(T)
3.3 Sparse solution recovery via greedy selection and local search
The solution generated by Algorithm[iia generally not binary-valued due to the entropy regularization, as illustrated in Fig.2 (1) making unsuitable for direct use as a mask. While a simple element-wise rounding approach could be considered, it would compromise both accuracy and constraint feasibility. Therefore, we develop a novel rounding procedure that combines greedy selection with local search to obtain high-quality feasible binary mask.
Greedy selection: Our approach consists of two stages. In the first greedy selection phase, we sort all elements of the approximate solution. We then iteratively assign each element to the binary mask, proceeding from largest to smallest, provided that doing so preserves the row and column sum constraints imposed by the transposable N:M sparsity. Fig. (2) through this procedure under transposable 2:4 sparsity constraints
While efficient, the greedy selection strategy can prematurely saturate certain rows columns, preventing the placement of subsequent high-value elements and yielding suboptimal binary masks. For instance, in Fig.2 (2) the fourth row and column contain only one active element, yet the transposable N:M constraints prevent additional elements from being added.
Local search: To address this limitation, we introduce a novel local search procedure that refines the greedy solution. For any unsaturated row and column j (i.e., containing fewer than N selected elements), we explore swap- baap-based local updates that preserve feasibility. Specifically, we explore operations that simultaneously insert two elements one one in row i and one in column j-while removing a conflicting element to maintain the transposable N:M constraints. We enumerate all such valid insert-remove triplets and select the one that maximally increases the objective. Formally, we select candidate swap coordinates (i', that maximize:
(6) where S denotes the current binary mask. The second term (with infinite penalty) ensures we neither insert elements already in the mask nor remove non-existent elements. When Swap(i', j'') > O, we insert elements (i,j") and (t', ()) while removing (f', J'), thereby increasing the objective value while maintaining feasibility. Fig.2 (3-4) illustrates this process, showing how adding (2, 4) and (4,2)
Swap(1',
(W + W [W I
((1 Sy + S Svy),
while removing (2, improves the objective by 0.32.
The complete rounding procedure is presented in Algorithm 2 While Hubara et al. 2021b also proposed a greedy approach for binary mask generation, our method differs in three key aspects: (i)
5

---

(1) Approximation solution
(2) Binary mask selection
(3) Swap score matrix
(4) Binary mask via local search
0.88
0.01
0.84
0.27
0.88
0.01
0.84
0.27
00.32
-20
0.33
-00
0.88
0.01
0.84
0.27
0.01
0.71
0.75
0.53
0.01
0.71
0.75
0.53
0.32
0.04
0.01
0.71
0.75
0.53
0.82
0.78
0.15
0.25
groedy selection
0.78
0.15
compute score
-0.28
-0.03
-00
perform
0.82
0.78
0.15
0.25
swap
0.29
0..00
0.26
0.95
0.29
0.50
0.26
0.95
-00
-00
-00
100
0.29
0.50
0.26
0.95
Objective:
5.73
Optioul (f', (2,22
Objective:
Figure 2: Illustration of our proposed rounding procedure for generating a binary mask with transpos- able 2:4 sparsity. Each cell displays the absolute value of Wil. (1): The approximation solution obtained from Algorithm the shading intensity reflects the magnitude of the approximate solu- and column j
tion:(2): The binary mask produced through greedy selection, with remaining unsaturated (each containing only one non-zero element); (3): Computed swap scores for candidate operations, with optimal score achieved at (i', (2, 2); (4): Refined binary mask after local search operation-inserting elements at positions (4, 2) and (2, 4) while removing (2, 2).
we apply rounding to entropy- regularzee approximate solution rather than directly to the original weight matrix; (ii) our novel local search strategy can further reduce rounding error by around 50% (see Appendix B and (iii) we leverage GPU to achieve significant speedup, as detailed below.
Computational efficiency: A key feature of rounding approach is computational efficiency, We have fully vectorized our algorithm so that both greedy selection and local search can be performed simultaneously across all millions of blocks through tensor operations (refer to Appendix A..2 for implementation details), thereby enabling direct GPU implementation without custom CUDA kernels. This vectorization achieves up to 10 times speedup compared sequential CPU implementations (refer to Appendix [B2 for ablation studies), making our approach highly practical for large-scale network pruning applications.
Algorithm 2 A binary mask generation approach based on greedy selection and local search
Input: Approximate solution S from Algorithm and number of local search step
Output: Feasible binary solution to problem
Initialize S Oarx Ms rоw counter Owr column counter C 0.
2: ((4e, [c)) M² + argsort((-S)) 1M "jlag=1)
Sort elements descending order b greedy selection
3: for = 1, 1,2,... M do
4: if Rí N and Cj N then
5:
Set Si < Update (Ri, Cj.) (Ri, + Cj + +1
6:
7:
for = 1, do
L local search steps
8:
if R, N. C. N. Vi [M] then
9:
break
10:
Pick i, E [M] such that R. < N, C <
11: Select (f' )/)= arg maxy,, Swap(i', (f)) as defined in Eq.
if Swap(E' j') then
13:
Set (S Sr Sa,y) (0, (R, C,) - (R, + C, 11).
return Feasible binary mask S
4 Layer-wise reconstruction with transposable N:M sparsity
We integrate TSENOR within leading LLM layer-wise pruning approaches to obtain transposable N:M sparse networks. These masks enable efficient fine-tuning with acceleration both forward and backward passes. Note that layer-wise pruning minimizes the discrepancy in outputs between dense and pruned layers, formulated as
minw (1/2)|X((W) WW) (1/2)
WI S.L. WET.
(7)

---

where W is the pre-trained weights, X represents input activations, and T denotes set of matrices with transposable N:M sparsity. We demonstrate integration with Wanda [Sun al. 2023). SparseGPT [Frantar and Alistarh 2023], and ALPS [eeng et al. 2024a
Integration with Wanda: Wanda evaluates weight importance using the product of weight magnitude and corresponding input feature norm, performing magnitude pruning based on this importance score. Our integration with Wanda involves solving problem (I) with W replaced by W' with entries Wiy W ill to get the pruning mask and setting all elements outside the mask to zero.
Integration with SparseGPT: SparseGPT traverses W left-to-right in groups of M columns, pruning each group W according to OBS scores [Hassibi and Stork 1992]. and updating W and remaining columns accordingly. To achieve transposable N:M sparsity, substitute the pruning step with TSENOR, solving problem with W replaced by the matrix with entries (- W
8y HH please
refer to the SparseGPT paper for algorithmic details and efficient updates of H
Integration with ALPS: Integrating TSENOR with ALPS poses technical challenges as ALPS' origi- nal update rules and convergence guarantees do not directly apply to our setting. We derive modified updates and establish new convergence guarantees as below. Following ALPS framework, we ad-
dresses layer-wise pruning problem through the ADMM approach [Boyd et al. 201T). We introduce an auxiliary variable D that replicates W and consider the following augmented Lagrangian:
(W, D. V) - 2 [
- W) W) 1 A
W-
(V, W WDD)
DI (8)
where (DD) is the indicator function that equals zero when D E T and infinity otherwise and > 0 the penalty parameter. ADMM minimizes this augmented Lagrangian by alternately updating W and D. followed by dual update for V.
Proposition iteration the ADMM update rules are given by:
1(++1) 1) = arg minw L,( WWW D v(t) = (H pI) (HW - v + +D
D(++1) arg minp L (W((1))) D, v(O) (W(H1) v(1 e s((+1)
(9)
((+1)) = ((t) + ((W(+1)) - D((+))),
where H = - X AI Above, ((++1) is the solution to the following problem:
maxs E,g Sis (W + /p)² s.I. S is a binary mask with transposable N:M sparsity (10)
(1+1)
with the same structure and directly apply our binary mask solver from Section 3
The key distinction between our modified ALPS framework and the original is in the D-update step. While standard ALPS employs direct projection for unstructured or non traasposspsabe N:M sparsity, our approach solves the transposable N:M sparsity constraint using our proposed entropy-regularized algorithm followed by rounding procedure. Our approach may not find the globally optimal mask, but we can still establish theoretical convergence guarantees as Theorem T Complete statements and proofs of Proposition and Theorem Jare provided in Appendix [.I]
Theorem 1. (Informal) Under mild assumptions on penalty parameter and sufficient accuracy of each D-update, there exists matrix W such that (()) -> W and Wtt) W as - 0o.
Experiments
This section evaluates the efficiency and effecctiveness of our proposed transposable binary mask solver and demonstrates its performance when integrated into existing N:M pruming frameworks. Detailed experimental setup and reproducibility information are provided in Appendix B.I with ablation studies and additional experimental results presented in Appendix B.2
5.1 Performance on a single matrix
We evaluate our proposed transposable binary mask solver against several approaches: (i) Network Flow method (Hubara et al.] (022b), which guarantees optimal solutions through bipartite matching algorithms; (ii) cuPDLP [u and Yang 2023 general-purpose GPU-accelerated linear programming
7

---

solver; (iii) 2-Approximation [Hubara et al. 2021b]. a greedy- based heuristic; (iv) Bi-NM adopted from (Zhang al., 2023]. which sequentially applies row-wise and then column-wise N:M sparsity; and (v) Max 1000, a randomized baseline that generates 1000 feasible masks and selects the best one. Our experiments focus on transposable N:M sparsity with M28, as smaller patterns (M=4) can already be optimally and efficiently solved [Hu et al. 2024).
We first examine solution quality of each approach through relative error against optimal solutions, excluding Network Flow and cuPDLP which guarantee optimality. We evaluate two variants of our method (1) Entropy: Algorithm with simple row-then-colee wo-tthen-colum N:M sparsity rounding, and (2) TSENOR: our full pipeline combining entropy regularization with specialized rounding (Algorithm 2). As shown Figure TSENOR achieves remarkably low relative error (1-10%) compared to 2- Z-Approximation. the best competing heuristic. The specialized rounding procedure alone also contributes substantially, reducing error by up to 10x compared simple rounding (i.e., Entropy), validating the effectiveness of both components in our pipeline. In contrast, simpler approaches like Bi-NM and Max 1000 exhibit substantially higher relative errors (up to 50%), highlighting the inherent difficulty of the transposable N:M sparsity problem and the value of our advanced solver.
TSENOR
2-3pproxlmation
Max1000
34%
45%
Relative Error
2,1%
2,25
3,4%
1.0%
2.2%
10
57677
0.34%
0.14%
0.857%
0.052%
0.0087%
2:8
4:8
4:16
8:16
8:32
16:32
Figure Solution quality comparison for transposable N:M mask generation. For various N:M sparsity patterns, we evaluate all methods on 100 MxM blocks sampled from LLaMA3 [Dubey et al. 2024) model weights. We report the average relative error, defined as (S(S*) - f(S)) (S*), where S is the optimal support and f is the objective defined in
Next, we benchmark computational efficiency on matrices of increasing size. We compare our method with two CPU-implemented approaches (Network Flow and 2-Approximation) and one GPU-accelerated method (cuPDLP) across various hardware platforms. Table shows our method consistently achieves the fastest runtimes, delivering up 300x speedup compared to methods guaranteeing optimal solutions. While Bi-NM and Max 1000 (not shown in the table) offer negligible runtime overhead, their poor solution quality renders them impractical. This implies that solver provides the optimal balance between solution quality and efficiency for large-scale network pruning.
cuPDLP
TSENOR
Matrix Size
Network Flow
2-Approximattion
V100
H100
V100
H100
512 512
1.82
(.13
14.6
12.1 (20.6)
7,82
0.11 (20.000
0.16
0 (10.00)
2048 2048
23.3 (+:0,89)
0.35 (1001))
20.9 (+0.82)
(=t.00
11.9 (=1.00)
0.27 (20.00)
0.20 (40,00)
0.12 (+:1000)
8192
(+5.22))
3.23 (+0.00)
(+9.65)
(#1.04)
(e0.5))
(=0000)
(40000)
(+:1000)
Table 1: Runtime (seconds) for transposable 8:16 sparsity. For GPU methods, test NVIDIA V100-PCIe-32GB, A 1000-PCIe-40GB and #100-PCIe-80GE CPU methods use 16-core parallel processing. Results averaged over 10 trials with standard deviations in parentheses.
5.2 LLAMA with transposable N:M sparsity
We evaluate our transposable N:M solver integrated into existing pruning approaches: Wanda (Snn
al. 2023), SparseGPT [Frantar and Alistarh 2023) and ALPS [Meng et al. 2024a], using ILL.MA- 3.2
Dubey al. 2024 models with I to 8 billion parameters. Performance is assessed via perplexity

---

and zero-shot benchmarks. Perplexity is computed following HuggingFace's 's methodology [Per 2022 with full stride on Sow-Wikieett2 [Merity et al., 2017]. PTB [Mareus et al. 1994), and C4 Raitel
2020] validation subset. Zero-shot evaluation uses LM Harness [Gao et al. on PIQA Bisk et al. 2020 ARC-E and ARC-C [Clark et al. 2018], Hellaswag (Zellers et al. 2019 Winogrande
et al.
[Sakaguchi et al. 202T]. RTE [Poliak] 2020]. OpenbookQA [Banerjee et al. 2019 and BoolQ (Clark)
ct al.
2019).
5.2.1 Trade-ofIs: benefits and costs of transposable N:M sparsity
Transposable N:M sparsity enables backward pass ac-
celeration beyond standard N:M sparsity, but imposes stricter constraints that potentially impact model perfor- mance. We quantify this trade-off through experiments. Fig. 4 (Upper) compares perplexity of LLaMA3.2- 8B when pruned to different sparsity patterns, while Fig. 4 (Lower) iillusraels illustrates computational speedup versus dense computation. Our results demonstrate that the performance gap between transposable N:M and stan- dard N:M diminishes dramatically as M increases from 4 to 32 (by approximately 90%). while transposable N:M consistently delivers superior speedup (3.3x at 75% sparsity) regardless of M value. This indicates that transposable N:M sparsity with larger M values offers an excellent practical trade-off, highlighting the importance of our efficient solver for arbitrary transpos- able sparsity patterns.
N:M Tran N-M
20
Perplexity
20
15.7
12.0
15.1
15
161
14.7
12.0
2:4
4:8
8:16
16:32
Speediu us. denss model
M 16
5.2.2 Integration
0.5
6.625
0.75
0.675
with various pruning frameworks
Sparsiy (1-A4M)
We evaluate our solver's effectiveness when integrated into different pruning methods. Table[2preeents the per- formance of LLaMA3.2-33 after one-shot pruning with various frameworks. As expected, applying transpos- able N:M sparsity directly with Wanda or SparseGPT results in significant accuracy degradation. However, integrating our solver with ALPS, which minimizes lay- erwise reconstruction error, successfully recovers most of the performance loss. Notably, our approach com- bined with ALPS produces transposable N:M sparse models that slightly outperform standard N:M sparse models obtained through SparseGPT, while providing additional computational benefits.
Figure 4: Upper: perplexity of LLaMA3.2- 8B pruned by ALPS with TSENOR, com- paring standard and transposable N:M spar- sity across different N:M patterns. (2) Lower: Computational speedup for for- ward and backward matrix operations in LLLMMA3.244
comparing (transposable) N:M sparse matrices (via nmSPMM [Ma] et al. 2025 against dense matrices (via NVIDIA cuBLAS).
Perplesity (1)
Zero-shot (1)
Spaniity
Algorithm
Transpose
C4
WT2
PTB
PIQA
ARC-E
ARC-C
WG
RTF
0QA
BonlQ
Avg
SparwwGPP
139.67
120.22
183.01
$3.86
29.
21.67
54.15
23.20
67.23
40.74
ALPS
50.12
82.28
110.73
$6.64
31:27
32.65
19.80
51.38
52.35
23.00
61.99
41.63
-endd
23379.13
100992.48
250675.00
50.98
26.06
24.83
27.90
90.12
52.71
26.60
55.26
39.32
THEMUR TEEMUR-Spareoder
239.08
302.75
378.69
$2.56
27.33
28.62
23.04
89.80
52.71
26,60
41.35
37.72
TEEMOR-ALPS
111.36
163.18
178.60
$1.90
28.92
30.43
20.39
50.99
53.07
26.60
61.22
8081
SpareeGPT
18.11
13.02
20.37
73.12
62.27
62.67
34.81
65.75
60.65
35,20
71.53
$8.25
ALPS
16.74
12.06
18.78
73.56
66.10
64.43
36.52
65.54
57.40
38.00
72.81
59.30
TEEMUR-VAnda
436.13
262.78
263.91
57.29
30.54
37.79
21.25
50.28
52.71
25.60
89.82
80.66
TEEMOR-Gpoae opp
20.29
14.30
23.81
72.36
38.69
99.64
33.02
63.06
53.79
34.20
65.99
55.10
TEENOR-ALPS
18:03
13.08
20.43
72.96
61.43
63.22
38.05
63.46
57.40
35.60
72.32
58.06
Table 2:
Performance analysis for (transposable) N:M pruning on I...MA3.2-3B model. Lower values are preferred for perplexity, and higher values are preferred for zero-shot tasks.

---

5.2.3 Fine-tuning transposable N:M sparse models
24
We fine-tune transposable N:M sparse models pruned with our approach (TSENOR+ ALPS) on C4 and compare their perplexity against Bi-NM (Zhang et al. 2023], which trains a non-transposable N:M network using gra- dients approximately calculated through transposable mask. As shown in Figure [ Bi-NM performs slightly better when M=4, but our approach achieves progres- sively lower perplexity as M increases. This is because transposable sparsity with larger M values has smaller impact on model performance, and our method's use of exact gradients during fine-tuning which leading to more effective parameter update. Refer to Appendix
Perplexity
22
22.0
BI-NM
TSENOR
19.7
18.7
17.7
16
2:4
4:8
8:16
16:32
Figure 5: Perplexity comparison of
LLaMA3.2-IB under two pruning ap- proaches: (1) TSENOR+ALPS followed by fine-tuning, and (2) standard N:M pruning followed by retraining via Bi-NM.
6.2.6 for comprehensive comparison between TSENOR+ALPS and Bi-NM.
6 Limitations and future work
While our work presents efficient algorithms for computing transposable N:M masks and transposable N:M sparse models and demonstrates computational speedup on matrix operations, several directions remain unexplored. Developing an end-to-end training pipeline that fully realizes the practical acceler- ation from transposable N:M sparsity would strengthen the applicability of our method. Additionally, comparing the computational cost and model quality trade-offs between transposable N:M sparsity and parameter-effiiient fine-tuning methods (e.g., LoRA [Hu et al. 202T]. J. SPP [L.u et al.) 2024]) would provide valuable guidance for practitioners. Another promising direction is incorporating channel-wise permutations of weight matrices before computing transposable N:M masks. While this approach has proven successful for standard N:M sparsity (Pool and Yu, 2021], extending it to the transposable setting remains unexplored. Despite introducing a complex combinatorial optimiza- tion problem, such extension might substantially improve pruning quality. Similarly, it would be interesting to explore loss functions that go beyond simple layerwise reconstruction error [Lucas and Mazumder). We believe these directions represent important future paths for advancing practical sparse model deployment.
7 Conclusion
In this paper we present TSENOR- novel efficient algorithm for generating high-quality trans- posable N:M sparse masks. TSENOR solves an ontropy-regularzee, optimal transport problem and applies new rounding procedure combining greedy selection with local search. By using tensor operations throughout, our method achieves significant speedup through GPU acceleration and scales billion- Iillion-paramettr language models. We can incorporate TSENOR within several existing layerwise pruning frameworks to create transposable N:M sparse LLMs with any N:M pattern. Our experiments show that networks with larger M values (e.g., 16:32) provide the same computational benefits as smaller M values but with much less impact on model accuracy, demonstrating our method's 's practical value.
Acknowledgements
This research is supported in part by grants from the Office of Naval Research (N0001425 12504, We acknowledge the MIT Engaging cluster for providing HPC resources that have contributed the research results reported within this paper. Additionally, we thank Google for providing us with Google Cloud Credits. We thank Shibal Ibrahim, Ryan Lucas, and Gabriel Afriat for their helpful discussions.
10

---

References
Perplexity of fixed-length models, 2022. htt.latpps///iggiggg....../o//oe
perplexity
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Iige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.0077 008774, 2023.
Abhimanyu Rajeshkumar Bambhaniya, Amir Yazdanbakhsh, Suvinay Subramanian, Sheng- Chun Kao, Shivani Agrawal, Utku Evci, and Tushar Krishna. Progressive gradient flow for robust n: M sparsity training in transformers. arXiv preprint XXiv:2402.007444, 2024.
Pratyay Banerjee, Kuntal Kumar Pal, Arindam Mitra, and Chitta Baral. Careful selection of knowledge to solve open book question answering. arXiv preprint /907. 10738, 2019.
Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Itera- tive bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, 37(2) 2015.
Riade Benbaki, Wenyu Chen, Xiang Meng, Hussein Hazimeh, Natalia Ponomareva, Zhe Zhao, and Rahul Mazumder. Fast as chita: Neural network pruning with combinatorial optimization. In International Conference on Machine Learning, pages 2031-2049. PMLR, 2023.
Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. Piqa: Reasoning about physical commonsense natural language. Proceedings of the AAAI conference on artificial intelligence. volume 34, pages 7432-7439, 2020.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, and Jonathan Eckstein. Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122, 2011.
Lev M Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR computational mathematics and mathematical physics, 7(3):200-217 217, 1967.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Roberto I. Castro, Andrei Ivanov, Diego Andrade, Tal Ben-Nun, Basilio B Fraguela, and Torsten Hoefler. Venom: A vectorized n: M format for unleashing the power of sparse tensor cores. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-14, 2023.
Li Chen, Penghao Wu, Kashyap Chitta, Bernhard Jaeger, Andreas Geiger, and Hongyang Li. End-to- end autonomous driving: Challenges and frontiers. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Hongrong Cheng, Miao Zhang, and Javen Qinfeng Shi. A survey on deep neural network pruning: Taxonomy, comparison, analysis, and recommendations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024.
Christopher Clark, Kenton Lee, Ming-Wes Wei Chang, Tom Kwiatkowski. Michael Collins, and Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. arXiv preprint arXiv:1905.10044, 2019.
Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint arXiv: (o0::00533005 2018.
Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.

---

Tim Dettmers, Ruslan Svirschevski, Vage Egiazarian, Denis Kuznedelev, Elias Frantar, Saleh Ashk- boos, Alexander Borzunov, Torsten Hoefler, and Dan Alistarh. Spqr: A sparse-quantized represen- tation for near-lossless IIm weight compression. arXiv preprini WrXiv:23066030778, 2023.
Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang. Angela Fan, al. The llama herd of models. arXiv preprint arXivv2407.21773, 2024.
Richard L Dykstra. An algorithm for restricted least squares regression. Journal of the American Statistical Association, 78(384):8378842, 1983.
Chao Fang. Wei Sun, Aojun Zhou, and Zhongfeng Wang. Efficient M sparse dnn training using algorithm, architecture, and dataflow co-design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 43(2):506-519, 2023.
Elias Frantar and Dan Alistarh. Sparsegpt: Massive language models be accurately pruned in one-shot. In International Conference on Machine Learning pages 10323-10337. PMLR, 2023,
Gao, Tow, B Abbasi, S Biderman, S Black, A DiPofi, Foster, L Golding, J Hsu, A Le Noac'h, et al. A framework for few-shot language model evaluation, 12 2023. URL https://eenoo. org/recordd/11256686. 7.
Jianping Gou, Baosheng Yu, Stephen J Maybank, and Dacheng Tao. Knowledge distillation: A survey, International Journal
Journal of Computer Vision, 12966)1779-11119 2021.
Gurobi. Gurobi Optimizer Reference Manual, 2022. URL https://www www.ggurrbb.com com
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances neural information processing systems, 28, 2015.
Babak Hassibi and David Stork. Second order derivatives for network pruning: Optimal brain surgeon. Advances in neural information processing systems, 5, 1992.
Y. He, X. Zhang, and J. Sun. Channel pruning for accelerating very deep neural networks. In 2017 IEEE International Conference on Computer Vision (ICCV), pages 1398-1406, Los Alamitos, CA. USA, oct 2017. IEEE Computer Society, doi: 10. 1 109/ URL https 7/doi www.ciippptrrriiitt.oooroooeooee
1109/ICCV. 2017 155
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2106.00 000.2885609685 2021.
Yuezhou Hu, Kang Zhao, Weiyu Huang, Jianfei Chen, and Jun Zhu. Accelerating transformer pre-training with 2: sparsity. arXiv preprint arXiv:2404.01847, 2024.
Ning-Chi Huang, Chi-Chih Chang, Wei-Cheng Lin, Endri Taka, Diana Marculescu, and Kai-Chiang Wu. Elsa: Exploiting layer-wise sparsity for vision transformer acceleration. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 8006-8015, 2024.
Itay Hubara, Brian Chmiel, Moshe Island, Ron Banner, Joseph Naor, and Daniel Soudry. Accelerated sparse neural training: A provable and efficient method to find n: m transposable masks. Advances in neural information processing systems, 34:21099-211 11192-11111111111111111111111111 2021a.
Itay Hubara, Yury Nahshan, Yair Hanani, Ron Banner, and Daniel Soudry, Accurate post training quantization with small calibration sets. In International Conference on Machine Learning, pages 4466 4475. PMLR, 2021b.
Bin Lin, Ningxin Zheng, Lei Wang, Shijie Cao, Lingxiao Ma, Quanlu Zhang, Yi Zhu, Ting Cao, Jilong Xue, Yuqing Yang, et al. Efficient gpu kernels for n: M-sparse weights in deep learning. Proceedings of Machine Learning and Systems, 5:513-525, 2023a.
Ji Lin, Jiaming Tang, Haotian Tang, Shang Yang. Xingyu Dang, and Song Han. Awq: Activation- aware weight quantization for Il compression and acceleration. arXiv preprint arXiv:2306.0000 00978. 2023b.
12

---

Jun Liu, Shulin Zeng, Junbo Zhao, Li Ding, Zeyu Wang, Jinhao Li, Zhenhua Zhu, Xuefei Ning, Chen Zhang, Yu Wang, al. Tb-stc: Transposable block-wise n: M structured sparse tensor core. In 2025 IEEE International Symposiun on High Performance Computer Architecture (HPCA), pages 142. IEFE, 2025.
Haihao Lu and Jinwen Yang. cupdlp. jl: A gpu implementation of restarted primal-dual hybrid gradient for linear programming in julia, arXiv preprint arXiv:2311.12/188 2023.
Xudong Lu, Aojun Zhou, Yuhui Xu, Renrui Zhang, Peng Gao, and Hongsheng Li. Spp: Sparsity-preserved parameter-efficient fine-tuning for large language models. arXiv preprint arXiv:2405. 16057, 2024.
Yucheng Lu, Shivani Agrawal, Suvinay Subramanian, Oleg Rybakov, Christopher De Sa, and Amir Yazdanbakhsh. Step: learning M structured sparsity masks from scratch with precondition. In International Conference on Machine Learning, pages 22812-22824. PMLR, 2023.
Ryan Lucas and Rahul Mazumder. Preserving deep representations in one-shot pruning: A hessian- free second-order optimization framework. The Thirteenth International Conference on Learning Representations.
Cong Ma, Du Wu, Zhelang Deng, Jiang Chen, Xiaowen Huang, Jintao Meng, Wenxi Zhu, Bingqiang Wang, Amelie Chi Zhou, Peng Chen, et al. Nm-spmm: Accelerating matrix multiplication using n: M sparsity with gpgpu. arXiv preprint arXiv:2503.01253, 2025.
Mohit Mahajan, Wen-Mei Hwu, and Rakesh Nagi. Determining optimal channel partition for fine grained structured sparsity. Optimization Letters, 18(9):2779-0990, 2024.
Vien V Mai, Jacob Lindbäck, and Mikael Johansson. A fast and accurate splitting method for optimal transport: Analysis and implementation. arXiv preprint arXiv:2110.11753 2021.
Mitchell Marcus, Grace Kim, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bies, Mark Ferguson, Karen Katz, and Britta Schasberger. The penn treebank: Annotating predicate argument structure. In Proceedings of the Workshop on Human Language Technology, HLT '94, page 1 14-119, USA, 1994. Association for Computational Linguistics. ISBN 1558603573. 1075835. URL http::t:t/....org//////// www../rr/.....1111111 101.:01111111111111100001000.
doi: 10.3115/107581..
Xiang Meng, Shibal Ibrahim, Kayhan Behdin, Hussein Hazimeh, Natalia Ponomareva, and Rahul Mazumder. Osscar: One-shot structured pruning in vision and language models with combinatorial optimization. In Forty-first International Conference on Machine Learning.
Xiang Meng, Kayhan Behdin, Haoyue Wang, and Rahul Mazumder. Alps: for highly sparse one-shot pruning for large language models. Advances in Neural Information Processing Systems, 37:37594-37625 2024a.
Improved optimization
Xiang Meng, Wenyu Chen, Riade Benbaki, and Rahul Mazumder. Falcon: Flop-aware combinatorial optimization for neural network pruning. In International Conference on Artificial Intelligence and Statistics, pages 4384 4392. PMLR, 2024b.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mix- ture models. In International Conference on Learning Representations, 2017. URL. https
//openreview.net www.nnte//oommmmdd/////eae.
Asit Mishra, Jorge Albericio Latorre, Jeff Pool, Darko Stosic, Dusan Stosie, Ganesh Venkatesh, Chong Yu, and Paulius Micikevicius. Accelerating sparse deep neural networks. arXiv preprint vrXiv:2/04.08378 2021.
Nvidia.
Nvidia a100
tensor core gpu architecture., 2020.
URL
https://www. www.wawwiiii..mmmm wwt..///oot//tn/////eee/.o///eee enzz http://slltltoootttaaaaaaeaaaaae htt.::ammppppaaractteeeeeeeetete
pdf
François Pacaud, Sungho Shin, Michel Schanen, Daniel Adrian Maldonado, and Mihai Anitescu.
Accelerating condensed interior-point methods on simd/gpu architectures. Journal of Optimization Theory and Applications, 202(1):184-20) 2024.
13

---

Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Vito,o, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Adam Poliak. A survey recognizing textual entailment as an nlp evaluation. arXiv preprint arXiv:2010.03061, 2020.
Jeff Pool and Chong Yu. Channel permutations for n: m sparsity. Advances neural information processing systems, 34: 34:13316-133211 2021.
Alec Radford, Jong Wook Kim, Tao Xu, Greg Brockman, Christine McLeavey, and Ilya Sutskever. Robust speech recognition via large-scale weak supervision. In International conference on machine learning, pages 28492-28518, PMLR, 2023.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with a unified text-to-text transformer. Mach. Learn. Res., (1))), jan 2020. ISSN 1532-4435.
Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. Communiccations of the ACM, 64(9):99-106. 2021.
Alexander Schrijver et al. Combinatorial optimizationn polyhedra and efficiency, volume 24. Springer, 2003.
Mingjie Sun, Zhuang Liu, Anna Bair, and Zico Kolter. simple and effective pruning approach for large language models. arXiv preprint arXiv:2306. 1695, 2023.
Wei Sun, Aojun Zhou, Sander Stuijk, Rob Wijnhoven, Andrew O Nelson, Henk Corporaal, et al. Dominosearch: Find layer-wise fine- grained n: M sparse schemes from dense neural networks. Advances in neural information processing systems, 34:20721-20732 2021.
Ychui Tang, Yunhe Wang, Yixing Xu, Yiping Deng, Chao Xu, Dacheng Tao, and Chang Xu. Manifold regularized dynamic network pruning. Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 5018-5028, 2021.
Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2008
Wei Wen, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Learning structured sparsity in deep neural networks. Advances in neural information processing systems, 29, 2016.
Carole-Jean Wu, Ramya Raghavendra, Udit Gupta, Bilge Acun, Newsha Ardalani, Kiwan Maeng, Gloria Chang, Fiona Aga, Jinshi Huang, Charles Bai, et al. Sustainable ai: Environmental implications, challenges and opportunities. Proceedings of Machine Learning and Systems, 4: 795-813, 2022.
Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can a machine really finish your sentence? arXiv preprint arXiv: 2019.
Yuxin Zhang, Yiting Luo, Mingbao Lin, Yunshan Zhong, Jingjing Xie, Fei Chao, and Rongrong Ji. Bi-directional masks for efficient n: M sparse training. In International conference on machine learning, pages 4 41488-4149 PMLR, 2023.
Aojun Zhou, Yukun Ma, Junnan Zhu, Jianbo Liu, Zhijie Zhang, Kun Yuan, Wenxiu Sun, and Hongsheng Li. Learning m fine-grained structured sparse neural networks from scratch. arXiv preprint arXiv:2 /02. 040/0, 2021.
Maohua Zhu, Tao Zhang, Zhenyu Gu, and Yuan Xie. Sparse tensor core: Algorithm and hardware co-design for vector wise sparse neural networks modern gpus. In Proceedings of the 52nd Annual IEEE/ACM International Symposium on Microarchitecture, pages 359-371, 2019.
14

---

A Technique Details
A.1 Proofs main results
A.1.1 Derivation of Dykstra's algorithm
In Section 3.2
we focus on solving the capacity-constrained optimal transport problem with entropy
regularization:
max ) (())) s.t. SIM NIM, S'IM N1M. 0sSS 1.
(11)
The objective of can be reformulated as follows:
M
(S. Wi) + H(S) = Σ
Sty
Wiy
Si log(Sis)
M
Sij el|Wal
(12)
S.y log
T w/=1
7 (KL(S || W,)
where = exp(r| and (S || W,) denotes the Kullback-Leibler divergence of S from W, Therefore, the optimization problem can be reformulated as:
3
min DKL S Wr) s.t. S nc S
(13)
i=1
where
= [S S1M N1M), C2 G- (5
(14)
This formulation be interpreted from the perspective of Bregman projections [Bregman 1967
The Kullback-Leibler divergence is a special case of the Bregman divergence generated by the negative entropy function. For any Bregman divergence D&, the Bregman projection of point y onto a convex set C is defined as:
Pe (y) = arg min D y). XEC
(15)
In our context, problem 13 represents the Bregman projection of W, onto the intersection of the constraint sets n C, with respect to the KL divergence. While computing this projection directly challenging, Dykstra's 's algorithm [Dykstra 1983 provides an iterative approach by alternately projecting onto each constraint set.
Dykstra's algorithm for Bregman projections begins by initializing:
())) W, and Q (0) = Q, (0)
Q = 1axM-
(16)
At each iteration f, for each constraint set C, (i 1, 3), the algorithm performs:
((++i/3) =
o Q."). and ((+1) = Q ! (S(++((-1)/3) a g(++1/3) (17)
where PSL arg min KL(r S) denotes the KL projection onto set C. @ and Ø denote element-wii wise multiplication and division, respectively. For our specific constraint sets, the projection operations can be derived analytically:
1. For the row sum constraint C₁, the KL projection has the closed-form solution:
N
L Diag
S
(18)
SIM
This is row-wise scaling operation that ensures each row sums to N.
15

---

2. Similarly, for the column sum constraint C2, the projection is:
(S) = SDiag
(19)
STIM
This performs column-wise scaling to satisfy the column sum constraint.
3. For the capacity constraint C3, the projection is:
P (S) min(S,
(20)
This clement-wise thresholding operation ensures all entries remain bounded by
Notably, for constraints C1 and C2, the dual variables Q0"h and Q can be eliminated from the implementation. This simplification arises because the projection onto C1 scales each row by constant factor to ensure the row sum equals N. When we subsequently update (( according to the ratio between the pre-projection and post-projection matrices, these scaling factors are precisely encoded Q However, in the next iteration, when we project ( C Q onto C₁ the row- wise scaling operation will normalize each row to sum to N regardless of the initial scaling. Thus, incorporating Q has no effect on the final projection result. identical argument applies to the column constraint C2 and its corresponding dual variable Q As result, we only need to maintain single dual variable Q corresponding to the capacity constraint Cz. The complete simplified algorithm is presented in Algorithm
A.1.2 Proof of Proposition 1
We derive the ADMM update rules by sequentially minimizing the augmented Lagrangian with respect each variable. First, we consider the W-update: W arg minw (WW, D(t), v(0).
Since I.p(W (W D(), V(9) quadratic function of W, we can find the minimizer by setting the gradient to zero:
V (W, (W, (9), V(0) = (x + W W) + v + +WW -D())= =0
(21)
Letting H X x AI, this yields the closed-form solution:
w(++) (H pl) (HW v(0) + (D())
(22)
Next, consider the D-update: ( arg minp Lp (W(++1) D, v(9). This equivalent to solving:
min (1) ((+1) D) @ w(++)) DD
(23)
DET
Completing the square and removing constant terms with respect to D, we have:
(w/++)++ v
min DET
(24)
The constraint D E T requires D to have a specific sparsity pattern, which we can represent using binary mask S where S;j = 1 indicates that Dij can be non-zero. Given fixed support defined by S. the optimal values for non-zero elements are exactly those of the unconstrained solution ((++)) (tt)pp Thus, we can express D as:
=
(w(+)) ((1) /p) oS
(25)
Our objective now becomes determining the optimal binary mask S. Substituting this representation of D into the objective:
= L (W(+))) + v(1 os S (w(++1) + vl9pp) -
0
Σ
(w 15
+V /p)(1 - S.y)
2
i.
Σ
(++1) (t) /p) -St))
i
(26)
16

---

The last equality follows since S {0, implies (1 Sıy)² = Sty). Minimizing this expression is equivalent maximizing:
(wlet + /D) s.t. S is binary mask with transposable N:M sparsity
max
Siz 1
(27)
Once the optimal mask S is determined, we recover D(++1) as:
((++1) (witt))+ os
(28)
Finally, the dual update follows the standard ADMM methodology:
v(++1) v p(W(+())) - -D(++1)
(29)
In practice, we employ an adaptive penalty parameter Pr. that varies across iterations, resulting in the following update rules:
W(++) = (H P-) HHW v()) + p.D(
D(++1) (wi++)) V o s((+1),
(30)
((+1) v(0) ( D
This completes the proof of Proposition
A.1.3 Convergence of update (30
We begin by formalizing assumptions regarding the penalty parameter sequence and the quality of each D (f+1) update.
Assumption 1. The penalty parameters {prje= in (30) are chosen to be an increasing sequence such that E 1/pt converges. Additionally, the binary mask ((++1) obtained from our solver does not decrease the objective in (10) compared to ((t), i.e.
(1+1) S
(++1) (w(t ij
v (1) /p)
2
Σ b
S (W!!tt)
v 1p))
(31)
Assumption I is mild in practice. To ensure Σx= 1/p, converges, we can simply select (e increasing geometric sequence. The second condition is readily satisfied by comparing the objective value of ((++1) obtained from our binary mask solver with that of ((), and defaulting to 1(++)) (*)) whenever the new solution would decrease the objective (though empirically, this safeguard never triggers).
We now restate the convergence theorem in its complete form:
Theorem 1. Under Assumption 1 let (D j and [W()) )22 be the sequences generated accord-
ing to 30 Then there exists a matrix W such that (t)) W and (tt) + W as t + 0o.
Proof of Theorem 1 The majority of this proof follows from the convergence analysis in Meng et al.) 2024a Theorem 1], as we employ identical W and V update rules. The critical distinction lies our D-update step. specifically in establishing the following inequality, which cannot be directly borrowed from the original proof:
D (W(++1) v(0
F < D (WW(+1) v v100/2)
(32)
17

---

To establish this inequality, we proceed as follows:
((++)) (witt)) v /10 -1( v(0/pt) 1. 11 -1 - ((44)))
- (1-56 -
(iiis (. + (.1//p )
Σ (1 (1-SS) (i!s ( /
(33)
4
(wi(t))+ + /10/ 3 - |
D -(witt)) /(0)
Here the first equality follows from the representation D(++1) = (w(++1) V S(++)) the first inequality follows directly from Assumption 1 and the final inequality leverages the fact that
D 0 if ! O.
Having established inequality 32 all remaining components of the convergence proof from Meng al. 2024a] Theorem 1] apply directly to setting. Therefore, the sequences (D(0) J1=0 and
(W
30 converge common limit W, completing the proof.
A.2
Algorithmic implementation details
In this section, present tensor-based implementation of Algorithms and 2 which enables parallel processing of millions of weight blocks simultaneously on GPUs, yielding significant computational speedup.
Our implementation is based on PyTorch. Given a weight matrix W and the desired transposable N:M sparsity parameters, we first reshape the matrix into tensor of shape (B, M, Mf) where B represents the number M x M blocks. All algorithmic operations are then applied simultancously to this batched tensor representation.
Implementation of Algorithm [ The Dykstra algorithm naturally lends itself tensor-based operations as it primarily involves matrix vector multiplications and element-wise operations. These operations are directly parallelizable across all blocks through PyTorch's built-in broadcasting mechanisms. A critical implementation detail is performing all operations in log-space to ensure numerical stability, particularly when using large entropy regularization parameters T:
def Log_softmax_noraall (x, dim, N): # Stable log-domail domain normalization
1se torch. torch. 1ogsumexp (x, dim=din, keepdim=True) return (1se torch. log (torch tensor (N)))
Batched Dykstra projections in log-space log_S = tau Norch.abs (batch_k) for in range (max_iter):
# Projection normallie (log_8, dim-1, N=N)
Row marginal (sum_i exp (1og_S) N)
10
log_S mo
11
12
# Projection 2: Column marginal (sum_j exp (log_8) S) R))
log_S = log_ www.sof.aa.oommooooooo tmar__ormallzeeeeeeeeeaett (log_S, dim=2, N=N)
15
Projection 3: Capacity constraint (S 1)
16
log_ tmp log_$ + log_0
log_S = torch. minimum (log_tmp ming.un
zeros_ like (log_tmp))
log_Q 1og_tmp log_S Dual variable update
18

---

Implementation of Algorithm Vectorizing the rounding procedure presents greater challenges due its conditional logic and iterative selection process. We overeome these challenges through careful masking and parallel accumulation operations. The key insight is transforming conditional logic into parallel tensor operations that work across all blocks simultaneously. For the greedy selection phase, we pre-compute all sorted indices and then use Boolean masks and accumulation counters to track row and column capacities across all blocks in parallel. For the local search phase, similarly transform the conditional swap operations into tensor-based score computation and masked updates, enabling simultaneous identification of deficit rows/columns and optimal swap positions across all blocks.
Vectorized greedy selection
sorted_ids abs_blocks (latten(1) . argsort (dim-1, descending-True) rows, cols borted_idx // M, sorted_ids idx M rov_counts, mask col_counts torch zeros ((B, torcor zeros (BB M)) ((B, M, M), dtype-torch, booll, device=device)
batch_idx torch. arange (B, devicesdevice)
for k in range(M*M)
I, rowsl: kl colsl: k]
10
cen_select (rov_counts [batch_ idx, rl (cun_sounts (batch_idx, c] < N)
11
12
Update mask and counters for all blocks simultaneously mask [batch_idd idx, r, c] I= can_select row row_counte [batch_idz, r] can_select
15
16
col counts [batch_idx, c] += can_select
Vectorized local search
19
for range (num_iter):
30
Find unsaturated rows and columns
row row_deficit = mask sum (dim=2) < N # Shape (B, M)
col deficit = mask sum (dim=1) < N # Shape: (B, x)
heeds_fix row_deficit.. any (dim=1) I col any (dim=1)
24
25
# Select deficit rows/columns (according to some criteria)
26
row_idx (blect_deficittcol_ccoccco col_idx
29
Compute and apply optimal aиaрs across all blocks score = compute svap_scores (H, mask, row_idx, col_idx)
30
compute_svap
max_score, flat_idx score. flatten (1)..aa max (dim=1)
swap_valid (max_score 0) & needs_fix
33
34
# Apply swaps only to blocks needing improvement
35
corch.where bodate_blocks torch where where (awaassssa_aaaa valid) [0] apply_swape (mask, update_blocke, row_idx, col_idx, flat_idx)
B Experimental Details
B.1 Experimental setup
Computing environments All experiments were conducted on computing cluster. Unless otherwise specified, we utilized an Intel Xeon Gold 6248 machine with 20 CPU cores and a single NVIDIA 1000 GPU, featuring 192GB of system RAM and 40GB of GPU memory, All language models and pruning methods were implemented using the PyTorch library Paszke al. 2017].
Choice of parameters For Algorithm 1 we set the regularization parameter 7 to 0.005 maxij W and limit the maximum iterations 300. In Algorithm 2 we perform I. 10 local search steps to refine the solution.
19

---

Implementation Details We provide configuration and implementation specifications for both baseline methods and integration frameworks utilized in our comparative analysis of transposable N:M sparsity solvers. For baseline methods:
Network Flow:
We utilize the official implementation from Hubbaa et al.
2021a (accessible via
GitHub) and adapt it for transposable N:M mask generation. To optimize computational efficiency, we employ CPU multi-processing with 16 parallel threads.
2-Approximation: We utilize the official implementation from Hubara et al. 202 la (accessible via vib))itHub) and adapt for transposable N:M mask generation. Similarly, we maximize throughput via CPU multi proceippoo with 16 parallel threads.
Bi-NM: We adapt the method from (Zhang et al., 2023] with slight modifications. First, we apply magnitude-baser
row-wise N:M sparsity to weight matrix W, generating mask S such that W @ S satisfies row-wise N:M sparsity. Subsequently, we impose column-wise N:M sparsity on W @ S₁ to obtain mask S2. The composite mask S ④ S2 then satisfies the transposable N:M sparsity requirement.
cuPDLP: We employ the official Julia implementation from [Lu and Yang 2023 (accessible via GitHub). For this method, we reformulate problem (I) as a linear programming problem by relaxing the binary constraint Syj E {0, to Siş E [0, IJ. This relaxed formulation is then processed by cuPDLP. Notably, we apply cuPDLP directly to the entire weight matrix rather than partitioning it into multiple M M submatrices (i.e., solving (3) block by block), the latter approach would significantly inhibit GPU acceleration capabilities.
Below are the implementation specifications for the N:M pruning frameworks with which we evaluated and integrated our proposed solver TSENOR:
SparseGPT: We adopt the official implementation from Frantar and Alistarh [203] (accessible
via GitHub) and apply the default hyperparameters for one-shot N:M pruning of LLMs.
Magnitude Pruning: We implement magnitude-based pruning by directly applying our proposed
solver TSENOR the weight matrices each network layer to generate transposable N:M masks.
Wanda: We utilize the official implementation from Sun et al. [2023] (accessible via GitHub) with default hyperparameters for one-shot transposable N:M pruning of LLMs. The detailed integration
procedure of our solver with Wanda is elaborated in Section 4
ALPS: We employ the official implementation from Meng et al.
[0024a] (accessible via GitHub)
with default hyperparameters for one-shot (transposable) N:M pruning of LLMs. The detailed
integration procedure of our solver with ALPS is elaborated in Section
Finetuning and Retraining Details We adopt the official implementation of Bi-NM Zhang et al. 2023 (accessible via GitHub), and adapt it for retraining pruned LLMs. To ensure fair comparison, we avoid sparse training from scratch. Instead, we first apply magnitude-based N:M pruning to pre-trained LLaMA3.2 IB, and then retrain the resulting model using Bi-NM.
For both finetuning and Bi-NM retraining, we use a learning rate of 2e-5 and a batch size of size 64 per step. The block size used is 1024 tokens per batch. The effective batch size is obtained by using a physical batch size of on GPU with 32 gradient accumulation steps before each weight update. Training is conducted on the first shard of the C4 training dataset, which contains over 150 million tokens. We employ the Adam optimizer with Py'oorch' 's default hyperparameters. A cosine learning rate scheduler is used, with a warmup ratio of 0.03 and weight decay applied.
B.2
Ablation studies and additional results
B.2.1
Effeetivvness of entropy regularization and rounding procedures
We evaluate the individual contributions of each component in our proposed solver TSENOR for generating high-quality transposable N:M masks. Our analysis compares three distinct rounding strategies:
Simple: Sequential application of row-wise N:M sparse rounding followed by column-wise N:M sparse rounding to obtain the transposable N:M mask. Greedy: Implementation of only the greedy selection procedure for rounding (lines 1-8 in Algo- rithm 2)
Optround: Our complete proposed rounding approach detailed in Algorithm incorporating both greedy selection and local search optimization.
20

---

For each strategy, we evaluate performance when rounding the approximate mask generated by our entropy-regularized optimization (Algorithm[]) [ As a baseline comparison, we also apply each rounding procedure directly to the magnitude of matrix weights (i.e., [W). Figure presents these experimental results.
Entropy Optoound
Entropy Greedy
Entrapy Simple
Optround
Groedy
Simple
13%
10-1
3%
5.1%
6.1%
3.2%
Relative Error
1.4%
1.4%
1.35
10-2
0.50%
0.02%
6.46%
68
0.21
0.13%
10-3
08%
0.064%
2.052%
0.014%
10-4
0.0087%
2:8
4:8
4:16
8:16
8:32
16:32
Figure 6: Solution quality comparison for transposable N:M mask generation. For various N:M sparsity patterns, we evaluate all methods on 100 M blocks sampled from LLaMA3 Dubey et al. 2024] model weights. We report the average relative emor, defined as (S(S*) ((S))/((?) where St is the optimal support and f is the objective defined in TT. "Entropy+" indicates rounding applied to masks generated by Algorithm T
Our findings demonstrate that each component of proposed rounding procedure contributes significantly to mask quality improvement. The greedy selection step reduces error by 50-90%, while the subsequent local search optimization further reduces error by up to an additional 50%. Moreover, applying our rounding techniques to the approximate mask generated through entropy regularization yields solutions with less than 5% error compared direct application the magnitude of weight matrix [W]. These results conclusively validate the importance of each component in our proposed methodology.
B.2.2 Acceleration from exploiting GPU parallelism
We assess the computational gains from GPU acceleration and algorithm vectorization in transpos- able N:M sparsity solver. comparess runtime performance of our Dykstra method (A (Algorithm[[) and rounding procedure (Algorithm 2) across CPU (direct and vectorized) and GPU implementations.
Dykstrs method (Algoritiin))
Rounding (Algaritimn
Matris Size
CPU
V100
H100
CPU
CPU(V)
V100
A100
x
1.29 (3000))
0.04 (e0000)
(-000)))))
0.00 (30000)
1.01 cenor)
(4000))
0.07 (50.00)
(:0000)
2048 x 2018
21.1 (50.44)
0.16 (e000)
(01000)000)
0.57 (10,00)
16.5 (=0.7)
2,87 (2002)
0.11 (50,00)
(=000)
0.05 (10000)
8192 x M392
344 (42.32)
2.99 (60000)
1.60 (0)00))
0.97 (10.00)
270 1.50
38 (10.15)
0.27 (50.00)
0.14 (0000))
0.09 (110.00)
Table 3: Runtime (scconds) for transposable 8:16 sparsity tested on four different device: a single Intel Xcon Gold 6248 CPU, NVIDIA VI00-PCIe-32GB, A100-PCIc-40GB, and H100-PCIe-S00 SOGB. CPU(V) denotes vectorized implementation. Results are averaged over 10 trials with standard deviations in parentheses.
Our hardware-ane -awrrere-wwweeeeeeeee design yields remarkable speedups: GPU acceleration provides up to 300x faster execution for the Dykstra method compared to CPU. For the rounding procedure, our vectorized CPU implementation achieves an 8x speedup, while GPU acceleration delivers up to 3000x acceleration over the baseline CPU implementation. These results demonstrate how our tensor operations based algorithms effectively leverage GPU architectures, particularly for large matrices (8192 8192), enabling efficient processing of ofte-ooftthe-rt models with minimal computational overhead.
21

---

B.2.3 Layer-wise reconstruction error comparison
We investigate the impact of transposable N:M sparsity on model performance by analyzing layer- wise reconstruction error in LLaMA3.2-8B after applying the ALPS one-shot pruning method. We define reconstruction error XXW / configurations.
Table presents results for various N:M
Our analysis reveals that while transposable N:M sparsity increases reconstruction error compared to standard N:M sparsity, this differential diminishes with larger M values decressinn from approxi- mately 30% additional additional error introduced by transposable constraints over standard N:M sparsity is smaller than the error increment from unstructured to standard N:M sparsity. Furthermore, transposable N:M sparsity with M=32 produces substantially lower reconstruction егтоr than standard N:M sparsity with M-4. These findings validate that N:M patterns with larger values offer superior performance and underscore the importance of our proposed solver.
small M values to only 7% larger M values. Notably, at M=32, the
50% (uns:
0.021)
62.5% (uns:
0,045)
Sparsity
2:4
4:8
8:16
16:32
3:8
6:16
12:32
0.041
0.031
0.026
0.024
0.063
0.055
0.050
Tran N.M
0.058
0,041
0.032
0.027
0.078
0.063
0.056
75% (uns: 0.093)
87.5%
(uns; 0,199)
Sparsity
1:4
2:8
4:16
8:32
1:8
2:16
4:32
N.M
0.143
0.121
0.108
0.102
0.247
0.227
0,215
N:M
0.122
0.109
0.253
Table 4: Layer-wise reconstruction enror for the "self attn.k proj" layer in the first block of LLaMA33 8B, comparing standard N:M and transposable N:M sparsity across different N:M patterns. The reconstruction error values for unstructured pruning at each sparsity level are shown in parentheses.
B.2.4 Comparing standard and transposable N:M sparsity after fine-tuning
We have compared one-shot pruning performance between transposable and standard N:M sparsity in Figure 4 We now compare fine-tuning performance between these settings across different N:M patterns on LLaMA3.22 1.2.-.2-1BB 1B in the following table. Similar to one-shot pruning, the performance gap between transposable N:M and standard N:M diminishes dramatically as increases from 4 to 32 (by approximately 80%).
Spansity
2:4
4:8
8:16
16:32
N:M
19.4
18.1
17.4
17.1
Tran N:M
22.1
19.7
18.4
17.7
Table 5: Perplexity comparison of LLaMA3.2-18 pruned using ALPS with TSENOR followed by fine-tuning, evaluated on both standard and transposable N:M sparsity across various N:M patterns.
B.2.5 Comprehensive model performance across N:M sparsity patterns
We evaluate the performance of one-shot pruning methods by comparing SparseGPT, ALPS, and TSENOR integrated with various techniques (MP, Wanda, and ALPS) on LLaMA models, as pre- sented in Tables 6 8 Our experiments examine both standard N:M and transposable N:M sparsity patterns across multiple configurations (1:4, 2:8, 4:16, 8:32, 2:4, 4:8, 8:16, and 16:32). Performance evaluation contains perplexity WikiText2, PTB, and C4 datasets, as well as reasoning abilities assessed through accuracy on PIQA, ARC-Easy (ARC-E), ARC-Challenge (ARC-C), Hellaswag (HS), Winogrande (WG), RTE, OpenbookQA (OQA), and BoolQ.
22

---

Spursity
N:M
Algoritlm
Transpose
C4
Purplesity
WT2
PTB
PRQA
115
ARC-E:
ARC-C
Zero-dunt (T)
WG
RTE.
OQQ
BoolQ
Arg
SparsodPt
738.04
110367
937.13
50.82
25.25
28.20
23:38
51.21
50.54
25.80
18.87
37.01
203.17
236.28
254.55
27.77
21.59
50.83
54.15
42.81
38.44
dppareePPT
$825.35
51.03
153KOR-ALBS
758.53
1032.33
1570.19
52.29
27.36
25.09
48.22
51.99
38.81
37.00
Sparse22
X
377.12
474,93
457.05
52.94
27.84
30.600
21.84
49.25
52.35
25.20
43.67
37.96
AL28
173:36
161 46
195.5 52
56 37
25.67
12.28
21.59
51.3 75
52.71
25.00
46.3
19.50
288
T53NOR- Kanda
1144154.00
1067911.25
593506.12
51.5 5%
25.75
25.80
26.62
$9.09
68.74
25.20
$2.75
39.22
1951 98
$39500 00
52. 50
36.07
50.90
40:95
37.23
T5SHOO PS
563.74
83
13.99
79.67
21.50
48.78
53.79
41.01
37.67
54.13
52.71
149.47
152.16
184.76
20.90
51.99
25.00
$1.01
39.72
4:16
TSSMOR- Vands
126002.87
118177 99
77005 69
51 25
76.71
34.75
35.60
49.3 96
48. 58
28.40
45.29
97.59
TSSHOR-62 Sear0uR--pasCCPPPPPp arF
906.56
1434,3
1982.64
52.85
26.47
28.16
22.95
19.09
51.99
24.00
39.72
37.03
TESKOR al PS
218.61
256.94
29K.77
$3.48
27.85
29.63
21.93
50.91
$2.85
26,80
42.57
38.11
Spa
X
232.80
293-42
54.00 90
27.94
10.68
22.18
53.71
61. 14.04
40.61
138-57
116.78 78
140.45
66
28.86
12.07
21.13
85
51.71
60:67
41
TSaddR-Vanda
142482.82
76792.37
51.74
26.35
25.42
26.71
52.71
29.40
39.89
850.53
51.07
18.17
TSSHUR-ALPS
109.09
176.82
53.10 10
27.95
30.96
22.10
90.83
53.07
28.00
41.25
38.41
SparsedPt
K
44,96
52,99
50.79
62.57
39.15
41.92
23.63
$4,93
54.51
29.20
52.17
46.01
ALPS
K
55.14
28.50
41.15
65. 60
41.92
44.11
25.68
55.41
52.21
50000
62.3 20.38
47.04
244
TESKOR- Vands
12718:35
3241132
30749 90
52.67
27.19
27.78
23.63
50. 56
52.71
24.20
41.99
37.56
TSEHUR-BP -par-sopPFFF
93.05
67.79
105 94
56.3 58
31.35
34.81
21:50
52.01
53.79
26.20
50.70
42.12
T53KOR-
56.11
51.11
75.79
39.09
36.91
23.29
50.91
53.17
23.00
62.
43.37
44.57
25.85
54.
53.79
62.17
47.66
A12S
27.56
20.56
52,89
68.01
16.91
28.50
56.7
52.71
52,80
62.19
49.59
48
TESKOR- Vanda
1226.75 75
1298.31
1546.12
54.13
28.50
31.23
21.76
49.33
52.71
23.40
40.73
37.72
TSSHUR- SepTRR---aaa SparseOFT
52.08
62.05
60-67
60.99
57.59
19106
25.17
53.04
53.
25.00
51.01
46.83
TSSMOR- AL
37.94
29.76
47.25
36
41.06
40.52
25.77
55.41
52.35
25.00
62.
46.32
SparsedPt
X
28.02
20.27
33.15
67.05
47.26
48.15
27.82
55.4
52.71
31.80
62.32
49.06
28.78
67.57
49.96
28.16
57.06
52.71
31,90
63.53
50.08
8:16
56
21.76
TS3KOR-6 arsu
54.30
54.87
61,87
46.43
T5SMOR--4 af PS
30.38
22.80
36.23
66 10
44.71
47.01
27.47
96.51
$3.07
50.30
62.14
4841
SpareeGPT
X
26.91
19.13
32.14
66.97
88.45
48.19
27.47
55.83
53.43
33.00
62.26
49.46
A125
22.97
16.25
27.6
68:88
51 30
50.34
30.03
56.43
52.71
33,80
62.94
50.68
16:32
BEaKOB-Wandda
144.48
115.23
173.61
61.21
36.12
38.72
23.89
51.54
$1.26
25.20
47.19
41.89
14.16
40.13
64
46.3
76 11
59:71
20.00
62.11
7SENOR-ALPS
25.92
19:12
31.08
66.21
50.55
29.95
55,80
54.51
62.39
49,69
Table 6: Performance analysis for (transposable) N:M pruning on LLaMA3.2- 1B model. Lower
values are preferred for perplexity, and higher values are preferred for zero-shot tasks.
N:M Spansity
Algurithm
Trunsguse
Perplesily (1)
Zero-shot (t)
WT2
PTB
PIQA
ARC-E
ARC-C
KTE
(M)A
Hool()
Avg.
SpareoGPt
37.83
ALPS
142.86 86
227.05
246.41
$4.08
27.79
26.62
21.3
26.60
TSEMOB- -audle
217413.53
216446.90
234474,44
51.14
26.17
25.55
27.47
52.80
27.40
46.94
THEMIR -SpareeGe
833 05
2068 74
3004.19 19
52.01
25.35
27.10
25 25.68
49.25
51.62
28.0
31.83
57.23
THENDE-ALE ALPB
295.36
$26.59
599.66
53.10
27.15
26.07
22.78
50.20
$2.35
27.60
37.89
37.39
SpareeGPT ALPS
196.82
238 65
295 95
53.21
28:28
29. 38
21
49.01
$1.26
26,80
51 65
38.93
103.2 22
119.57
163.66
54.75
29.15
50.18
20.52
45.46
52.71
26,00
61.3 87
40.49
2.8
TEENOR- Vanda
163461.16 16
170679.30
192995.58 58
51.14
26.14
25.00
27
50.14
53.79
27.60
45.3 1.235
33.37
115 WIT -SparswdPy
789
0%
57.07
35.85
40.72
1.99
37 83
19PNO pS
189.85
25
53.10
27.53
25.83
21 16
40.49
52.71
27. 27.20
20
31
48.70
41.05
ALPS
95.39
121.15
55.82
20.05
26.00
4:16
THENOR Vanda
60023.27 27
94040.87
120N17.32
50,60
25.84
24.75
27
49.64
50.54
37.80
54.25
38.11
THEMIT- Saptt--ppaee
327 64
395.5
S71.1
$2.39
27.56
30.21
35.81
47.99
52.31
25.40
46.67
36.22
TEENOR- ALDg
137.25
196899
226.89
53.97
28.11
50.30
21.59
50.99
52.71
23.20
55.41
40.05
SparswGPT ALPS
X
179
12
183.01
$3.86
28,80
20 20,50
21 21.67
48.46
54.15
23
62.23
40
80L12
82.28
110.75
56.64
31.27
32 32.65
19:30
51.38
52.35
23.00
61.99
41.63
8:32
FEEWIB-Vandd
73379.13 13
106992.48
259678.69
50.96
25.06
24.83
27
50.12
52.91
26,60
55.26
39.32
08
375.69
$2.56
25
49:00
52.71
37.72
THENDE-ALD ALPS
111.36
16
175.00
25.92
30.43
20.39
53.07
26
40.11
21.11
34.47
50.45
$1.
25
60.54
52.35
62
51.55
ALPS
23.92
1876
27.28
70.62
$4.45
56,
29 10:35
60.54
52.35
33.00
68.55
53.12
24
THEEIIR Vanda
5433.83
5336.00
4977.5 34
$1.47
25.89
27.74
21
$1.07
52.71
26.60
31.80
37 16
TRENOR- Spar
56.12
45.49
87.28
61,81
36.78
40.99
24.25
51.78
$2.71
27.40
62.25
44.74
TEENOB-ALE ALPS
41.19
35.02
54.76
63.93
42.47
44.49
26.96
$4.30
52.71
25,40
62.87
47.02
SpacseOPT
21.71
16.06
24.00
70.46
57.57
$7.41
32.51
63.61
53.07
53.00
70-46
54.86
ALPS
19:43
14.54
32.19
71.38
37
60.40
36.01
65.35
59.31
35. 35.40
69 30
57.05
TSPMIT Vands
1142.41
1184.56
974.31
$4.03
27.75
30.64
22.99
$0.50
52.71
26.00
50
FEENOR-8pazode
31.15
24.33
36.81
67.79
49.37
50.84
25.2
58.33
57.04
31.00
65.38
51.00
TEEMOR-ALPS
20.11
29.75
69.37
52.49
55.00
29.27
57.76
33.00
67.15
52.92
SparsuoPt
13.99
73.07
66.56
63.83
34.30
63.06
58.12
34,60
71.35
57.11
ALPS
17.60
2002
73,12
62.38
64.14
37 37
65.30
55,00
36,60
72.84
58.58
8:16
17PPIT- Venda
966.21
686.5
729-45
$5.96
20.25
54
22.
49.35
$2.31
26.00
45. 10
9982
TSEMUR- -paar
23.92
17.75
27.56
70.24
55.56
56.25
31.
59.75
55.00
$2,80
65.00 69
53.42
TSEMUR-ALP ALPP
20.26
15.11
22.97
72.20
58.54
80.25
35 15.32
61.64
51.99
35.40
7000
55.67
SparooGFP
X
18.11
13.02
20.37
73.12
62.27
62.67
34.81
65.75
60.63
35.20
71.53
58.25
ALPS
16.76
12.06
18.78
71.56
61.10
64.48
36.52
65.56
57.40
39:00
72.30
59.30
-oarda- THEMIR-GparewGeP
436.13
262
363.91
30.54
37.
21
52.71
49 92
40.66
59.64
13.08
20.43
57.40
73.32
Table 7: Performance analysis for (transposable) N:M pruning on LLaMA3.2-33 model. Lower
values are preferred for perplexity, and higher values are preferred for zero-shot tasks.
23

---

N:M Spursity
Algorithm
Transpose
Porplesity
Zem-shot (T)
C4
WT2
PTB
PIQA
HB5
ARC-E
ARC-C
WG
RTE.
OQA
BoslQ)
Avg
SparscOPT
188
221.53
317.35
52.45
28.00
29.17
21:35
47.91
54.15
26.30
37.
57.23
148.71
162 76
25.38
51:23
49:31
39.57
CREMOR "SEM 61.25
565.25
1116.69
1077.45
26.26
28.66
23.59
49.49
12.35
27.80
37.83
57.14
213.5
339
354.03
57.77
27.37
29.43
20.52
49.17
52.35
37.20
57.83
37.10
Sparse OPT
130.02
156.07
1R2 26
51.54
28.65
29 30.00
23.04
49. 80
53.07
27.00
40.52
18.27
ALPS
79.71
97.96
119.74
55.95
31.45
$1.19
21.76
$1.93
$2.71
26.40
61.31
41.50
2:8
slandd
337972.47 47
106156.00 78
210915.56 56
56.38
48
26.
76:71
48.78
51
78.20
51.09
18.90
CBEMOR+ 3pazsss07 A1.78
272.11
414.92
27.18
23.02
21.93
52.71
36.96
42
98:25
10782
152.00
15
29.19
$1,62
20.05
51.22
52.51
20
60.55
40.99
ALFS
65.58
64.25
92.66
57.83
33.26
53.25
20.99
$4.14
$3.79
27.20
62.14
42.83
4:16
95070 10
107645 22
106288877
$1.52
26.35
25.67
76.37
50. 16
51 19
30.40
37.89
17.56
CBEHOR- -aa----aaeee sOFTT
208.27
293.7
348.83
53.21
27.85
23,09
22.46
50.51
52.25
26.20
37.83
37.34
A1.8
111.11
14005
166 55
70.31
50.18
21:16
50.57
53.71
76.60
38.53
Oparne
90.09
115.57
58.47
53.14
34.79
35.51
21.76
52.71
62.75
8:32
79085 44
51239/92
44018844
50.93
25.92
26.05
26.04
50.67
51
79.50
55.55
12.41
TBEMCR+ Sparaeoet
170.92
21402
317.64
53,05
27.32
29.75
22.70
49.33
52.71
28.30
39.02
37.71
TSEMORLA A1.70
09.05
152.66
155.01
55.11
20.55
50.81
21:42
50.28
$2.71
26.80
50.25
59.62
SgarseOPT
16.19
46
71.20
$3.80
34.47
64.72
$4.40
71.81
56.30
19:67
1461
22.18
61.57
61.11
35.92
67-17
73.52
59.04
52.71
76.20
37.51
28.31
43.72
39.25
25.46
55.
53.07
28.00
66.24
46.79
DSEMOCL AL27
32.65
24.74
39.00
67.85
48.30
48.33
28.
58.00
52.71
29.20
66.
49.91
12.50
12:91
18.55
74.87
40
67.25 .3.43
18. 14
60. 30
55.25
97.20
75.0%
59 64
ALF3
16.06
11:31
16.63
75.90
57.38
63.
40. 10
28.28
61.37
38,00
75.67
62.00
4:8
1034.43
952.47
1990.95
70.70
22
30.33
38.96
24:13
17.93
27.61
35.35
31.57
54.51
74.13
54.85
21.79
15.77
34.39
57.16
15.48
10.66
16.04
75.63
68.41
65.74
40 70
60.58
59.63
39,00
77.55
63.08
KLDS
14.70
10.08
15.14
76.55
71.35
68.06
41.72
70.72
58.48
38
77:92
62.80
8:16
TBEMRR-Rada
383.74
251.90
413.10
57.78
32.44
$7.42
22.35
52.41
$2.35
27.40
64.04
40.77
18:55
13.10
19.79
73.56
62.91
61.15
37.08
63.51
57,40
37.60
74.13
58.66
17.03
11.96
17.98
75.90
56.24
66.82
38.31
67.96
56.68
36.60
71.37
50.71
OFF
89.6
71.27
14.02
9.47
14.60
43.52
75.47
64.23
16:32
336.90
219:25
379.07
61.04
34.11
64,62
25.00
52 96
52.91
26.50
55. 15.17
44.35
16.76
11.40
17.56
73.18
65.80
64.06
38.57
67.32
60.65
36.80
74,34
60.09
15.11
10.28
15.74
76.50
08.64
68.61
41.13
87.
61.37
39.00
79.11
62,80
Table 8: Performance analysis for (transposable) N:M pruning on ....MA3.2-88 model. Lower
values preferred for perplexity, and higher values are preferred for zero-shot tasks.
B.2.6 Additional results on fine-tuning transposable N:M sparse models
We show the results of fine-tuning transposable N:M sparse models pruned with our approach (TSENOR+ALPS) and compare against Bi-NM [Zhang et al. 2023] across multiple sparsity configura- tions (1:4, 2:8, 4: 4:16, 8:32, 2:4, 4:8, 8:16, and 16:32). Performance evaluation includes perplexity measurements on WikiTeex2,, PTB, and C4 datasets, as well as reasoning abilities assessed through accuracy scores PIQA, ARC-Easy (ARC-E), ARC-Challenge (ARC-C), Hellaswag (HS), Wino- grande (WG), RTE, OpenbookQA (OQA), and BoolQ.
Method
Config
C4 |
WT2
PTB
PIQA
ARC-E
ARC-C1
WG 1
OQA
BoolQ
Avg
72.74
101.57
120.19
57.18
27.73
33.63
21.76
51.38
53.43
25.40
61.90
48.84
57.66
75.04
58.16
28.28
34,51
53.43
62.08
B1-UM
2:8
53.59
69.83
92.71
59,36
29.06
34.68
22,53
50.12
52,71
25,40
60.64
41.81
2:8
40.27
44.21
57.42
59.85
29.94
35.02
21.16
49.96
53.07
25,80
61.41
42,03
B1-NK
4:16
45.81
56.77
77.02
60.83
29.97
36.41
21.59
50.83
53.79
24.40
61.62
42.43
4:16
35.66
37.49
51.27
61.21
32.74
36.24
22.10
51.14
52.71
28.20
62.11
43.68
B1-NM
8:32
42.25
46.39
63.22
61.15
30.81
37.58
23.63
$1.54
52.71
25.80
$1.37
42,20
8:32
33.42
33.25
47.26
62.13
33.90
37.75
22.78
51.54
53.43
27.00
62.17
43.84
Table 9:
Performance analysis for (transposable) N:M pruning on LLaMA3.2-1B IB model. Lower values are preferred for perplexity, and higher values are preferred for chot tasks.
24

---

Method
Config
C4
WT2
PTB
PIQA 1
HS
ARC-E 1
ARC-C1
WG
RTE
0Q4
BoolQ 1
Avg
Bi-MM
2:4
36.02
42
63.22
62.40
32.07
36.78
23.29
51.14
53.43
26.40
59.57
43.14
TSEXOR-ALPS
35.67
23.81
54.56
4:8
27.76
31.95
44.43
63.76
33.09
37.25
22.78
51.54
53.79
28.00
59.91
43.77
8:16
28.70
33.48
46.47
63.33
33.85
37.79
23.55
51.54
52.35
27.60
56.24
43.28
TS6MON
8:16
26.28
30.33
40.71
63.60
34.08
39.27
24.40
49.33
53.43
28.60
$7,40
43,76
B1-AX
16:32
27.84
32.10
44.68
63.55
33.90
39.02
23.12
49.58
52.71
27.00
58.69
43.48
16:32
25.57
28.38
39.30
63.28
34.41
39.31
23.21
52.01
54.87
28.20
60.12
44,43
1:4
126.51
272.02
228.17
57.45
27.10
31.57
20.99
$3.67
$2.35
24.00
53.33
40.06
196D/RRAAPS
1:4
72.35
122.32
137.06
56.96
26.99
31.61
21.33
49.64
51.26
23.80
55.41
39.63
B1-NM
2:8
108.17
193.02
179.63
58.27
27.46
33.12
21.42
50.99
53.07
22.60
59.45
40,80
1SESOR-ALPS
2:8
56.41
85.11
99.08
$8.49
27.38
33.59
20.99
51.62
53.07
25,00
60.00
41.27
Bi-NM
4:16
97.56
162.79
154.25
59.58
27.91
32,87
21.25
50.91
$4.51
23.80
62.17
41.62
1SBMOR-ALPS
4:16
48.74
67. .9.69
87.67
58.76
28.41
33.84
21.42
52.41
53.07
24.80
62.23
41.87
Bi-UM
8:32
88.68
144.25
148.01
59:47
28.23
33.38
22.27
50.12
52.71
24.80
61.77
41.59
T3FMOOR-ATPP
22.70
61.83
Table 10: Performance analysis for (transposable) N:M pruning OPT-350M model. Lower values are preferred for perplexity, and higher values are preferred for zero-shot tasks.
25

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: At the end of the introduction, we include paragraph that clearly states the contributions and scope of our paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitation of the work in Section 6
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
26

---

Justification: All assumptions and proofs for theoretical results (derivation of Algorithm Proposition and Theorem [ are provided Appendix A.1
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We thoroughly describe our proposed algorithm in Section 3 and we include all other details necessary for reproducing the results in Appendix A.2 and B.1
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
27

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Our code is publicly available at:
/ab/
TSENOR
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
ctiaps..ccpuulic/guuu
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We provide detailed settings of our proposed transposable N:M mask solver, its competitors, and the pruning frameworks consider in Appendix B.I
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: For runtime analysis of our transposable N:M mask solver, we conducted 10 trials, reporting means and standard deviations. Solution quality evaluations were averaged across 100 sampled matrix blocks. LLaMA3 pruning experiments used a single seed due to computational constraints.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
28

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπτог rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We provide details of the computational resources used for our experiments in Appendix B.I
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https///aaaarrpeccooooacaccaaaaa
Answer: [Yes]
Justification: We have reviewed the NeurlPS Code of Ethics and ensured that the research conducted in this paper fully complies with it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., s if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
To the best of our knowledge, our work has no societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.

---

If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), faimess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer[[NA]
Justification:
To the best of our knowledge, our work poses such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but encourage authors to take this into account and make best. faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: At the beginning of Section 5.2
we cite all the datasets and models used in experiments. In Appendix B.I we provide the sources of the code used our experiments.
Guidelines:
The answer NA means that the paper does
existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
30

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
31

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Although our work can be applied LLMs pruning, the core algorithm developed in our paper does not involve LLMs as important, original, or non-standard components of the algorithm itself.
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non ntn-standard components.
Please refer to our LLM policy for what should or should be described.
32


Reviews:
[{"review_id": "2pPkg0hOCi", "reviewer": "Reviewer_oDcR", "summary": "This paper presents TSENOR, an efficient algorithm for generating transposable N:M sparse masks that enable both forward and backward pass acceleration in large neural networks like LLMs. TSENOR uses an entropy-regularized optimal transport formulation solved with GPU-parallelizable Bregman projections to find high-quality fractional masks, then refines them into valid binary masks with a fast rounding procedure. Integrated with popular pruning frameworks like SparseGPT, Wandda and ALPS, TSENOR scales to billion-parameter models, supports flexible N:M ratios, and achieves substantial speedup with minimal performance loss. This work has showed it can achieve siganifically less relative error compared to other transposable pruning methods. Furthermore, it integrates with ALPS and achieves comparable performance with non-transposable ones on LLMs like LLaMA3.", "questions": "1. In section 5.2.1, it evaluates the tradeoff between speedup and performance loss, which seems to be one-shot pruning without fine-tuning.  If I understand correctly, it compares the one-shot pruning performance and estimates the speedup of fine-tuning. A more straightforward way might be to evaluate both on fine-tuning settings. \n2. What are the fine-tuning settings? If fine-tuning hard, will the transposable method like Bi-NM also work very well?", "limitations": "My main concern is that although the paper proposes an efficient method for generating transposable N: M sparse masks, the practical benefit may be limited if, after fine-tuning, models perform similarly to those produced by other transposable sparsity methods.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The paper has formulated transposable N: M sparsity cleanly as an entropy-regularized optimal transport problem with capacity constraints, which is mathematically well-founded. \n2. Dykstra’s algorithm and the proposed rounding algorithm with the local search are highly efficient, which can achieve the lowest relative error compared to the optimal solution while speeding it up by 100 times. \n3. This method looks like an effective plug-in for the ALPS method. And for one-shot pruning, this transposable N: M sparsity can achieve comparable performance with non-transposable ones on LLMs.  \n\nWeaknesses:\n1. As transposable N: M sparsity is designed to speed up both forward and backward, it is best to show practical benefit on more training or fine-tuning settings. While this paper has demonstrated it by fine-tuning LLaMA3.2-8B, although with much lower relative error compared to other transposable methods, the final performance improvement over Bi-NM seems limited.", "was_revised": true, "final_justification": "My concerns are cleared by the experiments provided in the rebuttal and I decide to raise my score.", "rebuttal": "We would like to thank the reviewer for their thoughtful feedback. Below, we provide some answers/clarifications.\n\n**As transposable N: M sparsity is designed to speed up both forward and backward, it is best to show practical benefit on more training or fine-tuning settings.**\n\nWe appreciate the reviewer's valuable suggestion. We have conducted additional fine-tuning experiments comparing TSENOR with Bi-NM on OPT-1.3B, with PTB perplexity results shown below (- denotes still running—will be updated later): \n\n|N:M |2:4 | 4:8 | 8:16 | 16:32| \n|---|---|---|---|---|\n|TSENOR|66.2| 46.7| 38.4|35.8|\n|Bi-NM |67.9|43.6|-|40.2|\n\nAs shown, TSENOR outperforms Bi-NM, particularly at larger M values. We will include more fine-tuning experiments across multiple models in our revised manuscript to further demonstrate TSENOR's practical benefits in fine-tuning settings.\n\n\n**While this paper has demonstrated it by fine-tuning LLaMA3.2-8B, although with much lower relative error compared to other transposable methods, the final performance improvement over Bi-NM seems limited.**\n\nFine-tuning is a highly effective step for performance recovery, and performance gaps between different pruning methods narrow significantly after fine-tuning [1,2]. Therefore, TSENOR's 3% improvement over Bi-NM after fine-tuning demonstrates TSENOR's superiority as a pruning algorithm, as these gains are achieved within an extremely competitive performance range.\n\nAdditionally, TSENOR reduces the memory footprint during fine-tuning. While Bi-NM requires storing two different N:M sparse masks (one for forward and one for backward passes), TSENOR needs only a single transposable N:M sparse mask.\n\n\n[1] Sparse Matrix in Large Language Model Fine-tuning\n\n[2] A Simple and Effective Pruning Approach for Large Language Models\n\n**What are the fine-tuning settings? If fine-tuning hard, will the transposable method like Bi-NM also work very well?**\n\nThe fine-tuning settings are provided in Appendix B.1. For both Bi-NM and TSENOR, we fine-tuned them on the first shard of the C4 dataset, which includes over 150 million tokens. We terminated fine-tuning until the loss showed no significant decrease. Bi-NM achieves backward speedup by using approximate gradients during fine-tuning. This approximation inherently limits its fine-tuning performance improvement compared to TSENOR, which maintains exact gradients throughout training.\n\n**In section 5.2.1, it evaluates the tradeoff between speedup and performance loss, which seems to be one-shot pruning without fine-tuning. If I understand correctly, it compares the one-shot pruning performance and estimates the speedup of fine-tuning. A more straightforward way might be to evaluate both \non fine-tuning settings.**\n\nThank you for this valuable suggestion! We compare fine-tuning performance for transposable and standard N:M sparsity across different N:M patterns on LLaMA3.2-1B in the following table. We will include this comparison in our revised manuscript.\n\n|N:M |2:4 | 4:8 | 8:16 | 16:32| \n|---|---|---|---|---|\n|Transposable N:M|22.1| 19.7| 18.4|17.7|\n|Standard N:M |19.4|18.1|17.4|17.1|\n\n\n\n**My main concern is that although the paper proposes an efficient method for generating transposable N: M sparse masks, the practical benefit may be limited if, after fine-tuning, models perform similarly to those produced by other transposable sparsity methods.**\n\nSince TSENOR generates pruned models with much higher performance compared to other transposable sparsity methods after one-shot pruning, it provides advantages in two key scenarios: (i) Limited fine-tuning: When training resources are constrained, TENSOR maintains superior performance over other methods due to its stronger starting point. (ii) Early termination: TENSOR can be early terminated during fine-tuning while achieving comparable results to fully fine-tuned models from other transposable methods, thereby saving computational resources.\n\nEven with full fine-tuning, TSENOR maintains a non-negligible improvement over Bi-NM, as mentioned previously."}, {"review_id": "xqbhQE3Jh2", "reviewer": "Reviewer_xTpm", "summary": "TSENOR is a work providing high quality N:M masks that scales to large models with efficient algorithms and exploitation of GPUs speedup in tensor multiplication. TSENOR generates weight mask by adapting Dykstra’s algorithm to solve an optimal transport problem. A greedy rounding method is further applied to create transposable binary mask.", "questions": "If one cares only about inference, can TSENOR be easily adapted to provide non-transposable masks?\n\nIt seems that optimal solution is more reachable when M is smaller than 8. Is it a general conclusion that larger M is always a significant improvements in solution quality (as shown in Upper Figure 4) in different types of networks?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\nTSENOR well balances the effectiveness and efficiency of N:M sparsity, which enables large M for higher quality solutions while keeping solving time within a feasible range. \nThe paper is well-written, algorithms are motivated in a clear way and explained with good examples. \nAblation study in the appendix covered most concerns of mine. For different features of TSENOR, there are evidence to justify their usage.\n\nWeaknesses:\n\nFor exploiting the GPU tensor multiplication, it would be nice to have a usable framework for TSENOR.\nSource code is not provided, and it is difficult for anyone tends to reproduce the results even though hyperparameters are provided.\nFine-tuning performance of TSENOR is not very well presented.", "was_revised": true, "final_justification": "I find this paper well written and the idea is noval. The authors replied to my questions with good answers and the discussion with other reviewers seems effective. I have no additional opinions about this paper, and I find my initial score the most suitable for this paper.", "rebuttal": "We would like to thank the reviewer for their thoughtful feedback. Below, we provide some answers/clarifications.\n\n**For exploiting the GPU tensor multiplication, it would be nice to have a usable framework for TSENOR. Source code is not provided, and it is difficult for anyone tends to reproduce the results even though hyperparameters are provided.**\n\nThank you for this valuable suggestion! We have prepared our complete implementation for public release. Due to conference guidelines prohibiting links in rebuttals, we will make the code available upon paper acceptance.\n\n**Fine-tuning performance of TSENOR is not very well presented.**\n\nWe appreciate the reviewer's valuable suggestion! We will include more fine-tuning experiments comparing TSENOR with other transposable methods in our revised manuscript. We have conducted additional experiments comparing TSENOR with Bi-NM on OPT-1.3B, as shown in the following table (- denotes still running—will be updated later): \n\n|N:M |2:4 | 4:8 | 8:16 | 16:32| \n|---|---|---|---|---|\n|TSENOR|66.2| 46.7| 38.4|35.8|\n|Bi-NM |67.9|43.6|-|40.2|\n\n\n**If one cares only about inference, can TSENOR be easily adapted to provide non-transposable masks?**\n\nThis is a good point. TSENOR is designed for generating transposable masks, but can be easily adapted to generate non-transposable masks. In this case, the per-block problem in Equation (2) only involves row-wise N:M constraints and can be solved directly by selecting $S_{ij}=1$ if $j$ is among the largest N values in row $i$. This version can still be integrated with layer-wise pruning approaches, including Wanda, SparseGPT, and ALPS, as discussed in Section 4.\n\n**It seems that optimal solution is more reachable when M is smaller than 8. Is it a general conclusion that larger M is always a significant improvements in solution quality (as shown in Upper Figure 4) in different types of networks?**\n\nYes, this is a general conclusion. Transposable N:M sparsity with smaller M imposes much stricter constraints — for example, an 8×8 block with 2:4 transposable sparsity has about 65 million feasible masks, while 4:8 transposable sparsity has greater than 100 billion feasible masks. Larger M values provide more flexibility in mask selection and therefore consistently yield better solution quality across different network types. This is further validated by our results on OPT-1.3B (as shown above), where larger M values consistently achieve higher performance."}, {"review_id": "DYogeyx5B7", "reviewer": "Reviewer_NiHC", "summary": "The paper introduces TSENOR, an algorithmic framework for efficiently generating transposable N:M sparse masks, essential for accelerating both forward and backward passes in neural network training. The key idea is formulating the mask generation problem as multiple optimal transport problems with entropy regularization, solved through Dykstra’s algorithm followed by a specialized rounding procedure. TSENOR is integrated into popular pruning methods such as Wanda, SparseGPT, and ALPS. The authors report significant computational speedups and reduced error relative to existing heuristics. Experimental results on large-scale models such as LLaMA demonstrate the practical efficacy of TSENOR, especially highlighting performance gains at larger M-values (e.g., 16:32 sparsity).", "questions": "1. Clarification of Computational Benefits at Larger M-values: Your claim— \"Our experiments show that networks with larger M values (e.g., 16:32) provide the same computational benefits as smaller M values but with much less impact on model accuracy\"— is unclear.\n    * Which specific experiments support this claim?\n    * Given that larger M-values inherently become less structured, it is counterintuitive that computational benefits remain constant. Could you clarify how these masks remain efficiently acceleratable?\n2. Accuracy-Speed Trade-off Analysis: If I understand correctly, transposable N:M sparsity should accelerate both training and inference. However, the current manuscript lacks explicit results that clearly illustrate improved accuracy-speed trade-offs.\n    * Could you clarify if and where such comparative results exist in the paper? If not, can you provide a rationale or consider including this comparison?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths:\n1. Novel Optimization Formulation: Formulating mask selection as an optimal transport problem with entropy regularization is both elegant and theoretically appealing, significantly simplifying computational complexity compared to previous methods.\n2. Efficiency and Scalability: The GPU-optimized implementation of TSENOR demonstrates remarkable efficiency and scalability, achieving substantial speedups (up to 100×) over baseline methods, enabling its practical application to large-scale language models.\n3. Practical Integration with Popular Methods: The proposed method seamlessly integrates with existing pruning frameworks like Wanda, SparseGPT, and ALPS, allowing straightforward adoption within the broader neural network pruning community.\n4. Comprehensive Experimental Validation: Experiments are thorough and extensive, covering both single-matrix evaluations and full-scale pruning scenarios on LLaMA models, clearly demonstrating computational advantages and acceptable accuracy trade-offs.\n\n## Weaknesses:\n1. Clarity on Practical Gain: While the method clearly demonstrates computational efficiency, the practical gain in terms of the speed-accuracy trade-off in training and inference is not fully explicit. Specifically, results explicitly comparing accuracy versus computational speed between transposable and non-transposable N:M masks (or between regular dense matmul) are limited or unclear.\n2. Technical Novelty Moderation: Although the connection to optimal transport is interesting and practically beneficial, the overall approach leverages well-established optimization techniques (e.g., entropy regularization, Dykstra's algorithm) and therefore offers moderate conceptual novelty.\n3. Limited Detailed Discussion on Larger M Values: The claim regarding the computational benefits and accuracy at larger M-values (e.g., 16:32) seems insufficiently justified. It's unclear how these larger M-values maintain similar computational benefits as smaller structured masks, considering the tendency towards unstructured patterns at larger M.\n\n## Overall Evaluation:\nThe paper presents an interesting approach by leveraging optimal transport theory for efficient mask generation in neural network pruning, particularly relevant given the increasing prominence of large language models. While computationally impressive, the practical advantage regarding accuracy-speed trade-offs is not fully articulated. The technical novelty is moderate, considering the method largely relies on known optimization techniques.\nThus, I lean towards a weak rejection given the current state, primarily because the critical practical gains (accuracy-speed trade-off improvements) are not thoroughly demonstrated. The paper could significantly benefit from narrowing its scope, providing more explicit comparative results, and further justifying claims regarding large M-value effectiveness.", "was_revised": true, "final_justification": "Thank you for the detailed explanation.\nThe rebuttal response solved my main concerns about the large M (I misunderstood this part, especially about wall-clock latency).\nAnd I now understand the significance of the proposed entropy regularization.\nWith the clarification, I understands the proposed methods also has practical speed gains.\nAfter the rebuttal all l my concerns have been resolved. \nNow I have raised my rating.", "rebuttal": "We would like to thank the reviewer for their thoughtful feedback. Below, we provide some answers/clarifications.\n\n**Clarity on Practical Gain: While the method clearly demonstrates computational efficiency, the practical gain in terms of the speed-accuracy trade-off in training and inference is not fully explicit. Specifically, results explicitly comparing accuracy versus computational speed between transposable and non-transposable N:M masks (or between regular dense matmul) are limited or unclear.**\n\nWe respectfully disagree with the reviewer's assessment, as we believe Section 5.2.1 already provides explicit evidence demonstrating the superior speed-accuracy trade-off achieved by transposable N:M sparsity with large M values.\nFigure 4 (upper) shows that when pruning LLaMA3.2-8B, the performance gap between transposable and standard N:M sparsity diminishes dramatically as M increases from 4 to 32, with transposable N:M performance growing rapidly. Figure 4 (lower) demonstrates that transposable N:M achieves significantly higher computational speedup than standard N:M during training. Moreover, the speedup of transposable N:M remains consistent across different M values. Together, these figures show that transposable N:M sparsity with large M values (M=32) achieves comparable accuracy to standard N:M while maintaining significant computational speedup during training. \n\n**Technical Novelty Moderation: Although the connection to optimal transport is interesting and practically beneficial, the overall approach leverages well-established optimization techniques (e.g., entropy regularization, Dykstra's algorithm) and therefore offers moderate conceptual novelty.**\n\nWe respectfully disagree with the reviewer's assessment. Our paper presents several technical novelties:\n+ In Section 3.2, we introduce a novel approach based on entropy regularization that solves masks with arbitrary transposable N:M sparsity. The key innovation is utilizing GPU tensor operations to solve millions of blocks simultaneously, making our approach highly parallelizable.\n+ In Section 3.3, we propose a novel rounding procedure that converts fractional solutions to high-quality binary masks through greedy selection and local search. Our tensor-based implementation processes millions of blocks simultaneously, achieving up to 10³× speedup over CPU implementation.\n+ In Section 4, we integrate TSENOR with existing layer-wise N:M pruning frameworks (Wanda, SparseGPT, ALPS) to generate transposable N:M sparse networks. For ALPS, we provide novel convergence guarantees for the resulting framework.\n\nWe believe these contributions represent algorithmic and theoretical advances beyond simply applying existing optimization techniques.\n\n**Limited Detailed Discussion on Larger M Values: The claim regarding the computational benefits and accuracy at larger M-values (e.g., 16:32) seems insufficiently justified. It's unclear how these larger M-values maintain similar computational benefits as smaller structured masks, considering the tendency towards unstructured patterns at larger M.**\n\nWe have provided comprehensive experimental evidence demonstrating the benefits of larger M-values — please refer to our detailed response to Weakness 1.\n\n**Clarification of Computational Benefits at Larger M-values: Your claim— \"Our experiments show that networks with larger M values (e.g., 16:32) provide the same computational benefits as smaller M values but with much less impact on model accuracy\"— is unclear. Which specific experiments support this claim?**\n\nThe experimental evidence supporting this claim is presented in Figure 4 and discussed in Section 5.2.1 — please refer to our detailed response to Weakness 1.\n\n\n**Given that larger M-values inherently become less structured, it is counterintuitive that computational benefits remain constant. Could you clarify how these masks remain efficiently acceleratable?**\n\nThe speedup is achieved using the NM-SpMM CUDA kernel [1], which employs memory access optimization and hierarchical blocking mechanisms for sparsity-aware acceleration. These optimizations enable near-theoretical peak performance across different N:M sparsity levels, ensuring that computational benefits remain nearly constant regardless of M value.\n\n[1] NM-SpMM: Accelerating Matrix Multiplication Using N:M Sparsity with GPGPU\n\n**Accuracy-Speed Trade-off Analysis: If I understand correctly, transposable N:M sparsity should accelerate both training and inference. However, the current manuscript lacks explicit results that clearly illustrate improved accuracy-speed trade-offs. Could you clarify if and where such comparative results exist in the paper? If not, can you provide a rationale or consider including this comparison?**\n\nIn Figure 4, we demonstrate that transposable N:M sparsity maintains comparable accuracy to standard N:M sparsity (upper figure) while achieving 30% to 4× speedup during training (lower figure) — please refer to our detailed response to Weakness 1."}, {"review_id": "coQFEWzo7b", "reviewer": "Reviewer_qhU9", "summary": "This paper proposes TSENOR, a novel and efficient algorithm for generating binary masks with transposable N:M sparsity, enabling acceleration in both forward and backward passes during neural network training. The authors formulate the mask generation problem as an entropy-regularized optimal transport problem and solve it using Dykstra’s algorithm. A GPU-optimized rounding step, composed of greedy selection and local search, ensures constraint satisfaction and mask quality. The method is integrated with several pruning frameworks (e.g., Wanda, SparseGPT, ALPS) and achieves substantial speedup (10–100×) and low reconstruction error (1–10%) on  LLaMA3.2–8B model.", "questions": "1. Why is Bi-NM used in Figure 5 as the primary comparison instead of 2-approx? In Figure 3, 2-approx shows better reconstruction error than Bi-NM, so it would be more convincing to include 2-approx as a baseline in Figure 5.\n\n2. Have you considered GPU-accelerated implementations of 2-approx for fairer runtime benchmarking?\nTSENOR is compared to 2-approx on CPU in Table 1. Leveraging NVIDIA’s cuOPT for general LP or other parallel kernels could offer a more apples-to-apples comparison with Network Flow.", "limitations": "While they do briefly mention limitations in two sentences at the end of section 6, it's not enough. I'd encourage the authors to add a dedicated section on limitations. A thorough discussion of what's missing or where the current work falls short is truly invaluable for paving the way for impactful future research.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "# Strengths\n\n1. Reformulating the sparse mask search as an optimal transport problem is an insightful approach, grounded in theory and convex optimization.\n\n2. Figure 3 shows that TSENOR achieves superior solution quality with significantly lower relative error compared to competing methods like 2-approx.\n\n3. Table 1 and related experiments show significant acceleration due to GPU parallelism, making the method viable for large models.\n\n4. Comprehensive empirical validation: Evaluation includes mask quality metrics, perplexity comparisons, and inference speedups on multiple sparsity levels.\n\n# Weaknesses\n1. Transposable N:M sparsity remains a relatively niche topic; thus, the broader significance and audience interest may be limited.\n\n2. Alternative baselines could be enhanced: While the current comparisons are reasonable, further exploration of acceleration for classic heuristics like 2-approx on GPU may reinforce the case.\n\n3. Incomplete code availability: The paper mentions GPU-efficient implementations, but only partial code appears to be provided. Without full implementation and integration examples, reproducibility and adoption may be hindered.", "was_revised": true, "final_justification": "After the rebuttle I decided to raise my score to 5", "rebuttal": "We would like to thank the reviewer for their thoughtful feedback. Below, we provide some answers/clarifications.\n\n**Transposable N:M sparsity remains a relatively niche topic; thus, the broader significance and audience interest may be limited.**\n\nWe appreciate this perspective. Transposable N:M sparsity addresses a critical challenge: accelerating both forward and backward passes during full fine-tuning without specialized hardware. As training costs become prohibitive, methods that enable efficient full fine-tuning on standard GPUs are essential. Our approach potentially enables researchers with limited resources to train and fine-tune large models more efficiently.\n\n**Alternative baselines could be enhanced: While the current comparisons are reasonable, further exploration of acceleration for classic heuristics like 2-approx on GPU may reinforce the case.** \n\nWe appreciate this valuable suggestion. Due to the sequential nature of 2-approx (selecting the best feasible element at each step), direct GPU implementation is challenging. To our knowledge, the only available GPU implementation [1] uses CUDA kernels, but after contacting the authors, we found their code is incompatible with modern GPUs on our platform.\nWe will consider implementing our own CUDA version of the 2-approx method as an enhanced baseline and compare it against TSENOR in both mask generation and fine-tuning settings in our revised manuscript.\n\n[1] Accelerating transformer pre-training with 2: 4 sparsity\n\n**Incomplete code availability: The paper mentions GPU-efficient implementations, but only partial code appears to be provided. Without full implementation and integration examples, reproducibility and adoption may be hindered.**\n\nThank you for this valuable suggestion! We have prepared our complete implementation for public release. Due to conference guidelines prohibiting links in rebuttals, we will make the code available upon paper acceptance.\n\n**Why is Bi-NM used in Figure 5 as the primary comparison instead of 2-approx? In Figure 3, 2-approx shows better reconstruction error than Bi-NM, so it would be more convincing to include 2-approx as a baseline in Figure 5.**\n\nBi-NM's advantage over 2-Approx and other methods only emerges during fine-tuning — it trains with non-transposable N:M masks and applies transposable masks only during gradient computation (backward pass) to achieve bidirectional acceleration. Therefore, we compare with Bi-NM in fine-tuning settings as it represents the strongest baseline.\nSince TSENOR generates transposable masks with either much higher quality or greater efficiency than 2-Approx and other competing methods (as shown in Figure 3 and Table 1), it predictably achieves superior fine-tuning performance. We will consider include fine-tuning comparisons with 2-Approx in our revised manuscript to provide more comprehensive evidence of TSENOR's advantages.\n\n**Have you considered GPU-accelerated implementations of 2-approx for fairer runtime benchmarking? TSENOR is compared to 2-approx on CPU in Table 1.**\n\nPlease refer to our reply to Weakness 2.\n\n**Leveraging NVIDIA’s cuOPT for general LP or other parallel kernels could offer a more apples-to-apples comparison with Network Flow.**\n\nWe appreciate this valuable suggestion. Currently, NVIDIA's cuOPT GitHub repository lacks documentation for its Python API, making direct comparison challenging. We have included comparisons in Table 1 with cuPDLP — a GPU-accelerated PDLP solver for linear programming, which offers similar insights (cuOPT also employs GPU-accelerated PDLP methods for solving LP problems). We will make our best effort to include a comparison with NVIDIA's cuOPT to serve as a stronger baseline for Network Flow methods in our revised manuscript.\n\n**While they do briefly mention limitations in two sentences at the end of section 6, it's not enough. I'd encourage the authors to add a dedicated section on limitations. A thorough discussion of what's missing or where the current work falls short is truly invaluable for paving the way for impactful future research.**\n\nThank you for this valuable suggestion! We will add a new section in our revised manuscript to thoroughly discuss the current constraints of our approach and directions for future improvements."}]

Author rebuttal:

Meta-review: This paper introduces TSENOR, a scalable and GPU-efficient algorithm for generating transposable N:M sparse masks, which accelerate both forward and backward passes in large-scale neural network training. The method formulates mask generation as an entropy-regularized optimal transport problem, solved with Dykstra’s algorithm and followed by a fast rounding procedure. Experiments on LLaMA and OPT models show up to 100× speedup over existing methods, improved reconstruction error, and performance competitive with or better than Bi-NM, especially at larger M values (e.g., 16:32).

Reviewers appreciate the clean formulation, strong efficiency gains, and thorough empirical validation, as well as the practical integration with existing one-shot pruning frameworks. Main concerns included the clarity of fine-tuning comparisons, the significance of larger M values, moderate conceptual novelty, and reproducibility due to initially missing full code release.

The rebuttal addressed these issues with additional fine-tuning results, clarifications on computational benefits at larger M, and a commitment to releasing full code and adding a limitations section. Multiple reviewers raised their scores after discussion, leading to a positive consensus. Overall, this is a solid and well-executed contribution that advances the state of the art in structured sparsity.
Decision: Accept (poster)