Two Sparse Matrices are Better than One: Sparsifying Neural Networks with Double Sparse Factorization
Authors: Vladimír Boža
Vladimír Macko
Venue: ICLR 2025 Poster (2025)
Keywords: sparse factorization
pruning
Primary area: other topics in machine learning (i.e., none of the above)
TL;DR: We factorize each matrix in neural network into two sparse matrices and achieve state-of-the-art sparsification results.

Abstract: Neural networks are often challenging to work with due to their large size and complexity. To address this, various methods aim to reduce model size by sparsifying or decomposing weight matrices, such as magnitude pruning and low-rank or block-diagonal factorization. In this work, we present Double Sparse Factorization (DSF), where we factorize each weight matrix into two sparse matrices. Although solving this problem exactly is computationally infeasible, we propose an efficient heuristic based on alternating minimization via ADMM that achieves state-of-the-art results, enabling unprecedented sparsification of neural networks. For instance, in a one-shot pruning setting, our method can reduce the size of the LLaMA2-13B model by 50% while maintaining better performance than the dense LLaMA2-7B model. We also compare favorably with Optimal Brain Compression, the state-of-the-art layer-wise pruning approach for convolutional neural networks. Furthermore, accuracy improvements of our method persist even after further model fine-tuning.
Code available at: https://github.com/usamec/double_sparse

Published as a conference paper at ICLR 2025
Two SPARSE MATRICES ARE BETTER THAN ONE: SPARSIFYING NEURAL NETWORKS WITH DOUBLE SPARSE FACTORIZATION
Vladimír Božal2 Vladimír Macko
Faculty of Mathematics, Physics and Informatics, Comenius University
Powerful Medical GrizzlyTech
{boza, vladimir podtimir.matt Seaddmi..maccoo@@eee..
uniba.sk
ABSTRACT
Neural networks are often challenging to work with due to their large size and complexity. To address this, various methods aim to reduce model size by sparsi- fying or decomposing weight matrices, such as magnitude pruning and low-rank or block-diagonal factorization. In this work, we present Double Sparse Factor- ization (DSF), where we factorize each weight matrix into two sparse matrices. Although solving this problem exactly is computationally infeasible, we propose efficient heuristic based on alternating minimization via ADMM that achieves state-of-the oof-the-ar art results, enabling unprecedented sparsification of neural networks. For instance, in one-shot pruning setting, our method reduce the size of the ILLMMA-13BB model by 50% while maintaining better performance than the dense LLaMA2-7B model. We also compare favorably with Optimal Brain Com- pression, the state-of-the-ars layer-wise pruning approach for convolutional neural networks. Furthermore, accuracy improvements of our method persist even after further model fine-tuning.
Code available at:
INTRODUCTION
Sparse neural networks have gained attention due to their potential reduce computational costs and memory usage, making them more efficient for deployment on resource-constraig devices (LeCun al. 1989 Han al., 2015 Hoefler et al., 2021). By redueing the number of non-zero parameters, sparse networks can achieve accuracy similar to dense networks while requiring fewer operations. Reducing network size also decreases the number of weights that must be loaded into the processing unit from memory, which is crucial since memory bandwidth often becomes bottleneck in neural network deployments, particularly during single-sample LLM inference (Xia al. 2023)
In this work, we propose an improvement over typical neural network sparsification. Instead of replacing each dense weight matrix with sparse matrix, we replace each dense matrix with a product of two sparse matrices. We devise heuristic algorithm for calculating sparse matrix factorization and achieve significant improvements over a wide range of models, including large language models and convolutional neural networks.
Summary of contributions. We propose a practical algorithm for factorizing a matrix into two sparse matrices called Double sparse factorization (DSF). We extend it for the layer- wiser-wieepp pruning scenario where one wants to preserve layer behavior for given set of calibration inputs. Our sparse factorization algorithm is heuristic based alternating minimization where each subproblem is solved using the ADMM algorithm for solving a sparse regression problem (Boža) 2024).
Our algorithm obtains superior results in the layer-wise pruning scenarios, where we fix the number of non-zero entries in each layer. We compare favorably to Optimal Brain Compression (Frantar & Alistarh 2022) for pruning convolutional image models. We also produce state-of- the-art layer- wise pruning results for large language models, where the larger pruned model has better perplexity than the dense smaller model (as far as we know, this is the first time for the uniform layer-wise pruning).

---

Published as a conference paper at ICLR 2025
Perplexity on Wikitext-2
LLaMA-7B DSF
8
LLaMA-13B DSF
LLaMA-7B ADMM
LLaMA-13B ADMM
4
8
10
12
Number of non-zero parameters (in billions)
Figure I: Comparison LLaMA2 models pruned either using our DSF algorithm or using previ- ously state-of- the-art ADMM pruning. We prune models using 0, 50, and 60% sparsities.
One could argue that our method requires storing one more pruning mask. We thus evaluate a scenario where one of the sparse factors mask (weights can be tuned, but nonzeros location is fixed) is randomly generated and fixed over the whole neural network. Our approach is better even in this scenario, which has almost the exact storage requirements regular pruning.
Finally, we also show that our factorized pruning brings benefits even when sparsified models are further fine-tuned after pruning and achieve competitive results for pruning convolutional networks on CIFAR and ImageNet datasets.
RELATED WORK
Neural network weight pruning and layer-wise one-shot pruning. Post-training network pruning compresses the already training network by removing redundant weights (LeCun et al.) [1989 Han
et al. 2015 Blalock et al.) 2020 Liu et al. 2018 Hoefler et al. 2021 Srinivas et al. 2022).
Some approaches focus on splitting the network into individual layer-wise problems, where one wants to preserve layer behavior over small set of calibration inputs. Optimal Brain Compression (OBC) (Frantar Alistarh, (022) removes one weight at a time and optimally updates the remain- ing weights in the layer. However, this approach is not feasible for large language models due to high computational cost. SparseGPT (Frantar Alistarh 2023) uses various approximations and practical algorithm at the expense of higher approximation error. Wanda (Sun et al. 2023) proposes to skip the weight update and prune weights based on the product of absolute magnitude and input norm. Finally, Boža (2024) obtains state-of-the-art layer-wise pruning results using an ADMM-based algorithm, which uses gradual pruning combined with Wanda mask selection and ADMM (Boyd al. 2011) weight update.
turns OBC into
Compression based on matrix factorization. Instead of turning weight matrices into sparse ma- trices, one can replace them with a product of multiple smaller matrices. typical example is low-rank factorization (Li & Shi 2018 Jaderberg et al.) (014) where one turns an n. X m matrix and m matrices. where
into a product of include butterfly matrices (Dao et al. 2019) and Monarch matrices (Dao et al. 2022), where indi- vidual factors have some specific structure. Monarch matrices are the product of block-diagonal, permutation, and another block-diagonal matrix. The projection of matrix into set of monarch matrices is done by splitting the original matrix into blocks and then running low-rank decompo- sition of each block. Another option is to decompose the matrix sum of low-rank and sparse matrix (Nikdan et al., 2024: Yu et al. 2017 Ke Kanade 2005 Wright et al. 2009). Distantly related to work sparse coding (Lee et al. (2066), which factorizes the matri product of sparse and dense matrix to represent each data point (row of the matrix) as a linear combination of only few basis vectors.
min m)) More complicated examples
2

---

Published as a conference paper at ICLR 2025
Separable convolutions. Convolutional layer be naturally factorized into depthwise (apply- ing filter per input channels) and pointwise convolution (mixing multiple channels). The idea was found initially in MobileNets (Howard 2017; Sandler et al. 2018). but they placed nonlinearity be- tween the depthwise and pointwise convolutions. However, some works successfully use separable convolutions without nonlinearity between them (Perešíni et al. 2021 Kriman al. 2020).
Sparse matrix factorization. Factorization of the matrix into (sometimes more than two) sparse factors has already been studied. It was shown that this problem is NP-hard even when the sparsity pattern for factors is given (Le et al., (02T). Le Magoarou & Gribonval (2016) provides a heuristic based on the proximal gradient step called palm4msa, which then used by Giffon al. (202T) for compression of neural networks, but with very limited practical success. In the appendix, we compare the quality of our factorization algorithm with palm4msa. There were also works using sparse matrix factorization for parameter efficient fine-tuning (Chen et al. 2024).
PRELIMINARIES
In this work, we work with the post-training neural network sparsification scenario. We given an already-trained network, and we will replace each weight matrix with a matrix that can be repre- sented more efficiently, such as a sparse (Hoefler et al., (2021) Monarch matrix (Dao al. 2022). Usually, the replacement is done by solving the projection problem, where we are looking for a ma- trix closest (typically using the Frobenius norm) the original one. For example, when the target matrix is sparse, solving the projection problem is just the magnitude pruning (Han et al.) 2015).
In many cases, the sparsified network is often fine-tuned further. This can be prohibitive in some applications, especially involving large language models. We often resort to one-shot pruning in such cases. We capture relevant statisties for each layer and prune them during one forward pass. This is usually done by solving the layer-wise pruning problem (Frantar & Alistarh| [2022] 2023 Boža, 2024), where given calibration input X, original matrix W, one looks for sparse matrix W such that the layer-wise error || XW, pl3 minimized.
3.1
LAYER- WISE PRUNING VIA ADMM
Boža 2024 solves the layer-wise pruning problem by application of the alternating direction method of multipliers (Boyd et all 2011) (ADMM). ADMM solves convex problems of the form:
find minimum of f(x + g(y), subject to Ax + By C, using iterations:
x ++1 arg min ((x (p/2)]|Ax + B² + u²
k+1 arg min ( +
BB c u 1
n n + k+1 + B2 k+1 12k+1_
Note that when the pruning mask fixed, the layer-wise pruning problem is convex problem (we have one linear regression for each output with different set of inputs).
This can be solved via ADMM as follows: Given X, W, and pruning mask M, we are looking for W, such that (1 M) @ W, 0 and layer-wise error is minimized. In ADMM formulation, f(W) represents the layer-wise error, and g(Z) would be an indicator function, which has a value of when Z has the correct mask and xo otherwise. Then initialize 2 M @ W and U = 0 and apply following ADMM iterations (p is penalty factor usually set to onc, represents sealed dual variables):
((++1) (X"x (X" ((Z(k) U(A))
z((+1) M @ (1++))) + ((())
(1)
((++1) = U* + W(--1) (k+11)
We will take final W, ((m) the output.
3

---

Published as a conference paper at ICLR 2025
then applies the following improvements: Preconditioning is applied first improve convergence. All input feature norms are normalized to one (and the matrix W is multiplied by original imput norms), which means that the diagonal of x x contains only ones.
Boza 2024)
A pruning mask found heuristically during the optimization process. During the first iterations, gradual magnitude pruning with cubic schedule (Zhu & Gupta 2018) is applied (in the original paper, cubic prune is applied during the first 15 iterations out of 20; also it was found that dropping smallest values from W U* is better than dropping smallest values from current valid solution )*).
4 DOUBLE SPARSE FACTORIZATION
In typical neural network pruning. we replace weight matrix W with matrix W, which has at most nonzeros, i.e. ||W'loo I 2. Here, we propose to replace weight matrix W with shape n x m with a product
two sparse matrices AB such that they have at most z nonzeros in total, i.c. || + || I 2. We call this a double sparse factorization. Usually, we assume that A is matrix with shape n x n, is matrix with shape n x m, and S m; not, we transpose the matrix W.
During neural network inference, we multiply some input shape n with matrix W. After our double sparse factorization which replaces W with product AB, we will first multiply X by A and then by B, i.c. doing B. Note, that the total number multiplications is bz, the same as in typical neural network pruning.
4.1 EXPRESSIVENESS AND EFFICIENCY OF DOUBLE SPARSE FACTORIZATION
Figure 2: Graphical illustration of double sparse factorization. A dense layer is turned into two sparse layers. With enough weights in sparse matrices, most connections will be covered by path through sparse matrices.
Many matrix factorizations mentioned previously in the literature can be (often trivially) rewritten double sparse representation with the same number of non-zeros. For example, low-rank factor- ization commonly done via SVD (Li & Shil 2018 Stewart 1993) is already in the double sparse product of biock-diagonal permutation, and block- diock-diagonal matrices, can represented in double sparse form by fusing a permutation matrix with one of the block-diagonal matrices. Also, DSF can efficiently represent matrix that consists of multiple disjoint low-rank submatrices.
form. Monarch factorization (Dao al.] 2002). which
The tricky case an ordinary sparse matrix Wp. can be represented in double sparse form product of identity and the original matrix: IW, However, this comes with the cost of additional non-zero entries for the identity matrix. Nevertheless, the experiments, we will show that double sparse representation represents the original dense matrix much better than ordinary sparse matrix with the same number of non-zeros.
4.2 HEURISTIC ALGORITHM FOR DOUBLE SPARSE FACTORIZATION
First, we look into the projection problem. Given matrix W, we want to replace with some compressed matrix W., where their difference ||W, W is minimized.
In our case, W. is a product of two sparse matrices A, B. Thus, we are given matrix W and are looking for matrices A, B such that:
4

---

Published as a conference paper at ICLR 2025
||AB W subject to || + BB S
minimize
This problem is NP-hard even when the sparsity pattern for matrices A and B is given (Le et al. 2021) thus we solve our problem heuristically.
First, decide how many nonzeros allocate for each matrix, ||Allo I Za. Bllo I 2b. These allocations were determined manually in our experiments. In general, we found that it is beneficial to give one of the matrices approximately 1/3 of the nonzeros and 2/3 to the other one. Then, we continue with an alternating minimization algorithm. We fix the value of A and find the best possible B, then fix the value of B and try to find the best possible value of A. We repeat this process multiple times.
condition changes to
One inner step of algorithm can formalized as: Given W, and B, find A such that:
minimize ||AB - W
subject ||A||o S Z
This problem is just an Lo constrained linear regression. We solve it using iterative ADMM solver Boža (2024) mentioned in preliminaries, which heuristically finds matrix mask and corresponding values. We also apply the following heuristic improvements.
Algorithm Heuristical sparse matrix factorization for solving projection problem. Given matrix W. number of outer iterations n, number of inner iterations m and number of nonzero elements Za, 2b we find A, B such that ||Al|o I 2a. BBllo S 2/ and AB is as close as possible to W.
Initialize ( (0)
U!!) 0- A, (0) - B
for k 1..n do
Po minn1.0, k/(n
- (e/nnn3))))
3))3
(kk), U.a +
solve arg min ||AB - W FF st. |BB||o S 26 via m iterations of ADMM
with starting point B 1, and starting Po
(k-
AK) U
solve arg min ||AB W| st. ||A||o S 2a via iterations of ADMM
with starting point A (k-1) and starting Po
end for
Warm starting the inner iterations. To improve the convergence of ADMM iteration, can warm-start it using the result from the previous step. To do that, we use not only the resulting sparse matrix but also all the dual variables U from the ADMM algorithm. This allows us decrease the number of inner iterations and speed up our algorithm.
Annealing, We found that our algorithm is often quickly stuck in some local optima. To prevent that, we propose a simple annealing scheme. The first step of ADMM for finding B is W = (AT A + WATT + (() )) Instead of using p in the first iteration, we use smaller Po (we use default p in the remaining steps of ADMM). This gives lower weight to the previous solution and allows us to escape from local minima at the first steps of the optimization. We gradually increase po from 0 to I throughout the optimization; we found that simple cubic schedule works best. We also found that using more outer iterations (n) and fewer inner iterations (m) leads to better results.
Initialization. To run our algorithm, we must assign an appropriate starting values to matrices A and B. We tested several choices (ablations provided in the Appendix initialization and singular value decomposition, but we settled on initializing as an identity matrix and B with magnitude pruning of the original input matrix.
(A.)), including random
some people call this dark magic
5

---

Published as a conference paper at ICLR 2025
4.3 APPLICATION OF SPARSE FACTORIZATION TO LAYER-WISE PRUNING
Next, we look into layer-wise pruning problem. In our case of the sparse factorization, we are given calibration input X, original weight matrix W and are looking for sparse A, B such that the reconstruction error ||XW - XABB|2
[/ is minimized.
We solve this problem by first rumning the weight projection algorithm from the previous section. However, for the pruning of LLMs, we found that it is better to project the weight matrix multiplied by input feature norms. This was previously done in Wanda pruning algorithm (Sun et al. 2023 We then scale one of the factors back. More formally we calculate matrix W", such that fj
||x:||2
Wij. then find A' and B such that error IIW" A A'B / is minimized and then compute O A.y. We do not do this rescaling for vision models.
Ag ||x,
We then proceed with the finalization step. We fix all sparsity masks and apply the ADMM algo- rithm for finding so that ||W XAB is minimized. This is a straightforward modification of the ADMM algorithm.
However, finding A is tricky and sometimes numerically unstable. In the inner iteration of ADMM, we need to find A such that (Z, U other variables from ADMM optimization): 7 + 212 is minimized. After taking gradients, we solve the equation: X ABB + PA X BT p(Z - U). This is special type of Sylvester equation Roth 1952 Jiang & Wei 2003). which can be solved using the eigendecomposition of X X and BB" We provide solution this problem in the Appendix [ We found that optimizing A only helpful for compressing vision models; we do not use it when compressing large language models.
|XW- - XAB|| 1B + p/2|
4.4 COMPUTATIONAL CONSIDERATIONS FOR DSF
The obvious drawback of DSF is having two sparse matrices compared to one. Here, we argue that doing computation with two sparse matrices needs resources comparable to doing computation with one sparse matrix with the same total number of nonzeros.
Storage requirements. Storing actual non-zero values has the same memory footprint for one sparse matrix and for DSF. The difference lies in storing nonzero positions (sparsity masks).
If we store sparsity masks as bit vectors, DSF would need store two masks rather than one. This leads to 2x increase in storage costs for square matrices but smaller increase for rectangular matrices (for example, in Llama-2-7B, we have matrices with size 4096x 1008, which would lead to 37% increase in storage cost for masks). Remember that we also store nonzero values (usually 16-bit floats), and they take the majority of the storage costs. Overall, when measured on Llama-2- 7B with 50% density, regular pruning would have a model size of 7.3GiB and DSF 7.7GiB. In the experiments, we show that DSF is still better even if we count the total model size.
The storage requirements will be identical if we store sparsity masks as nonzero positions (e.g.. using a compressed sparse row format). However, this format is preferable only for higher sparsities since storing one position index usually takes 16 (or more) bits. There are also various other storage formats (c.g., delta coding), but they are unexplored in the context of neural network sparsity.
Inference time. One could think that doing two sparse multiplications would be much slower than doing just one because of the sparse matrix multiplication overhead. However, when looking at actual benchmarks, we find that in lower sparsity ranges (50-95%), doing two sparse multiplications is usually 10-20% slower than doing one sparse multiplication with the same number of nonzeros. For example, Xia et al. (2023) reports in their benchmark that multiplication with 60% sparsity takes 0.36s, and multiplication with 80% sparsity takes 0.21s, which would translate into 0.42s for DSF. Similar slowdowns around 10-20% can be found for GPU kernels done by Gale et al. (2020) and for CPU inference, which tested in Appendix A.4
We would like to point out that in the case of single sample LLM inference, the bottleneck is loading weights from memory computational unit as reported in (Xia et al.) 2023), and the current token activations can usually reside in the fast cache. Also, one goal of the pruning is to fit the model into available GPU memory, and in some cases, inference time be sacrificed.

---

Published as a conference paper at ICLR 2025
Table I: Perplexity Wikitext-2 for layer-wise pruning of large language models. Density refers to the total % of nonzero weights compared to the dense model.
Density
Method
1-7B
2-7B
2-13B
2-70B
100%
Dense
5.68
5.12
4.57
3.12
Wanda
7.26
6.42
5.56
3,98
SparseGPT
7.22
6.51
5.63
3,98
ADMM
7.06
6.33
5.52
3.95
50%
DSF
6.12
5.58
4.87
3.44
DSF no fin.
6.17
5.61
4.89
3.45
DSF one mask fix
6.57
6.05
5.31
3.67
Wanda
10.66
9.71
7.75
4.98
SparseGPT
10.51
9.58
7.80
4.98
ADMM
9.22
8.70
7.09
4.81
40%
DSF
6.66
6.12
5.22
3.79
DSF no fin.
6.76
6.29
5.32
3.81
DSF one mask fix
7.82
7.47
6.21
4.27
Wanda
80.26
74.41
44.57
10.35
SparseGPT
26.73
26.64
20.53
9.33
ADMM
18.66
17.51
13.82
7,80
30%
DSF
8.33
8.01
6.43
4.56
DSF no fin.
9.13
10.82
7.5
4.59
DSF one mask fix
15.07
16.49
10.87
5.99
Table 2: Zero shot accuracies on zero-shot tasks when pruning Llama2-7B and Llama2-13B with 50% target density.
Model
Method
BoolQ
RTE
HellaSwag
WinoGrande
ARC-e
ARC-c
OBQA
Mean
Dense
77.71
62.82
57.19
69.22
76.35
43,43
31.40
59.73
Llama2-7B
ADMM
75.69
55.60
53.16
68.75
72.69
39.59
31.00
56.64
DSF
75.72
57.04
55.22
67.32
75.51
42.83
30.80
57.78
Dense
80.55
65.34
60.05
72.14
79.42
48.46
35.20
63.02
Llama2-133 13B
ADMM
81.35
64.98
56.70
72.53
76.52
43.00
33.20
61.18
DSF
80.34
64.26
58.57
72.61
78.28
47.10
36.60
62.54
Fine-tuning considerations. Another concern that during possible fine-tuning of the sparsified model, we need to store additional intermediate activations (in the middle of the double sparse factorization). This is true, but we found that with gradient checkpointing turned on and storing weights in compressed format (not as dense matrices), we can fine-tune on almost similarly sized sequences with DSF as when using regular pruning. provide more details the Appendix A.5
EXPERIMENTS
We evaluate our proposed Double Sparse Factorization multiple settings. First, we test on layer- wise pruning of large language models. We compare algorithms ADMM pruning (Boža) 2024]. which produces high-quality solutions in a reasonable time, even for large-scale models. Then we also layer-wise pruning of vision models and compare with Optimal Brain Compression (Frantar & Alistarh 2022), state of the art layer-wise pruning algorithm. Finally, we also test whether image models compressed with DSF can be successfully fine-tuned.
We also include ablation studies of DSF in the Appendix A.3
5.1 LAYER-WEE PRUNING OF LARGE LANGUAGE MODELS
Setup. We follow same setup as in Wanda (Sun et al., 2023) and ADMM pruning (Boža 2024). We 128 calibration samples from the C4 training dataset (Raffel al. 2020) and prune layers

---

Published as a conference paper at ICLR 2025
9
40%
Perplexity on Wikitext-2
DSF
ADMM
45%
7 335%
50%
40%
45%
5.%
50%
60%
55%
6.0
6.5
7.0
7.5
8.0
8.5
Model storage size [GiB]
Figure 3: Comparison of total model size vs Wikitext2 perplexity for various target densities of Llama2-7B.
sequentially in order. We prune LLaMA (Touvron et al.) 2023a and LLaMA-2 (Touvron al., 20236) models. Similarly to previous works, we measure perplexity on held-out Wikitext (Merity al., 2 When factorizing square matrices (mainly in self-attention), we the sparsity of one sparse factor to 16%. When factorizing rectangular matrices, the smaller factor will have 25% sparsity. The number of nonzeros the other factor is just the target number of nonzeros minus the number of nonzeros in the first factor.
Compared methods. We compare our Double Sparse Factorization in three settings. The first one is the default one, solving the layer-wise pruning problem. Then, we disable the finalization step; thus, we only approximate the original dense matrix scaled by the input feature norms and solve the matrix projection problem. Finally, we fix one of the sparse masks to random mask shared across all layers (but we run the finalization step). We compare our method with three layer-wise pruning algorithms: Wanda (Sun et al., 2023), which prunes weights with the smallest product of value and activation norm, ADMM pruming (Boža 2024), which also updates weights during the pruning using alternating direction method of multipliers, and SparseGPT (Frantar & Alistarh 2023).
Results. Results are summarized in Tab. aand Fig. T Our Double Sparse Factorization is superior previous layer-wise pruning methods. To knowledge, this is the first time when uniformly layer-wise pruned network has better perplexity than its dense counterpart (compare 50% pruned LLaMA2-13B with perplexity 4.87 dense LLaMA2-7B with perplexity 5.12). Even when fix one mask (and thus make the total size of the network the same as in regular pruning), our factorization produces favorable results. We also notice that in the lower sparsities, the finalization step is not that important but becomes noticeably important at higher sparsities.
Storage requirements for LLM its quality. We also compare total storage size (nonzero values storage as 16-bit floats + binary mask) vs Wikitext2 perplexity. We measure various target densities for Llama2-7B. Results are shown Fig 3 We can see that while DSF needs 0.4 GiB more storage for the same target density, it produces much better results, and this trend is more pronounced at lower densities.
Results on zero-shot tasks. We measure performance seven zero-shot tasks (we use the same selection as authors of ADMM pruning): BoolQ (Clark al. 2019). RTE (Wang et al. 2018). HellaSWAG (Zellers al. 2019), WinoGrande (Sakaguchi et al. 2021). ARC casy and challenge CCark et al. 2018), and OpenbookQA [Mihaylov et al. 2018). Results are summarized in Tab. On average, obtain better performance than previous pruning methods.
Pruning speed. We can prune the 7B models in apx. 30 minutes on one Nvidia 4090 GPU (this includes both forward pass and sparse factorization times). Note that reported total running times for ADMM pruning and SparseGPT are around 10-15 minutes (Boža 2024). We also study the effect of number of iterations pruning speed and solutions quality in the Appendix A.6
8

---

Published as a conference paper at ICLR 2025
Table 3:
Comparision of Double Sparse pruning Optimal Brain Compression Resnet50
using Imagenet dataset.
Number of nonzeros
FLOP reduction
Method
Test accuracy [%)
25.5M
Dense
76.13
OBC
75.65
16.8M
2x
DSF
75.78
OBC
75.01
12.3M
3x
DSF
75.56
OBC
74.05
10.2M
4x
DSF
74.95
Table 4: Test accuracy on CIFAR-10 10 using Resnet-20 with varying width. Density refers to the total % of nonzero weights compared to the dense model. FT refers to fine-tuiing.
Density 100%
Method
Resnet-20-16
Resnet-20-32
Dense
92.2 = 0.2
94.0 + 0.1
Magnitude w/o FT
70.6 = 0.5
86.2 + 0.3
Double sparse w/o FT
80.0 0.9
91.6 0.1
20%
Magnitude w/ FT
91.2 0.2
0.2
93.5
Double sparse w/ FT
0.1
93.6 0.1
Magnitude w/o FT Double sparse w/o FT
29.0 = 2.9
5..1
48.9 2.9
84.1+
10%
Magnitude w/ FT
89.3
92.
Double sparse FT
89.8 0.2
Further fine-tuning. We also tested the possibility of further fine-tuning of pruned L.LMs. DSF retains its advantage even after fine-tuning. Setup and results are summarized in Appendix A.7 A.7
5.2 COMPARISON WITH OPTIMAL BRAIN COMPRESSION
post-training layer-wise pruning algo- rithm, which prunes each network layer by removing connection at time and optimally updat- ing the remaining weights. Compared to the ADMM update algorithm mentioned in the previous section, it is much more accurate, but at the expense of much longer running time, unsuitable for large language models. However, OBC is still usable for moderately sized vision neural networks like ResNet50 (He al. 2016).
Optimal Brain Compression (Frantar & Alistarf 2022
In this experiment, we evaluate the effectiveness of our Double Sparse Factorization of ResNet50 on Imagenet (Russakovsky et al. 2015) dataset. We first run the OBC pipeline determine fayer-wiss pruning ratios. Using the same calibration dataset as OBC, we then factorize every convolutional layer into two sparse matrices with the same number of nonzero weights as the OBC solution. We treat convolutions as linear layers, where input is processed via the im2col procedure. The sparsity of the smaller factor set to maa(0.16 s/2) where is sparsity from OBC. The bigger factor will get the remaining nonzeros (so the total nonzeros of sparse factors match the number of nonzeros used by OBC). Results are summarized in Tab. 3 We see that our solution is superior to the solution found by OBC for every sparsity setting, and the gap grows wider with larger sparsities.
5.3 FINE-TUNING OF IMAGE MODELS PRUNED WITH DOUBLE SPARSE FACTORIZATION
Finally, we test whether the Double Sparse Factorization accuracy advantage remains after fine- tuning whole model. In this experiment, we only focus the original matrix projection and do not perform any input-dependent finalization. We test the pruning of Resnet-20 (He et al.) 2016) with varying starting widths (16 and 32) on the CIFAR-10 (Krizhevsky et al. 2009) dataset. We also test pruning Resnet-50 on Imagenet dataset (Russakovsky et al.) 2015). all experiments, we use the same sparsity in all layers. For CIFAR-10 10 experiments, we first train the dense network using the

---

Published as a conference paper at ICLR 2025
Table 5:
Test accuracy on Imagenet using Resnet-50. Density refers the total % of nonzero weights compared to the dense model. FT refers to fine-tuning.
Density 100%
Method
Test accuracy [%)
Dense
76.
Magnitude w/o FT
54.43
Double sparse w/o FT
71.85
20%
Magnitude w/ FT
75.43
Cyclical pruning Srinivas et al. 2022
75.3
Double sparse w/
75.78
Magnitude w/o FT
9.87
Double sparse w/o FT
55.76
10%
Magnitude w/ FT
73.32
Cyclical pruning Srinivas et al. (0022)
73.3
Double sparse w/ FT
74.50
procedure from Liu et al. (2022). We train for 160 epochs using SGD with a starting learning rate of 0.1 and 0.9 momentum. We decay the learning rate by 10 on epochs 80 and 120. We then prune each layer (except the first and last one) 10 20% of nonzeros using either magnitude pruning or our double sparse factorization method (on the weight projection problem). Then, we fine-tune the model for epochs, starting with learning rate of 0. and linearly decay the learning rate to zero (this was inspired by (Zimmer et al. 202T)). We run each setting 5 times using different seed. Results are shown in 4
For the Imagenet experiment, we start with the pre-trained Resnet-50 from Torchvision (maintainers contributors 2016). We then uniformly sparsify every layer except the first and last one and fine- tune for 20 epochs using SGD, with a linear learning rate decay from 0.01 of 0.9. We also compare with results reported by Sriiivas et al. (2022), which prunes and fine-tunes the neural network in multiple cycles with resets (Cyclical pruning). Results shown in Tab 5
and momentum
In all cases, starting test accuracy is higher for double sparse pruning and stays better when fine- tuned. This is especially evident at higher sparsities.
6 CONCLUSIONS AND FUTURE WORK
In this work, introduced Double Sparse Factorization (DSF), approach to decompose weight matrices into two sparse matrices, enabling more efficient neural networks. By applying DSF, we significantly improved layer-wise pruning for both large language models (LLMs) and convolutional neural networks (CNNs). The method effectively reduced the number of parameters without sacri- ficing model accuracy, achieving state-of-the Furthermore, our approach kept its performance gains even after further fine-tuning. Our work is also one of the first to show that a sparse neural network can achieve more gains by employing more complicated technique than just removing weights. One drawback of our solution is that in- dividual layer-wise wise sparsities need to be determined manually beforehand (compared to magnitude pruning. which unclear how to integrate DSF with gradual pruning with fine-tuning the whole network between pruning steps. We leave these enhancements for future work.
results compared to traditional pruning techniques.
work globally and determine sparsity in each layer automatically). Also, it is
ACKNOWLEDGMENTS
This research was supported by grants 1/0140/25, and 1/0538/22 from Slovak research grant agency VEGA. Part of the research results was obtained using the computational resources procured in the national project National competence centre for high performance computing (project code: 311070AKF2) funded by European Regional Development Fund, EU Structural Funds Informati- zation of society, Operational Program Integrated Infrastructure. We would also like to thank Elvir http:s////tttet ///ittttbubu com/ elvirern/
Cmčevićć for his GPU kemel implementation for DSF (bttps:/
double spa se__eenee)).
10

---

Published as a conference paper at ICLR 2025
REFERENCES
Davis Blalock, Jose Javier Gonzalez Ortiz, Jonathan Frankle, and John Guttag. What is the state of neural network pruning? Proceedings of machine learning and systems, 2: 2.129-146, 2020.
Stephen Boyd, Neal Parikh, Eric Chu, Borja Peleato, Jonathan Eckstein, et al. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Foundations and Trends@ in Machine learning, 3(1):1-122, 2011.
Vladimír Boža. Fast and effective weight update for pruned large language models. Transactions on Machine Learning Research, 2024. ISSN 2835-8856. URL https::/cpenreviee/ net/
Eorum?id= Eorum?id=Ihcpxa9.i1
Xuxi Chen, Tianlong Chen, Yu Cheng, Weizhu Chen, Ahmed Hassan Awadallah, and Zhangyang Wang. One is not enough: Parameter-efficient tie-ttningg with multiplicative sparse factorization. IEEE Journal of Selected Topics in Signal Processing, 2024.
Christopher Clark, Kenton Lee, Ming-Wei Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions. arXiv preprint 1rXiv: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: 180.:v:1000.550 00000000557, 2018.
Tri Dao, Albert Gu, Matthew Eichhorn, Atri Rudra, and Christopher Ré. Learning fast algorithms for linear transforms using butterfly factorizations. International conference on machine learning. pp. 1517-1527. PMLR, 2019.
Tri Dao, Beidi Chen, Nimit Sohoni, Arjun Desai, Michael Poli, Jessica Grogan, Alexander Liu, Aniruddh Rao, Atri Rudra, and Christopher Ré. Monarch: Expressive structured matrices for efficient and accurate training. In International Conference on Machine Learning, pp. 4690- 4721. PMLR, 2022.
Elias Frantar and Dan Alistarh. Optimal brain compression: A framework for accurate post-training quantization and pruning. Advances in Neural Information Processing Systems, 35:4475- 4488, 2022.
Elias Frantar and Dan Alistarh. Sparsegpt: Massive language models be accurately pruned in one-shot. In International Conference on Machine Learning, pp. 10323-10337. PMLR, 2023.
Trevor Gale, Matei Zaharia, Cliff Young, and Erich Elsen. Sparse gpu kernels for deep learning. In SC20: International Conference for High Performance Computing, Networking, Storage and Analysis, pp. 1-14. IEEE, 2020.
Luc Giffon, Stéphane Ayache, Hachem Kadri, Thierry Artières, and Ronan Sicre. Psm-nets: Com- pressing neural networks with product of sparse matrices. 2021 International Joint Conference on Neural Networks (IJCNN), pp. 1-8. IEEE, 2021.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pallern recognition, pp- 770-778, 2016.
Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. Journal of Machine Learning Research, 22(241):1-124 2021.
Andrew G Howard. Mobilenets: Efficient convolutional neural networks for mobile vision applica- tions. arXiv preprint / 048611 2017.
11

---

Published as a conference paper at ICLR 2025
Max Jaderberg, Andrea Vedaldi, and Andrew Zisserman. Speeding up convolutional neural networks with low rank expansions. arXiv preprint arXivv1405.3866, 2014.
Tongsong Jiang and Musheng Wei. On solutions of the matrix equations x- axb= c and x- axb= c.
Linear Algebra and its Applications, 367:225-233 2003.
Qifa Ke and Takeo Kanade. Robust 1/sub 1/norm factorization in the presence of outliers and miss- ing data by alternative convex programming. In 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 05), volume 1, pp. 739-746. IEEE, 2005,
Samuel Kriman, Stanislav Beliaev, Boris Ginsburg, Jocelyn Huang, Oleksii Kuchaiev, Vitaly Lavrukhin, Ryan Leary, Jason Li, and Yang Zhang. Quartznet: Deep automatic speech recog- nition with ld time-channel separable convolutions. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6124-6128. IEEE, 2020.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Quoc-Tung Le, Elisa Riccietti, and Rémi Gribonval. Spurious valleys, spurious minima and np- hardness of sparse matrix factorization with fixed support. arXiv preprint 12X.v:21 2021.
Luc Le Magoarou and Rémi Gribonval. Flexible multilayer sparse approximations of matrices and applications. IEEE Journal of Selected Topics in Signal Processing, 10(4):688-700, 2016.
Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Honglak Lee, Alexis Battle, Rajat Raina, and Andrew Ng. Efficient sparse coding algorithms. Advances in neural information processing systems, 19, 2006.
Chong Li and CJ Shi. Constrained optimization based low-rank approximation of deep neural net- works. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 732-747, 2018.
Shiwei Liu, Tianlong Chen, Xiaohan Chen, Li Shen, Decebal Constantin Mocanu, Zhangyang Wang, and Mykola Pechenizkiy. The unreasonable effectiveness of random pruning: Return of the most naive baseline for sparse training. arXiv preprint a:Xiv:2202.02643, 2022.
Zhuang Liu, Mingjie Sun, Tinghui Zhou, Gao Huang, and Trevor Darrell. Rethinking the value of network pruning. arXiv preprint arXiv:1810.05270 2018.
Vision maintainers and contributors. Torchvision: Pytorch computer vision library. https: 7/github. www. wttp://ottcccccciiiio..ooo 2016.
Vladimir Malinovskii, Denis Mazur, Ivan Ilin, Denis Kuznedelev, Konstantin Burlachenko, Kai Yi, Dan Alistarh, and Peter Richtarik. Pv-tuning: Beyond straight-through estimation for extreme Ilm compression. arXiv preprint arXiv:2405..0 14852, 2024.
Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models. arXiv preprint 17Xiv:1609.07843, 2016.
Todor Mihaylov, Peter Clark, Tushar Khot, and Ashish Sabharwal. Can a suit of armor conduct electricity? a new dataset for open book question answering, arXiv preprint arXiv:1809.02777 2018.
Saurav Muralidharan, Sharath Turuvekere Sreenivas, Raviraj Bhuminand Joshi, Marcin Cho- chowski, Mostofa Patwary, Mohammad Shoeybi, Bryan Catanzaro, Jan Kautz, and Pavlo Molchanov. Compact language models via pruming and knowledge distillation. In The Thirty- eighth Annual Conference on Neural Information Processing Systems, 2024.
NeuralMagic. Deepsparse inference engine.
https:/ htwp:/hwww..cmmmeeaaaaaaaaaaaa..
deepsparse] 2021.
12

---

Published as a conference paper at ICLR 2025
Mahdi Nikdan, Soroush Tabesh, and Dan Alistarh. Rosa: Accurate parameter--fffcient tine-tuning via robust adaptation. arXiv preprint arXiv:2401.04679, 2024.
Peter Perešíni, Vladimír Boža, Broña Brejová, and Tomáš Vinaf. Nanopore base calling on the edge. Bioinformatics, 37(24):4661-466) 2021.
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. The Journal of Machine Learning Research, 21(1):5485-555) 2020.
William E. Roth. The equations ax ax=yb= с and ax-xb= c in matrices. Proceedings of the American Mathematical Society, 3(3):392-396, 1952.
Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 1 115:21 1-252, 2015.
Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adver- sarial winograd schema challenge at scale. Communications of the ACM, 64(9):99-106, 2021.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Chighh Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4510-4520, 2018
Suraj Srinivas, Andrey Kuzmin, Markus Nagel, Mart van Baalen, Andrii Skliar, and Tijmen Blankevoort. Cyclical pruning for sparse neural networks. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 2762-2771, 2022.
Gilbert W Stewart. On the early history of the singular value decomposition. SIAM review, 35(4): 551-566, 1993.
Mingjie Sun, Zhuang Liu, Anna Bair, and Zico Kolter. A simple and effective pruning approach for large language models. arXiv preprint arXiv:2306. /695, 2023.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13977 202,,
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Niko- lay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open founda- tion and fine-tuned chat models. arXiv preprint arXiv:2307. 099809988 2023b.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv:1804.0744000 2018
Maurice Weber, Daniel Fu, Quentin Anthony, Yonatan Oren, Shane Adams, Anton Alexandrov, Xiaozhong Lyu, Huu Nguyen, Xiaozhe Yao, Virginia Adams, et al. Redpajama: an open dataset for training large language models. arXiv preprint arXiv:2411.12377 2024.
John Wright, Arvind Ganesh, Shankar Rao, Yigang Peng, and Yi Ma. Robust principal component analysis: Exact recovery of corrupted low-rank matrices via convex optimization. Advances in neural information processing systems, 22, 2009.
Haojun Xia, Zhen Zheng, Yuchao Li, Donglin Zhuang, Zhongzhu Zhou, Xiafei Qiu, Yong Li, Wei Lin, and Shuaiwen Leon Song. Flash-llm: Enabling cost-effective and highly-efficient large gen- erative model inference with unstructured sparsity. arXiv preprint arXiv:2309. 10285, 2023.
Xiyu Yu, Tongliang Liu, Xinchao Wang, and Dacheng Tao. On compressing deep models by low rank and sparse decomposition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 7370-7379, 2017.
Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can a ma- chine really finish your sentence? arXiv preprint arXiv: /900.07850000 2019.
13

---

Published as a conference paper at ICLR 2025
Michael Zhu and Suyog Gupta. To prune, not to prune: Exploring the efficacy of pruning for model compression. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Workshop Track Proceedings. OpenReview.net, 2018. htt.tttts://
ew net/ forum? 1= IDKPM
Max Zimmer, Christoph Spiegel, and Sebastian Pokutta. How learned to stop worrying and love retraining. arXiv preprint arXiv:2111.00844 2021.
A APPENDIX
A.1 SOLVING FOR IN THE LAYER- WISE RECONSTRUCTION PROBLEM
Recall that we want to find sparse A such that XW - XABIB is minimized (where X is calibration input, W is the original weight matrix, and B is the other sparse factor).
In the inner iteration of the ADMM, we need to find A such that (Z, U are other variables from ADMM optimization): ||XW - X ABB + p/21|A
Ull is minimized.
After taking gradients, we solve the equation:
X XBB"" + مd = x XWB + pZZ
We solve this equation using eigendecomposition and one simple trick. We use following cigendecomposition::: X QDQ", BB" = RER (where D, E' are diagonal matrices and Q, R are orthonormal).
We then multiply the equation by Q" from left and R from right and get: DQ ARE + pQ AR = Q" (x" + p U))R
We will now use that D, E are diagonal and create outer product of their diagonals: F= Tr(D) Tr.E). Now, we can use Hadamard product to get:
F Q" AR+ pº
TTATAAT AR = Q (x" XWB + p(z - U
And with slight abuse of notation (where F+ p means adding p to every element of F) we get: AR= XWB plz U)) (F+ +)
And thus:
A =
+ pZ - U))R (Tr(D) @ Tr(E) + +))
A.2 COMPARISON WITH OTHER MATRIX APPROXIMATION METHODS
We evaluate multiple methods for the weight projection problem. We use weight matrices from Llama-7B and Resnet-50. We truncate them to square matrices with sizes 64, 256, 1024, or 4096 (to accommodate Monarch factorization without problems). We evaluate our Double Sparse Fac- torization, palm4msa from Faust library (Le Magoarou & Gribonval 2016), which also factories matrix into two sparse matrices, magnitude pruning, which keeps values with the largest magnitude, singular value decomposition, which factorizes matrix into two low-rank matrices, and Monarch decomposition (Dao al., (022), which factorizes matrix into block-diagonal, permutation and block-diagonal matrix. In all cases, aim for 4x compression, i.e., each method can produce matrices that contain at most 25% non-zeros in total compared to the original matrix.
We see that our DSF consistently outperforms other methods. Interestingly, 4alm4mse is not better for small matrix sizes than magnitude pruning. Also, Monarch decomposition seems to be worse than ordinary SVD.
Results are summarized in Fig. 4
A.3 ABLATION OF DSF SETTINGS
We investigate some variations of DSF settings in Fig. 5 As in the experiments section, we target to have 25% of nonzeros compared to the original matrices. Running shorter iterations, especially our cubic first iteration weight schedule, benefits the final result. We also provide ablations for varying size of one factor (Fig. (), and also for various initializations (Fig
14

---

Published as a conference paper at ICLR 2025
Reconstruction error divided by magnitude pruning error
6
palm4msa
5
DSF
SVD
4
Monarch
3
2
1
102
10a
Figure 4: Reconstruction eгтоr of various compression methods on various matrix sizes for weight projection problem. We compress cach matrix to 25% of the original size. We normalize error by error of magnitude pruning. The mean is denoted by a large dot and individual results with smaller dots.
0.8
Default DSF
DSF 20x10 DSF w/o annealing
0.7
Reconstruction error divided by magnitude pruning error
0.6
0.4
0.3
10a
10a
Matrix size
Figure 5: Reconstruction error of various settings of DSF. Default DSF used 40 outer and 5 inner iterations. DSF 20x 10 refers to DSF with 20 outer and 10 inner iterations. DSF w/o annealing refers to DSF where we set first Po = 1.
15

---

Published as a conference paper at ICLR 2025
0.55
L.self attn.t__ppp o_prj
11.self attn. o proj
21.self attn.o__pp _rpoj
Reconstruction error divided by
0.50
31.self_atte aai_attttt_ppp
0.45
magnitude pruning
0.40
0.35
0.30
0.25
0.10
0.15
0.20
0.25
0.30
Density of the first factor
Reconstruction eтrоr for various densities of the first factor. We prune output projection from the attention layer in Llama-1 (matrix size 4096x4096) with target total density of 40%. We see that the optimal density of the first factor is slightly less than half of the target total density.
Figure 6:
Idntity init
Random init
Random orthogonal init init
Reconstructin error divided by magnitude pruning error
0.6
0.5
0.4
0.3
102
10a
Matrix size
Figure 7: Reconstruction error for various initialization schemes of the first factor in DSF. We see that choice of using identity init outperforms other common choices all except the smallest matrices.
16

---

Published as a conference paper at ICLR 2025
Table 6: Comparision of single CPU runtime for simple sparsity and DSF. Each time, compare the runtime of 48 layers with simple sparsity or DSF with an equal number of nonzeros (i.e., running 96 layers with half the density). We run the experiment on a single core using the DeepSparse engine.
Simple sparsity time [ms]
DSF time [ms]
Layer width
Batch size
Dense time [ms]
Density
0.5
30.5
36.3
64
49.5
0.25
18.9
21.3
0.125
10.11
11.43
1024
0.5
108.1
129.2
256
191.5
0.25
70.0
84.0
0.125
43.2
47.2
0.5
470
533
64
872
0.25
282
310
0.125
166
184
4096
0.5
1734
1965
256
3120
0.25
1050
1132
0.125
614
650
Table Comparision of multi-core CPU runtime for simple sparsity and DSF. Each time, we com- pare the runtime of 48 layers with simple sparsity or DSF with an equal number of nonzeros (i.e., running 96 layers with half the density). We run the experiment on cores using the DeepSparse engine. We throttled the frequency of the CPU to 3200 MHz to get consistent results unaffected by thermal throttling.
Simple sparsity
DSF
Layer width
Batch size
Dense time [ms]
Density
time [ms]
time [ms]
0.5
5.43
6.74
11.3
0.25
3.34
4.30
0.125
2.10
2.70
1024
0.5
19.30
23.66
256
36.25
0.25
11.87
15.66
0.125
7.75
9.29
0.5
101
122
64
162
0.25
62.3
74.5
0.125
37.7
44.93
4096
0.5
297
355
256
551
0.25
177
221
0.125
111
136
A.4 SPARSE MATRIX EFFICIENCY ON CPU
We use the following benchmark setup: We create chain of 48 or 96 matrices of size 1024x 1024 or 4096x4096 (the goal here that all matrices do not into the cache and must be reloaded during inference).
We then benchmark dense and sparse matrix multiplication over varying batch sizes and sparsity. We run Intel(R) Core(TM) 17-11800H and use DeepSparse inference engine (NeuralMagic) 2021 We try to simulate DSF vs single sparsity comparison (e.g. compare 48 layers with 50% density 96 layers with 25% density). Results summarized in Tab. and 7 We see that DSF has mostly a runtime 10-20% longer than ordinary sparse matrix multplication but still better than dense multiplication.
17

---

Published as a conference paper at ICLR 2025
Table 8: Maximum sequence length for various fine-tuning setups for Llama2-7B using A 100 with 40GB of memory and batch size 16. We always have gradient checkpointing turned on.
Setup
Maximum sequence length
Dense (base Llama2-7B)
1900
50% sparsity
2600
DSF with 50% total density
2400
6.6
DSF
ADMM pruning
6.4
Wikitext2 perplexity
6.2
6.0
5.8
10
60
80
10
20
30
40
50
60
Pruning time [min]
Figure 8: Comparison of total pruning time for DSF vs Wikitext2 perplexity for various number of pruning iterations. We also provide ADMM pruning for reference.
A.5 EFFECTS DSF FINETUNING
DSF makes the network deeper, and during fine-tuning, one needs to store more intermediate acti- vations. Moreover, if DSF results are stored as dense matrices, network size also increases.
We propose a simple storage solution for sparse matrices in Pytorch. We store nonzero values as parameters and packed masks as auxiliary parameter. During the forward pass, we unpack everything into dense matrix and then process input. This incurs small time overhead (which gets smaller the bigger batch becomes). A custom kernel would obviously be better solution, but writing custom GPU kernels is not the focus of this paper. This solution also only works if gradient checkpointing is enabled because otherwise, all of the unpacked dense matrices would be stored during the forward pass at once.
Here, search for the maximum sequence length batch size 16 on A100 GPU with 40GB memory. We use SGD optimizer without momentum. We turn on gradient checkpointing and test dense (vanilla model), sparse, and DSF representations. As reported in Tab. g when using DSF, the maximum fine-tunable sequence length drops, but is still higher than when using dense representation.
fine-tune. We finetune Llama2-7B using
A.6 COMPARISON OF FACTORIZATION TIME VS MODEL QUALITY
Varying the number of DSF iterations can lead to smaller or larger pruning times. Here, we study the effect of the number of pruning iterations (and thus pruning time) on solution quality. We use
18

---

Published as a conference paper at ICLR 2025
Table 9: Results after further LLM fine-tuning.
w/o finetuning Perplexity
w/ finetuning
Starting point
Zeroshot
Perplexity
Zeroshot
Llama2-7B Dense
5.12
59.71
Llama2-7B ADMM 50%
6.33
56.64
5.61 5.35
58.00
Llama2-7B DSF 45%
5.78
57.03
59.00
Llama2-7B with 50% target density and vary the number of factorization iterations from 1 to 80 (40
being the default). Results are summarized in Fig.
A.7 FURTHER LLM FINETUNING
We also tested limited full model fine-tuning of pruned LLMs. We finetune for two days on A100 GPUs. We use setup similar to (Malinovskii et al. (024) and use knowledge distillation loss (results from Muralidharan et al. (2024) also suggest that distillation loss just enough) and IB sample of the Redpajama dataset (Weber et al. 2024 as the calibration dataset. We used batch with 1M tokens and Adam W optimizer.
We compare ADMM pruned Llama2-7B with 50% density and DSF pruned model with 45% density compare the models with approximately the same storage sizes, Results are summarized in Tab. DSF maintains its advantage even after fine-tuning.
19


Reviews:
[{"review_id": "hT1i54iZqw", "reviewer": "Reviewer_VFC3", "summary": "The paper proposes Double Sparse Factorization (DSF) of the weight matrices to prune them effectively. They formulate it as an alternating optimization and optimize using ADMM. The experiments show a clear benefit of the proposed method on Llama for a language task and resnet on image classification.", "questions": "1. Could you discuss how this is related to sparse coding?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The idea is nice, the problem formulation is neat, and using ADMM for optimization is elegant. \n2. On pruning LLAMA, the method shows clear benefit over the compared methods. Image classification experiments are marginally better than previous methods.", "weaknesses": "1. The SVD comparison is unfair in my opinion. SVD is more suited for low-rank compression and it may not enforce sparsity. Using the sparsity ratio as the main criterion may not be ideal. Why not use FLOPs? As FLOPS directly relates to inference speed as opposed to sparsity ratio. I would suggest that the authors include a comparison based on FLOPs in addition to the sparsity ratio. This would provide a more comprehensive evaluation of computational efficiency across different compression methods, including SVD and sparse factorization approaches.\n2. ADMM optimization may be compute-intensive. Not much discussion about it unless I missed something. Could you provide an asymptotic time complexity analysis and/or empirical running time comparison of the ADMM? You may also discuss the trade-offs between computational cost and compression quality, as it would give readers a clearer understanding of practical applicability of the proposed method.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EMiAnqHFyw", "reviewer": "Reviewer_qugK", "summary": "This work introduces double sparse factorization (DSF) which combines matrix decomposition with pruning to yield compressed neural networks with better generalization performance than the baselines used for comparison. The authors demonstrate that their proposed algorithm, an extension of the alternating direction method of multipliers (ADMM) algorithm, is capable of achieving competitive results when compressing pretrained LLMs and CNNs.", "questions": "* Specifically which LLaMa model is used for reporting the results in Table 1? The authors refer to both LLaMa 1 and 2 in their experimental setup. \n* Does DSF provide latency/throughput benefits over dense or typical sparse networks (single layer sparsity) when using DeepSparse Engine? \n* Can DSF be extended to 2:4 sparsity? What is the trade-off with generalization performance? \n* How do the pruned LLMs compare when evaluated on OpenLLM v1 leaderboard evaluation tasks?\n* Missing results for Wanda at 70% sparsity: Why were these not included in Table 1? \n* What is the memory overhead when fine-tuning DSF LLMs in a naive way (i.e., with masked paramters intead of compressed representations)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* While pruning of factors obtained from matrix decomposition is not a novel contribution per se (Le Magoarou & Gribonval, 2016), its application to pretrained model compression is novel as far as I know. In any case, this work clearly distinguishes itself from prior art by focusing on the model compression task, particularly in the context of LLMs. \n* The paper is well written. \n* The empirical results outperform strong, SOTA baselines in a variety of contexts for LLMs and CNNS. \n* The authors take care to consider some of the practical concerns of their method, such as masking overhead. The demonstration of the generalization of DSF with a shared fixed A factor mask is particularly compelling. \n* Compression and efficient inference is of particular importance as model sizes continue to grow and scale. As such, this work addresses a timely and important topic.", "weaknesses": "Overall, I am leaning towards accept. However, I have some significant concerns regarding the practical applicability of the proposed method. Fundamentally, we require compressed models that offer advantages in one or more of the following dimensions: memory overhead, latency, and/or throughput. For each of these dimensions, we can consider both training and inference. For the following discussion, let’s consider an intermediate fully-connected layer from a decoder block in a  LLaMa 2-7B @ 50% sparsity. This layer’s weight tensor is of shape (11008, 4096). \n\n* Fine-tuning (FT) / training memory overhead: During FT, the proposed method requires ~37% more memory to store the intermediate activations of X@A@B compared with X@W. Activations can account for a significant portion of the overall memory footprint during training and this should be acknowledged in the paper. \n* Mask overheads: Assuming a bit-mask compression strategy and no shared masks between A factors, we find a similar 37% increased overhead compared to single layer sparsity. With shared A factors this overhead drops to ~1%, assuming the mask is shared across all 36 decoder blocks. From this perspective, I find the fixed-mask variant of DSF to be the most practically interesting. \n* Indices instead of bitmasks: In the introduction, the authors suggest using indices to store the locations of non-zero elements. However, given that we require uint16 indices to represent all positions in this weight tensor, this would only be practical at sparsities >= 15/16 compared to bit-masking. Given that this is currently an unobtainable level of sparsity for LLMs and roughly the limit at which we are able to find performant CNNs I find the suggestion to use indices to store non-zero locations poorly motivated. \n* Latency and Throughput: This is the most challenging dimension to estimate. Although the FLOPs analysis suggests similar performance to OBC, this may be misleading considering the additional matmul operations required in the low-rank decomposition and subsequent increase in overall memory bandwidth required to store and load intermediate activations between subsequent matmul kernel calls. I would be more convinced of the practical application for DSF if the authors include a discussion on runtime latency. This could be supported by preliminary benchmarking using Neural Magic’s DeepSparse Engine which would offer some empirical evidence of improved runtime properties. \n* 2:4 support: It’s unclear if the proposed method can support 2:4 sparsity as this would require a fixed sparsity level of 50% for both factors. The authors found that a smaller level of sparsity (~33%) yields the best performance but this prohibits using 50% sparsity in both factors as required for 2:4. \n* Hyperparameter sensitivity: There are a number of specific sparsity values used in the experimental method (16% sparsity, 25% sparsity, etc.). How sensitive is DSF to these values? If DSF is applied to a new model family, is it required to perform a hyperparameter search to find the optimal sparsity level for the smaller factor? How were these sparsity levels found? Could the authors add the results of their hyperparameter sweep for these values, assuming this was how the values were determined. \n* Reliance on PPL: The authors claim that their method “is the first layer-wise pruning method in which the larger pruned model is better than the dense smaller model.”. I believe this claim requires more evidence to support, namely, downstream evaluation for the compressed LLMs on real-world tasks. I would be more willing to support this claim with empirical results from the pruned models on OpenLLM Leaderboard v1 or similar. Relying on perplexity alone has been shown to be misleading for compressed models [1]. \n* LLM fine-tuning: The fine-tuning results section would benefit from expanding its scope to include fine-tuning of the compressed LLMs. I would also be interested to see what the memory overhead looks like for DSF when naive masked sparsity is used. \n\nBased on the above it appears that the memory overhead with a fixed A factor mask is comparable to regular pruning. However, it appears likely that the latency for DSF will be worse than models pruned with other techniques (Wanda, etc.). It is unclear whether DSF can support 2:4 sparsity whereas other methods such as Wanda do support this format (albeit with high loss). If tuning is required per model to set the smaller factor sparsity, this may result in DSF being much more expensive to use on new models. I am willing to accept this paper as the generalization results are good and motivate future work exploring this direction. However, given that DSF is fundamentally motivated by network compression, a more holistic discussion of the above points would convince me to raise my score and, in my opinion, raise the impact of this work. \n\n[1] A. Jaiswal, Z. Gan, X. Du, B. Zhang, Z. Wang, and Y. Yang, “Compressing LLMs: The Truth is Rarely Pure and Never Simple,” Oct. 02, 2023, arXiv: arXiv:2310.01382. doi: 10.48550/arXiv.2310.01382.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ykQlKNPqyv", "reviewer": "Reviewer_aP2Z", "summary": "The paper proposes Double Sparse Factorization, a method that, instead of pruning the original weight matrix, factorizes it into the product of two matrices (similar to e.g. low-rank decomposition), which together satisfy the same sparsity constraint. To solve this problem, they use the ADMM method. The paper claims to improve upon existing pruning and layer-wise pruning approaches, and they back their claims with experiments on state-of-the-art language models and medium-sized vision models. In addition, they show that the superiority of their methods seems to prevail after retraining the pruned models.", "questions": "- In Line 465 you state that your method does not support gradual pruning with fine-tuning between pruning steps, could you elaborate why? I am not sure what I am missing here.\n- In Line 196, you first \"look into the projection problem\". I am not quite sure I understand correctly how that is not the entire problem? A proper solution to that is what you are looking for, isn't it?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The idea is interesting, to the best of my knowledge relatively novel, and the experiments are quite convincing. Most of the paper is fairly easy to follow and the reader is not left with many questions. I appreciate that the authors provide results before and after retraining the pruned models, as this is often not done in other papers. The proposed method is interesting, however there are open questions that I will discuss below.", "weaknesses": "I have several concerns regarding the soundness, clarity, and contribution of this work, which I detail below. I hope these remarks are helpful for improving the paper and am open to discussing my evaluation.\n\n### Clarity\nWhile I think that the idea proposed in this paper might be promising, I sometimes had a hard time following the paper. I think the structure as well as details could be improved.\n- Section 3.1 would greatly benefit from a more detailed explanation of the ADMM method. How are Z and U initialized? I understand that it is not your job to explain ADMM in detail, but I think that nevertheless the paper would greatly benefit from more detailed remarks - at least in the appendix. Since this method is not standard (at least in the pruning literature and to my knowledge), I think it would be helpful to make this more clear.\n- In two sentences (Line 149, 150) you basically explain how you find the sparsity mask. Why do you precondition? How exactly is the cubic schedule (I presume Zhu & Gupta?) implemented, over how many iterations, with which interval between the increases? I am trying my best to infer this from somewhere, but it is nowhere to be found? Either I am missing something or the paper is lacking a crucial part, namely how the sparsity mask is found.\n- In Line 258, you state that you are using the Wanda saliency map, I think it would be good to give the mathematical formulation to that, especially how you \"scale one of the factors back\".\n\n\n### Soundness\n- Lines 37-39: If you replace the dense weight matrix with a product of two sparse matrices, will your model not be much slower at inference than when replacing with just a sparse matrix? For Low-rank decomposition, you at least get two linear layers which are much smaller dense matrices, but in your case, you basically have two sparse matrices. While you argue in Line 162 that the total number of multiplications is equal, this is far from realizable on the existing hardware. In practice, you incur a non-trivial overhead. I would like to hear the authors' thoughts on this.\n- Line 50: \"our method is the first layer-wise pruning method in which the larger pruned model is better than the dense smaller model\" - Are you sure this is true? I feel like already the original SparseGPT paper gets fairly close and there have been a variety of improvements since then, e.g. using non-uniform layer-wise sparsity. Maybe this claim can or should be made more precise.\n\n\n### Experimental Validation\n- Missing ablations: The paper is fixing a lot of hyperparameters and making claims without ablations. That includes e.g. the selection of sparsity distribution between the matrices (Line 209) or the initialization for A and B (Lines 248-250), among others. Such ablations should be added to justify the choice of parameters.\n- Table 1: Why are you not comparing to SparseGPT, am I missing something? In my experience, SparseGPT is a very strong baseline. Also, why do you omit Wanda for 30% density? Is Wanda using a \"finalization\" step as well, i.e., are you reconstructing the remaining weights after pruning? You get that more or less for free if you pass the calibration data through anyway.\n- Section 5.4: I find the choice of hyperparameters for the retraining/fine-tuning quite arbitrary. You use a stepped schedule for most of the pretraining, then use a stepped learning rate schedule for retraining as wellf 70 total) epochs. [1] shows that if you properly choose the initial learning rate of a linear schedule, you can recover the accuracy drop of magnitude pruning in very few iterations. I am not sure if these results would withstand scrutiny. It would be good to use best practices here, i.e., for the convolutional networks you can definitely use a linear/cosine schedule for pretraining, and then choose the initial learning rate for linear-schedule-retraining adaptively, as in [1]. This will give much more realistic results.\n\n\n### Minor Remarks\n- Line 131: I presume it should be \"**the** layer-wise pruning problem\".\n- In general, you do not seem to use the glossary package and define your DSF-acronym over and over again. That is a bit contrary to the purpose of an abbreviation. Also, you sometimes use DSF, and sometimes DFS (as in Double Factorization Sparse), see e.g. Line 315 or the caption in Line 686 where this happens in the same sentence.\n\n#### References\n[1] Zimmer, M., Spiegel, C., & Pokutta, S. (2021). How I Learned to Stop Worrying and Love Retraining. _arXiv preprint arXiv:2111.00843_. https://arxiv.org/abs/2111.00843", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)