  Transformer models have achieved state-of-the-art results across a diverse
range of domains. However, concern over the cost of training the attention
mechanism to learn complex dependencies between distant inputs continues to
grow. In response, solutions that exploit the structure and sparsity of the
learned attention matrix have blossomed. However, real-world applications that
involve long sequences, such as biological sequence analysis, may fall short of
meeting these assumptions, precluding exploration of these models. To address
this challenge, we present a new Transformer architecture, Performer, based on
Fast Attention Via Orthogonal Random features (FAVOR). Our mechanism scales
linearly rather than quadratically in the number of tokens in the sequence, is
characterized by sub-quadratic space complexity and does not incorporate any
sparsity pattern priors. Furthermore, it provides strong theoretical
guarantees: unbiased estimation of the attention matrix and uniform
convergence. It is also backwards-compatible with pre-trained regular
Transformers. We demonstrate its effectiveness on the challenging task of
protein sequence modeling and provide detailed theoretical analysis.
