CAP:  Correlation-Aware Pruning for Highly-Accurate Sparse Vision Models
Authors: Denis Kuznedelev
Eldar Kurtic
Elias Frantar
Dan Alistarh
Venue: NeurIPS 2023 poster (2023)
Keywords: neural network pruning
vision transformer
sparsity
model compression
TL;DR: We have proposed a novel correlation-aware pruner that allows to achieve high sparsity for a new generation of vision models.

Abstract: Driven by significant improvements in architectural design and training pipelines, computer vision
has recently experienced dramatic progress in terms of accuracy on classic benchmarks such as ImageNet. 
These highly-accurate models are challenging to deploy,  as they appear harder to compress using standard techniques such as pruning. 
We address this issue by introducing the Correlation Aware Pruner (CAP), 
a new unstructured pruning framework which significantly pushes the compressibility limits for state-of-the-art architectures.
Our method is based on two technical advancements: a new theoretically-justified pruner, which can handle complex weight correlations accurately and efficiently during the pruning process itself,  and an efficient finetuning procedure for post-compression recovery. 
We validate our approach via extensive experiments on several modern vision models such as Vision Transformers (ViT), 
modern CNNs, and ViT-CNN hybrids, showing for the first time that these can be 
pruned to high sparsity levels (e.g. $\geq 75$%) with low impact on accuracy ($\leq 1$% relative drop). 
Our approach is also compatible with structured pruning and quantization, and can lead to practical speedups of 1.5 to 2.4x without accuracy loss. To further showcase CAP's accuracy and scalability, we use it to show for the first time that extremely-accurate large vision models, trained via self-supervised techniques,  can also be pruned to moderate sparsities, with negligible accuracy loss.

CAP: Correlation-Aware Pruning for Highly -eccur-Accurate Sparse Vision Models
Denis Kuznedelev
Eldar Kurtic
Skoltech & Yandex
IST Austria
Denis Kuzzedeeler@kolltechh.rr
eldar kurticiiit.aeee
Elias Frantar IST Austria
Dan Alistarh
IST Austria & Neural Magic dan. alistarhhistttt...... at
elias wwwntartist.acccoommmm ac
Abstract
Driven by significant improvements in architectural design and training pipelines, computer vision has recently experienced dramatic progress in terms of accuracy on classic benchmarks such as ImageNet. These highly-accurate models are challenging deploy, as they appear harder compress using standard techniques such as pruning. We address this issue by introducing the Correlation Aware Pruner (CAP), new unstructured pruning framework which significantly pushes the compressibility limits for state-of-the-ar architectures. Our method is based on two technical advancements: new theoretically-jue justiffed pruner, which can handle complex weight correlations accurately and efficiently during the pruning process itself, and an efficient finetuning procedure for post-compression recovery. We validate our approach extensive experiments on several modern vision models such as Vision Transformers (ViT), modern CNNs, and ViT-CNN hybrids, showing for the first time that these can be pruned to high sparsity levels (e.g. 2 75%) with low impact on accuracy (< 1% relative drop). Our approach is also compatible with structured pruning and quantization, and can lead to practical speedups of 1.5 to 2.4x without accuracy loss. To further showcase CAP's accuracy and scalability, we use it to show for the first time that extremely-accurate large vision models, trained via self-supervised techniques, can also be pruned to moderate sparsities, with negligible accuracy loss!.
Introduction
Computer vision has seen impressive progress recently via new generation of architectures motivated by the Vision Transformer (ViT) approach [9, 43] and its extensions, e.g. [1, 28, 46), accompanied by more advanced data augmentation and training approaches [43, 48]. Next-generation vision models such as ViT [9, 43] and ConvNext [49, 29] achieve breakthrough performance across vision tasks, despite encoding fewer inductive biases. This comes the of very large computational and parameter budgets, both for training and deployment. Thus, there a clear need to reduce these costs via compression, enabling deployment in essource-constratii settings.
Yet, the general consensus from the literature is that cext-generation models are harder to compress
while preserving accuracy, relative to their classic convolutional counterparts [6, 40, 35. 20]. For example, if current techniques can compress the classic ResNet50 model [18] to 80-90% unstructured sparsity with negligible loss of accuracy [33, 44], the best surrentlyknoww results for similarly- accurate VIT models only reach most 50% sparsity while maintaining dense accuracy [6]. Our investigation of this phenomenon, detailed in the paper, shows that this occurs for two reasons:
'The code is available at https:://gtthii C
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

1. Hardness of Pruning:
As illustrated in Figure 2, existing pruning approaches, based on magnitude [16]. first-order [38] or second-order information [39] drop very significant accuracy per pruning step for next-generation architectures such as ViT and ConvNext.
2. Expensive Recovery: At the same time, recovering accuracy via fine-tuning [15] is itself computationalll--calleennggn as next next-generation architectures are notoriously hard to train and finetune [41, 43].
Therefore, it is natural ask whether this "lack of compressibility" is inherent for next- gext-generation vision models, and whether their increased accuracy comes at the price of higher deployment costs.
Contributions. In this paper, we resolve this question by proposing new highly-accurate correlation- aware pruner (CAP). which shows that high sparsity can be achieved across next-generating archi- tectures such as ViT [9, 43], ConvNext (29, 49], and augmented ResNets [48], and that this can be done in comppttttionall-effeeeee compression such as token dropping and quantization, and can lead to significant inference speedups, at little no accuracy loss.
manner. Furthermore, CAP is compatible with other forms of
Our primary motivation to resolve the hardness of pruning modern, highly-accurate vision models. A key weakness of existing state-of-the-arr approaches [10, 38, 6, 33, 39, 14], is that they do not directly take into account weight correlations: At each pruning step, saliency score is computed per weight, e.g., the magnitude, weights are ranked by this score, and a large subset is chosen to be removed and/or re-introduced. However, this does not take into account the fact that removed weights may themselves be correlated: for example, a pair of linearly-dependent rows in a layer's weight matrix may seem individually easy remove, since they are mutually-redundant,, but removing for
both at a step may lead to a large accuracy drop. This phenomenon is especially Transformer- based architectures, which encode more complex inter-weight correlations, relative to their convolutional counterparts, in which correlations tend to be localized [39].
We circumvent this issue via a novel formulation of the constrained optimization problem correspond- ing to choosing the optimal weights to prune at a step [17], while taking correlations into account. We prove formally that this task can be reduced to finding the set of sparse weights which best preserve the correlation between the dense weights and their gradients, on given set of training samples. This allows us to efficiently solve the "opttial pruning with correlations" problem, via a fast approximate solver for the above constrained optimization problem.
The CAP algorithm outperforms all other known pruners by a considerable margin (see Figure 6). In turn, this precision lends greater flexibility in gradual pruning, and enables us to build a computationally- -efelile-fffiienttt approach to compress next-generation vision models, addressing our second motivating challenge. Specifically, our gradual pruning approach provides simple and general recipe combining data-efficient augmentation and regularization [43, 41] with theoretically-justffeed learning rate rewinding [36. 23], leading to state-of-the-as sparsity- sasilyy----acuurcyy tradc-offs.
For instance, experiments on the standard ImageNet-IK. IK benchmark [37] show for the first time that ViT models can attain high sparsity levels without significant accuracy impact: specifically, we can achieve 75-80% sparsity with relatively minor (< 1%) accuracy loss, and 90% sparsity with moderate loss. turn, this sparsity leads to computational speedups of more than 2x. Our approach extends to aighly-accurate pruning of large ViTs trained by self-super pretraining, but also to other modern models, such as ConvNext [29, 49] or highly- ResNets [48].
In sum, our results show that mext-generatie higuly-accurate vision architectures are still highly- compressible, but may also require next- text-generation pruning approaches.
Related work. Next-generation vision architectures such as Vision Transformers (ViT') [9] and ConvNext [29, 49] have set new accuracy benchmarks, but are known to require careful tuning in terms of both augmentation and training hyper- hyper-paramett parameters. Identifying efficient recipes is an active research topic in itself [43, 41]. We propose simple and general recipes for fine-tuning such models, which should be useful to the community. Several prior works have investigated ViT compression, but focus on structured pruning, such as removing tokens [54, 22, 50, 31, 40, 35, 20]. Our experiments show that structured approaches are orthogonal to CAP, which can be applied in conjunction to structured compression, to obtain further gains.
The only existing prior work on unstructured VIT pruning is SVITE [6], which performed careful customization of the RigL pruning method [10] to the special case of ViT models. We also present
2

---

results relative to other methods, such as tuned magnitude pruning, the best first-order and second- order pruners [39, 38. 14, 23] and AC/DC pruning [33]. (These methods are known to outperform all other prior methods.) CAP improves upon existing methods across almost all benchmarks, by large margins at high sparsity.
Research on accurate pruning using second-orde information was initiated by LeCun et al. [26], and has recently garnered significant attention [8, 45, 39, 52]. This approach can lead to good results for both gradual pruning [39] and one-shot (post-training) compression [12]. Existing such pruners are not correlation-aware, and are outperformed by CAP across all of our experiments.
2 Background and Problem Setup
The pruning problem assumes a fixed model architecture with weights w E Rd (d is the total number of parameters), and aims find configuration of weights with many zeros as possible while preserving the performance of the original dense model. Gradual pruning, e.g. [19], usually starts from an accurate dense model, and progressively removes weights by setting them to zero, followed by fine-tuning phases.
Weight Saliency. The pruning step usually relies on proxies for weight importance, defined according certain criteria. For instance, the weight magnitude is arguably the most popular criterion, e.g. [16, 53, 15]. Specifically, given model w E R. the saliency of each weight is its absolute value (the magnitude) Pj |wy| for j 21.2.... ... d): weights with the smallest scores are pruned away. Gradual magnitude pruning is usually a strong baseline across most models and settings. Many other criteria exist, such as gradient magnitude [10] "rates of change" in the weights [38].
The Optimal Brain Surgeon (OBS). LeCun et al. [26] and Hassibi et al. [17] obtained weight saliency scores by leveraging (approximate) second-order information about the loss, starting from the Taylor approximation of the loss C in the vicinity of the dense model parameters w". Assuming that w is close to the optimum (hence VL((") = 0), one seeks binary mask M (with elements {0, 13) and new values for the remaining weights wMM such that the resulting increase in loss is minimal. A standard approach to approximate the loss increase is to expand the loss function to the second order in model weights:
1 M) - L(w") = = (( - (WW w*)
where Hw(w") is the Hessian of the model at w", and w.M represents weights after the pruning step. In this setup, [26] and [17] showed that the "optimal"" weight to remove, incurring the least loss, and the update to the remaining weights, can be determined via a closed-form solution to the above inverse problem. Specifically, the saliency score Pi for 7th weight and the optimal weight update ów for the remaining weights after elimination of the 7th weight are as follows:
W and
P:
is 8w"
H (w" )e;,
2 H
(w*)
H (w*)
where e; is the 7th basis vector. Theoretically, the procedure would have to be executed one-weight- at-a-time, recomputing the Hessian after each step. In practice, this procedure suffers from a number of practical constraints. The first is that direct Hessian-inverse computation is computationally- infeasible for modern DNNs, due to its quadratic-in-dimenns This has led to significant recent work on efficient second-order approximations for pruning and quantization [8, 45, 52].
storage and computational costs.
WoodFisher and the Optimal BERT Surgeon. The empirical Fisher approximation [2] is a classic way of side-stepping some of the above constraints, and can be formally- as follows:
N Σ
Hc(w") ~ F(w*) Alax +
VL,(W')VLL
(3)
N
where (.w")) E Rdd is gradient computed on sample of data, À > is dampening constant needed for stability, and N is the total number of gradients used for approximation. Note that the resulting matrix is positive definite.
3

---

The memory required to store the empirical Fisher matrix is still quadratic in d, the number of parameters. Singh and Alistarh [39] investigated a diagonal block-wise approximation with predefined block size B. which reduces storage cost from O to O (Bd), and showed that this approach can lead to strong results when pruning CNNs. Kurtic al. [23] proposed a formula for pruning fixed groups/patterns (c.g.. 4 consecutive weights), together with set of non-trivial optimizations to efficiently compute the Fisher block inverses, which allowed them scale the approach for the first time to large language models.
A second obvious limitation of the OBS framework is that applying the procedure and recomputing the Hessian one weight at time is prohibitively expensive, so one usually prunes multiple weights at once. Assuming we are searching for the set of weights Q whose removal would lead to minimal loss increase after pruning, we get the following constrained optimization problem:
min ów F (w")ōw s.t. Eqõw + EQw" = 0, Sw 2
(4)
where Eq E RIQ)xd xd is a matrix of basis vectors for each weight in Q. The corresponding saliency score for the group of weights Q and the update dw of remaining weights are [23]:
1 PQ wQ T (F (F-'(w )1e,))) w and ów =-F- E (F (F"((w")) (ww"))o.))) WQ. (5)
However, an exhaustive search over all subsets of size [Q] from d elements requires (1)) evaluations, which makes it prohibitively expensive for [Q] > 1. For unstructured pruning, virtually all known techniques, e.g. [39, 14), ignore correlations between weights. Similarly, for group pruning, Kurtic et al. [23] ignore correlations between groups. Despite these approximations, both approaches yield state-of-the-art results in their respective setups. As we will demonstrate later, our CAP method improves upon these approximations by reformulating this problem and proposing a correlation-awarc solution that is fast and memory-efficien even for models with 100M parameters.
3 The CAP Pruning Framework
We introduce new techniques to address both the hardness of pruning modern vision architectures, and their high computational cost for fine-tuning: we introduce new state-of-the-art one-shot pruner, which is complemented with a simple and general framework for data-efficient fine-tuning.
3.1 Ingredient 1: Efficient Correlation-Aware Pruning
Our aim is to solve the pruning problem stated in the previous section: given weight pruning target k. find the optimal set of weights Q to be pruned, such that [Q] and the loss increase is minimized. Exactly solving for the optimal Q is an NP-hard problem [3], so we will investigate an iterative greedy method for selecting these weights, similar to the ideal version of the OBS framework discussed above. Importantly, our method properly considers weight correlations, which turn out to be important since, as demonstrated in Appendix Q. the empirical Fisher has an apparent non-diagonal structure, while being.ass fast and space-efficient. In turn, this leads to significant improvements over other pruners, especially in the context of vision transformers.
Formally, a correlation-awee atively, as follows. Given set of already weights Q, initially 0. we always add to Q the weight q which has minimal joint saliency PQU(s). repeating until the size of Q equals the pruning target k. The fact that we add weights to the set one-by-one allows us to take into account correlations between pruned weights. However, naive implementation this scheme, which simply recomputes saliency at each step, would be prohibitively expensive. since it requires (kkd) evaluations of PQ- each of which involves an ((B3) matrix inversion, where B is the Fisher block size.
greedy weight selection approach would perform pruning steps iter-
Disentangling Correlations. The centerpiece of our approach is reformulation of the OBS multi- weight pruning problem in Equation 5 which will allow to take correlations into account, while being practically-efficienn. Specifically, we now show that, when using the empirical Fisher approximation, the problem of finding the optimal set of weights Q to be removed, while taking correlations into account, is equivalent to the problem of finding the set of sparse weights which best preserve the original correlation between the dense weights w and the gradients V (w(")) on an

---

fixed set of samples i E S. Formally, this result, whose proof we provide in Appendix O is stated as follows.
Theorem 3.1. Let S be set with m samples, and let (ww ....., Vm be set of their grudients, with corresponding inverse empirical Fisher matrix F-"(w"). Assume a sparsification larget of k weights from w'. Then, spurse minimizer for the constrained squared error problem
1
m Σ
)
min W/
(6)
2m
s.1. w' has at least k zeros, is also a solution to the problem of minimizing the Fisher-based group-OBS metric
arg min Q 2 w F (F-1(w")QQo))
w
Fast Solver. The formulation in Equation (6) reduces pruning to a sparse regression problem, where the "input" is given by gradients over calibration samples. A related problem arises in the context of one-shot (post-training) pruning [21, 12], where the authors solve sparse lz-fitting problem, but sparse weights are determined relative to the layer inputs rather than the layer gradients. Specifically, the OBC solver [12] utilizes that, due to the quadratic loss, the per-row Hessians are independent of both the weights and each other. Thus the solver processes matrix rows sequentially, greedily eliminating weights, one-by-one, increasing order of squared error while always updating all remaining weights to compensate for weight removal as much as possible. This essentially implements the OBS selection and update in Equation 2 exactly, assuming layer-wise E2 loss. We extend this strategy to efficiently implement our new Fisher-based greedy weight-subset selection.
A direct application of the OBC approach to remove (dd) weights would have ((d)) runtime, where is the layer dimension, as the (dd))-imme selection + update process is repeated ((d) times. By utilizing the block-diagonal structure of the Fisher matrix with block size B during the update after each weight elimination, this complexity can be reduced to O(d max(d, B²)), which however still too slow B is typically much smaller than d. Instead, we proceed differently: we apply the sparse regression solver to each individual Fisher block separately and globally merge results only in the very end. This allows us to efficiently simulate global weight saliency calculation and weight updates following Equations 5 and 7, in block-Fisher formulation. The full algorithm requires Odd B²) runtime and Odd B) space and is detailed in Appendix l-an efficient implementation also provided in the Supplementary
The key difference of our approach relative to WoodFisher is that updates are continuously executed during subset-selection and we are thus explicitly considering the correlations captured by the off- diagonal Fisher elements. When working with small block sizes, our method is very fast and has practically no overhead over existing Fisher-based OBS approaches, while yielding significantly improved one-shot pruming results (see e.g. Figure 2 and the accompanying discussion).
An Faster Variant for Massive Models. In Appendix B, we present a version of CAP which scales efficiently to models with more than I billion parameters, by leveraging additional approximations in the Fisher matrix structure and by relaxing the pruning order.
3.2 Ingredient 2: Fine-tuning and Pruning Procedure
To achieve best performance, modern training procedures involve longer training schedules together with careful choice of hyperparameters, since these are known to have major impact on conver- gence and accuracy [43, 41, 48). We found the same to apply to post-pruning accuracy recovery, which is key in gradual pruning; below, we describe the main ingredients to obtaining accuraee fine-tuning schedules as part of our method.
Learning Rate Schedule. First, achieve good performance during gradual pruning, the learning rate (LR) schedule is crucial. Specifically, we propose to use a cyclic linear schedule:
1%T
(t)) = Mmnax
(7maa
7min)
(8)
T
where For means taking the remainder after integer division by x. We chose a linear decay for simplicity; obtained similar results for other functions (c.g., cubic decay). By contrast, as
5

---

illustrate in Figure 1, the cyclic nature of the schedule is key for accurate pruning, as well as for efficient sparsity sweeps (see below).
Theoretical Justification, Specifically, this choice justified theoretically by tying back to the original assumptions of the OBS framework: for Equation to hold, the pruned model should be well- optimized (i.e. have small gradients) at the point when pruning is performed. Moreover, right after the pruning step, having a larger value of the learning rate is useful since it gives the model a chance to recover from the sub-optimal point induced via pruning. We note that this learning rate schedule different from prior work on pruning, which typically uses a single decay cycle [25, 39, 33], or dynamic learning rate rewinding, e.g. [11, 36].
0.0000
0.8
Relative acc drop (%)
cyclic
cosine
Learning rate
Sparsic
15
0.2
0.0002
0.0001
0.55
5
0.0000
Epoch
Sparsity
0.85
0.77
Figure (left): Blue: Cyclic linear learning rate schedule used in the work. Violet: Dependence of the global model sparsity on the epoch. Every change in sparsity corresponds to pruning step. (right): Relative accuracy drop (i.e difference between validation accuracy before and after pruning update) for training with cyclic and cosine schedule, respectively.
Regularization and Augmentation. For augmentation, similarly to [6]. we adopt known best- practices from the literature: smaller models such DeiT-Tiny benefit from lower levels of data augmentation during fine-tuning as [41], whereas larger models such as DeiT-Base behave best with more complex augmentation and regularization [43]. This is intuitive, since fine-tuning sparsified small models with high augmentation may exceed model capacity, rendering the optimization process unstable. We provide detailed parameter values and ablations in Appendix C.
Augmentation for the Empirical Fisher. The choice of augmentation is of great importance not only for the model training but for the accurate estimate of the Empirical Fisher as well. We observed that without proper augmentation the sparse solution obtained overfits to the training data even when finetuned with the same augmentation and regularization setup. We provide details in Appendix P.
Efficient Sparsity Sweeps. We propose a simple iterative pruning framework, which takes set of target sparsity configurations and produces models which match these configurations in single run. Specifically, we start from standard gradual pruning setup, which prunes in sequence of steps of increasing sparsity, followed by sparse fine-tuning. We then set the intermediate values in such a way that all intermediate target sparsity levels achieved. For example, if one wishes to obtain checkpoints with sparsity levels 40%, 50%, 75%, 90%, one can set the lowest sparsity level on the gradual pruning schedule 40%, the highest sparsity level 90%, and 50%, 75% as intermediate points. Between any two such pruning steps, we apply the cyclic retraining schedule above, which ensures that all intermediate points are sufficiently optimized.
We emphasize that the accurate CAP pruner is key for efficient pruning: virtually all previous high-accuracy pruning methods in this setting, e.g. [25, 39, 6) redo the entire training run for each sparsity target. In our experiments, also examine the impact of additional fine-tuning applied to each checkpoint, and show that induces small-but-consistenn improvements.
Experimental Setup and Results
Setup and Goals. We consider the ImageNet [37] image classification benchmark, and aim to examine how sparsity impacts accuracy for different model variants. We consider three scenarios: one-shot, stepe pruning of a pretrained model, where performance clearly tied to the quality of the second-order approximation, one-shot fine-tuning, in which we follow one-shot pruning

---

by short period of fine-tuning and, finally, iterative gradual pruming, where one applies pruning periodically, with some retraining interval, gradually increasing sparsity.
4.1 One-shot pruning, without and with fine-tuning
We start by examining the quality of existing one-shot pruners relative to CAP. We compare against carefully-tuner variants of Magnitude Pruning (Magn), First-Order Gradient times Weight (GrW) [38], and the SOTA second-order methods WoodFisher [39, 23] and M-FAC [14]. Our tuning process, optimal hyper-pane parameter choices, and ablations are detailed in Appendices and K. WF-1 represents the diagonal approximation of the Hessian proposed by the original OBD [26], scaled via the WoodFisher implementation. For Magnitude and CAP we present results for both uniform layer-wise sparsity and global sparsity. For all other methods, we present results for global sparsity, which yields better results, as the methods can adjust sparsity globally. We only investigate global sparsity for the other methods in Figure 2.
DelT-Tiny
50% sparsity
0.7
Dense WF CAP
Val accuracy
0.5
1.45
4044
-+-
Magn (U)
Magn (G)
0.3
1.40
GrW
WP-1 (G)
0.2
1.35
M-PAC (G)
WF (G)
CAP (U)
0.0
0.7
Sparsity
Figure 2: One-shot pruning for DeiT-Tiny.
Figure 3: Validation loss surface.
The full comparison is presented in Figure 2 for DeiT-Tiny. Notice that all first and second-order methods outperform Magnitude, and that all 2nd-order methods better than the 1st order saliency. WoodFisher with small block size is better than both the diagonal approximation and large-block M-FAC. This suggests that is beneficial take weight correlations into account, but attempting incorporate dependencies between large groups weights may lead to noisy estimates detrimental to performance. We also present comparison other models (VIT and ResNet) in Appendix E.
CAP outperforms all other methods, by large margin. Remarkably, the gap so large that CAP with uniform sparsity still outperforms WoodFisher with global sparsity, which can re-distribute sparsity across layers. The computational cost of WF is approximately the same as for CAP: CAP pruning step on DeiT-Small takes 23 minutes, compared to 20 minutes for WF. (The majority of the cost for both methods comes from the collection of gradients, not Hessian estimation.)
To investigate the performance difference between CAP and WF, we pruned several variants ViT models to 50% and compared the mask overlap between WF and CAP via their IoU (intersection over union). observe that the sparsification masks differ significantly: the loU between the WF and CAP mask is 82.7%. 80.5%, 73.3% for DeiT-Tiny, DeiT-Small, and DeīT-Base, respectively, suggesting that the weight correlations taken into account by CAP lead significantly different pruning decisions. The same trend is visible in the validation loss surface, projected on the plane in weight space, for the dense model and the 50% sparse models via WF and CAP. (We adopt the approach from [32] for loss surface visualization. Specifically, the unit vector in the horizontal direction is chosen to be WWF w" and the vertical direction is defined by the component of WCAP - w* orthogonal to the horizontal axis. Above w", WWF. F, WCAP are the weights of the dense model and sparse solutions found by WF and CAP, respectively.) Figure shows that CAP chooses significantly less steep direction in the loss basin compared to WF.
Compressing highly-accurate models. Modern pretraining methods [7, 5, 34, 51] in conjunction with large vision backbones achieve extremely high accuracy standard benchmarks such as ImageNet- IK. We leverage the scalability and accuracy of CAP to investigate, for the first time, sparsity in such highly-accurate accurate models, in the absence of finetuning, Specifically, start from the
7

---

ConyNext--arge checkpoint pretrained via CLIP on the LAION-2B dataset and finetuned sequentially on ImageNet-21k and ImageNet- Ik [47].
Table 1: Accuracies of CLIP- ELIP-pretraines ConvNext-L on ImageNet- 1k, following one-shot pruning.
Model
Method
Spansity (8)
Topl-Accurayy (%)
Donse
87.8
GM
80.2
WF
50
86.6
CAP
87.5
GM
38.7
ConvNoxt-L
85.1
CAP
87.1
GM
0.5
WF
70
73.7
CAP
86.8
In Table compare our method with WoodFisher (WF) and Global Magnitude (GM) for one- shot pruning via several sparsity targets. Results show that 1) CAP can induce 50% sparsity with relatively low (0.3%) accuracy loss, and 60% with less than 1% accuracy drop; CAP significantly outperforms other methods. In addition, we find that these results can be improved with a limited amount of fine-tuning; please see Appendix E for full results.
4.2 Gradual Pruning Results
Finally, we execute gradual pruning with the sparsity schedule, augmentation choices, and cyclic linear learming-rati rate scheduler discussed above. The whole gradual pruning procedure lasts for 300 epochs, as in [43]. We aim to obtain accurate sparse checkpoints for 50%, 60%. 75%, 80%, and 90% sparsity. For this, we prune to 40% in the initial step, and increment sparsity every 20 epochs, until reaching 90%, with fine-tuning in between. (See Appendix for full results and ablations.) We select the accuracy of intermediate models which match the target sparsities; to examine the impact of fine-tuning, trained each of the resulting sparse checkpoints for additional 100 epochs, marked with (f). We compare with global magnitude (GM) following the same schedule as CAP, as well as the state-of-the-ee ofrtt-rrrttttt SVTTE [6] paper, which trains the sparse model from seratch using variant of RigL [10]. but for a total of 600 epochs. The results are in Table 2.
Table 2: Results for gradual pruming of DeiT-Tiny and Small models on ImageNet- Ik. CAP achieves 50% sparsity without accuracy loss, and 80% sparsity with less than 1% relative error.
Model
Method
Spusity (%)
Reduction (96)
FLOP
Topl Accuracy (96)
Model
Method
Sponity (%)
FLOP Reduction (16
Accurayy (%)
Top1
Dense
0
0
72.2
Dense
79.8
GM
43.9
73.5
GM
46.7
79.3 (79.8 (2 79.7
CAP
50
43.9
73.7
50
SVITE: Tiny
43.9
69.6
SVITE-Small
46.3
DaiT-Tiny
CAP
GM
52.6
52.6
73.3
73.1 (73.2 11)
SVITE-Smal
CAP
$6.2
19.3 (79.8
f2
CAP
GM
65.8
(71. 11)
(7.36
DeiT-
CAP
GM
20.1
70.2
78.0 (78.7 t1)
78.5 (79.0
SVITE-Tay Tln
SVITE SViTE-Small
70.3
77.0
GM
69.7
(70.9 1)
GM
74.2
27.3 (27.9
CAP
71.7 (72.0 11)
CAP
74.9
78.0 (78.6
GM
79.0
66.2 (56.6 1)
GM
$4.0
74. (74.7
F3
CAP
79.0
(68.0 1)
90
SVITE-Tiny
79.0
40.7
SVITE-Small
For DeiT-Tiny and 50% sparsity, we achieve significant improvements upon SViTe, and even manage to improve test accuracy relative to the dense model. We believe this is due to the choice of augmentation during fine-tuning, and possibly due to regularizing effects of sparsity. At 75-80%, we recover the dense model accuracy. We observe significant accuracy drop only at 90%. GM pruning also benefits from the choices made in our schedule, outperforming SVITE at 50% sparsity; yet, there are significant gaps in favor of CAP higher sparsities, expected.
On the 4x larger Small model, SVITE performs remarkably well at 50% sparsity (79.7%). almost matching the dense model, but CAP outperforms it slightly after fine-tuning (79.9%). In terms
8

---

of total training budget, SVITE uses 600 epochs to produce each model (and so, the 50%ssparse one as well). whereas we use total of 40 epochs for gradual pruming to 50% initial fine-tuning, and 100 additional epochs for sparse model fine-tuning, Even if we take into account the original 300 epochs for training the publicly-availabee
dense DeiT checkpoint [43]. our approach significantly more efficient (440 vs. 600 epochs). The cost savings compound across sparse models, since we obtain all our pruned models from the same end-to-end gradual run. At 75% sparsity, CAP drops ~ 1% of accuracy relative to dense post-finetuning, with a significant gap of 1% Top-1 relative to GM, and 2% Top-1 relative to SVITE. The trend continues for higher sparsities, where note remarkable gap of 5.7% Top-1 vs SViTE at 90% sparsity. We obtain similar numbers for DeiT--Bse in Table 3; generally, we achieve 2 99% recovery at 2 75% sparsity, showing for the first time that ViT models can be pruned to such sparsities with marginal accuracy loss.
FLOP Reducction (%)
Topl Accuracy (%)
Model
Method
Sparsity (9))
Dense
0
81.8
Val accurroi
CAP
48.5
81.6
SVITE-Rase
50
48.0
81.5
DelT-B (SVITE)
DeiT-Be Base
SWITE-Rase
CAP
60
57.5
58.2
81.5
81.3
DefT-B (CAP)
DalT-S (SVITE)
DefT-S (CAP)
75
77.7
72.8
81.1 (81.2
(81.
DeiT-T (SVITE)
90
87.4
79.7 (80.1 T>
DaiT-T (CAP)
50
393
209
250
Throughput (img/s)
Table 3: Accuracy results for gradual pruning of DeiT-Base model on ImageNet-Ik.
Figure 4: Accuracy vs. real-time throughput for dense (+) and sparse ViT-models.
Sparse Speedups. The results in Figure 4 examined the speedups obtained by CAP from unstructured sparsity for (50%, 75%, 90%) -sparee ViT-family (base, small, tiny) models, when executed sparsity-aware CPU inference engine [24]. Specifically, we executed the models from Table 2 using 4 cores of Intel(R) Xeon(R) Gold 6238R CPU, batch size 64. We find it interesting that sparse ViTs build an almost-contiguous Pareto frontier from 82% to 68% Top-I accuracy (Y axis), with a 25x span in throughput (from 11 imgs/second to 260 imgs/second, X axis). Notably, the DeiT-Tiny model obtains a speedup of 2.4x without any accuracy loss, while Base and Small ViTs show 1.5x speedups with minimal loss of accuracy. Thus, these results show that unstructured sparsity can be very promising approach to speeding up ViTs. We note that competing methods (e.g. SViTE) would provide similar speedups at the same sparsity levels, but significantly lower accuracy, as shown in the figure, as well as in Table 2.
Additional Results and Details. Due to space constraints, full ablations and several additional experiments have been deferred to the Appendix. We present the full pseudocode for CAP in Appendix A, and faster approximate version of CAP in Appendix B. We describe all parameters and perform additional ablations in Appendices and J. We present results for one-shot pruning across several other models, as well as with short amounts of fine-tuning, in Appendix E. We present gradual pruning results for several other vision models (EfficientFormer,, ResNet50D, and EfficientNetV2) in Appendix F and demonstrate that one can compress them to high sparsity as well, using our approach. Appendix H we show that CAP comes with little additional computational cost compared to WoodFisher [23]. In Appendix we show that CAP can also be applied in conjunction with other types of compression, and remi-structured (2:4) sparsity. In Appendix M, we show that CAP also outperforms AC/DC pruning [33], whereas Appendix N contains results for the DeTR detection model. In Appendix G we study the scaling behavior of sparsity solvers with respect to the ConvNext2 model family.
particular token pruning [35], quantization-awwe aware training.
5 Discussion
We presented new correlation pruner called CAP, which sets new oftt--of-the-at sparsity- accuracy trade-off. We have shown for the first time that ViT variants can support significant weight pruning (2 75%) at relatively minor accuracy loss (< 1%), inducing compression trade-offs that highly models can also support sparsity
similar to those of CNNs, and that CLIP-pretraing accurately. Thus, despite weaker inductive biases, next-generation vision models do not require over prerpearamttiiiationn and can be competitive with CNNs in terms of accuracy accuracy-per-parran www--peee--pppteee Our approach is complementary to other compression approaches, leading to significant speedups.

---

6 Acknowledgements
This project has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement No 805223 ScaleML.). The authors would also like to acknowledge computational support from the ISTA IT department, in particular Stefano Elefante, Andrei Hornoiu, and Alois Schloegl, as well as Amazon EC2 for research credits. D.K. was supported by Russian Science Foundation, grant 21-11-00373.
References
[1] Alaacldin Ali, Hugo Touvron, Mathilde Caron, Piotr Bojanowski, Matthijs Douze, Armand Joulin, Ivan Laptev, Natalia Neverova, Gabriel Synnaeve, Jakob Verbeek, et al. Xcit: Cross- covariance image transformers. Advances in neural information processing systems, 34, 2021.
[2] Shun-Ichi Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):251-
276, 1998.
[3] Thomas Blumensath and Mike E Davies. Iterative thresholding for sparse approximations. Journal of Fourier Analysis and Applications, 14(5-6):629-644, 2008
[4] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In European conference on computer vision, pages 213-229. Springer, 2020.
[5] Mathilde Caron, Hugo Touvron. Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin. Emerging properties self-supervised vision transformers, 2021.
[6] Tianlong Chen, Yu Cheng, Zhe Gan, Lu Yuan, Lei Zhang, and Zhangyang Wang. Chasing sparsity in vision transformers: An end-to-end exploration. Advances in Neural Information Processing Systems, 14:1994--19988, 2021.
[7] Ting Chen, Simon Korbblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations, 2020.
[8] Xin Dong, Shangyu Chen, and Sinno Jialin Pan. Learning prune deep neural networks via layer-wise optimal brain surgeon. In Conference on Neural Information Processing Systems (NeurlPS), 2017.
[9] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale, 2020.
[10] Utku Evci, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pages PMLR, 2020.
[11] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Stabilizing the lottery ticket hypothesis. arXiv preprint arXiv: 000.:0113...11,.. 2019.
[12] Elias Frantar and Dan Alistarh. Optimal Brain Compression: A framework for accurate post-training quantization and pruning. arXiv preprint arXiv:2208. 7 1580, 2022.
[13] Elias Frantar and Dan Alistarh. Sparsegpt: Massive language models can be accurately pruned in one-shot, 2023.
[14] Elias Frantar, Eldar Kurtie, and Dan Alistarh. M-fac: Efficient matrix-free approximations of second-order information. Advances Neural Information Processing Systems, 34, 2021.
[15] Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv: 1902:v:902.095777 09574, 2019.
[16] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural net- works with pruning, trained quantization and huffman coding. arXiv preprint 4rXiv:1510.00149, 2015.
10

---

[17] Babak Hassibi, David G Stork, and Gregory J Wolff. Optimal brain surgeon and general network pruning. In IEEE international conference on neural networks, pages 293-299. IEEE, 1993.
[18] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[19] Torsten Hoefler, Dan Alistarh, Tal Ben-Nun, Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. Journal of Machine Learning Research, 22(241):1-124, 2021.
[20] Zejiang Hou and Yuan Kung. Multi-dimensional model compression of vision transformer. In 2022 IEEE International Conference on Multimedia and Expo (ICME), pages 01-06. IEEE, 2022.
[21] Itay Hubara, Brian Chmiel, Moshe Island, Ron Banner, Joseph Naor, and Daniel Soudry. Accelerated sparse neural training: A provable and efficient method to find n: m transposable masks. Advances in Neural Information Processing Systems, 34:21099-21111, 2021.
[22] Sehoon Kim, Sheng Shen, David Thorsley, Amir Gholami, Woosuk Kwon, Joseph Hassoun, and Kurt Keutzer. Learned token pruning for transformers, 2021.
[23] Eldar Kurtic, Daniel Campos, Tuan Nguyen, Elias Frantar, Mark Kurtz, Benjamin Fineran, Michael Goin, and Dan Alistarh. The optimal bert surgeon: Scalable and accurate second-order pruning for large language models. arXiv preprint arXiv:2203.07259, 2022.
[24] Mark Kurtz, Justin Kopinsky, Rati Gelashvili, Alexander Matveev, John Carr, Michael Goin, William Leiserson, Sage Moore, Bill Nell, Nir Shavit, and Dan Alistarh. Inducing and exploiting activation sparsity for fast inference on deep neural networks. In Hal Daumé IIII and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 5543, Virtual, 13-18 Jul 2020. PMLR.
[25] Aditya Kusupati, Vivek Ramanujan, Raghav Somani, Mitchell Wortsman, Prateek Jain, Sham Kakade, and Ali Farhadi. Soft threshold weight reparameterization for learnable sparsity. In International Conference on Machine Learning, pages
PMLR, 2020.
[26] Yann LeCun, John Denker, and Sara Solla. Optimal brain damage. Advances in neural information processing systems, 2, 1989.
[27] Yanyu Li, Geng Yuan, Yang Wen, Eric Hu, Georgios Evangelidis, Sergey Tulyakov, Yanzhi Wang, and Jian Ren. Efficientformer: Vision transformers at mobilenet speed. arXiv preprint arXiv:2206.01191, 2022.
[28] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hierarchical vision transformer using shifted windows. In Proceedings of the IEEE/CVF Internutional Conference on Computer Vision, pages 10012-10022, 2021.
[29] Zhuang Liu, Hanzi Mao, Chao-Yuaa Wu, Christoph Feichtenhofer, Trevor Darrell, and Saining Xie. A convnet for the 2020s. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 11976-1 1986, 2022.
[30] Asit Mishra, Jorge Albericio Latorre, Jeff Pool, Darko Stosic, Dusan Stosic, Ganesh Venkatesh, Chong Yu, and Paulius Micikevicius. Accelerating sparse deep neural networks, 2021.
[31] Bowen Pan, Rameswar Panda, Yifan Jiang. Zhangyang Wang, Rogerio Feris, and Aude Oliva. la-red 2; Interpretability-wwe aware redundancy reduction for vision transformers. Advances in Neural Information Processing Systems, 34:24898-2499 2021.
[32] Mansheej Paul, Feng Chen, Brett W. Larsen, Jonathan Frankle, Surya Ganguli, and Gintare Karolina Dziugaite. Unmasking the lottery ticket hypothesis: What's encoded in a winning ticket's 's mask? In The Eleventh International Conference on Learning Representa- tions, 2023.

---

[33] Alexandra Peste, Eugenia Iofnova, Adrian Vladu, and Dan Alistarh. Ac/de: Alternating compresseddddcooppessed training of deep neural networks, Advances in Neural Information Processing Systems, 34:8557-85777 2021.
[34] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agar- wal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.
Learning transferable visual models from natural language supervision, 2021.
[35] Yongming Rao, Wenliang Zhao, Benlin Liu, Jiwen Lu, Jie Zhou, and Cho-Jui Hsieh. Dynamievit: Efficient vision transformers with dynamic token sparsification. Advances in neural information processing systems, 34: 13937-13949, 2021.
[36] Alex Renda, Jonathan Frankle, and Michael Carbin. Comparing rewinding and fine-tuning in (00.a02228882002 neural network pruning. arXiv preprint arXiv:2033.23889 2020.
[37] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, Alexander C. Berg, and Li Fei-Fei. ImageNet Large Scale Visual Recognition Challenge. International Journal of Computer Vision (IJCV), 115(3):211225) 2015.
[38] Victor Sanh, Thomas Wolf, and Alexander Rush. Movement pruning: Adaptive sparsity by fine-tuning. Advances in Neural Information Processing Systems, 13:20378-20382 2020.
[39] Sidak Pal Singh and Dan Alistarh. Woodfisher: Efficient second-order approximation for neural network compression. Advances in Neural Information Processing Systems, 33:18098-18109, 2020.
[40] Zhuoran Song, Yihong Xu, Zhezhi He, Li Jiang, Naifeng Jing, and Xiaoyao Liang. Cp-vit: Cascade vision transformer pruning via progressive sparsity prediction, 2022.
[41] Andreas Steiner, Alexander Kolesnikov, Xiaohua Zhai, Ross Wightman, Jakob Uszkoreit, and Lucas Beyer. How to train your vit? data, augmentation, and regularization in vision transformers, 2021.
[42] Mingxing Tan and Quoc Le. Efficientnetv2: Smaller models and faster training. In International Conference on Machine Learning, pages 10096-10106. PMLR, 2021.
[43] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In International Conference on Machine Learning, pages 10347-10357. PMLR, 2021.
[44] Antoine Vanderschueren and Christophe De Vleeschouwer. Are straight-through gradients and soft tofttthresholding all you need for sparse training? Proceedings of the IEEE/CVE Winter Conference on Applications of Computer Vision, pages 3808-3811 2023.
[45] Chaoqi Wang. Roger Grosse, Sanja Fidler, and Guodong Zhang, Eigendamage: Structured pruning in the pooneccer-factoreee eigenbasis. In International Conference on Machine Learning, pages
PMLR, 2019.
[46] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pyramid vision transformer: A versatile backbone for dense prediction without convolutions. Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 568-574 2021
[47] Ross Wightman. Pytorch image models. models, 2019.
httte:://giituub..o//rriggggg
pytorch- image-models,
[48] Ross Wightman, Hugo Touvron, and Hervé Jégou. Resnet strikes back: An improved training 2021.
procedure in timm. arXiv preprint
[49] Sanghyun Woo, Shoubhik Debnath, Ronghang Hu, Xinlei Chen, Zhuang Liu, In So Kweon, and Saining Xie. Convnext v2: Co-designing and scaling convnets with masked autoencoders, 2023.
12

---

[50] Yifan Xu, Zhijie Zhang, Mengdan Zhang, Kekai Sheng. Ke Li. Weiming Dong, Liqing Zhang, Changsheng Xu, and Xing Sun. Evo-vit: Slow-fast token evolution for dynamic vision trans- former, 2021.
[51] Jiahui Yu, Zirui Wang, Vijay Vasudevan, Legg Yeung, Mojtaba Seyedhosseini, and Yonghui Wu. Coca: Contrastive captioners are image-text foundation models, 2022.
[52] Shixing Yu, Zhewei Yao, Amir Gholami, Zhen Dong, Sehoon Kim, Michael W Mahoney, and Kurt Keutzer. Hessian-aware pruning and optimal neural implant. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 3880-3891, 2022.
[53] Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint arXiv:1710.01878, 2017.
[54] Mingjian Zhu, Yehui Tang, and Kai Han. Vision transformer pruning, 2021.
13

---

A CAP algorithm description
The section below illustrates the CAP pruning algorithm step-by-step. Prunable model weights IRd partitioned into blocks of fixed size B. Below pj inside block it belongs to and Pj is the score across the whole model. The steps of the algorithm are listed below:
(B) denotes the saliency scores for weight 7th
Algorithm CAP pruning algorithm
1: P; saliency scores for weights
2: Accumulate Fisher inverse blocks F
3: for each block do
4: err =0
5: for element in a block do
6: Select the weight w; with smallest score p3 (using the (2) for Ps)
7: Prune wi
8:
Update remaining weights in the block via (2)
9:
err+ = p
10:
P: 4 err
11: Save current state of the block for later merging
12: Update Fisher inverse block
13: end for
14: end for
15: Sort the scores P; in ascending order
16: Mark the weights with smallest scores p; as pruned
17: for each block do
18: Load the saved state the block with the weights marked pruned and remaining alive.
19: end for
B FastCAP: A faster version of the algorithm
CAP can scale models with < IB parameters, covering most standard vision models. Its key computational and memory cost comes because of computing and maintaining the inverse Fisher approximation, similarly WoodFisher/Optimal BERT Surgeon.
To address the scalability issue present much more scalable approximate variant of CAP, called FastCAP, which inspired by the recent SparseGPT scalable pruner [13]. Specifically, FastCAP reduces compute and memory cost by 100x by leveraging a cheaper Fisher approximation and relaxing the optimal greedy order of pruning. FasICAP can be scaled billion-parameter vision models, i.e. we can prune ViT-Giant in a few minutes, while achieving reasonable performance in shot-setting for 50-70% sparsity.
The main components of the CAP/FastCAP algorithm are:
Empirical Fisher estimate. The original CAP has specific Fisher block for each output channel, whereas the FasICAP version averages blocks across the output channel dimension. This a further approximation, but significantly reduces storage complexity.
Weight elimination and update iteration. the original CAP eliminates weights in greedy optimal order, FasCCAP prunes weights in fixed order, similar to SparseGPT [13]. This reduces computational complexity.
The full pseudocode for FastCAP is provided in Algorithm 2. The same procedure is applied for all weights. We use the following notation:
B Fisher block size
b block size in iterative pruning algorithm
. . number of gradients
NB number blocks per parameter
The Fisher matrix is the same for all blocks, reducing space complexity O(B²). We adapted the trick of maintaining the Fisher inverse in Cholesky form from SparseGPT [13], to account for iterative climination of the weights in a fixed order. This allows running the iterative process efficiently.
14

---

Algorithm 2 Fast CAP pruning algorithm
1: 1. Fisher accumulation
2: F <- matrix with zeros with shape (B, B)
3: for i= I:N do do
4: reshape V W to (Nn, B)
5: == N V
6: end for
7: 2. Iterative pruning
8: M <- INnXB // binary pruning mask
9: E <- XN // block pruning enrors
F &- ( efficient form of the Fisher inverse
11: for = =0, b, 26, ... do
M.) f- mask of p)% weights wk in W W.)+++)) with largest w [F -P:x for ...., ++0
13:
do B.j-i < FF // pruning error
14:
15:
E.j-i < (1 M.j) Ras- freeze weights
16:
W W.J:(++b) W (.(++b)) E..j- ())+BB----)- // update remaining weights correct output
17:
end for
18:
end for
19: W + W. MMMM/ set pruned weights to 0
To validate performance of FasICAP applied it for pruning of large VIT models in one-shot setting, specifically model has >IB parameters. We compared the top-1 accuracy ImageNet of FastCAP Magnitude pruner. One can see that FastCAP significantly outperforms the baseline. At the same time, Fas(CAP has reasonable runtime and memory footprint at this scale. The pruning step for the whole model takes 400 seconds on a single A A100 GPU.
fnnk from the TIMM library [48]. This
Table 4: Performance of large ViT after one-shot pruning.
Model
Sparsity
Method
Accuracy (%)
0
88.7
Magnitude
87.9
50
FastCAP
EVA VIT-G
Magnitude
855.5
FastCAP
86.3
Magnitude
64.3
70
FastCAP
76.1
C Training details
aiggmentatoonrrggaaaiizzaiooo recipe
For the gradual pruming experiments (with 300 epochs) we have used cyclic learning schedule, with high learning rate directly after the pruning step with gradual decrease up to the next pruning step. For both DeiT-Tiny and DeiT-Small model during the additional fine-tuning for 100 epochs ve applied cosine annealing schedule with 7max = 5 10 Mwin the same as in the Table 6.
1- 10 - and all other parameters
D Post-Pruning Recovery
The choice of augmentation parameters and learning rate schedule is critical for high performance. For example, reducing the level of augmentation during fine-tuning for smaller models. e.g. DeiT-Tiny, significant improves performance, whereas larger models, e.g. the 4x larger DeiT-Small, requires strong augmentations for best results even during fine-tuning, See Figure 5 for an illustration; the augmentation procedure is described in detail in C.
15

---

Table Summary of the augmentation and regularization procedures used in the work.
Procedure
DeiT
lightl
Weight decay
0.05
0.03
Label smoothing &
0.1
0.1
Dropout
X
X
Stoch.Depth
0.1
0.0
Gradient Clip.
X
1.0
H.flip
RRC
Rand Augment
9/0.5
2/0.5
Mixup alpha
0.8
0.0
Cutmix alpha
1.0
0.0
Frasing prob.
0.25
0.0
Brasing count
Test crop ratio
0.9
0.9
Table 6: Hyperparameters of the schedules used in gradual pruning.
Model
Prune freq
LR sched [fdecay. Thuxx: Tminn
Augm
Batch size
Epochs
DeiT-Tiny
20
{cyclic_linear, 5 10-4, 1- 10-5)
lightl deit
1024
300
DeiT-Small
20
[cyclic_linear, 5 10-1, 1,,11 1. 10-5)
1024
300
Moreover, the choice of cyclic learning rate (LR) schedule is critical as well. To illustrate this, compare convergence obtained when using a cosine annealing schedule, which very popular for pruning CNNs [25, 39, 33], from Thmar = 5 10-1 to 1)min = 10-5, while performing pruning updates 2 times more frequently (one update per 10 epochs) than our standard setup from the following section 4.2. The results are provided in Figure 5, where cosine annealing (no cycles) is in red. All experiments use the CAP pruner, and highlight the importance of the learning rate and augmentation schedules for recovery.
DaiT-Tiny
DelT-Small
light1
deit
Via Somm
mm 10)
laghtt
delt
Epoch
Epoch
Figure 5: Ablations of the training setting on DeiT-Tiny (up) and DeiT-Small (down). Green curves correspond to the light! [41] augmentation recipe, blue curves to the deir [43] recipe. The red curve follows training with a single (acyelic) cosine annealing schedule, as in [25, 39].
E
Additional Results for One-Shot Pruning
In this section present comparison of Global Magnitude (GM), WoodFisher (WF) and Correlation Aware (CAP) pruners in one-shot pruning setting for DeiT models [43] of different size (i.c DeiT-Tiny, DeiT-Small, DeiT)Basc) to study the scaling behavior of VIT sparsification.
Notice, that the gap between magnitude pruning and second order methods is very pronounced for all models, whereas the difference in performance between CAP and WF decreases with increase of the size model. Nevertheless, CAP performs still noticeably better than WF, especially in high sparsity regime.
Pruning and finetuning. In most of the practical setups one cannot achieve both high compression rate and maintain performance the dense model in one-shot setup. The full retraining procedure allows to achieve high sparsity but is rather expensive in the terms of compute. One can be interested
16

---

Detl Base
MF
Spandty
Sparsty
Spaniity
Figure 6: One-shot pruning of different DeiT versions.
have something in between- moderately sparse model, close in performance to the original model but without the need of long and expensive training.
In the experiments below prune all models to 50% sparsity, and fine-tune for 20 epochs. In addition to ViT/DeiT, we also consider similar models based on variants of self-attention [28, 1].
and compare against GM baseline. We use linearly-decaying learning rate schedule between
Tmaz = 10 4 to Mma = 10 - and the DeiT training recipe [43]. The results are given in Table 7, and show that CAP can almost recoerrecover accuracy in this setup for all models; the gaps from GM
and WF (see Deil-Small 75 and 90%) are still very significant.
Table 7: One-shot fine-tuning on letgeNet-1k.
Model
Method
Sparsity
Topl-Aceuracy
Model
Methol
Spurity (%)
Topl Tucurrcy (%)
These
89.8
Dense
GM
79.0
CAP
GM
82.5
WF
82.5
DeTT-Small
GM
74.3
CAP
N2.8
75
75.8
CAP
76.9
Nox-NextSSmall
GM
80.7
WF
75
81.0
GM
CAP
81.9
WF
90
59.3
CAP
65.1
GM
70.9
WF
73.2
Donse
0
81.8
78.3
CAP
GM
50
81.6
81.5
Small
Dense
82.0
GM
81.7
DeT--awe
GM
80.1
CAP
81.9
WP
75
80.2
CAP
81.0
Dense
81.3
GM
68.1
Tiny
GM
80.6
WF
CAP
N0.9
CAP
F Experiments with other models
In the main part of the text, we considered only gradual pruning of ViT models, but the proposed method is applicable to any architecture for image classification, such as convolutional neural network (CNN) or a ViT-CNN hybrid. We have selected recently proposed EfficientForme [27] as member of ViT-CNN hybrid family and trained it using the same setting and hyperparameters as for DeiT- Small. Two CNN architectures- ResNet50-D and EfficientNetV2--inn
[42] 3, considered in this work were trained with the use of augmentation and regularization procedure described in the recent PyTorch blog post. Differently from most of the prior art we have used the ResNet50-D trained with the modern recipe from timm repository.
For ResNet50-D we prune all convolutional weights except the first convolution and we keep the classification layer dense. In EfficientNetv2-Tinyy do not contribute much to the total number of parameters and FL.PPs but they are important to the model performance. We have set the block size be 256 for ResNer5O-D and 16 for EfficientNetV2- Tiny while keeping all the other hyperparameters of CAP the same as for DeiT' experiments. Such a small block size was chosen for EfficientNerV2-TTig due to the fact that it is the largest common divisor of the prunable weights.
do not prune depthwise convolutions since they
First of all, we conducted comparison between one-shot pruning methods for ResNet50-D. We compare between Uniform and Global magnitude pruning, WoodFisher with block size of 256,
2resnet.50d checkpoint with 80.5 accuracy for dense model
3 "efficientnetr2 _r_t checkpoint with 82.3 % accuracy for dense model
17

---

M-FAC with block size of 2048 and CAP with uniform and global sparsity, One can observe that CAP outperforms all previous methods even when comparing uniform sparsity with global sparsity, Contrary to the case of DeiT where there is no much difference in performance between uniform and global magnitude pruning for ResNet50-D global sparsity turns out to be much better. This results is quite expectable since CNN are not uniform and deeper layers are mode wide than those close to the input.
18

---

ResNet50-D
Val accuracy
Magn (U)
Magn (G)
0.2
M-FAC
0.3
CAP (U)
CAP (G)
0.0
Sparsity
Figure 7: One-shot pruming of ResNet50-D model on ImageNet dataset.
Next we carried out one-shot finetuning experiments with ResNet50-D keeping setup the same as for DeiT models in Table 7. We have selected 75 % and 90 % as the difference between methods becomes pronounced only at sufficiently high sparsity. Notably, the performance of Global magnitude and WF is roughly the same, the initial difference after one-shot pruning between WF and Global Magnitude vanishes during finetuning procedure, whereas there is still a gap performance between CAP and other methods.
Table 8: One-shot fine-tuning on ImageNet.
Model
Method
Sparsity (%) Topl Acccuracy (%)
Dense
80.5
GM
79.0
WF
79.0
ResNet-50D
CAP
79.2
GM
74.7
WF
90
74.8
CAP
75.2
Finally we conducted gradual pruning runs following the same sparsification schedule as for DeiT- models. The EfficientFormer and EfficientNet models despite being already very optimized and parameter efficient can be still compressed with small drop in accuracy.
G Scaling behaviour of pruning with respect to model size
To study the scaling behavior with respect to model size we took all variants of the ConvNext2 family of models [49] since covers wide range model sizes except for the large one due to the memory and compute constraints. The smallest model from the family ConvNext2-Atto has 3.7M parameters whereas the largest considered ConwNex12-Large has 198M parameters. All the models were pruned to 50% in one-shot. We observed that the relative accuracy drop (difference between accuracy of the dense and sparse model) initially decreases with increase of model size and then reaches plateau. CAP consisently outpeforms WF across all scales and the difference is the most pronounced for the smallest model.
19

---

Table Gradual pruning on ImageNet. Parentheses followed by the upwards directed arrow denote additional fine-tuning for 100 epochs.
Model
Method
Sparsity (%)
Topl-Aceuracy (%)
Dense
0
78.9
50
78.0
EtfFormer-LI
60
77.4
CAP
75
76.4
90
72.4 (72.8 1)
Dense
0
80.5
50
79.8
ResNet-50D
60
79.7
CAP
75
79.2 (79.6 f) 77.1 (77.5 1)
90
Dense
82.4
50
81.0
EnNeetV-TTnn
60
80.6
CAP
75
79.6 (80.0 f)
90
75.0
16
CAP
WF
Accuracy drop (%)
10
8
8
16
32
64
128
256
#
Params (M)
Figure 8: Left: CAP vs WoodFisher for pruning of ConvNext2 family.
H Timings
Any algorithms involving second order loss information believed to require tremendous amounts of compute. Time required for calculation of pruning scores and the OBS update comprises collection of grads, Fisher inverse rank-1 updates and additional pruning iteration for CAP. We have measured the time of single pruning step for DeiT-Small and present the results Table 10. All measurements were done
single RTX A6000 GPU with 48GB of memory. One observe that the amount of time needed to perform a pruning update is not very large, especially when compared to the duration of typical training procedure of modern computer vision models ImageNet that usually takes several days on a multi-gpu node. Note that the additional step for CAP adds small fraction total computational time relative to other steps of the OBS method.
Table 10: Minutes per pruning step for Deil-Small.
Model
Method
Time (minutes)
Fast WoodFisher [23]
20
DeiT-Small
CAP
23
20

---

I Composite compression
In addition to weight pruning one can decrease storage and inference cost with the help of other compression approaches: quantization (casting weights and activations to lower precision) and token pruning specific for the transformer architecture.
L.1 Quanticatoon-Aware Training
Weight quantization is done in the following way- one takes sparse checkpoint and then runs quantization aware training (QAT). We ran QAT training for 50 epochs with linearly decaying learning rate schedule from 7/max 10-A to Y/min 10-S, Models are quantized to 8-bit precision. In all experiments performed accuracy of quantized model almost reproduces the accuracy of the sparse model stored in full precision.
Table 11: ImageNet- IK top-1 accuracy for sparse models after QAT training.
Model
Sparsity (%)
Accuracy (%)
DeiT-Tiny
75
72.2
DeiT-Small
75
77.7
DeiT-Base
75
81
1.2 Token Pruning
There are different approaches for token pruning proposed in the literature. In this work follow the one from [35]. Specifically, in Dynamic one selects the ratio of tokens being pruned at each step with the lowest importance score, predicted by the model itself. Following the main setup from the paper we prune tokens after 3rd 6th, gth block, and the token pruning ratio after each block is p 0.2 (i.e 20% least improtant tokens pruned).
Table 12: ImageNet-IK top-1 accuracy for sparse models with token pruning.
Model
Method
Sparsity (%)
Top1-Accurag (%)
50
72.0
DynamicViT-Tiny
CAP
60
71.6
75
70.2
50
79.5
DynamieViT ViT-Small
CAP
60
79.4
75
78.7
L.3 Semi-structured sparsity
While CPUs can utilize sparsity patterns of arbitrary form to speed-up the computations at the present time modern GPU accelerators can handle only restricted form of unstructured sparsity, namely the N M sparsity pattern that enforces exactly N non-zero values for each block of M weights. Namely, since the introduction of Ampere architecture NVIDIA GPUs have special kernels that can work with 4 sparse matrices [30]. One can integrate the N M sparsity in the CAP framework without significant changes. The only difference with the original CAP approach is that while running the CAP iterations one doesn't I prune a given weight in case
group of M weights to which this weights belongs to there are M - N zero weights. Since the sparsity pattern is significantly constrained compared to generic unstructured sparsity pattern drop in performance after doing pruning step and consequent fine-tuning is more challenging than it would be for unconstrained sparsity. In experiments below we prune models
4 sparsity either in one-shot setting and fineshot+ We apply shorter (10 epochs) and longer (50 epochs) finetuning procedure with linearly decaying learning rate schedule. According to the results in the Table 13 CAP significantly outperforms competitive methods for one-shot pruning, although the drop in performance is quite large for all methods. After finetuning procedure difference between different methods decreases. Nevertheless, there is some gap in performance between second order methods and magnitude pruning even after relatively long finetuning.
To demonstrate practical benefits from 2:4 sparsity pattern we compiled both sparse and dense models via TensorRT engine and compared the throughput. The inference executed on Nvidia T4 GPU
21

---

Table 13: Semi-structured 2 : pruning of ViT models,
Lpochs
Topl-Accuracy (18)
CAP
55.9
Deil
WF
10
71.1
CAP
71.5
GM
72.5
WF
30
72.7
CAP
71.7
Demse
79.8
GM
53.6
DetT Small
CAP
WF
50
79.0
CAP
79.0
Dense
81.8
GM
66.4
WF
73.7
CAP
78.1
DelT- Base
GM
81.2
WF
CAP
81.7
with batch size of 64 in half precision. Sparsity allows for small but certain speedup for models of different scale.
Table 14: Speedup factors for 2 sparsity.
Model
Speedup
DeiT-Tiny 1.07
Deil-Small
1.07
DeiT-Base 1.10
CAP/WF hyperparameters
Following the oBERT's directions [23] on identifying the optimal set of hyperparameters via one-shot pruning experiments, conduct grid search over the three most important hyperparameters:
Number of grads collected for Fisher inverse
Dampening constant
Block size
The more grads are collected, the more accurate the empirical Fisher inverse estimate, however, more compute is required at the same time. We chose N 4096 point from which further increase of Fisher samples doesn't improve performance a Dependence of the one-shot pruning performance at different sparsities vs number of grads is presented
Figure 9.
The next parameter to studied is the dampening constant À in. This constant regularizes the empirical Fisher matrix and allows to avoid instabilities in computation of the inverse. However, this constant decreases the correlation between different weights and the limit - oo OBS reduces to magnitude pruning. The optimal dampening constant for CAP (Nopt = 10-*) is smaller than the one for WoodFisher (Aopt = 10 (0- i.e CAP remains numerically and computationally stable with smaller amount of regularization compared to WF (we observed that for À < 10 -7 WF performance starts to deteriorate rapidly).
22

---

DeiT-Small
DeiT-Small
08
16
16
236
256
Val accuracy
4096
accuracy
4096
1024
Sparsity
Spansity
Figure 9: Left: One-shot pruning performance of WoodFisher. Right: One-shot pruning performance of CAP.
DelT-Small
DeLT-Small
le-5 1e-8
le-7
1e-8
1e-7
Val aocuracy
aocuracy
0.5
0.4
03
088
0.
0.0
0.9
0.5
Sparsity
Sparsity
Figure 10: Left: One-shot pruning performance of WoodFisher. Right: One-shot pruning perfor- mance of CAP.
And the last but not the least important parameter is the block size in [39]. The larger the block size is, the more correlations between different weights are taken into account. However, as mentioned in 2 the computational and storage cost scales with the block size. Moreover, for fixed number of gradients in the Fisher estimate matrix with larger block sizes likely to be worse conditioned. Therefore, one would like to work with smaller block sizes but not to keep the approximation as accurate possible. We've selected block size according the accuracy-efficiency trade-off.
DeiT-Small
DeiT-Small
96
96
192
0.6
Val accuracy
urcyracy
0.5
0.5
0.4
0.4
0.3
63
04
0.5
0.6
477
0.5
0.5
0.3
04
05
8-5
0.7
0.8
0.5
Sparsity
Sparsity
Figure 11: Left: One-shot pruning performance of WoodFisher. Right: One-shot pruning perfor- mance of CAP.
In addition, we' ve studied the benefit from application of multiple recomputations in the one-shot pruning setting for WoodFisher and CAP. Since the assumption of static Fisher matrix F f(w*) doesn't hold in general, expect that multiple recomputations are likely to result in higher one-shot accuracy
23

---

in accordance with the result from [14]. This is indeed the case. The gain from recomputations is more pronounced for WoodFisher, since CAP already performs implicit Fisher inverse updates in its operation. Yet, the efect is not vanishing even for the case of CAP.
DefT-Small
0.8
0.7
0.5
Val accuracy
0.5
0.4
WF (Nr=1)
0.3
WF (Nr=2)
0.2
WF (Nr=5)
WF (Nr=8)
0.3
CAP (Nr=1)
CAP (Nr=5)
0.0
Sparsity
Figure 12: One-shot performance for WF and CAP with different number of recomputations N
K Details and hyperparameter choices for other pruning methods
In this section we provide some additional details about methods compared on Figures and The popular Movement Pruning [38] computes the weight saliency scores during the training pro- cedure, hence it is not a one-shot pruning method by definition. We have observed that use of the naive elementwise product of gradient and weights ( (ie p; @ V [(w)) leads to poor performance, significantly below even the Magnitude Pruning baseline. However, the following first order pruning criterion:
(w)ll
Pr
allows to get reasonable saliency scores that produce more accurate sparse models than Magnitude Pruning. However, its performance is still inferior to any of the second order pruning methods. This method is denoted as GrW (Gradient times weight) on Figures and M-FAC Pruner proposed in [14] is a pruner leveraging second order information that doesn't 't require an explicit construction of Fisher Inverse matrix. Therefore, unlike WoodFisher and CAP that require O(Bd) memory computation and storage cost of this method is constant with respect to the block size and one can take into account correlations between larger groups of weights for free. Following the original paper we chose block size of 2k as the best performing one. However, one can see from Figures 2 and 7 that smaller block sizes turn out to perform better. A possible explanation of this phenomenon is that the Fisher Inverse estimate becomes too noisy and unstable for large blocks.
L Execution latency
In addition to the plot throughput accuracy shown in the main part we present in this section execution latency per sample latency when running models on the DeepSparse engine. The results are presented on Figure 13.
M Comparison with AC/DC training
In addition to the sparse training from scratch with periodic updates of the sparsity weights with some saliency criterion for weight elimination and regrowth [10] one can consider alternating compressedddecompressse training (AC/DC), proposed in [33]. Namely one switches between dense stages with standard unconstrained training of the model, and sparse stages when the model is pruned to the target sparsity level and trained with the frozen sparsity mask until the beginning of the next dense stage, when the sparsity mask is removed. This procedure produces both accurate dense and sparse models.
24

---

82
DefT-Base
DeiT-Small
80
DeiT-Tiny
78
Val. accuracy
76
70
68
Latency (ms)
Figure 13: Accuracy latency ImageNet- lk.
Following the original paper we use magnitude pruming as saliency criterion for weight pruning. The augmentation and regularization pipeline follows the settings from [43]. All models with AC/DC were trained for 600 epochs in total with first pruning step at epoch 150 followed by 7 sparse stages 25 epochs long each, and dense stages of the same length. The last dense stage lasts 50 epochs and the last sparse 75 epochs long. Learning rate is gradually decayed from 7/max = 5 10 to Mmin 10-6 with cosine annealing. Initial warm-up phase with linearly increasing learning rate is 20 epochs. We compare AC/DC with CAP models finetuned for additional 100 epochs.
Table 15: AC/DC vs CAP (finetuned for additional 100 epochs) on ImageNet- lk.
Model
Method
Sparsity (%)
Topl Focuurcyy (%)
CAP
79.9
60
AC/DC
80.4
CAP
79.0
DeiT-Small
75
AC/DC
79.0
CAP
75.8
90
AC/DC
72.0
One can observe that at low sparsity AC/DC achieves higher accuracy for the same sparsity target (even outperforming the dense baseline by 0.6%), whereas for 75% performance of both methods is equal, and CAP outperforms AC/DC at higher sparsity. However, one should note, that CAP uses computational budget (including the training of original model) of 440 epochs for 60% sparsity, 520% for 75% and 700% for 90% vs 600 epochs used AC/DC.
N One-shot pruning of DETR
The approach presented in the paper is not limited to the image classification task, but can be applied to other computer vision tasks, such object detection. We chose the DeTR model [4] with ResNet50 backbone and ran one-shot pruning procedure with global magnitude, WoodFisher and CAP pruner. Specifically, we pruned all convolutional layers in the CNN backbone expect the first one and all linear projections in transformer encoder and decoder blocks while keeping the detection heads dense. The results are presented in Table 16. Following the standard protocol we used bbox mAP for evaluation. One can observe, that difference between the second order methods and magnitude pruning is very pronounced even for relatively small sparsity of 50%, and CAP outperforms WF pruner.
25

---

Table 16: One-shot pruning of DeTR.
Model
Method
Sparsity (%)
bbox mAP
Dense
0.42
GM
0.16
DeTR
WF
50
0.36
CAP
0.38
O Proof of Theorem
Theorem O.0. Let S be a set of samples, and let Ve, (w")..... ...... Ven((") be a set of gradients with i S, with corresponding empirical Fisher matrix F (w"). Assume sparsification target of weights w". Then, a sparse minimizer for the the constrained squared error problem
(V" Ve w-) w' has least k zeros,
minlw!
(10)
2m
is also solution the problem of minimizing the Fisher-based group-OBS metric
argmin QQQ) 2 wQ (
WQ:
(11)
Proof. We start by examining the unconstrained squared error function in Equation (10), which
denote by G. Clearly, the function G is d-dimensional quadratic in the variable w', and has minimum at w Next, let us examine G's second-order Taylor approximation around w given by
(w'
Ve, (w") (w' w").
(12)
where used the fact that w is minimum of the squared error, and thus the function has 0 gradient it. However, by the definition the empirical Fisher, this exactly equal to
(w' w*) FWW""/W''www (w'w""
(13)
The Taylor approximation is exact, as the original function is quadratic, and the two functions are equivalent, Hence, we have obtained the fact that, under the empirical Fisher approximation, a k-sparse solution minimizing Equation 10 will also be a k-sparse solution minimizing Equation 1. However, the question of finding a k-sparse solution minimizing Equation 1 is precisely the starting point of the standard OBS derivations (see c.g. [39] [23]), which eventually lead to the formula in Equation (11). This concludes the proof.
P Augmentation choice for Empirical Fisher
compared the performance of CAP with Empirical Fisher computed on image-label pairs where the validation transforms were applied to images (i.e center crop with resize) and the same set of augmentations used for training and finetuning (RandAugment transforms, Label smoothing, e.t.c.). We observed that the sparsity solution obtained without augmenting samples for Empirical Fisher estimate turns out to be strongly overfitting. We point out that in both cases we use the same population size for Empirical Fisher.
Figure 14 illustrates this result: using validation augmentation (red) yields better training loss but degenerates in terms of validation accuracy. A possible explanation is that CAP chooses an overfitting solution which the model is unable escape during finetuning.
26

---

DaIT-Tiny
DeiT-Tiny
aug
oug
Train loss
Vil hoss
125
11.
12.
153
Epoch
Epoch
Figure 14: Training (Ieft) and validation loss (right) for one-shot finetuning.
Fisher matrix structure
In order to validate the necessity taking into account the correlations between weights, one has to make sure that the empirical Fisher matrix used as proxy for Hessian is non-diagonal. We have visualized average block of empirical Fisher for particular layer Figure 15 from DeiT-Tiny and ConyNext-Small models. One can see, Fisher matrix exhibits a pronounced non-diagonal structure, which justifies the need of careful and thorough treatment of weight correlations.
blocks.5.atth sattn.pro..ae wwinnproo..wigg.... weight
Stages.2.blocke. 24.mp..f2..mm.m111mm..m.. www.mmll.....ee..m.....mmmmmmmm. weeeght
Figure 15: Left: empirical Fisher block for a weight from DeiT-Tiny, Right: empirical Fisher block for weight from Con-Next-Small.
R Broader impact
Compressed models are not expected exhibit more malicious and potentially harmful behavior compared to the dense models. However, they may face the same issues like the original models in safety-critical applications such susceptibility adversarial attacks and distribution shifts.
Limitations
The proposed method is mostly suitable for small and medium sized models (up to order of ~ 100M). For larger models the compute and storage cost associated with the estimate empirical Fisher becomes prohibitively expensive. Compression of the largest models considered is this paper requires 2-4 high-end GPUs (A100 with 80GiB). Pruning models to high sparsity requires significant amount of training. Search for fast and efficient procedures for the recovery of compressed models is left as potential direction for further research.
27


Reviews:
[{"review_id": "hOUsBC8GeX", "reviewer": "Reviewer_wReA", "summary": "The paper proposed a Correlation Aware Pruner (CAP) , a new unstructured pruning framework capable to prune models to high sparsity. It takes into account weight correlations. To do this, the paper reformulate the OBS multi-weight pruning problem: when using the empirical Fisher approximation, the problem of finding the optimal set of weights to be removed, while taking correlations into account, is equivalent to the problem of finding the set of sparse weights which best preserve the original correlation between the dense weights and the gradients on an fixed set of samples.\n\nOn top of that, the paper also applies a series of training techniques to improve training: Learning Rate Schedule,  Regularization and Augmentation, Efficient Sparsity Sweeps. Results show better performance compared to existing works, expecially at high compression ratio", "questions": "See weekness", "limitations": "Please address the limitations and potential negative societal impact in the revision.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written, and has good logic. Great amount of experiments and ablations discussion to strengthen the proposed method. ", "weaknesses": "Unstructured pruning is hard to have actual hardware speedup due to the irregular sparsity. Although the proposed method can maintain high accuracy at extreme prune ratios, it may just be just theoretically more efficient. \n\nThe author is encouraged to add inference latency or throughput in the results tables 1 & 2", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and comments! \n\nIt is true that, traditionally, sparsity is harder to leverage for computational speedups. However, unstructured sparsity is now supported with speedups on CPU, and 2:4 semi-structured sparsity is supported with speedups on NVIDIA GPUs. Our method can create accurate models targeting both sparsity types: \n\n* Figure 4 shows end-to-end throughput speedups of more than 2x for CPU deployments when running CAP models using the DeepSparse inference engine (supporting unstructured sparsity). \n* In Appendix H.3, we provide accuracy results for several models with 2:4 semi-structured sparsity, with minor or no performance drop compared to the original dense model. This format is natively supported with speedups by all modern NVIDIA GPUs (Ampere, Hopper) [1].\n \nFollowing your suggestion, we will add the corresponding inference throughput speedups in Tables 1 and 2. The numbers can currently be read from Figure 4, which provides the desired data in speedup-vs-accuracy format. Please note that, e.g. for DeiT-Tiny, we obtain a real-world speedup of > 2x at negligible accuracy loss. \n\nThe main limitation of our method is the scalability, since the memory footprint and runtime becomes prohibitively expensive for models with 1B parameters and more. However, one can propose a relaxed version with some additional approximations that can be scaled to large models. We describe it in more detail in general response. \n\nSparse models are not expected to show more malicious behavior compared to the dense models. However, as any other kind of technology, they can be applied both for good and bad purposes. The main potential outcome of our work is the speedup and more widespread adoption of modern computer vision architectures in resource constrained setup, such as inference on edge devices.\n\n[1] https://developer.nvidia.com/blog/exploiting-ampere-structured-sparsity-with-cusparselt/\n"}, {"review_id": "K7GxEc3548", "reviewer": "Reviewer_JVcP", "summary": "This paper proposes to consider the correlation between pruned elements in pruning deep neural netowkr models. The paper provides an efficient algorithm to distangle the correlation into a sparse regression problem, and propose a fast solver to find the solution. Further exploration is performed on the learning rate scheduling and data augmentation of the pruning and finetuning process. The final method results in better model size-accuracy tradeoff comparing to previous method with less training cost.", "questions": "See weakness.", "limitations": "The limitation and social impacts have been adequately discussed.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This paper provides well motivated method on model pruning with solid theortical justification\n2. The proposed reformulation of sparse minimization and the fast solver of the optimization is novel an have significant impact on model compression\n3. Adequate experiments are provided to show the effectiveness of the proposed method, including pruning advanced highly accurate models\n4. The paper is overall well written and easy to follow.", "weaknesses": "As discussed in the limitation, the cost of considering full correlation is still prohibitive on large models. It would be interesting to see some relaxation of the proposed method that can have less cost while maintaining most of the good performance. More discussion is encouraged on the potential relaxation strategy, and the tradeoff between optimization cost and performance.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your very insightful feedback!\n\nRegarding scaling, currently, CAP can scale easily to models with hundreds of millions of parameters, with reasonable block sizes and reasonable runtime (< 30 minutes / pruning step on 1 GPU). Yet, you are right in that it would be challenging to scale CAP to billion-parameter models, because of the necessity of storing and processing blocks of the Fisher inverse. \nMotivated in part by your suggestion, we observed that there is a relaxation of CAP which can easily scale to massive models, via two steps: \n\n* First, one can average Fisher blocks across the layer output dimension and use these blocks as proxy of the Hessian, where each Hessian matrix is the same for all output channels. (This step is similar to the Layer-Wise Optimal Surgeon paper [1].) \n* Secondly, following the recent SparseGPT paper [2], instead of eliminating the weights in the greedy-optimal order, i.e. always selecting the weight whose elimination leads to the smallest increase of loss, one can prune them in some fixed order, fixed across all output dimensions. Specifically, for this we adapted the iterative removal process from SparseGPT, which is more GPU-friendly and scales better with increase of model size. \n\nThe resulting modification is an approximation of CAP: the main constituents - block-wise Fisher approximation and resolution of inter-weight correlations are the same as in the original algorithm. The two approximations above lead to reduction of the memory footprint and the runtime which are linear in the embedding dimension: in practice, this is 100x-1000x compared to the original CAP. Thus, FastCAP is easily scalable to billion-parameter models with reasonable computational cost. \n\nTo validate performance of FastCAP we applied it for pruning of large ViT models in a one-shot setting, specifically `eva_giant_patch14_224.clip_ft_in1k` from the `timm` library. This model has **>1B** parameters. We compared the top-1 accuracy on ImageNet of FastCAP vs Magnitude pruner. One can see that FastCAP significantly outperforms the baseline. At the same time, FastCAP has a reasonable runtime and memory footprint at this scale. Pruning step takes ~400 seconds on a single A100 GPU. \n\nTable 1. Performance of large ViT after 1-shot pruning.\n|   Model   | Sparsity |   Method  | Accuracy (%) |\n|:---------:|:--------:|:---------:|:------------:|\n| EVA ViT-G |     0    |     -     |     88.7     |\n|           |    50    | Magnitude |     87.9     |\n|           |          |  FastCAP  |     88.1     |\n|           |    60    | Magnitude |     85.5     |\n|           |          |  FastCAP  |     86.3     |\n|           |    70    | Magnitude |     64.3     |\n|           |          |  FastCAP  |     76.1     |\n\n[1] Dong, Xin, Shangyu Chen, and Sinno Pan. \"Learning to prune deep neural networks via layer-wise optimal brain surgeon.\" Advances in neural information processing systems 30 (2017).\n\n[2] Frantar, Elias, and Dan Alistarh. \"Massive language models can be accurately pruned in one-shot.\" arXiv preprint arXiv:2301.00774 (2023).\n"}, {"review_id": "cUko1HjG5W", "reviewer": "Reviewer_kMpj", "summary": "The submission proposes a second-order method for unstructured pruning of neural net parameters, to leverage the efficiency gains of sparsity. It uses an optimization based on the empirical Fischer matrix to find saliency scores, that are used for the order in which weights are pruned. They present an algorithm based on solving the problem on individual sub-blocks, and then using that within a global pruning. They also present a schedule, across different hyperparameters, for training with pruning. This is demonstrated on ConvNeXt and DeiT models, along with other CNN and ViT models in the supplement.", "questions": "**Code**: Some miscellaneous minor comment from trying the included code\n\nREADME.md marks the step to install wandb as \"optional.\" Not entirely optional, though, given that it does import it:\n\n```\n  File \"CAP-code/research/one_shot_pruning.py\", line 4, in <module>\n    import wandb\nModuleNotFoundError: No module named 'wandb'\n```\n\nCommenting out the import, then see:\n\n```\nAttributeError: module 'numpy' has no attribute 'object'.\n`np.object` was a deprecated alias for the builtin `object`. To avoid this error in existing code, use `object` by itself. Doing this will not modify any behavior and is safe. \nThe aliases was originally deprecated in NumPy 1.20; for more details and guidance see the original release note at:\n    https://numpy.org/devdocs/release/1.20.0-notes.html#deprecations\n```\n\nwithin the import of onnx inside sparseml:\n\n```\n    from sparseml.pytorch.utils import LOGGING_LEVELS, BaseLogger, LoggerManager\n  File \"${HOME}/anaconda3/envs/CAP/lib/python3.9/site-packages/sparseml_nightly-0.13.0.20230704-py3.9.egg/sparseml/pytorch/utils/__init__.py\", line 23, in <module>\n    from .exporter import *\n  File \"${HOME}/anaconda3/envs/CAP/lib/python3.9/site-packages/sparseml_nightly-0.13.0.20230704-py3.9.egg/sparseml/pytorch/utils/exporter.py\", line 26, in <module>\n    import onnx\n  File \"${HOME}/anaconda3/envs/CAP/lib/python3.9/site-packages/onnx-1.10.1-py3.9-linux-x86_64.egg/onnx/__init__.py\", line 20, in <module>\n    import onnx.helper  # noqa\n  File \"${HOME}/anaconda3/envs/CAP/lib/python3.9/site-packages/onnx-1.10.1-py3.9-linux-x86_64.egg/onnx/helper.py\", line 17, in <module>\n    from onnx import mapping\n  File \"${HOME}/anaconda3/envs/CAP/lib/python3.9/site-packages/onnx-1.10.1-py3.9-linux-x86_64.egg/onnx/mapping.py\", line 27, in <module>\n    int(TensorProto.STRING): np.dtype(np.object)\n  File \"${HOME}/anaconda3/envs/CAP/lib/python3.9/site-packages/numpy/__init__.py\", line 305, in __getattr__\n    raise AttributeError(__former_attrs__[attr])\n```\n\nFollowing instructions in the README had given me `numpy==1.24.3` and `onnx==1.10.1`. It's likely that one needs to hold back numpy, likely an underlying issue with the requirements specified for SparseML. Presumably this codebase is using an old version of sparseml that specifies a requires.txt such that it's versions specified with '>=' no longer really work with the latest versions now available. Authors should check & perhaps update the install commands in their README accordingly, or update their sparseml version. I was able to resolve this with instead:\n\n```\nconda install numpy==1.20.3\n```\n\nGenerally recommended practice for distributing this kind of research code is to explictly specify versions of the requisite packages with `==`, so we know exactly how the authors originally did all this.\n\nSample command for `one_shot_pruning.py` in README also includes the command-line arguments `--data-dir` and `--sparseml-recipe`, when the arguments actually added to argparse are `--data_dir` and `--sparseml_recipe`, and arguments `-b` and `--experiment` that don't seem to exist.", "limitations": "Cite computation cost (at training/pruning, not inference/deployment time) as the limitation. The Fischer matrix will still grow quadratically in the number of parameters. This is unfortunate given the likelihood that the largest models that would benefit the most from pruning, in absolute terms. (And it is an oft-observed principle in ML that simple methods that scale better are usually more impactful.)", "rating": 3, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "**i)** Achieves better accuracy & sparsity.\n\nThe proposed pruning gets pareto-dominant results relative to some similar prior work. The evaluation is done across multiple choices of the sparsity vs accuracy tradeoff.\n\nNot all experiments consider some of the most similar previous methods, though, such WoodFisher in the \"Gradual Pruning\" results, though the original work did include gradual pruning during training. (See section 5.2 of [38])\n\n**ii)** Considers good selection of recent models\n\nExperiments demonstrate the pruning on both up-to-date ConvNet and vision transformer models. In the supplement and code, experiments on ResNet-50 and EfficientNet are also provided.\n\n**iii)** Includes code\n\nThe submission includes the code used to run the experiments, based on SparseML, along with YAML files specifying the hyperparameters for a number of the experiments.", "weaknesses": "**iv)** Largely superseded by Optimal BERT Surgeon in a lot of settings\n\nOBS is a more scalable algorithm based on the same underlying principles. The core contribution seems to be a different method of approximating the solution to the original 2nd-order problem, plus better hyperparameter tuning. It does seem like a reasonable approach for relatively smaller models, to seek a tighter approximation to the original optimization.\n\n**v)** Source of improvement in end metrics remains unclear\n\nAt its core, the starting point of the construction of the method in the submission is similar to [38]: namely, second-order pruning with the empirical Fisher matrix in place of the Hessian. The differences from [38] then include a) a different method of approximating the pruning on the full matrix, described toward the end of Section 3.1, and b) improved hyperparameters during gradual pruning.\n\nThe paper states that ablation studies are given in appendices B, I, and J. These appendices specify different sets of hyperparameters, and include results of sparsity vs accuracy for multiple different choices of some of these hyperparameters. I didn't find any \"ablation\" studies that evaluate parts of the proposed method with other parts \"ablated\" or removed: for example, the results of using Algorithm 1 *without* the changes to data augmentation, the sparsity and learning rate schedule, etc.\n\nExperiments also don't compare against [38] for the gradual pruning case, so the effect of the hyperparameter tuning and schedules isn't measured by a comparison to baseline. It's possible that the improved choices in which weights to prune, as seen in the one-shot case, could also affecting the gradual pruning case, but it's also possible that the training can close a lot of this gap.\n\nThe experiments also use very recent ViT-based models, showing some more up-to-date results than prior work. It is plausible that better pruning is necessary to get good results for these models, as argued, but this is incompletely supported.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback, which we address in detail below. \n\n> iv) Largely superseded by Optimal BERT Surgeon in a lot of settings\n\nIn short, we emphasize that the scalability of both methods you reference (Optimal BERT Surgeon (OBS) and CAP) is essentially the same, while CAP is significantly more accurate across all the settings we tried.  \n\nBoth OBS and CAP use the same 2nd order approximation (the block-wise empirical Fisher). The computational and storage cost of both OBS and CAP are dominated by the estimate of the Fisher inverse. Specifically, most of the practical runtime is taken by the forward-backward passes required for estimating the Empirical Fisher at a pruning step. Then, the Optimal BERT Surgeon selects a large group of weights at a single step and prunes it. By contrast, our algorithm eliminates weights one-by-one and accounts for the change of correlations and importance of a particular weight after each previous weight. \n\nThe key theoretical contribution of our work is a new algorithm for efficiently resolving these inter-weight correlations which arise during pruning: essentially, CAP allows us to efficiently “simulate” OBS weight removal one-weight-at-a-time (which would take massive time to run iteratively). In turn, taking correlations into account leads to much more accurate pruning, as we illustrated in Figures 2 and 3. If we remove this correlation-solving component, our approach becomes identical to OBS.\n\nIn practice, the runtime and scalability cost of the CAP component is negligible relative to the cost of obtaining the Fisher estimate. We have mentioned this in the main text (l.352), and detailed it in Appendix G: our method has essentially the same runtime and memory costs compared to WoodFisher/Optimal BERT Surgeon, while being significantly more accurate.  \n\nOn methodology, we would like to emphasize that we have considered the best available implementation of the Optimal Brain Surgeon Framework, which is the Optimal BERT Surgeon. The hyperparameter tuning procedure was the same for all methods--we tuned each method independently, and always selected the best hyperparameter configurations for each method in turn. Details on this are provided in the Appendix. Hence, we believe that our comparisons are fair. \n\n> v) Source of improvement in end metrics remains unclear\n\nAs noted above, our contribution is an efficient exact weight correlation solver during pruning: if we remove the correlation solver from CAP, we obtain an instance of OBS using a block-wise Fisher approximation, which is essentially WoodFisher/Optimal BERT Surgeon. \nThus, our one-shot pruning comparisons essentially provide one of the key ablation study that the reviewer is asking for: WoodFisher/OBS is CAP without the correlation solving. So, in the comparisons with WoodFisher/OBS, we are ablating the key component of our method. We have provided this comparison, showing the impact of correlation solving, in Figure 2 and Table 4 in the main text, and Figure 6, Table 6, Figure 7, Table 7, and Figure 8 in the Appendix, across several models and tasks. \n\nFurther, we have shown that correlation solving (our method) has a significant effect, beyond just accuracy: in Figure 3 (main text), we illustrated that the weight configurations chosen by CAP and WoodFisher/OBS are significantly different: the sparse weights obtained after one-shot pruning land at different points in the loss basin. \n\nIn Appendix Figure 7, we show exactly the same one-shot effects for a ResNet50-D model, whereas Table 6 presents results for a ConvNext model. This validates the fact that our results hold across very different architectures. Moreover, we have also shown results on different tasks (DeTR). \n\nAppendix C performs ablations for the fine-tuning parameters (learning rate schedule and augmentation procedure), validating our choice of schedule. The one-shot + fine-tuning results in Appendix Tables 6 and 7 confirm the effect that the reviewer is referring to: fine-tuning usually reduces the gap between methods, but the differences remain significant, especially at large sparsities. (E.g., CAP produces a 90%-sparse model that is more accurate by 5 Top-1 points relative to WF, on ConvNext-Small.) \n\nIn sum, we believe that all these results support our claim that correlation solving can have a consistent significant impact on pruning accuracy, across model scales, model types, and tasks.  \n\n(For reference, WoodFisher and Optimal BERT Surgeon implement the same empirical Fisher approximation, but Optimal BERT Surgeon presents a more efficient implementation, with parameters specifically chosen for accuracy and scalability on Transformer models.) \n\n> Code: Some miscellaneous minor comment from trying the included code\n\nWe would like to sincerely thank you for your effort in trying out our code, and we apologize for the dependency issues you encountered. We have taken all your suggestions into account to produce an improved version of the code package. \n\n> Limitations\n\nIndeed, computational cost is an issue for all approximate second-order methods in deep learning, which we see as an intriguing challenge to address. Please note, however, that the blockwise Fisher matrix approximation used in our work doesn’t scale quadratically with the dimension: it is linear in the dimension times block size: the algorithm requires $O(d B)$ memory and has $O(d B^2)$ runtime, as mentioned in Section 3.1.  Larger models benefit more from pruning, but compression of moderate-size models (e.g. with 1-50M parameters) is still of great practical use for inference on edge devices, constrained in their compute power. Our work shows significant practical speed-ups for unstructured sparsity on commodity CPUs, therefore it can have real-world impact. \n\nTo further address this concern of scalability, in the response to Reviewer JVcP and general response we present a much more efficient approximate version of CAP (FastCAP).\n"}, {"review_id": "hue5XkieGO", "reviewer": "Reviewer_gPY6", "summary": "This paper studies the unstructured pruning problem for vision transformer models. The Correlation Aware Pruner (CAP) is proposed. CAP takes into account weight correlations and achieves a new state-of-the-art result.", "questions": "Please see weaknesses.", "limitations": "The authors have adequately addressed the limitations", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method achieves strong experimental results. For the first time, ViT models can attain high sparsity levels (75-80%) without significant accuracy loss (<1%). Note that previous methods reached at most 50% sparsity.\n- CAP is reasonable and well-motivated. This paper points out an important problem that removed weights may themselves be correlated. It also highlights the importance of the learning rate schedule. Overall, this paper provides lots of useful information for unstructured pruning for ViT.\n- The whole paper is organized and written well. Experiments are sufficient and sound.", "weaknesses": "- The biggest problem is unstructured pruning struggles with GPU devices. The authors test models’ latency on a sparsity-aware CPU inference engine. However, GPU is not considered. Overall, unstructured pruning performs badly on GPU which limits its practical ability.\n- Some results of SViTE are missing in Tab. 2. It is better to change the order to put CAP at the bottom of each section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the feedback!\n\n**1. Applicability to GPUs:** \n\nIn Appendix H.3, we provided results for pruning with hardware-supported 2:4 sparsity pattern [1]. This semi-structured sparsity pattern can lead to speedups of tensor operations on the Ampere and Hopper GPU architecture. One can see that our method allows us to compress the models without significant drop in performance in this setup. For convenience, we present a sample of the results in **Table 1** below. \n\n**Table 1. Semi-structured 2:4 pruning of ViT models followed by 10 epochs of finetuning.**\n\n|    Model    | Method | Top1-Accuracy (\\%) |\n|:-----------:|:------:|:------------------:|\n|  DeiT-Tiny  |    -   |        72.2        |\n|             |   GM   |        68.8        |\n|             |   CAP  |        71.5        |\n|  DeiT-Small |    -   |         79.8       |\n|             |    GM  |         77.9       |\n|             |   CAP  |         79.0       |\n|   DeiT-Base |    -   |         81.8       |\n|             |    GM  |         81.2       |\n|             |   CAP  |         81.3       |\n\n**2. Comparison with SViTE:** \n\nWe included all the results from the original paper (where there was a result for a specific sparsity level) as well as additional experiments we performed ourselves (in case there was no experiment with the given sparsity in the paper). The training procedure in SViTE requires 2x more epochs than the full CAP pipeline, and has to be rerun for every sparsity level. (Recall that CAP produces all sparse models in a single run.) Due to the high computational cost of retraining ViT models, we were unable to perform experiments for some sparsity levels. \n\nWe would have liked to run these additional experiments for SViTE for the rebuttal phase, but unfortunately the experiments wouldn’t finish by the end of the rebuttal period, given the large cost of running 600 epochs of training for large models on our computational resources. We plan to add a full comparison, across all sparsity levels, in the next revision. At the same time, we note that currently CAP appears to outperform SViTE across all sparsity levels. (Please see Figure 4 for an illustration across the entire DeiT family of models.)\n\n[1] https://developer.nvidia.com/blog/exploiting-ampere-structured-sparsity-with-cusparselt/\n"}]

Author rebuttal:
We thank the reviewers for their feedback and comments on our work. 

Below is the summary of the main concerns and questions addressed in our rebuttal:

**1. Difference between WoodFisher (Optimal Brain Surgeon) and CAP.**

In the response, we emphasized that our contribution is not another approximation of Fisher matrix, but a new algorithm resolving the correlations between the weights during the pruning process. Specifically, CAP allows the user to efficiently emulate the ideal Optimal Brain Surgeon (OBS) process of pruning one-weight-at-a-time, adjusting the remaining weights after each removal. As such, it is the first implementation of “true” OBS at scale. If we completely remove correlation solving from CAP and perform one-shot pruning, we simply obtain a vanilla instance of OBS, essentially WoodFisher. 

Thus, our comparisons with regular instances of OBS such as WoodFisher/Optimal BERT Surgeon, which do not solve for correlations, essentially showcase the power of correlation solving. These results are shown in Figures 2 and 3 and Table 4 in the main text and  Figure 6, Table 6, Figure 7, Table 7, and Figure 8 in the Appendix, show that resolving correlations accurately can have a major impact on the accuracy of the pruned model. Appendix Figure 12 performs a very fine-grained analysis of the impact of correlation solving on the accuracy of pruned models. 

**2. CAP Scalability.**

The version of CAP we presented in our submission can scale to models with < 1B  parameters, covering most standard vision models. Its key computational and memory cost comes because of computing and maintaining the inverse Fisher approximation. This is the same as other methods, such as WoodFisher/Optimal BERT Surgeon, and the running time of CAP is essentially the same as these prior methods, while being significantly more accurate.  
  
To address this scalability concern in full, in response to Reviewer jVCP we present a much more scalable approximate variant of CAP, called FastCAP, which is inspired by the recent SparseGPT scalable pruner (arXiv::2301.00774). Specifically, FastCAP reduces compute and memory cost by ~100x by leveraging a cheaper Fisher approximation and relaxing the optimal greedy order of pruning. The other method components stay the same. FastCAP can be scaled to billion-parameter vision models, i.e. we can prune ViT-Giant in a few minutes, while achieving reasonable performance in one shot-setting for 50-70% sparsity. We present a simple description of FastCAP in the responses to Reviewers jVCP and  kMpj, and plan to provide the full results in the next revision.  The results for pruning of large ViT model are presented in **Table 1**.

Table 1. Performance of 1-shot pruning on ViT-Giant.
|   Model   | Sparsity |   Method  | Accuracy (%) |
|:---------:|:--------:|:---------:|:------------:|
| EVA ViT-G |     0    |     -     |     88.7     |
|           |    50    | Magnitude |     87.9     |
|           |          |  FastCAP  |     88.1     |
|           |    60    | Magnitude |     85.5     |
|           |          |  FastCAP  |     86.3     |
|           |    70    | Magnitude |     64.3     |
|           |          |  FastCAP  |     76.1     |

**3. Practical Speedups.**

We presented end-to-end speedup results on CPUs in the original submission: for instance, we obtain speedups of 1.5--2x across ViT family models, with negligible accuracy impact.  Although general sparsity is not supported on GPU hardware, 2:4 structured sparsity is natively supported in modern (Ampere and Hopper) GPU architectures, and leads to speedups of the tensor multiplication operations. Our method can be applied to create 2:4 sparse models as well, with a minor modification to the sparsity mask constraint. 

Accuracy results for the resulting 2:4-sparse models were presented in Appendix H.3. For convenience, we present them in **Table 2** below. The resulting models could be executed with speedups via the NVIDIA TensorRT GPU inference engine, at relatively minor accuracy drops (0.8-0.1%) relative to the dense baselines. 

Table 2. Semi-structured 2:4 pruning of ViT models followed by 10 epochs of finetuning

|    Model    | Method | Top1-Accuracy (\%) |
|:-----------:|:------:|:------------------:|
|  DeiT-Tiny  |    -   |        72.2        |
|             |   GM   |        68.8        |
|             |   CAP  |        71.5        |
|  DeiT-Small |    -   |         79.8       |
|             |    GM  |         77.9       |
|             |   CAP  |         79.0       |
|   DeiT-Base |    -   |         81.8       |
|             |    GM  |         81.2       |
|             |   CAP  |         81.3       |

We look forward to an engaging discussion! 





Meta-review: Summary
This paper presents an approach to pruning models by looking at the correlations in the model weights. The authors reduce this problem to solving a sparse regression problem that allows them to achieve a high degree of sparsity in the final pruned model. The paper provides a good connection to theory for motivating this way of pruning and achieves a good tradeoff in performance and model weights.

Reviews & Justification
The authors addressed the reviewers concerns successfully. RwReA increased their rating to WA (didn’t mark); RkMpj’s concerns were addressed but didn’t update their rating. Overall, this paper makes a valuable addition to the model pruning.
Decision: Accept (poster)