Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention

Abstract

Transformers achieve remarkable performance in several tasks but due to their quadratic complexity, with respect to the input's length, they are prohibitively slow for very long sequences. To address this limitation, we express the self-attention as a linear dot-product of kernel feature maps and make use of the associativity property of matrix products to reduce the complexity from $\mathcal{O}\left(N^2\right)$ to $\mathcal{O}\left(N\right)$, where $N$ is the sequence length. We show that this formulation permits an iterative implementation that dramatically accelerates autoregressive transformers and reveals their relationship to recurrent neural networks. Our linear transformers achieve similar performance to vanilla transformers and they are up to 4000x faster on autoregressive prediction of very long sequences.

arXiv commentICML 2020, project at https://linear-transformers.com/

Cited by in corpus (91)

• A Survey on Visual Transformer
• CoAtNet: Marrying Convolution and Attention for All Data Sizes
• Efficiently Modeling Long Sequences with Structured State Spaces
• ABCNet: Attentive Bilateral Contextual Network for Efficient Semantic Segmentation of Fine-Resolution Remote Sensing Images
• Multi-stage Attention ResU-Net for Semantic Segmentation of Fine-Resolution Remote Sensing Images
• RoFormer: Enhanced Transformer with Rotary Position Embedding
• XCiT: Cross-Covariance Image Transformers
• A Practical Survey on Faster and Lighter Transformers
• Perceiver: General Perception with Iterative Attention
• Random Feature Attention
• Rethinking Attention with Performers
• CSWin Transformer: A General Vision Transformer Backbone with Cross-Shaped Windows
• Sparse DETR: Efficient End-to-End Object Detection with Learnable Sparsity
• Video Background Music Generation with Controllable Music Transformer
• Chasing Sparsity in Vision Transformers: An End-to-End Exploration
• Fastformer: Additive Attention Can Be All You Need
• LoFTR: Detector-Free Local Feature Matching with Transformers
• Deep Generative Modelling: A Comparative Review of VAEs, GANs, Normalizing Flows, Energy-Based and Autoregressive Models
• Graph Neural Networks for Natural Language Processing: A Survey
• SOFT: Softmax-free Transformer with Linear Complexity
• Choose a Transformer: Fourier or Galerkin
• Long-Short Transformer: Efficient Transformers for Language and Vision
• Is Attention Better Than Matrix Decomposition?
• Luna: Linear Unified Nested Attention
• ATISS: Autoregressive Transformers for Indoor Scene Synthesis
• Self-Attention Between Datapoints: Going Beyond Individual Input-Output Pairs in Deep Learning
• An Attention Free Transformer
• Container: Context Aggregation Network
• The Jazz Transformer on the Front Line: Exploring the Shortcomings of AI-composed Music through Quantitative Measures
• LieTransformer: Equivariant self-attention for Lie Groups
• Deep Encoder, Shallow Decoder: Reevaluating Non-autoregressive Machine Translation
• Automated Identification of Cell Populations in Flow Cytometry Data with Transformers
• CCVS: Context-aware Controllable Video Synthesis
• Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention
• Combiner: Full Attention Transformer with Sparse Computation Cost
• Adaptive Fourier Neural Operators: Efficient Token Mixers for Transformers
• A Survey of Deep Learning Approaches for OCR and Document Understanding
• Structure-Enhanced Pop Music Generation via Harmony-Aware Learning
• Multi-View Stereo with Transformer
• Compound Word Transformer: Learning to Compose Full-Song Music over Dynamic Directed Hypergraphs
• Centroid Transformers: Learning to Abstract with Attention
• STAR: Sparse Transformer-based Action Recognition
• Transformers: "The End of History" for NLP?
• Coordination Among Neural Modules Through a Shared Global Workspace
• A Domain-Knowledge-Inspired Music Embedding Space and a Novel Attention Mechanism for Symbolic Music Modeling
• Relative Positional Encoding for Transformers with Linear Complexity
• Going Beyond Linear Transformers with Recurrent Fast Weight Programmers
• Fast Convergence of DETR with Spatially Modulated Co-Attention
• Softmax-free Linear Transformers
• 3D Object Detection with Pointformer
• Scatterbrain: Unifying Sparse and Low-rank Attention Approximation
• Asymptotic theory of in-context learning by linear attention
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding
• Gated Recurrent Context: Softmax-free Attention for Online Encoder-Decoder Speech Recognition
• The Piano Inpainting Application
• Attention Approximates Sparse Distributed Memory
• Unleashing Transformers: Parallel Token Prediction with Discrete Absorbing Diffusion for Fast High-Resolution Image Generation from Vector-Quantized Codes
• Rethinking Lifelong Sequential Recommendation with Incremental Multi-Interest Attention
• Patch-Based Stochastic Attention for Image Editing
• FMMformer: Efficient and Flexible Transformer via Decomposed Near-field and Far-field Attention
• A Unified Pruning Framework for Vision Transformers
• Not All Memories are Created Equal: Learning to Forget by Expiring
• Urban Sound Classification : striving towards a fair comparison
• TensorCoder: Dimension-Wise Attention via Tensor Representation for Natural Language Modeling
• PoNet: Pooling Network for Efficient Token Mixing in Long Sequences
• PnP-DETR: Towards Efficient Visual Analysis with Transformers
• Redesigning the Transformer Architecture with Insights from Multi-particle Dynamical Systems
• Sub-word Level Lip Reading With Visual Attention
• Transformed CNNs: recasting pre-trained convolutional layers with self-attention
• Smart Bird: Learnable Sparse Attention for Efficient and Effective Transformer
• On Learning the Transformer Kernel
• Sparse Attention with Linear Units
• Sparse Factorization of Large Square Matrices
• Deep Learning: Our Miraculous Year 1990-1991
• Do Long-Range Language Models Actually Use Long-Range Context?
• $\infty$-former: Infinite Memory Transformer
• When Attention Meets Fast Recurrence: Training Language Models with Reduced Compute
• Beyond Nyströmformer -- Approximation of self-attention by Spectral Shifting
• Token Pooling in Vision Transformers
• Skyformer: Remodel Self-Attention with Gaussian Kernel and Nyström Method
• PermuteFormer: Efficient Relative Position Encoding for Long Sequences
• Ripple Attention for Visual Perception with Sub-quadratic Complexity
• CoRe: An Efficient Coarse-refined Training Framework for BERT
• T-EMDE: Sketching-based global similarity for cross-modal retrieval
• How Can Self-Attention Networks Recognize Dyck-n Languages?
• Weight Squeezing: Reparameterization for Knowledge Transfer and Model Compression
• Knowledge Transfer by Discriminative Pre-training for Academic Performance Prediction
• Learning Hard Retrieval Decoder Attention for Transformers
• Towards Incremental Transformers: An Empirical Analysis of Transformer Models for Incremental NLU
• Poly-NL: Linear Complexity Non-local Layers with Polynomials
• Decision Machines: Congruent Decision Trees