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 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.
Introduction
The Transformer architecture has become the backbone of modern deep learning, yet it suffers from a fundamental scalability issue: the self-attention mechanism. The computational cost of standard softmax attention grows quadratically ($O(N^2)$) with the sequence length $N$. This scaling behavior makes it prohibitively expensive for processing long documents, high-resolution images, or long-form video.
To address this, researchers have previously proposed Random Feature Attention (RFA) and methods like Performers, which use kernel linearization to reduce complexity to $O(N)$. However, these methods often suffer from a "performance gap" compared to standard Transformers. This research introduces Linear Randomized Attention (LARA), a mechanism that achieves the efficiency of linear-time models while maintaining the high fidelity of standard softmax attention by reframing the problem through the lens of statistical importance sampling.
The Problem: Understanding Approximation Bias
The primary reason previous linear approximations like RFA underperform is mathematical bias. Standard softmax attention is calculated as a ratio of two kernels (the numerator representing the weighted values and the denominator representing the normalization term). Traditional RFA approximates these two components separately using random features.
Because the expectation of a ratio is not generally equal to the ratio of expectations, this "kernel linearization" approach is inherently biased. This bias leads to poor approximation fidelity, especially in complex tasks where precise attention weights are critical.
Proposed Methodology
1. Randomized Attention (RA)
The authors first propose Randomized Attention (RA), which treats the entire softmax operation as a single expectation over an input-dependent mixture of Gaussians. By sampling from this specific distribution, RA provides the first truly unbiased estimator for softmax attention. While RA offers superior accuracy, it remains $O(N^2)$ because the sampling distribution is unique to each query, preventing the "associative property" trick used to achieve linearity.
2. Linear Randomized Attention (LARA)
To achieve $O(N)$ complexity, the authors developed LARA using Multiple Importance Sampling (MIS). Instead of generating a unique distribution for every single query, LARA uses a small, shared set of "proposal" distributions ($C \ll N$) based on clusters or "landmarks" of queries.
By employing a self-normalized version of the MIS estimator, LARA enables the computation reuse necessary for linear time and space complexity. This allows the model to retain the query-specific expressiveness of RA while operating with the efficiency of RFA.
Experimental Results
The researchers evaluated RA and LARA across multiple domains to test their robustness and efficiency:
- Image Classification (ImageNet-1k): Using the DeiT-Small architecture, LARA achieved a Top-1 accuracy of 80.62%. This significantly outperformed the Performer (74.57%) and even slightly exceeded standard Softmax attention (79.90%) in specific long-sequence configurations.
- Machine Translation (WMT14 EN-DE): LARA reached 27.0 BLEU, nearly matching the standard Transformer's 27.5 BLEU, whereas the Performer trailed significantly at 23.3-23.7 BLEU.
- Long Range Arena (LRA): On this benchmark designed specifically for long-dependency tasks (including ListOps and Pathfinder), RA and LARA achieved the highest average scores, demonstrating their ability to handle long-context modeling better than existing linear alternatives.
- Efficiency: Despite the increased mathematical complexity, LARA's computational overhead is marginal. It runs nearly as fast as RFA and Performer, while the quadratic RA was found to be twice as slow as standard softmax due to the sampling overhead.
Conclusion and Future Work
LARA represents a significant step forward in the quest for efficient Transformers. By identifying the importance sampling nature of attention, the authors have bridged the gap between $O(N)$ efficiency and $O(N^2)$ accuracy.
Currently, LARA is optimized for bidirectional (encoder) attention. Future research directions include extending this framework to support causal masking for autoregressive language modeling (decoders) and exploring the application of importance sampling to other kernel types, such as trigonometric kernels.
Summary updated