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

41–50 of 175 posts

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

#41

Post by yorwba »

TheDudeMan wrote: post #34
yorwba wrote: post #9

I 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.

Winning against their own baseline, not against the current best-performing model. Which apparently is S5 currently https://paperswithcode.com/sota/long-range-modeling-on-lra with 87.46 overall vs. 58.31 here.

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

#42

Post by DrNosferatu »

TheDudeMan wrote: post #35
DrNosferatu wrote: post #22

Can 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.

Yes, in Mamba accuracy seems to goes down and has trouble in exact token recall. But, I would say it might be good for very power efficient edge deployment, and ultra long contexts.

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

#43

Post by agoose77 »

pointlessone wrote: post #5

OK, 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?

I am not an expert by _any_ means, but to provide _some_ intuition — self-attention is ultimately just a parameterised token mixer (see https://medium.com/optalysys/attention-fourier-transforms-a-...) i.e. each vector in the output depends upon the corresponding input vector transformed by some function of all the other input vectors.

You can see conceptually how this is similar to a convolution with some simplification, e.g. https://openreview.net/pdf?id=8l5GjEqGiRG

Convolutions are often used in contexts where you want to account for global state in some way. - https://openreview.net/pdf?id=8l5GjEqGiRG

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

#46

Post by singularity2001 »

larodi wrote: post #2

Man, this all really gets increasingly more complex in increasingly complex math…

Deep learning actually simplifies the extremely complex math of previous machine learning and statistics/stochastics into a very reasonable set of operations:

matrix multiplications and some very simple activation functions (plus automatic derivates, some magic and some scientific glasses which you can ignore)

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

#47

Post by markisus »

The Fourier transform is taken along the “token” dimension. However, in many applications, this dimension is not meaningful. That’s why transformers are a great option for consuming data which is permutation invariant.

I would like to see additional experiments using the lesser known Fourier transform over finite groups [1], which is permutation invariant but shares many properties with the standard Fourier transform.

I also wonder if this becomes the next big thing for LLMs, how easy will it be for inference engines(eg vLLM, llama.cpp) to integrate it?

[1] https://en.wikipedia.org/wiki/Fourier_transform_on_finite_gr...

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

#48

Post by kla-s »

TheDudeMan wrote: post #35
DrNosferatu wrote: post #22

Can 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.

Actually its a little more nuanced:

Operation Type|Mamba Complexity|Transformer Complexity

Training(per iteration)|O(L)|O(L^2)

Autoregressive Inference(per step)|O(T)|O(L)

Memory Requirements|O(C)|O(L)

Where: L stands for the sequence length. T denotes a fixed constant that accounts for compression and selection time in Mamba's autoregressive inference. C reflects the fixed size of the SSM (State Space Model) latent state in Mamba

Per: https://github.com/state-spaces/mamba/issues/196

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

#49

Post by gct »

bee_rider wrote: post #39
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

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).

They usually have dedicated acceleration hardware, yes: https://www.ti.com/lit/an/sprabb6b/sprabb6b.pdf?ts=174057874...
Post reply on HN