# Efficient Attention via Control Variates

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 83 of its 103 references that are in the map.
- First posted on arXiv 9 Feb 2023.

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

- [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)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [SGDR: Stochastic Gradient Descent with Warm Restarts](https://mlsanity.com/paper/1608.03983/) (2016)
- [Training data-efficient image transformers & distillation through attention](https://mlsanity.com/paper/2012.12877/) (2020)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Pointer Sentinel Mixture Models](https://mlsanity.com/paper/1609.07843/) (2016)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Pyramid Vision Transformer: A Versatile Backbone for Dense Prediction without Convolutions](https://mlsanity.com/paper/2102.12122/) (2021)
- [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)
- [fairseq: A Fast, Extensible Toolkit for Sequence Modeling](https://mlsanity.com/paper/1904.01038/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [Perceiver: General Perception with Iterative Attention](https://mlsanity.com/paper/2103.03206/) (2021)
- [Designing Network Design Spaces](https://mlsanity.com/paper/2003.13678/) (2020)
- [CvT: Introducing Convolutions to Vision Transformers](https://mlsanity.com/paper/2103.15808/) (2021)
- [Image Transformer](https://mlsanity.com/paper/1802.05751/) (2018)
- [PVT v2: Improved Baselines with Pyramid Vision Transformer](https://mlsanity.com/paper/2106.13797/) (2021)
- [Compressive Transformers for Long-Range Sequence Modelling](https://mlsanity.com/paper/1911.05507/) (2019)

## Built on by (most cited first, 23 of 23)

- [Many-Shot In-Context Learning](https://mlsanity.com/paper/2404.11018/) (2024)
- [The Hedgehog & the Porcupine: Expressive Linear Attentions with Softmax Mimicry](https://mlsanity.com/paper/2402.04347/) (2024)
- [Lightning Attention-2: A Free Lunch for Handling Unlimited Sequence Lengths in Large Language Models](https://mlsanity.com/paper/2401.04658/) (2024)
- [TransNormerLLM: A Faster and Better Large Language Model with Improved TransNormer](https://mlsanity.com/paper/2307.14995/) (2023)
- [Various Lengths, Constant Speed: Efficient Language Modeling with Lightning Attention](https://mlsanity.com/paper/2405.17381/) (2024)
- [MetaLA: Unified Optimal Linear Approximation to Softmax Attention Map](https://mlsanity.com/paper/2411.10741/) (2024)
- [SARA-RT: Scaling up Robotics Transformers with Self-Adaptive Robust Attention](https://mlsanity.com/paper/2312.01990/) (2023)
- [DiJiang: Efficient Large Language Models through Compact Kernelization](https://mlsanity.com/paper/2403.19928/) (2024)
- [Linear Attention Sequence Parallelism](https://mlsanity.com/paper/2404.02882/) (2024)
- [TaylorShift: Shifting the Complexity of Self-Attention from Squared to Linear (and Back) using Taylor-Softmax](https://mlsanity.com/paper/2403.02920/) (2024)
- [Linear Attention via Orthogonal Memory](https://mlsanity.com/paper/2312.11135/) (2023)
- [FLuRKA: Fast and accurate unified Low-Rank & Kernel Attention](https://mlsanity.com/paper/2306.15799/) (2023)
- [Scaling Reasoning without Attention](https://mlsanity.com/paper/2505.22425/) (2025)
- [Proxy Compression for Language Modeling](https://mlsanity.com/paper/2602.04289/) (2026)
- [FactorLLM: Factorizing Knowledge via Mixture of Experts for Large Language Models](https://mlsanity.com/paper/2408.11855/) (2024)
- [Coneheads: Hierarchy Aware Attention](https://mlsanity.com/paper/2306.00392/) (2023)
- [Interactive Multi-Head Self-Attention with Linear Complexity](https://mlsanity.com/paper/2402.17507/) (2024)
- [FlashEVA: Accelerating LLM inference via Efficient Attention](https://mlsanity.com/paper/2511.00576/) (2025)
- [Scratchpad Patching: Decoupling Compute from Patch Size in Byte-Level Language Models](https://mlsanity.com/paper/2605.09630/) (2026)
- [Feature Shift Localization Network](https://mlsanity.com/paper/2506.09101/) (2025)
- [Shallow Neural Networks Learn Low-Degree Spherical Polynomials with Feature Learning by Learnable Channel Attention](https://mlsanity.com/paper/2512.20562/) (2025)
- [Data-Aware Random Feature Kernel for Transformers](https://mlsanity.com/paper/2603.04127/) (2026)
- [Temporal Preservation over Processing: Diagnosing and Designing Spatiotemporal Single-Stage Video Detectors](https://mlsanity.com/paper/2606.31421/) (2026)

## Abstract (arXiv)

Random-feature-based attention (RFA) is an efficient approximation of softmax attention with linear runtime and space complexity. However, the approximation gap between RFA and conventional softmax attention is not well studied. Built upon previous progress of RFA, we characterize this gap through the lens of control variates and show that RFA can be decomposed into a sum of multiple control variate estimators for each element in the sequence. This new framework reveals that exact softmax attention can be recovered from RFA by manipulating each control variate. Besides, it allows us to develop a more flexible form of control variates, resulting in a novel attention mechanism that significantly reduces the approximation gap while maintaining linear complexity. Extensive experiments demonstrate that our model outperforms state-of-the-art efficient attention mechanisms on both vision and language tasks.