Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.

The 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.

The 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. 
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. 

The 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. 

The 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?

As 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)?


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.


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.
- Extensive ablation studies demonstrate the effectiveness of DGE and the authors make convincing conclusions.
- More results on other vision tasks show the generalizability of DGE.

Weakness:

- The definition of P in Figure1 and Figure3 is unclear, is it the $\rho$ in equation(6)?
- "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?
- 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.

[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.


limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
main_review:  Originality: 

This 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.

Quality: 

The 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.

Clarity: 

The submission is clearly written and well-organized.

Significance: 

The 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.

Issues:

1. 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.

2. 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.

3. 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.)

4. 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. 

limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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. 
main_review: Strengthes:
1. Overall, the paper is well-written and easy to follow. 
2. Extensive experiments are conducted with different transformer architectures.
3. The idea of dymamic routing is straightforward.

Weaknesses:
1. 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.
2. 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.
limitations_and_societal_impact: No.
review_title: null

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)