Source-linked AI summary
Efficient Attention: Attention with Linear Complexities
Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, Hongsheng Li
TL;DR
Dot-product attention provides global dependency modeling but its quadratic resource demands restrict use on large inputs. The paper proposes efficient attention, which preserves the representational power of dot-product attention with substantially lower complexity, and reports improved performance across evaluated tasks. Its efficiency enables attention in higher-resolution and resource-constrained settings.
Problem
Dot-product attention’s quadratic memory and computational complexity makes global dependency modeling prohibitively expensive on large inputs.
Method
The paper introduces efficient attention, a resource-efficient mechanism with linear complexity that preserves dot-product attention’s representational power.
Results
Efficient attention produced significant improvements across four evaluated tasks, with state-of-the-art results reported for object detection and stereo depth estimation.
Takeaways & Limitations
Efficient attention enables broader integration of attention modules, including in higher-resolution network parts and resource-constrained tasks.
Takeaways & Limitations
With softmax normalization, efficient attention only closely approximates the original softmax operation rather than matching it exactly.
Abstract
from arXiv · showhide
Dot-product attention has wide applications in computer vision and natural language processing. However, its memory and computational costs grow quadratically with the input size. Such growth prohibits its application on high-resolution inputs. To remedy this drawback, this paper proposes a novel efficient attention mechanism equivalent to dot-product attention but with substantially less memory and computational costs. Its resource efficiency allows more widespread and flexible integration of attention modules into a network, which leads to better accuracies. Empirical evaluations demonstrated the effectiveness of its advantages. Efficient attention modules brought significant performance boosts to object detectors and instance segmenters on MS-COCO 2017. Further, the resource efficiency democratizes attention to complex models, where high costs prohibit the use of dot-product attention. As an exemplar, a model with efficient attention achieved state-of-the-art accuracies for stereo depth estimation on the Scene Flow dataset. Code is available at https://github.com/cmsflash/efficient-attention.
1. Introduction
Dot-product attention models global dependencies but its quadratic resource demands restrict application on large inputs. The paper introduces efficient attention to retain representational power while reducing complexity and enabling broader use.
- Dot-product attention expands the receptive field to the entire input, complementing convolution and recurrence for long-range dependency modeling.
- Quadratic memory and computational complexity makes dot-product attention prohibitively expensive for large inputs and generally limits it to low-resolution features.A 64-channel 128 × 128 feature map can require over 1 GB of GPU memory and over 25 GMACC.
- Efficient attention is mathematically equivalent to dot-product attention with scaling normalization and approximately equivalent with softmax normalization.Experiments reported that the approximate equivalence did not impact accuracies.
- Efficient attention has linear memory and computational complexities with respect to input size while retaining the same representational power as dot-product attention.
- Its efficiency permits more attention modules and integration into higher-resolution network parts, producing performance boosts in object detection and instance segmentation on MS-COCO 2017.
- Efficient attention also facilitates attention for resource-hungry tasks such as stereo depth estimation on the Scene Flow dataset.
2. Related works
Related work distinguishes dot-product attention from scaling attention and contrasts efficient attention with other efficient non-local methods. The paper positions efficient attention as an equivalent, structurally compatible alternative rather than an approximation.
- Dot-product attention originated in machine translation, became central to Transformers, and was adapted to computer vision through the non-local module.
- 2.2. Scaling attention: Scaling attention emphasizes important features and suppresses uninformative ones, serving a different goal from dot-product attention’s global dependency modeling.
- 2.2. Scaling attention: Efficient attention is mathematically equivalent to dot-product attention with scaling normalization and approximately equivalent with softmax normalization.
- 2.3. Efficient non-local operations: Unlike low-rank affinity methods such as LatentGNN, efficient attention is not an approximation and has a one-to-one mapping between structural components and the non-local module.
- 2.3. Efficient non-local operations: The paper reports that efficient attention outperforms each compared efficient non-local method in empirical comparisons.
3. Method
Efficient attention reorganizes attention computation to avoid pairwise position similarities while preserving dot-product attention under scaling normalization and closely approximating it under softmax normalization. This removes quadratic resource terms and enables attention on larger or higher-resolution inputs.
- Dot-product attention: Dot-product attention computes all pairwise position similarities, requiring O(n^2) memory and O(d_kn^2) computation.Each position aggregates values from all positions using similarity-weighted summation.
- Efficient attention: Efficient attention forms global context vectors by treating the keys as d_k attention maps and aggregating values through weighted summation.Queries then provide position-specific coefficients over these global context vectors.
- Efficient attention: The mechanism is implemented by flattening an input feature map, applying efficient attention, reshaping the output, optionally restoring channel dimensionality, and adding a residual connection.A 1x1 convolution restores dimensionality when d_v differs from d.
- Equivalence: Efficient attention is mathematically equivalent to dot-product attention with scaling normalization and approximately equivalent under softmax normalization.The scaling-normalization equivalence follows from associativity and commutativity of matrix multiplication; the softmax operations are not exactly equivalent but closely approximate the original effect.
- Efficiency advantage: Efficient attention has O(dn + d^2) memory and O(d^2n) computational complexity when d_v = d_k = d.Avoiding pairwise similarities eliminates the O(n^2) memory and computation terms, producing substantial savings as input size grows.
- Efficiency advantage: For a 64 × 64 feature map, efficient attention saves 17 times the memory and 33 times the computation relative to a non-local module.At 256 × 256, the non-local module requires 17.2 GB of memory and 413 GMACC, while the resource gap widens with input size.
4. Experiments on the MS-COCO task suite
MS-COCO experiments compare efficient attention with non-local attention across resource usage, normalization, key dimensionality, and detection and segmentation performance. Efficient attention preserves comparable effects while enabling substantially lower resource use and broader integration.
- Comparison with non-local attention: Efficient attention achieves substantially better performance-cost trade-offs than non-local attention on MS-COCO object detection and instance segmentation.At matched insertion locations, the methods have nearly identical performance effects, while efficient attention uses orders of magnitude fewer resources; under the same 12 GB VRAM cap, it achieves significantly better performance.
- Comparison with competing methods: EA models achieve the highest performance and performance improvement across the reported MS-COCO settings while using the least resources.The comparison includes competing methods for object detection and instance segmentation, with EA baselines described as significantly stronger.
- Normalization: The effectiveness of efficient attention does not depend on whether scaling or softmax normalization is used.Following the normalization comparison, the remaining experiments use softmax normalization.
- Key dimensionality: Reducing key dimensionality from 128 to 32 causes minimal accuracy change in efficient-attention models.The result supports using smaller key and query dimensionalities to save additional resources.
5. Experiments on other tasks
Experiments extend efficient attention beyond the MS-COCO suite to stereo depth estimation and temporal action localization. The method improves task performance while making attention feasible where non-local attention can be prohibitively expensive.
- Stereo depth estimation: Efficient attention improves stereo depth estimation on Scene Flow and achieves a new state-of-the-art result with EA-PSMNet.A non-local module at the same location would require 9.68 TB of memory, prohibiting effectiveness verification, while EA-PSMNet substantially outperforms competing methods.
- Evaluation setup: The MS-COCO comparison tables report box AP, mask AP, memory, and computation for attention-module placements across ResNet and feature-pyramid levels.Memory and computation count only the attention modules, while res{x} and fpn{x} identify insertion locations.
- Temporal action localization: Efficient attention substantially improves temporal action localization performance on THUMOS14 when added to the ResNet-50 R-C3D baseline.Two efficient attention modules are inserted after res3 and res4 in the backbone.
6. Visualization
The visualization analyzes efficient-attention maps and relates their semantic diversity to a template-map interpretation. Different map sets tend to focus on foreground, object cores, or object peripheries.
- Semantic focus: The three map sets show distinct semantic focuses: foreground, core object parts, and object peripheries.Column 2 tends toward foreground regions, column 3 toward object cores, and column 4 toward peripheral regions.
- Template-map interpretation: The semantic distinctiveness of the map sets supports representing attention maps as linear combinations of semantically focused template maps.This interpretation connects the visualization to the paper’s template-map analysis.
- Global attention maps: Global attention maps from FPN level 1 are visualized for four MS-COCO images, with three corresponding map sets shown per example.The left-most column contains the input images, and the remaining columns contain global attention maps.
7. Conclusion
The paper presents efficient attention as a substantially more resource-efficient alternative to dot-product attention. Across four evaluated tasks, it improves performance, including state-of-the-art results for object detection and stereo depth estimation.
- Conclusion: Efficient attention is quadratically more memory- and computationally-efficient than dot-product attention.The paper presents this reduction as enabling attention use with large inputs or tight resource constraints.
- Conclusion: Experiments verify efficient attention’s effectiveness across four distinct tasks and report significant improvement for each task.The paper identifies object detection, instance segmentation, and stereo depth estimation among the evaluated tasks, and reports state-of-the-art results for object detection and stereo depth estimation.
A. Architecture details for experiments on MS-COCO 2017
The experiments on MS-COCO 2017 use a documented architecture configuration.
- Table 9 details the architecture used in the MS-COCO 2017 experiments.
- The architecture details concern experiments conducted on MS-COCO 2017.
- The architecture is presented as part of the experimental setup.
B. Fine-grain metrics for experiments on MS-COCO 2017
This section presents fine-grain object detection and instance segmentation metrics on MS-COCO 2017, alongside architecture details and table conventions for non-local and efficient-attention modules.
- Fine-grain metrics: Table 10 presents fine-grain object detection metrics on MS-COCO 2017.
- Fine-grain metrics: Table 11 presents fine-grain instance segmentation metrics on MS-COCO 2017.
- Architecture details: The MS-COCO 2017 architecture details assume a ResNet-50 backbone, with changes for ResNet-101 and ResNeXt-101.
- Table conventions: In Tables 10 and 11, +n NL denotes adding n non-local blocks, while +n EA denotes adding n efficient-attention modules to the backbone and FPN.
- Table conventions: OOM indicates out-of-memory errors in the object detection and instance segmentation metric tables.