Two Sparse Matrices are Better than One: Sparsifying Neural Networks with Double Sparse Factorization

## Abstract

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 .

## 1 Introduction

Sparse neural networks have gained attention due to their potential to reduce computational costs and memory usage, making them more efficient for deployment on resource-constrained devices (LeCun et al., ; Han et al., ; Hoefler et al., ). By reducing the number of non-zero parameters, sparse networks can achieve accuracy similar to dense networks while requiring fewer operations. Reducing network size decreases the number of weights that must be loaded into the processing unit from memory, which is crucial since memory bandwidth often becomes a bottleneck in neural network deployments, particularly during single-sample LLM inference (Xia et al., ).

In this work, we propose an improvement over a typical neural network sparsification. Instead of replacing each dense weight matrix with a sparse matrix, we replace each dense matrix with a product of two sparse matrices. This was proposed before (Giffon et al., ) but without practical success. We provide a much better heuristic for calculating sparse matrix factorization and achieve significant improvements over a wide range of models, including large language models and convolutional neural networks.

Figure: Figure 1: Comparison of LLaMA2 models pruned either using our Double Sparse Factorization (DSF) or using previously state-of-the-art ADMM pruning. We prune models using 0, 50, and 60% sparsities.
Refer to caption: /html/2409.18850/assets/x1.png

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-wise pruning scenario where one wants to preserve layer behavior for a given set of calibration inputs. Our sparse factorization algorithm is a heuristic based on alternating minimization where each subproblem is solved using the ADMM algorithm for solving a sparse regression problem (Boža, ).

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, ) for pruning convolutional image models.
We also produce state-of-the-art layer-wise pruning results for large language models. Moreover, our method is the first layer-wise pruning method in which the larger pruned model is better than the dense smaller model.

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 as regular pruning.
We also note that when one stores nonzero positions as explicit indices (not sparsity masks), the actual memory requirements only depend on a total number of non-zeros, so there is no increase in memory consumption for double sparsity.

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.

## 2 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., ; Han et al., ; Blalock et al., ; Liu et al., ; Hoefler et al., ; Srinivas et al., ).

Some approaches focus on splitting the network into individual layer-wise problems, where one wants to preserve layer behavior over a small set of calibration inputs. Optimal Brain Compression (OBC) (Frantar & Alistarh, ) removes one weight at a time and optimally updates the remaining weights in the layer. However, this approach is not feasible for large language models due to high computational cost. SparseGPT (Frantar & Alistarh, ) uses various approximations and turns OBC into a more practical algorithm at the expense of higher approximation error. Wanda (Sun et al., ) proposes to skip the weight update and prune weights based on the product of absolute magnitude and input norm. Finally, Boža () 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 et al., ) weight update.

Compression based on matrix factorization. Instead of turning weight matrices into sparse matrices, one can replace them with a product of multiple smaller matrices. A typical example is a low-rank factorization (Li & Shi, ; Jaderberg et al., ) where one turns an $n\times m$ matrix into a product of $n\times k$ and $k\times m$ matrices, where $k<<\min(n,m)$. More complicated examples include butterfly matrices (Dao et al., ) and Monarch matrices (Dao et al., ), where individual factors have some specific structure. Monarch matrices are the product of block-diagonal, permutation, and another block-diagonal matrix. The projection of a matrix into a set of monarch matrices is done by splitting the original matrix into blocks and then running a low-rank decomposition of each block. Another option is to decompose the matrix as a sum of low-rank and sparse matrix (Nikdan et al., ; Yu et al., ; Ke & Kanade, ; Wright et al., ).

Separable convolutions. Convolutional layer can be naturally factorized into depthwise (applying filter per input channels) and pointwise convolution (mixing multiple channels). The idea was found initially in MobileNets (Howard, ; Sandler et al., ), but they placed nonlinearity between the depthwise and pointwise convolutions. However, some works successfully use separable convolutions without nonlinearity between them (Perešíni et al., ; Kriman et al., ).

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., ).
Le Magoarou & Gribonval () provides a heuristic based on the proximal gradient step called palm4msa, which is then used by Giffon et al. () for compression of neural networks, but with very limited practical success. In the experiments section, we compare the quality of our factorization algorithm with palm4msa.

## 3 Preliminaries

In this work, we work with the post-training neural network sparsification scenario.
We are given an already-trained network, and we will replace each weight matrix with a matrix that can be represented more efficiently, such as a sparse (Hoefler et al., ) or Monarch matrix (Dao et al., ). Usually, the replacement is done by solving the projection problem, where we are looking for a matrix closest (typically using the Frobenius norm) to the original one. For example, when the target matrix is sparse, solving the projection problem is just the magnitude pruning (Han et al., ).

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 statistics for each layer and prune them during one forward pass. This is usually done by solving layer-wise pruning problem (Frantar & Alistarh, ; ; Boža, ), where given calibration input $X$, original matrix $W$, one looks for sparse matrix $W_{p}$, such that the layer-wise error $||XW-XW_{p}||_{2}^{2}$ is minimized.

### 3.1 Layer-wise pruning via ADMM

Boža () solves the layer-wise pruning problem by application of the alternating direction method of multipliers (Boyd et al., ) (ADMM). It provides a method for finding pruned weights given a pruning mask and also a heuristic for finding the pruning mask. First, given $X$, $W$, and pruning mask $M$, we are looking for $W_{p}$ such that $(1-M)\odot W_{p}=0$ and layer-wise error is minimized. This is done via $m$ ADMM iterations ($\rho$ is penalty factor, $U$ represents scaled dual variables):

$$ $\displaystyle\widehat{W}^{(k+1)}$ $\displaystyle=(X^{T}X+\rho I)^{-1}(X^{T}XW+\rho(Z^{(k)}-U^{(k)})$ (1) $\displaystyle Z^{(k+1)}$ $\displaystyle=M\odot(\widehat{W}^{(k+1)}+U^{(k)})$ $\displaystyle U^{(k+1)}$ $\displaystyle=U^{k}+\widehat{W}^{(k+1)}-Z^{(k+1)}$ $$

We will take final $W_{p}=Z^{(m)}$ as the output.
Pruning mask $M$ is found during the optimization process. First, the problem is preconditioned, so the diagonal of $X^{T}X$ contains ones. Then, the sparsity matrix $M$ is found using gradual pruning with the cubic schedule.

## 4 Double Sparse Factorization

In typical neural network pruning, we replace weight matrix $W$ with matrix $W_{p}$ which has at most $z$ nonzeros, i.e.
$||W_{p}||_{0}\leq z$.
Here, we propose to replace weight matrix $W$ with shape $n\times m$ with a product of two sparse matrices $AB$ such that they have at most $z$ nonzeros in total, i.e. $||A||_{0}+||B||_{0}\leq z$.
We call this a double sparse factorization.
Usually, we assume that $A$ is a matrix with shape $n\times n$, $B$ is a matrix with shape $n\times m$, and $n\leq m$; if not, we transpose the matrix $W$.

### 4.1 Expressiveness and efficiency of double sparse factorization

Figure: 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 a path through sparse matrices.
Refer to caption: /html/2409.18850/assets/x2.png

Many matrix factorizations mentioned previously in the literature can be (often trivially) rewritten to double sparse representation with the same number of non-zeros.
For example, low-rank factorization commonly done via SVD (Li & Shi, ; Stewart, ) is already in the double sparse form.
Monarch factorization (Dao et al., ), which is a product of block-diagonal, permutation, and block-diagonal matrices, can represented in double sparse form by fusing a permutation matrix with one of the block-diagonal matrices.
Also, double sparse factorization can efficiently represent a matrix that consists of multiple disjoint low-rank submatrices.

The tricky case is an ordinary sparse matrix $W_{p}$. It can be represented in double sparse form as a product of identity and the original matrix: $IW_{p}$. However, this comes with the cost of additional non-zero entries for the identity matrix.
However, in the experiments, we will show that the double sparse representation represents the original dense matrix much better than an ordinary sparse matrix with the same number of non-zeros.

### 4.2 Heuristic algorithm for obtaining double sparse factorization

First, we look into the projection problem. Given matrix $W$, we want to replace it with some compressed matrix $W_{c}$, where their difference $||W_{c}-W||_{F}$ is minimized.

In our case, $W_{c}$ is a product of two sparse matrices $A,B$.
Thus, we are given matrix $W$ and are looking for matrices $A,B$ such that:

$$ minimize $\displaystyle||AB-W||_{F}$ subject to $\displaystyle||A||_{0}+||B||_{0}\leq z$ $$

This problem is NP-hard even when the sparsity pattern for matrices $A$ and $B$ is given (Le et al., ) thus we solve our problem heuristically.

First, we decide how many nonzeros we allocate for each matrix, so our condition changes to $||A||_{0}\leq z_{a},||B||_{0}\leq z_{b}$.
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.

One inner step of our algorithm can formalized as: Given $W,B$, find $A$ such that:

$$ minimize $\displaystyle||AB-W||_{F}$ subject to $\displaystyle||A||_{0}\leq z_{a}$ $$

This problem is just an $L_{0}$ constrained linear regression. We solve it using an iterative ADMM solver Boža () mentioned in preliminaries, which heuristically finds matrix mask and corresponding values. We also apply the following heuristic(^1^11some people call this a dark magic) improvements.

Figure: Algorithm 1 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 $z_{a},z_{b}$ we find $A,B$ such that $||A||_{0}\leq z_{a}$, $||B||_{0}\leq z_{b}$ and $AB$ is as close as possible to $W$.

Warm starting the inner iterations. To improve the convergence of ADMM iteration, we 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 to 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 $\widehat{W}_{b}=(A^{T}A+\rho I)^{-1}(A^{T}W+\rho(B^{(k-1)}-U_{b}^{(k-1)}))$. Instead of using $\rho$ in the first iteration, we use smaller $\rho_{0}$ (we use default $\rho=1$ 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 $\rho_{0}$ from 0 to 1 throughout the optimization; we found that a 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 value to matrices $A$ and $B$. We tested several choices, including random initialization and singular value decomposition, but we settled on initializing $A$ as an identity matrix and $B$ with magnitude pruning of the original input matrix.

### 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-XAB||_{2}^{2}$ is minimized.

We solve this problem by first running 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., ). We then scale one of the factors back. We do not do this rescaling for vision models.

We then process with the finalization step. We then fix all sparsity masks and apply the ADMM algorithm for finding $B$ so that $||XW-XAB||_{2}^{2}$ 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$ are other variables from ADMM optimization):
$||XW-XAB||_{2}^{2}+\rho/2||A-Z+U||_{2}^{2}$ is minimized. After taking gradients, we solve the equation: $X^{T}XABB^{T}+\rho A=X^{T}XWB^{T}+\rho(Z-U)$. This is a special type of Sylvester equation Roth (); Jiang & Wei (), which can be solved using the eigendecomposition of $X^{T}X$ and $BB^{T}$.
We provide a solution to this problem in the appendix. We found that optimizing $A$ is only helpful for compressing vision models; we do not use it when compressing large language models.

## 5 Experiments

We evaluate our proposed Double Sparse Factorization in multiple settings.
First, we test it on layer-wise pruning of large language models. We compare our algorithms to ADMM pruning (Boža, ), which produces high-quality solutions in a reasonable time, even for large-scale models.
Then we test it also on layer-wise pruning of vision models and compare it with Optimal Brain Compression (Frantar & Alistarh, ), state of the art layer-wise pruning algorithm.

We then proceed with the evaluation of the quality of our algorithm on the matrix projection problem. We compare with various matrix compression algorithms, including palm4msa (Le Magoarou & Gribonval, ), Monarch decomposition (Dao et al., ), and SVD.
Finally, we also test whether models compressed with DSF can be successfully fine-tuned.

### 5.1 Layer-wise pruning of large language models

**Table 1: Perplexity on 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 |
|  | 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 |
|  | 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 |
| 30% | ADMM | 18.66 | 17.51 | 13.82 | 7.80 |
| 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 |  |

Setup. We follow same setup as in Wanda (Sun et al., ) and ADMM pruning (Boža, ).
We use 128 calibration samples from the C4 training dataset (Raffel et al., ) and prune layers sequentially in order.
We prune LLaMA (Touvron et al., ) and LLaMA-2 (Touvron et al., ) models. Similarly to previous works, we measure perplexity on held-out Wikitext (Merity et al., ). When factorizing square matrices (mainly in self-attention), we set the sparsity of one sparse factor to $16\%$. When factorizing rectangular matrices, the smaller factor will have $25\%$ sparsity. The number of nonzeros in 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 (DFS) 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 a random mask shared across all layers (but we run the finalization step).
We compare our method with two layer-wise pruning algorithms: Wanda (Sun et al., ), which prunes weights with the smallest product of value and activation norm, and ADMM pruning (Boža, ), which also updates weights during the pruning using alternating direction method of multipliers.

Results. Results are summarized in Tab. [1](#S5.T1) and Fig. [1](#S1.F1).
Our Double Sparse Factorization is superior to previous layer-wise pruning methods. To our knowledge, this is the first time when a layer-wise pruned network has better perplexity than its dense counterpart (compare 50% pruned LLaMA2-13B with perplexity 4.87 to dense LLaMA2-7B with perplexity 5.12).
Even when we 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.

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, ).

### 5.2 Comparison with Optimal Brain Compression

Optimal Brain Compression (Frantar & Alistarh, ) is a post-training layer-wise pruning algorithm, which prunes each network layer by removing one connection at a time and optimally updating 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 et al., ).

In this experiment, we evaluate the effectiveness of our Double Sparse Factorization of ResNet50 on Imagenet (Russakovsky et al., ) dataset.
We first run the OBC pipeline to determine layer-wise 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 is set to $max(0.16,s/2)$ where $s$ 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. [2](#S5.T2). 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.

**Table 2: Comparision of our Double Sparse pruning vs. Optimal Brain Compression on Resnet50 using Imagenet dataset.**
| Number of nonzeros | FLOP reduction | Method | Test accuracy [%] |
| --- | --- | --- | --- |
| 25.5M | - | Dense | 76.13 |
| 16.8M | 2x | OBC | 75.65 |
| DSF | 75.78 |  |  |
| 12.3M | 3x | OBC | 75.01 |
| DSF | 75.56 |  |  |
| 10.2M | 4x | OBC | 74.05 |
| DSF | 74.95 |  |  |

### 5.3 Comparison with other matrix approximation methods

Figure: Figure 3: Reconstruction error of various compression methods on various matrix sizes for weight projection problem. We compress each 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.
Refer to caption: /html/2409.18850/assets/x3.png

Now, 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 Factorization (DSF), palm4msa from Faust library (Le Magoarou & Gribonval, ), 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 et al., ), which factorizes matrix into block-diagonal, permutation and block-diagonal matrix.
In all cases, we aim for 4x compression, i.e., each method can produce matrices that contain at most 25% of non-zeros in total compared to the original matrix.

Results are summarized in Fig. [3](#S5.F3). We see that our DSF consistently outperforms other methods. Interestingly, palm4mse is not better for small matrix sizes than magnitude pruning. Also, Monarch decomposition seems to be worse than ordinary SVD.

### 5.4 Fine-tuning models pruned with double sparse factorization

**Table 3: Test accuracy on CIFAR-10 using Resnet-20 with varying width. Density refers to the total % of nonzero weights compared to the dense model. FT refers to fine-tuning.**
| Density | Method | Resnet-20-16 | Resnet-20-32 |
| --- | --- | --- | --- |
| 100% | Dense | $92.2\pm 0.2$ | $94.0\pm 0.1$ |
| 20% | Magnitude w/o FT | $70.6\pm 0.5$ | $86.2\pm 0.3$ |
| Double sparse w/o FT | $80.0\pm 0.9$ | $91.6\pm 0.1$ |  |
| Magnitude w/ FT | $90.7\pm 0.3$ | $93.2\pm 0.1$ |  |
| Double sparse w/ FT | ${\bf 91.1\pm 0.1}$ | ${\bf 93.5\pm 0.1}$ |  |
| 10% | Magnitude w/o FT | $29.0\pm 2.9$ | $51.1\pm 5.2$ |
| Double sparse w/o FT | $48.9\pm 2.9$ | $84.1\pm 0.5$ |  |
| Magnitude w/ FT | $88.4\pm 0.3$ | $92.1\pm 0.2$ |  |
| Double sparse w/ FT | ${\bf 89.3\pm 0.3}$ | ${\bf 92.5\pm 0.1}$ |  |

**Table 4: Test accuracy on Imagenet using Resnet-50. Density refers to the total % of nonzero weights compared to the dense model. FT refers to fine-tuning.**
| Density | Method | Test accuracy [%] |
| --- | --- | --- |
| 100% | Dense | $76.13$ |
| 20% | Magnitude w/o FT | $54.43$ |
| Double sparse w/o FT | $71.85$ |  |
| Magnitude w/ FT | $75.43$ |  |
| Cyclical pruning | $75.3$ |  |
|  | Double sparse w/ FT | ${\bf 75.78}$ |
| 10% | FT | $9.87$ |
| Double sparse w/o FT | $55.76$ |  |
| Magnitude w/ FT | $73.32$ |  |
| Cyclical pruning | $73.3$ |  |
|  | Double sparse w/ FT | ${\bf 74.50}$ |

Finally, we test whether the double sparse advantage remains after fine-tuning a whole model.
In this experiment, we only focus on the original matrix projection and do not perform any input-dependent finalization.
We test the pruning of Resnet-20 (He et al., ) with varying starting widths (16 and 32) on the CIFAR-10 (Krizhevsky et al., ) dataset. We also test using Resnet-50 using Imagenet dataset (Russakovsky et al., ). In all experiments, we use the same sparsity in all layers.
For CIFAR-10 experiments, we first train the dense network using the procedure from Liu et al. (). 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) to 10 or 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 50 epochs, starting with a learning rate of 0.01, which decays to 0.001 after 20 epochs. We run each setting 5 times using different seed. Results are shown in Tab [3](#S5.T3).

For the Imagenet experiment, we start with the pre-trained Resnet-50 from Torchvision (maintainers & contributors, ).
We then uniformly sparsify every layer except the first and last one and fine-tune using SGD, with a linear learning rate decay from 0.01 to zero and momentum of 0.9.
We also compare with results reported by Srinivas et al. (), which prunes the neural network in multiple cycles with resets (Cyclical pruning). Results are shown in Tab [4](#S5.T4).

In all cases, starting test accuracy is higher for double sparse pruning and stays better when finetuned. This is especially evident at higher sparsities.

## 6 Conclusion

In this work, we introduced Double Sparse Factorization (DSF), an 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 sacrificing model accuracy, achieving state-of-the-art results compared to traditional pruning techniques. 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 a more complicated technique than just removing weights.

## Appendix A Appendix

### A.1 Solving for A in the layer-wise reconstruction problem

Recall that we want to find sparse $A$ such that $||XW-XAB||_{2}^{2}$ 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-XAB||_{2}^{2}+\rho/2||A-Z+U||_{2}^{2}$ is minimized.

After taking gradients, we solve the equation:

$$ $X^{T}XABB^{T}+\rho A=X^{T}XWB^{T}+\rho(Z-U)$ $$

We solve this equation using eigendecomposition and one simple trick.
We use following eigendecompositions:$X^{T}X=QDQ^{T},BB^{T}=RER^{T}$ (where $D,E$ are diagonal matrices and $Q,R$ are orthonormal).

We then multiply the equation by $Q^{T}$ from left and $R$ from right and get:

$$ $DQ^{T}ARE+\rho Q^{T}AR=Q^{T}(X^{T}XWB^{T}+\rho(Z-U))R$ $$

We will now use that $D,E$ are diagonal and create an outer product of their diagonals: $F=\operatorname{Tr}(D)\otimes\operatorname{Tr}(E)$.
Now, we can use Hadamard product to get:

$$ $F\odot Q^{T}AR+\rho Q^{T}AR=Q^{T}(X^{T}XWB^{T}+\rho(Z-U))R$ $$

And with slight abuse of notation (where $F+\rho$ means adding $\rho$ to every element of $F$) we get:

$$ $Q^{T}AR=Q^{T}(X^{T}XWB^{T}+\rho(Z-U))R\oslash(F+\rho)$ $$

And thus:

$$ $A=Q(Q^{T}(X^{T}XWB^{T}+\rho(Z-U))R\oslash(\operatorname{Tr}(D)\otimes\operatorname{Tr}(E)+\rho))R^{T}$ $$

### A.2 Ablation of DSF settings

We investigate some variations of DSF settings in Fig. [4](#A1.F4). 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.

Figure: Figure 4: Reconstruction error of various settings of DSF. Default DSF used 40 outer and 5 inner iterations. DFS 20x10 refers to DSF with 20 outer and 10 inner iterations. DSF w/o annealing refers to DSF where we set first $\rho_{0}=1$.
Refer to caption: /html/2409.18850/assets/x4.png

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Could you discuss how this is related to sparse coding?
soundness: 3
strengths: 1. The idea is nice, the problem formulation is neat, and using ADMM for optimization is elegant. 
2. On pruning LLAMA, the method shows clear benefit over the compared methods. Image classification experiments are marginally better than previous methods.
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.
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.
2. 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.

---

confidence: 4
contribution: 2
initial_rating: 6
presentation: 3
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. 
* Does DSF provide latency/throughput benefits over dense or typical sparse networks (single layer sparsity) when using DeepSparse Engine? 
* Can DSF be extended to 2:4 sparsity? What is the trade-off with generalization performance? 
* How do the pruned LLMs compare when evaluated on OpenLLM v1 leaderboard evaluation tasks?
* Missing results for Wanda at 70% sparsity: Why were these not included in Table 1? 
* What is the memory overhead when fine-tuning DSF LLMs in a naive way (i.e., with masked paramters intead of compressed representations)?
soundness: 3
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. 
* The paper is well written. 
* The empirical results outperform strong, SOTA baselines in a variety of contexts for LLMs and CNNS. 
* 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. 
* 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.
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.
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). 

* 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. 
* 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. 
* 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. 
* 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. 
* 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. 
* 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. 
* 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]. 
* 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. 

Based 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. 

[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.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
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.
- 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?
soundness: 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.
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.
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.

### Clarity
While 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.
- 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.
- 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.
- 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".


### Soundness
- 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.
- 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.


### Experimental Validation
- 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.
- 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.
- 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.


### Minor Remarks
- Line 131: I presume it should be "**the** layer-wise pruning problem".
- 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.

#### References
[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

Meta-review: The authors propose a method for sparsifying neural network parameter matrices by reparameterizing them as the product of two sparse matrices.  This is accomplished via a heuristic that seeks to minimize the error of the factorized approximation relative to the original weights subject to hard (i.e., L0) sparsity constraints on the factorized matrices via ADMM.  While the idea is conceptually rather simple, the authors are largely in agreement that the empirical performance of the method is convincing.  Reviewers raised concerns that the increased overhead of performing two sparse matrix multiplications could be detrimental, but the authors note that their primary goal is to reduce the memory footprint of the model and not necessarily improve inference speed.

While one reviewer still notes potential issues with clarity in the manuscript, this would appear to be something that can be addressed in a final revision and I believe this work is of sufficient interest and quality to be accepted.

Decision: Accept (Poster)