# SOFT: Softmax-free Transformer with Linear Complexity

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

## Key facts

- Cited by 128 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 48 references that are in the map.
- First posted on arXiv 22 Oct 2021.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [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)
- [Swin Transformer: Hierarchical Vision Transformer using Shifted Windows](https://mlsanity.com/paper/2103.14030/) (2021)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Rethinking the Inception Architecture for Computer Vision](https://mlsanity.com/paper/1512.00567/) (2015)
- [mixup: Beyond Empirical Risk Minimization](https://mlsanity.com/paper/1710.09412/) (2017)
- [Training data-efficient image transformers & distillation through attention](https://mlsanity.com/paper/2012.12877/) (2020)
- [Deformable DETR: Deformable Transformers for End-to-End Object Detection](https://mlsanity.com/paper/2010.04159/) (2020)
- [CutMix: Regularization Strategy to Train Strong Classifiers with Localizable Features](https://mlsanity.com/paper/1905.04899/) (2019)
- [Non-local Neural Networks](https://mlsanity.com/paper/1711.07971/) (2017)
- [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)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [Rethinking Semantic Segmentation from a Sequence-to-Sequence Perspective with Transformers](https://mlsanity.com/paper/2012.15840/) (2020)
- [Perceiver: General Perception with Iterative Attention](https://mlsanity.com/paper/2103.03206/) (2021)
- [Tokens-to-Token ViT: Training Vision Transformers from Scratch on ImageNet](https://mlsanity.com/paper/2101.11986/) (2021)
- [Designing Network Design Spaces](https://mlsanity.com/paper/2003.13678/) (2020)
- [Efficient Transformers: A Survey](https://mlsanity.com/paper/2009.06732/) (2020)
- [Going deeper with Image Transformers](https://mlsanity.com/paper/2103.17239/) (2021)
- [Long Range Arena: A Benchmark for Efficient Transformers](https://mlsanity.com/paper/2011.04006/) (2020)
- [Twins: Revisiting the Design of Spatial Attention in Vision Transformers](https://mlsanity.com/paper/2104.13840/) (2021)
- [ConViT: Improving Vision Transformers with Soft Convolutional Inductive Biases](https://mlsanity.com/paper/2103.10697/) (2021)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Conditional Positional Encodings for Vision Transformers](https://mlsanity.com/paper/2102.10882/) (2021)

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

- [PixArt-Sigma: Weak-to-Strong Training of Diffusion Transformer for 4K Text-to-Image Generation](https://mlsanity.com/paper/2403.04692/) (2024)
- [FLatten Transformer: Vision Transformer using Focused Linear Attention](https://mlsanity.com/paper/2308.00442/) (2023)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Run, Don't Walk: Chasing Higher FLOPS for Faster Neural Networks](https://mlsanity.com/paper/2303.03667/) (2023)
- [EdgeViTs: Competing Light-weight CNNs on Mobile Devices with Vision Transformers](https://mlsanity.com/paper/2205.03436/) (2022)
- [Demystify Mamba in Vision: A Linear Attention Perspective](https://mlsanity.com/paper/2405.16605/) (2024)
- [Modeling Dense Multimodal Interactions Between Biological Pathways and Histology for Survival Prediction](https://mlsanity.com/paper/2304.06819/) (2023)
- [The Hidden Attention of Mamba Models](https://mlsanity.com/paper/2403.01590/) (2024)
- [Agent Attention: On the Integration of Softmax and Linear Attention](https://mlsanity.com/paper/2312.08874/) (2023)
- [Beyond the Limits: A Survey of Techniques to Extend the Context Length in Large Language Models](https://mlsanity.com/paper/2402.02244/) (2024)
- [Test-time regression: a unifying framework for designing sequence models with associative memory](https://mlsanity.com/paper/2501.12352/) (2025)
- [Flowformer: Linearizing Transformers with Conservation Flows](https://mlsanity.com/paper/2202.06258/) (2022)
- [FasterViT: Fast Vision Transformers with Hierarchical Attention](https://mlsanity.com/paper/2306.06189/) (2023)
- [THE-X: Privacy-Preserving Transformer Inference with Homomorphic Encryption](https://mlsanity.com/paper/2206.00216/) (2022)
- [Bridging the Divide: Reconsidering Softmax and Linear Attention](https://mlsanity.com/paper/2412.06590/) (2024)
- [Replacing softmax with ReLU in Vision Transformers](https://mlsanity.com/paper/2309.08586/) (2023)
- [A survey on efficient vision transformers: algorithms, techniques, and performance benchmarking](https://mlsanity.com/paper/2309.02031/) (2023)
- [In-Context Learning with Many Demonstration Examples](https://mlsanity.com/paper/2302.04931/) (2023)
- [A Survey of Mamba](https://mlsanity.com/paper/2408.01129/) (2024)
- [Self-Guided Diffusion Models](https://mlsanity.com/paper/2210.06462/) (2022)
- [Transforming medical imaging with Transformers? A comparative review of key properties, current progresses, and future perspectives](https://mlsanity.com/paper/2206.01136/) (2022)
- [SimA: Simple Softmax-free Attention for Vision Transformers](https://mlsanity.com/paper/2206.08898/) (2022)
- [Generative Semantic Segmentation](https://mlsanity.com/paper/2303.11316/) (2023)
- [Linear Complexity Randomized Self-attention Mechanism](https://mlsanity.com/paper/2204.04667/) (2022)
- [Attention Mechanism in Neural Networks: Where it Comes and Where it Goes](https://mlsanity.com/paper/2204.13154/) (2022)
- [Primal-Attention: Self-attention through Asymmetric Kernel SVD in Primal Representation](https://mlsanity.com/paper/2305.19798/) (2023)
- [Castling-ViT: Compressing Self-Attention via Switching Towards Linear-Angular Attention at Vision Transformer Inference](https://mlsanity.com/paper/2211.10526/) (2022)
- [Transformers from an Optimization Perspective](https://mlsanity.com/paper/2205.13891/) (2022)
- [Prune Spatio-temporal Tokens by Semantic-aware Temporal Accumulation](https://mlsanity.com/paper/2308.04549/) (2023)
- [Efficient Diffusion Transformer with Step-wise Dynamic Attention Mediators](https://mlsanity.com/paper/2408.05710/) (2024)

## Abstract (arXiv)

Vision transformers (ViTs) have pushed the state-of-the-art for various visual recognition tasks by patch-wise image tokenization followed by self-attention. However, the employment of self-attention modules results in a quadratic complexity in both computation and memory usage. Various attempts on approximating the self-attention computation with linear complexity have been made in Natural Language Processing. However, an in-depth analysis in this work shows that they are either theoretically flawed or empirically ineffective for visual recognition. We further identify that their limitations are rooted in keeping the softmax self-attention during approximations. Specifically, conventional self-attention is computed by normalizing the scaled dot-product between token feature vectors. Keeping this softmax operation challenges any subsequent linearization efforts. Based on this insight, for the first time, a softmax-free transformer or SOFT is proposed. To remove softmax in self-attention, Gaussian kernel function is used to replace the dot-product similarity without further normalization. This enables a full self-attention matrix to be approximated via a low-rank matrix decomposition. The robustness of the approximation is achieved by calculating its Moore-Penrose inverse using a Newton-Raphson method. Extensive experiments on ImageNet show that our SOFT significantly improves the computational efficiency of existing ViT variants. Crucially, with a linear complexity, much longer token sequences are permitted in SOFT, resulting in superior trade-off between accuracy and complexity.