Linformer: Self-Attention with Linear Complexity

Abstract

Large transformer models have shown extraordinary success in achieving state-of-the-art results in many natural language processing applications. However, training and deploying these models can be prohibitively costly for long sequences, as the standard self-attention mechanism of the Transformer uses $O(n^2)$ time and space with respect to sequence length. In this paper, we demonstrate that the self-attention mechanism can be approximated by a low-rank matrix. We further exploit this finding to propose a new self-attention mechanism, which reduces the overall self-attention complexity from $O(n^2)$ to $O(n)$ in both time and space. The resulting linear transformer, the \textit{Linformer}, performs on par with standard Transformer models, while being much more memory- and time-efficient.

References in corpus (11)

• Distilling the Knowledge in a Neural Network
• Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer
• Language Models are Few-Shot Learners
• Longformer: The Long-Document Transformer
• Mixed Precision Training
• Training Deep Nets with Sublinear Memory Cost
• Generating Long Sequences with Sparse Transformers
• Pointer Sentinel Mixture Models
• Reformer: The Efficient Transformer
• Transformers with convolutional context for ASR
• Training with Quantization Noise for Extreme Model Compression

Cited by in corpus (171)

• Transformers in Vision: A Survey
• On the Opportunities and Risks of Foundation Models
• Deformable DETR: Deformable Transformers for End-to-End Object Detection
• A General Survey on Attention Mechanisms in Deep Learning
• Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting
• Point Transformer
• TransGAN: Two Pure Transformers Can Make One Strong GAN, and That Can Scale Up
• XCiT: Cross-Covariance Image Transformers
• Perceiver IO: A General Architecture for Structured Inputs & Outputs
• Synthesizer: Rethinking Self-Attention in Transformer Models
• Long Range Arena: A Benchmark for Efficient Transformers
• Multi-Behavior Hypergraph-Enhanced Transformer for Sequential Recommendation
• The NLP Cookbook: Modern Recipes for Transformer based Deep Learning Architectures
• A Survey on Aspect-Based Sentiment Classification
• MobileViT: Light-weight, General-purpose, and Mobile-friendly Vision Transformer
• Enable Deep Learning on Mobile Devices: Methods, Systems, and Applications
• A Practical Survey on Faster and Lighter Transformers
• Do Transformers Really Perform Bad for Graph Representation?
• CenterCLIP: Token Clustering for Efficient Text-Video Retrieval
• Perceiver: General Perception with Iterative Attention
• Recent Progress in Transformer-based Medical Image Analysis
• Random Feature Attention
• Rethinking Attention with Performers
• Revisiting Deep Learning Models for Tabular Data
• Supervised and Unsupervised Neural Approaches to Text Readability
• Local-Global Context Aware Transformer for Language-Guided Video Segmentation
• Chasing Sparsity in Vision Transformers: An End-to-End Exploration
• Charformer: Fast Character Transformers via Gradient-based Subword Tokenization
• Does the Magic of BERT Apply to Medical Code Assignment? A Quantitative Study
• Compacter: Efficient Low-Rank Hypercomplex Adapter Layers
• Fastformer: Additive Attention Can Be All You Need
• Long-Range Transformers for Dynamic Spatiotemporal Forecasting
• Attention is Not All You Need: Pure Attention Loses Rank Doubly Exponentially with Depth
• 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
• IA-RED${}^2$: Interpretability-Aware Redundancy Reduction for Vision Transformers
• SOFT: Softmax-free Transformer with Linear Complexity
• Exploring the Synergies of Hybrid CNNs and ViTs Architectures for Computer Vision: A survey
• Choose a Transformer: Fourier or Galerkin
• Long-Short Transformer: Efficient Transformers for Language and Vision
• Multiscale Vision Transformers
• Is Attention Better Than Matrix Decomposition?
• UTNet: A Hybrid Transformer Architecture for Medical Image Segmentation
• Keeping Your Eye on the Ball: Trajectory Attention in Video Transformers
• Luna: Linear Unified Nested Attention
• Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries
• An Attention Free Transformer
• Container: Context Aggregation Network
• Structured Prediction as Translation between Augmented Natural Languages
• Mokey: Enabling Narrow Fixed-Point Inference for Out-of-the-Box Floating-Point Transformer Models
• LieTransformer: Equivariant self-attention for Lie Groups
• Multimodal Fusion and Vision-Language Models: A Survey for Robot Vision
• On the design space between molecular mechanics and machine learning force fields
• HTLM: Hyper-Text Pre-Training and Prompting of Language Models
• MaX-DeepLab: End-to-End Panoptic Segmentation with Mask Transformers
• Networked Time Series Imputation via Position-aware Graph Enhanced Variational Autoencoders
• 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
• Efficient Quantized Sparse Matrix Operations on Tensor Cores
• RealFormer: Transformer Likes Residual Attention
• Centroid Transformers: Learning to Abstract with Attention
• Cluster-Former: Clustering-based Sparse Transformer for Long-Range Dependency Encoding
• Transformers: "The End of History" for NLP?
• Efficient Transformers with Dynamic Token Pooling
• Coordination Among Neural Modules Through a Shared Global Workspace
• Multitask Balanced and Recalibrated Network for Medical Code Prediction
• Conformer-Kernel with Query Term Independence for Document Retrieval
• Pre-Trained Models: Past, Present and Future
• OnDev-LCT: On-Device Lightweight Convolutional Transformers towards federated learning
• Pre-Trained Language Models for Keyphrase Prediction: A Review
• Relative Positional Encoding for Transformers with Linear Complexity
• UMat: Uncertainty-Aware Single Image High Resolution Material Capture
• SeisT: A foundational deep learning model for earthquake monitoring tasks
• Effective End-to-End Vision Language Pretraining with Semantic Visual Loss
• Affective Signals in a Social Media Recommender System
• Analogous to Evolutionary Algorithm: Designing a Unified Sequence Model
• Fast Convergence of DETR with Spatially Modulated Co-Attention
• Vision Xformers: Efficient Attention for Image Classification
• The NLP Task Effectiveness of Long-Range Transformers
• Transformer Acceleration with Dynamic Sparse Attention
• VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization
• UFO-ViT: High Performance Linear Vision Transformer without Softmax
• Long Short-Term Transformer for Online Action Detection
• MMMNA-Net for Overall Survival Time Prediction of Brain Tumor Patients
• Not All Attention Is All You Need
• The Sensory Neuron as a Transformer: Permutation-Invariant Neural Networks for Reinforcement Learning
• Sparse Attentive Memory Network for Click-through Rate Prediction with Long Sequences
• A Cost-Efficient FPGA Implementation of Tiny Transformer Model using Neural ODE
• Fourier Transformer: Fast Long Range Modeling by Removing Sequence Redundancy with FFT Operator
• Noise-Robust End-to-End Quantum Control using Deep Autoregressive Policy Networks
• 3D Object Detection with Pointformer
• OmniNet: Omnidirectional Representations from Transformers
• Scatterbrain: Unifying Sparse and Low-rank Attention Approximation
• LazyFormer: Self Attention with Lazy Update
• An Unbiased Transformer Source Code Learning with Semantic Vulnerability Graph
• Asymptotic theory of in-context learning by linear attention
• Automated essay scoring using efficient transformer-based language models
• Styleformer: Transformer based Generative Adversarial Networks with Style Vector
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding
• High-Resolution Optical Flow from 1D Attention and Correlation
• ContextSpeech: Expressive and Efficient Text-to-Speech for Paragraph Reading
• Optimizing Inference Performance of Transformers on CPUs
• On the Trade-off between Redundancy and Local Coherence in Summarization
• Not All Memories are Created Equal: Learning to Forget by Expiring
• Contrastive Learning for Local and Global Learning MRI Reconstruction
• RGB-D-Fusion: Image Conditioned Depth Diffusion of Humanoid Subjects
• FMMformer: Efficient and Flexible Transformer via Decomposed Near-field and Far-field Attention
• Towards mental time travel: a hierarchical memory for reinforcement learning agents
• What Context Features Can Transformer Language Models Use?
• A Multilingual Translator to SQL with Database Schema Pruning to Improve Self-Attention
• PnP-DETR: Towards Efficient Visual Analysis with Transformers
• Stochastic Spiking Attention: Accelerating Attention with Stochastic Computing in Spiking Networks
• DyFormer: A Scalable Dynamic Graph Transformer with Provable Benefits on Generalization Ability
• PoNet: Pooling Network for Efficient Token Mixing in Long Sequences
• Shot Contrastive Self-Supervised Learning for Scene Boundary Detection
• Redesigning the Transformer Architecture with Insights from Multi-particle Dynamical Systems
• Unifying Instance and Panoptic Segmentation with Dynamic Rank-1 Convolutions
• Group Equivariant Stand-Alone Self-Attention For Vision
• Hi-Transformer: Hierarchical Interactive Transformer for Efficient and Effective Long Document Modeling
• Transformed CNNs: recasting pre-trained convolutional layers with self-attention
• Hybrid and Collaborative Passage Reranking
• HR-NAS: Searching Efficient High-Resolution Neural Architectures with Lightweight Transformers
• Long-Range Transformer Architectures for Document Understanding
• A Singular Value Perspective on Model Robustness
• Astronomical image time series classification using CONVolutional attENTION (ConvEntion)
• Transformation Invariant Cancerous Tissue Classification Using Spatially Transformed DenseNet
• A Simple and Effective Positional Encoding for Transformers
• Video Transformer for Deepfake Detection with Incremental Learning
• EL-Attention: Memory Efficient Lossless Attention for Generation
• Armour: Generalizable Compact Self-Attention for Vision Transformers
• Smart Bird: Learnable Sparse Attention for Efficient and Effective Transformer
• Unlocking Pixels for Reinforcement Learning via Implicit Attention
• Translational Equivariance in Kernelizable Attention
• EasyTransfer -- A Simple and Scalable Deep Transfer Learning Platform for NLP Applications
• The Role of Global and Local Context in Named Entity Recognition
• Token Pooling in Vision Transformers
• Enabling Lightweight Fine-tuning for Pre-trained Language Model Compression based on Matrix Product Operators
• Transformer-F: A Transformer network with effective methods for learning universal sentence representation
• Pre-trained Language Model based Ranking in Baidu Search
• Do Long-Range Language Models Actually Use Long-Range Context?
• Updater-Extractor Architecture for Inductive World State Representations
• Linear Self-Attention Approximation via Trainable Feedforward Kernel
• Compositional Attention: Disentangling Search and Retrieval
• PairConnect: A Compute-Efficient MLP Alternative to Attention
• Focus on the Core: Efficient Attention via Pruned Token Compression for Document Classification
• Metric Transforms and Low Rank Matrices via Representation Theory of the Real Hyperrectangle
• H-Transformer-1D: Fast One-Dimensional Hierarchical Attention for Sequences
• Exceeding the Limits of Visual-Linguistic Multi-Task Learning
• Speech Summarization using Restricted Self-Attention
• T-EMDE: Sketching-based global similarity for cross-modal retrieval
• Transfer training from smaller language model
• Skyformer: Remodel Self-Attention with Gaussian Kernel and Nyström Method
• Efficient Transformer for Direct Speech Translation
• Semantic Frame Forecast
• PlueckerNet: Learn to Register 3D Line Reconstructions
• LightSeq2: Accelerated Training for Transformer-based Models on GPUs
• Yformer: U-Net Inspired Transformer Architecture for Far Horizon Time Series Forecasting
• Galaxy Morphological Classification with Efficient Vision Transformer
• On Inductive Biases for Machine Learning in Data Constrained Settings
• Doc2Dict: Information Extraction as Text Generation
• Decoupled Transformer for Scalable Inference in Open-domain Question Answering
• THG: Transformer with Hyperbolic Geometry
• Dispatcher: A Message-Passing Approach To Language Modelling
• Learning Hard Retrieval Decoder Attention for Transformers
• Poly-NL: Linear Complexity Non-local Layers with Polynomials
• Ripple Attention for Visual Perception with Sub-quadratic Complexity
• Knowledge Transfer by Discriminative Pre-training for Academic Performance Prediction
• Audiomer: A Convolutional Transformer For Keyword Spotting
• PermuteFormer: Efficient Relative Position Encoding for Long Sequences
• MATE: Multi-view Attention for Table Transformer Efficiency