Stable, Fast and Accurate: Kernelized Attention with Relative Positional
  Encoding
  The attention module, which is a crucial component in Transformer, cannot
scale efficiently to long sequences due to its quadratic complexity. Many works
focus on approximating the dot-then-exponentiate softmax function in the
original attention, leading to sub-quadratic or even linear-complexity
Transformer architectures. However, we show that these methods cannot be
applied to more powerful attention modules that go beyond the
dot-then-exponentiate style, e.g., Transformers with relative positional
encoding (RPE). Since in many state-of-the-art models, relative positional
encoding is used as default, designing efficient Transformers that can
incorporate RPE is appealing. In this paper, we propose a novel way to
accelerate attention calculation for Transformers with RPE on top of the
kernelized attention. Based upon the observation that relative positional
encoding forms a Toeplitz matrix, we mathematically show that kernelized
attention with RPE can be calculated efficiently using Fast Fourier Transform
(FFT). With FFT, our method achieves $\mathcal{O}(n\log n)$ time complexity.
Interestingly, we further demonstrate that properly using relative positional
encoding can mitigate the training instability problem of vanilla kernelized
attention. On a wide range of tasks, we empirically show that our models can be
trained from scratch without any optimization issues. The learned model
performs better than many efficient Transformer variants and is faster than
standard Transformer in the long-sequence regime.
