Makes me think what if NNs are treated as black box signal processing units. What other techniques can we borrow from signal processing?
The FFT Strikes Back: An Efficient Alternative to Self-Attention
31–40 of 175 posts
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#32Google 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
Referenced in this paper:
"Overall, while approaches such as FNet, Performer, and sparse transformers demonstrate that either fixed or approximate token mixing can reduce computational overhead, our adaptive spectral filtering strategy uniquely merges the efficiency of the FFT with a learnable, input-dependent spectral filter. This provides a compelling combination of scalability and adaptability, which is crucial for complex sequence modeling tasks."
And a comparison section after that.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#33I am very out of my depth here haha with the math, appreciate those below taking the time to baby walk me along with the understanding!
Great links too!
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#34I 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?
They do show their model as winning every category in Long Range Arena (LRA) benchmark. Hopefully they have not excluded losing categories or better models.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#35Can someone confirm the big O time complexities of 1. traditional Self-Attention; 2. Flash-Attention? 3. Any novel others?
Mamba is O(n). But I guess it has other drawbacks.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#36Machines going to be thinking in the frequency domain. We cooked.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#37Earlier 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…
Most likely the embedding of the token is passed through FFT
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#38Well done!
Besides immediate speed gains, I guess this opens the door to ultra-long contexts. Larger than say, 16M tokens.
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#39Google 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
That seems like an odd comparison, specialty hardware is often better, right?
Hey, do DSPs have special hardware to help with FFTs? (I’m actually asking, this isn’t a rhetorical question, I haven’t used one of the things but it seems like it could vaguely be helpful).
Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention
#40This guy's has had a lot bangers lately.