OATS: Outlier-Aware Pruning Through Sparse and Low Rank Decomposition

## Abstract

Abstract The recent paradigm shift to large-scale foundation models has brought about a new era for deep learning that, while has found great success in practice, has also been plagued by prohibitively expensive costs in terms of high memory consumption and compute. To mitigate these issues, there has been a concerted effort in post-hoc neural network pruning techniques that do not require costly retraining. Despite the considerable progress being made, existing methods often exhibit a steady drop in model performance as the compression increases. In this paper, we present a novel approach to compressing large transformers, coined OATS, that utilizes the second moment information in the input embeddings to decompose the model weights into a sum of sparse and low-rank matrices. Without any retraining, OATS achieves state-of-the-art performance when compressing models by up to 60 % percent 60 60\% 60 % on large language models such as Llama-3 and Phi-3 and vision transformers such as ViT and DINOv2 while delivering up to 1.37 × 1.37\times 1.37 × the CPU acceleration versus a model that was comparably pruned.

## 1 Introduction

Large scale transformer-based models have found great success in a number of domains ranging from image classification (Wu et al., ), language modelling (Devlin et al., ), and question answering (Brown et al., ). However, these models contain billions of parameters making them computationally expensive to train and deploy which has lead to an increased demand for resource-saving techniques like model quantization (Dettmers et al., ; Egiazarian et al., ), parameter efficient fine-tuning (Hu et al., ; Zhao et al., ), and, most relevant to this work, neural network pruning (Frantar & Alistarh, ).

Pruning has been a key focus for model compression since the early days of deep networks (Mozer & Smolensky, ; LeCun et al., ; Hassibi & Stork, ). Over the years, various pruning techniques have emerged, introducing sparsity either before training (Lee et al., ; Wang et al., ; Tanaka et al., ; de Jorge et al., ), during training (Zhu & Gupta, ; Evci et al., ), or post-training (Benbaki et al., ). In the context of large foundation models, post-training pruning methods, particularly those requiring minimal (Xia et al., ; Ma et al., ) or no re-training (Frantar & Alistarh, ; Sun et al., ; Ashkboos et al., ; Zhang et al., ) are preferred for their computational efficiency. These techniques, when compressing models by $50\%$, have demonstrated the ability to accelerate end-to-end CPU inference by up to $1.8\times$ (Frantar & Alistarh, ; Yin et al., ) and GPU inference by up to $1.63\times$ using structured N:M sparsity (Mishra et al., ), highlighting their potential in real-world applications.

Despite the significant advancements in pruning techniques, it was recently shown that current methods suffer from a consistent degradation in model performance as compression levels increase (Yin et al., ). Moreover, although structured pruning offers greater potential for acceleration compared to unstructured pruning, it often imposes a much steeper trade-off in terms of model accuracy and effectiveness (Chen et al., ). These challenges underscore the need for more sophisticated pruning strategies to strike a better balance between efficiency and performance.

### 1.1 Contributions

To mitigate these issues, we introduce Outlier-Aware Pruning Through Sparse and Low Rank Decomposition (OATS), a novel retraining-free method for compressing large transformers that utilizes the second moment of the input embeddings to approximate the model’s weight matrices as a sum of a sparse matrix and a low-rank matrix.

We evaluate OATS on recent large language models – Phi-3 (Abdin et al., ) and Llama-3 (Dubey et al., ) – and vision transformers – ViT (Wu et al., ) and DinoV2 (Oquab et al., ) – demonstrating that OATS achieves new state-of-the-art performance across a wide range of commonly employed performance metrics. Furthermore, by combining structured pruning with unstructured pruning, our benchmarks utilizing the Deepsparse Engine by NeuralMagic () reveal that OATS leads to more CPU speed-up across all levels of compression when compared to models that utilize just unstructured pruning.

To facilitate the interpretability of the sparse and low-rank terms found by OATS, we run experiments where we divide the compressed model into two models, a sparse model and a low-rank model, and visualize their respective attention heat maps utilizing attention rollout (Abnar & Zuidema, ). Our visualizations on vision transformers (Wu et al., ) reveal a complementary relationship between the two models, with each focusing on different key areas of the image, effectively segmenting it into distinct regions.

## 2 The OATS Algorithm

The key observation behind the OATS algorithm is that the weight matrices, ${\bm{W}}\in\mathbb{R}^{d_{out}\times d_{in}}$, in a transformer model can be faithfully approximated as a summation of a sparse and low rank matrix by solving the following optimization problem, commonly known as Robust PCA (Chandrasekaran et al., ; Candès et al., ):

$$ $\min_{{\bm{S}},{\bm{L}}\in\mathbb{R}^{d_{out}\times d_{in}}}\|{\bm{W}}-{\bm{S} }-{\bm{L}}\|_{F}^{2}\;\text{ s.t. }\;\text{Rank}({\bm{L}})\leq r,\;\|{\bm{S}} \|_{0}\leq k.$ (1) $$

### 2.1 Alternating Thresholding

To solve Equation 1, OATS leverages the alternating thresholding algorithms proposed by Netrapalli et al. () and Bertsimas et al. () that iteratively alternates between solving for the low-rank term ${\bm{L}}$, through singular-value thresholding, and for the sparse term ${\bm{S}}$, through hard-thresholding. Given a matrix ${\bm{A}}\in\mathbb{R}^{m\times n}$, singular-value thresholding, also known as truncated SVD, is defined as:

$$ $\textsc{TruncatedSVD}({\bm{A}},r)={\bm{U}}_{r}\mathbf{\Sigma}_{r}{\bm{V}}_{r}^ {\top},$ $$

where ${\bm{U}}_{r},\mathbf{\Sigma}_{r},{\bm{V}}_{r}^{\top}$ correspond to the matrices formed by retaining only the top-$r$ singular vectors and singular values from the full SVD of ${\bm{A}}$. Hard-thresholding, which succeeds the singular-value thresholding step, is defined as:

$$ $\textsc{HardThreshold}({\bm{A}},k)={\bm{M}}\odot{\bm{A}},$ $$

Figure: Algorithm 1 AlternatingThreshold

where ${\bm{M}}\in\mathbb{R}^{m\times n}$ is a binary matrix with $k$ non-zero entries coinciding with the $k$ largest entries in magnitude in ${\bm{A}}$. Alternatively, the hard-thresholding can also be performed row-wise rather than layer-wise in which case ${\bm{M}}$ would be a binary matrix with $m\cdot\left\lfloor\frac{k}{m}\right\rfloor$ non-zero entries coinciding with the $\left\lfloor\frac{k}{m}\right\rfloor$ largest entries in magnitude in each row of ${\bm{A}}$.

These steps are summarized in Algorithm 1 on the right. To optimize memory usage, the low-rank term ${\bm{L}}$ is stored as its two low-rank components: ${\bm{U}}_{r}$ and $\mathbf{\Sigma}_{r}{\bm{V}}_{r}^{\top}$.

### 2.2 Incorporating Outlier Information

The alternating thresholding on its own yields suboptimal results because the activations of large-scale transformers exhibit a small number of large-magnitude features and altering these negatively impacts model performance (Kovaleva et al., ; Dettmers et al., ; Sun et al., ). OATS takes inspiration from Wanda (Sun et al., ) and incorporates outlier information through a diagonal scaling matrix ${\bm{D}}\in\mathbb{R}^{d_{in}\times d_{in}}$ that captures the second moment of the input activations

$$ ${\bm{D}}=\text{diag}\left(\sqrt{{\bm{X}}^{\top}{\bm{X}}}\right),$ $$

where ${\bm{X}}\in\mathbb{R}^{B\times d_{in}}$ and $B$ is the product of the batch size and sequence length.
The weight matrix ${\bm{W}}$ is then scaled by ${\bm{D}}$ before applying AlternatingThreshold:

$$ ${\bm{S}},{\bm{L}}=\textsc{AlternatingThreshold}\left({\bm{W}}{\bm{D}},N,r,k \right).$ $$

To undo the scaling, OATS applies the inverse transformation to reach the compressed weight

$$ ${\bm{W}}_{\text{compressed}}=({\bm{S}}+{\bm{L}}){\bm{D}}^{-1},$ $$

where it leverages the fact that ${\bm{D}}$ is diagonal so that it both preserves the sparsity pattern of ${\bm{S}}$ and is easy to invert. Aligned with (Frantar & Alistarh, ; Sun et al., ), and Zhang et al. (), the activations are calculated through a calibration set that is propagated through the compressed layers.

### 2.3 OATS Parameters

To determine the rank $r$ and the number of nonzeros $k$, OATS takes in as input two hyperparameters: the *compression rate*, $\rho\in(0,1)$, and the *rank ratio*, $\kappa\in(0,1)$. The compression rate coincides with the sparsity rate required by existing pruning algorithms and is defined as:

$$ $\rho=1-\frac{\#\text{ of nonzero parameters in compressed layer}}{\#\text{ of parameters in original layer}}=1-\frac{k+r(d_{out}+d_{in})}{d_{out}\cdot d_{in }}.$ $$

The rank ratio represents the proportion of nonzero parameters that appear in the low-rank term:

$$ $\kappa=\frac{r(d_{out}+d_{in})}{(1-\rho)d_{out}\cdot d_{in}}.$ $$

Given a fixed compression rate $\rho$ and rank ratio $\kappa$, the two equations above can be solved to obtain the rank $r$ and nonzeros $k$:

$$ $r=\left\lfloor\kappa\cdot(1-\rho)\cdot\frac{d_{out}\cdot d_{in}}{d_{out}+d_{in }}\right\rfloor\qquad k=\left\lfloor(1-\kappa)\cdot(1-\rho)\cdot d_{out}\cdot d _{in}\right\rfloor.$ (2) $$

The complete OATS algorithm pseudocode can be found in Algorithm 2 below.

Figure: Algorithm 2 OATS

## 3 Experiments on Large Language Models

### 3.1 Experiment Setup

##### Models and Tasks

We evaluate OATS on two state-of-the-art families of large language models: Phi-3 (Abdin et al., ) and Llama-3 (Dubey et al., ). To gauge the algorithm’s performance under various model sizes, we select Phi-3 Mini, a $3.8$B parameter model, Phi-3 Medium, a $14$B parameter model, and Llama-3 8B, an $8$B parameter model, so that models of various sizes are represented in our experiments. We utilize LM Harness developed by Gao et al. () to evaluate zero-shot performance on eight tasks, five-shot performance on the Massive Multitask Language Understanding benchmark by Hendrycks et al. (), and language generation on WikiText-2.

**Table 1: Hyperparameters utilized for OATS across model families. Both parameters are further ablated in Section 3.3.**
| Parameters | Phi-3 | Llama-3 |
| --- | --- | --- |
| Iterations | 80 | 80 |
| Rank Ratio | 25% | 30% |

##### Pruning Benchmarks

As OATS does not require costly retraining after model compression, we opt to benchmark it with three current state-of-the-art algorithms that similarly do not require such overhead: SparseGPT by Frantar & Alistarh (), Wanda by Sun et al. (), and DSNoT(^1^11DSNoT experiments are run with both SparseGPT and Wanda. We report the best results across the two. Further details are in Appendix A.4.) by Zhang et al. (). The parameters utilized for OATS are depicted in Table 1.

##### Calibration Data

Remaining consistent with Frantar & Alistarh (), Sun et al. (), and Zhang et al. (), our calibration data consists of 128 sequences of length 2048 sampled from the first shard of the C4 training set (Raffel et al., ). To ensure consistency, we utilize the same calibration data for all pruning algorithms that we benchmark.

##### Layer-Wise Compression Rates

We benchmark our algorithm across a wide range of compression rates: {0.3, 0.4, 0.5, 0.6}. For compression rates at or below $0.5$, we compress all transformer blocks uniformly. At the higher compression rate of $0.6$, we utilize Outlier Weighed Layerwise Sparsity Ratios (OWL) developed by Yin et al. () which was shown to lead to significant performance improvements at higher compression rates. We exclude pruning any linear layers that are present in the model head and embeddings which conforms with what was done in the prior works by Frantar & Alistarh (), Sun et al. (), and Zhang et al. ().

##### Hardware Speedup

To measure the CPU speedup generated by the unstructured sparsity and low-rank compression of OATS, we utilize the DeepSparse Inference Engine developed by NeuralMagic (). More recently, NVIDIA’s sparse tensor cores are able to leverage for acceleration structured N:M sparsity, a sparsity pattern where every $N$ in $M$ parameters are zero (Mishra et al., ). We include in our experiments the natural extension of OATS to structured N:M sparsity where we impose the structured sparsity pattern onto the sparse term in the decomposition.

### 3.2 Results

##### Five-shot MMLU

Depicted in Table 2 below is the MMLU accuracy of OATS relative to current state of the art pruning algorithms. OATS is able to outperform all prior methods across all compression rates with an increasing gap as the compression rate increases. Specifically, at $50\%$ compression, OATS surpasses previous pruning algorithms by a margin of $2.52\%$ on Phi-3 Medium and $5.42\%$ on Phi-3 Mini.

**Table 2: Comparison of average five-shot accuracies (%) on MMLU under different compression rates.**
| Compression<br>Rate | Method | Phi-3 | Llama-3 8B |  |
| --- | --- | --- | --- | --- |
| Mini | Medium |  |  |  |
| 0% | Dense | 70.34 | 76.78 | 64.97 |
| 30% | SparseGPT | 68.31 | 74.12 | 64.25 |
| Wanda | 67.63 | 75.18 | 63.67 |  |
| DSNoT | 68.02 | 75.13 | 63.72 |  |
|  | OATS | 68.84 | 76.15 | 65.22 |
| 40% | SparseGPT | 63.47 | 72.42 | 60.91 |
| Wanda | 64.15 | 73.34 | 60.33 |  |
| DSNoT | 63.57 | 73.20 | 59.99 |  |
|  | OATS | 65.75 | 74.99 | 62.46 |
| 50% | SparseGPT | 53.22 | 67.63 | 53.60 |
| Wanda | 54.57 | 69.76 | 49.83 |  |
| DSNoT | 54.28 | 68.65 | 49.20 |  |
|  | OATS | 59.99 | 72.28 | 56.46 |

##### Zero-shot Tasks

Table 3 below reports the zero-shot accuracy of OATS relative to current state of the art pruning algorithms averaged across the following eight popular tasks: PIQA (Bisk et al., ); HellaSwag (Zellers et al., ); Winogrande (Sakaguchi et al., ); OpenBookQA (Mihaylov et al., ); RTE (Wang et al., ); BoolQ (Clark et al., ); ARC-e and ARC-c (Clark et al., ). Mirroring the trend observed in the five-shot results, the improvement from OATS compared to prior pruning algorithms increases with compression, culminating in a $2.05\%$ advantage over prior methods at $50\%$ compression for Phi-3 Mini.

**Table 3: Comparison of average zero-shot accuracies (%) under different compression rates. Task-specific scores can be found in Appendix A.1.**
| Compression<br>Rate | Method | Phi-3 | Llama-3 8B |  |
| --- | --- | --- | --- | --- |
| Mini | Medium |  |  |  |
| 0% | Dense | 71.99 | 74.27 | 69.79 |
| 30% | SparseGPT | 70.63 | 74.53 | 69.08 |
| Wanda | 70.66 | 74.05 | 68.63 |  |
| DSNoT | 71.20 | 74.03 | 68.98 |  |
|  | OATS | 71.48 | 74.04 | 69.34 |
| 40% | SparseGPT | 69.18 | 74.40 | 67.58 |
| Wanda | 68.80 | 73.01 | 67.04 |  |
| DSNoT | 69.08 | 72.90 | 66.65 |  |
|  | OATS | 70.04 | 74.46 | 68.68 |
| 50% | SparseGPT | 66.36 | 73.25 | 64.66 |
| Wanda | 65.03 | 70.96 | 63.27 |  |
| DSNoT | 65.33 | 71.12 | 62.74 |  |
|  | OATS | 68.41 | 73.39 | 65.71 |

##### Generation Task

Depicted in Table 4 below is the WikiText-2 perplexity of OATS relative to current state of the art pruning algorithms. At $50\%$ compression, OATS results in an $8.5\%$ reduction in perplexity on the larger Phi-3 Medium model, and an even larger $9\%$ reduction on Phi-3 Mini and Llama-3 8B.

**Table 4: Comparison of perplexity (lower is better) on WikiText-2 under different compression rates.**
| Compression<br>Rate | Method | Phi-3 | Llama-3 8B |  |  |
| --- | --- | --- | --- | --- | --- |
| Mini | Medium |  |  |  |  |
| 0% | Dense | 9.50 | 6.21 | 10.17 |  |
| 30% | SparseGPT | 11.19 | 7.48 | 9.71 |  |
| Wanda | 10.71 | 7.28 | 9.39 |  |  |
| DSNoT | 10.51 | 7.11 | 9.36 |  |  |
| OATS | 10.27 | 6.85 | 9.59 |  |  |
| 40% | SparseGPT | 13.03 | 8.52 | 10.01 |  |
| Wanda | 12.59 | 8.49 | 9.74 |  |  |
| DSNoT | 12.17 | 8.24 | 9.60 |  |  |
| OATS | 11.53 | 7.70 | 9.24 |  |  |
| 50% | SparseGPT | 16.80 | 9.89 | 11.95 |  |
| Wanda | 17.23 | 10.12 | 12.36 |  |  |
| DSNoT | 16.68 | 9.96 | 12.41 |  |  |
| OATS | 15.18 | 9.05 | 10.87 |  |  |

**Table 5: MMLU accuracy ($\%$) of models compressed by $60\%$ using OWL ratios.**
| Method | Phi-3 Mini | Llama-3 8B |
| --- | --- | --- |
| SparseGPT | 46.20 | 39.48 |
| Wanda | 44.22 | 31.20 |
| DSNoT | 44.75 | 33.28 |
| OATS | 52.59 | 44.46 |

##### Performance Under High Compression

Depicted in Table 5 on the right is the 5-shot MMLU accuracy ($\%$) of models compressed to a higher compression rate of $60\%$ utilizing OWL ratios. Following the trend above, we can see that OATS continues to considerably outperform its competitors.

### 3.3 Ablations for OATS

We conduct ablation studies for OATS on Phi-3 Mini at $40\%$ compression rate with a rank ratio of $20\%$ to depict the quantitative impact of the following design choices that were made:

- •
Scaling the weights by the second moment of the input activations, ${\bm{D}}$, versus not scaling.
- •
Pruning the weights per each output row in the matrix versus pruning layer-wise.

The results of our ablations are depicted in Table 6 below:

**Table 6: Ablations of OATS on Phi-3-Mini at $40\%$ compression rate with a rank ratio of $20\%$. The experiments show that scaling the weights by the second moment of the input activations and pruning row-wise significantly improves the performance of OATS.**
| Ablation | MMLU $(\uparrow)$ | Zero-shot $(\uparrow)$ | Perplexity $(\downarrow)$ |  |
| --- | --- | --- | --- | --- |
| No Scaling | Layer-Wise | 62.46 | 67.58 | 19.21 |
| Row-Wise | 65.31 | 68.22 | 18.34 |  |
| Scaling by ${\bm{D}}$ | Layer-Wise | 64.44 | 70.52 | 11.68 |
| Row-Wise | 65.84 | 70.71 | 11.50 |  |

In addition to the ablations, in Figure 1 below, we show how the rank ratio and the number of iterations impact the performance of OATS .

Figure: Figure 1: The effect of varying the rank ratio and number of iterations on zero-shot and five-shot accuracy.

The experiments reveal that the performance under the rank ratio generally saturates between $25\%$ to $30\%$ prior to deteriorating. For the number of iterations, there is a sharp increase in performance from 0 0-$20$ iterations before leveling off and saturating at around $80$ iterations.

### 3.4 Hardware Speedup

##### CPU Speedup

We utilize the DeepSparse engine by NeuralMagic () to measure the CPU acceleration induced by OATS compared to pruned models with unstructured sparsity. We run end-to-end inference on a compressed Phi-3 Medium 15B model for a single batch of 2048 tokens on an Intel Xeon Gold 6148 CPU @ 2.40GHz with 32 cores. The achieved speed-ups are depicted in Table 7 below.

**Table 7: Comparison of throughput and speedup achieved through OATS and unstructured pruning methods relative to their dense counterparts.**
| Compression<br>Rate | Method | Throughput (tokens/sec) | Speedup |
| --- | --- | --- | --- |
|  | Dense | 4.03 | $1.00\times$ |
| 30% | Unstructured Pruning | 4.32 | $1.07\times$ |
| OATS | 5.58 | $\mathbf{1.38\times}$ |  |
| 40% | Unstructured Pruning | 5.08 | $1.26\times$ |
| OATS | 6.86 | $\mathbf{1.73\times}$ |  |
| 50% | Unstructured Pruning | 7.16 | $1.78\times$ |
| OATS | 8.31 | $\mathbf{2.06\times}$ |  |

Our results highlight that by trading unstructured sparsity for structured sparsity through the low-rank terms, OATS leads to significantly more CPU speed-up compared to models that rely solely on unstructured pruning. In particular, at $40\%$ compressed, OATS has $1.37\times$ the speed-up than unstructured pruning.

##### N:M Performance

We benchmark the N:M performance of OATS against the 2:4 structured sparsity performance of current state of the art pruning algorithms. Since the low-rank terms found by OATS remains dense, we opt to impose the *sparser* structured sparsity pattern of 2:8 on the sparse term returned by OATS testing various rank ratios of $0.25$, $0.3$, $0.35$, $0.4$, $0.45$, and $0.5$. In Figure 2 below, we depict the compression ratio versus the 5-shot MMLU accuracy of different compression algorithms.

Figure: Figure 2: Experiments evaluating OATS with 2:8 structured sparsity on the sparse terms against 2:4 sparsity of state-of-the pruning algorithms. The rank ratio for OATS is varied to capture the performance across different compression rates.

Our results show that despite having a much stricter structured sparsity pattern of 2:8, OATS is able to recover the model performance through the presence of its low-rank terms. Specifically, at a fixed compression rate of $50\%$, OATS is able to outperform all prior state-of-the-art by up to $9.2\%$. In the case of Llama-3 8B, OATS surpasses previous methods by $2.86\%$ with $8\%$ more compression.

## 4 Experiments on Vision Transformers

We run experiments on Google’s ViT-Base (Wu et al., ), an $86.6$M parameter model trained in a supervised manner on ImageNet-21k (Ridnik et al., ) and fine-tuned on ImageNet 2012 (Russakovsky et al., ), and DinoV2-Giant (Oquab et al., ), a $1.14$B parameter model that was trained utilizing self-supervised learning.

We benchmark OATS against the same three pruning algorithms: SparseGPT, Wanda, and DSNoT, by evaluating on the validation split of ImageNet (Russakovsky et al., ). A subset of size $2048$ from the training split of ImageNet is utilized for the calibration data and is maintained consistent across all pruning experiments. All OATS experiments utilize a rank ratio of $\kappa=20\%$ and $N=80$ iterations. We exclude from compression the embedding layers and the classifier layer.

Depicted in Table 8 below are the validation accuracies of ImageNet for ViT-Base and DinoV2-Giant under various compression rates.

**Table 8: ImageNet validation accuracy ($\%$).**
| Compression<br>Rate | Method | ViT-Base | DinoV2-Giant |
| --- | --- | --- | --- |
| $0\%$ | Dense | 80.33 | 86.55 |
| 30% | SparseGPT | 80.21 | 86.46 |
| Wanda | 80.28 | 86.47 |  |
| DSNoT | 80.16 | 86.46 |  |
| OATS | 80.15 | 86.52 |  |
| 40% | SparseGPT | 79.58 | 86.39 |
| Wanda | 79.34 | 86.32 |  |
| DSNoT | 79.46 | 86.37 |  |
| OATS | 79.86 | 86.46 |  |
| 50% | SparseGPT | 78.44 | 86.04 |
| Wanda | 76.19 | 85.81 |  |
| DSNoT | 76.90 | 85.93 |  |
| OATS | 78.77 | 86.14 |  |

## 5 Visualizing and Interpreting the Decomposition

To develop a better understanding of how the sparse and low rank components individually contribute to the flow of information through the attention mechanism, we compute and visualize the attention rollout (Abnar & Zuidema, ) of the compressed model when:

- •
All low-rank terms are set to zero and inputs are propagated through only the sparse terms.
- •
All sparse terms are set to zero and inputs are propagated through only the low-rank terms.

Figure 3 below provides a visualization of how the information would flow through a standard transformer block for both settings.

Figure: (a) Sparse Terms Only

We utilize various images in the Microsoft COCO dataset (Lin et al., ) to generate the attention rollout. Figure 4 below depicts the attention rollout computed using the scheme described above on ViT-B that was compressed by $50\%$ with a rank ratio of $20\%$.

Figure: Figure 4: Attention rollout visualization applied to various images on the Microsoft COCO dataset.
Refer to caption: extracted/5866936/vit_viz/og_0.png

The rollout visualizations show that the sparse and low-rank terms capture distinct areas of the image, effectively segmenting it, and reveal three distinct patterns in how the image is partitioned. The first type of behavior, which is also commonly exhibited in the classical setting (Candès et al., ), is when one component (commonly sparse) captures the subject(s), while the other component (commonly low-rank) captures the background. The second behavior occurs when both components focus on different parts of the same subject, capturing distinct features. The third behavior arises when the image contains multiple subjects, with each component isolating a different subject. While these patterns provide initial insights into how the components process visual information, further investigation is needed to fully understand the underlying mechanisms driving these behaviors.

## 6 Related Works

##### Connection with Wanda

OATS utilizes the same outlier scaling as the the one that is employed by Wanda (Sun et al., ). In fact, Wanda can be seen as a special case of OATS when the rank ratio $\kappa=0$, which, according to Equation 2, results in the low-rank term becoming the $\mathbf{0}$ matrix. This leads to OATS performing a singular hard thresholding step that is equivalent to the pruning step described by Wanda and returning a compressed matrix equal to:

$$ ${\bm{W}}_{\text{compressed}}=\textsc{HardThreshold}({\bm{W}}{\bm{D}},k){\bm{D} }^{-1}.$ $$

##### Sparse and Low-Rank Approximation in Transformers

The emergence of sparse and low-rank structures in transformers has recently become an area of both theoretical and practical interest. On the theoretical front, Zhao et al. () showed that the logits of LLMs trained utilizing next token prediction converge to a low rank and sparse structure. On the practical front, Scatterbrain proposed by Chen et al. () shows that its possible to approximate the entire attention mechanism with a single sparse and low rank representation. LoRAP by Li et al. () finds a low-rank representation for the attention matrices by utilizing a similar scaling technique as OATS. Recent works, such as LoSparse (Li et al., ), LoRAPrune (Zhang et al., ), and APT (Zhao et al., ), propose variations of applying structured pruning on the weights while incorporating a low-rank adapter that is trained via gradient descent. We want to highlight that unlike OATS, these works utilize training and low-rank adaptation to recover model performance from structured pruning, whereas OATS depends on an intrinsic sparse and low-rank approximation of the weight matrices.

##### Robust PCA Algorithms

While OATS utilizes an alternating thresholding approach for its efficiency and simplicity, the search for fast Robust PCA algorithms has been a key area of interest since the inception of the problem. An alternative approach is to apply a convex relaxation, replacing the sparsity and low-rank constraints with an $\ell_{1}$ and nuclear norm surrogate leading to Stable Principle Component Pursuit (Zhou et al., ). Another way to enhance computational efficiency is to utilize gradient descent by parameterizing the low-rank matrix as ${\bm{L}}={\bm{U}}{\bm{V}}^{\top}$, and then performing gradient descent on ${\bm{U}}$ and ${\bm{V}}$ (Yi et al., ; Tong et al., ).

##### Pruning and Interpretability

While pruning has been proven to be a successful approach to model compression, there is still ongoing research into what pruning is pruning and how it impacts model performance. Paganini () show that magnitude-based pruning has a disproportionate negative effect on underrepresented classes. In a similar vein, Yin et al. () show that pruning LLMs can lead to irreversible damage to model performance on tasks that are more challenging. We highlight that the low-rank term present in OATS might be able to mitigate the negative impacts of pruning raised by the prior works. Indeed, in Tables 2 and 5, we can see that at higher compression rates, the gap between OATS and prior state-of-the-art is significantly larger suggesting that the low-rank term plays a critical role in mitigating the loss in performance at high compression.

## 7 Conclusion

We have introduced OATS, an algorithm that distinguishes itself from prior algorithms by utilizing outlier information to determine a compressed sparse and low-rank decomposition without any re-training. We run a number of experiments showing that OATS is able to consistently outperform prior state-of-the-art across multiple benchmarks and compression rates while also improving on speed-up. Furthermore, in the search for interpretability, we have generated visualizations highlighting that the sparse and low-rank terms capture different segments of the image. We hope that our work can be utilized to investigate how sparse and low-rank structures in transformers can be fully leveraged for maximal memory and compute efficiency.

## Appendix A Appendix

### A.1 Zero-Shot Task-Specific Performance

Table 9 depicts the task-specific performance for the zero-shot evaluation results presented in Section 3.2 and Appendix A.4.

Table: Table 9: Task-Specific Zero-Shot Results

### A.2 MMLU Subjects

We evaluate on the following MMLU subjects:

- •
Abstract Algebra
- •
Business Ethics
- •
College Computer Science
- •
College Mathematics
- •
Conceptual Physics
- •
Formal Logic
- •
Machine Learning
- •
Miscellaneous
- •
Philosophy
- •
Global Facts

which aligns with the subset utilized in the codebase of Ashkboos et al. () that can be found here: [https://github.com/microsoft/TransformerCompression](https://github.com/microsoft/TransformerCompression).

### A.3 Attention Rollout: Details

To generate the attention rollout visualizations depicted in Section 5, we average the attention matrices across the attention heads and discard the bottom $40\%$ attention pixels. The act of discarding the lowest value attention pixels was inspired by the following blog post by Gil ().

### A.4 Pruning Implementation and Hyperparameters

Our code and pruning method implementations are based on the following codebases:

- •
SliceGPT (Ashkboos et al., ): [https://github.com/microsoft/TransformerCompression](https://github.com/microsoft/TransformerCompression)
- •
SparseGPT (Frantar & Alistarh, ): [https://github.com/IST-DASLab/sparsegpt](https://github.com/IST-DASLab/sparsegpt)
- •
Wanda (Sun et al., ): [https://github.com/locuslab/wanda](https://github.com/locuslab/wanda)
- •
DSNoT (Zhang et al., ): [https://github.com/zyxxmu/DSnoT](https://github.com/zyxxmu/DSnoT)
- •
OWL (Yin et al., ): [https://github.com/luuyin/OWL](https://github.com/luuyin/OWL)

We utilize Huggingface’s Transformers library to implement the large language models and vision transformers for our experiments (Wolf et al., ).

#### A.4.1 SparseGPT Hyperparameters

We utilize a blocksize of 128 across all experiments and a Hessian dampening of $0.01$ and $0.1$ where the ladder is utilized only when faced with non-positive definiteness issues related with the Cholesky decomposition.

#### A.4.2 DSNoT Hyperparameters

We run experiments utilizing DSNoT where the initial masks are generated by SparseGPT and Wanda. All DSNoT experiments were run with $50$ iterations and an update threshold of $0.1$. Depicted in Table 10 below show the results distinguishing between the two initial methods that were utilized.

Table: Table 10: LLM performance metrics of DSNoT with different initial methods.

Table 11 below depicts the analogous results but for our vision transformer experiments:

Table: Table 11: ImageNet Validation Accuracy of DSNoT with different initial methods.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 4
questions: One potential extension of this work could involve incorporating quantization into the proposed framework. Although this addition may be a long shot, integrating quantization could make the model a unified approach to transformer compression. Could the authors provide insights on whether quantization can be integrated with their current framework, or if not, what are the main challenges?
soundness: 3
strengths: - The concept of compressing a model as a sum of a sparse and low-rank matrix is very promising. Unlike most prior methods, which focus on one approach, OATS leverages both to potentially enhance performance.

- OATS is retraining-free, which is crucial for practical applications where even a single backpropagation pass can be computationally prohibitive.

- The framework has been tested on state-of-the-art models like Llama and ViT, demonstrating competitive performance.

- The Alternating Thresholding technique in OATS heuristically finds an effective combination of low-rank and sparse components and accommodates different sparsity patterns.

- By scaling the weight matrix $W$ with a diagonal rescaling matrix $D$, OATS emphasizes outliers, enabling outlier-aware compression that avoids performance degradation.
summary: The paper introduces OATS (Outlier-Aware Pruning Through Sparse and Low-Rank Decomposition), a method designed to compress large transformer models without the need for retraining. The central concept involves representing weight matrices as the sum of a sparse and low-rank matrix.

The authors propose an iterative alternating thresholding technique to compute the joint sparse and low-rank decomposition of a matrix. They also focus on preserving outliers by scaling weights according to input embeddings prior to decomposition. The results indicate that OATS performs effectively on both language and vision tasks, outperforming other pruning methods proposed for transformers across various compression levels and tasks. Additionally, OATS offers speed improvements on the CPU.
weaknesses: One concern is that the method relies on multiple calls to truncated SVD, which can be computationally intensive. Specifically, finding the top-$r$ singular values of an $m \times n$ matrix has a time complexity of $O(mnr)$. Given that compression speed is a significant factor for practical applications, it would be helpful if the authors could clarify the time complexity and wall-clock time spent on the compression process of the overall algorithm. This would offer a more concrete understanding of its practicality.

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 2
questions: See the Weakness. Additionally, why use inverse transformation to reach the compressed weight? What is the actual speedup when using N:M sparsity on GPUs.
soundness: 2
strengths: + Low-rankness plus sparsity is a good fit for compressing LLMs without retraining.
+ By separating the model into a sparse and a low-rank part, the approximation error can be theoretically reduced as the two parts can compensate for each other. 
+ This paper provides measurements for practical speedups on CPUs with existing sparse computation frameworks.
summary: This paper introduces OATS, a novel compression technique for large-scale transformers that combines sparse and low-rank approximations to reduce memory and compute costs without requiring costly retraining. OATS scales model weights by the second moment of input embeddings to preserve essential outlier features in transformers, ensuring model performance is maintained during compression. This approach addresses the typical performance degradation seen with increasing compression in existing pruning methods.
weaknesses: - The novelty is limited. The combination of low-rankness and sparsity is an old topic that has been explored for many years [R1, R2]. Applying the well-established approximation techniques to decompose/compress the large matrices in LLMs has little technical contribution. Besides, compressing DNN models using low-rank and sparse decomposition has already been well explored in [R3]. This paper just scales it to larger models and matrices. Authors are encouraged to specify the unique difference from existing approaches and why this difference is also unique for LLMs.
- The proposed Truncated SVD and Threshold strategies to achieve low-rankness and sparsity are too trivial. It is unknown how to decide the rank and number of zeroes. Besides, the order of applying SVD and thresholding has a significant impact on the approximation errors. Authors are encouraged to clearly explain why using such decomposition strategies.
- This paper claims "outlier information" in this paper. However, I have not seen any analysis or explanation for the "outlier information," and the proposed solution is not related to the "outlier information." Instead, this paper seems to directly apply the pruning approaches proposed in Wanda. The authors are encouraged to provide explanations of why the diagonal matrix is related to "outlier information" and why it is good for compression.
- Many works have been proposed to compress LLMs with low-rankness and sparsity [R4-R6]. The authors have not presented the main differences among them and the unique contributions that stand out from those works.
- Even though theoretical analysis may not have a practical guarantee of accuracy, the authors are encouraged to provide.
- The paper presentation could be improved, especially the math equations. 

[R1] Sparse and Low-Rank Matrix Decompositions, Forty-Seventh Annual Allerton Conference, 2009.

[R2] Godec: Randomized low-rank & sparse matrix decomposition in noisy case. ICML 2011.

[R3] On compressing deep models by low rank and sparse decomposition, CVPR 2017.

[R4] Slope: Double-pruned sparse plus lazy low-rank adapter pretraining of llms

[R5] LoSparse: Structured Compression of Large Language Models based on Low-Rank and Sparse Approximation

[R6] SLiM - One-shot Quantized Sparse Plus Low-rank Approximation of LLMs

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
questions: It would be nice to see a bigger hyperparameter selection section with more architerctures considered.
soundness: 4
strengths: The method proposed by this paper is well-explained and well-justified. The actual practical algorithm is easy to follow. 

Real-time speedup is shown in the CPU setting.

The experiments cover a range of model sizes (3.8-14B parameters). I especially liked seeing results on fairly small models, since those may be harder to compress. 

Section 5 is an interesting way to look at the problem, which I think can lead to interesting further work in the direction of interpretability.
summary: This paper proposes a relatively novel model compression technique aimed at Transformer architectures, in which weight matrices are approximated as a sum of a sparse and a low-rank matrix. To control for the (previously documented) outlier feature problem, weights are also scaled by the second moment of their input.
weaknesses: The choice of the rank ratio parameter could have been better explored (in particular, looking at multiple architectures/tasks). 

Typos:
Line 18: “approximating each weight” -> “approximating each weight matrix”
Line 142: “the activations are calculated through a calibration set that is propagated through the compressed layers” - should be uncompressed?

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: 1. The author has clarified the differences between Wanda and OATS. However, an ablation study would further illustrate the impact of the low-rank term on performance. How much does the low-rank term contribute to the performance boost compared to Wanda alone?
2. The hardware speedup on GPU with N:M sparsity patterns can be shown and discussed in Section3.4.
3. The paper lacks details on how the sparsity pattern is defined for a matrix composed of a sparse matrix S plus a dense matrix LLL, especially within the context of N:M sparsity and structured pruning. Providing more detailed explanations would enhance clarity. 
4. The baseline for models are all originally designed for LLMs. It would be valuable to compare against pruning metrics specifically designed for ViTs. This would present a stronger baseline to effectively showcase the proposed method’s advantages.
5. The motivation behind the choice of outlier information for the sparse term S is not entirely clear. Given that there are various methods for selecting the sparse components, such as using magnitude-based or gradient-based criteria, it would be helpful to know if the authors experimented with these or other selection methods.
6. Given that most pruning studies report results on 70B-parameter models, has the author tested their method on larger language models, such as Llama2-70B or the newer Llama3-70B?
soundness: 3
strengths: 1.This paper propose a novel method for large transformers compression that utilizes the second moment of the input embeddings to approximate the model’s weight matrices as a sum of a sparse matrix and a low-rank matrix.

2.Extensive experiments on recent large language models demonstrate the effectiveness of the proposed method, which also generalizes well to vision Transformers.
summary: In this paper, the author presents a novel approach to compressing large transformers, coined OATS, that utilizes the second moment information in the input embeddings to decompose the model weights into a sum of sparse and low-rank matrices. The author also conducts a lot of experiments showing that OATS is able to consistently outperform prior state-of-the-art across multiple benchmarks and compression rates while also improving on speed-up.
weaknesses: Please see the questions.

Meta-review: **Summary**

The paper presents OATS (Outlier-Aware Pruning Through Sparse and Low-Rank Decomposition), a technique developed to compress large transformer models and reduce memory and compute costs without requiring costly retraining. This method is based on decomposing the weight matrices into a combination of a sparse matrix and a low-rank matrix. OATS enhances model compression by scaling the weights of transformer models according to the second moment of input embeddings, a strategy designed to retain crucial outlier features. This method effectively maintains model performance, addressing the common issue of performance degradation observed with higher compression levels in conventional pruning techniques. The authors demonstrate that OATS effectively compresses transformer models for both language and vision tasks, surpassing the performance of other pruning methods across various tasks and compression levels. Additionally, OATS provides notable speed enhancements when deployed on CPUs.

**Strengths**

The reviewers unanimously highlighted several strengths of the proposed framework:
* OATS eliminates the need for retraining, which is essential for practical scenarios where even a single backpropagation pass can be computationally expensive.
* The method has been evaluated on cutting-edge architectures such as Llama and ViT on a large range of model sizes, solidly demonstrating that it can compete with recent benchmarks in terms of performance.
* The paper includes data on practical speed improvements on CPUs when using current frameworks for sparse computation.

**Weaknesses**

The reviewers brought up several core weaknesses: 
* Some very relevant prior works are missing, some of which are conceptually identical to the proposed work, e.g., Yu et al., "On compressing deep models by low rank and sparse decomposition," CVPR 2017. 
* The choice of rank ratio parameter and why it should be fixed across different layers, as opposed to considering dynamic ranks across different layers, e.g., as done in the concurrent work [1].
* The lack of computational analysis for OATs
* Poor placement of the paper in the landscape of current literature.

[1] "Dynamic Low-Rank Sparse Adaptation for Large Language Models," in Proc. Thirteenth Int. Conf. Learning Representations, 2024, under review. [Online]. Available: https://openreview.net/forum?id=oXh0939Zzq

**Conclusion** 

The majority of the reviewers evaluated this paper positively. However, Reviewer BUra (Rating: 3, Confidence: 5) raised several critical issues about the submitted work, with which I largely agree, particularly the omission of critical prior works that are conceptually similar to the current submission. The authors have addressed most of the concerns raised by Reviewer BUra, which unfortunately, Reviewer BUra did not acknowledge. While I share some of Reviewer BUra's reservations, I believe that in light of the authors' rebuttal, the paper's strengths outweigh its weaknesses. Considering this, I view the paper as marginally above the acceptance threshold and recommend acceptance.

Decision: Accept (Poster)