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

131–140 of 175 posts

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

#131

Post by hinkley »

light_hue_1 wrote: post #93
TheDudeMan wrote: post #32

Earlier quoted context omitted.

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 fo…

Except that the paper is written as if they discovered that you can use an fft for attention. They even have a "proof". It's in the title. Then you discover everyone already knew this and all they do is as some extra learnable parameters. Pretty lame.

Search engines don't always turn up prior art the way you'd like. Simple jargon discrepancies can cause a lot of mischief. Though I'm sure a case could be made about it being confirmation bias. It's hard to get people to search in earnest for bad news. If it's not in your face they declare absence of evidence as evidence of absence.

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

#132

Post by hinkley »

unraveller wrote: post #94
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

GPU saw a 10% improvement over the TPU >The TPU is so inefficient at FTs that the researchers did not use the FFT algorithm on sequences > on an Nvidia Quadro P6000 GPU, the FT was responsible for up to 30% of the inference time on the FNet architecture [0] This company [0] claimed in 2021 they could squash inference time by 40% if google would use their light chips on TPU. Perhaps more if FFTNet does more heavy lift…

I have been entertaining myself a bit lately by thinking about the ways in which some improvements to a design are very, very interesting to people when it takes 1.2 machines to do a task, not worth paying attention to when it's 6 machines to do the task, and suddenly very interesting again when it's 120 machines to do the task. There's that weird saddle point in the middle where I cannot get anyone else interested in my 20% resource improvements. It's just crickets.

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

#133

Post by spot5010 »

evanb wrote: post #120
snickmy wrote: post #112

Earlier quoted context omitted.

this is a great way to put it, that said, it was not obvious to me that the attention space (how it is structured in LLMs) is a frequency domain

A cartoon: To form a coherent idea you need to coordinate a lot of tokens. In other words, ideas are long-distance correlations between tokens. Ideas are the long-wavelength features of streams of tokens. Is it exactly right? No. But as a cartoon it can motivate exploring an idea like this.

Right. This makes sense. But why Fourier space in particular. Why not, for example, a wavelet transform.

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

#135

Post by ted_dunning »

ambicapter wrote: post #69
xeonmc wrote: post #7

Basically 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. [0] https://en.wikipedia.org/wiki/Convolution_theorem

> In other words, work in the domain that is natural to your data. Why would multiplication be more "natural" to a domain than convolution, as opposed to just simpler to calculate?

Here is an example that shows how high dimensional data can be sparse (aka simple aka natural) in some projections. Since FFTs are just a reprojection of your data, this provides useful intuition.

https://bsky.app/profile/bsky.tdunning.com/post/3lgvuzuju3k2...

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

#136

Post by 1024core »

spot5010 wrote: post #133
evanb wrote: post #120

Earlier quoted context omitted.

A cartoon: To form a coherent idea you need to coordinate a lot of tokens. In other words, ideas are long-distance correlations between tokens. Ideas are the long-wavelength features of streams of tokens. Is it exactly right? No. But as a cartoon it can motivate exploring an idea like this.

Right. This makes sense. But why Fourier space in particular. Why not, for example, a wavelet transform.

> Why not, for example, a wavelet transform.

That is a great idea for a paper. Work on it, write it up and please be sure to put my name down as a co-author ;-)

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

#137

Post by evanb »

spot5010 wrote: post #133
evanb wrote: post #120

Earlier quoted context omitted.

A cartoon: To form a coherent idea you need to coordinate a lot of tokens. In other words, ideas are long-distance correlations between tokens. Ideas are the long-wavelength features of streams of tokens. Is it exactly right? No. But as a cartoon it can motivate exploring an idea like this.

Right. This makes sense. But why Fourier space in particular. Why not, for example, a wavelet transform.

Now you’re talking efficiency—-certainly a wavelet transform may also work. But wavelets tend to be more localized than FTs.

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

#138

Post by 3abiton »

evanb wrote: post #120
snickmy wrote: post #112

Earlier quoted context omitted.

this is a great way to put it, that said, it was not obvious to me that the attention space (how it is structured in LLMs) is a frequency domain

A cartoon: To form a coherent idea you need to coordinate a lot of tokens. In other words, ideas are long-distance correlations between tokens. Ideas are the long-wavelength features of streams of tokens. Is it exactly right? No. But as a cartoon it can motivate exploring an idea like this.

This is really a very interesting way of visualizing it.

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

#139

Post by monkfish328 »

1024core wrote: post #136
spot5010 wrote: post #133

Earlier quoted context omitted.

Right. This makes sense. But why Fourier space in particular. Why not, for example, a wavelet transform.

> Why not, for example, a wavelet transform. That is a great idea for a paper. Work on it, write it up and please be sure to put my name down as a co-author ;-)

Or for that matter, a transform that's learned from the data :) A neural net for the transform itself!

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

#140

Post by LudwigNagasena »

xpe wrote: post #116
rachofsunshine wrote: post #111

Earlier quoted context omitted.

This is a good general tool for less-mathematically-deep folks to keep in their pocket: look for well-behaved objects that do something nice under the operation you're interested in. Typical "well-behaved" objects do things like stay where they are, or end up as a constant multiple of themselves, or end up as 0 or 1, or something like that. Then try to represent everything else in terms of those objects, so that you…

A nice generalization. An example in statistics is the expectation operator. You can throw away a lot of detail if you only care about one central moment. And if you need more information about a distribution, add more moments. Also, this works for public policy. Frame everything as a well functioning market and hope for the best. /s But seriously, a nice intuition.

Well, “think of the other points as (fixed point) + (small perturbation) and reduce your work to handling the perturbation” is literally how modern economic models (DSGE) are studied and then used for public policy.
Post reply on HN