PaperlayerView exact revision on arXiv

Source-linked AI summary

QuadTree Attention for Vision Transformers

Shitao Tang, Jiahui Zhang, Siyu Zhu, Ping Tan

arXiv:2201.02767v2cs.CV

TL;DR

Vision transformers offer long-range dependency modeling, but quadratic attention limits their use in dense, high-resolution tasks. QuadTree Attention uses coarse-to-fine token pyramids and top-K region selection to reduce computation, achieving state-of-the-art results across feature matching, stereo, classification, and detection.

  • Problem

    Quadratic attention complexity makes vision transformers difficult to apply to tasks requiring high-resolution dense predictions.

  • Method

    QuadTree Attention builds token pyramids and computes attention coarse-to-fine, selecting top K regions so irrelevant finer-level regions are skipped.

  • Results

    QuadTree Attention achieves state-of-the-art performance across feature matching, stereo, image classification, and object detection, with reduced computation.

  • Takeaways & Limitations

    The method supports both cross-attention and self-attention while combining global coarse-level information with local fine-level details.

Abstract

from arXiv · show

Transformers have been successful in many vision tasks, thanks to their capability of capturing long-range dependency. However, their quadratic computational complexity poses a major obstacle for applying them to vision tasks requiring dense predictions, such as object detection, feature matching, stereo, etc. We introduce QuadTree Attention, which reduces the computational complexity from quadratic to linear. Our quadtree transformer builds token pyramids and computes attention in a coarse-to-fine manner. At each level, the top K patches with the highest attention scores are selected, such that at the next level, attention is only evaluated within the relevant regions corresponding to these top K patches. We demonstrate that quadtree attention achieves state-of-the-art performance in various vision tasks, e.g. with 4.0% improvement in feature matching on ScanNet, about 50% flops reduction in stereo matching, 0.4-1.5% improvement in top-1 accuracy on ImageNet classification, 1.2-1.8% improvement on COCO object detection, and 0.7-2.4% improvement on semantic segmentation over previous state-of-the-art transformers. The codes are available at https://github.com/Tangshitao/QuadtreeAttention.

1 INTROCUTION

QuadTree Attention addresses the quadratic cost of vision transformers by combining coarse-to-fine token selection with attention over relevant regions, preserving fine details and long-range dependencies. The method improves performance across cross-attention and self-attention vision tasks while reducing computation.

  • Motivation: Vision transformers capture long-range dependencies but have quadratic complexity in the number of image patches, limiting high-resolution dense prediction.Prior approaches reduce cost by using low-resolution or sparse tokens, approximating attention, or restricting attention to local windows.
  • Approach: QuadTree Attention builds token pyramids and computes attention from coarse to fine, selecting top K regions and skipping irrelevant regions at finer levels.The design applies to both cross-attention and self-attention.
  • Results: 4.0 higher AUC@20° than a linear transformer on ScanNet feature matching is achieved with similar flops.The reported feature-matching result is 61.6 AUC@20°.
  • Results: About 50% flops reduction is achieved in stereo matching while maintaining similar end-point-error to a standard transformer.The method also reduces memory consumption in the reported stereo comparison.

2 RELATED WORK

Related work reduces transformer cost through linear approximations, sparse or low-resolution tokens, and local attention. These strategies trade computational efficiency against attention coverage or vision-task performance.

  • Efficient Transformers: Efficient-transformer research targets the quadratic cost of full attention for long token sequences.The literature is categorized into multiple efficiency strategies, including linear approximate attention.
  • Vision Transformers: Vision Transformers apply transformers to image recognition, but full attention makes dense prediction tasks such as detection and segmentation difficult.This motivates efficient vision-transformer designs.
  • Cross-Attention Methods: Cross-attention methods improve feature matching by processing local descriptors or seeded matches, while linear attention is also used to reduce computation.These approaches target correspondence problems with different sparsity or approximation choices.

3 METHOD

QuadTree Attention reduces vision-transformer computation by organizing tokens into pyramids and evaluating attention coarse to fine. It selects promising regions at coarse levels, aggregates messages across pyramid levels, and achieves linear complexity through sparse attention.

  • Attention in Transformer: The transformer projects input embeddings into query, key, and value tokens before computing attention-based message aggregation.Self-attention uses identical inputs, whereas cross attention uses different inputs.
  • QuadTree Attention: QuadTree Attention reduces computational cost by recursively computing attention from coarse to fine and skipping irrelevant regions at finer levels.The design aims to reduce information loss while maintaining efficiency.
  • QuadTree Attention: At each pyramid level, top K key tokens are selected from coarse attention scores, and finer-level attention is evaluated only in corresponding regions.Query and key/value pyramids are constructed by downsampling feature maps; average pooling is used for query and key tokens.
  • QuadTree-A: QuadTree-A assembles each full message from partial messages computed at different pyramid levels, assigning finer evaluation to more relevant regions.Less-related regions are processed at coarse levels, while highly related regions are processed at fine levels; the selected regions collectively cover the image space.
  • QuadTree-B: QuadTree-B computes the message as a weighted average of partial messages from different levels, using overlapping regions to address score and contribution issues in QuadTree-A.The weights are learned, and the attention message uses the standard attention computation.
  • Efficiency and Position Encoding: Both QuadTree-A and QuadTree-B use sparse attention evaluation, giving quadtree attention computational complexity linear in the number of tokens.The method also incorporates multiscale positional encoding using locally enhanced positional encoding on value tokens.

4 EXPERIMENT

Across cross-attention and self-attention tasks, the quadtree transformer delivers strong accuracy while reducing computation through coarse-to-fine attention and selective region refinement.

  • Experimental scope: The evaluation covers feature matching, stereo, image classification, and object detection, spanning both cross-attention and self-attention settings.Feature matching and stereo fuse information across images; classification and detection use self-attention.
  • Feature matching: QuadTree-B improves AUC@20° by 2.6 on LoFTR-lite and 1.9 on LoFTR over the linear transformer.The comparisons are conducted on ScanNet feature matching.
  • Stereo matching: QuadTree-B achieves similar stereo EPE of 0.45 px versus 0.46 px for STTR, with 52% of the FLOPs and 63% of the memory consumption.It also achieves higher IOU for occlusion estimation than STTR.
  • Image classification: QuadTree-B outperforms PVTv2 by 0.4%-1.5% in ImageNet top-1 accuracy with fewer parameters, while QuadTree-B-b2 surpasses Swin Transformer-S by 1.0%.The reported comparison attributes the advantage to combining global coarse-level and local fine-level information.
  • Object detection: QuadTree-B-b2 exceeds ResNet101 and ResNeXt101-32x4d by 7.7 AP and 6.3 AP, respectively, with about 40% backbone FLOPs reduction.The object detection experiments use RetinaNet on COCO.
  • Attention comparison: Under matched backbone and positional-encoding settings, QuadTree attention consistently outperforms Swin and PVT, and achieves 0.9 higher AP than focal attention.The paper suggests whole-image coverage may explain the focal-attention comparison.

5 CONCLUSION

The paper introduces QuadTree Attention, a linear-complexity vision-transformer mechanism that combines coarse global selection with fine regional attention across multiple vision tasks.

  • 5 CONCLUSION: QuadTree Attention reduces vision-transformer computational complexity from quadratic to linear.The method builds token pyramids and computes attention coarse to fine.
  • 5 CONCLUSION: At each level, it selects the top K regions by attention score and skips irrelevant regions during finer-level computation.The mechanism applies to both cross-attention and self-attention.
  • 5 CONCLUSION: The quadtree transformer achieves state-of-the-art performance in feature matching, stereo, image classification, and object detection.

A.1 COMPLEXITY ANALYSIS

QuadTree attention builds token pyramids and evaluates attention coarsely before refining selected regions. With constant K, its computational complexity is linear in the number of tokens.

  • Complexity scaling: The quadtree complexity is O(KHW), where H × W is the token count and K is the number of selected patches.The coarsest-level token count is treated as constant.
  • Complexity scaling: With constant K, quadtree attention has linear complexity in the number of tokens.
  • Feature matching result: The supplied Megadepth caption reports that the proposed method performs better than other methods in feature matching.

B.1 FEATURE MATCHING

The feature-matching evaluation uses ScanNet image pairs and pose-based AUC metrics, while the network replaces the coarse-level transformer with quadtree attention. The method is also evaluated within an STTR-based stereo-style architecture and outperforms other methods on Megadepth.

  • Evaluation setup: ScanNet evaluation uses 1,500 testing pairs, resized to 640 × 480, and reports pose-error AUC at 5°, 10°, and 20° thresholds.Pose error is the maximum angular error in rotation and translation, estimated with RANSAC from predicted matches.
  • Model configuration: The ScanNet implementation replaces only the coarse-level transformer with quadtree attention.
  • Results: On Megadepth, the proposed method outperforms other methods by a large margin.
  • Model configuration: The STTR-based network combines a CNN backbone, quadtree self- and cross-attention, an optimal-transport regression head, and context refinement.It uses six self- and cross-attention layers with 128 channels and four pyramid levels.

B.4 OBJECT DETECTION AND INSTANCE SEGMENTATION

QuadTree attention improves object detection and instance segmentation performance across the reported Mask-RCNN settings. Its COCO evaluations use PVTv2 backbones with reduction attention replaced by quadtree attention.

  • Results: QuadTree attention achieves consistently better performance than other methods for Mask-RCNN object detection and instance segmentation.
  • Evaluation settings: The COCO Mask-RCNN experiments include 12-epoch training at 800 × 1333 resolution and 36-epoch training with multi-scale augmentation.
  • Evaluation settings: Table 7 evaluates object detection on COCO val2017 using a PVTv2 backbone with reduction attention replaced by quadtree attention.
  • Evaluation settings: Table 8 evaluates COCO object detection with Mask-RCNN after 36 epochs and multi-scale data augmentation using the PVTv2 backbone.
  • Comparative settings: Table 9 compares image classification and object detection under Swin-T settings.

C TRAINING LOSS

Training and validation curves show quadtree attention improving optimization and validation performance relative to several efficient attention baselines. The reported implementation also trades slower forward time for lower memory usage than PVTv2-b0.

  • Feature matching: Quadtree-B obtains consistently lower training loss and higher validation performance than spatial-reduction, linear, and other compared transformers in feature matching.
  • Image classification: In image classification, quadtree attention has consistently lower loss and higher top-1 accuracy than Swin Transformer and PVT.
  • Runtime and memory: Quadtree-b0 takes 0.046s per RetinaNet forward pass versus 0.026s for PVTv2-b0, while using 339MB instead of 574MB memory.

E ABLATIONS

The ablations show that QuadTree-B produces more accurate attention maps and stronger task performance than QuadTree-A and competing efficient attention methods. Multiscale position encoding and larger top-K values further improve results, with performance saturating quickly as K grows.

  • QuadTree-A vs QuadTree-B: QuadTree-B consistently outperforms QuadTree-A in feature matching, image classification, and detection because its score maps are more accurate and less affected by coarse-level estimation errors.The comparison is illustrated using attention score maps at different levels for the same query point.
  • Attention visualization: Spatial reduction and linear attention attend to large unrelated regions, whereas quadtree attention focuses on the most relevant area.The competing methods lose fine-grained information, while the quadtree maps are visualized across coarse and fine levels.
  • Comparisons with Swin and Focal: 0.9% higher top-1 accuracy and 2.6% higher AP are achieved over Swin Transformer, while matching Focal Transformer's classification accuracy with fewer flops and exceeding its detection AP by 0.9%.These comparisons replace the corresponding Swin attention with Quadtree-B attention.
  • Multiscale position encoding: 1.3 improvement on object detection is obtained by adding multiscale position encoding to the Quadtree-B-b2 model.The ablation is reported for the Quadtree-B-b2 configuration.
  • Top K numbers: Performance improves as K increases but saturates quickly, indicating that only a few high-scoring tokens need subdivision at the next level.This trend is evaluated for object detection and feature matching under different K values.
Loading 2201.02767v2…