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

111–120 of 175 posts

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

#111

Post by rachofsunshine »

ndriscoll wrote: post #82
ambicapter wrote: post #69

Earlier quoted context omitted.

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

One way to think about things is in terms of diagonalization. A generic linear operator is a fairly complicated thing that mixes information from different dimensions. When you diagonalize an operator, it's the same operator, but you're choosing a coordinate system where it becomes clear that all it was really doing was stretching along each coordinate axis, so you've broken it down into something that acts independe…

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 can take advantage of their convenient behavior. Less-difficult examples include:

- Prime factorization: primes have nice properties, and you can turn every integer into a product of primes (polynomial factorization is an extension of this idea) and work with the nice prime properties

- Vector spaces: basis vectors have nice properties, so you write vectors as sums of them and do operations on the coefficients instead of the vectors themselves

- The exponential function: it's the unique function with f'(x) = f(x), so you try to turn everything else into exponentials anytime you have to solve some painful differential equation because you know those terms will go away

- Fixed points in dynamical systems: if you don't want to analyze how arbitrary things change, find the points that don't, then think of the other points as (fixed point) + (small perturbation) and reduce your work to handling the perturbation

- Taylor series: polynomials are easy, smooth functions are hard, so turn your smooth function into a polynomial and do polynomial things with it

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

#112

Post by snickmy »

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

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

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

#113

Post by Karrot_Kream »

rachofsunshine wrote: post #111
ndriscoll wrote: post #82

Earlier quoted context omitted.

One way to think about things is in terms of diagonalization. A generic linear operator is a fairly complicated thing that mixes information from different dimensions. When you diagonalize an operator, it's the same operator, but you're choosing a coordinate system where it becomes clear that all it was really doing was stretching along each coordinate axis, so you've broken it down into something that acts independe…

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…

Yeah this mindset is often called "mathematical maturity" in books, and you've laid out a good pratical subset of it.

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

#114

Post by SJC_Hacker »

xphos wrote: post #88
yagizdegirmenci wrote: post #28

Earlier quoted context omitted.

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.

Yeah but a comparison in power utilization is needed too. You can build hardware that is better than a GPU at something i.e MatMul being really efficient and fast. However, actual FFT hardware would annihilate power and speed at large enough n. Simply because the number of multiplications MatMul does is O(n^3) as opposed to the O(n log n) multiplies that FFT does (complex verse real multiplies with holding).

FFT is only O(N log N) for a vector of length N WRT to matrices for an N by N matrix it would be like O(N^2 log N) you would perform FFT for each row or column

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

#115

Post by jacksnipe »

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?

Because multiplication gives rise to simpler algebras than convolution does.

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

#116

Post by xpe »

rachofsunshine wrote: post #111
ndriscoll wrote: post #82

Earlier quoted context omitted.

One way to think about things is in terms of diagonalization. A generic linear operator is a fairly complicated thing that mixes information from different dimensions. When you diagonalize an operator, it's the same operator, but you're choosing a coordinate system where it becomes clear that all it was really doing was stretching along each coordinate axis, so you've broken it down into something that acts independe…

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.

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

#117

Post by xpe »

iNic wrote: post #11
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?

- The Fourier Transform is an invertable operator (i.e. it acts on functions, in the case of matrices both functions and operators are themselves matrices). It transforms into what we call frequency space. - This is most intuitive for signal analysis or images [1]. - Frequency space is inherently "complex", i.e. represented by complex numbers. - Frequencies have the advantage that they take a "global" view of the pro…

Worth noting that frequency space is often considered one dimensional. Adding the phase is what gives the other dimension.

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

#118

Post by Eridrus »

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…

4096 tokens is pretty short by today's standards for transformers too.

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

#119

Post by kkylin »

snickmy wrote: post #112
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

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

Exactly. Exploiting the structure of the matrix (e.g., it is well approximated by a circulant matrix) is natural if there is structure to exploit. If everything in the preprint holds up, that might suggest some symmetries (e.g., approximate stationarity in time) in the data at hand.

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

#120

Post by evanb »

snickmy wrote: post #112
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

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.

Post reply on HN