Efficient Attention: Attention with Linear Complexities

By Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, Hongsheng Li. 2018

772 citations recorded by the source corpus.

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.

Subfields: Computer Vision and Pattern Recognition, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Model Architectures

Citations in the corpus

RoFormer: Enhanced Transformer with Rotary Position Embedding (2021, background): “The self-attention can be rewritten in a more general form.”
Self-attention Does Not Need $O(n^2)$ Memory (2021, methodology): “…and architectures with more favorable complexity classes (Kitaev et al., 2020; Roy et al., 2021; Zaheer et al., 2020; Choromanski et al., 2020; Wang et al., 2020; Ren et al., 2021; Child et al., 2019; Tay et al., 2021; Wang et al., 2020; Ma et al., 2021; Shen et al., 2021; Qiu et al., 2020).”
Axial-DeepLab: Stand-Alone Axial-Attention for Panoptic Segmentation (2020, methodology): “Efficient attention methods are proposed to reduce its complexity [71,38].”
Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention (2020, background): “Concurrently with this work, Shen et al. (2020) explored the use of linearized attention for the task of object detection in images.”
MaX-DeepLab: End-to-End Panoptic Segmentation with Mask Transformers (2020, background): “Both classes of methods have boosted various vision tasks such as image classification [18, 5, 72, 37, 57, 89, 28], object detection [91, 80, 72, 36, 10, 108], semantic segmentation [15, 106, 39, 29, 109, 107], video recognition [91, 18], image generation [73, 35], and panoptic segmentation [89].”
CoAtNet: Marrying Convolution and Attention for All Data Sizes (2021, methodology): “A common approach is to augment the ConvNet backbone with explicit self-attention or non-local modules [9, 10, 11, 12], or to replace certain convolution layers with standard self-attention [11] or a more flexible mix of linear attention and convolution [41].”
Nyströmformer: A Nystöm-based Algorithm for Approximating Self-Attention (2021, methodology): “We pro-pose to simply use Segment-means similar to the local average pooling previously used in the NLP literature (Shen et al. 2018a).”
Meta-learning via Language Model In-context Tuning (2021, background): “, 2021), more few-shot examples (which requires a longer context size (Dai et al., 2019; Child et al., 2019; Shen et al., 2021; Wang et al., 2020)), and larger models (Brown et al.”
XCiT: Cross-Covariance Image Transformers (2021, methodology): “Other methods provide an approximation of the self-attention matrix which can be achieved by a projection across the token dimension [71], or through a factorization of the softmax-attention kernel [15, 37, 56, 78], which avoids explicit computation of the attention matrix.”
CMX: Cross-Modal Fusion for RGB-X Semantic Segmentation With Transformers (2022, methodology): “In contrast, [76] uses a global context vector G = KV with a size RChead×Chead and the attention result is calculated by QG.”
MotionDiffuse: Text-Driven Human Motion Generation With Diffusion Model (2022, methodology): “Hence, we adopt Efficient Attention (Shen et al., 2021) to speed up the self-attention module.”
Multistage Attention ResU-Net for Semantic Segmentation of Fine-Resolution Remote Sensing Images (2020, background): “[14] modified the position of softmax functions, resulting in the complexity reduction at OO(NN).”
FastFormers: Highly Efficient Transformer Models for Natural Language Understanding (2020, neutral): “…some other methods such as early exiting (Xin et al., 2020; Liu et al., 2020; Schwartz et al., 2020; Zhou et al., 2020) and linear time complexity self-attention models (Shen et al., 2018; Wang et al., 2020) could be added to the proposed recipes and possibly improve the efﬁciency further.”
Visual Attention Methods in Deep Learning: An In-Depth Survey (2022, methodology): “In the decoders, convolutional networks are (a) Efficient Attention [156] (b) Slot Attention [119] (c) RFA [140] (d) X-Linear [135] (e) Axial [171] (f) Transformer [165] Figure 5: The architectures of self-attention methods: Transformers [165], Axial attention [171], X-Linear [135], Slot [119] and…”
EfficientViT: Lightweight Multi-Scale Attention for High-Resolution Dense Prediction (2023, background): “Stage 3 C3 x 64 x 128 on v Stage 4 C4 x 32 x ce A While ReLU-based attention [28] and other linear attention modules [3, 12, 43, 48] has been explored in other domains, it has never been successfully applied to high-resolution dense prediction.”
Attention mechanism in neural networks: where it comes and where it goes (2022, background): “A novel linearized attention mechanism performs well on object detection, instance segmentation, and stereo depth estimation [190].”
MARE: Self-Supervised Multi-Attention REsu-Net for Semantic Segmentation in Remote Sensing (2021, background): “To alleviate the huge computational costs, ref [24] reduced the complexity from O(N2) to O(N √ N); ref [25] to O(N log N); and [18,26,27] to O(N).”
k-means Mask Transformer (2022, background): “Both approaches have boosted various vision tasks, such as image classiﬁcation [19,7,81,44,64,94,32,70,107,103], image generation [78,42], object detection [97,84,81,43,10,116], video recognition [97,19,3,33], semantic segmentation [17,110,46,35,117,115,111,100,11], and panoptic segmentation [94].”
Linear Transformers Are Secretly Fast Weight Programmers (2021, background): “Recent work proposed “linear Transformers” with constant size memory and time complexity linear in sequence length (Katharopoulos et al., 2020; Choromanski et al., 2021; Peng et al., 2021; Shen et al., 2018).”