Sub-Linear Memory: How to Make Performers SLiM

By Valerii Likhosherstov, Krzysztof Marcin Choromanski, Jared Davis, Xingyou Song, Adrian Weller. 2020

25 citations recorded by the source corpus.

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(L^2)$ 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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Model Architectures, Efficiency & Compression

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Model Architectures

In Efficiency & Compression

Citations in the corpus

FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022, methodology): “There are numerous approaches to overcome this bottleneck, including approximation with hashing (i.e., sparse) such as Reformer [53] and Smyrf [20] and with low-rank approximation such as Performer [13, 56].”
Scatterbrain: Unifying Sparse and Low-rank Attention Approximation (2021, methodology): “…including attention matrix approximation such as Reformer [36], Performer [17], leveraging a side memory module that can access multiple tokens at once [38, 39, 56] such as Longformer [5] and BigBird [70], segment-based recurrence such as Transformer-XL [19] and Compressive Transformer [49].”
On The Computational Complexity of Self-Attention (2022, methodology): “More recent works such as the Performer [11], Slim [30], or RFA [31] approximate the attention computation using random projections.”