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

Author's response

Thank you very much for a helpful and insightful review. Here are the responses to your concerns; we split them over multiple comments. >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. We agree that the ADMM method for pruning is underexplored and not well known. We expanded section 3.1 to provide a quick overview of ADMM method used by "Fast and Effective Weight Update for Pruned Large Language Models" (https://openreview.net/forum?id=1hcpXd9Jir). Mainly, we talk about what ADMM does, how layer-wise pruning maps onto ADMM, and how the pruning mask is found. We decided not to put more details into an appendix because we believe that if the reader needs even more information, reading the original paper by Boza would be much more beneficial than reading the appendix in this paper. > 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". We added this to section 4.3. > 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. We added section 4.4 to discuss the DSF method's computational concerns. Part of our argument regarding speed can be summarized as follows: a) In many cases (e.g., local LLM inference), the main concern is fitting the best model into a small memory footprint. In this case, a slight decrease in inference speed might be tolerable. b) There are cases (again, for example, local single batch LLM inference) where the main computational bottleneck is transferring weights from memory to the local cache. This is explored in Flash-LLM (https://arxiv.org/pdf/2309.10285). Memory transfer is similar for DSF and for single sparsity. c) Doing two sparse multiplications is not much slower than doing one sparse multiplication with the same total number of nonzeros. We tested this using DeepSparse and found that DSF is ~10-20% slower than ordinary sparse multiplication (this is inline with other literature), but still faster than dense multiplication. > 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. SparseGPT was not better in terms of perplexity (5.63 for pruned Llama2-13B, 5.12 for dense Llama2-7B), but is better on zero-shot benchmarks. Outlier weighted sparsity (https://arxiv.org/pdf/2310.05175) might be better, but they do not report such results. "Discovering Sparsity Allocation for Layer-wise Pruning of Large Language Models" (https://openreview.net/forum?id=rgtrYVC9n4) reports better results in zero-shot benchmarks but does not report perplexity. Thus, we are adjusting our claim to uniform layer-wise pruning and perplexity measure. > 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. We added even more ablations to the appendix.

Author response part 2

> 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. ADMM by Boza is better than SparseGPT, so we feel that including it in Table 1 does not bring any value. We added SparseGPT results to Table 1. We omitted 30% density with Wanda, because it has bad results. But since this raised questions, we put it back. Wanda algorithm does not use finalization, it just selects weight to prune. But Wanda with finalization is just ADMM-1 algorithm in ADMM pruning paper and is generally worse than ADMM with pruning done gradually. > 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. First of all, in the Imagenet experiment, we already used a linear schedule for fine-tuning (we also compared it to cyclical pruning to ensure that our baseline is high-quality). But you are completely right about CIFAR. Here, we switched to the linear learning rate schedule for finetuning, which leads to ~0.5% gains in almost all cases (and DSF is still better). Thank you for pointing this out. We keep the pretraining schedule as is since it produces high-quality dense results (slightly better than reported in the original resnet paper). >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. ... Thank you for pointing all of this out. DFS is just a typo. We also removed unnecessary DSF definitions. > 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. First of all, we changed the wording from "does not support" to "it is unclear how to do." Here is our reasoning why it is unclear: Imagine that your target density is 25%. In regular pruning, you can first prune to 50% density, then finetune network, and then prune again to 25% density. This works because you can easily prune the already-pruned matrix. But if you apply DSF, how should you apply DSF again with a lower target density? You could multiply the factors to get a dense matrix and factorize that, but is it the correct way? > 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? The original layer-wise pruning problem is min ||XW - XAB||^2. The projection problem is min ||X - AB||^2, thus a simplified version. Thank you again for your very good suggestions. We hope our response clarifies your concerns. If that’s the case, we would greatly appreciate it if you would consider raising your score.

Quick replies

Thank you for the replies, here is a quick clarification. > So are you here using the Hadamard product between a real value (the norm) and a matrix, or am I reading this in a wrong way? Yes, this was a slight abuse of notation, we changed to explicit element calculation in the paper. We calculate the norm of each feature and multiply the corresponding row in the matrix W (assuming your linear layer calculates $XW$, where $X$ is input and $W$ is the weight matrix). > I am also not entirely sure that the storage requirements are actually the same, given that starting from an matrix, you end up with an and an matrix, i.e., you increase from to parameters, despite enforcing the same overall sparsity. I We have the same number of nonzeros, so same storage requirement for them. Storage requirements for sparsity masks will be higher, but masks are a smaller part of the storage costs. We also have Figure 7 in the Appendix, which shows that DSF models are much better even when we consider overall storage size (not just the number of nonzeros). > I might be mistaken here, but e.g. for CSR format, the row pointer can also depend on the number of rows, which would clearly yield some overhead here. Yes, there will be a small overhead. For example, if you have a matrix size 4096*4096 and 95% sparsity, you need 838860 numbers for nonzeros and 838860 numbers for column indices and 4096 numbers for row pointers. DSF would need an additional 4096 number for row pointers in the second matrix, which is less than 0.3% of overall storage costs. > that time could be used to reconstruct the weights given the found sparsity mask of SparseGPT. In my experience, this improves even SparseGPT and would yield a more realistic comparison. SparseGPT does not have an explicit parameter that trades solution quality and solution time. There is a block size (the lower the blocksize, higher the solution time), but that does not lead to an increase in solution quality in our experience (and for example for Llama-2-7B and 50% sparsity changing block size from 128 to 64 lead to much worse solution, perplexity went from 6.52 to 6.99). > Maybe I am missing something again, but I assume that then the projection problem should involve W and not X? Sorry, this is our spelling error in that comment. It should read: "The projection problem is min ||**W** - AB||^2, thus a simplified version." Paper has this everywhere correctly, this was a mistake only in this comment.

Authors' response part 2

> 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. > Can DSF be extended to 2:4 sparsity? What is the trade-off with generalization performance? DSF cannot do 2:4 sparsity right now. Also, if both factors are in 2:4 sparsity and DSF runs over a square matrix, then you have the same number of nonzeros as the original matrix, which does not bring any gains. What might be viable with 2:4 are two things: a) Having one factor in 2:4 format and the second one as very sparse (95+% of sparsity). b) Having block sparsity with blocks having 2:4 sparsity. But both options require significant research and tuning, and we leave them for future work right now. > 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. We found that having both factors with an equal number of nonzeros works quite well but can be slightly tuned. We added more ablations to the appendix (we determined hyperparameters by taking a couple of layers and observing reconstruction error). > 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]. > How do the pruned LLMs compare when evaluated on OpenLLM v1 leaderboard evaluation tasks? We are adjusting our claim to uniform layer-wise pruning and perplexity measure. We also added measurements on seven zero-shot evaluations used in other pruning papers before (arc-easy, arc-challenge, winogrande, and hellaswag are also parts of OpenLLM v1). > LLM fine-tuning: The fine-tuning results section would benefit from expanding its scope to include fine-tuning of the compressed LLMs. A decent full-parameter finetuning run takes a lot of time (one also needs to do a decent hyperparameter sweep, at least for the learning rate). We are unsure whether we can make this happen during the discussion period. > I would also be interested to see what the memory overhead looks like for DSF when naive masked sparsity is used. Using masked sparsity naively would result in many problems (mainly ~40% more space needed for weight storage). We tested a different approach, where we stored weight in compressed format and unpacked on the fly during the forward pass. If finetunng batch is large enough, this occurs a negligible time overhead. We explore this more in the appendix A.4. > 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. We have Llama1-7B (denoted as 1-7B) and Llama2-7/13/70B (denoted as 2-7B, 2-13B, 2-70B respectively). > Missing results for Wanda at 70% sparsity: Why were these not included in Table 1? We omitted 30% density with Wanda because it had bad results. But since this raised questions, we put it back. Thank you again for your very good suggestions. We hope our response clarifies your concerns. If that’s the case, we would greatly appreciate it if you would consider raising your score.

Additional results for LLM finetuning (distillation)

We finished limited finetuning (distillation) experiments (run for 2 days on 4xA100). We distilled Llama2-7B and compared the fine-tuning of regularly pruned model via ADMM with 50% density and the DSF pruned model with 45% density (after accounting for masks, these models have similar storage sizes). Results are summarized in the appendix, and here we put the table for the reference: | Model | Pruning type | PPL w/o finetuning | Zero-shot w/o finetune | PPL w/ finetuning | Zero-shot w/ finetuning | |-----------|--------------|--------------------|------------------------|-------------------|-------------------------| | Llama2-7B | Dense | 5.12 | 59.71 | - | - | | Llama2-7B | ADMM 50% | 6.33 | 56.64 | 5.61 | 58.00 | | Llama2-7B | DSF 45% | 5.78 | 57.03 | 5.35 | 59.00 | As we can see, DSF retains its advantage even after finetuning.

Clarifications

Thank you, for the response, here is a quick clarification. >Could you share the dense runtimes as well. They were actually in Table 6, but hidden in parentheses under batch size (not the best idea on our part). We put dense runtimes into a separate column to make benchmarks more readable. We also double-checked the dense runtime and found that Deepsparse is slightly faster than just torch.compile with max-autotune (and thus every dense number is from Deepsparse). In all cases, even at 50% density, DSF is faster than dense runtime (e.g., for 4096x4096 matrices with 64 batch size, we have dense runtime of 872 ms, simple sparsity runtime of 470 ms, and DSF runtime of 533 ms). > Could you repeat the deepsparse benchmarks with additional cores as well? Added Table 7 with this. > Could you share deepsparse benchmarks with alternating 16/25% sparsity... We tested this and it is not different from the results with even distribution. For square matrices with size 4096x4096 with 50% total density, 16% density in the first factor and 34% in the second we get following: | Batch size | Dense runtime | Single sparsity | DSF | |------------|---------------|-----------------|-----| | 64 | 162 | 101 | 122 | | 256 | 551 | 301 | 354 | For rectangular matrices with size 4096*11008 (found in Llama-2-7B MLP block), 50% total density, 25% density in smaller factor and 40.7% density in the larger factor we get following runtimes: | Batch size | Dense runtime | Single sparsity | DSF | |------------|---------------|-----------------|-----| | 64 | 426 | 251 | 276 | | 256 | 1474 | 792 | 929 | > limited practical relevance We found that in almost all scenarios we tested so far (even outside ones mentioned in the paper), DSF is better than regular sparsity and can have surprisingly good results. Let us share a **very preliminary** test we ran a couple of days ago (we are definitely not putting this into current paper). We aggressively pruned Llama3-8B to ~16% density, with the goal that the final result would have 2bits per parameter (8bits would be used for nonzeros and mask will be compressed with something similar to compression in https://proceedings.mlsys.org/paper_files/paper/2024/file/c74b624843218d9b6713fcf299d6d5e4-Paper-Conference.pdf) . We then fine-tuned models for half of a day and measured perplexity. When we compare with results from PV-tuning paper (https://arxiv.org/abs/2405.14852 table 2), we would find following | Method | Perplexity | |-----|-----| | Dense | 5.54 | | QUIP | 76.95 | | Regular sparsity | 16.3 | | DB-LLM | 12.77 | | DSF | 10.3 | | PV-tuning | 6.99 | As you can see, DSF can be almost as good as the best quantization method (and is better than many good quantization methods that use fine-tuning like DB-LLM) while offering the benefits of relatively easy fine-tuning. Also keep in mind, this was just a first very quick experiment with setup like this one.

Authors' response

Thank you for your thoughful review. Here are the responses to your concerns: >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. Yes, SVD comparison is kind of unfair; that's why we compare with it only in the section about the comparison of matrix approximation methods. We are not using FLOPs since FLOPs are in a linear relationship with sparsity in the case of single-layer processing and also when using uniform sparsity over all layers (as is in the case of LLMs). FLOPs do not have a direct relationship with sparsity in the case of nonuniform sparsity in vision models (different layers process different numbers of elements). That's why we use FLOPs in the OBC section. SVD has the obvious benefit of doing just two dense matrix multiplications and thus not having time overhead associated with sparse matrix multiplication. But, our primary baseline is regular pruning, which already has sparse matrix multiplication. We added section 4.4 to discuss the computational concern of DSF and argue that DSF has similar overheads as regular pruning. > 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. The original ADMM paper (https://openreview.net/forum?id=1hcpXd9Jir) shows that ADMM is better than solving this problem via gradient descent and is definitely better than $n$ independent linear regressions. It also shows that it is as fast as SparseGPT. At the end of section 5.1, we mention the pruning time. We added one more experiment to the appendix, showing the relationship between pruning time and model quality. > Could you discuss how this is related to sparse coding? We added this to the related work section. We hope that these answers clarify your concerns.

One more note

One more note: We have moved the whole section about layer-wise error comparison (comparing DSF with magnitude pruning, SVD, ...) to the appendix. Is there anything more we can do to clarify your concerns?