Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The FFT Strikes Back: An Efficient Alternative to Self-Attention

arxiv.org

Post reply on HN
Print view View original

21–30 of 175 posts

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#21

Post by physicsguy »

xeonmc wrote: post #8
jampekka wrote: post #6

Earlier quoted context omitted.

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

Yep, it's very common to use this. we used it for grid based pairwise interactions since it turns N^2 op into N log N.

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#23

Post by jampekka »

xeonmc wrote: post #8
jampekka wrote: post #6

Earlier quoted context omitted.

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

Sorry, added the convolution theorem part in an edit after your comment.

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#25

Post by DrNosferatu »

DrNosferatu wrote: post #22

Can someone confirm the big O time complexities of 1. traditional Self-Attention; 2. Flash-Attention? 3. Any novel others?

Ok, what FlashAttention changes is space complexity: from O(N^2) to O(N). Time complexity is still ~O(N^2) as with standard Self-Attention.

In other words, optimizes practical runtime through I/O reduction without altering asymptotic complexity

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#26

Post by roflmaostc »

yagizdegirmenci wrote: post #10

Google 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. [0]: https://arxiv.org/abs/2105.03824

Reference for the later part?

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#27

Post by DrNosferatu »

yagizdegirmenci wrote: post #10

Google 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. [0]: https://arxiv.org/abs/2105.03824

But this would only work on a very limited number of tokens, right?

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#28

Post by yagizdegirmenci »

roflmaostc wrote: post #26
yagizdegirmenci wrote: post #10

Google 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. [0]: https://arxiv.org/abs/2105.03824

Reference for the later part?

The section "3.3 Implementation" is mostly about hardware level speedups, which basically says:

On GPU(s) FFT is consistently faster, but in TPU(s), for shorter sequences matrix multiplication was faster.

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#30

Post by blovescoffee »

pointlessone wrote: post #14
jampekka wrote: post #6

Earlier quoted context omitted.

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…

I’m still confused. Does it treat the input tokens as a sampled waveform? I mean, say I have some text file in ASCII. Do I then just pretend it’s raw wav and do FFT on it? I guess it can give me some useful information (like does it look like any particular natural language or is it just random; sometimes used in encrytion analysis of simple substitution cyphers). It feels surprising that revers FFT can get a coheren…

No. The FFT is an operation on a discrete domain, it is not the FT. In the same way audio waveforms are processed by an FFT you bucket frequencies which is conceptually a vector. Once you have a vector, you do machine learning like you would with any vector (except you do some FT in this case, I haven’t read the paper).
Post reply on HN