Chasing Sparsity in Vision Transformers: An End-to-End Exploration
Authors: Tianlong Chen
Yu Cheng
Zhe Gan
Lu Yuan
Lei Zhang
Zhangyang Wang
Venue: NeurIPS 2021 Poster (2021)
Keywords: Vision Transformer
Sparsity
Data and Architecture Sparse Co-Training

Abstract: Vision transformers (ViTs) have recently received explosive popularity, but their enormous model sizes and training costs remain daunting. Conventional post-training pruning often incurs higher training budgets. In contrast, this paper aims to trim down both the training memory overhead and the inference complexity, without sacrificing the achievable accuracy. We carry out the first-of-its-kind comprehensive exploration, on taking a unified approach of integrating sparsity in ViTs "from end to end''. Specifically, instead of training full ViTs, we dynamically extract and train sparse subnetworks, while sticking to a fixed small parameter budget. Our approach jointly optimizes model parameters and explores connectivity throughout training, ending up with one sparse network as the final output. The approach is seamlessly extended from unstructured to structured sparsity, the latter by considering to guide the prune-and-grow of self-attention heads inside ViTs. We further co-explore data and architecture sparsity for additional efficiency gains by plugging in a novel learnable token selector to adaptively determine the currently most vital patches. Extensive results on ImageNet with diverse ViT backbones validate the effectiveness of our proposals which obtain significantly reduced computational cost and almost unimpaired generalization. Perhaps most surprisingly, we find that the proposed sparse (co-)training can sometimes \textit{improve the ViT accuracy} rather than compromising it, making sparsity a tantalizing "free lunch''. For example, our sparsified DeiT-Small at ($5\%$, $50\%$) sparsity for (data, architecture), improves $\mathbf{0.28\%}$ top-1 accuracy, and meanwhile enjoys $\mathbf{49.32\%}$ FLOPs and $\mathbf{4.40\%}$ running time savings. Our codes are available at https://github.com/VITA-Group/SViTE.

Chasing Sparsity in Vision Transformers: An End-to-End Exploration
Tianlong Chen', Yu Cheng", Zhe Gan', Lu Yuan', Lei Zhang', Zhangyang Wang' University of Texas at Austin, MMicrosoft Corporation, 'Internatoonal Digital Economy Academy ftianlong. chen, atlaswnng) @utexas. edu, (yu. cheng, zhe, zhe.gan, gan, wwanmmmmc..cc..oommmmmm aaaa,,ayaa/miccrooot...mm leizhangen@ieee.org
Abstract
Vision transformers (ViTs) have recently received explosive popularity, but their enormous model sizes and training costs remain daunting. Conventional post- training pruning often incurs higher training budgets. In contrast, this paper aims to trim down both the training memory overhead and the inference complexity, without sacrificing the achievable accuracy. We carry out the first-of-its-kinn kind comprehensive exploration, on taking unified approach of integrating sparsity in ViTs "from end to end". Specifically, instead of training full ViTs, we dynamically extract and train sparse subnetworks, while sticking to fixed small parameter budget. Our approach jointly optimizes model parameters and explores connectivity throughout training, ending up with one sparse network as the final output. The approach seamlessly extended from unstructured to structured sparsity, the latter by considering to guide the prune-and-grow of self-attention heads inside ViTs. We further co-explore data and architecture sparsity for additional efficiency gains by plugging in novel learnable token selector to adaptively determine the currently most vital patches. Extensive results on ImageNet with diverse ViT backbones validate the effectiveness of our proposals which obtain significantly reduced computational cost and almost unimpaired generalization. Perhaps most surprisingly, find that the proposed sparse (co- coo-)training can sometimes improve the VET' accuracy rather than compromising it, making sparsity a tantalizing "free lunch". For example, sparsified DeiT-Small at (5%, 50%) sparsity for (data, architecture), improves O. 0.28% top-1 accuracy. and meanwhile enjoys 49.32% FLOPs and 4.40% running time savings. Our codes are available at https: //github. com/ VITA-Group/SViTE.
Introduction
Recent years have seen substantial efforts devoted scaling deep networks to enormous sizes. Parameter counts are frequently measured in billions rather than millions, with the time and financial outlay necessary train these models growing in concert. The trend undoubtedly continues with the recent forefront of transformers [1-3] for computer vision tasks. By leveraging self-attention, reducing weight sharing such convolutions, and feeding massive training data, vision transformers have established many new state-of-the-an (SOTA) records in image classification [1, 2]. object de- tection [4-7], image enhancement [8, 9], and image generation [10-12]. Existing vision transformers and variants, despite the impressive empirical performance, have in general suffered from gigantic parameter-counts heavy run-time memory usages, and tedious training. That naturally calls for the next step research of slimming their inference and training, without compromising the performance.
Model compression and efficient learning exploration the emerging vision transformer field remains scarce [13]. Among the large variety of compression means [14], sparsity has been one of the central themes since the beginning [15].
strangers deep learning researchers, although their
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Conventional approaches first train dense networks, and then prune large portion of parameters in the trained networks zero. Those methods significantly reduce the inference complexity. However, the price is to cost even more significant computational resources and memory footprints at training, since they commonly require (multiple rounds of) re-training to restore the accuracy loss [15-17]. That price becomes particularly prohibitive for vision transformers, whose vanilla one-pass training is already much more tedious, slow, and unstable compared to training standard convolutional networks.
An emerging subfield has explored the prospect of directly training smaller, sparse subnetworks in place of the full networks without sacrificing performance. The key idea is to reuse the sparsity pattern found through pruning and train a sparse network from scratch. The seminal work of lottery ticket hypothesis (LTH) [18] demonstrated that standard dense networks contain sparse matching subnetworks (sometimes called "winning tickets") capable of training in isolation to full accuracy. In other words, we could have trained smaller networks from the start if only we had known which subnetworks to choose. Unfortunately, LTT requires to empirically find these intriguing subnetworks by an iterative pruning procedure [18-27], ; which still cannot get rid of the expensiveness of post- training pruning. In view of that, follow-up works reveal that sparsity patterns might emerge the initialization [28, 29]. the early stage of training [30, 31], or in dynamic forms throughout training [32-34] by updating model parameters and architecture typologies simultaneously. These efforts shed light on the appealing prospect of "end to end" efficiency from training to inference, by involving sparsity throughout the full learning lifecycle.
This paper presents the first-of-its -ts comprehensive exploration of integrating sparsity in vision transformers (ViTs) "from end to end"" With (dynamic) sparsity as the unified tool, we can improve the inference efficiency from both model and data perspectives, while also saving training memory costs. Our innovative efforts are unfolded along with the following three thrusts:
From Dense to (Dynamic) Sparse: Our primary quest is to find sparse ViTs without sacrificing the achievable accuracy, and meanwhile trimming down the training memory overhead. To meet this challenging demand, we draw inspirations from the latest sparse training works [34, 35] that dynamically extract and train sparse subnetworks instead of training the full models. Sticking to a fixed small parameter budget, our technique jointly optimizes model parameters and explores connectivity throughout the entire training process. We term our first basic approach as Sparse Vision Transformer Exploration (SVITE).
Most sparse training works [32, 33, 36-39, 38, 34, 40, 41, 35] restricted discussion to unstructured sparsity. To attain structured sparsity which is more hardware-frrn waire-friendly unlike classical channel pruning available for convolutional networks, we customize a first-order importance approximation [16, 42] to guide the prune- and-grow of self-attention heads inside ViTss. This seamlessly extends SVITE to its second variant of Structured Sparse Vision Transformer Exploration ViTE..
From Unstructured to Structured:
We further conduct a unified co-exploration towards joint data and architecture sparsity. That is by plugging in novel learnalle token selector to determine the most vital patch embeddings the current input sample. The resultant framework of Sparse Vision Transformer Co- Exploration (SVITE+) remains to be end-to-end trainable and can gain additional efficiency.
From Model to Data:
Extensive experiments conducted ImageNet with DeiTTTiny/Small/Base Results of substantial computation savings and nearly undamaged accuracies consistently endorse our proposals' effec- tiveness. Perhaps most impressively, we find that the sparse (co-) >training can even improve the VIT accuracy rather than compromising it, making sparsity a tantalizing "free lunch". For example, apply- ing SVITE+ on DeiT-Small produces superior compressed ViTs at 50% model sparsity plus 5% data sparsity, saving 49.9 49.32% FLOPs and 4.40% running time, while attaining a surprising improvement of 0. 0.28% accuracy: even when the data sparsity increases to 10% (the model sparsity unchanged), there is still no accuracy degradation, meanwhile saving 52.38% FLOPs and 7.63% running time.
2 Related Work
Vision Transformer. Transformer [43] stems from natural language processing (NLP) applications. The Vision Transformer (ViT) [1] pioneered to leverage pure transformer, to encode an image by splitting it into a sequence of patches, projecting them into token embeddings, and feeding them to

---

transformer encoders. With sufficient training data, VIT is able to outperform convolution neural networks on various image classification benchmarks [1, 44]. Many ViT variants have been proposed since then. For example, DeiT [2] and T2T-ViT [45] are proposed to enhance ViT's training data efficiency, by leveraging teacher-student and better crafted architectures respectively. In addition to image classification, ViT has attracted wide attention in diverse computer vision tasks, including object detection [4-7], segmentation [46, 47], enhancement [8, 9], image generation [10-12], video understanding [48, 49], vision-language [50-57] and 3D point cloud [58].
Despite the impressive empirical performance, ViTs are generally heavy to train, and the trained models remain massive. That naturally motivates the study to reduce ViT inference and training costs, by considering model compression means, Model compression has been well studied in both computer vision and NLP applications [59-61, 42, 62, 21J. Two concurrent works [13, 63] made initial attempts towards ViT post-training compression by pruning the intermediate features and tokens respectively, but did not jointly consider weight pruning nor efficient training. Another loosely related field is the study of efficient attention mechanisms [64, 10, 52, 65-75]. They mainly reduce the calculation complexity for self-attention modules via various approximations such as low-rank decomposition. Our proposed techniques represent an orthogonal direction and can be potentially combined with them, which we leave as future work. Another latest concurrent work [76] introduced an interpretable module to dynamically and gracefully drop the redundant patches, gaining not only inference efficiency but also interpretability. Being unique and orthogonal effort from ours, their method did not consider the training efficiency yet.
Pruning and Sparse Training. Pruning is well-known to effectively reduce deep network inference
costs [77, 15]. It can be roughly categorized into two groups: (i) unstructured pruning by removing
insignificant weight elements per certain criterion, such as weight magnitude [78, 15], gradient [16] and hessian [79]; (di) structured pruning [80-82] by remove model sub-structures, e.g., channels [80, 81] and attention heads [42], which are often more aligned with hardware efficiency. All above require training the full dense model first, usually for several rettr rounds.
The recent surge of sparse training seeks adaptively identify high-quality sparse subnetworks and train only them. Starting from scratch, those methods learn to optimize the model weights together with sparse connectivity simultaneously. [32, 33] first introduced the Sparse Evolutionary Training (SET) technique [32], reaching superior performance compared to training with fixed sparse connectivity [83, 36). [37-39] leverages "weight reallocation" " to improve performance of obtained sparse subnetworks. Furthermore, gradient information from the backward pass is utilized to guide the update of the dynamic sparse connectivity [38, 34], which produces substantial performance gains. The latest investigations [40, 41, 35] demonstrate that more exhaustive exploration in the connectivity space plays a crucial role in the quality of found sparse subnetworks. Current sparse training methods mostly focus on convolutional networks. Most of them discuss unstructured sparsity, except a handful [84, 30] considering training convolutional networks with structured sparsity.
3 Methodology
Our SVITE method (and its variants ViTT and SViTE+) is inspired from state-of-the-art sparse train- ing approaches [34, 35] in CNNs. This section presents the sparse exploration of ViT architectures, then shows the detailed procedure of input token selection for extra efficiency gains.
3.1 Sparse VIT Exploration
Revisiting sparse training. Sparse training starts from randomly sparsified model; after optimiz- ing several iterations, it shrinks a portion of parameters based on pre-defined pruning criterion, and activates new connections w.r.t. grow indicators. After upgrading the sparse topology, it trains the new subnetwork until the next update of the connectivity. An illustration of the overall procedure is shown in Figure 1. The key factors of sparse training are sparsity distribution, @ update schedule, @ pruning and 4 grow criterion.
For a consistent description, we follow the standard notations [34, 35]. Let DD be the training dataset. b. D is randomly sampled data batch for iteration t. fw(() represents
Notations.
the model with parameters W (W(1)... .... (())). where (1( e R. 1 < 1 < L, Nr is the
3

---

Transfermer Encoder
Sparse VT Expleration
Prune
Inaefener Benders
Transio Faredes
Tokens
Grow
Remaining Connections
Praned Connection
Training
Growa Connection
-...
Training
......
Traiiig Time
Update Interval AT
Update Sparse Connectivity
Update Interval AT
Concal
Selected Tokens
$
10
Mistt
Token Selection for SVITE+
Thunsornne Prusing
Promcable Weights
Learable Top- X Selection
Sottmax
Nerm
Removeable Modules
M0:00 MEEM
Scores
11
Soorer Function
Scried
Dot-Product
V
W
Skip Connection
Frnsay Will
Adl&
Linear Prujection
WHll
X0
Figure 1: The overall procedure of our proposed sparse VIT exploration framework. Upper Figure: first training VIT for AT iterations, then performing prune-and growwwowwwwww-----ooo strategies explore critical sparse connectivities, repreating until convergence. Bottom Left Figure: enforcing either structured unstructured sparsity transformer layers in ViT. Bottom Right Figure: first scoring each input embedding and applying the learnable top-k selection to identify the most informative tokens.
number of prunable parameters in the 4th layer, and denotes the number of transformer layers. Note that the first linear projection layer and the classifier of ViT [1, 2] are not sparsified in our framework. As illustrated in Figure ((bottom-left) w (w- (1.) T==1 w (w(l.) () 1h=1
w (w-lia) Jh=1 are the weights of the self-attention module in the 4h layer, W(.1), W(L2) w(1,3) are the weights of the multilayer perceptron (MLP) module in the 4th layer, and W(O (W w KR w.", W(..1) W(..),, W(l.3)) collectively represent all the parameters in the 4h layer, where H denotes the number of attention heads, and 1 S < H. X Q K(O,, and V()) are the corresponding input and intermediate features, respectively. Each sparse layer only maintains fraction st E (0, 1) of its connections, and the overall sparsity of a sparse subnetwork is calculated as the ratio of pruned elements to the total parameter counts, i.e., Σ, EN
Sparse Vision Transformer Exploration (SVITE). SVITE explores the unstructured sparse topol- ogy in vision transformers. To be specific, we adopt Erdös-Rényí [32] as our 1 sparsity distribution. The number of parameters in the sparse layer is scaled by t Xm. where is the number of neurons at layer I. This distribution allocates higher sparsities to the layers with more parame- ters by scaling the portion of remaining weights with the sum of the number of output and input neurons/channels. For the @ update schedule, it contains: (i) the update interval AT, which is the number training itcrations between two sparse topology updates; (iz) the end iteration Tend. indicating when to stop updating the sparsity connectivity, and set Tend 80% of total train- ing iterations in our experiments; (ti)) the initial fraction a of connections that can be pruned or grow, which is 50% in case; (fv) decay schedule of the fraction of changeable connections Sdocay (t, a, Tona) = & [1++ cos( Tend )), where cosine annealing is used, following [34, 35]. During each connectivity update, we choose the weight magnitude as @ the pruning indicator, and gradient magnitude O the grow indicator. Specifically, we eliminate the parameters with the layer-wise smallest weight values by applying binary mask Mprune. then grow new connections with the highest magnitude gradients by generating a new binary mask mggrow. Both masks are employed to W()) via the element-wiss dot product, and note that the number of non-zero elements in Mprume and mggrow are equal and fixed across the overall procedure. Newly added connections are not activated in the last sparse topology, and are initialized to zero since produces better performance as demonstrated in [34, 35].

---

Infrequent gradient calculation [34] is adopted in our case, which computes the gradients in an online manner and only stores the top gradient values. As illustrated in [34], such fashion amortizes the extra effort of gradient calculation, and makes it still proportional to 1 long as AT 2 T- where s is the overall sparsity.
Structured Sparse Vision Transformer Exploration (iT Although models with unstruc- tured sparsity achieve superior performance, structured sparsity [80-82] is much more hardware friendly and brings practical efficiency on realistic platforms, which motivates us to propose Struc- tured Sparse ViT Exploration ViTE) We inherit the design of 1 sparsity distribution and @ update schedule from the unstructured SVITE, and a round-up function is used to eliminate decimals in the parameter counting. The key differences lie in the new ① pruning and 4 grow strategies.
Pruning criterion: Let A(,A) denote fea- tures computed from the self-attention
Algorithm 1 Sparse VIT Co-Exploration (SViTE+).
head (W-L.A) w-ll-h) w.( and in-
Initialize: ViT model fw, Dataset D, Sparsity dis- {s1,-.. sL.. Update schedule
tribution &
put embeddings (") as shown in Fig- ure We perform the Taylor expansion to the loss function [16, 42], and derive a proxy score for head importance blow:
{ (AT, Tend, a, fdecay ). Learning rate
1: Initialize fw with random sparsity S reduced parameter count.
b Highly
2: for each training iteration do
3: Sampling batch by 'D
2
4: Scoring the input token embeddings and selecting
I( = ATT.) dAum))
(1)
the top-k informative tokens > Token selection
5:
if (t mod AT = 0) and t < Tend then
where C(-) is the cross-entropy loss 6:
for each layer ( do
used in ViT. During each topology up- date, we remove attention heads with the smallest I For MIPs, score neurons with f-norm of their associ- ated weight vectors [85], and drop in- significant neurons. For example, the Jth neuron W((.)) in Figure has
7:
p = fdecay (f, a, (1end)((110) Performing prune-and-grow with portion w.r.t certain criterion, generating masks Mprune and Mygrow to update fw 's sparsity patterns end for else
8:
Connectivviy exploration
9:
10:
11:
W W nn Vw end if
D Updating Weights
an importance score ||w](t.))] lle,, where w!!!))) is the juh row of W(..)).
12:
13: end for
14: return a sparse ViT with trained token selector
Grow criterion: Similar to [34, 35], we active the new units with the highest magnitude gradients, such as = ll,, and ||
(c(x aw lle, for the hu attention head and the juh
neuron of the MLP (W(L))), respectively, The gradients are calculated in the same manner as the one in unstructured SVITE, and newly added units also initialized to zero
3.2 Data and Architecture Sparsity Co-Exploration for Higher Efficiency
Besides exploring sparse trans- former architectures, we further slim the dimension of input token embeddings for extra efficiency bonus by leveraging a learnable to- ken selector, as presented in Fig- ure 1. Meanwhile, the introduced data sparsity also serves as an im- plicit regularization for VIT train- ing, which potentially leads im- proved generalization ability, as ev- idenced Table 6. Note that, due to skip connections, the number of input tokens actually determines the dimension of intermediate features, which substantially contributes to the overall computation
Algorithm 2 The top-k selector PyTorch-like style.
def topk_ selector (logits, k, tau, dim=-1): Maintain tokens with the top-$k$ highest scores gumbels
-torch. emppy_like (1ogits)) "ep_gggitttt.pponntttaall., exponential, () 11 gumbels = (logits gumbels) / tau
# tau is the temperature
y y_soft gumbels caabbess.sffmaan .off (dim)
# Straight through
index = (k,,, dim=dim) [1] y y_hard scatter (logits, index, k) ret y_hard r_soft.detacht y_soft
return ret
5

---

Table I: Details of training configurations in our experiments, mainly following the settings in [2].
Backbone
Update Schedule (AT, Tomi, a. Jáncyy }
Batch Size
Epochs
Inherited Settings from DeiT [2]
DeiT-Tiny
[20000, 1200000, 0.5, cosine]
512
600
AdamW, 0.0005 x batchulae cosine decay
Deil-Small
(15000, 1200000, 0.5, cosine)
512
600
warmup 5 epochs, 0.05 weight decay 0.1 label smoothing. augmentations, etc.
DeiT-Base
(7000, 600000, 0.5, cosine)
1024
600
cost. In other words, the slimmed input token embeddings directly result in compressed intermediate features, and bring substantial efficiency gains.
For the input tokens ( Rnxd, where n denotes the number of tokens to be shrunk, and is the dimension of each token embedding that keeps unchanged. As shown in Figure 1, all token embeddings are passed through a learnable scorer function which is parameterized by an MLP in our experiments. Then, selection of the top-k importance scores (1 S k S d) is applied on top of it, aiming to preserve the significant tokens and remove the useless ones. To optimize parameters of the scorer function, we introduce the popular Gumbel-Softmad [86, 87] and straigh-thhoouhh tricks [88] to enable gradient back- propaaaatot through the top-k selection, which provides an efficient solution to draw samples from discrete probability distribution. A detailed implementation is in Algorithm 2.
The full pipeline of data and architecture co-exploration is summarized in Algorithm 1. We term this approach SViTE+ We first feed the randomly sampled data batch to the token selector and pick the top-k informative token embeddings. Then, we alternatively train the sparse ViT for AT iterations and perform prune-and-guy -grow to explore the sparse connectivity in ViT' dynamically. In the end, a sparse ViT model with a trained token selector is returned and ready for evaluation.
4 Experiments
Baseline pruning methods. We extend several effective pruning methods from CNN compression as our strong baselines. Unstructured pruning: (i) One-shot weight Magnitude Pruning (OMP) [15], which removes insignificant parameters with the globally smallest weight values; (it) Gradually Magnitude Pruning (GMP) [17], which seamlessly incorporates gradual pruning techniques within the training process by eliminating few small magnitude weights per iteration: and (dii) Taylor Pruning (TP) [16], which utilizes the first-order approximation of the training loss to estimate units' importance for model sparsification. Structured praning: Salience- based Structured Pruning (SSP). We draw inspiration from [42, 85). and remove sub-modules in ViT (e.g., self-attention heads) by leveraging their weight, activation, and gradient information. Moreover, due to the repetitive architecture of ViT, we can easily reduce the number of transformer layers to create a smaller dense ViT (Small-Dense) baseline that has similar parameter counts to the pruned ViT model.
The Overall Performance of SVITE, ViITE and SVITE+
Implementation details. Our experiments are conducted on ImageNet with DeiT- Tiny/Small/Base backbones. The detailed training configurations are listed in Table 1,
82
DeiT Basc
Testing BasiingAccsl Accurazy (%)
80-
DaallSmall
which mainly follows the default setups in [2].
All involved customized hy perparameterss are
78-
tuned via grid search (later shown in Figure 3).
SViTE-Small
76
For a better exploration of sparsity connec- tivities, we increase training epochs to 600 for all experiments. GMP [17] has an addi- tional hyperparameter, i.e., the pruning sched- ule, which starts from \ and ends at of the training epochs with 20 times pruning in total. More details are referred to Appendix A1.
SVITE-Buse
74
ViTE-Baas
DeiT-Tiny
SVITE- -Small
100
FLOPs (x1019)
Top- I accuracy (%) over FLOPs (x 10' on Im- ageNet of our methods, i... SVITE, ViTTE and SVITE+, compared to DeiT baselines, trained on Imagenet- IK only. (sparse) vision transformers on the ImageNet- IK task using CUDA benchmark mode. To be specific we separately calculate the time elapsed during each iteration, to eliminate the impact of the hardware environment as much as possible. Note that the time for the data I/O is excluded.
Figure 2:
Training time measuring protocol. We strictly measure the running time saving of
Highlight of our findings. The overall performance of SVITE, VITTE,, and SVITE+ on DeiT backbones are summarized in Figure 2. We highlight some takeaways below.

---

Takeaways: 1 SVITE produces sparse DeiT's with enhanced generalization and substantial reduced FLOPs, compared to its dense counterpart (*). SViTE+ further improves the performance of SViTE by selecting the most vital patches. @ S'TE achieves matched accuracy on DeiT-Small, and significantly enhances performance on DeiT-Base. Meanwhile, its structural sparsity brings considerable running time savings. Appropriate data and architecture sparsities can effectively regularize ViT training, leading to a new SOTA win-win between ViT accuracy and efficiency.
4.1 SViTE with Unstructured Sparsity
We perform SVTTE to mine vital unstructured sparsity in Dei''s [2]. Solid lines in Figure 2 record the top-1 test-set accuracy over FLOPPs on ImageNet-IK of SViTE-Small and SViTE-Base with range of sparsity from 30% to 70%. In general, we observe that SVITE generates superior sparse ViTs with both accuracy and efficiency gains. Table 2, 3, and present the comparison between SVTTE and various pruning baselines. From these extensive results, draw several consistent observations. First, compared to the dense baselines, SViTE-Tiny, -Small, and -Base obtain 25.56% 34.16%, 46. 46.26% 55.44%, and 47.95% ~ 57.50% FLOPs reduction, respectively, a
at 30% ~ 60% sparsity levels with only a negligible accuracy drop within 0.5%. verifies the effectiveness of our proposal, and indicates severe parameter redundancy in VIT. Second, our SVITE models from dynamic explorations consistently surpass other competitive baseline methods, including OMP, GMP, TP, and Small-Dense by substantial performance margin. Among all the baseline approaches, GMP that advocates a gradual pruning schedule achieves the best accuracy with all three DeiT backbones. Third, in Figure 2, both SViTE-Small (blue solid line) and SViTE-Base (green solid line) show an improved trade-off' between accuracy and efficiency, compared to their dense DeiT counterparts. Interestingly, also observe that with similar parameter counts, large sparse ViT consistently outperforms the corresponding smaller dense VIT. A possible explanation is those appropriate sparse typologies regularize network training and lead to enhanced generalization, which coincides with recent findings of critical subnetworks (i.c., winning tickets) in dense CNNs [89, 22] and NLP transformer [21, 90] models.
Table 2: Results of SVITE- E-Tny on ImageNet- IK
Table 3: Results of SViTE-Small on ImageNet- K.
Accuracics (%) within/out of parenthesis are the repro- duced/reported [2] performance.
Accuracies (%) within/out of parenthesis are the repro- duced//reported [2] performance.
Models
Spansity (NPar.)
FLOPs Saving
Ascuracy (%)
Models
Spursity (dPara.)
FLOPs Saving
Accuracy (%)
DeiT-Ting
(5.72M)
72.20 (71.90)
DeiT-Small
(22. IM)
0%
79.90 (9978)
SVITE-Tiay
30% (4.02M)
25.56%
71.78
SViTE-Small
50% (TLIM)
46 26%
79.72
OMP
(4.02M)
25.56%
(11.IM)
46.25%
GMP
30% (4,02M)
25.56%
69.56
GMP
50% (11.MM
46.26%
76.88
30% (4.02M)
25.56%
68.38
TP
50% (1LI
46.26%
76.30
SVITE-TiRy
40% (3.46M)
34.18%
71.75
SVITE-
60% (8. (8.9M)
55.44%
79.41
OMP
40% (3.46M)
34.16%
66.52
OMP
60% (8.9M)
55.44%
75.32
GMP
40% (3.46M)
34.15%
68.36
GMP
60% (8.9M)
55.44%
76.79
TP
40% (3.46M)
34.17%
65.45
TP
60% (8.9M)
55.44%
74,50
Small-Dense
0% (3.94M)
32.54%
67.33
Small-Dense
(11 (M)
49.32%
73.93
Table 4: Results of VITE with structured sparsity on ImageNet- IK with DeiT-Tnyy/mmllBBase Accuracies (%) within/out of parenthesis the reproduueedheported [2] performance.
Models
Sparsity (%)
Parameters
FLOPs Saving
Running Time Reduced
Top-1 Accuracy (%)
DeiT-Tiny (Dense)
0%
5.72M
0%
0%
72.20 (71.80) 80)
SVITE- Tiny (Unstructured)
30%
4.02M
25.56%
0%
71.78
SSP-Tiny (Structured)
30%
4.21M
23.69%
10.57%
68.59
SPVITE-Tim (Structured)
30%
4,21M
23.69%
10.57%
70.
DeiT-Small (Dense)
0%%
22,1M
0%
0S%
79.90 (79.78)
SVITE-Smal (Unstructured)
40%
13.3M
36.73%
0%
80,26
SSP-Small (Structured)
40%
14.6M
31.63%
22.65%
77.74
S"VITE- Small (Structured)
40%
14.6M
31.63%
22.65%
79.22
DeiT- (Dense)
0%
86.6M
0%
0%
81.80 (80.98)
SViTE-Bas (Unstructured)
40%
52.0M
38.30%
0%
81.56
SSP-Buse (Structured)
40%
56.8M
33%
24.70%
80.08
S'ViTE-Base (Structured)
40%
56.8M
33.13%
24.70%
82.22
4.2
VITE with Structured Sparsity
For more practical benefits, we investigate sparse DeiT's with structured sparsity. Results are summa- rized in Table 4. Besides the obtained 23.79% 33.63% FLOPs savings, V S²
7

---

Small, and S Base enjoy an extra 10.57%. 22.65%, and 24.70% running time reduction, respectively, from 30% 40% structured sparsity with competitive top-1 accuracies. Further- more, ViTE consistently outperforms the baseline structured pruning method (SSP), which again demonstrates the superior sparse connectivity learned from dynamic sparse training.
The most impressive results come from ViVTE--Ba at 40% structured sparsity. It even surpasses the dense DeiT base model by 0.42% 1. 1.24% accuracy with 34.41% parameter counts, 33. 13% FLOPs, and 24.70% running time reductions. We conclude that (7) an adequate sparsity from S VITE boosts ViT's generalization ability, which can be regarded as an implicit regularization: (it) larger ViTs (e.g.. DeiT-Base) tend to have more superfluous self- aelf-attention heads, and are more amenable to structural sparsification from ViTE, based on Figure 2 where dash lines denote the overall performance of S' and S-VIE-BBase with a range of sparsity from 30% to 70%.
Table 5: Results of SVITE-Bar on ImageNet- IK.
Table 6: Results of --iTE+ on ImageNet- 1 K. Accuracies (%) within/out of parenthesis are the repro- duced/reported [2] performance.
Accuracies (%) within/out of parenthesis the repro- duced/reported [2] performance.
Models
Sparsity (MPrra.)
FLOPs Saving
Accuracy (%))
# #lokens (%)
Time Reduced
FLOPs Saving
Accuracy (%)
DeTT Base
0% (86.6M)
0%
81.80 (80.08)
SViTE+-Small 50% Unstructured Sparsit
SVITE-Base
50% (43.4M)
47.95%
81.51
100%
0%
46.26%
79.72
OMP
47.94%
95%
4,40%
49.32%
80.18
GMP
50% (43.4M)
47.95%
80.79
90%
7.63%
52.38%
79.91
TP
50% (43.4M)
47.94%
80.55
70%
19.77%
63.95%
77.90
SVITE-Base
60% (34.8M)
57,50%
81.28
S SiViEE+SSaall 40% Structured Sparsity
OMP
57.50%
100%
22.65%
31.63%
79.22
GMP
60% (34.8M)
57.50%
80.44
95%
27.17%
37.76%
78. 78.44
60% (34.8M)
57.49%
80.37
90%
29.21%
41.50%
78.16
Small Dense
0% (44.0M)
49.46%
78.59
70%
39.10%
54.96%
74.77
4.3 SVITE+ with Data and Architecture Sparsity Co-Exploration
In this section, we study data and architecture sparsity co-exploration for ViTs, i.e., SViTE+, Blessed by the reduced input token embeddings, even ViTs with unstructured sparsity can have running time savings. The benefits are mainly from the shrunk input and intermediate feature dimensions. Without loss of generality, we consider SViTE+-Small with 50% unstructured sparsity and S with 40% structured sparsity as examples. As shown in Table 6 and Figure 2, SSilE+ at 50% unstructured sparsity capable of abandoning 5% 10% tokens while achieving 4.40% ~ 7.63% running time and 49.32% ~ 52.38% FLOPs savings, with even improved top-1 testing accuracy. It again demonstrates that data sparsity as an implicit regularizer plays a beneficial role VIT training. However, slimming input and intermediate embedding is less effective when incorporated with ViTE, suggesting that aggressively removing structural sub-modules hurts VIT's generalization.
4.4 Ablation and Generalization Study of SVITES
Update interval in SVITE. The length of the update interval AT controls one of the essential trade- offs in our proposed dynamic sparse exploration, since AT multiplying the number of updates the pre-defined Tend. On the one hand, a larger updated interval (i.e., smaller update frequency) produces a more well-trained model for improved estimation of units' importance. On the other hand, larger update frequency (i.e., smaller AT) allows more sufficient exploration of sparse connectivities, which potentially generates higher-quality sparse subnetworks, as demonstrated in [35]. We evaluate this factor in our SVITE context, and collect the results in Figure 3 (Left). We observe that AT 20000 works the best for EViTE-Tiny. and both larger and smaller AT degrade the performance.
ACCURACY
68.45
69.09
69.30
69.60
68.60 84
68.84
69.60
ACCURACY
66,77
67.88
65.84
65.72
1000
2000
5000
10000
15000
20000
25000
1024
512
256
128
Update Interval (AT)
Batch Size (b)
Figure 3: Accuracy of SViTE-Tiny with 50% unstructured sparsity. Left: ablation studies the update interval
(AT); Right: ablations studies of the adopted batch size (b).

---

DeiT-Base
S 40% Structured Spanity
with Unstractured Sparsity
Figure 4: Attention probabilities for DeiT-Base, S Basc, and SViTE-Base models with layers (rows) and 12 heads (columns) using visualization tools provided 194]. Attention maps are averaged over 100 test samples from ImageNet-1K IK to present head behavior and remove the dependence on the input content. The black square is the query pixel. indicates pruned attention heads. Zoom-in for better visibility.
D
Figure 5: Leamed patch selection patterns of SViTE+-Small at 10% data and 50% architecture sparsity levels. i indicates removed inessential patches.
Batch size in SVITE. Besides the update interval AT, batch size (b) also affects the aforementioned trade-off, especially for the data-hungy ViT training. We investigate different batch sizes in Figure 3 (Right), and find that 512 outperforms other common options for SViTE-Tiny
Generalization study of SVITE and its variants. It is worth mentioning that proposed frame- works (SVITE, VPTTE,, SViTE+) are independent of the backbone architectures, and can be easily plugged in other vision transformer models [91, 45, 92, 93]. We implemented both SVITE and S*ViTE on TNT-S [91]. SViTE-TNT-S gains 0.13 accuracy improvements (Ours: 81.63 v.s. TNT-S: 81,50) and 37.54% FLOPs savings 40% unstructured sparsity; S²ViTE-TNT-S obtains 32.96% FLOPs and 23.71% running time reductions at 40% structured sparsity with almost unimpaired accuracy (Ours: 81.34 v.s. TNT-S:81.50).
Visualization
Sparse connectivity patterns. We provide unit-wise and element-wise heatmap visualizations for SViTE-Bate with 40% structured sparsity in Figure A7 (in Appendix). Similarly, element-wise heatmap visualizations of WiTEEBBse with 50% unstructured sparsity are displayed in Figure A6. We find that even unstructured sparsity exploration can develop obvious structural patterns (i.e., "vertical lines" in mask heatmaps), which implies stronger potential for hardware speedup [95].
Self-attention heatmaps. As shown in Figure 4, we utilize tools in [94] to visualize attention maps of (sparse) ViTs. Multiple attention heads show similar behaviors, which implies the structural redundancy. Fortunately, V"VITE eliminates unnecessary heads to some extent. With regard to SViTE-Base's visual results, seems to activate fewer attention heads for predictions (darker colors mean larger values), compared the ones of dense DeiT-Base. We also observe that in the bottom layers, the attention probabilities are more centered at several heads; while in the top layers, the attention probabilities more uniformly distributed. This kind of tendency is well preserved by sparse ViT (SViTE) from Dense ViTs.
Learned patch selection patterns. Figure 5 presents the learned behaviors of our token selector in SViTE+. We observe that the useless removed patches are typically distributed around the main object

---

or in the background. Meanwhile, the patches within the objects of interest are largely persevered, which evidences the effectiveness of our learned patch token selector.
Conclusion and Discussion of Broader Impact
In this work, we introduce sparse ViT exploration algorithms, SVITE, and its variants S and SViTE+, to explore high-quality sparse patterns in both ViT's architecture and input token embeddings, alleviating training memory bottleneck and pursuing inference ultra-efficiency (e.g.. running time and FLOPs). Comprehensive experiments on ImageNet validate the effectiveness of our proposal. Our informative visualizations further demonstrate that SViTE+ is capable of mining crucial connections and input tokens by eliminating redundant units and dropping useless token embeddings. Future work includes examining the performance of our sparse ViT's on incoming hardware accelerators [96-100], which will provide better supports for sparsity.
This work is scientific in nature, and we do not believe it has immediate negative societal impacts. Our findings of sparse vision transformers are highly likely to reduce both memory and energy costs substantially, leading economic deployment in real-world applications (e.g., on smartphones).
Acknowledgment
Z.W. is in part supported by an NSF RTML, project (#2053279).
References
[1] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. arXiv preprint arXiv:2010. /929, 2020.
[2] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco Massa, Alexandre Sablayrolles. and Hervé Jégou. Training data-efficient image transformers & distillation through attention. arXiv preprint arXiv:2012. 12877, 2020.
[3] Kai Han, Yunhe Wang, Hanting Chen, Xinghao Chen, Jianyuan Guo, Zhenhua Liu, Yehui Tang, An Xiao, Chunjing Xu, Yixing Xu, et al. A survey on visual transformer. arXiv preprint arXiv:2012. 12556, 2020.
[4] Minghang Zheng, Peng Gao, Xiaogang Wang, Hongsheng Li, and Hao Dong. End-to-end object detection with adaptive clustering transformer. arXiv preprint arXiv:2011.09315, 2020.
[5] 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.
[6] Zhigang Dai, Bolun Cai, Yugeng Lin, and Junying Chen. Up-detr: Unsupervised pre-training for object detection with transformers. arXiv preprint arXiv:2011.09090 2020.
[7] Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai. Deformable (detr): Deformable transformers for end-to-end object detection. In International Conference on Learning Representations, 2021.
[8] Hanting Chen, Yunhe Wang, Tianyu Guo, Chang Xu, Yiping Deng, Zhenhua Liu, Siwei Ma, Chunjing Xu, Chao Xu, and Wen Gao. Pre-trained image processing transformer. arXiv preprint arXiv:2012. 00364, 2020.
[9] Fuzhi Yang, Huan Yang, Jianlong Fu, Hongtao Lu, and Baining Guo. Learning texture transformer network for image super-resolution. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 5791-5800, 2020.
[10] Niki Parmar, Ashish Vaswani, Jakob Uszkoreit, Lukasz Kaiser, Noam Shazeer, Alexander Ku, and Dustin Tran. Image transformer. International Conference on Machine Learning, pages 4055-4066 PMLR, 2018
10

---

[11] Mark Chen, Alec Radford. Rewon Child, Jeffrey Wu, Heewoo Jun, David Luan, and llya Sutskever. Generative pretraining from pixels. In Hal Daumé III and Aarti Singh, editors. Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1691-1703. PMIRR 13-18 Jul 2020.
[12] Yifan Jiang, Shiyu Chang, and Zhangyang Wang. Transgan: Two transformers can make one strong gan. arXiv preprini arXiv:2 2021.
[13] Mingjian Zhu, Kai Han, Yehui Tang, and Yunhe Wang. Visual transformer pruning, 2021.
[14] Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. A survey of model compression and acceleration for deep neural networks. arXiv preprint arXiv: 1711v11710.09282, 2017.
[15] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. In International Conference on Learning Representations, 2016.
[16] Pavlo Molchanov, Arun Mallya, Stephen Tyree, luri Frosio, and Jan Kautz. Importance estimation for neural network pruning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1264-11272, 2019.
[17] Michael Zhu and Suyog Gupta. To prune, or not to prune: exploring the efficacy of pruning for model compression. arXiv preprint arXiv:1710.01873 2017.
[18] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2018.
[19] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Linear 2019.
mode connectivity and the lottery ticket hypothesis. arXiv preprint
[20] Zhenyu Zhang. Xuxi Chen, Tianlong Chen, and Zhangyang Wang. Efficient lottery ticket finding: Less data is more. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12380-12390. PMLR, 18-24 Jul 2021.
[21] Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained bert networks. arXiv preprint 1rXiv:2007.12223, 2020.
[22] Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Michael Carbin, and Zhangyang Wang. The lottery tickets hypothesis for supervised and self-supervised pre-training in computer vision models. arXiv preprint arXiv:2012.06900. 2020.
[23] Xuxi Chen, Zhenyu Zhang, Yongduo Sui, and Tianlong Chen. [GAN)s can play lottery tickets too. In International Conference Learning Representations, 2021.
[24] Haoyu Ma, Tianlong Chen, Ting-Kuei Hu, Chenyu You, Xiaohui Xie, and Zhangyang Wang. Good students play big lottery better. arXiv preprint arXiv:2101.03255, 2021.
[25] Zhe Gan, Yen-Chun Chen, Linjie Li, Tianlong Chen, Yu Cheng, Shuohang Wang, and Jingjing Liu. Playing lottery tickets with vision and language. arXiv preprint arXiv:2 1832, 2021.
[26] Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. arXiv preprint arXiv:2102.06790, 2021.
[27] Tianlong Chen, Yu Cheng, Zhe Gan, Jingjing Liu, and Zhangyang Wang. Ultra-data- efficient gan training: Drawing lottery ticket first, then training it toughly. arXiv preprint urXiv:2103.0083 2021.
[28] Namhoon Lee, Thalaiyasingam Ajanthan, and Philip Torr. Snip: Single-shot network pruning based on connection sensitivity. In International Conference Learning Representations, 2019.
[29] Chaoqi Wang, Guodong Zhang, and Roger Grosse. Picking winning tickets before training by preserving gradient flow. In International Conference Learning Representations, 2020.
11

---

[30] Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Richard G. Baraniuk, Zhangyang Wang, and Yingyan Lin. Drawing early-bird tickets: Toward more efficient training of deep networks. In International Conference on Learning Representations, 2020.
[31] Xiaohan Chen, Yu Cheng, Shuohang Wang, Zhe Gan, Zhangyang Wang, and Jingjing Liu. Earlybert: Efficient bert training via early- bird lottery tickets. arXiv preprint arXivv2101.000 10000003,, 2020.
[32] Decebal Constantin Mocanu, Elena Mocanu, Peter Stone, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. Scalable training of artificial neural networks with adaptive sparse connectivity inspired by network science. Nature communications, 9(1):1-12, 2018.
[33] Shiwei Liu, Decebal Constantin Mocanu, Amarsagar Reddy Ramapuram Matavalam, Yulong Pei, and Mykola Pechenizkiy. Sparse evolutionary deep learning with over one million artificial neurons on commodity hardware. Neural Computing and Applications, 2020.
[34] Utku Evei, Trevor Gale, Jacob Menick, Pablo Samuel Castro, and Erich Elsen. Rigging the lottery: Making all tickets winners. In International Conference on Machine Learning, pages 2943-2952. PMLR, 2020.
[35] Shiwei Liu, Lu Yin, Decebal Constantin Mocanu, and Mykola Pechenizkiy. Do actually need dense over-paraameterivaaion?? in-time over-parameterizzaion in sparse training. arXiv preprint arXiv:2102.02887, 2021.
[36] Utku Evci, Fabian Pedregosa, Aidan Gomez, and Erich Elsen. The difficulty of training sparse neural networks. arXiv preprint arXiv: 107, 2019.
[37] Hesham Mostafa and Xin Wang. Parameter efficient training of deep convolutional neural networks by dynamic sparse reparameterization. In International Conference Machine Learning, 2019.
[38] Tim Dettmers and Luke Zettlemoyer. Sparse networks from scratch: Faster training without losing performance. arXiv preprint arXiv:1907.04840. 2019.
[39] Shiwei Liu, Decebal Constantin Mocanu, Yulong Pei, and Mykola Pechenizkiy. Selfish sparse 2021.
mn training. arXiv preprint
[40] Siddhant Jayakumar, Razvan Pascanu, Jack Rae, Simon Osindero, and Erich Elsen. Top-kast: Top-k always sparse training. Advances in Neural Information Processing Systems, 33, 2020.
[41] Md Aamir Raihan and Tor M Aamodt. Sparse weight activation training. arXiv preprint arXiv:2001.0166, 2020.
[42] Paul Michel, Omer Levy, and Graham Neubig. Are sixteen heads really better than one?, 2019.
[43] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008. 2017.
[44] Jianyuan Guo, Kai Han, Han Wu, Chang Xu, Yehui Tang, Chunjing Xu, and Yunhe Wang. Cmt: Convolutional neural networks meet vision transformers. arXiv preprint arXiv:2107.0626. 2021.
[45] Li Yuan, Yunpeng Chen, Tao Wang, Weihao Yu, Yujun Shi, Zihang Jiang, Francis EH Tay, Jiashi Feng, and Shuicheng Yan. Tokens-to-token vit: Training vision transformers from scratch imagenet. arXiv preprint arXiv:2101. 2021.
[46] Huiyu Wang, Yukun Zhu, Hartwig Adam, Alan Yuille, and Liang-Chich Chen. Max-deeplab: End-to-end panoptic segmentation with mask transformers, arXiv preprint arXiv:2012.00759, 2020.
[47] Yuqing Wang, Zhaoliang Xu, Xinlong Wang, Chunhua Shen, Baoshan Cheng, Hao Shen, and Huaxia Xia. End-to-end video instance segmentation with transformers. arXiv preprint arXiv:2011.145033 2020.
12

---

[48] Yanhong Zeng, Jianlong Fu, and Hongyang Chao. Learning joint spatial-temporaa transfor- mations for video impainting In European Conference on Computer Vision, pages 528-543. Springer, 2020.
[49] Luowei Zhou, Yingbo Zhou, Jason J Corso, Richard Socher, and Caiming Xiong. End-to-end dense video captioning with masked transformer. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9739-8748, 2018.
[50] Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee. Vilbert: Pretraining task-agnostic visiolinguistic representations for lision-and-langaage tasks. arXiv preprint arXiv:1908 02265, 2019.
[51] Hao Tan and Mohit Bansal. Lxmert: Learning cross-modality encoder representations from transformers. arXiv preprint arXiv:1908. 07490, 2019.
[52] Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu. Uniter: Universal image-text representation learning. In European Confer- ence on Computer Vision, pages 104-120. Springer, 2020.
[53] Weijie Su, Xizhou Zhu, Yue Cao, Bin Li, Lewei Lu, Furu Wei, and Jifeng Dai. Vl-bert: Pre-training of generic visual- linuul-inguistic representations. arXiv preprint arXiv:1908.000 1908.08530, 2019.
[54] Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsich, and Kai-Wei Wei Chang. Visualbert: A simple and performant baseline for vision and language. arXiv preprint 190iv:190..0333 2019.
[55] Gen Li, Nan Duan, Yuejian Fang, Ming Gong, and Daxin Jiang. Unicoder-vl: A universal encoder for vision and language by cross-modal pre-training In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 11336-11344, 2020.
[56] Xiujun Li, Xi Yin, Chunyuan Li, Pengchuan Zhang, Xiaowei Hu, Lei Zhang, Lijuan Wang, Houdong Hu, Dong, Furu Wei, et al. Oscar: Object-semantics aligned pre-training for vision-language tasks. In European Conference Computer Vision, pages 121-137. Springer, 2020.
[57] Luowei Zhou, Hamid Palangi, Lei Zhang, Houdong Hu, Jason Corso, and Jianfeng Gao. Unified vision-language pre-training for image captioning and vqa. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 13041-13049, 2020.
[58] Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip Torr, and Vladlen Koltun. Point transformer. arXiv preprint arXiv:2012.09 1964 2020.
[59] Angela Fan, Edouard Grave, and Armand Joulin. Reducing transformer depth on demand with structured dropout. In International Conference on Learning Representations, 2020.
[60] Fu-Ming Guo, Sijia Liu, Finlay S Mungall, Xue Lin, and Yanzhi Wang. Reweighted proximal pruning for large-scale language representation. arXiv preprint arXiv: /2486, 2019.
[61] Prakhar Ganesh, Yao Chen, Xin Lou, Mohammad Ali Khan, Yin Yang. Deming Chen, Mari- anne Winslett, Hassan Sajjad, and Preslav Nakov. Compressing large-scale transformer-basel models: A case study on bert. arXiv preprint arXiv:2002.11988 2020.
[62] S. McCarley, Rishay Chakravarti, and Avirup Sil. Structured pruning of bert-based question answering model. arXiv preprint 19..v:1910.000000
2019.
[63] Yehui Tang, Kai Han, Yunhe Wang, Chang Xu, Jianyuan Guo, Chao Xu, and Dacheng Tao. Patch slimming for efficient vision transformers. arXiv preprint 1iXXv:21060028555 2021.
[64] Pengchuan Zhang, Xiyang Dai, Jianwei Yang, Bin Xiao, Lu Yuan, Lei Zhang, and Jianfeng Gao. Multi-scale vision longformer: A new vision transformer for high-resolution image encoding. arXiv preprint arXiv:2 153558 2021.
[65] Iz Beltagy, Matthew E. Peters, and Arman Cohan. Longformer: The long-dd transformer. arXiv preprint arXiv:2004.05750, 2020.
13

---

[66] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.0444 2020.
[67] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention-based permutation-invariant neural networks. In International Conference on Machine Leurning, pages 3744-3753. PMLR, 2019.
[68] Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-bass based sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53-68 68, 2021.
[69] Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, and Timothy Lillicrap, Compressive transformers for long-range sequence modelling. arXiv preprint arXiv:/91 00055/911.005,, 2019.
[70] Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim Salimans. Axial attention in multidimensional transformers. arXiv preprint arXiv:/912.12/000 2019.
[71] Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning, pages 5156-5165. PMLR, 2020.
[72] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009. 1et00099914794 14794, 2020.
[73] Yi Tay, Mostafa Dehghani, Samira Abnar, Yikang Shen, Dara Bahri, Philip Pham, Jinfeng Rao, Liu Yang, Sebastian Ruder, and Donald Metzler. Long range arena: A benehmark for efficient transformers. arXiv preprint arXiv:201 (0t::2011..044 1.04006, 2020.
[74] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler. Efficient transformers: A survey. arXiv preprint arXiv:2009.0673 2020.
[75] Sinong Wang, Belinda Z. Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self- attention with linear complexity, 2020.
[76] Bowen Pan, Yifan Jiang, Rameswar Panda, Zhangyang Wang, Rogerio Feris, and Aude Oliva. la-red?: Interpretability redundancy reduction for vision transformers, 2021.
[77] Yann LeCun, John S Denker, and Sara A Solla. Optimal brain damage. In Advances in neural information processing systems, pages 598-605, 1990.
[78] Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 1135-1143, Curran Associates, Inc., 2015.
[79] Yann LeCun, John S. Denker, and Sara A. Solla. Optimal brain damage. In D. S. Touretzky, edi- tor, Advances in Neural Information Processing Systems 2, pages 995-605, -agaannK 1990.
[80] Zhuang Liu, Jianguo Li, Zhiqiang Shen, Gao Huang, Shoumeng Yan, and Changshui Zhang. Learning efficient convolutional networks through network slimming. In Proceedings of the IEEE International Conference on Computer Vision, pages
2017.
[81] Yihui He, Xiangyu Zhang, and Jian Sun. Channel pruning for accelerating very deep neural networks. In Proceedings of the IEEE International Conference on Computer Vision, 2017.
[82] Hao Zhou, Jose M Alvarez, and Fatih Porikli. Less is more: Towards compact enns. In European Conference on Computer Vision, pages 662-677. Springer, 2016.
[83] Decebal Constantin Mocanu, Elena Mocanu, Phuong H Nguyen, Madeleine Gibescu, and Antonio Liotta. A topological insight into restricted boltzmann machines. Machine Learning, 104(2-3)243-2700 2016.
14

---

[84] Sangkug Lym, Esha Choukse, Siavash Zangeneh, Wei Wen, Sujay Sanghavi, and Mattan Erez. Prunetrain: fast neural network training by dynamic sparse model reconfiguration. In Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1-13, 2019.
[85] Brian R Bartoldson, Ari S Morcos, Adrian Barbu, and Gordon Erlebacher. The generalization- stability tradeoff in neural network pruning. arXiv preprint arXiv: /906. 03728, 2019.
[86] Emit J. Gumbel. Statistical theory of extreme values and some practical applications. The Journal of the Royal Aeronautical Society, 58(527):792-799) 1954.
[87] Chris J Maddison, Daniel Tarlow, and Tom Minka. A sampling. arXiv preprint
2014.
[88] Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley Osher, Yingyong Qi, and Jack Xin. Understanding thraugh estimator in training activation quantized neural nets. arXiv preprint arXiv:1903.05662 2019.
[89] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. The lottery ticket hypothesis at scale. arXiv preprint arXiv:1903.0160 2019.
[90] Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv:1902.09574 2019.
[91] Kai Han, An Xiao, Enhua Wu, Jianyuan Guo, Chunjing Xu, and Yunhe Wang. Transformer in transformer. arXiv preprint arXiv:2103.001 12, 2021.
[92] 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. arXiv preprint arXiv:2102.12122, 2021.
[93] Daquan Zhou, Bingyi Kang, Xiaojie Jin, Linjie Yang, Xiaochen Lian, Zihang Jiang, Qibin Hou, and Jiashi Feng. Deepvit: Towards deeper vision transformer. arXiv preprinl arXiv:2103./ 11886, 2021.
[94] Sran-Baptiste Cordonnier, Andreas Loukas, and Martin Jaggi. On the relationship between self- attention and convolutional layers. In International Conference on Learning Representations, 2020.
[95] Erich Elsen, Marat Dukhan, Trevor Gale, and Karen Simonyan. Fast sparse convnets. In Proceedings of the IEEE/CVE conference on computer vision and pattern recognition, pages 14629-14638, 2020.
[96] Peiqi Wang, Yu Ji, Chi Hong, Yonggiang Lyu, Dongsheng Wang, and Yuan Xie. Snrram: An efficient sparse neural network computation architecture based on resistive random-access memory. In 2018 55th ACM/ESDA//EFE Design Automation Conference (DAC), pages 1 1-6, 2018.
[97] Mike Ashby, Christiaan Baaij. Peter Baldwin, Martijn Bastiaan, Oliver Bunting, Aiken Caim- cross, Christopher Chalmers, Liz Corrigan, Sam Davis, Nathan van Doorn et al. Exploiting unstructured sparsity on next-generation datacenter hardware. None, 2019.
[98] Chen Liu, Guillaume Bellec, Bernhard Vogginger, David Kappel, Johannes Partzsch, Felix Neumärker, Sebastian Höppner, Wolfgang Maass, Steve B Furber, Robert Legenstein, et al. Memory-efficient deep learning spinnaker 2 prototype. Frontiers in neuroscience, 12:840, 2018.
[99] Song Han, Xingyu Liu, Huizi Mao, Jing Pu, Ardavan Pedram, Mark A. Horowitz, and William J. Dally. Eie: Efficient inference engine compressed deep neural network. In 2016 ACM/IEE 43rd Annual International Symposium on Computer Architecture (ISCA), pages 243 254, 2016.
[100] Yu-Hsin Chen, Tien-Ju Yang, Joel Emer, and Vivienne Sze. Eyeriss v2: A flexible accelerator for emerging deep neural networks on mobile devices. IEEE Journal on Emerging and Selected Topics in Circuits and Systems, 9(2):922-308 2019.
15


Reviews:
[{"review_id": "olC4pBAYz-U", "reviewer": "Reviewer_tKZe", "summary": "This work proposes sparse ViT algorithms, named as SViTE and its variants S^2ViTE, and SViTE+, to explore high-quality sparse patterns in both ViT’s architecture and input token embeddings. The proposed methods can jointly optimize model parameters and explore connectivity throughout training. Experiments are conducted on ImageNet to validate the effectiveness of the proposed methods and find that SViTE+ can mine crucial connections and input tokens.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "This work aims to explore the sparse vision transformers by unstructured and structure pruning methods. The proposed SViTE and its variants S^2ViTE, and SViTE+ achieve impressive results on baselines.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1. The reproduced result on DeiT-base is much lower than the reported results (80.98 v.s. 81.80). What's the potential reason? DeiT has opensource the training scripts and pretrained weights. If considering the reported results of DeiT as the baseline, SViTE and its variants do not achieve such impressive improvements as stated in the paper.\n2. The proposed method is only validated on the DeiT but not validated on more advanced image transformer architecture such as TNT[1], T2T[2], PVT[3], etc. It would be better to validate the effects of the proposed methods (at least S^2ViTE) on more architectures.   \n\n\n[1] Han, Kai, et al. \"Transformer in transformer.\" arXiv preprint arXiv:2103.00112 (2021). \n[2] Yuan, Li, et al. \"Tokens-to-token vit: Training vision transformers from scratch on imagenet.\" arXiv:2101.11986 (2021). \n[3] Wang, Wenhai, et al. \"Pyramid vision transformer: A versatile backbone for dense prediction without convolutions.\" arXiv preprint arXiv:2102.12122 (2021).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "_j-MQQS0Os", "reviewer": "Reviewer_EjXo", "summary": "The author proposes three methods for achieving sparse vision transformers to reduce the number of parameters and FLOP. By using a dynamic structured sparsity injecting method, the authors are able to achieve promising speedup without loss of accuracy. For an example, the author claims to achieve 14.7% run time reduction with 0.42% accuracy improvement. However, the training settings of the author's experiments and the DeiT baseline are different. Thus, there are some ambiguities exits.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Strength:\n\n1. The paper is well organized and easy to follow.\n2. The sparsity in vision transformers is an interesting problem to explore as it could be potentially used to apply ViTs on large input images which otherwise will cause a huge cost of the computation memory.\n3. The token selector is an interesting propose to dynamically select the top-k tokens that are more important to a given input sample.\n\nWeakness:\n\n1. The proposed methods are trained with longer epochs than the baseline models (600 VS 300). It has been proven that training with longer epochs will further increase the performance of the ViTs with proper augmentation. Thus, it is not clear if the proposed method is able to achieve better accuracy with less parameters and computations or the method is actually applied on a stronger baseline and the the accuracy is actually reduced from the stringer baseline.\n\n2. The idea of selecting Top-k tokens is interesting but the current analysis is not enough to support its efficiency. There is no ablations on the impacts of the selector. For example, as shown in Fig. 6 in [1], the sparsity of the attention map is increasing from bottom layers to the top layers. As the attention map sparsity is related to the token sparsity, it may be more convincing to show if following a decaying sparsity could better preserve the model accuracy and the proposed method could learned a layer-wise sparsity that is following such kind of observations.\n\n3. Based on the results in Tab. 4 in the paper, it seems that the accuracy drop is more significant on smaller models. Considering that the proposed methods are all trained with 2x longer epochs, it is not clear what is the performance drop on large models given a well trained baseline.\n\nOverall, I agree that injecting sparsity into ViTs is an interesting and meaningful topic to explore. However, based on the current experiments results and ablation analysis, I am not clear the impacts of the proposed method on the accuracy.  I am willing to increase my score if the author could address my concerns sufficiently.\n\n[1] Zhou, D., Kang, B., Jin, X., Yang, L., Lian, X., Jiang, Z., ... & Feng, J. (2021). Deepvit: Towards deeper vision transformer. arXiv preprint arXiv:2103.11886.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "9DQDHb7H0vq", "reviewer": "Reviewer_ZXSe", "summary": "This work pioneered to study of various sparse training and pruning techniques to the recently proposed vision transformers (ViT). It shows the effectiveness of pruning/sparse training/data selection in such settings. This is a  interesting work for both ViT and sparse learning communities. ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Positive \n+\tThis paper presents a particularly comprehensive study for bringing sparsity into ViTs. Sparsity itself is addressed from various angles, e.g., data sparsity and sparse training connectivity (structured and unstructured). \n+\tThe authors studied a structured version of sparse training. Unlike CNNs where structural sparsity is often enforced by channel prunin, the authors leveraged a BERT-like idea to defined the importance of self-attention heads, by first-order loss approximation. \n+\tThe authors experimented with various ViT and DeitT models on ImageNet. Their results are very useful and interesting. Sparsely trained VIT can outperform the dense baseline and other state-of-the-art methods to obtain sparsity. \n+\tOverall, this paper establishes so far the most promising trade-off between ViT accuracy and efficiency.  Interestingly, with similar parameter counts, a large sparse ViT consistently outperforms the corresponding smaller dense ViT.\n+\tThe work suggests sparsity conveys not only higher efficiency for transformer, but even sometimes improved accuracy. That potentially will lend a better understanding of the optimization difficulty in training ViTs, which recently received much attention.\n+\tFigures, algorithms, pseudocodes, and summary-of-takeaway windows help understand this paper.\n\nNegative\n-\tI am not impressed by SViTE+ results. Look at Table 6, only 5- 10% of tokens can be removed without compromising accuracy. 30% removed would drop accuracy to unacceptable. This is surprising to me, since apparently many tokens would be redundant for making predictions on an image. The author might have to explain why. \n-\tAlso, SViTE+ seems not compatible with structural sparsity.\n-\tThe abstract highlights two results, both improving test accuracy while saving parameters and running time. Whereas those are good, the authors organized their statements in a quite confusing way, e.g., I was only expecting some counterintuitive results after “Perhaps most surprisingly,..”, but the authors laid another similar-flavor result before that one. That caused a negative reading experience (especially it is in the abstract). \n-\tAlso, since most results still mildly sacrificed some accuracy, it is inappropriate or misleading to highlight only two rare results with occasional accuracy gains. This looks like an accidental writing inconsistency issue but must be fixed.\n-\tThe paper overall has a quite clear and logical outline. But it, unfortunately, suffers from a number of annoying typos such as “ scarifying” (many times!) and “ typologies”. More careful proofreading would have helped. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Efficient training and inference can save ML costs, leading to more economic ML deployment in real-world applications. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5h"}, "extra_text": {}}, {"review_id": "16Qz1vwgjXg", "reviewer": "Reviewer_6KF1", "summary": "Vision Transformers (ViT) have attracted much attention recently; however their large model sizes and high training cost pose practical problems for computer vision tasks. This paper introduces sparse ViT exploration algorithms ($SViTE$, $S^2ViTE$, $SViTE+$) to explore sparse patterns in the ViT architectures. The goal is to alleviate the training memory bottleneck and achieving high inference efficiency. The authors conducted comprehensive experiments on ImageNet dataset to validate their approach.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "**Strengths:**\n\n- The paper is clear, well-written and well organized.\n- The authors included different illustrations and descriptions of the proposed algorithms. In addition to including several visualizations such as the sparse connectivity patterns and self-attention heatmaps.\n- The experimental results show the efficiency of the proposed methods. The gain in the classification accuracy and the runtime savings are significant in many cases.\n- The proposed methods could open a way for training and utilizing Vision Transformer models in an efficient way for complex computer vision tasks especially for low resources devices and real-time applications. \n\n\n**Weaknesses:** \n\n- The novelty of the proposed methods seem to be highly incremental. It seems the methods/ideas presented here were borrowed from the prior related work ([24], [25]); the difference seems to be applying those methods on Vision Transformers. \n- In the visualization Figure 5, the dropped/selection patches patterns seem to be random. There is high similarity between many of the background patches and other patches that weren't dropped. \n- Some visualizations are not clear enough. For example, in Figure 4, I couldn't notice the black squares mentioned in the caption.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There is no potential negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "24"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Four experts reviewed this paper and gave ratings 6, 6, 6, and 7, respectively. The reviewers expressed concerns about novelty, writing, and some details, but they generally appreciated the study of sparsity in Transformers. Some reviewers especially liked the results. AC felt that the concerns can be addressed in a light revision of the paper after reading the rebuttal and the post-rebuttal discussions. Hence, the decision is to recommend the paper for acceptance. The authors are encouraged to make necessary changes in the camera-ready to address the reviewers' questions to the best of their ability. We congratulate the authors on the acceptance of their paper!

Decision: Accept (Poster)