  Transformer and its variants are fundamental neural architectures in deep
learning. Recent works show that learning attention in the Fourier space can
improve the long sequence learning capability of Transformers. We argue that
wavelet transform shall be a better choice because it captures both position
and frequency information with linear time complexity. Therefore, in this
paper, we systematically study the synergy between wavelet transform and
Transformers. We propose Wavelet Space Attention (WavSpA) that facilitates
attention learning in a learnable wavelet coefficient space which replaces the
attention in Transformers by (1) applying forward wavelet transform to project
the input sequences to multi-resolution bases, (2) conducting attention
learning in the wavelet coefficient space, and (3) reconstructing the
representation in input space via backward wavelet transform. Extensive
experiments on the Long Range Arena demonstrate that learning attention in the
wavelet space using either fixed or adaptive wavelets can consistently improve
Transformer's performance and also significantly outperform learning in Fourier
space. We further show our method can enhance Transformer's reasoning
extrapolation capability over distance on the LEGO chain-of-reasoning task.
