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.

本文提出了一种基于自归一化重要性采样器的线性随机化注意力机制，结合了随机特征关注性的表达性和计算效率，能够以线性时间和空间复杂度近似整个 softmax 注意力，与随机特征关注性相比，具有很大的性能优势。