Synergistic Patch Pruning for Vision Transformer: Unifying Intra- & Inter-Layer Patch Importance
Authors: Yuyao Zhang
Lan Wei
Nikolaos Freris
Venue: ICLR 2024 poster (2024)
Keywords: Vision Transformers
Model compression
Dynamic pruning
Primary area: representation learning for computer vision, audio, language, and other modalities

Abstract: The Vision Transformer (ViT) has emerged as a powerful architecture for various computer vision tasks. Nonetheless, this comes with substantially heavier computational costs than Convolutional Neural Networks (CNNs). The attention mechanism in ViTs, which integrates information from different image patches to the class token ([CLS]), renders traditional structured pruning methods used in CNNs unsuitable. To overcome this issue, we propose SynergisTic pAtch pRuning (STAR) that unifies intra-layer and inter-layer patch importance scoring. Specifically, our approach combines a) online evaluation of intra-layer importance for the [CLS] and b) offline evaluation of the inter-layer importance of each patch. The two importance scores are fused by minimizing a weighted average of Kullback-Leibler (KL) Divergences and patches are successively pruned at each layer by maintaining only the top-k most important ones. Unlike prior art that relies on manual selection of the pruning rates at each layer, we propose an automated method for selecting them based on offline-derived metrics. We also propose a variant that uses these rates as weighted percentile parameters (for the layer-wise normalized scores), thus leading to an alternate adaptive rate selection technique that is input-based. Extensive experiments demonstrate the significant acceleration of the inference with minimal performance degradation. For instance, on the ImageNet dataset, the pruned DeiT-Small reaches a throughput of 4,256 images/s, which is over 66\% higher than the much smaller (unpruned) DeiT-Tiny model, while having a substantially higher accuracy (+6.8\% Top-1 and +3.1\% Top-5).

Published as a conference paper at ICLR 2024
SYNERGISTIC PATCH PRUNING FOR VISION TRANS- FORMER: UNIFYING INTRA- & INTER-LAYER PATCH
IMPORTANCE
Yuyao Zhang
Lan Wei
Institute of Advanced Technology University of Science and Technology of China Hefei, Anhui, 230026, P.R.China
School of Computer Science and Technology University of Science and Technology of China Hefei, Anhui, 230026, P.R.China we i lan@ma www.st.....uu.....o. edw.ccndcccc
pastc.edu.. cn juttazhang@ma
Nikolaos M. Freris
School of Computer Science and Technology University of Science and Technology of China Hefei, Anhui, 230026, P.R.China n nr@uuscc. edu.cn cn
ABSTRACT
The Vision Transformer (ViT) has emerged as a powerful architecture for var- ious computer vision tasks. Nonetheless, this comes with substantially heavier computational costs than Convolutional Neural Networks (CNNs). The attention mechanism in ViTs, which integrates information from different image patches to the class token ([CLS)), renders traditional structured pruning methods used in CNNs unsuitable. To overcome this issue, we propose SynergisTic pAtch pRuning (STAR) that unifies intra-layer and inter-layer patch importance scoring. Specifi- cally, our approach combines a) online evaluation of intra-layer importance for the [CLS] and b) offline evaluation of the inter-layer importance of each patch. The two importance scores are fused by minimizing a weighted average of Kullback- Leibler (KI.) Divergences and patches are successively pruned at each layer by maintaining only the top-k most important ones. Unlike prior art that relies on manual selection of the pruning rates each layer, propose automated method for selecting them based on offline-derived metrics. We also propose a variant that uses these rates weighted percentile parameters (for the layer-wise normalized scores), thus leading to an alternate adaptive rate selection technique that is input-based. Extensive experiments demonstrate the significant accelera- tion of the inference with minimal performance degradation. For instance, on the ImageNet dataset, the pruned DeiT-Small reaches a throughput of 4,256 images/s. which is over 66% higher than the much smaller (unpruned) DeiT- Tiny model, while having a substantially higher accuracy (+6.8% Top-1 and +3. 1% Top-5).
INTRODUCTION
Transformers have gained popularity as backbone networks for various applications. The key to the proliferation of the Vision Transformer (ViT) and its variants lies in unified architecture that effectively tackles the long-range dependencies in images (Dosovitskiy et al. (021). However, the intricate architecture involved brings along intensive computational costs that prohibit the model deployment on resource-conssrained devices (Zheng et al.) 2022). This motivates the need for ViT compression. Existing research ViT compression has drawn inspiration from techniques used in Convolutional Neural Networks (CNNs), such as weight pruning (Chen et al. 2021b Yu & Wu, 2023 Yu al.) 2022] Zhu al., 2021). quantization (Liu et al.) (021). and compact architecture design (Chen et al. 10) There are also several dynamic methods to adjust the pruning thresholds
based on the input (Zhang & Freris] [0233 Tang et al.) [222T] Lin et al., 2020 Wang et al. 2020).
For instance, methods like channel or filter pruning aim to reduce the model size by removing unnecessary structures. However, hasty pruning of entire channels ViTs can result in information
"Corresponding author

---

Published as a conference paper at ICLR 2024
loss (Hou & Kung 2022), , as ViTs split input images into multiple patches and perform calculations on all patches in parallel. Moreover, the self-attention mechanism in ViT aggregates features using position embedding and assesses patch significance to the class token ([CLS) in different layers (blocks) of the network. The quadratic time and memory complexity associated with the number of input patches is the source of the main computational burden in ViTs.
For this reason, patch pruning becomes topical. Recent studies (Liang et al. 2022 Tang et al. 2022) indicate that certain patches in ViTs encode task-irreeevant information (such as the background) while the importance of any given patch varies across ViT blocks (see Fig Nonetheless, most existing techniques do not fully explore the redundancies across different ViT blocks (Pan et al.) 2021a Xu et al., 2022). It is thus crucial to ensure that patches critical for deeper layers are not mistakenly pruned in shallower layers. Mainstream patch pruning methods (Dong et al.
2023 Wei
cet al., 2023) employ recursive sampling techniques to select informative patches and reduce the model inference time. However, these 'static" methods (Chen et al., 2021b Fayyaz al. et al.) 2021) prune a predetermined subset of patches regardless of input image dependency. limiting their performance. In contrast, input-adaptive approaches Xu et al. (2022). like the one proposed in this paper, perform pruning during inference (adaptive to the input data).
2022 Rao
To tackle this, we propose a new method called SynergisTic pAtch pRuning (STAR) that combines dynamic evaluation of intra-layer patch importance during inference with inter-layer patch impor- tance calculated offline (using tools from model interpretability). The former is achieved by using the attention map at each block, while we employ Layer-wise Relevance Propagation (LRP) (Chefer et al. 2021) for the latter. Subsequently, the two importance scores at each layer are fused so as to prune by retaining the most important ones. Given that the scores are positive, the fusion is accomplished by viewing them as a probability mass function (pmf) and seeking to find the pmf that minimizes a weighted sum of the Kullback-Leibler (KI) divergence which admits a simple closed-form solution as the (element-wise) product of the scores raised to two powers that add to one. Apart from assessing patch importance, another crucial challenge is determining the retention rate per layer to balance compression and accuracy. In this regard, existing patch pruning methods fall into two categories. There are methods like Liang et al. (2022); Yang et al. (202I), that rely on empirical per-layer retention rate settings: this process heavily relies on the dataset at hand and may not generalize well across different tasks. Other methods, such as Hou & Kung (2022); [Tag et al. (2022); Wang et al.] (2022). use sensitivity analysis and iterative rate search, which comes at a cost of increased computation overhead.
Our method offers lightweight solution for automatically determining layer-wise retention rates. To that end, we first compute the Average Cosine Similarity (ACS) between patches at each layer (in an offline manner), which is used to capture the extent of layer-wise redundancy. This choice is motivated by previous research (Gong et al., 2021 Zhou et al. (021) showing that deeper network layers tend have higher patch similarity and, thus higher redundancy. Subsequently, we propose a rule for selecting the layer-wise retention rates that contain single hyperparameter This features a monotonicity property in two aspects: a) the retention rate decreasing with ACS (as motivated above), and b) the retention rate is increasing in It thus allows for efficient tuning of the proposed method to strike a salient balance between compression and accuracy. Additionally, we introduce a variant that leverages these rates weighted percentile parameters for the poyer-wise scores. This, in turn, gives rise to an adaptive rate selection method that is contingent on the input data.
In summary, our work introduces three key novelties: a) evaluation of inter-layer patch importances. b) fusion mechanism for integrating inter-layer and intra-layer importances, and c) new auto-tuning mechanism for layer-wise retention rates with no overhead of re- re-training.
Contributions:
1) We propose SynergisTic pAtch pRuning (STAR) for Vision Transformers, which combines dy- namic evaluation of patch importances within every single layer during inference together with offline analysis of patch importance across layers. Importance scores are fused by using a weighted exponentiation to determine the overall importance of each patch. STAR provides a more compre- hensive view of the significance of each patch for the overall process and ensures that patches crucial for deeper layers are not mistakenly pruned based on shallower layer evaluation alone.
2) STAR incorporates an efficient means for automatically selecting the pruning rate each layer. We propose simple bilinear relation of the retention rate to a) the offline metrics (ACS) and b) a single control parameter p. This relationship establishes a crucial monotonicity, enabling effective
2

---

Published as a conference paper at ICLR 2024
and efficient tunability of the proposed method to trade off compression accuracy. Furthermore, we introduce an adaptive variant of the method, which yields input-dependent retention rates by uti- lizing the previous values weighted percentile parameters with the same monotonicity property. 3) Through extensive experiments, we demonstrate superior performance in terms of both com- pression and accuracy over leading methods. Specifically, on the ImageNet dataset, achieves higher accuracy with Top-1 Acc. degradation ranging from 0.2% to 0.3% while compress- ing the GFLOPs of DeiT-Base&Ting by over 42% and 46%, respectively. The pruned DeiT-Small model achieves a throughput of 4,256 images/s, over 66% higher than the unpruned DeiT- Tiny model, while maintaining a substantial accuracy improvement of +6.8% Top-1 and +3.1% Top-5.
approach
RELATED WORK
Research efforts have been dedicated to pruning Vision Transformer (ViT), aimed at improving infer- ence efficiency and facilitating the deployment on devices with limited computational capabilities. Existing works on compressing ViTs fall into two main categories:
Pruning focuses eliminating redundant or less critical connections or weights to create a more compact and efficient network. While primarily developed for CNNs, methods based on sparse learning (Yu et al. 2022: Chen et al. (222h)) and sensitivity analysis (Yang) jet al.) 202T) have been explored to reduce model redundancy in VīT'. Nevertheless, ViT divides input images into multiple patches, and computations are carried out in parallel across all patches. Pruning entire channels is static for all input, which may lead to reduction in network capacity and limit the expressive power of the model (Chu et al.] [022] Hou & Kung 2022). In response this
Structure/Chamme
challenge, patch pruning has been proposed and it gives greater flexibility by allowing the dynamic selection of a subset of patches deemed useful for each layer.
Patch Pruning aims to remove redundant or less informative patches from the input image. This is based on the characteristic that ViT can process an arbitrary length of the input patch. It capitalizes on the self-attention mechanism in Transformer, which can thus effectively capture dependencies between patches in different layers (Peng et al. 202I). Tang et al. (2022) uses a top-down approach to compute importance scores for each patch by approximating its impact on the reconstruction error. Liang et al. (202)) introduce a fused patch representing the patches removed in each layer. Xu et al. 2022 keep patches with low-frequency components to convey more critical information to subsequent layers. However, all the aforementioned methods evaluate patch importance at a given layer and thus may fail to capture the cross-layer importance. [Chnn al. (2023) automatically select compression rates by incorporating a by hyperparameter A. Nevertheless, requires retraining for different compression targets and does not address inter-layer dependencies explicitly.
regularizer into the loss controlled
To address this limitation, we propose a novel approach that incorporates inter-layer importance (inspired by model interpretability analysis) with intra-layer importance, offering more compre- hensive and direct view of the significance of each patch for the overall task. Besides, most methods rely on manually tuning the pruning rates at each layer Yu et al.) 2022 Yu & Wu 202Tb Zhu al, (02T). In contrast, STAR automates the pruning rate selection by pre-computing the ACS between patches within each VIT block.
et al.)
3 ATTENTION MAP FOR DYNAMIC INTRA-LAYER PATCH EVALUATION
The attention operator at the 1-th (1 S Sig L) Transformer block for the h-th (1 S h S H) head is:
Attention(Q K V/") = Soottmax x+
VA
(1)
V
where Q', K,, Vg are the query, key, and value of the h-tt head in the I-th layer, df = d/HH with d the
xx/xx is the attention map. Touvron et al.
input dimension and H the heads number, and Softmax
Val
202T) append the class token [CLS] to the tokens (patches) before the first layer. This traverses the ViT blocks and is used at the end to predict the class. The [CLS] plays the role of synthesizing information within layer, and the attention map of it to the remaining tokens within layer can
be regarded as the contribution of each patch to the classification outcome. The [CLS] attention to
other tokens in the 1-th ViT block and h-th head can be written as (Vaswaní al. 2017
Attention/ccs) (g K/A Vih)
Softmax
Selne K!.
V =ttn/j) V
(2)
3

---

Published as a conference paper at ICLR 2024
(e) Figure 1: Visualization of class attention in DeiT-Base using modified LRP for inter-layer patch importance. (a) is the original image; (b) and (c) are the visualization of the importance (plotted by color code) of the image patches (tokens) at the third and twelfth Transformer layers (blocks), respectively. For example, the patch within the red square is considered unimportant (blue) for classification in the third layer but becomes important (red) in the twelfth layer. It is thus crucial to ensure that patches critical for deeper layers are not mistakenly pruned in shallower layers.
(a) Original
Block
where qlass denotes the query vector of [CLS]. As mentioned above, the [CLS] of each layer aggre- gates the contributions of all image tokens for the classification task, as it can be viewed by treating ALtention|cLs]
linear combination of 1/^ [uf, v/ ...,.. e\} value vectors, that correspond to the N tokens. Therefore, the corresponding coefficient aftm can be considered as the impor- tance of the i-th token at the [-th layer for the classification outcome for a given input, as in Liang et al. (2022); [Wang al. (2022). By collecting the results from all attention heads, the Intra-layer importance score in the 1-th layer is obtained by averaging as: ( Σi attn((.)-
Note that attn(i) can be calculated the forward process (i.e., sequentially, during inference), and the pruned patches are discarded from all subsequent Transformer layers; this directly reduces the computational costs involved (see Fig. 2 for an illustration). In our ablation study, the first part of Table demonstrates that only using the Attention map attn")) for patch pruning as in (Wang et al, 2022) can seriously affect the classification accuracy. The main reason for the model impairment is that pruning the output of each layer based on intra-layer information is rather aggressive. Tokens with low importance for [CLS] in the shallow blocks may be more important in the deeper blocks, which creates confusion in the pruning process because the intra-layer important scores only mea- sure the importance for [CLS] within a single layer. Nevertheless, once patches are pruned, they cannot be inserted back. This motivates us to explore inter-layer dependencies to capture the overall importance of a patch in the whole model, which is discussed in the next section.
4 INTER-LAYER PATCH IMPORTANCE USING LRP
In this section, we describe how inter-layer patch importances can serve to improve compression. First, we present the key challenges and considerations that motivate us. Fig iillsstate the contri- bution of image patches to the final classification task at various layers within the DeiT-Base model, leveraging a modified LRP for inter-layer patch importance. This reflects the significance of each image patch to the [CLS] at the last layer and this visualization illustrates that the significance of a given patch varies across VIT blocks, which serves as motivation for evaluating inter-layer im- portance throughout the entire classification task. For instance, patches with low importance for (CLS] in the shallow blocks (see Fig TT) may become more important the deeper blocks (see Fig[Tp) Many existing methods do not fully exploit the redundancies present across different ViT blocks. This oversight can lead to essential patches required for deeper layers being mistakenly pruned based solefy on evaluations from shallower layers. This serves as the motivation for combin- ing dynamic evaluation of intra-layer patch importance scores within each individual layer during inference with offline calculations of lnter-layer patch importance across layers. This combined approach provides more comprehensive assessment of patch importance within ViTs.
In the following, we will recap LRP first, and then the modifications we made on it. Details of the modified LRP are described Appendix B The Layer-wise Relevance Propagation (LRP) method, has proven to be effective in interpreting neural networks (Bach et al. 2015). A variant of LRP has been specifically designed for Vision Transformer (Chefer et al. 2021) using the GELU acti- vation (Hendrycks & Gimpel| 2016). This analysis can give both positive and negative values. We only consider the relevance scores that have a positive value as described by Chefer et al. (202T). In our modification, a) instead of operating at the pixel level, we carry additional aggregation of
4

---

Published as a conference paper at ICLR 2024
multiple pixels' relevance belonging to the same patch and b) rather than focusing solely captur- ing the relationship between one pixel and one class, we have adapted the original LRP to capture the correlation between one patch and multiple classes.
The calculation inter-layer patch importance Si)) is carried ing dataset (with no overhead to the inference). It serves to assess the importance of each patch from the viewpoint of the overall classification process and obtain statistical information based on the dataset. During inference, these pre-competed inter-layer patch importances are combined with intra-layer importances, which are obtained dynamically based on the imput for the [CLS] attention map in each layer to achieve complementarity. In the subsequent section, we delineate our approach for fusing the intra-layes and inter-layer importance scores.
an offline fashion on the train-
5 SYNERGISTIC PATCH PRUNING (STAR) FOR VITS
Intra-layer analysis derives the importance score of each image patch for the class token [CLS] within layer based on the linear relationship between the attention map and the value matrix in 2). However, the linear relationship is valid within single layer, and not for whole model (due to the Softmax operation). Thus, intra-layer scores cannot fully capture the patch importance for overall classification task. contrast, the inter-layer analysis by LRP reflects the contribution of each image token to the [CLS] the last layer. In summary, the intra-layer and inter-layer importance information can complement each other and synthesize more comprchensive criteria for patch pruning. The inter-layer method can compensate for the lack of inter-layer information in the intra-layer method by pre-computing scores offline using Alg. ii Appendix The intra-layer method operates sequentially an online manner (see steps 5,6 of Alg. D. and so does our proposed method, STAR.
(a) Patch pruning for VT
(b) Ollline Evalustion
Reietet
Forward
1-th
th
Discoller
WIT
Propagation
Block
Original
retention_ reeee=00%
retention, rafec:75%
Aud: A--1 Azza)
(c) Online Evaluation
(d) Synergis Tie pAtch pRuning (STAR)
adtelo
Intra tayer Importarnd Scores
()
Intor-ayer Importance Bookes
Fusion
Multi-head Sell-atlention Block
]
x
Oulput
Pruning
X).1
Figure 2: (a) Visualization of patch pruning for VIT (according to the listed retention rates, from the original 16 patches, 8 patches are kept in the second layer, and 6 at the third). (d) Overview of SynergisTic pAtch pRuning (STAR). Inter-layer importance scores (b) for each layer are com- puted offline using the LRP method during back-propagation on the training dataset. Intra-layer importance scores (c) are obtained online (i.e., during inference) using the attention map of each layer's [CLS]. The inter-layer importance score Simter and the intra-layer importance score Simta, cor-
giste (1-a), Pruning is conducted responding to the i-th token at the /-th block are fused ( ((..))
by retaining the top-k important patches based on the fused scores.
5.1 FUSION OF
IMPORTANCE SCORES
We opt to carry fusion of the intra-layer and inter-layer scores (see Fig. 2 and Alg. [.. so as to capture the impact of patch pruning on single-layer basis as well as incorporate inter-layer rela- tions pertaining to the whole classification task. First, note that both scores are positive (due to the Softmax operation in (2) and the restriction to positive values in Therefore, after normalization, they can be viewed probability mass functions (pmfs). For simplicity, we denote by p² the pmf corresponding to lntre-layer scores and by p² the pmf for inter-layer scores. The Bellbackk-eibblle (KL) divergence is widely used distance for pmfs, that is defined as KL(p, Σ, P; log pt 9:
for pmfs p. g with common support. Our fusion method amounts to calculating weighted centroid
5

---

Published as a conference paper at ICLR 2024
(with parameter [0, 11) with respect to the KL divergence using the following formulation:
minimize a (plle") + - a) (pll²"). s.t. p. 200 E,
(3)
where a is a hyperparameter that balances the contribution of intra-/inter-lat layer scores. This problem admits closed- form solution:
(pt) (pt)
Pi Σ, (p!) ". (p?) (p?)'_a
(4)
that is glusel Simmn x Simer(1-a) (the derivation is provided in Appendix Cp. Given the retention rates, layer-wise pruning is carried by maintaining the top- important patches in the (-th layer (step 9 of Alg. D note that [CLS] is excluded from this operation), sequentially. In the following, we provide a method to automatically select retention rates each layer based metrics that obtained offline (i.e., as a pre-processing step).
Algorithm/ SynergisTic Tic pAtch pRuning (STAR)
Input: Training dataset D, test dataset ε, Vision Transformer T with L layers, hyperparameter for fusion, average cosine similarity ACS (pre-computed offline from the training data), hyperparameter P controlling the FLOPs Drop.
1: gimkr +- InteriS V7, [Alg. 2].
2: for e & do
3: Initialize the input of the first block X1 =
4: for = 1,. do
5:
Calculate attmli Softmax
Vat
6: Calculate Sig H Σ h=1 albrity
7:
Calculate Stesed
S a (1)
x Simer(1
(1)
8:
Set ACS, ACCS ACS: + ACS, AC18;
ACS,, ACS,
Option 1: Static retention rate selection
Keep p: patches with top-k (S scores.
Option 2: Adaptive retention rate selection
9:
(() + Normalize and sort sifised
(1)
Calculate r = idx (CDF((f 2
Keep patches with top-k k (Stized) scores.
10:
end for end for
11:
Output: The pruned Vision Transformer T'.
5.2
DESIGN OF THE RETENTION RATES
Fig. shows the visualization of the contribution of the image patches to the final classification task at different layers: Fig. [T illustrates that the attention scores of image patches [CLS] usu- ally have a clustering effect at a larger depth of the network, while they are relatively scattered in a shallow layer (Fig. [T).. This indicates that as the network gets deeper, there is an increasing number of patches that can be pruned due to their minimal impact on the final classification task. In our proposed method, each layer uses a different retention rate pl (thus, the number of retained patches up until layer the running product p1 patches as the network goes deeper (Zhou et al. 2021) motivates us to employ the average cosine similarity (ACS) calculation among the image patches X, E Nxd produced by each ViT block to automatically determine the retention rates Pt. Specifically, ACS is calculated as follows:
Pi). The rise in cosine similarity between image
N
Xi X
ACS: N(N
(5)
|||||a|||X||2
2=0 1=1+1
Based on this, we establish a linear relationship between the retention rate Pr each layer and the ACS, which can be used for static retention rate selection (Option in Step 9 of Alg, [ static means that these rates are the same for any input to the model), i.e., = a ACS, +bb We select the
parameters (a. b) based on two principles: 1) since the first layer is the most sensitive to pruning, retain all patches (i.e. P1 = 1) and 2) since the last layer is typically less sensitive, we set Pt. = P. where p E (0, 1) be used as the single control parameter steer the desired FL.PPs Drop. By

---

Published as a conference paper at ICLR 2024
solving the resulting 2 x 2 linear system: 1 Pi a +b, = Pz a ACSS obtain the expression in Step 8 of Alg. [ Note that this is bilinear in (ACS,, p) (i.e., is linear to each one for the other fixed). Given that ACS, is the smallest value across experimentally), we can deduce a monotonicity property in that for all I: a) Pi decreases with ACS, (since / 1) and b) Pt increases with p. for all 1 A 1 (since ACS₁ > ACS)). This is a desirable trait, as it allows for efficiently tuning the method to achieve a target overall FLOPs reduction (c.g., using bisection), in order to trade off compression vs. accuracy.
L...., L (this is verified
Additionally, introduce (Option 2 in Step 9 of Alg. [T adaptive means that the retention rate depends on the input). This done by using the calculated value Pr as weighted percentile parameter for the normalized fused importance scores (CDF stands for cumulative distribution function). The same monotonicity property holds for this variant and additionally, we prove that its compression is no less than that of Option 1 (see Appendix D
alternate adaptive retention rate selection, which we call a-STAR
EXPERIMENTS
STAR is evaluated on the benchmark ImageNet (ILSVRC2012) dataset using two popular ViT mod- els, namely DeiT (Touvron et al., 2021) (three differentt sizes: DeiT-Tiny, DeiT-Small. DeiT-Base; the code is modified based on the study of Meta Research), and LV-ViT (Jiang et al., 2021) (two dif- ferent sizes: LV-ViT-S, LV-ViT-M). All experiments are deployed with Py NVIDIA A100 & 3090 GPUs. Instead of training the network from scratch, we directly use the pre-trained models, The pruned models are fine-tuned for 120 epochs with hard distillation (Touvron et al. (021) of their corresponding original models. All throughputs are measured during interence on an A100 GPU with a batch size of 128 and FP32. The learning rate is reduced from 2e-5 to 2c-9 with a cosine schedule, We refer the reader to Appendix E for the experimental setting details. Our code is available here
6.1
EXPERIMENTAL RESULTS
We compare our proposed method with several representative model compression methods, includ-
ing SCOP (a technique inspired by CNN channel pruning) (Tagg et al. 2020). PoWER (Goyal
cet al. 2020 VTP (huu et al. 2021), HVT (Pan et al. 2021b), SAViT (Zheng et al. 2022). IA-
RED PPn et al. 202 EVIT (Liang et al. 2022), and Patch Slimming (PS) (Tang et al. 2022
multi-dimensional pruning CP- ViT (Song et al. 2022). and VTC-LFC (Wang et al. [2022] token
merging pruning ToMe (Bolya et al. 2023). Through extensive experimentation, it is portrayed that
STAR achieves formidable compression while also maintaining high model accuracy, as shown in
Table For full results, see Appendix B
For the DeiT- Base model. STAR achieves substantial reduction of 42.0% in FLOPs, with a negligible drop of only 0.3% in Top-1 Acc. and O. 1% in Top-5 Acc. Even at a higher level of FLOPs reduction, namely 47.2% (+4.0% over VTP), the drop in Top-5 Acc. is only 0.5%, and the drop in Top-1 Acc. is 0.8%. We also assessed the acceleration in inference speed using a single 1100 GPU with batch size of 128. The DeiT-Base model under the two mentioned pruning levels achieved speedup of 69.5% and 84.9% after pruning.
Results on DeiTs:
The DeiT-Small model originally has much lower computational cost of 4.6 GFLOPs than DeiT- Base but still greatly benefits from pruning with STAR. STAR achieves a reduction of 43.5% with corresponding speedups of 83.9% and 104.5% on a single A100 GPU, with minimal accuracy drop (0.4%/0.6f 60% for Top-1 and 0.5%/0.7% 70% for Top-5). These speedups surpass other methods, and so do the respective accuracies. The merits are further accentuated by measuring the achieved throughput (the number of images that can be processed per second). Remarkably, the pruned DeiT- Small reaches a throughput of 4, 4,080.6 images/s, which over 60% higher than the much smaller (unpruned) DeiT-Tiny model, while having a substantially higher accuracy (+7.0% Top-1 and +3.2% Top-5). Even for the smallest-scale DeiT-Timy model, our method showcases a twofold increase in throughput by reducing the computational cost just 0.7 GFLOPs. Despite this significant reduction in computation, the degradation in Top-1 Acc. is minimal, at only 0.2%. Compared to VTC-LFC, it exhibits a +27.1% % speedup and a 1.0% improvement in Top-1 Acc. Last but not least, even for cases where our method has the same FLOPs reduction as another method (i.e., SCOP on DeiT- Base/-Small), in addition to superior accuracy, it achieves much higher throughput because of its lightweight nature as an online pruning method.
Results on VV-v:Ts: We conducted experiments using two LV- models. For the medium-sized LV-VIT-M model, STAR achieved Top-1 Acc. of 83.3% and Top-5 Acc. of 96.4%. This is an
7

---

Published as a conference paper at ICLR 2024
Table 1: Experimental results of SynergisTic pAtch pRuning. 'STAR' means using the static re- tention rate selection (Option I in Step 9 of Alg. 2) while "a-STAR refers using the adaptive retention rate selection (Option 2). The hyperparameter (Alg. D controls the compression rate. 'FLOPs denotes the FLOPs reduction ratio, while the throughput measures the number of images that can be processed per second (including the cost of both online patch pruning and inference). The speedup (i.e., increase of throughput) is obtained on A100 GPU. The marker indicates the result is from the corresponding articles. The best results in each column are depicted in boldface.
Model
Method
P
Top-1 Acc.
Top-5 Acc.
GFLOPs
P
Throughput Specdup (%)
Baseline
818
95.6
17.6
1,05L6
IA-RED2
80.3
95.0
11.8
33.0
1,380.1
31.2
EVIT
81.3
95.3
11.6
34,1
1,454.7
38.3
CP-VIT
41.6
DeiT-Base
SCOP
79.7
94.5
10.2
42.0
1,504.7
43.1
STAR (Ours)
0.75
81.5
95.5
10.2
42.0
1,782.8
69.5
a-STAR (Ours)
0.75
81.4
95.5
10.0
43.2
1,867,0
77.5
VIP
1,586.0
50.8
STAR (Ours)
0.7
$1.0
95.1
9.3
47.2
1,944.5
84.9
a-STAR (Ours)
0.7
80.8
95.0
9.0
48.9
2,028.2
92.8
Baseline
79.8
95.0
4,6
1,995.6
IA-RED
2,566.4
28.6
SCOP
77.5
93.5
43.5
2,823.8
41.5
PoWER
78.3
94.0
2.7
41.3
2,939.5
47.3
DeiT-Small
ToMe
79.4
41.3
3,346.7
61.7
STAR (Ours)
0.75
79.4
43.5
3,670.8
83.9
a-STAR (Ours)
0.75
79.3
94.4
2.5
45.7
3,843.7
92.6
HVT -...............................
78:0
93.8
24
47.8
2,83577
"22TT"
STAR (Ours)
0.7
104.5
s-STAR (Ours)
0.7
79.0
94.2
52.2
4,256.9
113.3
Baseline
72.2
91.1
1.3
2,544.0
SAViT
70.7
0.9
30.8
ToMe
71.4
3,137.1
57.2
DeiT-Tiny
VTC-LFC
71.0
90.4
0.8
41.7
4,352.8
71.1
STAR (Ours)
0.8
72.0
90.7
0.7
46.2
5,042.9
98.2
a-STAR (Ours)
0.8
46.2
5,104.8
99,8
Haseline
1,061.6
LV-VITM
EVIT
82.9
95.8
8.5
32.5
1,820.6
71.5
STAR (Ours)
0.8
83.3
96.4
6.7
46.8
1,922.6
81.1
a-STAR (Ours)
1,971.7
85.7
Baseline
83.3
1,68L.3
PS-LV-ViT-S EVIT
82.4
4.7
27.7
82.5
96.2
3.9
40.0
2,374.0
41.2
LV-VI-SS
VTC-LFC
STAR (Ours)
0.65
82.7
96.2
3.2
50.8
3,353.2
99.4
a-STAR (Ours)
0.65
82.5
96.1
3.1
52.3
3,439.8
104.6
increase of +0.4% over EVIT, while STAR also achieves +9.6% higher speedup. Similarly, the experimental results for LV-ViT-S outperform other approaches across all evaluation metrics, achieving high acceleration of 99.4%.
Additional results a-STAR: Compared to STAR, a-STAR adaptively adjusts the retention rate for different inputs. Notably, a-STAR achieves higher compression and throughput, while STAR demonstrates better accuracy when using the same p. The only overhead of a-STAR is the additional calculation of CDF after sorting, which is negligible. For instance, in the
of DeiT-Small with = 0.75, a-STAR exhibits a +2.2% increase in flops drop and +8.7% in throughput compared to STAR. However, STAR maintains +0.1% % higher Top-1 and Top-5 accuracy than a-STAR.
6.2 ABLATION STUDY
To further analyze the impact of different components on the proposed method, we conducted sep- arate experiments to test the influence of the intra-layer and inter-layer scoring mechanisms, using only intra-layer scores together with our automatic pruning schedules based on ACS, as well as effectiveness of KL fusion. All results reported in this section are obtained before fine-tuning.
Effectiveness of intra-layer inter-layer scores: For the former two parts Table 2, the re- tention rates at each layer were derived empirically using product rule. A significant decrease in classification accuracy observed for using intra-layer scores only for patch pruning. With a GFLOPs reduction to 10.2 (as indicated in the last row of the Intra-layer pruning part in the table), the Top-1 Acc. drops by 2.4% and the Top-5 Acc. drops by 1.4%. Furthermore, when aiming for higher compression rates with retention rates of 0.5, 0.25 0.52. and 0.125 0.53 only layers
8

---

Published as a conference paper at ICLR 2024
Table 2: Ablation for the effectiveness of different modules in STAR on the ImageNet dataset for DeiT-Base. Intra-/Inter-layer pruning refers to using only intra-/inter-layer importance scores in the top-k selection for pruning. Furthermore, the pruning schedules are designed manually: the prune layers indicate the selected layers for patch pruning (no pruming carried in other layers), and retention rate represents the patch keep ratio for each selected layer. Top-1 Acc. and Top-5 Acc. reported in the table reflect the accuracy without fine-tuning. An Inter-layer pruning sample of T 10 rounds is used to get the inter-layer information. ACS method refers to automatically determining the layer-wise wise retention rate using the mechanism presented in Sec. 5.2 and only intra- layer importance, while STAR and a-STAR additionally use the fusion.
Method
prune layers
retention rate
batch size
Top-1 Acc.
Top-5 Acc.
GFLOPs
DeiT-Base
81.8
95.6
17.6
[4.7,10]
& & 0.5
71.1
88.4
7.8
Intra-layer pruning
[5.8,10]
0.7 & 0.7 & 0,73
78.0
93.1
11.0
[4,7,10]
0,7 & 0.7 & 0,7
79.4
94.2
10.2
[5,8,10]
0.7 & 0.7 & 0.7
64
64_1
79.6
11.0
Inter-layer Pruming
[5.8, 10]
0.70 & 0.7 & 0.73
128
77.3
93.1
11.0
[4,7,10]
0,7 & 0.7 & 0.73
128
78.2
93,9
10.2
0.65
76.6
92.6
8.4
ACS
0.7
78.2
93.6
9.3
0.75
79.7
94.5
STAR (Ours)
0.75
128
80.0
94.7
10.2
a-STAR (Ours)
0.77
128
80.2
94.8
10.2
4, 7, and 10, respectively, the Top-1 Acc. drops by unacceptable 10.7% compared to the un- pruned model, and the Top-5 Ace. decreases by 7.2%. This illustrates that intra-layer scores alone ineffective, they fail to protect those patches critical for deeper layers from being pruned at shallower layer, as explained in Sec. 4 Besides, pruning based solely on inter-layer information is sufficient either. For instance, when the GFLOPs drop to 10.2, the Top-1 Acc. decreases by 3.6% and Top-5 Acc. decreases by 1.7% compared to the original model. This is because this approach alone lacks any adaptability the input (since the scores are obtained through offline aggregation). These findings serve in support of our choice to fuse the scores.
Influence of automatic pruning schedules based on ACS: The ACS module is used to automati- cally determine the layer-wise retention rate based on the target compression rate (p) at the last layer, as explained in Sec. 5.2 In Table 2 we used this method without fusion (i.e., only on intra-layer scores). Compared to the manually chosen pruning schedules (Intra-layer pruning part of Table 2) the ACS-based generation achieves better performance for comparable FLOPs reduction. For in- stance, by setting p 0.75, ACS achieves the same GFLOPs (10.2) with improvement (+0.3%) in both Top-1 and Top-5 Accuracy. We sampled 500 images to calculate the ACS between patches in our experiment. Details about using different data sizes to calculate ACS are listed in Table 6 Appendix
The last part of Table 2 employs the ACS module on the fusion result of intra-/inter-layer importance scores. We present two variants: STAR and a-STAR, corresponding to the options of static and dynamic retention rate selection outlined in Alg. (Seep 9). For the static ratio setting (STAR), our results demonstrate improvements in both Top-1 Acc. (+0.6%) and Top-5 Acc. (+0.5%) compared using intra-layer importance scores alone. With the same GFLOPs (10.2), the adaptive pruning strategy (a-STAR) achieves +0.2% 1% additional improvement on Top-1 and Top-5 Acc. over STAR. These findings underscore the effectiveness of fusing intra-/inter- layer scores in the context of patch selection. In our experiments, we use 0.15 in DeiT models and 0.3 for LV-ViT models. Details the selection the hyperparameter a the KL fusion module of STAR are listed in Table 3 Appendix
Effectiveness of KL fusion:
E
CONCLUSION
STAR is dynamic patch pruning method tailored for Vision Transformers (ViTs). It combines intra- layer importance scores, which capture the importance of patches at specific layer, with inter-layer importance scores that consider the variable impact of patches across layers on the final classifi- cation outcome. By automatically designing pruning schedules based on these fused importance scores, STAR substantially reduces computational costs while maintaining high accuracy. Numer- comparative experiments the DeiT and LV-ViT models illustrated improvements in terms of both higher compression and accuracy. Besides, STAR is lightweight as it can be unraveled from the consistently higher throughput it achieves (even for common FL.OPs reduction).

---

Published as a conference paper at ICLR 2024
REFERENCES
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Robert Müller, and Wojeiech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, (0(7))c0130140, 2015.
Daniel Bolya, Cheng Yang Fu, Xiaoliang Dai, Peizhao Zhang. Christoph Feichtenhofer, and Judy Hoffman, Token Merging: Your ViT But Faster. In ICLR, 2023.
Hila Chefer, Shir Gur, and Lior Wolf. Transformer interpretability beyond attention visualization. In CVPR, pp. 782-791, 2021.
Mengzhao Chen, Wenqi Shao, Peng Xu, Mingbao Lin, Kaipeng Zhang, Fei Chao, Rongrong Ji, Qiao, and Ping Luo. DiftRate: Differentiable Compression Rate for Efficient Vision Trans- formers. In ICCV, 2023.
Minghao Chen, Houwen Peng, Jianlong Fu, and Haibin Ling, Autoformer: Searching transformers for visual recognition. In ICCV, pp. 12270-12280, 2021a.
Tianlong Chen, Yu Cheng, Zhe Gan, Lu Yuan, Lei Zhang, and Zhangyang Wang. Chasing sparsity in Vision Transformers: An end-to-end exploration. In NeurIPS, pp. 19974-19988, 2021b.
Yun Chu, Pu Li, Yong Bai, Zhuhua Hu, Yongqing Chen, and Jiafeng Lu. Group channel pruning and spatial attention distilling for object detection. Applied Intelligence, pp. 1-19, 2022.
Peiyan Dong, Mengshu Sun, Alec Lu, et al. HeatViT: Hardware-Efficient Adaptive Token Pruning for Vision Transformers. In IICCA, pp. 442-455, 2023.
Alexey Dosovitskiy, Lucas Beyer, and Alexander Kolesnikov. An Image is worth 16x16 words: Transformers for Image Recognition at Scale. In ICLR, 2021.
Mohsen Fayyaz, Soroush Abbasi Koohpayegani, Farnoush Rezaei Jafari, Sunando Sengupta, Hamid Reza Vaezi Joze, Eric Sommerlade, Hamed Pirsiavash, and Jürgen Gall. Adaptive token sampling for efficient vision transformers. In ECCV, pp. 396-414, 2022.
Chengyue Gong, Dilin Wang, Meng Li, Vikas Chandra, and Qiang Liu, Vision transformers with patch diversification. arXiv preprint arXiv:2104. 12753, 2021.
Saurabh Goyal, Anamitra Roy Choudhury, Saurabh Raje, Venkatesan Chakaravarthy, Yogish Sab- harwal, and Ashish Verma. POWER-BERT: Accelerating BERT inference via progressive word- vector elimination. ICML, pp. 3690-3699, 2020.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (GELUs). arXiv preprint 086666 2016.
Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, Dawn Song, Jacob Steinhardt, and Justin Gilmer. The many faces of robustness: A critical analysis of ouitt--distribution generalization. In ICCV, 2021.
Zejiang Hou and Sun- Yua-Yuan Kung. multi-dimensional Vision Transformer compression via depen- dency guided Gaussian process search. In CVPR, pp. 3669-3678, 2022.
Zi-Hang Jiang, Qibin Hou, Li Yuan, Daquan Zhou, Yujun Shi, Xiaojie Jin, Anran Wang, and Jiashi Feng. All tokens matter: Token labeling for training better vision transformers. In NeurIPS, pp- 18590-18602, 2021.
Youwei Liang, Chongjian Ge, Zhan Tong. Yibing Song, Jue Wang, and Pengtao Xie. Not all patches are what you need: Expediting vision transformers via token reorganizations. In ICLR, 2022.
Tao Lin, Sebastian U Stich, Luis Barba, Daniil Dmitriev, and Martin Jaggi. Dynamic model pruning with feedback. arXiv preprint arXivv2006.07253, 2020.
Zhenhua Liu, Yunhe Wang, Kai Han, Wei Zhang, Siwei Ma, and Wen Gao. Post-training quantiza- tion for vision transformer. In NeurIPS, pp. 28092-28103, 2021.
10

---

Published as a conference paper at ICLR 2024
Grégoire Montavon, Sebastian Lapuschkin, Alexander Binder, Wojciech Samek, and Klaus-Robert Müller. Explaining nonlinear classification decisions with deep Taylor decomposition. Pattern Recognition, pp. 211-222, 2017.
Bowen Pan, Rameswar Panda, Yifan Jiang, Zhangyang Wang, Rogerio Feris, and Aude Oliva. IA- RED Interpretabliiy-AAaare Redundancy Reduction for Vision Transformers. In NeurlPS, pp- 24898-249111 2021a.
Zizheng Pan, Bohan Zhuang, Jing Liu, Haoyu He, and Jianfei Cai. Scalable vision transformers with hicrarchical pooling. In ICCV, pp. 377-386, 2021b.
Zhiliang Peng, Wei Huang, Shanzhi Gu, Lingxi Xie, Yaowei Wang, Jianbin Jiao, and Qixiang Ye. Conformer: Local features coupling global representations for visual recognition. In ICCV, pp. 367-376, 2021.
Yongming Rao, Wenliang Zhao, Benlin Liu, Jiwen Lu, Jie Zhou, and Cho-Jui Hsich. Dynamic Efficient vision transformers with dynamic token sparsification. NeurlPS, pp. 13937-13949, 2021.
Zhuoran Song, Yihong Xu, Zhezhi He, Li Jiang, Naifeng Jing, and Xiaoyao Liang. CP- VTP: Cascade Vision Transformer Pruning via progressive sparsity prediction. arXiv preprint arXiv:2203.04570, 2022.
Ychui Tang, Yunhe Wang, Yixing Xu, Dacheng Tao, Chunjing Xu, Chao Xu, and Chang Xu. SCOP: Scientific control for reliable neural network pruning. In NeurIPS, pp. 10936-10947, 2020.
Ychui Tang, Yunhe Wang, Yixing Xu, Yiping Deng, Chao Xu, Dacheng Tao, and Chang Xu. Mani- fold regularized dynamic network pruning. CVPR, pp. 5018-5022 2021.
Yehui Tang, Kai Han, Yunhe Wang, Chang Xu, Jianyuan Guo, Chao Xu, and Dacheng Tao. Patch slimming for efficient Vision Transformers. In CVPR, pp. 12165-12174, 2022.
Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles, and Hervé Jégou. Training data-efficient image transformers & distillation through attention. In ICML, pp. 10347-10357, 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurlPS, volume 30, 2017.
Yulong Wang, Xiaolu Zhang, Xiaolin Hu, Bo Zhang, and Hang Su. Dynamic network pruning with interpretable layerwise channel selection. In AAAI, pp. 6299-6306, 2020.
Zhenyu Wang, Hao Luo, Pichao Wang, Feng Ding, Fan Wang, and Hao Li. VTC-LFC: Vision transformer compression with cowffrequency components. In NeurlPS, volume 35, pp. 13974- 13988, 2022.
Siyuan Wei, Tianzhu Ye, Shen Zhang, Yao Tang, and Jiajun Liang. Joint Token Pruning and Squeezing Towards More Aggressive Compression of Vision Transformers. arXiv preprint arXiv:2304. 10716, 2023.
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. In AAAL, pp. 2922-299222 2022.
Huanrui Yang, Hongxu Yin, Pavlo Molchanov, Hai Li, and Jan Kautz. NViT: Vision Transformer compression and parameter redistribution. arXiv preprint arXiv:2110.04869, 2021.
Hao Yu and Jianxin Wu. A unified pruning framework for vision transformers. Science China Information Sciences, 66(7):1-2, 2023.
Shixing Yu, Tianlong Chen, Jiayi Shen, Huan Yuan, Jianchao Tan, Sen Yang, Ji Liu, and Zhangyang Wang. Unified visual transformer compression. In ICLR, 2022.
11

---

Published as a conference paper at ICLR 2024
Yuyao Zhang and Nikolaos M. Freris. Adaptive filter pruning via sensitivity feedback. IEEE Trans- actions on Neural Networks and Learning Systems, pp. 1-13, 2023. doi: 10.1109/TNNLS.2022.. 3246263.
Chuanyang Zheng, Kai Zhang, Zhi Yang, et al. SAVIT: Structure-Aware Vision Transformer Pruning via Collaborative Optimization. In NeurIPS, pp. 9010-9023, 2022.
Daquan Zhou, Bingyi Kang, Xiaojie Jin, Linjie Yang. Xiaochen Lian, Zihang Jiang, Qibin Hou, and Jiashi Feng. DiepVIT: Towards Deeper Vision Transformer. arXiv preprins arXiv:2103. 1886, 2021.
Mingjian Zhu, Yehui Tang, and Kai Han. Vision transformer pruning. arXiv22104.08500, 2021.
arXiv preprint
12

---

Published as a conference paper at ICLR 2024
APPENDIX
This appendix is composed of five parts. Section presents a detailed description of the Vision Transformer (ViT) architecture. The algorithm of using (a slight modification of) LRP to calculate the inter-layer patch importance is described in Appendix B The details about the derivation of the fusion mechanism are listed in Section C while the adaptive retention rate selection is discussed in Section D Finally, the full experimental results are presented in Section
A PRELIMINARIES
A Vision Transformer (ViT) block includes a multi-head self-attention (MSA) block and a multi- layer perceptron (MLP) block. The input image ' DRDWXC size D W and channel number C' is reshaped into flattened patches x!²) E Nx(('))) the image is split into N = (D-W) patches of size P P that are treated the same way as tokens (words) in an NLP application.
The patches are then projected into d-dimensional embedding space to obtain X E Nxd Besides, (Dosovitskiy al., 202I) proposed add a learnable embedding the sequence of patch embeddings as a class token [CLS]. Notice that since the Transformer block does not limit the size of input N, always possible add a class token before data processing for Transformer models that do not inherently have [CLS]. The [CLS] serves to aggregate patch information and is directly responsible for the classification task, thus the final input that includes [CLS] is given by Xo (N++1)xd At the 1-th (1 S S L) block, the MSA and MLP modules operate as follows:
11
X MSA (XI-1) + X1-1 = Concat Softmax
V
+ +
Vap
(6)
Xi MLP (X1) (X/W)) W? + X/,
where Q = =X K = X and VAh 1 are the query, key, and value of the h-th head in the 1-th layer. Note that X₁ E (N++1)xd for all l,... LL and the dimensions of the weight matrices are given by: w/1.. E Rdxd,,wwh- w.h.h e Rdxds whe E Bdddd dy dę = d, 4 = d/ H. where H is the number of heads. After (column-wise) concatenation, a learnable projection Wo is applied to the multi-head structure. Wi and W? are the weights for the MLP block and é represents the activation function (e.g., GELU) that is applied element-wise. The above description shows that the ViT block can operate for an arbitrary number of input patches. Thus, it is feasible and reasonable to reduce the amount of model computation by reducing the number of patches, concept typically referred to patch pruning.
B MODIFIED LRP FOR INTER-LAYER PATCH IMPORTANCE
In this section, we present more details on the modified LRP for capturing inter-layer patch impor- tance, The relevance propagation in LRP follows the Deep Taylor Decomposition (Montavon al.) 2017
Σ (X,, W:) Ri
R = 9 (X, W. R42)
dxl LX(X,, W.)
where E {1,..., L} is the layer index in network and (X,X, Wi) is the 1-th layer's operation the input feature map X, with weight W,; 2/f refers the j-th element of the input and R2 is the j-th relevance value in layer I. For Vision Transformer using the GELU activation, this analysis can give both positive and negative values. We only consider the relevance scores that have positive value as described by [Chffer et al.) (2021) to avoid the mix between positive and negative values which may lead to an inaccurate high relevance score. In our modification, instead of operating at the pixel level, we carry an additional aggregation of multiple pixels' relevance belonging to the same patch. Relevance ())) of the j-th patch to the target class E top-y classes C on layer I is calculated follows (Chefer et al. 2021):
13

---

Published as a conference paper at ICLR 2024
Algorithm 2 Inter-layer importance scores using LRP.
Input: Vision Transformer T with L layers, training dataset number of highest-Acc. classes 7 number rounds T.
for t= 1....... do
2: Randomly sample a batch from D.
3: for in do
4:
Retrieve the classes C with top-ry highest Acc. for с in do
5:
6:
Initialize ReL+1.e) as (one-hot encoding of the target class c).
7:
Compute the gradients of all layers VA; for L,..., 1....,,dd. do
8:
xf
9:
R [il(tn)e E((((AE))) offe" Rittoy // where Q {(1.5) 2 2/ 0}
10:
(t.e)) = T+ B& (VA) @ Ra.,))
11:
((.e) Att.e: Aa+1o)) ... A(t.c)
12:
(t.e) [T.E)
end for end for
14:
15:
end for
16: for 1= 1 L do
17:
Siner
(1)
I8 Eeer Ecee (l,c)-
18:
end for end for
for 1=
I..... L do
21: (1)
Σ Sinke
22: end for
Output: The inter-layer importance scores Sinler
x wwf
Bli,e = GQ (Xi, Wi, Wi,R,)))) = E
R Rit
(8)
(((())))) E E(i(())E)) of uos
where I denotes the VIT block index, Q := {(t,)) j) of 2 0} is the subset of patch index pairs corresponding to positive relevance values and indices i.j represent image patches. X, and W denote the input and weights (the compound h-th attention head) of layer To initialize the relevance propagation, set the patch relevance R(L+1e) = 1. as one-hot encoding for the target classes c.
W!n" E Rddd,, W.i.k E Rdxdd, W Rdxdd for the
Following the propagation procedure of relevance and gradients and denoting each attention map by A₁ (X)++))) for block I, the relevance scores R.(.e) along with the gradients V A are used to recursively compute the inter-layer patch importance scores Sa,e) B [N based on:
S(,c)) = ((.e)) Aut+,.) ... A((,)) where ((t,)) = I E, (AA O R...))
(9)
and @ is the Hadamard product, E, denotes averaging across the 'heads' dimension, the superscript denotes the positive part. In the output Sg.e) R(N+1)((N+1) each row corresponds to the relevance of the corresponding patch with respect to each of the other patches. Note that ( reflects the importance 'to-go', i.c., from the current layer until the end of the network. For our method, we only consider the relevance map derived from the row that corresponds to [CLS], that is ((..)
N- This captures each patch's 's influence on the classification token for layer and class The inter-layer importance score Sin obtained by averaging across classes C. Alg. details the aforementioned process.
In Alg. 2 we sample batches for rounds (step 1) to calculate the inter-layer information (7 = 10 is used in our experiments). For each image batch of data B, we define the set of top-y classes (y = 6 is used in our experiments). We calculate scores according to steps 9- 12: we obtain Rq.e) in step 9 for all patches (including the [CLS]) for each class in C. according to the propagation step described in 77h. while steps 10-11 compute the scores among all patches (by multiplying A from the 1-th layer the last layer). Only the first row (corresponding to [CL.S) is kept in step 12
14

---

Published as a conference paper at ICLR 2024
the importance scores of all patches for each class The inter-layer importance score (() is obtained by averaging across batches and classes C (step 17), and the number rounds T (step 21).
C DETAILED DERIVATION OF FUSION STEP
This section gives the detailed derivation of equation
Recall the problem:
minimize
aKL (pllp') + (1 aL (pllp")
P
s.t. p. 220.
E.
where a (E [0, 1) is a hyperparameter that balances contribution of intra-finter-layer scores; p² the pmf corresponding intra-layer scores and y² is the pmf for inter-layer scores.
First, notice that the constraint p: 2 implicit (due to the logarithm in the definition of the KI. divergence- (L, q) = E. pt log 2s ), so it does not have to be incorporated in the Lagrangian of the problem (i.e., it can be relaxed). The Lagrangian for (3) with multiplier v (corresponding to the equality constraint) is given by:
gi
L(p, A, 0)
Σ
ap, log P: ap: logpt + (1 )); logp,
p - (1- ppp logp? +o
-p-1
= E{
P:
ps log - opi log p. - (1 a)p; log p. + upi -
The KKT conditions boil down to:
pi 2 0.
Vi
E.Pr 1
logp; + - log (p!) - log (p:) +v= 0.
Vi
It is plain to verify that Slater's condition is satisfied (the explicit constraint set is non-empty and affine) so that strong duality holds. From the last KKT condition, it follows that:
log + 1 log (p!)² log (x?)
+ 0.
Consequently, derive:
p = ( (1,) ((+t)) Vi
In view of P: obtain:
Σ(!) (1) ( ((+0)
e (1+t)
(10)
Ej(r)a (1))
The unique (because of strict convexity) solution is thus given by:
(vt) (vz) 1-a Pt
Vi
Σ, (pt) (p?)'-a>
that is ffused S Sinter(1-a)
D ADAPTIVE RETENTION RATE SELECTION
We present more details on the design and analysis of adaptive retention rate selection (a-STAR, corresponding to Option 2 in Step 9 of Alg. TT in this section. We begin by establishing lemma that needed to prove that the overall compression S-SR is no less than that of STAR, for common parameter p.
15

---

Published as a conference paper at ICLR 2024
Lemma 1. Consider pmf that satisfies p1 P PN. The CDF & Egst Pe satisfies:
G 2 N
Vi [I....,N.
Proof. By definition, cN 1. Assume 3i E [l....,N 1) that G < N. This implies that minjgt Pt IV (since minygi pt I q.). From monotonicity, it holds that maxz>; ps I min;gj Pi N. Additionally, = oN = q + EjziDi < + (N - i) = 1. Thus,
contradiction.
The main idea of a-STAR is to use the retention rates of STAR (pt) as weighted percentile values for patch pruning. This leads to dynamic compression rate (i.e., that depends on the input), since the number of retained patches now depends also on the distribution of (fused) scores.
Formally, for the 1-th Transformer layer (1 S i S T.,, we obtain a set of normalized fused scores denoted as ftued = { The primary objective is to partition this set into two distinct subsets: Sfined = R₂ L Pt, where R2 represents the retained patches in the 1-th layer, and P: represents the pruned patches in the same layer. The objective to:
minimize R2 C
R2
(11)
(
s.t. P(R)) pt.
where P( sf. is plain to check that there exists an optimal solution of (10) where R1 contains the highest scores (for any solution, switching a score in R, that is lower than a score in Pi would still satisfy the constraint). This suggests that solving (10) can be performed by the steps in Option 2 of Alg. 2 (sorting Stuse in decreasing order and computing the index where the CDF first exceeds the value pt). Let pi == N; [pc 2 pt (Nr denotes the number of patches at layer l): note that and solving (10) with p\ in place of pt yields an upper bound on the optimal [R,]. It follows from Lemma I that [Ra] S [ptN]] (since N.) 2 Pt). Since the number of retained patches for STAR is exactly [p: Ni], , have established that the number of retained patches by a-STAR at layer I is no larger than that for STAR. By repeating this argument layer-wise (in view also of the fact that N141 Ni), we establish that the FLOPs Drop for a-STAR is least high the one for STAR. This is consistent with our experimental results in Table Finally, we can also establish the same monotonicity property for S-SR as STAR (i.e., decreasing ACS and increasing in p). This because of the fact that the optimal solution of (10) is non-decreasing in pl.
E FULL EXPERIMENTS
In this section, we present the full results of the experiments. Fig. shows the comparison between our approach and baselines on the trade-off between Top-1 1 Acc. and Throughput on the ImageNet dataset. We measured the throughput of all methods and a batch size of 128. The input image size is 2242, and the Multiply-Accume (MACs) metric is determined using torchprofile. Our code was implemented in PyTorch 1.8.0 and Python 3.7 on a system equipped with 4 NVIDIA Tesla A GPUs and NVIDIA 3090 GPUs. The CUDA version employed 11.3, and the inference precision the compressed models are fine-tuned for 120 epochs with hard distillation (Touvron et al., 2021]) on images of resolution 224 of their corresponding original models. Since ToMe (Bolya et al., 2023) conducts experiments on DeiT model compression by training from scratch for 300 epochs, and Patch Slimming (Tang et al. [2022) does not provide open-source code, we rely directly on the results reported in their respective papers. STAR yields consistent improvement over the state-of- the-art methods in all scenarios.
NVIDIA A 100 GPU with 40GB memory
computations
float32. After pruning.
Influence of hyperparameter in KL fusion: Table shows the full results of varying the hyper- parameter a for KL fusion. In order to experiment with as many choices and models as possible, all experiments listed did not apply fine-tuning. The batch sizes are determined based on the maximum memory allowed by a single A100 GPU for different models. Specifically, the batch sizes are 192, 256, and 512 for DeiT-Base, DeiT-Small, and DeiT-Tiny, while LV-VIT-M and VV-V employ
16

---

Published as conference paper at ICLR 2024
84
LEVITM
DAVISS
STARIU/VITM
STAR HAVIES
Exit Daee
VIP.DuT-Base
taVe pelt Timy
Dell Base
Sel T-Base
VFC-FC. pelis
ImageNet Top-1 Acc. 196)
Scon flane
WVVIB STOR (Oum))
ToMe Deff-Small
STARIDerT
78
74
Deintiny
STARIDe/::T0
5000
Throughput (images/s)
Figure 3: Accuracy-throughpu trade-off. The baseline models (DeiT and LV-ViT) are depicted in solid lines, while dashed lines connect points for our pruning method. The same model is denoted by the same marker, while the same method indicated by the same color. STAR achieves the most favorable trade-off, surpassing other methods in terms of both accuracy and throughput.
Table 3: Effect of hyperparameter a in the KI. fusion module of STAR and a-STAR for DeiT and VV- models (without fine-tuning). 'STAR" means using the static retention rate selection while 'a-STAR' refers to using the adaptive retention rate selection. a = means intra-layer only and inter-layer only. The batch size represents the maximum value that can be selected for running the models on a single A100 GPU, and the value of p is determined based on the target pruning ratio. The values marked boldface represent the best results: in all cases, fusion is instrumental (i.e.. E (0, 1) are the worst choices), while there is robustness in choosing a with optimal performance in 10.15, 0.3).
DeiT-Base
KL. fusion with Batch size
192,
p= 0.75
0.0
0.15
0.2
0.3
0,4
0.5
0.6
0.7
0.9
1.0
Top-1 Acc.
81.8
77.7
79.9
80.0
79.7
779.
79.6
79.6
79.5
79.5
79.4
79.4
STAR
Top-5 Ace.
95.6
93.2
94.5
94.7
94.6
94.4
94.5
94.4
94.4
94.3
94.3
94.2
94.1
Top-1 Ace."
31.3
77.4
79.3
79.7
79.6"
79.5
79.3
79.3
79.2
779.2
779,2
79922
79.
a-STAR
Top-5 Acc.
95.6
93.0
94.3
94.5
94.4
94.3
94.2
94.2
94.2
94.2
94.1
94.1
94.1
Deil DeiT-Small
KL Jusion with Batch
256, p 0.75
0.0
0.15
0.2
0.3
0.5
0.6
0.7
0.9
1.0
Top-1 Acc.
79.8
75.5
77.5
77.6
77.5
77.3
77.1
77.0
77.0
76.9
77.0
77.0
76.9
STAR
Top-5 Acc.
95.0
92.4
93.8
93.9
93.8
93.6
93.5
93.5
93.5
93.6
93.5
93.4
Top-i Acc.
79.8
75.4
77.2
77.3
77.2
77.0
76.8
76.6
76.6
76.4
76.5
76.4
76.3
a-STAR
Top-5 Acc.
95.0
92.4
93.6
93.7
93.6
93.4
93.4
93.3
93.3
93.3
93.2
93.2
93.1
DeiT-Tiny
KIL fusion with Batch
512, p= 0.8
0.0
0.2
0.3
0.5
0.6
0.7
1.0
Top-T Aca."
72.2
66.2
68.7
68.9
68.7
68.7
68.6
68.6
68.5
668.
668.4
66.3
66.2"
STAR
Top-5
91.1
87.5
89.1
89.0
88.9
88.8
88.8
88.7
88.8
Top-I Acc."
72.2
65.7
68.3
68.6
68.3
68.3
68.2
68.2
68.0
'67.5
'67.9
'67.8
66.66"
a-STAR
Top-5 Ace.
91.1
87.2
88.6
88.8
88.7
88.6
88.5
88.5
88.5
88.4
88.4
88.3
LV-ViT-M
KL fusion with Batch size
128, p
0.8
C Top-i Acc.
0.0
0.25
0.6
1.0
83.3
80.3
82.3
82.4
82.3
82.2
82.2
82.1
'82.6
82.6
81.9
STAR
Top-5 Acc.
96.6
94.7
95.9
95.9
96.0
95.8
95.8
95.7
Top-1 Acc.
79.8
81.9
82.0
82.1
81.7
81.8
81.7
81.6
81.6
a-STAR
Top-5 Acc.
96.6
94.3
95.7
95.7
95.7
95.8
95.7
95.6
95.6
95.5
95.5
95.5
95.4
LV-V
fusion with Batch size 256,, p
0.65
Cx Top-1 Acc."
0.0
0.2
0.25
0.3
0.5
0.6
0.7
0.8
0.9
1.0
83.3
71.3
78.4
78.6
78.6
78.7
78.5
78.4
78.1
788.2
788.
771
78.00
STAR
Top-5 Acc.
96.3
89.6
93.7
93.7
93.7
93.8
93.7
93.5
93.5
93.4
93.3
93.3
93.3
Top-I Acc.
83.3
71.2
77.9
78.0
78.1
78.0
77.9
77.7
77.8
77.6
77.6
77.5
77.3
8-STAR
Top-5 Acc.
96.3
89.5
93.3
93.4
93.3
93.2
93.1
92.9
92.9
92.8
92.7
92.7
17

---

Published as a conference paper at ICLR 2024
batch sizes of 128 and 256, respectively. For DeiT-Base, DeiT-Small and DeiT-Tiny models, the highest Top-1 Acc. and Top-5 Acc. are achieved with a set to 0.15, while for the LV-ViT-M and LV-ViT-S model, the optimal values 0.3 and 0.25, respectively. It is noteworthy that after ap- plying STAR to prune DeiT--mmll, the resulting Top-1 Acc. and Top-5 Acc. are improved by 0.7% and 0.5%, respectively, compared using only intra-layer importance scores. This finding further supports the effectiveness of our fusion module.
Influence of hyperparameter p on pruning: Fig. 4aa illustrates the impact p on the layer- wise retention rate of DeiT-Base generated by the static retention rate selection method described in Sec. [.2] illustrates the previously discussed monotonicity property (i.e., the higher the p. the higher the retention rate at each layer). Table 4 and Table 5 show the accuracy of DeiT and LV- models varying with GFLOPss under different compression ratios without fine-tuning; Figure bb) visualizes it for the DeiT-Base model. For instance, in DeiT-Base, when the value of p is set to 0.9, the corresponding GFLOPs of the pruned DeîT-Base model 14.0. As decreases 0.6, the GFLOPs also decrease to 7.7. This demonstrates the effectiveness of our approach in that a single hyperparameter p can control the overall compression. rate calculated by STAR (using the static retention rate selection) and a-STAR (using the adaptive retention rate selection). As expected, the CDF curve is concave, which shows that the retention rate calculated by a-STAR no larger than that for STAR (pt), and this is consistent with our discussion in Appendix
Figure c we compare the retention
Top- Acc thu Calculated
Retention 00
Layer index
Retention rate
(a) Retention rate DalT-Base
(b) Vertation of GFLOPs and Acc. DelT-Base
(c) CDF of fused scores of DerT-Base Leyer1
Figure 4: (a) Impact of on the layer-wise static retention rate selection. (b) Impact of on the GFLOPs and Top-1 Acc. of Deit-Based using STAR. (c) Comparison of the retention rate derived by STAR and a-STAR.
Table 4: DeiT results under different compres- Table 5: LV-VIT results under different compres- sion levels (without fine-tuning).
sion levels (without fine-tuning).
Model
P
GFLOPs
Top-1 I Acc.
Top-5 Ace.
Model
P
GFT.OPs
Top- I Avc.
Top-5 Acc.
1.0
95.6
12.6
96.6
0.9
81.6
95.5
8.8
DeiT-Bace
0.8
11.2
80.9
95.1
LV-VIT-M
0.8
6.7
82.4
96.0
0.7
9,3
79.1
94.3
0.7
5.5
80.3
95.2
0.6
7.7
76.5
92.8
0.6
4.7
77.3
91.5
1.0
4.6
79.8
95.0
1.0
6.5
83,3
96.3
0.9
94.8
0.9
5.0
83.1
96.3
DeiT-Samll
0.8
2.8
78.7
94.2
LV-VIT-S
0.8
4.0
82.1
95.9
0.7
2.3
76.4
93.1
3.4
94.8
0.6
2.0
73.5
92.6
3.0
92.9
1.0
1.3
72.2
91.1
0.9
0.9
71.3
90.7
DeiT-Tiny 0.8
68.9
89.1
0.7
0.6
65.8
87.5
0.6
0.5
63.4
84.9
Influence of data size used to calculate ACS on pruning: In this ablation study, we use different sizes of data to calculate the average cosine similarity between patches on DeiT-Base using STAR model accuracy with the of p=0.75. The result in Table 6 shows that when the data size is 500, the pre-computing takes 14.2 seconds and the Top-1 Acc. and Top-5 Acc. 0.1% and 0.2% better than using data size 250, while it keeps the same when increasing the data size to 1000. This result supports the choice of using a data size of 500 in our experiment.
and show its impact
Impact of fine-tuning: The result in Table displays the impact of fine-tuning DeiT and LV- ViT after iiter-pruned models accuracy for STAR. shows that fine-tuning can enhance model accuracy by minimum of 0.4% and maximum of 4%.
18

---

Published as a conference paper at ICLR 2024
Table 6: Impact of data sizes used calculate the average cosine similarity between patches the DeiT-Based model accuracy when using p=0.75 without fine-tuning for STAR. Data Size = 500
gives the best trade-off between pre-computing time and model accuracy.
Data Size
Time of Computing ACS
GFLOPs
Top-1 Acc.
Top-5 Acc.
1000
27.6s
10.22
80.0
94.7
500
14.2s
10.20
80.0
94.7
250
7.3s
10.20
79.9
94.5
100
3.4s
10.18
79.8
94.5
Table 7: Impact of fine-tuning on accuracy for STAR. FT denotes fine-tuning the compressed model for 120 epochs. w/o means without fine-tuning, w/ means with fine-tuning, and means the im- provement of Acc. under fine-tuning.
Top-1 I Acc. Top-5 Acc.
Model
GFLOPs
w7o FT
W/FT
DeiT-Base
10.2
80.0/94.7
81.5/95.5
1.5/0.8
DeiT-Samll
2.6
77.6/93.9
79.4/94.5
1.8/0.6
DeiT-Tiny
0.7
68.9/89.1
72.0/90.7
3.1/1.6
LV-VIT-M
6.7
82.4/96.0
83.3/96.4
0.9/0.4
LV-VIT-S
3.2
78.7/93.8
82.7/96.2
4.0/2.4
Table 8: Comparison between STAR and DiftRate with fine-tuning of 30 epochs.
DeiT-Base
GFLOPs
Acc. (%)
Throughput
Speedup (%)
Baseline
17.6
81.8
1,051.6
DifiRate
11.5
81.6
1,444.9
37.4
STAR
11.2
81.6
1,595.9
51.7
a-STAR
11.0
81.5
1,702.1
61.8
Table 9: DeiT performance on out-of-distribution datasets (ImageNet-R).
Top-1 I Acc. the
Top-1 Acc. the after-pruned model (%)
Model
GFLOPs
GFLOPs
FLOPs 4 (%)
before- pruned model (%)
DeiT-Base DeiT-Samll
45.36
17.6
43.64
11.2
36.4
42.50
4.6
41.05
2.8
39,1
DeiT-Tiny 33.19
1.3
31.07
0.7
46.1
Comparison with DiffRate: Result in Table 8 is about the comparison between STAR and DiffRate (Chen et al.] 2023) on DeiT-Base with fine-tuning of 30 epochs under the same setting NVIDIA A100 GPU with 40GB
DiftRate. The throughput of this experiment was tested memory, utilizing the batch size 128 and fp32. With the same Top-1 Acc. of the after-pruned DeiT- Base, STAR achieves reduction of 0.3 in GFLOPs and +14.3% throughput speedup compared to DiffRate, while a-STAR achieves 24.4% higher speedup with negligible accuracy drop (-0.1% (0.1%)
Model performance on -nttof-distribution datasets: The result Table lists the Top-1 Acc. of the before- before-pruned pruned model and after-prunee model (without fine-tuning) on the out-of-distribution dataset ImageNet-R (Hendrycks al. (02T). It is worth noting that for DeiT-Small, STAR achieves reduction of 39.1% in FLOPs, with a drop of only 1.45% in Top-1 Acc. on ImageNet-R. These results demonstrate the robustness of STAR as an effective patch pruning method on the out-of- distribution dataset.
19


Reviews:
[{"review_id": "5XLkklH34u", "reviewer": "Reviewer_h5Sc", "summary": "The paper proposes a new patch pruning method (STAR) by combining intra-layer and inter-layer scores.\nThe intra-layer score uses attention values to CLS token, and the inter-layer score utilizes Layer-wise relevance Propagation (LRP) which was proposed in a previous study for ViT interpretability. For inference, the intra-layer score is calculated by the network in an online manner, while a saved inter-layer score which is averaged over training data is used to utilize it without additional computation. By well-designed pruning threshold determination method, STAR outperforms other patch pruning methods.", "questions": "- Is there any difference from LRP for STAR compared to [A]?\n  - [A] Transformer Interpretability Beyond Attention Visualization, CVPR 2021\n\n- As I understand, LRP in [A] requires a relevance score back-propagation for every computation unit. But, Line 9 in Algorithm 1 is not enough to explain it. I strongly recommend authors redesign Section 4 to help readers to understand LRP. Current Algorithm 1 has a lot of flaws and errors. If it is not different from [A], I recommend simplifying the explanation and focusing on explaining the inference stage.\n\n- I think LRP statistics on the training set are used for inference, like batch-norm. Am I right? \nIt is an important point but not clearly described. \nPlease clarify the inference process. Especially, it should be clearly stated to check whether additional computation for LRP is excluded from inference costs or not.\nIf LRP computation is required for every inference, I will lower my rating.\n\n- What is the impact of the fine-tuning process? Can STAR work without fine-tuning?\n\n- Could you visualize saved training stats of inter-layer scores (LRP)? Is there any pattern related to CLS token?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 4, "strengths": "- STAR shows that offline importance score—saved inter-layer score statistics over training data—can be effectively used for patch pruning methods. I believe this is the paper's key contribution.\n\n- STAR achieves reasonable performance improvement over other baselines.\n\n- STAR enables adaptive inference, which gives additional performance gain.\n\n- A hyper-parameter for compression rate handling is well-designed", "weaknesses": "- Writing is unclear and hard to understand.\n\n- Method is incremental. STAR is a combination of two methods: attention score for CLS token and Layer-wise Relevance Propagation (LRP) for ViT. In particular, LRP for STAR looks the same as the original LRP for ViT.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "tNTNLP18ih", "reviewer": "Reviewer_kdgo", "summary": "This paper presents a new token pruning method for vision transformers. It utilizes an online evaluation of intra-layer importance and an offline evaluation of inter-layer importance of each token (patch), using a newly designed method named Layer-wise Relevance propagation. The patches are pruned at each layer by maintaining only the top-k important ones. It also uses the average cosine similarity to decide the pruning ratio of each layer. It also introduces another dynamic pruning ratio selection method based on the input features. The method is evaluated on ImageNet classification with DeiT and LV-ViT. It outperforms existing token pruning methods on Transformers such as SCOP, PoWER, ToMe, VTC-LFC etc with better accuracy under similar compression ratio.", "questions": "-\tHow is the throughput measured (Table 1). What kind of engineering setup do you use? Such as usage of TensorRT, cuda version, inference precision (fp16 or float32). What is the batch size used (batch size has a large impact on throughput).", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-\tThe idea of using attention score with the CLS token as the cues for token pruning is simple and effective. Combining the intra-layer importance and inter-layer importance is novel. The proposed method of using average cosine similarity to decide the pruning ratio facilitates automatic estimation of pruning ratio at each layer.\n-\tThe conducted experiments cover different baseline methods and different pruning ratios, showing the proposed method can outperforming the existing patch-pruning methods.\n-\tPaper writing is clear and easy to follow.", "weaknesses": "-\tIt seems the pruned model still needs finetuning with 120 epochs to reach a strong performance. Is this setting similar to the existing methods? If the finetuning settings of different methods are different, it will lead to an unfair comparison.\n-\tIn the fusion of intra and inter-layer importance scores, a parameter $\\alpha$ is used. How is this parameter tuned? Do you use the same \\alpha for different models? \n-\tSome parts of the paper are too verbose. Abstract includes too much technical details. The claimed contribution in the introduction section is too long and is hard to understand (including too many details).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "wZnKxhZnJ7", "reviewer": "Reviewer_cb4H", "summary": "This paper suggests a token compression method used for ViTs named STAR. To better determine which tokens should be pruned, STAR combines an intra-layer importance metric given by [CLS] token and an inter-layer importance metric given by layer-wise relevance propagation into a more comprehensive metric. STAR is able to automate pruning ratio selection across layers. Experimental results on DeiT and LV-ViT show improved performance over some previous token compression methods.", "questions": "See Weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper is generally well-written.  Experimental results on DeiT and LV-ViT show improved performance over some previous token compression methods.", "weaknesses": "- Novelty\n  - The proposed STAR is a combination of existing importance-aware (given by [CLS] token) token compression methods such as EViT[1] and layer-wise relevance propagation method[2]. Simply composing two existing metrics, as the core novelty of the paper, does not deserve a good contribution, in my opinion.\n  - The proposed STAR is not the first work to capture the cross-layer importance and enables different compression ratios among different layers. For example, DiffRate[3] can also automatically learn different compression rates across layers. The lack of thorough comparisons with these previous approaches also harms the contribution and novelty of this paper.\n- Method\n  - The proposed STAR introduces an extra procedure for pre-computing average cosine similarity as a metric, while other token compression method does not. It is unclear how much extra time this procedure will cost and how the size of the dataset used for pre-computing will affect the model performance.\n- Experiments\n  - Some important baselines are missing. For example, DiffRate[3] mentioned above.\n  - The setting of comparison experiments is unfair. STAR uses an extra distillation to enhance the after-pruning performance, while some compared methods, such as ToMe[4], do not use it. Experimental results without distillation should also be reported to achieve a fair comparison.\n  - Some ablation studies are missing. For example, the impact of the dataset size used for pre-computing metrics on model performance. Besides, it would be better if there were zero-shot experiments to investigate how well these pre-computed metrics perform on out-of-distribution datasets (e.g., ImageNet-R[5]).\n  - Experimental results at different compression ratios on the same model are missing. For each model, there is only one compression ratio used, and different compression ratios on the same model are needed to verify the effectiveness of the proposed STAR under higher and lower compression ratios.\n  - Experiments on different architectures are insufficient. The experiments are only conducted on DeiT and LV-ViT, and it would be better to also have experimental results on other branches of the ViT family, for example, Swin Transformer[6] and CSWin Transformer[7], which adopt window attentions.\n\nReferences  \n[1] EViT: Expediting Vision Transformers Via Token Reorganizations.  \n[2] Transformer interpretability beyond attention visualization.  \n[3] DiffRate: Differentiable Compression Rate for Efficient Vision Transformers.  \n[4] Token merging: Your vit but faster.  \n[5] The many faces of robustness: A critical analysis of out-of-distribution generalization.  \n[6] Swin transformer: Hierarchical vision transformer using shifted windows.  \n[7] CSWin Transformer: A General Vision Transformer Backbone With Cross-Shaped Windows.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IRp2A5Scri", "reviewer": "Reviewer_fwdP", "summary": "This paper proposes a dynamic patch pruning method for accelerating vision transformers. Inter-layer importance scores are computed to obtain the importance of patches at a specific layer. The inter-layer importance scores consider the impact of patches across layers on the final classification output.", "questions": "See Weaknesses", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper articulates its points effectively.\nThe target issues of the paper are meaningful and worth exploring. The idea is novel, and the motivation is clear.\nThe inclusion of experimental analysis on pruning vision transformers is a strength of the paper. This analysis provides valuable insights and promotes understanding of the proposed method.", "weaknesses": "1. This paper does not cite some dynamic pruning papers, such as [1,2,3].\n[1] Manifold Regularized Dynamic Network Pruning. CVPR2021\n[2] DYNAMIC MODEL PRUNING WITH FEEDBACK. ICLR2020\n[3] Dynamic Network Pruning with Interpretable Layerwise Channel Selection. AAAI2020\n\n2. The patch pruning methods cannot save the parameters, while channel pruning can achieve this goal. How to reduce the parameters is worth exploring.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)