  Transformers are state-of-the-art models for a variety of sequence modeling
tasks. At their core is an attention function which models pairwise
interactions between the inputs at every timestep. While attention is powerful,
it does not scale efficiently to long sequences due to its quadratic time and
space complexity in the sequence length. We propose RFA, a linear time and
space attention that uses random feature methods to approximate the softmax
function, and explore its application in transformers. RFA can be used as a
drop-in replacement for conventional softmax attention and offers a
straightforward way of learning with recency bias through an optional gating
mechanism. Experiments on language modeling and machine translation demonstrate
that RFA achieves similar or better performance compared to strong transformer
baselines. In the machine translation experiment, RFA decodes twice as fast as
a vanilla transformer. Compared to existing efficient transformer variants, RFA
is competitive in terms of both accuracy and efficiency on three long text
classification datasets. Our analysis shows that RFA's efficiency gains are
especially notable on long sequences, suggesting that RFA will be particularly
useful in tasks that require working with large inputs, fast decoding speed, or
low memory footprints.
