The 2D Discrete Fourier Transform (DFT) can replace attention because the 2D DFT looks a lot like attention. The algorithm loops over each pair of values in the

The 2D Discrete Fourier Transform (DFT) can replace attention because the 2D DFT looks a lot like attention. The algorithm loops over each pair of values in the input matrix, calculating first a linear combination of each pair that scales based on the distance between the values in the matrix. Closer values have more influence on each other than more distance values. This linear combination is fed into the famous e^(i*pi) equation that transforms it into a sinusoid. The sinusoids are summed up, giving you an output matrix that is a sum of sinusoids representing the frequency domain. By comparison, the attention algorithm also combines each pair of values in the input matrix, but that linear combination involves learned weights, rather than simple fixed basis functions (sines and cosines) in the DFT. The FNet paper suggests that the DFT works as a replacement for attention because in making the pairwise calculations to generate the 2D frequency representation of the input, information on these pairwise relationships is surfaced and made available to later feed-forward layers. As a handy add-on feature, the DFT also makes positional embedding unnecessary, because positional information is encoded by the DFT at each layer. That being said, in the paper they still applied positional embeddings so that they could make a direct comparison with the BERT architecture. Amazing how these old signal processing ideas have made their way into neural networks, still proving their effectiveness and efficiency after 100 years or more (Gauss devised the Fast Fourier Transform algorithm in 1805 but we left it mostly on the shelf until it was reinvented by Cooley and Tukey in 1965).