Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new attention mechanism in vision transformers, which is called quadtree attention. This quadtree attention mechanism builds token pyramids and computes the attention in a coarse-to-fine manner. At each level, only top K regions with the highest attention scores from query and key are selected for further attention computation on finer tokens, while other regions simply use (current) coarse attention as a part of output. In the empirical study, the proposed quadtree attention achieves good performance on a wide range of vision tasks (e.g. feature matching, stereo matching, classification and object detection) with less computation.
main_review: Pros:
1. The multi-scale design in quadtree attention is reasonable:
The quadtree attention can model long-range interactions using coarse tokens from less relevant regions, while establishing dense interactions using fine tokens from informative local regions. Thus, the multi-scale structure (in a coarse-to-fine manner) in quadtree attention provides and efficient way to capture both long-range and local interactions. A further modified version of quadtree attention (QuadTree-B) introduces additional weights and overlapping regions, reducing the effect from inaccurate attention score on coarse tokens.

2. The quadtree attention can be used in both self-attention and cross-attention, which leads to a wider applicability.

3. Empirical performance demonstrates the effectiveness of the proposed approach: On feature matching tasks, the proposed quadtree achieves significant improvement on AUC of camera pose errors. On stereo matching and object detection, it is observed that the computation (Flops) is reduced by a large margin with on-par performance.

4. The paper is well written and easy to follow.
 
Cons / Questions / Suggestions:
1. From the technical contribution aspect, the quadtree structure is not brand new. It is arguably true that the proposed approach is one of the earliest attempts to introduce quadtree structure into the attention mechanism. However, since some recent work [1] also employs coarse-to-fine structure in attention, it would be better to have some comparison with such work.
[1] Focal Self-attention for Local-Global Interactions in Vision Transformers, NeurIPS 2021

2. The design of pyramid tokens is unclear:
  - (1) In Figure 1, Top-2 patches are used to compute finer attention. I wonder why in level 2 there are two sub-patches (green and yellow)? From the position of red patch in level, we should only have the green patch in level 2 (which could be consistent with Figure 2). In addition, why the two green patches in level 2 of image B have the same location in the 2x2 grid (both are lower left)? The same pattern is also observed in red patches in level 3.
  - (2) It remains unclear that how the pyramid tokens are generated: In Page 4-5, it mentions "we construct L-level pyramids for query and value V tokens respectively by 2x2 average pooling". Does it mean the coarse tokens are always average pooled fine tokens at one level lower? Is there any additional patch embedding layer introduced?
  - (3) In level 1, top K patches are selected, which leads to 4K sub-patches in level 2. Does it uniformly sample top K sub-patches from 4K sub-patches, or each 2x2 sub-patches from coarse patch must have one sampled sub-patch? 

3. In the empirical experiments, the quadtree attention does not bring much efficiency improvement on the ImageNet classification: It has very similar #parameters and #flops compared with its baseline (PVTv2), which is quite different from the object detection task. I wonder what is the reason behind such as big gap.

4. Typos
- Equation (1): Should be V instead of V^T
- Figure 2: It would be better to use \mathbf{m}_i^1 instead of m_i^1 for a consistent notation in the text.
- Line below Eq (4): Should s_ij^1 be s_ij^0?
summary_of_the_review: In summary, I think the proposed quadtree attention is a reasonable efficient design of attention mechanism. It builds coarse and fine tokens, which is able to model both long-range and local interactions. Empirical results also demonstrate that the proposed approach achieves good performance with less computation on many vision tasks. However, I still hold some concerns in technical contribution, unclear design of the pyramid tokens, and performance on classification task. Thus, I would like to rate this paper as "marginally above the acceptance threshold".
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The paper proposed an attention approach to handle the global or long-range attention by leveraging the idea of quadtree structure, meanwhile reducing the quadratic complexity of original attention operation to linear. Experiments are performed on several tasks, e.g. feature matching, image classification, and objection detection. Superior results are achieved on these tasks. 
main_review: ## Strengths

- The idea of the paper is clear and easy to follow up.
- The effectiveness of the proposed approach is verified on different tasks. 

## Weaknesses
- Some important related works are missing. The previous work [1] also proposed a multi-level attention approach to efficiently balance the short-distance and long-distance attention, which proposed the same way to generate the multi-level or fine and coarse tokens. From this point, the idea of quadtree-b attention is very similar to [1]. However, the authors did not mention and discuss the relation to this very related work. I suggest the authors carefully discuss the relation [1]. 

- The paper proposed an efficient way to process long-distance and short-distance attention. There should be some baselines we should compare with, 1) the vanilla attention mechanisms, 2) some other efficient attention mechanisms, e.g. shifted windows attention in Swin-transformer, focal attention in Focal Transformer[1], sampled K,V in PVT. However, the authors only compared with the PVT. I'd like to see more solid apple-to-apple comparisons and discussions on that. 

## Questions:
- How about the real runtime when applying quadtree attention to PVT architecture? 
- As I posted above, I think the quadtree attention mechanism is a general attention mechanism. I'd like to know how about the performance when applying to other transformer-based architecture, e.g. Swin-transformer, ViT, et. al. 
- The authors argue that Swin-transformer restricts the attention in the local windows. However, by shifting the windows in the Swin Transform, it enables that information exchange between windows for Swin. From this point, I don't think that Swin-transformer limits the attention whin local windows. 


[1] Focal Self-attention for Local-Global Interactions in Vision Transformers. 
summary_of_the_review: The paper proposed a clear method to handle long-distance and short-distance attention. However, important related work is missing in the discussion. As mentioned above, I think more discussions and experiments should be added to support the claim. I am leaning to reject the paper if the authors can't address my concerns.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper aims to address the quadratic computational complexity of vanilla Transformers. The key idea is to build token pyramids and computes attention in a coarse-to-fine manner, which reduces the computational complexity to linear. The resulting attention paradigm forms a quadtree structure, and two variants, QuadTree-A and QuadTree-B, are further proposed to improve message aggregation. Experiments are conducted on four different computer vision tasks involving either self-attention or cross attention. Results show that the proposed approach matches the state of the art with much fewer FLOPs and model parameters.
main_review: Pros. 

1. This paper is easy to follow and overall well-structured.

2. I think the problem this paper tries to tackle is interesting for the community. Designing an efficient attention mechanism in Transformers for vision tasks is definitely an important problem. Especially, computing attention within token pyramids following a quardtree structure is novel to me, which has not been studied in previous work.

3. The experiments are comprehensive and strong. It is good to see the comparisons on four different computer vision tasks which cover both self-attention and cross-attention. Although the improvement in accuracy seems minor to me, the reduction in computation is notable.

Cons.

Overall, I have some concerns about the experiment, and the following points might be worthy to study in the rebuttal period.

1. Spare attention usually leads to a faster convergence rate but higher final losses compared to full attention. I wonder if this still holds in QuadTree Attention. It is interesting to see the training curve of the proposed method compared with ViT or Swin.

2. I wonder if the number of tokens in the finest resolution will affect the model performance. E.g., what is the current patch size of the input image, and will it lead to performance improvement if a larger or smaller patch size is chosen?

3. It is also worthy to explore if variants of larger (smaller) size in model parameters will lead to performance improvement, and how FLOPs change in these variants.
summary_of_the_review: The paper studied a challenging and important problem in efficient attention mechanisms. I think the overall method is novel and the experimental results are promising, which leads me to a positive rating. I hope the authors can further address my concerns in the rebuttal.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes an efficient attention algorithm based on quadtree for vision transformers. It establishes a feature pyramid for tokens and aggregates sparse key-value features in each pyramid level. The method achieves competitive performance on the stereo, image classification and object detection.
main_review: Strength:
+ Introducing the quadtree to the vision transformers is interesting and makes sense. It can efficiently achieve long-range dependence while keeping the local details.
+ The paper is overall well-written and well-organized.
+ The reported performance is competitive against many state-of-the-art vision transformers.

Weakness:
- Top-k assignment for tokens in the quadtree is nondifferentiable, which may reduce the generalization. How does the proposed method achieve end-to-end training?
- The quadtree aggregates features in an unstructured and iterative way. It is unfriendly to the parallel devices and probably takes more latency than the dense attention. It would be nice to provide the actual throughput on GPUs to demonstrate the efficiency.
summary_of_the_review: The paper proposes a novel efficient vision transformer based on quadtrees, which is interesting and technical sound. It achieves competitive performance in various vision tasks.
review_title: null

Meta-review: The paper proposes an efficient attention variant inspired by quadtrees, for use in vision transformers. When applied to several vision tasks, the approach leads to better results and/or less compute. 

The reviews are all positive about the paper, after taking into account the authors' feedback (one reviewer forgot to update their official rating, apparently). They point out that the idea is reasonable and the empirical evaluation is thorough and convincing, with good gains on several tasks and datasets.

Overall, I recommend acceptance.
Decision: Accept (Poster)