Dynamic Grained Encoder for Vision Transformers
Authors: Lin Song
Songyang Zhang
Songtao Liu
Zeming Li
Xuming He
Hongbin Sun
Jian Sun
Nanning Zheng
Venue: NeurIPS 2021 Poster (2021)
Keywords: Computer Vision
Vision Transformer
Dynamic Network

Abstract: Transformers, the de-facto standard for language modeling, have been recently applied for vision tasks. This paper introduces sparse queries for vision transformers to exploit the intrinsic spatial redundancy of natural images and save computational costs. Specifically, we propose a Dynamic Grained Encoder for vision transformers, which can adaptively assign a suitable number of queries to each spatial region. Thus it achieves a fine-grained representation in discriminative regions while keeping high efficiency. Besides, the dynamic grained encoder is compatible with most vision transformer frameworks. Without bells and whistles, our encoder allows the state-of-the-art vision transformers to reduce computational complexity by 40%-60% while maintaining comparable performance on image classification. Extensive experiments on object detection and segmentation further demonstrate the generalizability of our approach. Code is available at https://github.com/StevenGrove/vtpack.

Dynamic Grained Encoder for Vision Transformers
Lin Song Songyang Zhang 2.4.5+ Songtao Liu Zeming Li Hongbin Sun Jian Sun
Xuming He²
Nanning Zheng* 1 College of Artificial Intelligence, Xi'an Jiaotong University ShanghaiTech University
Megvii Inc. (Facc++) *University of Chinese Academy of Sciences
Shanghaii Institute of Microsystem and Information Technology, Chinese Academy of Sciences stevengrove nu.xxjt.edd.com sy.zhangbuaa @ geagl..ammmmm com,
liusongtao @ megvii.com, hexm @ betanghaitech.du.... (hsun, nnzheng) emaal.xjt..edu.cm (lizeming, sunjian) @megvii.com
Abstract
Transformers, the de-facto standard for language modeling, have been recently applied for vision tasks. This paper introduces sparse queries for vision trans- formers to exploit the intrinsic spatial redundancy of natural images and save computational costs. Specifically, we propose Dynamic Grained Encoder for vision transformers, which can adaptively assign a suitable number of queries to each spatial region. Thus achieves fine-grained representation in discriminative regions while keeping high efficiency. Besides, the dynamic grained encoder is compatible with most vision transformer frameworks. Without bells and whistles, our encoder allows the state-of-the-art vision transformers to reduce computa- tional complexity by 40%-60% while maintaining comparable performance on image classification. Extensive experiments on object detection and segmenta- tion further demonstrate the generalizability our approach. Code is available at https://ggtbbb..om///everdvvvvvv
1 Introduction
Following the evolution of network architectures natural language processing (NLP), Vision Transformers [1-5] have recently attracted increasing research attention and demonstrated promising results on several vision tasks, such as image classification, object detection, and other pivel-level tasks. Vision transformers are notable for modeling long-range dependencies and introducing less inductive bias, considered to solid alternative CNNs for vision tasks.
One of the eminent obstacles for vision transformers is the high computational cost. Vision tasks typically require high-resolution image features to obtain detail and structure representation, which is critical for pixel-level tasks [6-10]. However, since the encoders in vision transformers need to establish pairwise relationships, high-resolution features could impose unacceptable computational and memory costs. Therefore, similar to the efficient transformers [1 1-13] in NLP, many variants [2- 4] of vision transformers are proposed perform sparse self-attentions with dense queries and sparse key-value pairs based on fixed pattern or heuristic rules.
In this paper, notice that different from natural language, natural images involve much spatial redundancy, especially in flat or low-texture regions [14-18]. This could enable the image features to have a low resolution in some regions while maintaining similar representational capabilities.
To verify the spatial redundancy in vision transformers, we give an empirical analysis for DeiT [19] on ImageNet [20] classification dataset (the details refer to Sec. 3.1). It demonstrates the existence
"quual contribution. This work was done in Megvii Research. Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Dynamic Crained Encoder
Dynamic Grained Router
Pooling
Vanilla Encoder Block
Dayodling
Flatten
R Rechape 21)
Feature
Mixud-Grained
kv
Sparse Tokams
Figure 1:
The overall diagram the proposed dynamic grained encoder. x is the input sequence. and y is the output sequence. The dynamic grained router automatically split 2D feature into mixed-er grnedggrinnddd patches with a different number of tokens in patch. Each patch is then flattened as a sparse query by average pooling operator. The vanilla encoder block can be standard transformer encoder or other efficient variants. Besides, the dash lines are only used in the training phase.
of spatial redundancy in queries, and the complexity can be dramatically reduced by downsampling some highly redundant regions while maintaining comparable performance. These properties allow the queries to use mixed granularity to achieve a balance between effectiveness and efficiency, ie., more tokens in more discriminative regions while fewer tokens in less informative regions. However, the distribution of spatial redundancy varies greatly among different input images, making it difficult for static method handle complex and variable features.
We thus attempt to explore new perspective: introducing dynamic network mechanism into vision transformers reduce the spatial redundancy of image features. As shown in Fig. 1, we propose a Dynamic Grained Encoder (DGE) to replace the vanilla encoder in vision transformers. could assign suitable number of queries for each region by using dynamic grained router, e.g., the foreground regions of the cat head in Fig. are assigned more queries than the background regions. Concretely, reshaped 2D feature is first divided into regions using fixed window. For each region, the number of patches is decided by data-dependent routing process, and each patch is average pooled obtain ID token. All the tokens then concatenated into sequence as the queries. Since our method focuses on the sparsity of queries, compatible with many efficient transformer encoders [2,3, 11-13], making our approach available generic plugin most vision transformers [1-3, 19.21]. Furthermore, the output of the encoder is restored to the input resolution by an un-pooling operation and compensates for detailed information with the input feature.
To demonstrate the effectiveness, we conduct extensive experiments on three typical vision transform- ers, i.e., DeiT [19], PVT [3] and DPVT, where DPVT is new framework based the deformable attention [2]. In the image classification task, our dynamic grained encoder allows these models to reduce computational complexity by 40%-6094 while maintaining comparable performance. On the other hand, with lower computational complexity, the accuracy can be improved by up to 4.4% on ImageNet val set. In addition, the experiments object detection and segmentation show the strong robustness and generalization of our method.
Related Work
2.1 Vision Transformer
Recently, Vision Transformers. inspired by the significant success of transformer [22] achieved the NLP field, have received more attention in the vision community. VIT [i]. which converts the image into a sequence and applies the transformer encoder structure directly on it for image classification, has pioneered this direction in visual recognition. To tackle the issue of training efficiency and data efficiency, DeiT [19] introduces several training strategies to enable learning the vision transformer on ImageNet. PVT [3] further develops feature pyramid based on the transformer structure and makes applicable for the various downstream vision tasks. Swin [21] introduces local window idea to improve the efficiency of the transformer structure. Our work mainly focuses on reducing the spatial redundancy and improving the model efficiency a data-dependent manner, which is rarely explored in previous works and complementary with various vision transformer structures.

---

1000
Complexu
101
Aecurayy (16)
80
Aduumyy
0,8
Complexity Releiitytaaii Ratio
Comre Condlation ation coefficiins
01.9
Propartion (%a
60
0.6
0.6
40
0.4
0.3
0
0.1
00.00.00000444 1-..044-....---040000000
103112
Condation coefficient
Correlationcceffiiiei threshold
Layer index ofDeiT-
(a) Distribution
(b) Accuracy Complexity
(c) Layer
Figure 2: Spatial redundancy statistics of the vanilla encoders in DeiT-S [19]. The correlation
coefficient used to measure the similarity of queries local region. Higher the correlation corresponds to more spatial redundancy. (a) indicates that most queries are highly redundant in a local region. (b) reflects that reducing the queries with high redundancy has little impact on performance. (c) means that the redundancy varies greatly in some layers.
2.2 Efficient Transformer
To improve the efficiency of transformers, prior works mainly concentrate reducing the quadratic computation of self-attention. These works can he roughly summarized as three types: learnable/fixed pattern based methods, low-rank/kernel based methods and memory based methods. Some recent approaches [12,2] 23-26] try to reduce the complexity of the self-attention mechanism by using heuristic method to generate fixed or learnable patterns. Other efforts [11, 13, 27, 28] focus on utilizing the low-rank property of the attention matrix or introducing kernels to avoid computing the attention matrix explicitly. Moreover, some works [29-31] also explore the memory mechanism to improve efficiency. However, previous attempts mainly concentrate on the NLP tasks. Different from the language sequence, which has a highly abstract representation of information, natural images typically have much spatial redundancy. It makes the vision transformers require expensive costs for downstream vision tasks, especially the dense-prediction tasks, e.g., object detection, segmentation. Our work tries to utilize this intrinsic property of natural images to achieve redundancy reduction in data-dependent manner.
2.3 Dynamic Network
Dynamic networks [32] are proposed to adaptively change the network architecture and parame- ters according to input, which have been widely explored in computer vision and natural language processing tasks. Most of the dynamic networks focus on coarse- coarse-grained strategy by dropping blocks [33-36], pruning channels [8] or adjusting layer-level scales [39,40] 40]. For instance, MSDNet [34] proposes an early existing mechanism achieve efficient inference for image classifi- cation. Switch Transformer [41] uses the Mixture of Experts (MoE) model [42] to select different parameters for each input sample. DRNet [39] attempts to perform adaptive scale transformation in feature pyramid network for semantic segmentation. The closest works to ours are probably the Dynamic Convolution [43] and the Dynamic Hcad [10], which use a learnable mask to skip specific spatial locations. However, they only applicable to the CNN-based networks, and the skipping-locatte strategy could result in significant performance degradation for vision transformers (refer to Sec. 4.1.2) Different from them, method adapts the region-level granularity to the input feature for the vision transformers, which is more general and flexible.
3 Method
3.1 Empirical Analyses on Spatial Redundancy
To investigate the spatial redundancy of vision transformer on image data, we conduct a series of experiments on the ImageNet [20] val set with pre-trained DeiT-S [19] model. Our main purpose to explore the relationship among the granularity of queries, computational complexity, and classification performance. Specifically. for each encoder layer in DeiT-S, reshape its input
3

---

queries (excluding the extra embedding) as 2D feature map and split it into 2 x 2 non-overlap patches. For each patch, we calculate its average token, and measure the similarity of each token in the patch with the average token by using the Pearson Correlation Coefficient (PCC) metric.
Then have three valuable observations. (1) Queries share similar patterns in a local region. From the correlation coefficient histogram plotted in Fig. 2(a), most of the correlation coefficients are greater than 0.8, which indicates the queries typically have strong correlation in local region. (2) Large potential of reducing spatial redundancy. Furthermore, in each patch, we replace the tokens with the average token when their correlation coefficient is above a given threshold. As shown in Fig. 2(b), we illustrate the accuracy/complextt curve varying correlation thresholds. When the threshold 0.9, the complexity decreases by 27%, but the top-1 accuracy decreases by only 0.3%. This evidence demonstrates the potential of reducing the spatial redundancy on vision transformers. (3) Statie strutegy is sub-optimal. As shown in Fig. 2(c), some encoders have large variance of correlation coefficients among different images. Thus, using data-independent methods to reduce spatial redundancy sub-optimal, which may lead to considerable performance degradation. These observations motivate us to explore data-dependent manner to reduce spatial redundancy.
3.2 Dynamic Grained Encoder
3.2.1 Overall Architecture
In this paper, we propose a new encoder block for vision transformers, called Dynamic Grained Encoder (DGE). As shown in Fig. 1, the proposed encoder consists of two main modules, i.e., dynamic grained router and vanilla encoder block. Specifically, the dynamic grained router adaptively generates mixed-grained patches for 2D feature. The vanilla encoder block can be a standard encoder block [22] or other efficient variants [2. 9, 11-13,14400 44], which made up of multi head attention and a feed-forward network. If there are extra tokens in the input sequence, such as class embedding in VIT [1], we handle them separately with the vanilla encoder. For ease of presentation. the rest of this section only considers the input sequence without extra tokens.
Given an input sequence x E R(HXW)XC for the dynamic grained encoder, (H, W) denotes the resolution of the feature, C' is the number of channels. To compatible with most vanilla encoders, we only generate sparse queries q E R NxC by the dynamic grained router, where N indicates the number of queries. Then the sparse queries as well dense keys k and values are transformed by a vanilla encoder. It is worth mentioning that keys and values can be sparse in the vanilla encoder to improve efficiency further. The output sequence of the vanilla encoder is restored to a 21) feature with the original resolution by using an un un-pooling operation. Furthermore, to enhance the details of the output feature and alleviate the vanishing gradient problem, we add residual connection [45] to fuse the input sequence.
3.2.2 Dynamic Grained Router
To achieve dynamic grained patches in space, we first partition the 2D feature, denoting as z, into multiple regions, which can perform in regular or irregular ways. Although the irregular ways, e.g., superpixels [46] and segmentation [47], may lead to better performance, it is very unfriendly to memory access and inducing inefficiency. Therefore, as shown in Fig. 3, we adopt a S x S non-overlap "indow? to split image features into multiple regular regions. Furthermore, we define set of candidate granularities tb ( $2...., Φx} } to represent the optional patch size in a region, where K is the number of candidate granularities. The granularity denotes the side length of patch, e.g. Φ = 8 corresponds to an 8 x 8 patch. Since each patch is pooled into one query in the encoder, larger granularity indicates fewer queries and less computation. For convenience, we set the region size with the maximum granularity, i.e., S max($) ( in the experiments.
Inference. For a region E 21, _ 11 we use a gating network to select granularity from the set of candidate granularities. Concretely, we reduce the region feature 2, into representative token by using the average pooling operation and linearly project it to the gating logits:
1
h(2,))
Σ
Bi
WWWL +b,
(1)
52
(Bottom-right padding is adopted the feature if needed.

---

Dynamic Grained Router
Dynamic Routing for
P
Gumbel Noise
z'
Pooling
MLP
SoltMax
P
Z
ArgMax
Region Split
Dynamic Routing for Each Region
Output Patches
Gulti-Grained Putch Split
Routing
Figure 3: The diagram of the dynamic grained router in a DGE. As shown in the left part, 2D feature is split into multiple regions. For each region, shown in the right part, generate multiple groups of patches with different granularities and select a specific group by the gating network. The Gumbel noise is added achieve end-to-ent training. Besides, the modules in dash lines are only used the training phase.
where W E RCcK and b E RI*X indicate the weight and bias, respectively. The gating logits is used to decide the granularity for the region by calculating the gating indices:
8, = arg max (h(z))()))s) (1,2 K).
As shown in Fig. 3, we split the region feature into multiple groups of patches' with K granularities. We then choose group of specific granularity according the gating indices. We denote the selected group as z'; E IR Nox5, xc where N; - 0o;
S is the number of patches in the group.
pi;
As shown in Fig. 1. to construct sequence queries, the spatial mean vector of each patch as the representative token by a pooling operation and concatenate all the tokens for the vanilla encoder:
VanillaEncodee((;: k, v), where q:
Σ is E N.NC Po.
(3)
Compared with the previous encoders [2, 11-13, the number of queries is reduced to 1 1/08, of the original, the efficiency of the encoder can be improved, and the acceleration more significant when selected granularity 0; is larger.
Training. To enable the end-to-end training for the gating network, motivated by [43, 48-50), replace the determined decisions in Eq. 2 with a stochastic sampling process during the training phase. Specifically, given a categorical distribution with unnormalized log probabilities, discrete gating index can be yielded with noise samples 9j drawn from standard Gumbel distribution:
0 = arg max(h(z;)) + 9k), whore 9k ~ Gumbel(0, 1).
4)
Furthermore, since the Eq. 4 a hard decision process, is not straightforward train the gating logits. To enable the pack-propagation, adopt the Gumbel-Softmax technique [51] to give continuous and differentiable approximation by replacing the argmax with a softmax operation. The soft gating score for region is then selected by the gating index:
exp((h(xx)e, + go))/T)
Pi ΣR exp((h(x:)+ + gx)/T)
[0.
(5)
where a fixed temperature = 1 used our experiments for convenience. Similar with [43,52], further use straight-through estimator for the gradients of gating logits, which are obtained through the soft gating score pi during the backward pass:
y P:
forward
y
(6)
backward
The above stochastic process only adopted in the training phase. Our method requires no random sampling and exponential functions during inference, guarantecing high efficiency in practice.
5

---

(a) gating indices of different images
(b) gating indices of different stages
Figure 4: Visualization of predicted gating indices of PVT-S+DGE on ImageNet val set. The candidate granularity
& {1, 2, 4}, which are shown in red, green and blue respectively, Higher granularity corresponds to less computational complexity. Our dynamic encoder tends to assign more queries the representative foreground regions than the background regions, thus significantly reducing the computational cost. The left and right parts of Fig.4 come from stage 1 and stage 2 of PVT, respectively. From left to right, the heatmaps of each instance Fig.4(b) correspond to stage 1, stage 2, and stage 3, respectively.
3.2.3 Budget Constraint
In the absence of a budget constraint, our encoder typically prefers to assign more queries to each region achieve high performance. To obtain better balance between effectiveness and efficiency, we define a computational budget denoted as E [0, 1]. which corresponds to the desired computational complexity ratio relative to the vanilla encoder without dynamic grained.
Given vision transformer with L dynamic grained encoders, we can calculate the used computational complexity ratio of the transformer by:
B Et E.e
where 10 = Ex 03 E.P. OB.
forward backward
The C¹ indicates the computational complexity required to compute a query in an encoder layer. The gi corresponds to the number of queries, adopting straight-throuu estimator to enable end-to-end training. This strategy ensures accurate complexity estimation when computing the training loss. Moreover, we use the Euclidean distance for the budget loss to narrow the computational complexity to predetermined bound:
Lrask + ALbuugees where Lbudget (33 - 7)2
The hyper-parameter À balances losses among different tasks, making the gradients have the same order of magnitude. Besides, for batched image inputs, averaged along the batch dimension to estimate the average load of the network.
Experiment
In this section, we apply our encoder to the state-of-the-art vision transformers and conduct exten- sive experiments on image classification, object detection, and segmentation. To demonstrate the generalization of our method, we conduct experiments on three Vision Transformer frameworks, i.e., DeiT [19], PVT [3] and DPVT. Where DPVT is a new framework we proposed, which is PVT [3] but using the deformable attention [2] as the vanilla encoder. Different from the dense self-attention process in DeiT, PVT and DPVT utilize sparse key-value pairs in position-insensitee and position-sensitive ways, respectively. These three frameworks could represent the vanilla encoder used by most vision transformers.
based on the architecture

---

83
M
81
DPVTS
Topl Accuracy (%
79
S DeTSS
Top Accuracy (%)
PVT-S DHT-S
ResNer-101
78
MSDNet
75
Ti
76
DPVT-Ti
DPVT-S DGE
PVT-Ti
DeiT-Ti
74
71
PVT
PVT-S- DGE
69
ResNet188
PVT+DGE
72
Dii--Ti
DelT S+DGE
70
10
14
2
FLOPPs()
FLOPS
(a) Model size (7 0.5)
(b) Budget
768
640
Complexity Ratio
640
mloC (%)
42.5
0.6
0.5
0.4
41.5
512
PVT
0.3
PVT-DGE
0.2
41
100
200
300
400
500
600
700
Layer index of DeiT-S+DGE
FLOPs (G)
(c) Layer (7 0.5)
(d) Resolution (y 0.5)
Figure 5: Visualization of accuracy and computational complexity of different configurations. (a), (b) and (c) evaluated on ImageNet val set. The PVT and PYT+DGE in (a) is scaled by model size, Le., "tiny". "small" "medium" and "large". (b) indicates the performance of our method with different budget constraints. (c) reflects the distribution of computational complexity different encoder layers of the DeiT-S+DGE. (d) is evaluated on ADE-20K val set with varying image resolutions.
4.1 Image Classification on ImageNet
4.1.1
Implementation Detail
All the experiments for image classification are based on ImageNet [20] classification dataset. We use 256 x 256 as the input image resolution for training and evaluation. For a fair comparison, we follow the training settings in DeiT and PVT. Specifically, the random-size cropping. random horizontal flipping [53] and mixup [54] are used for data augmentation. We use the Adam [55] optimizer with the weight decay of 0.05 and the momentum of 0.9. The learning rate is initially set to 0.001 and decreases according to the cosine schedule [56]. All the models are trained for 300 epochs with 128 images per batch. The label-smoothing regularization used in the training phase. Besides, for the dynamic grained encoders, phase, use four compute nodes with 32 Nvidia Tesla V100 GPUs. For instance, we spend about 1.2 days training the PVT-S with DGE model for 300 epochs. For the runtime evaluation, we measure the frameworks both Intel Xeon Gold 6130 CPU and Nvidia Tesla V100 GPU to demonstrate the efficiency of our dynamic networks.
set to 1.0 and set to [1, 2, 4} by default. During the training
'To achieve efficient region splitting, we choose 256 256 instead of 224 x 224 as it is divisible by more optional granularities. We re-trait train all involved vision transformers in this work for fair comparison.
7

---

Table 1: Performance of dynamic grained encoder with different configurations on ImageNet val set. The budget for DGE is set to 0.5. "Region" means using region-wise routing instead of layer-wise routing in the encoder.
Framework
Dynamic
Region
Top1 Acc
Top5 Acc
FLOPs
#Param
PVT-S
x
80.2
95.2
6.2G
28.2M
2,
79.1
94.5
3.4G
+12.1K
1
78.8
94.4
3.5G
+8.1K
PVT-S+DGE
1,2
80.0
95.0
3.5G
+8.1K
1,2,4
80.2
95.0
3,5G
+12.1K
1,2, 4,
79.9
95.0
3,4G
+16.1K
4.1.2 Ablation Study
Where Fine-Grained Queries Assigned? To reveal the undergoing properties of our dynamic grained encoder, we illustrate the predicted gating indices / on ImageNet val set, which is shown in Fig. 4. Without additional supervision other than classification, instance-award masks with rich details. It allows the encoder to assign more queries on the foreground regions with discriminative features than background regions. This ensures that the network can consume less computational cost while maintaining fine-grained representation. In addition, as presented Fig. 4(b), the predicted gating indices have similar patterns among different stages in the PVT. It demonstrates the effectiveness for a pyramid network, which is crucial for applying to the downstream tasks.
dynamic network can generate
Dynamic vs Static To demonstrate the superiority of the dynamic mechanism, we give a compar- ison the PVT framework with different model sizes in Fig. 5(a). For convenience, fix the budget constraint at 0.5. Our dynamic grained encoder can reduce the computational complexity by half while maintaining comparable performance. On the other hand, with similar computational complexity, our method can improve the static transformers by to 4.4%. The results demonstrate the effectiveness our method even on the efficient vision transformers. In addition, as shown in Fig. 5(c), we calculate the complexity ratio of each layer in DeiT-S with DGE, where the complexity of the network in the middle layers varies significantly due to the dynamic mechanism. Interestingly. the deeper layer has lower average computational complexity, which means the deeper layer tends to assign fewer queries. Thus, DeiT is turned into a dynamic feature pyramid structure, which is consistent with the observation in CNNs.
Budget Constraint and Candidate Granularity Set As illustrated in Fig. 5(b), we give com- parison of varying the budget constraints 7, which is selected from {0.25, 0.5, 0.75, 1.0} respectively. The redundancy in space allows the network achieve comparable performance with much less computational cost even on the efficient transformers, e.g., PVT and DPVT. Our encoder achieves the optimal balance between effectiveness and efficiency when the budget about half. Therefore, we set the budget constraint to 0.5 for other experiments by default. In addition, we report the performance of PVT-S with DGE with different candidate granularity set Tab. 1. When gating indices degenerate into learnable binary mask similar to dynamic convolutions [10,43], but this strategy results significant performance degradation. There no significant difference in performance between other granularity settings. The performance is highest when & 21, 4]. which becomes our default setting.
=00, 1). the
Region-wise Routing vs Layer-wise Routing The Fig. 4 clearly demonstrates that DGE can perform dynamic granularity in space to adapt different object structures. Nevertheless, most previous dynamic networks are based on layer-wise routing [32]. To demonstrate the advantages of our method, we set the region size S x S to the input feature size so that DGE can degraded from region-wiss routing to layer-wise routing. As shown in Tab. 1, regionnwiss gating achieves 1. 1% absolute gains over layer-wise gating with similar complexity, which agrees well with the empirical analysis in 1.
8

---

Table 2: Performance of dynamic grained encoder on COCO val set. All experiments conducted with schedule [57]. Time and FLOPs are measured on an 800 x 1280 image. "C" and "G" indicate the backbone latency on CPU (Xeon 6130) and GPU (Tesla V100). All the budget for DGE is 0.5.
Backbone
Size
#Param
Latency
FLOPS
Mask R-CNN(Ix)
(M)
C(ms)
G(ms)
(G)
AP,
AP.
APE
APm
AP
AP
ResNet
50
44.2
189
38.0
59.6
41.4
34.4
55.1
36.7
PVT
Small
44.3
880
33
251
40.4
62.9
43.8
37.8
60.1
40.3
PVT+DGE
Small
44.3
440
26
185
62.6
43.2
37.5
59.7
40.0
DPVT
Small
37.7
1090
50
186
44.0
65,9
48.2
40.3
62.9
43.4
DPVT+DGE
Small
37.7
720
34
147
43.8
65.7
47.7
40.0
62.6
43.2
ResNet
101
63.2
263
40.4
61.1
44.2
36.4
57.7
38.8
ResNeXt
(3x(3)x4)
62.8
354
41.9
62.5
45.9
37.5
59.4
40.2
PVT
Medium
63.9
1260
73
339
42.0
64.4
45.6
39.0
61.6
42.1
PVT+DGE
Medium
63.9
620
40
228
41.7
64.1
45.0
38.3
62.0
40.6
DPVT
Medium
49.9
1800
75
236
46.4
68.0
51.1
42.0
65,22
45.2
DPVT+DGE
Medium
49.9
1240
50
169
45.8
67.2
50.0
41.4
64.5
44.6
Table 3: Performance of different backbones for semantic segmentation ADE-20K val set. The inference time (backbone) is measured for a 512 x 2048 input image. "C" and "G" indicate the latency CPU and GPU.
Table 4: Comparisons with state-of-the-art vision transformers ADE-20K val set. FLOPs tested on 512 2048 resolution.
Backbone
#Param (M)
FLOPs
mloU
(G)
(%)
Backbone
#Param (M)
FLOPs
mloU (%)
Latency
(G)
C(ms)
G(ms)
ResNet-50 [45]
28.5
184
36.7
PVT-S [3]
226
41.8
PVTS
28.2
226
41.8
1350
Swin-Ti [21]
31.9
187
41.5
PVT+S+DGE
28.2
155
41.7
720
42
Twins-S [60]
28.3
174
43.2
PVT-M
48.0
44.0
1910
DPVT-S+DGE
21.7
121
44.4
PVT-M+DGE
48.0
202
43.9
1100
64
ResNet-101 [45]
47.5
262
38.8
DPVT-S
21.7
157
44,4
1470
55
PVT-M
48.0
316
44.0
DPVI-S+DGE
21.7
121
44.4
860
32
Swin-S [21]
53.2
280
44,9
DPVT-M
34.3
209
46.8
1990
110
Twins-B [60]
60.4
318
45.3
DPYT-M+DGE
34.3
148
46.1
1260
50
DPVT-M+DGE
34.3
148
46.1
4.2
Experiments for Downstream Tasks
4.2.1 Object Detection/lnstanc Segmentation on COCO
We apply our models for object detection and instance segmentation on the COCO dataset [58]. We resize the images that the shorter side is 768 pixels. All experiments are conducted on 8 GPUs with 2 images per GPU (effective minibatch size 16) for 90K iterations. The learning rate initialized to le-4, which is decreased by 10 at the 60K and 80K iteration. Following the settings in PVT [3], report the performance with 1x training schedule [57,59].
The results are reported in Tab. 2. performance at 40.1% APboz with a significant complexity reduction (185G vs 251G) and inference speed up by 22%. Even with larger models different vanilla encoders, method is still effective and efficient. addition, the proposed vision transformer variant, i.e., DPVT, is also competitive in terms of parameter, computational cost and performance. Moreover, DPVT-M+DGE achieves 45.8 APbor with 169G FLOPs, even efficient than the ResNet-50 backbone.
When equipped with DGE, the PVT-S achieves comparable
4.2.2 Semantic Segmentation on ADE-20K
We further evaluate our models as the backbones for Semantic-FPN [61] on ADE-20K [62] dataset. the experiments are based on MM-Segmentation toolkit [63]. In the training phase, we follow the settings in PVT [3] and set the learning rate to le-4, which gradually decreases to 0 by the poly strategy [64]. The images are cropped 512 x 512 and augmented with random scaling (from 0.5 to 2.0) and flipping. All models trained in 80k iterations with a batch size of 32.

---

We conduct several ablation studies by introducing the DGE block into PVT [3] and our proposed DPVT. As shown in Tab. 3. with our dynamic grained encoder, DPVT+DGE and PVT+DGE both achieve competitive performance with significant computation cost reduction by about 30% FL.OPs. On the other hand, PVT-M+DGE achieves 2. % mloU absolute gains over PVT-S but with less computational complexity. As illustrated in Fig. 5(d), this phenomenon also occurs for different image sizes on the same framework, e.g., our method has up to 1.2% mloU absolute gains against the baseline with similar computational complexity. In addition, as shown in Tab. 4, our DPVT models with DGE are superior to the state-of-the-art vision transformers in terms of parameters, computational complexity and performance. These results well demonstrate the generalization ability and robustness of our method.
5
Conclusion
In this paper, we analyze the spatial redundancy in vision transformers and propose a dynamic grained encoder to speed up inference. Our encoder can adaptively yield a suitable number of queries for different regions to reduce spatial redundancy while maintaining comparable performance. Besides, our encoder is compatible with many efficient transformers and can be trained in an end-to-end manner. The extensive experiments demonstrate the effectiveness and generalization of our method. In general, this paper explores a new perspective, i.e., leveraging the intrinsic properties of natural images with the dynamic network mechanism to achieve efficient vision transformers. We hope that our dynamic grained encoder can provide insights into future works and beyond.
Acknowledgments and Disclosure of Funding
This research was supported by National Key R&D Program of China (No. 2017YFA0700800) National Natural Science Foundation China (No. 61790563 and 61774125), Shanghai Science and Technology Program (No. 21010502700).
References
[1] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai Thomas Unterthiner, Mostafa Dehghami, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010. 11929, 2020.
[2] Xizhou Zhu, Weijie Su, Lewei Lu, Bin Li, Xiaogang Wang, and Jifeng Dai. Deformable detr: Deformable transformers for end-to-end object detection. arXiv preprint 10X0v22010.04159, 2020.
[3] Wenhai Wang. Enze Xie, Xiang Li. Deng-Ping Fan, Kaitao Song. Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pyramid vision transformer: versatile backbone for dense prediction without convolutions. arXiv preprint arXiv:2102. 12122, 2021.
[4] 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 on imagenet. arXiv preprint arXiv:2101.1 1986, 2021.
[5] Hila Chefer, Shir Gur, and Lior Wolf. Transformer interpretability heyond attention visualization. In IEFF/VV Conference Computer Vision and Pattern Recognition, 2021.
[6] Tsung- Yi Lin, Priya Goyal, Ross Girshick. Kaiming He. and Piotr Dollár. Focal loss for dense object detection. In IEEE International Conference on Computer Vision. 2017.
[7] Tsung- Yi Lin, Piotr Dollár, Ross Girshick, Kaiming He, Bharath Hariharan, and Serge Belongic. Feature pyramid networks for object detection. IEEE Conference on Computer Vision and Pattern Recognition, 2017.
[8] Adam W Harley, Konstantinos G Derpanis, and Iasonas Kokkinos. Segmentation aware convolutional networks using local attention masks. In IEEE International Conference on Computer Vision, 2017.
[9] Lin Song, Yanwei Li, Zhengkai Jiang, Zeming Li, Xiangyu Zhang, Hongbin Sun, Jian Sun, and Nanning Zheng. Rethinking learnable tree filter for generic feature transform. Advances in Neural Information Processing Systems, 2020.
[10] Lin Song, Yanwei Li, Zhengkai Jiang, Zeming Li. Hongbin Sun, Jian Sun, and Nanning Zheng. Fine- grained dynamic head for object detection. Advances in Neural Information Processing Systems, 2020.
10

---

[11] 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 urXiv:2009.14994 2020.
[12] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.0443 04451, 2020.
[13] Sinong Wang. Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint arXiv:2006. 047668 2020.
[14] Wenjin Wang, Sander Stuijk, and Gerard De Haan. Exploiting spatial redundancy of image sensor for motion robust rppg. IEEE transactions Biomedical Engineering, 2014.
[15] Yunpeng Chen, Haoqi Fan, Bing Xu, Zhicheng Yan, Yannis Kalantidis, Marcus Rohrbach, Shuicheng Yan, and Jiashi Feng. Drop an octave: Reducing spatial redundancy in convolutional neural networks with octave convolution. In JEEE/CVF International Conference on Computer Vision, 2019.
[16] Marco Tagliasacchi, Alan Trapanese, Stefano Tubaro, Joao Ascenso, Catarina Brites, and Fernando Pereira. Exploiting spatial redundancy in pixel domain wyner-ziv video coding. In International Conference on Image Processing. 2006.
[17] Lin Song, Shiwei Zhang, Gang Yu, and Honghin Sun. Tacnet: Transition-awen context network for spatio-temporal action detection. In IEEE Conference on Computer Vision and Pattern Recognition, 2019.
[18] Shiwei Zhang, Lin Song, Changxin Gao, and Nong Sang. Glnet: Global local network for weakly supervised action localization. IEEE Transactions on Multimedia, 2019.
[19] Hugo Touvron, Matthicu 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.
[20] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In IEEE Conference on Computer Vision and Pattern Recognition, 2009.
[21] Ze Liu, Yutong Lin, Yue Cao. Han Hu, Yixuan Wei, Zheng Zhang, Stephen Lin, and Baining Guo. Swin transformer: Hicrarchical vision transformer using shifted windows, arXiv preprint 1031::2003.14030, 2021.
[22] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, 2017.
[23] Rewon Child, Scott Gray, Alec Radford, and Ilya Sutskever. Generating long sequences with sparse transformers. arXiv preprint urXiv:1904.10509 2019.
[24] Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim Salimans. Axial attention in multidimensional transformers. arXiv preprint arXiv: /2180, 2019.
[25] Yi Tay, Dara Bahri, Liu Yang, Donald Metzler, and Da-Cheng Juan. Sparse sinkhorn attention. In International Conference on Machine Learning, 2020.
[26] Minghao Chen, Houwen Peng, Jianlong Fu, and Haibin Ling. Autoformer: Searching transformers for visual recognition. In IEEE/CVF International Conference Computer Vision, 2021.
[27] 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, 2020.
[28] Yi Tay, Dara Bahri, Donald Metzler, Da-Cheng Juan, Zhe Zhao, and Che Zheng, Synthesizer: Rethinking self-attention in transformer models. arXiv preprint arXiv:2005.0077 2020.
[29] Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content-bass sparse attention with routing transformers. Transactions of the Association for Computational Linguistics, 9:53 68, 2021.
[30] Manzil Zaheer, Guru Guruganesh, Avinava Duhey, Joshua Ainslie, Chris Alberti, Santiago Ontanon, Philip Pham. Anirudh Ravula, Qifan Wang, Li Yang. et al. Big bird: Transformers for longer sequences. arXiv preprint 2xXXx:20077.4062 2020.
[31] Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.0 05.e4.555555 150, 2020.
[32] Yizeng Han, Gao Huang, Shiji Song, Le Yang, Honghui Wang, and Yulin Wang. Dynamic neural networks:
A survey. arXiv preprint 202.:::002.04906 2021.
[33] Zuxuan Wu, Tushar Nagarajan. Abhishek Kumar, Steven Rennie, Larry Davis, Kristen Grauman, and Rogerio Feris, Blockdrop: Dynamic inference paths in residual networks. In IEEE Conference on Computer Vision and Pattern Recognition, 2018
11

---

[34] Gao Huang, Danlu Chen, Tianhong Li. Felix Wu, Laurens van der Maaten, and Kilian Q Weinberger. Multi-scale dense networks for resource efficient image classification. arXiv preprint 2017.
[35] Ravi Teja Mullapudi, William R Mark, Noam Shazeer, and Kayvon Fatahalian. Hydrancts: Specialized dynamic architectures for efficient inference. IEEE Conference on Computer Vision and Pattern Recognition, 2018.
[36] Xin Wang, Fisher Yu, Zi- Yi Dou, Trevor Darrell, and Joseph E Gonzalez. Skipnet: Learning dynamic routing in convolutional networks. In European Conference on Computer Vision, 2018.
[37] Shaohui Lin, Rongrong Yuchao Li, Yongjian Wu, Feiyue Huang, and Baochang Zhang. Accelerating convolutional networks via global & dynamic filter pruning. In IJCAI, 2018.
[38] Zhonghui You, Kun Yan, Jinmian Yc, Meng Ma, and Ping Wang. Gate dccorator: Global filter pruning method for accelerating deep convolutional neural networks. arXiv preprint arXiv: 19099081744 2019.
[39] Yanwei Li, Lin Song, Yukang Chen, Zeming Li, Xiangyu Zhang, Xingang Wang, and Jian Sun. Learning dynamic routing for semantic segmentation. In IEEE Conference on Computer Vision and Pattern Recognition, 2020.
[40] Yang. Yizeng Han, Xi Chen, Shiji Song, Jifeng Dai, and Gao Huang. Resolution adaptive networks for efficient inference. In IEEE Conference on Computer Vision and Pattern Recognition, 2020.
[41] William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprini arXiv:2101. 00.61991111111. 2021.
[42] Noam Shazeer, Azalia Mirhoseini. Krzysztof Maziarz, Andy Davis, Quoe Le, Geoffrey Hinton, and Jeff Dean. Outrageously large neural networks: The sparsely-gated mixture-of-experts layer. arXiv preprint 3xXiv:7001.05366 2017.
[43] Thomas Verelst and Tinne Tuytelaars. Dynamic convolutions:
Exploiting spatial sparsity for faster inference. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020.
[44] Lin Song, Yanwei Li, Zeming Li, Gang Yu. Hongbin Sun, Jian Sun, and Nanning Zheng. Learnable tree filter for structure- preeturriggee feature transform. In Advances in Neural Information Processing Systems, 2019.
[45] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In IEEE Conference Computer Vision and Pattern Recognition, 2016.
[46] Radhakrishna Achanta, Appu Shaji, Kevin Smith, Aurelien Lucchi, Pascal Fua, and Sabine Süsstrunk. Slic superpixels compared to statc-of-the-art superpixel methods. IEEE transactions pattern analysis and machine intelligence, 2012.
[47] David A Forsyth and Jean Ponce. Computer vision: modern approach. Pearson, 2012.
[48] Andreas Veit and Serge Belongie. Convolutional networks with adaptive inference graphs. In European Conference on Computer Vision (ECCV), 2018.
[49] Charles Hermann, Richard Strong Bowen, and Ramin Zabih. An end-to-end approach for speeding up neural network inference. arXiv e-prints, 2018.
[50] Zhenda Xie, Zheng Zhang, Xizhou Zhu, Gao Huang, and Stephen Lin. Spatially adaptive inference with stochastic feature sampling and interpolation. In European Conference on Computer Vision, 2020.
[51] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterizztion with gumbel-softmax. arXiv preprint 6 6.1.011144 144, 2016.
[52] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. 2013.
[53] Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. Going deeper with convolutions. In IEEE Conference Computer Vision and Pattern Recognition. 2015.
[54] Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimization. arXiv preprint arXiv:1710.0041] 2017.
[55] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint
10xiv:771..05100,200
[56] Ilya Loshchilov and Frank Hutter. Sgdr: Stochastic gradient descent with warm restarts, arXiv preprint arXiv: 039883 2016.
[57] Yuxin Wu, Alexander Kirillov, Francisco Massa, Wan- Yen Lo, and Ross Girshick. Detectron2, https: //gittin /tt.thtb.coo///teeeee http://www.ceeeeeoeeeeeereretota 2019.
12

---

[58] Tsung- Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick. Microsoft Common objects in context. In European Conference on Computer Vision, 2014.
[59] Jianfeng Wang. Lin Song, Zeming Li, Hongbin Sun, Jian Sun, and Nanning Zheng. End-to-end object detection with fully convolutional network. In IEEF/CVF Conference Computer Vision and Pattern Recognition, 2021.
[60] Xiangxiang Chu, Zhi Tian, Yuging Wang, Bo Zhang, Haibing Ren, Xiaolin Wei, Huaxia Xia, and Chumhua Shen. Twins: Revisiting the design of spatial attention in vision transformers. arXiv preprint arXiv:2104. 133400 2021.
[61] Alexander Kirillov, Ross Girshick, Kaiming He, and Piotr Dollár. Panoptic feature pyramid networks. In IEEE Conference on Computer Vision and Puttern Recognition, 2019.
[62] Bolei Zhou, Hang Zhao, Xavier Puig, Sanja Fidler, Adela Barriuso, and Antonio Torralba. Scene parsing through adc20k dataset. Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition CVPR), 2017.
[63] MMSegmentation Contributors. MMSegmentation: Openmmlab semantic segmentation toolbox and com/open--oee mml mmmlaa/mmmeeeeetttioonn 2020.
benchmark. sttps://gitee
[64] Hang Zhang, Kristin Dana, Jianping Shi, Zhongyue Zhang, Xiaogang Wang, Ambrish Tyagi, and Amit Agrawal. Context encoding for semantic segmentation. In IEEE Conference on Computer Vision and Puttern Recognition, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] We observed that the variance of some experimental results was very small. Due resource constraints, did not report error bars for all the experiments.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're
asing/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
13

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "tyedgCYZD80", "reviewer": "Reviewer_8cdz", "summary": "This paper introduces sparse queries for vision transformers to exploit the intrinsic spatial redundancy of natural images and save computational costs. Specifically, the authors propose a Dynamic Grained Encoder for vision transformers, which can adaptively assign a suitable number of queries to each spatial region. Concretely, a reshaped 2D feature is first divided into regions using a fixed window. For each region, the number of patches is decided by a data-dependent routing process, and each patch is average pooled to obtain a 1D token. All the tokens are then concatenated into a sequence as the queries. Finally, the output of the encoder is restored to the input resolution by an un-pooling operation and compensates for detailed information with the input feature.\n\nThe Dynamic Grained Router is discrete in nature. The authors use the Gumbel softmax trick to train it. To encourage the efficiency, the authors add a (soft) budget regularization to the loss, which can be trained with gradient-based methods.\n\nThe authors apply the Dynamic Grained Router to DEIT and PVT, and show that the proposed Dynamic Grained Router can effectively reduce the FLOPs while nearly keeping the accuracy. However, in terms of actual runtime, the overhead from Dynamic Grained Router diminishes the theoretical FLOP gains in the low-resolution region. ", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "There is clearly a discrepancy between the reported theoretical FLOPs and the actual runtime performance. The authors do not present details about how the FLOPs are computed, for a model with a dynamic behavior. The authors may want to elaborate on this. \n\nThe visualization in Figure 4 looks interesting. Which layer does this visualization come from? The authors may want to provide per-layer visualization to show the difference cross the early and last few layers. The authors may also want to do an quantitative analysis on ImageNet segmentation (like Table 2 in https://arxiv.org/pdf/2012.09838.pdf), to show how good the dense query region captures the foreground region. \n\nThe model for the Dynamic Grained Router (Equation 1) seems very simple, just a linear layer on the pooled feature.  It is surprising that this simple design, optimized with Gumbel softmax, works. Are there any tricks in the training?\n\nAs mentioned in Line 225-227, \"the deeper layer has lower average computational complexity, which means the deeper layer tends to assign fewer queries. Thus, DeiT is turned into a dynamic feature pyramid structure, which is consistent with the observation in CNNs.\" This in fact matches the practice in current pyramid transformer arch design (PVT, Vision Longformer, Swin Transformer). Although the authors mention that the Dynamic Grained Router also apply to these pyramid transformers, how much speed gain can it bring with the constraint of no accuracy drop? Based on Figure 5(c), the redundancy is mostly in later layers, whose number of tokens has already been reduced in pyramid transformers. Can the authors give Figure 5(c)-like plot for PVT? Do the authors expect that similar profile will be true for pyramid transformers with local attention mechanism (like Vision Longformer, Swin Transformer)?\n\n", "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": "4"}, "extra_text": {}}, {"review_id": "eiZIDvZHH4R", "reviewer": "Reviewer_g5J8", "summary": "The authors propose a dynamic grained encoder for vision transformer, which introduces sparse queries to exploit the spatial redundancy. The novel method reduces the computational cost by 40%-60% under comparable performance on image classification. The generalizability of the proposed method is demonstrated on object detection and semantic segmentation. Besides, the authors analyze the intrinsic spatial redundancy of natural images and the properties of the proposed method, which are very interesting.", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": " Originality: \n\nThis work is related to vision transformer and dynamic networks. The authors propose a novel dynamic routing method for vision transformer, which exploits the spatial redundancy and reduces the computational complexity significantly.\n\nQuality: \n\nThe submission is technically sound. In Sec. 3.1, the authors analyze the spatial redundancy of natural images, including spatial redundancy statistics, the correlation corresponding to spatial redundancy among different images, and the accuracy impact when reducing the number of queries. It claims the spatial redundancy could be exploited and a data-dependent manner is necessary. The proposed method is evaluated on Image Classification, Object Detection, and Semantic Segmentation.\n\nClarity: \n\nThe submission is clearly written and well-organized.\n\nSignificance: \n\nThe results are good. The experiments show that the proposed dynamic routing method reduces the computational cost for vision transformer. The generalizability is demonstrated on downstream tasks including object detection and semantic segmentation.\n\nIssues:\n\n1. In Fig. 5, the comparable methods are slightly few on Image Classification. the proposed method does not compare with other dynamic networks like dynamic convolution and MSDNet.\n\n2. The proposed region split and routing method bring extra computational cost. Please compare the actual throughput of all models in Fig. 5 (b) to demonstrate the high efficiency.\n\n3. In Sec. 4.1.1, the input resolution is 256x256, limited to the power of 2. Did you try other input resolutions like 224x224? If yes, how to handle the non-2-power resolution? Could you please provide the performance under 224x224 resolution? (The issue shall be addressed to improve the impact of this work.)\n\n4. Besides data dynamic, it is suggested to consider model dynamic. Autoformer (https://arxiv.org/abs/2107.00651) provides dynamic search of layers for vision transformer, while DVT (https://arxiv.org/pdf/2105.15075.pdf) proposes adaptive sequence length for vision transformer. Both are related to this concurrent work. Pls add them into discussion and comparison. \n", "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": "6 hours"}, "extra_text": {}}, {"review_id": "ZBwWYzX51mI", "reviewer": "Reviewer_dTZ9", "summary": "This paper investigates the spatial redundancy of natural images and proposes a novel Dynamic Grained Encoder(DGE) for vision transformer. Experiments show that simply replacing the transformer encoder block with DGE can reduce half complexity while the performance is competitive. The visualization shows how it works and the results on object detection and segmentation further verify its feasibility.\n\n", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "- Figure2 clearly illustrates the spatial redundancy. It's not surprising to find the spatial redundancy, but, interestingly, the authors try to divide the patch dynamically. And Figure4 shows it can pay more attention (more queries) for the foreground regions.\n- Extensive ablation studies demonstrate the effectiveness of DGE and the authors make convincing conclusions.\n- More results on other vision tasks show the generalizability of DGE.\n\nWeakness:\n\n- The definition of P in Figure1 and Figure3 is unclear, is it the $\\rho$ in equation(6)?\n- \"The vanilla encoder block is made up of an MHSA and an MLP\", since the length of the token is reduced in GAE, is the residual in MHSA dropped out?\n- The authors have considered irregular ways in the paper, like segmentation, and finally simply split images for friendly memory access. However, DGE seems to produce continuous regions for vision transformer. In my opinion, spatial redundancy also exists in discontinuous regions, for example, the wall behind people is similar. Some people design adaptive clustering strategies for queries, like ACT[1], which can be seemed to deal with discontinuous regions. It will be more significant to produce discontinuous dynamic regions.\n\n[1] Zheng M, Gao P, Wang X, et al. End-to-end object detection with adaptive clustering transformer[J]. arXiv preprint arXiv:2011.09315, 2020.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10 hours"}, "extra_text": {}}, {"review_id": "4_aaEqA8hv", "reviewer": "Reviewer_6xYd", "summary": "The paper proposes a dynamic approach to split an patch into different sizes to save computations for vision transformers. In particular, the authors first split an image into different regions. And for each region, the authors propose a dynamic approach to select one of three predefined patch sizes. This is achieved with a gumbel-softmax function, which enables deriving categorical decisisons in a differentiable way.  The authors experimented with DeiT , PVT  and DPVT. ", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Strengthes:\n1. Overall, the paper is well-written and easy to follow. \n2. Extensive experiments are conducted with different transformer architectures.\n3. The idea of dymamic routing is straightforward.\n\nWeaknesses:\n1. Dynamic networks are oftentimes not GPU friendly since they produce instance-specific inputs. It would be nice to discuss the runtime in addition to flops.\n2. It would be nice to provide more training details like what is the type of GPUs used and how many hours are used in sec 4.1.1. The authors answered yes to the question \"Did you include the total amount of compute and the type of resources use[ type of GPUs, internal cluster, or cloud provided]\".  But, these details could not be found in the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No. ", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a dynamic vision transformer model that reduces spatial redundancy of image features. Three reviewers recommend acceptance, highlighting that the paper is well-written, the idea is interesting, and the experiments are rigorous, demonstrating the effectiveness of the method in different tasks (image classification, object detection, and semantic segmentation). One reviewer considers that the paper does not pass the acceptance threshold, due to unclear actual runtime gains when images have low-resolution, a concern shared by other reviewers as well. In the rebuttal, the authors demonstrated that a significant advantage in throughput on GPUs can be obtained through their implementation of  an optimized CUDA kernel for batched sparse matrix multiplication. The AC finds this response convincing, and agrees with the majority that the paper passes the acceptance bar of NeurIPS. The authors are encouraged to add the discussion in the rebuttal to the final version of the paper.
Decision: Accept (Poster)