Generating Long Sequences with Sparse Transformers

Abstract

Transformers are powerful sequence models, but require time and memory that grows quadratically with the sequence length. In this paper we introduce sparse factorizations of the attention matrix which reduce this to $O(n\sqrt{n})$. We also introduce a) a variation on architecture and initialization to train deeper networks, b) the recomputation of attention matrices to save memory, and c) fast attention kernels for training. We call networks with these changes Sparse Transformers, and show they can model sequences tens of thousands of timesteps long using hundreds of layers. We use the same architecture to model images, audio, and text from raw bytes, setting a new state of the art for density modeling of Enwik8, CIFAR-10, and ImageNet-64. We generate unconditional samples that demonstrate global coherence and great diversity, and show it is possible in principle to use self-attention to model sequences of length one million or more.

References in corpus (12)

• WaveNet: A Generative Model for Raw Audio
• Convolutional Sequence to Sequence Learning
• Mixed Precision Training
• Exploring the Limits of Language Modeling
• End-To-End Memory Networks
• Training Deep Nets with Sublinear Memory Cost
• Identity Mappings in Deep Residual Networks
• The challenge of realistic music generation: modelling raw audio at scale
• Generating Wikipedia by Summarizing Long Sequences
• PixelSNAIL: An Improved Autoregressive Generative Model
• Parallel Multiscale Autoregressive Density Estimation
• Monotonic Chunkwise Attention

Cited by in corpus (274)

• An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale
• Denoising Diffusion Probabilistic Models
• TransUNet: Transformers Make Strong Encoders for Medical Image Segmentation
• Transformers in Vision: A Survey
• Language Models are Few-Shot Learners
• On the Opportunities and Risks of Foundation Models
• Longformer: The Long-Document Transformer
• Deformable DETR: Deformable Transformers for End-to-End Object Detection
• Scaling Laws for Neural Language Models
• Is Space-Time Attention All You Need for Video Understanding?
• Evaluating Large Language Models Trained on Code
• MLP-Mixer: An all-MLP Architecture for Vision
• Zero-Shot Text-to-Image Generation
• Enhancing the Locality and Breaking the Memory Bottleneck of Transformer on Time Series Forecasting
• ALBERT: A Lite BERT for Self-supervised Learning of Language Representations
• Linformer: Self-Attention with Linear Complexity
• CTRL: A Conditional Transformer Language Model for Controllable Generation
• OCNet: Object Context Network for Scene Parsing
• Efficiently Modeling Long Sequences with Structured State Spaces
• Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting
• DeBERTa: Decoding-enhanced BERT with Disentangled Attention
• Improved Denoising Diffusion Probabilistic Models
• Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity
• Axial Attention in Multidimensional Transformers
• Reformer: The Efficient Transformer
• Multi-stage Attention ResU-Net for Semantic Segmentation of Fine-Resolution Remote Sensing Images
• Variational Diffusion Models
• Big Bird: Transformers for Longer Sequences
• TransGAN: Two Pure Transformers Can Make One Strong GAN, and That Can Scale Up
• XCiT: Cross-Covariance Image Transformers
• Synthesizer: Rethinking Self-Attention in Transformer Models
• Long Range Arena: A Benchmark for Efficient Transformers
• Sparse Networks from Scratch: Faster Training without Losing Performance
• The NLP Cookbook: Modern Recipes for Transformer based Deep Learning Architectures
• A Simple Language Model for Task-Oriented Dialogue
• Scaling Laws for Autoregressive Generative Modeling
• HiPPO: Recurrent Memory with Optimal Polynomial Projections
• Theoretical Limitations of Self-Attention in Neural Sequence Models
• VideoGPT: Video Generation using VQ-VAE and Transformers
• Adversarial Video Generation on Complex Datasets
• A Practical Survey on Faster and Lighter Transformers
• Perceiver: General Perception with Iterative Attention
• Shuffle Transformer: Rethinking Spatial Shuffle for Vision Transformer
• SAINT: Improved Neural Networks for Tabular Data via Row Attention and Contrastive Pre-Training
• Random Feature Attention
• Rethinking Attention with Performers
• MelNet: A Generative Model for Audio in the Frequency Domain
• Pretrained Transformers for Text Ranking: BERT and Beyond
• Jukebox: A Generative Model for Music
• CSWin Transformer: A General Vision Transformer Backbone with Cross-Shaped Windows
• LeViT: a Vision Transformer in ConvNet's Clothing for Faster Inference
• Beyond 512 Tokens: Siamese Multi-depth Transformer-based Hierarchical Encoder for Long-Form Document Matching
• Sparse DETR: Efficient End-to-End Object Detection with Learnable Sparsity
• Structured Denoising Diffusion Models in Discrete State-Spaces
• Fastformer: Additive Attention Can Be All You Need
• Long-Range Transformers for Dynamic Spatiotemporal Forecasting
• Sparse Sinkhorn Attention
• Deep Spatial Transformation for Pose-Guided Person Image Generation and Animation
• Explicit Sparse Transformer: Concentrated Attention Through Explicit Selection
• ProtTrans: Towards Cracking the Language of Life's Code Through Self-Supervised Deep Learning and High Performance Computing
• Deep Generative Modelling: A Comparative Review of VAEs, GANs, Normalizing Flows, Energy-Based and Autoregressive Models
• PolyGen: An Autoregressive Generative Model of 3D Meshes
• BASE Layers: Simplifying Training of Large, Sparse Models
• Single Headed Attention RNN: Stop Thinking With Your Head
• Long-Short Transformer: Efficient Transformers for Language and Vision
• Multiscale Vision Transformers
• BP-Transformer: Modelling Long-Range Context via Binary Partitioning
• Dance Revolution: Long-Term Dance Generation with Music via Curriculum Learning
• Interlaced Sparse Self-Attention for Semantic Segmentation
• Pop Music Transformer: Beat-based Modeling and Generation of Expressive Pop Piano Compositions
• Luna: Linear Unified Nested Attention
• Keeping Your Eye on the Ball: Trajectory Attention in Video Transformers
• Learning to Efficiently Sample from Diffusion Probabilistic Models
• Compressive Transformers for Long-Range Sequence Modelling
• LambdaNetworks: Modeling Long-Range Interactions Without Attention
• ATISS: Autoregressive Transformers for Indoor Scene Synthesis
• Augmenting Self-attention with Persistent Memory
• DeLighT: Deep and Light-weight Transformer
• Maximum Likelihood Training of Score-Based Diffusion Models
• Very Deep VAEs Generalize Autoregressive Models and Can Outperform Them on Images
• Self-Attention Between Datapoints: Going Beyond Individual Input-Output Pairs in Deep Learning
• MUSE: Parallel Multi-Scale Attention for Sequence to Sequence Learning
• An Attention Free Transformer
• Pyramid Medical Transformer for Medical Image Segmentation
• Checkmate: Breaking the Memory Wall with Optimal Tensor Rematerialization
• A Dataset for Answering Time-Sensitive Questions
• Audio Transformers
• ProGen: Language Modeling for Protein Generation
• VIMPAC: Video Pre-Training via Masked Token Prediction and Contrastive Learning
• MaX-DeepLab: End-to-End Panoptic Segmentation with Mask Transformers
• Addressing Some Limitations of Transformers with Feedback Memory
• Learnable Fourier Features for Multi-Dimensional Spatial Positional Encoding
• Unsupervised Brain Anomaly Detection and Segmentation with Transformers
• Exascale Deep Learning for Scientific Inverse Problems
• DeepSVG: A Hierarchical Generative Network for Vector Graphics Animation
• Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention
• Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers
• ETC: Encoding Long and Structured Inputs in Transformers
• Combiner: Full Attention Transformer with Sparse Computation Cost
• Learning Vision-Guided Quadrupedal Locomotion End-to-End with Cross-Modal Transformers
• Adaptive Fourier Neural Operators: Efficient Token Mixers for Transformers
• A Survey of Deep Learning Approaches for OCR and Document Understanding
• Data Movement Is All You Need: A Case Study on Optimizing Transformers
• Mind the Gap: Assessing Temporal Generalization in Neural Language Models
• Neural Language Generation: Formulation, Methods, and Evaluation
• The Chess Transformer: Mastering Play using Generative Language Models
• Improving Generalization of Transformer for Speech Recognition with Parallel Schedule Sampling and Relative Positional Embedding
• Codified audio language modeling learns useful representations for music information retrieval
• GMAT: Global Memory Augmentation for Transformers
• Pile-Up Mitigation using Attention
• Compound Word Transformer: Learning to Compose Full-Song Music over Dynamic Directed Hypergraphs
• RealFormer: Transformer Likes Residual Attention
• Zero-shot Entity Linking with Efficient Long Range Sequence Modeling
• One Epoch Is All You Need
• Adaptively Sparse Transformers
• M6-10T: A Sharing-Delinking Paradigm for Efficient Multi-Trillion Parameter Pretraining
• Cluster-Former: Clustering-based Sparse Transformer for Long-Range Dependency Encoding
• Conformer-Kernel with Query Term Independence for Document Retrieval
• Generative Adversarial Transformers
• Coordination Among Neural Modules Through a Shared Global Workspace
• Blockwise Self-Attention for Long Document Understanding
• Pre-Trained Models: Past, Present and Future
• The Power of Selecting Key Blocks with Local Pre-ranking for Long Document Information Retrieval
• Learning Energy-Based Models by Diffusion Recovery Likelihood
• SceneFormer: Indoor Scene Generation with Transformers
• Neural Shuffle-Exchange Networks -- Sequence Processing in O(n log n) Time
• A Tutorial on VAEs: From Bayes' Rule to Lossless Compression
• Relative Positional Encoding for Transformers with Linear Complexity
• Scaling Autoregressive Video Models
• Low-Rank Bottleneck in Multi-head Attention Models
• SAC: Accelerating and Structuring Self-Attention via Sparse Adaptive Connection
• SEAL: Segment-wise Extractive-Abstractive Long-form Text Summarization
• Self-Attentional Credit Assignment for Transfer in Reinforcement Learning
• SparseBERT: Rethinking the Importance Analysis in Self-attention
• TT-Rec: Tensor Train Compression for Deep Learning Recommendation Models
• Accelerating Sparse DNN Models without Hardware-Support via Tile-Wise Sparsity
• Score-based Generative Modeling in Latent Space
• Transformer Acceleration with Dynamic Sparse Attention
• Rethinking Architecture Design for Tackling Data Heterogeneity in Federated Learning
• Hierarchical Opacity Propagation for Image Matting
• Vision Xformers: Efficient Attention for Image Classification
• UFO-ViT: High Performance Linear Vision Transformer without Softmax
• Transformers predicting the future. Applying attention in next-frame and time series forecasting
• Augmenting Decompiler Output with Learned Variable Names and Types
• Efficient Attentions for Long Document Summarization
• AMBERT: A Pre-trained Language Model with Multi-Grained Tokenization
• Vector Quantized Contrastive Predictive Coding for Template-based Music Generation
• Efficient and Private Federated Learning with Partially Trainable Networks
• ERNIE-Doc: A Retrospective Long-Document Modeling Transformer
• $O(n)$ Connections are Expressive Enough: Universal Approximability of Sparse Transformers
• Memory Optimization for Deep Networks
• Generating Images with Sparse Representations
• Scatterbrain: Unifying Sparse and Low-rank Attention Approximation
• On the Integration of Self-Attention and Convolution
• Automated essay scoring using efficient transformer-based language models
• The Piano Inpainting Application
• Stable, Fast and Accurate: Kernelized Attention with Relative Positional Encoding
• TR-BERT: Dynamic Token Reduction for Accelerating BERT Inference
• Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
• High-Resolution Optical Flow from 1D Attention and Correlation
• On Sparsifying Encoder Outputs in Sequence-to-Sequence Models
• Multiresolution and Multimodal Speech Recognition with Transformers
• Locally Masked Convolution for Autoregressive Models
• Fast Transformers with Clustered Attention
• Predictive Sampling with Forecasting Autoregressive Models
• word2ket: Space-efficient Word Embeddings inspired by Quantum Entanglement
• Unleashing Transformers: Parallel Token Prediction with Discrete Absorbing Diffusion for Fast High-Resolution Image Generation from Vector-Quantized Codes
• Chunked Autoregressive GAN for Conditional Waveform Synthesis
• PopMAG: Pop Music Accompaniment Generation
• Which transformer architecture fits my data? A vocabulary bottleneck in self-attention
• When FastText Pays Attention: Efficient Estimation of Word Representations using Constrained Positional Weighting
• Summarize, Outline, and Elaborate: Long-Text Generation via Hierarchical Supervision from Extractive Summaries
• Deep Learning in Computer-Aided Diagnosis and Treatment of Tumors: A Survey
• FMMformer: Efficient and Flexible Transformer via Decomposed Near-field and Far-field Attention
• Which *BERT? A Survey Organizing Contextualized Encoders
• Generating Music with a Self-Correcting Non-Chronological Autoregressive Model
• Eigen Analysis of Self-Attention and its Reconstruction from Partial Computation
• Hybrid Generative-Contrastive Representation Learning
• Efficient Transformers in Reinforcement Learning using Actor-Learner Distillation
• Untangling tradeoffs between recurrence and self-attention in neural networks
• GroupFormer: Group Activity Recognition with Clustered Spatial-Temporal Transformer
• Sub-Linear Memory: How to Make Performers SLiM
• Transformers for Limit Order Books
• Improving Deep Transformer with Depth-Scaled Initialization and Merged Attention
• What Context Features Can Transformer Language Models Use?
• Not All Memories are Created Equal: Learning to Forget by Expiring
• A Unified Efficient Pyramid Transformer for Semantic Segmentation
• KVT: k-NN Attention for Boosting Vision Transformers
• PoNet: Pooling Network for Efficient Token Mixing in Long Sequences
• Transformer Language Models with LSTM-based Cross-utterance Information Representation
• Syntax-BERT: Improving Pre-trained Transformers with Syntax Trees
• Long-term series forecasting with Query Selector -- efficient model of sparse attention
• Salient Positions based Attention Network for Image Classification
• TensorCoder: Dimension-Wise Attention via Tensor Representation for Natural Language Modeling
• Adding Recurrence to Pretrained Transformers for Improved Efficiency and Context Size
• HR-NAS: Searching Efficient High-Resolution Neural Architectures with Lightweight Transformers
• baller2vec++: A Look-Ahead Multi-Entity Transformer For Modeling Coordinated Agents
• PGT: Pseudo Relevance Feedback Using a Graph-Based Transformer
• Parallel and Flexible Sampling from Autoregressive Models via Langevin Dynamics
• s-Transformer: Segment-Transformer for Robust Neural Speech Synthesis
• Adaptive Feature Selection for End-to-End Speech Translation
• Staircase Attention for Recurrent Processing of Sequences
• Hi-Transformer: Hierarchical Interactive Transformer for Efficient and Effective Long Document Modeling
• Open Question Answering over Tables and Text
• On the Out-of-distribution Generalization of Probabilistic Image Modelling
• Multi-scale Transformer Language Models
• Layered gradient accumulation and modular pipeline parallelism: fast and efficient training of large language models
• EasyTransfer -- A Simple and Scalable Deep Transfer Learning Platform for NLP Applications
• Meta-Embeddings Based On Self-Attention
• Current Limitations of Language Models: What You Need is Retrieval
• Closing the Dequantization Gap: PixelCNN as a Single-Layer Flow
• Limitations of Autoregressive Models and Their Alternatives
• Not All Attention Is Needed: Gated Attention Network for Sequence Data
• Smart Bird: Learnable Sparse Attention for Efficient and Effective Transformer
• Permutation-Invariant Variational Autoencoder for Graph-Level Representation Learning
• Multi-Scale Local-Temporal Similarity Fusion for Continuous Sign Language Recognition
• Shatter: An Efficient Transformer Encoder with Single-Headed Self-Attention and Relative Sequence Partitioning
• TransMask: A Compact and Fast Speech Separation Model Based on Transformer
• On the Distribution, Sparsity, and Inference-time Quantization of Attention Values in Transformers
• Armour: Generalizable Compact Self-Attention for Vision Transformers
• Sparse Factorization of Large Square Matrices
• Sparse Attention with Linear Units
• Long Document Ranking with Query-Directed Sparse Transformer
• N-ODE Transformer: A Depth-Adaptive Variant of the Transformer Using Neural Ordinary Differential Equations
• Neural Function Modules with Sparse Arguments: A Dynamic Approach to Integrating Information across Layers
• On Learning the Transformer Kernel
• SMYRF: Efficient Attention using Asymmetric Clustering
• Streaming Transformer ASR with Blockwise Synchronous Beam Search
• H-Transformer-1D: Fast One-Dimensional Hierarchical Attention for Sequences
• Learning Set-equivariant Functions with SWARM Mappings
• Context-Gated Convolution
• Scene Graph Modification Based on Natural Language Commands
• SCRAM: Spatially Coherent Randomized Attention Maps
• Composable Generative Models
• Do Long-Range Language Models Actually Use Long-Range Context?
• $\infty$-former: Infinite Memory Transformer
• StreaMulT: Streaming Multimodal Transformer for Heterogeneous and Arbitrary Long Sequential Data
• Token Pooling in Vision Transformers
• Autoregressive Diffusion Models
• L-Verse: Bidirectional Generation Between Image and Text
• Compositional Attention: Disentangling Search and Retrieval
• Beyond Nyströmformer -- Approximation of self-attention by Spectral Shifting
• Resampling Base Distributions of Normalizing Flows
• The DEformer: An Order-Agnostic Distribution Estimating Transformer
• BERTnesia: Investigating the capture and forgetting of knowledge in BERT
• Transformer ASR with Contextual Block Processing
• GSA-Forecaster: Forecasting Graph-Based Time-Dependent Data with Graph Sequence Attention
• Understanding and Overcoming the Challenges of Efficient Transformer Quantization
• Tensor Data Scattering and the Impossibility of Slicing Theorem
• Data-Informed Global Sparseness in Attention Mechanisms for Deep Neural Networks
• A Survey on Green Deep Learning
• Graph Conditioned Sparse-Attention for Improved Source Code Understanding
• Differential Music: Automated Music Generation Using LSTM Networks with Representation Based on Melodic and Harmonic Intervals
• The University of Sydney's Machine Translation System for WMT19
• Vector-Vector-Matrix Architecture: A Novel Hardware-Aware Framework for Low-Latency Inference in NLP Applications
• Exploring Discourse Structures for Argument Impact Classification
• Learning Hard Retrieval Decoder Attention for Transformers
• Exploiting Uncertainty of Loss Landscape for Stochastic Optimization
• Hierarchical Context-Aware Transformers for Non-Autoregressive Text to Speech
• Sparse Graph to Sequence Learning for Vision Conditioned Long Textual Sequence Generation
• ProSTformer: Pre-trained Progressive Space-Time Self-attention Model for Traffic Flow Forecasting
• Skyformer: Remodel Self-Attention with Gaussian Kernel and Nyström Method
• Input-independent Attention Weights Are Expressive Enough: A Study of Attention in Self-supervised Audio Transformers
• Incremental Neural Coreference Resolution in Constant Memory
• Ripple Attention for Visual Perception with Sub-quadratic Complexity
• Modularized Transfomer-based Ranking Framework
• DCT: Dynamic Compressive Transformer for Modeling Unbounded Sequence
• T-EMDE: Sketching-based global similarity for cross-modal retrieval
• Injecting Hierarchy with U-Net Transformers
• Poly-NL: Linear Complexity Non-local Layers with Polynomials
• Logic and the $2$-Simplicial Transformer
• HETFORMER: Heterogeneous Transformer with Sparse Attention for Long-Text Extractive Summarization
• Leveraging redundancy in attention with Reuse Transformers
• Exploring and Improving Mobile Level Vision Transformers