We introduce Performers, Transformer architectures which can estimate regular
(softmax) full-rank-attention Transformers with provable accuracy, but using
only linear (as opposed to quadratic) space and time complexity, without
relying on any priors such as sparsity or low-rankness. To approximate softmax
attention-kernels, Performers use a novel Fast Attention Via positive
Orthogonal Random features approach (FAVOR+), which may be of independent
interest for scalable kernel methods. FAVOR+ can be also used to efficiently
model kernelizable attention mechanisms beyond softmax. This representational
power is crucial to accurately compare softmax with other kernels for the first
time on large-scale tasks, beyond the reach of regular Transformers, and
investigate optimal attention-kernels. Performers are linear architectures
fully compatible with regular Transformers and with strong theoretical
guarantees: unbiased or nearly-unbiased estimation of the attention matrix,
uniform convergence and low estimation variance. We tested Performers on a rich
set of tasks stretching from pixel-prediction through text models to protein
sequence modeling. We demonstrate competitive results with other examined
efficient sparse and dense attention methods, showcasing effectiveness of the
novel attention-learning paradigm leveraged by Performers.

本文介绍 Performers，这是 Transformer 结构，可以通过使用一种称为 FAVOR + 的新方法来估计常规（softmax）全秩注意力 Transformers，其具有可证明的准确性，但仅使用线性（而不是二次）空间和时间复杂性，而不依赖于任何先验知识，如稀疏度或低秩性。Performers 是线性结构，可以与常规 Transformers 完全兼容，并具有较强的理论保证。在各种任务上对 Performers 进行了测试，并展示了其在各自领域内对其他有效稀疏和密集关注方法的竞争力，展示了 Performers 所利用的新型关注学习范式的效果。