# Sub-Linear Memory: How to Make Performers SLiM

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Dec 2020.

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

- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Token Fusion: Bridging the Gap between Token Pruning and Token Merging](https://mlsanity.com/paper/2312.01026/) (2023)
- [S3: Increasing GPU Utilization during Generative Inference for Higher Throughput](https://mlsanity.com/paper/2306.06000/) (2023)
- [Accelerating Transformers with Spectrum-Preserving Token Merging](https://mlsanity.com/paper/2405.16148/) (2024)
- [A Fast Transformer-based General-Purpose Lossless Compressor](https://mlsanity.com/paper/2203.16114/) (2022)
- [PermuteFormer: Efficient Relative Position Encoding for Long Sequences](https://mlsanity.com/paper/2109.02377/) (2021)
- [Simplex Random Features](https://mlsanity.com/paper/2301.13856/) (2023)
- [Mnemosyne: Learning to Train Transformers with Transformers](https://mlsanity.com/paper/2302.01128/) (2023)
- [How Many Tokens Do 3D Point Cloud Transformer Architectures Really Need?](https://mlsanity.com/paper/2511.05449/) (2025)
- [GIST: Gauge-Invariant Spectral Transformers for Scalable Graph Neural Operators](https://mlsanity.com/paper/2603.16849/) (2026)
- [Manifold Random Features](https://mlsanity.com/paper/2602.03797/) (2026)
- [SLAY: Geometry-Aware Spherical Linearized Attention with Yat-Kernel](https://mlsanity.com/paper/2602.04915/) (2026)
- [Multiple View Performers for Shape Completion](https://mlsanity.com/paper/2209.06291/) (2022)
- [Less is More! A slim architecture for optimal language translation](https://mlsanity.com/paper/2305.10991/) (2023)
- [Linear Attention is Enough in Spatial-Temporal Forecasting](https://mlsanity.com/paper/2408.09158/) (2024)
- [Efficient Learned Data Compression via Dual-Stream Feature Decoupling](https://mlsanity.com/paper/2604.07239/) (2026)

## Abstract (arXiv)

The Transformer architecture has revolutionized deep learning on sequential data, becoming ubiquitous in state-of-the-art solutions for a wide variety of applications. Yet vanilla Transformers are notoriously resource-expensive, requiring O(L2) in serial time and memory as functions of input length L. Recent works proposed various linear self-attention mechanisms, scaling only as O(L) for serial computation. We perform a thorough analysis of recent Transformer mechanisms with linear self-attention, Performers, in terms of overall computational complexity. We observe a remarkable computational flexibility: forward and backward propagation can be performed with no approximations using sublinear memory as a function of L (in addition to negligible storage for the input sequence), at a cost of greater time complexity in the parallel setting. In the extreme case, a Performer consumes only O(1) memory during training, and still requires O(L) time. This discovered time-memory tradeoff can be used for training or, due to complete backward-compatibility, for fine-tuning on a low-memory device, e.g. a smartphone or an earlier-generation GPU, thus contributing towards decentralized and democratized deep learning.