PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Transformers: A Survey

Yi Tay, Mostafa Dehghani, Dara Bahri, Donald Metzler

arXiv:2009.06732v3cs.LGcs.AIcs.CLcs.CVcs.IR

TL;DR

Transformers’ quadratic self-attention costs motivate a rapidly growing body of efficiency-focused architectures. This survey organizes and reviews these models across techniques and domains, concluding that efficiency claims must be evaluated against practical constraints and trade-offs.

  • Problem

    Quadratic time and memory costs in self-attention restrict Transformer scalability for long sequences, motivating many new efficiency-focused model variants.

  • Method

    The paper surveys efficient Transformer literature, proposes a taxonomy of technical approaches, and walks through representative models across language and vision.

  • Results

    The survey provides a taxonomy, high-level abstractions, model walkthroughs, and discussion of evaluation landscapes, design trends, and orthogonal efficiency efforts.

  • Takeaways & Limitations

    Efficient Transformer models should be understood through their technical innovations and evaluated across both architectural efficiency and practical deployment considerations.

  • Takeaways & Limitations

    Some efficient attention models can be slower in practice, provide no speed or memory gains for short sequences, or incur difficult causal-masking and throughput trade-offs.

Abstract

from arXiv · show

Transformer model architectures have garnered immense interest lately due to their effectiveness across a range of domains like language, vision and reinforcement learning. In the field of natural language processing for example, Transformers have become an indispensable staple in the modern deep learning stack. Recently, a dizzying number of "X-former" models have been proposed - Reformer, Linformer, Performer, Longformer, to name a few - which improve upon the original Transformer architecture, many of which make improvements around computational and memory efficiency. With the aim of helping the avid researcher navigate this flurry, this paper characterizes a large and thoughtful selection of recent efficiency-flavored "X-former" models, providing an organized and comprehensive overview of existing work and models across multiple domains.

1. Introduction

Efficient Transformers address the quadratic time and memory costs of self-attention, which limit scalability for long sequences. This survey organizes recent efficiency-focused models across technical innovations and language and vision use cases.

  • Nearly a dozen efficiency-focused Transformer models were proposed in the six months before the manuscript’s first draft, making the literature difficult to track.
  • Self-attention connects all sequence tokens through relevance-based pooling but has quadratic time and memory complexity.
  • Transformer efficiency includes both memory footprint and computational cost, including FLOPs during training and inference.
  • Efficient self-attention is especially important for long documents, images, and videos composed of many tokens or pixels.
  • The survey reviews architectural innovations targeting quadratic attention complexity, pooling, sparsity, parameter sharing, and other general efficiency improvements.
  • It proposes a taxonomy organized by technical innovation and primary use case, reviews language and vision models, and connects their approaches.

2. Background on Transformers

Transformers stack blocks containing multi-head self-attention, feed-forward networks, normalization, and residual connections. Their attention computation scales quadratically with sequence length, while practical efficiency also depends on feed-forward costs, model usage, and hardware throughput.

  • Transformer blocks combine multi-head self-attention, position-wise feed-forward networks, layer normalization, and residual connectors.
  • Inputs are embedded into d_model-dimensional representations, combined with positional encodings, and passed through multi-headed self-attention.
  • Attention forms query, key, and value projections, computes row-wise softmax alignment scores, concatenates head outputs, and applies an output projection.
  • The self-attention output enters a two-layer feed-forward network with ReLU activations operating independently at each sequence position.
  • The QK^T multiplication requires N^2 time and memory, restricting long-sequence applications; feed-forward layers contribute approximately half of Transformer compute time or FLOPs.
  • Transformers operate as encoder-only, decoder-only, or encoder-decoder architectures, with encoder-decoder models adding cross-attention.
  • Complexity does not guarantee real-world throughput or latency: a linear-complexity model can be slower than a quadratic-complexity model in practice.

3. A Survey of Efficient Transformer Models

The survey presents a high-level overview of efficient Transformer models, beginning with a characterization of model families and a graphical overview of representative architectures.

  • The survey characterizes efficient Transformer models and uses Table 1 and Figure 2 to summarize released models and representative architectures.

3.1 A Taxonomy of Efficient Transformers

The taxonomy groups efficient Transformers by core techniques and use cases, covering attention-pattern restrictions, memory, low-rank and kernel methods, recurrence, downsampling, and sparse computation. These categories can overlap because models may combine multiple innovations.

  • Fixed Patterns (FP): Fixed patterns sparsify attention with predefined local, block, strided, or compressed access patterns.
  • Fixed Patterns (FP): Blockwise attention reduces complexity from N2 to B2 when B << N by restricting tokens to fixed local blocks.
  • Combination of Patterns (CP): Combination approaches improve coverage by combining distinct access patterns, such as local and strided attention or attention along separate tensor axes.
  • Learnable Patterns (LP): Learnable-pattern models learn token relevance and assign tokens to buckets or clusters, using mechanisms such as hashing, k-means, or learned sorting.
  • Neural Memory: Neural-memory methods use learnable side memory or global tokens to gather information from multiple or entire sequences.
  • Low-Rank Methods and Kernels: Low-rank methods project keys and values from sequence length N to a lower dimension k, while kernels rewrite attention without explicitly computing the N × N matrix.
  • Recurrence, Downsampling, and Sparse Models: Recurrence connects sequence blocks, downsampling reduces sequence resolution, and sparse models activate parameter subsets to improve the parameter-to-FLOPs ratio.
  • The taxonomy has no sharp boundaries because models may combine innovations; Routing Transformer’s clustering, for example, can also be viewed as global model memory.

3.2 Detailed Walk-through of Efficient Transformer Models

The survey walks through representative efficient Transformer models, covering local attention, memory compression, and permutation-invariant set processing. These approaches reduce attention costs through restricted neighborhoods, compressed keys and values, or inducing points.

  • The detailed walkthrough covers representative models rather than exhaustively detailing every efficient Transformer.It proceeds through local and fixed patterns, global model memory, combined patterns, memory-based sparse approaches, and learnable patterns.
  • Memory Compressed Transformer: Memory Compressed Transformer localizes attention and compresses keys and values to handle longer sequences.Local attention partitions the sequence into blocks, while memory-compressed attention applies strided convolution to keys and values while leaving queries unchanged.
  • Memory Compressed Transformer: O(b·n) is the computational and memory cost of local attention when blocks have size b.For memory-compressed attention with kernel size and stride k, the cost reduces to O(n · n/k).
  • Image Transformer: Image Transformer restricts self-attention to local neighborhoods using query blocks and associated memory blocks.Its attention matrix has shape lq × m, and its memory and computational complexity is O(n · m).
  • Image Transformer: Local attention reduces computation and memory but can lose the global receptive field and introduces a region-length trade-off.The local-attention cost remains quadratic in the region length.
  • Set Transformer: Set Transformer uses attention and inducing points for set inputs, reducing attention complexity from quadratic to linear while preserving permutation invariance.Its encoder-decoder composition is permutation invariant, with permutation-equivariant attention blocks and permutation-invariant pooling.

3.2.4 Sparse Transformer

Sparse Transformer factorizes attention into local and strided fixed patterns, while Axial Transformer applies attention along individual tensor axes. Both reduce attention resources while targeting broader coverage than purely local attention.

  • Sparse Transformer: Sparse Transformer reduces dense attention by computing only selected query-key pairs defined by local neighborhoods and fixed strides.Half of its heads use local attention and the other half use fixed strided patterns.
  • Sparse Transformer: The factorized sparse attention combines local and strided patterns across heads, producing the pattern illustrated in Figure 4.The figure distinguishes local self-attention from the strided component.
  • Sparse Transformer: O(n log n) is the Sparse Transformer attention-layer memory complexity, down from O(n^2), without changing parameter costs.The original Q, K, V transformations are retained.
  • Axial Transformer: Axial Transformer applies separate attentions along each axis of a multidimensional tensor instead of flattening the input.Each attention mixes information along one axis while keeping other axes independent.
  • Axial Transformer: Axial Transformer provides a global receptive field and straightforward efficient implementation without requiring a custom kernel.For decoding, shift operations are combined with axial attentions to satisfy causality.
  • Axial Transformer: O(n√n) is Axial Transformer’s attention complexity on a square image, saving O(√n) over standard self-attention.For a d-dimensional tensor, it saves an O(N^(d−1)/d) resource factor over standard self-attention.

3.2.6 Longformer

Longformer and related sparse models extend local attention with dilations, global tokens, or learned routing to cover longer sequences efficiently. Their complexity and applicability depend on the chosen attention structure and decoding setting.

  • Longformer: Longformer uses dilated sliding windows to improve long-range coverage while retaining sparse attention.Its receptive field expands with depth, from local patterns at lower levels to global patterns at upper levels.
  • Longformer: O(nk) is Longformer’s complexity, where k is the window size; global attention also doubles attention-layer parameter cost.Classification uses global memory tokens with access to all input sequences.
  • ETC: ETC introduces global-local attention with global-to-global, global-to-local, local-to-global, and local-to-local interactions.It prepends ng auxiliary global tokens to the original sequence.
  • ETC: O(n_g^2 + n_gN) is ETC’s stated memory complexity, with n_g global tokens and input length N.
  • BigBird: BigBird combines global tokens, random attention, and fixed local sliding windows.Its global tokens can be selected from within the input sequence through the internal transformer construction.
  • BigBird: O(n) is BigBird’s self-attention memory complexity, with no new parameters beyond the standard Transformer.
  • Routing Transformer: Routing Transformer learns content-based sparse attention by clustering projected queries and keys, restricting each token to its assigned cluster.Online k-means uses trainable centroids and balanced cluster assignments.
  • Routing Transformer: O(n^1.5) is Routing Transformer’s memory complexity, with additional centroid and projection parameters.

3.2.10 Reformer

Reformer uses locality-sensitive hashing to bucket and sort tokens, restricting attention to nearby bucketed chunks while adding reversible layers for memory savings.

  • LSH Attention: Reformer hashes queries and keys into buckets so attention is computed only when their hashes match.The hashing uses a random-projection matrix and preserves autoregressive validity with position indices.
  • Memory Efficiency with LSH Attention: Chunked and sorted bucketing processes tokens bucket by bucket, with each token attending to its own and previous chunk.This organization improves Reformer’s overall efficiency.
  • Parameter and Memory Complexity: Reformer has memory complexity O(n log n) and shares queries and keys, reducing QKV transform costs by a third.Random projections are not trainable parameters, so they add no parameter cost.
  • Parameter and Memory Complexity: Reversible layers reduce training memory by reconstructing activations instead of storing them for every layer during backpropagation.This complements the memory savings from LSH attention.

3.2.12 Linformer

Linformer reduces self-attention complexity through low-rank length projections, while Performer and Linear Transformer use kernel formulations to avoid explicitly materializing the N × N attention matrix.

  • Linformer: Linformer projects keys and values from length N to k, producing an N × k attention product and O(n) memory complexity.The extra length projections add negligible parameters when k is sufficiently small.
  • Performer: Performer uses orthogonal random features to approximate kernel attention without explicitly computing the N × N attention matrix.Its bidirectional FAVOR complexity is O(Md + Nd + MN), where M controls the number of random features.
  • Performer: During autoregressive training, Performer’s unidirectional kernel attention requires a left-to-right scan and can be several times slower than vanilla Transformer.Efficient memory complexity therefore does not necessarily imply faster practical training.
  • Linear Transformer: Linear Transformer uses kernelized self-attention and matrix associativity to reduce self-attention complexity from quadratic to linear.It also represents causal attention as a constant-memory recurrent computation.
  • Linear Transformer: Linear Transformers can improve inference speeds by up to three orders of magnitude without much loss in predictive performance.They share the drawback of limited parallelization during autoregressive teacher-forced training.
  • Linear Transformer: With feature-map cost O(c), Linear Transformer runs in O(Ncd); using elu gives c = d and end-to-end complexity O(Nd2).The recurrence uses accumulated states for causal attention.

3.2.15 Synthesizers

Synthesizers investigate whether self-attention must condition attention weights on token content, including dense, random, and factorized variants. Their factorized forms connect synthetic attention to low-rank efficient Transformers.

  • Synthesizer motivation: Synthesizers approximate attention weights instead of computing them from pairwise dot products, making them only implicitly related to efficient Transformers.The survey characterizes factorized variants as low-rank efficient Transformer models.
  • Dense Synthesizers: Dense Synthesizers project each token to an N-dimensional vector using a two-layer nonlinear feed-forward network to form the attention matrix.The construction uses X, W1, W2, and ReLU activation.
  • Random Synthesizers: Random Synthesizers generate the attention matrix from random matrices, which may be trainable or non-trainable.The matrix R has shape N×N, and the authors report competitive performance for Random Synthesizers.
  • Factorized variants: Factorized Synthesizers impose low-rank structure on dense and random attention matrices using factors such as R1 and R2 in R^N×k.The factorized Dense Synthesizer additionally uses projection, tiling, and repetition functions.
  • Complexity: Random Synthesizers avoid storing N^2 activations when R is non-trainable, while trainable variants retain N^2 memory complexity but eliminate N^2 dot products.Factorized Random Synthesizers reduce parameter costs to 2(N × k).

3.2.16 Transformer-XL

Transformer-XL improves long-sequence processing through segment-based recurrence rather than explicit sparsification of dense self-attention. Compressive Transformers extend this design with compressed memory for older activations, while sparse and mixture-of-experts models provide broader efficiency strategies.

  • Transformer-XL: Transformer-XL connects adjacent sequence blocks through recurrent memory instead of explicitly sparsifying the dense self-attention matrix.Its keys and values are conditioned on the previous sequence’s length, with gradients stopped through the memory connection.
  • Transformer-XL: Transformer-XL uses relative positional encodings in attention-weight computation rather than adding absolute positional encodings to content embeddings.The survey notes that these encodings are not directly relevant to model efficiency.
  • Compressive Transformers: Compressive Transformers preserve past segment information by moving older activations from primary memory into a compressed secondary memory.Compression functions include pooling, convolutions, dilated convolutions, and usage-based selection.
  • Compressive Transformers: Compressive Transformers use auto-encoding and attention-reconstruction losses to retain information from compressed memories over long sequences.The first reconstructs original memory, while the second reconstructs attention over model memory.
  • Sparse models: Sparse models activate subsets of parameters or activations, with mixture-of-experts routing tokens to selected experts through a top-k gating mechanism.The survey includes GShard, Switch Transformer, and GLaM among these models.

4. Discussion

The survey organizes efficient Transformer research by evaluation challenges and evolving design patterns, from fixed sparsity and memory mechanisms to learnable, low-rank, kernel, and hybrid approaches. It also emphasizes that efficiency claims depend on sequence length, hardware, masking, implementation complexity, and benchmark scope.

  • Evaluation: Comparisons are difficult because papers choose different benchmarks, model configurations, and pretraining settings, making performance gains hard to attribute.LRA partially addresses this by benchmarking 10 xformer variants on long-range encoder-only tasks, excluding causal generative modeling.
  • Design trends: Efficient Transformer designs progressed from fixed local or block patterns to factorized patterns, model memory, learnable token clustering, and global-memory sparse extensions.The survey connects early fixed-pattern work with later memory-based, Reformer, Routing Transformer, ETC, and Longformer approaches.
  • Design trends: Low-rank and kernel methods form a later design wave, but the survey reports that their superiority over learnable-pattern methods remains unclear because evaluation is still developing.Examples include Linformer, Performer, Linear Transformers, and Low-Rank Transformer.
  • Design trends: Hybrid models combine techniques, including dynamic low-rank attention with fixed patterns or memory-based methods with local attention.The survey cites Long Short Transformer, Poolingformer, and Scatter Brain as examples.
  • Design trends: Recurrent models operate orthogonally to most other approaches, while sparse models extend beyond attention and have recently shown considerable success.This distinction makes recurrent models less directly comparable with other efficient Transformer families.
  • Orthogonal efficiency efforts: Inference-time pruning can remove attention heads with minimal downstream degradation, while block pruning has made a Transformer 2.4x faster with little predictive loss on language tasks.Fast exit is another direction that stops computation when predictions are confident.
  • Efficiency caveats: Efficient Transformer variants have often lacked broad pretraining-and-finetuning validation, while implementation complexity and hardware-specific kernels limit drop-in adoption.The survey identifies these constraints alongside continued dominance of vanilla Transformers in many applications.
  • Efficiency caveats: Many efficient attention models are not necessarily faster: short sequences may yield no speed or memory gain, and causal masking or TPU packing can impose substantial throughput trade-offs.Some models cannot be packed or causally masked at all.

5. Conclusion

The survey synthesizes efficient Transformer research through a taxonomy, model walkthroughs, evaluation-landscape analysis, design trends, and discussion of orthogonal efficiency efforts. It is intended as an organized overview of techniques and models addressing Transformer efficiency.

  • Contribution: The paper surveys efficient Transformer models, especially methods addressing the quadratic complexity of self-attention.It provides a taxonomy and high-level abstraction of the core techniques used by these models.
  • Contribution: The survey characterizes models by technique, walks through several architectures, and discusses their evaluation landscape and design trends.It also covers parallel efforts that may improve Transformer efficiency more generally.
Loading 2009.06732v3…