The FFT Strikes Back: An Efficient Alternative to Self-Attention
1–10 of 175 posts
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#2Man, this all really gets increasingly more complex in increasingly complex math…
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#3Isn't flash attention already n log n?
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#4Isn't flash attention already n log n?
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#5OK, I admit that the math flies way over my head and I barely understand the text around the math. Can someone please explain (in basic English) how this is equivalent to attention mechanism? What friquencies does it talk about? How does it encode positional relations between tokens?
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#6OK, I admit that the math flies way over my head and I barely understand the text around the math. Can someone please explain (in basic English) how this is equivalent to attention mechanism? What friquencies does it talk about? How does it encode positional relations between tokens?
The actual mechanism at least is quite simple. Essentially it takes the FFT of the input embeddings, multiplies it elementwise with weights that are gotten from the input embeddings using an MLP (plus a constant (but learnable) bias) and then runs it through an activation function and finally takes the inverse FFT.
The "frequencies" are probably something quite abstract. FFT is often used in ways where there aren't really clear frequency interpretation. The use is due to convenient mathematical properties (e.g. the convolution theorem).
Rather amazing if this really works well. Very elegant.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#7Basically leverages convolution theorem[0]: expensive convolutions in direct space becomes simple multiplications in reciprocal space, and vice versa.
Whereever you have a convolution operation on your data, transform them to the conjugate domain to turn it into multiplication.
In other words, work in the domain that is natural to your data.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#8OK, I admit that the math flies way over my head and I barely understand the text around the math. Can someone please explain (in basic English) how this is equivalent to attention mechanism? What friquencies does it talk about? How does it encode positional relations between tokens?
The actual mechanism at least is quite simple. Essentially it takes the FFT of the input embeddings, multiplies it elementwise with weights that are gotten from the input embeddings using an MLP (plus a constant (but learnable) bias) and then runs it through an activation function and finally takes the inverse FFT. The "frequencies" are probably something quite abstract. FFT is often used in ways where there aren't r…
Essentially leveraging Convolution theorem. Same philosophy pops up in many places, e.g. DFT calculations
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#9I don't see how you could fit causal masking into this framework without having to do n different FFTs, and there's no mention of positional embeddings either, so I guess the self-attention implementation being compared against is noncausal NoPE, which would make this a case of baseline sandbagging and maybe not so impressive.
If the results were close to state-of-the-art, probably the author would've mentioned it?
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#10Google introduced this idea in 2022 with "FNet: Mixing Tokens with Fourier Transforms" [0].
Later they found out that, performance of their TPU(s) for matrix multiplication was faster than FFT in the most scenarios.