# Linear Complexity Randomized Self-attention Mechanism

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 68 of its 100 references that are in the map.
- First posted on arXiv 10 Apr 2022.

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

- [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)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [End-to-End Object Detection with Transformers](https://mlsanity.com/paper/2005.12872/) (2020)
- [mixup: Beyond Empirical Risk Minimization](https://mlsanity.com/paper/1710.09412/) (2017)
- [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)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [CutMix: Regularization Strategy to Train Strong Classifiers with Localizable Features](https://mlsanity.com/paper/1905.04899/) (2019)
- [RandAugment: Practical automated data augmentation with a reduced search space](https://mlsanity.com/paper/1909.13719/) (2019)
- [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)
- [The Kinetics Human Action Video Dataset](https://mlsanity.com/paper/1705.06950/) (2017)
- [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)
- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Random Erasing Data Augmentation](https://mlsanity.com/paper/1708.04896/) (2017)
- [Perceiver: General Perception with Iterative Attention](https://mlsanity.com/paper/2103.03206/) (2021)
- [The "something something" video database for learning and evaluating visual common sense](https://mlsanity.com/paper/1706.04261/) (2017)
- [Deep Networks with Stochastic Depth](https://mlsanity.com/paper/1603.09382/) (2016)
- [Designing Network Design Spaces](https://mlsanity.com/paper/2003.13678/) (2020)
- [CvT: Introducing Convolutions to Vision Transformers](https://mlsanity.com/paper/2103.15808/) (2021)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)

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

- [Adapting Language Models to Compress Contexts](https://mlsanity.com/paper/2305.14788/) (2023)
- [In-context Autoencoder for Context Compression in a Large Language Model](https://mlsanity.com/paper/2307.06945/) (2023)
- [The Devil in Linear Transformer](https://mlsanity.com/paper/2210.10340/) (2022)
- [Lightning Attention-2: A Free Lunch for Handling Unlimited Sequence Lengths in Large Language Models](https://mlsanity.com/paper/2401.04658/) (2024)
- [In-Context Learning with Many Demonstration Examples](https://mlsanity.com/paper/2302.04931/) (2023)
- [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)
- [Training Tensor Attention Efficiently: From Cubic to Almost Linear Time](https://mlsanity.com/paper/2405.16411/) (2024)
- [Faster Causal Attention Over Large Sequences Through Sparse Flash Attention](https://mlsanity.com/paper/2306.01160/) (2023)
- [Efficient Attention via Control Variates](https://mlsanity.com/paper/2302.04542/) (2023)
- [UncertaintyRAG: Span-Level Uncertainty Enhanced Long-Context Modeling for Retrieval-Augmented Generation](https://mlsanity.com/paper/2410.02719/) (2024)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [CAB: Comprehensive Attention Benchmarking on Long Sequence Modeling](https://mlsanity.com/paper/2210.07661/) (2022)
- [Linear Attention Sequence Parallelism](https://mlsanity.com/paper/2404.02882/) (2024)
- [IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUs](https://mlsanity.com/paper/2405.02842/) (2024)
- [SelfCP: Compressing Over-Limit Prompt via the Frozen Large Language Model Itself](https://mlsanity.com/paper/2405.17052/) (2024)
- [Linear Video Transformer with Feature Fixation](https://mlsanity.com/paper/2210.08164/) (2022)
- [Squid: Long Context as a New Modality for Energy-Efficient On-Device Language Models](https://mlsanity.com/paper/2408.15518/) (2024)
- [Theoretical Understanding of In-Context Learning in Shallow Transformers with Unstructured Data](https://mlsanity.com/paper/2402.00743/) (2024)
- [Attention and Self-Attention in Random Forests](https://mlsanity.com/paper/2207.04293/) (2022)
- [DBA: Efficient Transformer with Dynamic Bilinear Low-Rank Attention](https://mlsanity.com/paper/2211.16368/) (2022)
- [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)
- [FactorLLM: Factorizing Knowledge via Mixture of Experts for Large Language Models](https://mlsanity.com/paper/2408.11855/) (2024)
- [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)
- [Finite-Time Analysis of Gradient Descent for Shallow Transformers](https://mlsanity.com/paper/2601.16514/) (2026)
- [Analytical Correction for Subsampling Bias in Drifting Models](https://mlsanity.com/paper/2604.27239/) (2026)
- [Scratchpad Patching: Decoupling Compute from Patch Size in Byte-Level Language Models](https://mlsanity.com/paper/2605.09630/) (2026)
- [Attentive Multi-Layer Perceptron for Non-autoregressive Generation](https://mlsanity.com/paper/2310.09512/) (2023)

## Abstract (arXiv)

Recently, random feature attentions (RFAs) are proposed to approximate the softmax attention in linear time and space complexity by linearizing the exponential kernel. In this paper, we first propose a novel perspective to understand the bias in such approximation by recasting RFAs as self-normalized importance samplers. This perspective further sheds light on an unbiased estimator for the whole softmax attention, called randomized attention (RA). RA constructs positive random features via query-specific distributions and enjoys greatly improved approximation fidelity, albeit exhibiting quadratic complexity. By combining the expressiveness in RA and the efficiency in RFA, we develop a novel linear complexity self-attention mechanism called linear randomized attention (LARA). Extensive experiments across various domains demonstrate that RA and LARA significantly improve the performance of RFAs by a substantial margin.