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

101–110 of 175 posts

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

#101

Post by j2kun »

bjourne wrote: post #92
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

Yeah, but the savings are theoretical. You turn a O(n^2) operation into O(nlog n). Sounds great until you realize that n is three on average. To boot, you have to use complex numbers for calculations which are also less numerically stable. So, to the best of my knowledge, FFT is not a win for ordinary convolution. Maybe for self-attention and for their use cases n is much larger, I didn't read the article. But you st…

There are integer-only FFT analogues that enable the same tricks. Cf. https://en.wikipedia.org/wiki/Discrete_Fourier_transform_ove...

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

#102

Post by j2kun »

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

> faster than FFT

Not only that, but FFT support on TPU has always been best effort. Last I tried this, there were serious precision issues.

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

#103

Post by soVeryTired »

ToValueFunfetti wrote: post #98
bjourne wrote: post #92

Earlier quoted context omitted.

Yeah, but the savings are theoretical. You turn a O(n^2) operation into O(nlog n). Sounds great until you realize that n is three on average. To boot, you have to use complex numbers for calculations which are also less numerically stable. So, to the best of my knowledge, FFT is not a win for ordinary convolution. Maybe for self-attention and for their use cases n is much larger, I didn't read the article. But you st…

3^2 / (3*log(3)) = >6x performance improvement and, if three is a linear average, I'd expect the average improvement to be even higher. I know real world computation doesn't answer to the simple scaling equations and there may well be a constant factor >6 that eats the gains, but I don't think the two Big Os and a n=3 are sufficient to make your case.

FYI you’re using log(3) to the base 10 there. That’s less than one so your figures look artificially good.

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

#104

Post by feoren »

bjourne wrote: post #92
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

Yeah, but the savings are theoretical. You turn a O(n^2) operation into O(nlog n). Sounds great until you realize that n is three on average. To boot, you have to use complex numbers for calculations which are also less numerically stable. So, to the best of my knowledge, FFT is not a win for ordinary convolution. Maybe for self-attention and for their use cases n is much larger, I didn't read the article. But you st…

> You turn a O(n^2) operation into O(nlog n). Sounds great until you realize that n is three on average.

Sure, but are long convolutions avoided precisely because they're expensive? This paper is talking about an alternative to an attention mechanism, which covers the entire context window, no? Isn't this paper saying: you could use a long convolution for this instead, and long convolutions don't have to be slow?

> you have to use complex numbers for calculations which are also less numerically stable

I haven't heard numerical stability being a big deal in neural nets; in fact don't people often use 16-bit floats as weights to save on space? Does the numerical stability of complex numbers exceed the precision dropped off by quantization anyway? Are complex numbers really inherently less numerically stable, or are we just not as good at using them yet?

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

#106

Post by ToValueFunfetti »

feoren wrote: post #100
ToValueFunfetti wrote: post #98

Earlier quoted context omitted.

3^2 / (3*log(3)) = >6x performance improvement and, if three is a linear average, I'd expect the average improvement to be even higher. I know real world computation doesn't answer to the simple scaling equations and there may well be a constant factor >6 that eats the gains, but I don't think the two Big Os and a n=3 are sufficient to make your case.

That's not how O(f(n)) notation works. You can't just plug in an n to O(f(n)) / O(g(n)) and claim a specific performance improvement. You have to actually know all the factors that are stripped off by big-O to do that, and you never really do. For instance, you're ignoring the cost to transform between domains. > I know real world computation doesn't answer to the simple scaling equations ... but No, no "but". This d…

>This defeats the entire claim, and you can't just "but" it back.

You may have missed what the "but" is doing- it's agreeing with you. My entire claim is defeated, and it uses the same reasoning that that the parent used to make their claim. I'm not attempting to show that there is an improvement, only that the lack of improvement has not been demonstrated by listing two Big-Os and setting n.

But yes, the log base 10 is my bad.

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

#107

Post by markisus »

yorwba wrote: post #75
markisus wrote: post #74

Earlier quoted context omitted.

I’m thinking the integers mod 2^n where n is something computers are good at (8, 32, 64). You have hardware support the group operation.

That is the traditional Fourier transform, except it can be a cyclic group of any size, doesn't need to be a power of 2. (Though FFTs with 2^n input size are particularly easy to implement.) And it's not permutation invariant.

I was careless in my thinking, thanks for the correction. I was imagining since you sum the group elements in any order, there is a permutation invariance. But the group elements themselves play the role of the "token index" and group elements are not interchangeable. To actually make this idea interesting, one would have to use a group in which the choice of group element assigned to each input token would not affect the result.

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

#108

Post by adgjlsfhk1 »

bjourne wrote: post #92
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

Yeah, but the savings are theoretical. You turn a O(n^2) operation into O(nlog n). Sounds great until you realize that n is three on average. To boot, you have to use complex numbers for calculations which are also less numerically stable. So, to the best of my knowledge, FFT is not a win for ordinary convolution. Maybe for self-attention and for their use cases n is much larger, I didn't read the article. But you st…

fft is unitary so it has really good numerical stability

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

#109

Post by physicsguy »

dekhn wrote: post #91
physicsguy wrote: post #21

Earlier quoted context omitted.

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.

That sounds just like Particle Mesh Ewald, which we use in molecular dynamics to approximate the forces of pairwise interactions (interpolated on a grid). I https://en.wikipedia.org/wiki/P3M

It's similar but I worked on magnetic spin systems with dipole-dipole interactions, so there wasn't the interpolation part, and as I understand it in Ewald summation you're always assuming periodic boundary conditions.

In our spin systems you basically pre-compute the interaction kernel tensor and can either take into account periodicity or ignore it depending on what sort of system you're looking at. Often you don't want the periodic effect since the dipole-dipole interaction is only one of many, much of the interesting phenomena in magnetics is in the interplay between short range forces and the long range forces. At each time step you FFT to the magnetisation tensor and then multiply with the interaction tensor, then iFFT.

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

#110

Post by cowsandmilk »

bigmattystyles wrote: post #78
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

Is reciprocal space always just 1/space as in frequency=1/t?

In the case of FFTs, no. Which is why I prefer the term Fourier space. I don’t like frequency domain because I frequently work with 3-D and 5–D FFTs while I’ve always felt frequency is connected to single dimension FFT.
Post reply on HN