Linear Complexity Randomized Self-attention Mechanism

Lin Zheng, Chong Wang, Lingpeng Kong

Standard softmax self-attention is the core of Transformer models, but it suffers from a major bottleneck: its computational cost grows quadratically ($O(N^2)$) with the sequence length $N$. This makes processing long sequences, such as high-resolution images or lengthy documents, prohibitively expensive.

Previous attempts to solve this, such as Random Feature Attention (RFA) (used in models like the Performer), linearize the attention kernel to achieve $O(N)$ complexity. However, RFA introduces a systematic bias because it approximates the exponential kernel while ignoring that softmax attention is fundamentally a ratio of these kernels. This bias often leads to inferior performance and slower convergence compared to standard Transformers.

To bridge the gap between efficiency and model expressiveness, researchers have introduced LARA (Linear Randomized Attention), a novel attention mechanism that achieves linear time and space complexity while significantly improving approximation accuracy.

Reframing Attention as Importance Sampling

The authors tackle the bias problem by recasting the attention mechanism as a statistical estimation problem. They reveal that RFA acts as a "self-normalized importance sampler," and this self-normalization is the exact source of its bias.

To correct this, they first derive Randomized Attention (RA), a theoretical unbiased estimator for the entire softmax attention operation. RA uses a query-specific Gaussian mixture distribution to sample random features. While highly accurate, RA cannot easily share statistics across different queries, leaving it stuck at $O(N^2)$ complexity.

To regain linear efficiency, the authors propose LARA. LARA utilizes Multiple Importance Sampling (MIS) with a small set of $C$ "landmark" proposal distributions ($C \ll N$). By using query-specific weighting functions to adaptively combine these shared proposals, LARA can pre-compute key-value statistics once. This maintains the $O(N)$ efficiency of RFA while capturing the query-specific nuances that make RA so accurate.

Key Results and Performance

LARA was rigorously evaluated across diverse domains, including image classification (ImageNet-1k), video action recognition (Kinetics-400, SSv2), machine translation (WMT14), and long sequence modeling (Long Range Arena).

Approximation Fidelity: In Mean Squared Error (MSE) tests against true softmax, LARA consistently demonstrated much lower error than the Performer. As more samples are added, LARA's error continues to drop, whereas the Performer's error plateaus due to its inherent bias.

Approximation MSE of different attention mechanisms across varying sequence lengths.

Task Performance: * ImageNet: On the DeiT-Small architecture, LARA-8 achieved 80.62% Top-1 accuracy, outperforming both the Performer (74.57%) and the standard Softmax Transformer (79.90%). * Video Recognition: LARA outperformed the Performer by over 5% on K400 and 10% on SSv2, offering a superior trade-off between accuracy and speed compared to other efficient baselines. * Long Range Arena (LRA): Both RA and LARA achieved the highest average scores across the LRA benchmark, proving their robustness for very long sequences where standard Transformers typically struggle.

Efficiency: Despite its high accuracy, LARA remains highly efficient. It runs nearly as fast as the Performer and consumes significantly less memory than standard softmax attention as sequence lengths scale up.

Relative memory consumption and running time across different sequence lengths.

Limitations and Future Work

While LARA presents a massive step forward for efficient attention, it currently has a few limitations. The present version is designed for bidirectional (encoder) attention and does not yet support the causal (autoregressive) attention modes required for GPT-style models. Additionally, the framework introduces new hyperparameters—such as the number of proposals ($C$) and the weighting coefficient ($\beta$)—which may require task-specific tuning. Future work will also explore incorporating trigonometric or other types of random features beyond the positive randomized mappings currently used.

Summary updated

Abstract

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 \emph{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.
BibTeX
@inproceedings{zheng2022linear,
  author = {Lin Zheng and Chong Wang and Lingpeng Kong},
  title = {{Linear Complexity Randomized Self-attention Mechanism}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
}
Figure