mlsanityData to 7 Oct 2026

Linear Complexity Randomized Self-attention Mechanism

arXiv 2204.04667 ↗First posted 10 Apr 2022cs.LG cs.CL cs.CVcited by 31

Not on the map. Why?

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.

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

Builds on

68 of 100 references.

References · 68

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  4. 2020An Image is Worth 16x16 Words: Transformers for Image Recognition at Scalecited by 29,915
  5. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  6. 2021Swin Transformer: Hierarchical Vision Transformer using Shifted Windowscited by 12,082
  7. 2020End-to-End Object Detection with Transformerscited by 7,384
  8. 2017mixup: Beyond Empirical Risk Minimizationcited by 5,155
  9. 2016SGDR: Stochastic Gradient Descent with Warm Restartscited by 4,993
  10. 2020Training data-efficient image transformers & distillation through attentioncited by 4,560
  11. 2020Longformer: The Long-Document Transformercited by 3,362
  12. 2015Neural Machine Translation of Rare Words with Subword Unitscited by 2,898
38 more
  1. 2019CutMix: Regularization Strategy to Train Strong Classifiers with Localizable Featurescited by 2,875
  2. 2019RandAugment: Practical automated data augmentation with a reduced search spacecited by 2,261
  3. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 1,979
  4. 2021Pyramid Vision Transformer: A Versatile Backbone for Dense Prediction without Convolutionscited by 1,960
  5. 2017The Kinetics Human Action Video Datasetcited by 1,894
  6. 2020Big Bird: Transformers for Longer Sequencescited by 1,673
  7. 2020Reformer: The Efficient Transformercited by 1,658
  8. 2020Rethinking Attention with Performerscited by 1,584
  9. 2021Decision Transformer: Reinforcement Learning via Sequence Modelingcited by 1,528
  10. 2019Generating Long Sequences with Sparse Transformerscited by 1,523
  11. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
  12. 2017Random Erasing Data Augmentationcited by 1,235
  13. 2017The "something something" video database for learning and evaluating visual common sensecited by 1,092
  14. 2021Perceiver: General Perception with Iterative Attentioncited by 1,089
  15. 2016Deep Networks with Stochastic Depthcited by 973
  16. 2020Designing Network Design Spacescited by 954
  17. 2021CvT: Introducing Convolutions to Vision Transformerscited by 946
  18. 2020Efficient Transformers: A Surveycited by 784
  19. 2018Image Transformercited by 770
  20. 2021PVT v2: Improved Baselines with Pyramid Vision Transformercited by 749
  21. 2020Long Range Arena: A Benchmark for Efficient Transformerscited by 696
  22. 2021Perceiver IO: A General Architecture for Structured Inputs & Outputscited by 616
  23. 2018Universal Transformerscited by 613
  24. 2021Twins: Revisiting the Design of Spatial Attention in Vision Transformerscited by 565
  25. 2021Linear Transformers Are Secretly Fast Weight Programmerscited by 471
  26. 2020Efficient Content-Based Sparse Attention with Routing Transformerscited by 469
  27. 2021Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attentioncited by 468
  28. 2021A Survey of Transformerscited by 399
  29. 2021Early Convolutions Help Transformers See Bettercited by 395
  30. 2021Random Feature Attentioncited by 350
  31. 2021FNet: Mixing Tokens with Fourier Transformscited by 343
  32. 2021XCiT: Cross-Covariance Image Transformerscited by 335
  33. 2018Generating Wikipedia by Summarizing Long Sequencescited by 333
  34. 2020Sparse Sinkhorn Attentioncited by 250
  35. 2021Keeping Your Eye on the Ball: Trajectory Attention in Video Transformerscited by 224
  36. 2021Multi-Scale Vision Longformer: A New Vision Transformer for High-Resolution Image Encodingcited by 207
  37. 2018Scaling Neural Machine Translationcited by 204
  38. 2020Synthesizer: Rethinking Self-Attention in Transformer Modelscited by 204

50 most cited of 68 All 68 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 10; 2024: 11; 2025: 1; 2026: 4.

31 papers.

Sort:

By area:

  1. 2023Adapting Language Models to Compress Contextscited by 350
  2. 2023In-context Autoencoder for Context Compression in a Large Language Modelcited by 190
  3. 2022The Devil in Linear Transformercited by 98
  4. 2024Lightning Attention-2: A Free Lunch for Handling Unlimited Sequence Lengths in Large Language Modelscited by 57
  5. 2023In-Context Learning with Many Demonstration Examplescited by 39
  6. 2023TransNormerLLM: A Faster and Better Large Language Model with Improved TransNormercited by 34
  7. 2024Various Lengths, Constant Speed: Efficient Language Modeling with Lightning Attentioncited by 31
  8. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 29
  9. 2023Faster Causal Attention Over Large Sequences Through Sparse Flash Attentioncited by 24
  10. 2023Efficient Attention via Control Variatescited by 23
  11. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  12. 2024UncertaintyRAG: Span-Level Uncertainty Enhanced Long-Context Modeling for Retrieval-Augmented Generationcited by 14
19 more
  1. 2022CAB: Comprehensive Attention Benchmarking on Long Sequence Modelingcited by 10
  2. 2024Linear Attention Sequence Parallelismcited by 8
  3. 2024IceFormer: Accelerated Inference with Long-Sequence Transformers on CPUscited by 8
  4. 2024SelfCP: Compressing Over-Limit Prompt via the Frozen Large Language Model Itselfcited by 8
  5. 2022Linear Video Transformer with Feature Fixationcited by 6
  6. 2024Squid: Long Context as a New Modality for Energy-Efficient On-Device Language Modelscited by 6
  7. 2024Theoretical Understanding of In-Context Learning in Shallow Transformers with Unstructured Datacited by 5
  8. 2022Attention and Self-Attention in Random Forestscited by 4
  9. 2023Linear Attention via Orthogonal Memorycited by 4
  10. 2022DBA: Efficient Transformer with Dynamic Bilinear Low-Rank Attentioncited by 3
  11. 2023FLuRKA: Fast and accurate unified Low-Rank & Kernel Attentioncited by 3
  12. 2024FactorLLM: Factorizing Knowledge via Mixture of Experts for Large Language Modelscited by 2
  13. 2024Interactive Multi-Head Self-Attention with Linear Complexitycited by 1
  14. 2025FlashEVA: Accelerating LLM inference via Efficient Attentioncited by 1
  15. 2026Analytical Correction for Subsampling Bias in Drifting Modelscited by 1
  16. 2026Scratchpad Patching: Decoupling Compute from Patch Size in Byte-Level Language Modelscited by 1
  17. 2023Attentive Multi-Layer Perceptron for Non-autoregressive Generationcited by 0
  18. 2026Finite-Time Analysis of Gradient Descent for Shallow Transformerscited by 0
  19. 2026Temporal Preservation over Processing: Diagnosing and Designing Spatiotemporal Single-Stage Video Detectorscited by 0