# Combiner: Full Attention Transformer with Sparse Computation Cost

arXiv: https://arxiv.org/abs/2107.05768 · HTML: https://mlsanity.com/paper/2107.05768/

## Key facts

- Cited by 64 papers in the map (data through 14 Oct 2026).
- Builds on 35 of its 43 references that are in the map.
- First posted on arXiv 12 Jul 2021.

## Builds on (most cited first, 30 of 35)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [ALBERT: A Lite BERT for Self-supervised Learning of Language Representations](https://mlsanity.com/paper/1909.11942/) (2019)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Glow: Generative Flow with Invertible 1x1 Convolutions](https://mlsanity.com/paper/1807.03039/) (2018)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Pixel Recurrent Neural Networks](https://mlsanity.com/paper/1601.06759/) (2016)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)
- [CCNet: Criss-Cross Attention for Semantic Segmentation](https://mlsanity.com/paper/1811.11721/) (2018)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Enhancing the Locality and Breaking the Memory Bottleneck of Transformer on Time Series Forecasting](https://mlsanity.com/paper/1907.00235/) (2019)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [PixelCNN++: Improving the PixelCNN with Discretized Logistic Mixture Likelihood and Other Modifications](https://mlsanity.com/paper/1701.05517/) (2017)
- [Axial Attention in Multidimensional Transformers](https://mlsanity.com/paper/1912.12180/) (2019)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Music Transformer](https://mlsanity.com/paper/1809.04281/) (2018)
- [Breaking the Softmax Bottleneck: A High-Rank RNN Language Model](https://mlsanity.com/paper/1711.03953/) (2017)
- [PixelSNAIL: An Improved Autoregressive Generative Model](https://mlsanity.com/paper/1712.09763/) (2017)

## Built on by (most cited first, 30 of 64)

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Extending Context Window of Large Language Models via Positional Interpolation](https://mlsanity.com/paper/2306.15595/) (2023)
- [Memorizing Transformers](https://mlsanity.com/paper/2203.08913/) (2022)
- [Landmark Attention: Random-Access Infinite Context Length for Transformers](https://mlsanity.com/paper/2305.16300/) (2023)
- [Transformer Quality in Linear Time](https://mlsanity.com/paper/2202.10447/) (2022)
- [EfficientViT: Memory Efficient Vision Transformer with Cascaded Group Attention](https://mlsanity.com/paper/2305.07027/) (2023)
- [FLatten Transformer: Vision Transformer using Focused Linear Attention](https://mlsanity.com/paper/2308.00442/) (2023)
- [MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformers](https://mlsanity.com/paper/2305.07185/) (2023)
- [Self-attention Does Not Need O(n2) Memory](https://mlsanity.com/paper/2112.05682/) (2021)
- [Token Fusion: Bridging the Gap between Token Pruning and Token Merging](https://mlsanity.com/paper/2312.01026/) (2023)
- [SparQ Attention: Bandwidth-Efficient LLM Inference](https://mlsanity.com/paper/2312.04985/) (2023)
- [Block-Recurrent Transformers](https://mlsanity.com/paper/2203.07852/) (2022)
- [Hierarchical Transformers Are More Efficient Language Models](https://mlsanity.com/paper/2110.13711/) (2021)
- [Efficient Transformers with Dynamic Token Pooling](https://mlsanity.com/paper/2211.09761/) (2022)
- [Advancing Transformer Architecture in Long-Context Large Language Models: A Comprehensive Survey](https://mlsanity.com/paper/2311.12351/) (2023)
- [Prompt Compression for Large Language Models: A Survey](https://mlsanity.com/paper/2410.12388/) (2024)
- [Model Compression and Efficient Inference for Large Language Models: A Survey](https://mlsanity.com/paper/2402.09748/) (2024)
- [General-purpose, long-context autoregressive modeling with Perceiver AR](https://mlsanity.com/paper/2202.07765/) (2022)
- [AI-Generated Content (AIGC): A Survey](https://mlsanity.com/paper/2304.06632/) (2023)
- [State Space Model for New-Generation Network Alternative to Transformers: A Survey](https://mlsanity.com/paper/2404.09516/) (2024)
- [CAKE: Cascading and Adaptive KV Cache Eviction with Layer Preferences](https://mlsanity.com/paper/2503.12491/) (2025)
- [SHViT: Single-Head Vision Transformer with Memory Efficient Macro Design](https://mlsanity.com/paper/2401.16456/) (2024)
- [Your Transformer May Not be as Powerful as You Expect](https://mlsanity.com/paper/2205.13401/) (2022)
- [Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers](https://mlsanity.com/paper/2406.16747/) (2024)
- [Fractal Generative Models](https://mlsanity.com/paper/2502.17437/) (2025)
- [Q-ViT: Fully Differentiable Quantization for Vision Transformer](https://mlsanity.com/paper/2201.07703/) (2022)
- [Accelerating Transformers with Spectrum-Preserving Token Merging](https://mlsanity.com/paper/2405.16148/) (2024)
- [The What, Why, and How of Context Length Extension Techniques in Large Language Models -- A Detailed Survey](https://mlsanity.com/paper/2401.07872/) (2024)
- [Linear Complexity Randomized Self-attention Mechanism](https://mlsanity.com/paper/2204.04667/) (2022)
- [V2PE: Improving Multimodal Long-Context Capability of Vision-Language Models with Variable Visual Position Encoding](https://mlsanity.com/paper/2412.09616/) (2024)

## Abstract (arXiv)

Transformers provide a class of expressive architectures that are extremely effective for sequence modeling. However, the key limitation of transformers is their quadratic memory and time complexity O(L2) with respect to the sequence length in attention layers, which restricts application in extremely long sequences. Most existing approaches leverage sparsity or low-rank assumptions in the attention matrix to reduce cost, but sacrifice expressiveness. Instead, we propose Combiner, which provides full attention capability in each attention head while maintaining low computation and memory complexity. The key idea is to treat the self-attention mechanism as a conditional expectation over embeddings at each location, and approximate the conditional distribution with a structured factorization. Each location can attend to all other locations, either via direct attention, or through indirect attention to abstractions, which are again conditional expectations of embeddings from corresponding local regions. We show that most sparse attention patterns used in existing sparse transformers are able to inspire the design of such factorization for full attention, resulting in the same sub-quadratic cost (O(Llog(L)) or O(L√L)). Combiner is a drop-in replacement for attention layers in existing transformers and can be easily implemented in common frameworks. An experimental evaluation on both autoregressive and bidirectional sequence tasks demonstrates the effectiveness of this approach, yielding state-of-the-art results on several image and text modeling tasks.