5 ms·

Basically leverages convolution theorem[0]: expensive convolutions in direct space becomes simple multiplications in reciprocal space, and vice versa. Whereeve

by xeonmc 2y ago

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

snickmy 2y ago
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
- kkylin 2y ago
  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.
- evanb 2y ago
  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.
  - kridsdale1 2y ago
    I like this. Anything that connects new synapses in my skull via analogy is a good post.
  - spot5010 2y ago
    Right. This makes sense. But why Fourier space in particular. Why not, for example, a wavelet transform.
    - 1024core 2y ago
      > 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 ;-)
      - monkfish328 2y ago
        Or for that matter, a transform that's learned from the data :) A neural net for the transform itself!
        spot5010 2y ago
        That would be super cool if it works! I’ve also wondered the same thing about activation functions. Why not let the algorithm learn the activation function?
        porridgeraisin 2y ago
        This idea exists (the broad field is called neural architecture search), although you have to parameterize it somehow to allow gradient descent to happen. Here are examples: https://arxiv.org/abs/2009.04759 https://arxiv.org/abs/2009.04759 https://arxiv.org/abs/1906.09529 https://arxiv.org/abs/1906.09529
        FuckButtons 2y ago
        Mostly because of computational efficiency irrc, the non linearity doesn’t seem to have much impact, so picking one that’s fast is a more efficient use of limited computational resources.
    - evanb 2y ago
      Now you’re talking efficiency—-certainly a wavelet transform may also work. But wavelets tend to be more localized than FTs.
    - thesz 2y ago
      This way you end up with time dilated convolutional networks [1]. [1] https://openreview.net/pdf?id=rk8wKk-R- https://openreview.net/pdf?id=rk8wKk-R-
  - 3abiton 2y ago
    This is really a very interesting way of visualizing it.
- pavelstoev 2y ago
  I wrote down the following in the internal Slack chat on 01.06.2025, but of course, the performance of the actual effort is much more than writing it down. Large language models (LLMs) operate in a high-dimensional token space, where tokens (words, subwords, or characters) can be viewed as discrete signals covering the multi-dimensional knowledge space. So FFT analysis methods can be applied to reduce time domain complexity to frequency domain representation with an idea to reduce computational complexity. So we can map token signals into the frequency domain. This transformation allows us to analyze token dynamics, such as their frequency of occurrence, temporal correlations, and interactions across contexts, with computational efficiency. In this approach, embeddings are treated as signals, and their relationships in sequence are captured as patterns in the frequency domain. FFT could be used to decompose token streams into dominant frequency components, revealing periodic or recurrent patterns in language usage - these patterns are repeatable across human generated knowledge and generally follow a predefined set of rules so the signals are not just white noise, they are predictable. By analyzing these frequency components, predictions of the next token can be made by emphasizing high-energy components in the frequency spectrum, reducing noise and focusing on statistically probable outcomes. Using this method we can reduce computational overhead during training and inference by enabling lightweight spectral analysis rather than heavy attention mechanisms, especially for long-context or repetitive sequences. Also using classical signal filtering techniques (LPF, HPF, band pass) could help align model behavior with human linguistic patterns, refine token embeddings, and improve efficiency in both training and inference phases.
  - deleted 2y ago
    [deleted]
ttoinou 2y ago
Yeah basic math space transformation sandwich : 1) turn data into another space 2) operate in that space 3) transform back into original space. To optimize this, optimize each step and work as much as possible in the most efficient space
- kridsdale1 2y ago
  Remains to be seen how lossy the transformations are. We lose a lot of data in DSP (aka “media”) doing too much.
  - thesz 2y ago
    ReLU throws away half of data. Yet it works.
ambicapter 2y ago
> 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?
- MajimasEyepatch 2y ago
  As an example, if you're trying to "smooth out" some signal, what you're really trying to do is remove the high frequency components. So using a Fourier transform to convert it to the frequency domain lets you directly work with the frequency data, rather than indirectly in the time/space/whatever domain. The fact that the operation is simpler in the frequency domain is a good hint that you've picked the "natural" space in which to look at the problem. Of course, there's no formal definition of "naturalness," and at the end of the day, you get the same result either way.
- amelius 2y ago
  I think they just meant simpler to calculate.
- ndriscoll 2y ago
  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 independently in a simple way on each dimension. The Fourier transform is unitary, so the intuition is that you're basically doing something like a rigid transformation of space (e.g. a rotation), and when you look from the correct angle, you see that your original operator wasn't some complicated "add a stretched version of this dimension to this other dimension minus a stretched version of a third dimension", but just "stretch this by this, this by this, etc." On the other hand, convolution itself is already "just" multiplication. e.g. multiplying polynomials is convolution of their coefficients (to get the x^n coefficient, you need to add up all the combinations of a_i a_j x^i x^j where i+j=n), and this point of view also applies to e.g. linear time-invariant systems[0] by thinking of your function as the weights of an infinite weighted sum (so sort of an infinite polynomial) of time-shift operators (and this point of view works for other groups, not just time shifts). So f(t) is then the "coefficient" for the t-shift, and multiplying two such weighted sums again has you convolve the coefficients (so your original functions). The jargon way to say this is that your space of G-invariant functions is secretly the free algebra generated by G (G being a group). From that point of view, convolution is the "natural" multiplication on G-invariant functions. One can then ask whether there's a Fourier transform for other groups, which leads to abstract harmonic analysis. e.g. the Mellin transform is the Fourier transform for scale/stretch invariant functions as opposed to shift invariant. [0] The typical systems that one studies in signal processing contexts where convolution and Fourier transforms are your bread and butter: https://en.wikipedia.org/wiki/Linear_time-invariant_system https://en.wikipedia.org/wiki/Linear_time-invariant_system
bigmattystyles 2y ago
Is reciprocal space always just 1/space as in frequency=1/t?
- nh23423fefe 2y ago
  yes. usually 1/space is often called wavenumber (k).
- cowsandmilk 2y ago
  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.
  - xeonmc 2y ago
    The formal, general name is “Dual space” I think.
    - jey 2y ago
      Unfortunately that’s very vague because there’s many notions of “dual space” within applied mathematics, even just considering the parts relevant to engineering applications.
  - SJC_Hacker 2y ago
    Maybe something like "recurrence space" would be better. Frequency does have a physical interpretation which could be misconstrued, e.g. the FFT of a wave in the space domain yields the wavenumber in the independent variable, not the frequency.
- rocqua 2y ago
  Ite called reciprocal because the fourier transformation is it's own inverse, and the input and output space have the same 'shape' (functions from the reals to the complex numbers). So they are considered two sides of the same coin. And reciprocal in that sense.
bjourne 2y ago
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 still have to deal with complex numbers.
- ToValueFunfetti 2y ago
  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.
  - feoren 2y ago
    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 defeats the entire claim, and you can't just "but" it back. Also, you appear to have used base-10 log for Log(3). It's almost certain that base-2 is more appropriate, leading to a factor of 1.8x, not 6x. But of course Log_1000(n) and Log_2(n) have the same Big-O, which is why the base is left off, so you really just cannot say anything specific at all. O(n^2) might be faster than O(n*log(n)) up to n = Graham's number.
    - ToValueFunfetti 2y ago
      >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.

by xeonmc 2y ago

snickmy 2y ago

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

kkylin 2y ago
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.
evanb 2y ago
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.
- kridsdale1 2y ago
  I like this. Anything that connects new synapses in my skull via analogy is a good post.
- spot5010 2y ago
  Right. This makes sense. But why Fourier space in particular. Why not, for example, a wavelet transform.
  - 1024core 2y ago
    > 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 ;-)
    - monkfish328 2y ago
      Or for that matter, a transform that's learned from the data :) A neural net for the transform itself!
      - spot5010 2y ago
        That would be super cool if it works! I’ve also wondered the same thing about activation functions. Why not let the algorithm learn the activation function?
        porridgeraisin 2y ago
        This idea exists (the broad field is called neural architecture search), although you have to parameterize it somehow to allow gradient descent to happen. Here are examples: https://arxiv.org/abs/2009.04759 https://arxiv.org/abs/2009.04759 https://arxiv.org/abs/1906.09529 https://arxiv.org/abs/1906.09529
        FuckButtons 2y ago
        Mostly because of computational efficiency irrc, the non linearity doesn’t seem to have much impact, so picking one that’s fast is a more efficient use of limited computational resources.
  - evanb 2y ago
    Now you’re talking efficiency—-certainly a wavelet transform may also work. But wavelets tend to be more localized than FTs.
  - thesz 2y ago
    This way you end up with time dilated convolutional networks [1]. [1] https://openreview.net/pdf?id=rk8wKk-R- https://openreview.net/pdf?id=rk8wKk-R-
- 3abiton 2y ago
  This is really a very interesting way of visualizing it.
pavelstoev 2y ago
I wrote down the following in the internal Slack chat on 01.06.2025, but of course, the performance of the actual effort is much more than writing it down. Large language models (LLMs) operate in a high-dimensional token space, where tokens (words, subwords, or characters) can be viewed as discrete signals covering the multi-dimensional knowledge space. So FFT analysis methods can be applied to reduce time domain complexity to frequency domain representation with an idea to reduce computational complexity. So we can map token signals into the frequency domain. This transformation allows us to analyze token dynamics, such as their frequency of occurrence, temporal correlations, and interactions across contexts, with computational efficiency. In this approach, embeddings are treated as signals, and their relationships in sequence are captured as patterns in the frequency domain. FFT could be used to decompose token streams into dominant frequency components, revealing periodic or recurrent patterns in language usage - these patterns are repeatable across human generated knowledge and generally follow a predefined set of rules so the signals are not just white noise, they are predictable. By analyzing these frequency components, predictions of the next token can be made by emphasizing high-energy components in the frequency spectrum, reducing noise and focusing on statistically probable outcomes. Using this method we can reduce computational overhead during training and inference by enabling lightweight spectral analysis rather than heavy attention mechanisms, especially for long-context or repetitive sequences. Also using classical signal filtering techniques (LPF, HPF, band pass) could help align model behavior with human linguistic patterns, refine token embeddings, and improve efficiency in both training and inference phases.
- deleted 2y ago
  [deleted]

ttoinou 2y ago

Yeah basic math space transformation sandwich : 1) turn data into another space 2) operate in that space 3) transform back into original space. To optimize this, optimize each step and work as much as possible in the most efficient space

kridsdale1 2y ago
Remains to be seen how lossy the transformations are. We lose a lot of data in DSP (aka “media”) doing too much.
- thesz 2y ago
  ReLU throws away half of data. Yet it works.

ambicapter 2y ago

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

MajimasEyepatch 2y ago
As an example, if you're trying to "smooth out" some signal, what you're really trying to do is remove the high frequency components. So using a Fourier transform to convert it to the frequency domain lets you directly work with the frequency data, rather than indirectly in the time/space/whatever domain. The fact that the operation is simpler in the frequency domain is a good hint that you've picked the "natural" space in which to look at the problem. Of course, there's no formal definition of "naturalness," and at the end of the day, you get the same result either way.
amelius 2y ago
I think they just meant simpler to calculate.
ndriscoll 2y ago
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 independently in a simple way on each dimension. The Fourier transform is unitary, so the intuition is that you're basically doing something like a rigid transformation of space (e.g. a rotation), and when you look from the correct angle, you see that your original operator wasn't some complicated "add a stretched version of this dimension to this other dimension minus a stretched version of a third dimension", but just "stretch this by this, this by this, etc." On the other hand, convolution itself is already "just" multiplication. e.g. multiplying polynomials is convolution of their coefficients (to get the x^n coefficient, you need to add up all the combinations of a_i a_j x^i x^j where i+j=n), and this point of view also applies to e.g. linear time-invariant systems[0] by thinking of your function as the weights of an infinite weighted sum (so sort of an infinite polynomial) of time-shift operators (and this point of view works for other groups, not just time shifts). So f(t) is then the "coefficient" for the t-shift, and multiplying two such weighted sums again has you convolve the coefficients (so your original functions). The jargon way to say this is that your space of G-invariant functions is secretly the free algebra generated by G (G being a group). From that point of view, convolution is the "natural" multiplication on G-invariant functions. One can then ask whether there's a Fourier transform for other groups, which leads to abstract harmonic analysis. e.g. the Mellin transform is the Fourier transform for scale/stretch invariant functions as opposed to shift invariant. [0] The typical systems that one studies in signal processing contexts where convolution and Fourier transforms are your bread and butter: https://en.wikipedia.org/wiki/Linear_time-invariant_system https://en.wikipedia.org/wiki/Linear_time-invariant_system

bigmattystyles 2y ago

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

nh23423fefe 2y ago
yes. usually 1/space is often called wavenumber (k).
cowsandmilk 2y ago
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.
- xeonmc 2y ago
  The formal, general name is “Dual space” I think.
  - jey 2y ago
    Unfortunately that’s very vague because there’s many notions of “dual space” within applied mathematics, even just considering the parts relevant to engineering applications.
- SJC_Hacker 2y ago
  Maybe something like "recurrence space" would be better. Frequency does have a physical interpretation which could be misconstrued, e.g. the FFT of a wave in the space domain yields the wavenumber in the independent variable, not the frequency.
rocqua 2y ago
Ite called reciprocal because the fourier transformation is it's own inverse, and the input and output space have the same 'shape' (functions from the reals to the complex numbers). So they are considered two sides of the same coin. And reciprocal in that sense.

bjourne 2y ago

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 still have to deal with complex numbers.

ToValueFunfetti 2y ago
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.
- feoren 2y ago
  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 defeats the entire claim, and you can't just "but" it back. Also, you appear to have used base-10 log for Log(3). It's almost certain that base-2 is more appropriate, leading to a factor of 1.8x, not 6x. But of course Log_1000(n) and Log_2(n) have the same Big-O, which is why the base is left off, so you really just cannot say anything specific at all. O(n^2) might be faster than O(n*log(n)) up to n = Graham's number.
  - ToValueFunfetti 2y ago
    >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.