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

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.

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.

Why would multiplication be more "natural" to a domain than convolution, as opposed to just simpler to calculate?

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

- 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

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.

That's all that "natural" means in this context. It's like "elegant" -- if it just takes less effort to get the result u need then why wouldn't you take the easier route?

So they are considered two sides of the same coin. And reciprocal in that sense.

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.

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?

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

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.

"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 for complex sequence modeling tasks."

And a comparison section after that.

Pretty lame.

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

The downside of implementing directly in hardware, the size would be fixed.

>The TPU is so inefficient at FTs that the researchers did not use the FFT algorithm on sequences < 4096 elements, instead opting for a quadratic-scaling FT implementation using a pre-computed DFT matrix.

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

[0]: https://scribe.rip/optalysys/attention-fourier-transforms-a-...

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

On GPU(s) FFT is consistently faster, but in TPU(s), for shorter sequences matrix multiplication was faster.

I still think we are comparing ASIC matmul hardware to non ASIC FFT hardware. The given TPU hardware is doing 256x256 matrix multiplication in linear time by using 256x256 multiplier grids. FFT ASIC could like do the same thing but be able to handle a much higher N size before memory becomes the bottleneck.

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

And it's not permutation invariant.

Aren't tokens transformed with position dependent information in most models?

I believe llama applies a rotation to the vector based on the position in the input.

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

- This mechanism is not equivalent to the attention mechanism. There is definitely a trade-off.

- But it is possible that it captures many of the important relationships that attention capture.

- I do not have good intuition for modReLU right away, but it seems important because it modifies the frequencies but preserves the inverse Fourier transform.

[1]: https://homepages.inf.ed.ac.uk/rbf/HIPR2/fourier.htm

Or equivalently rotates a (real) bias term with the input angle and adds that into the original.

  (abs(z) + c)*exp(i*arg(z)) = abs(z)*exp(i*arg(z)) + c*exp(i*arg(z)) = z + c*exp(i*arg(z))

The "frequencies" are probably something quite abstract. FFT is often used in ways where there aren't really clear frequency interpretation. The use is due to convenient mathematical properties (e.g. the convolution theorem).

Rather amazing if this really works well. Very elegant.

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.

I mean, say I have some text file in ASCII. Do I then just pretend it’s raw wav and do FFT on it? I guess it can give me some useful information (like does it look like any particular natural language or is it just random; sometimes used in encrytion analysis of simple substitution cyphers). It feels surprising that revers FFT can get a coherent output after fiddling with the distribution.

It seems unlikely to work for language.

If the results were close to state-of-the-art, probably the author would've mentioned it?

"SLA's are most likely to be violated 23-25 minutes after a service deployment. Hmm, I wonder why that is... Oh no."

Jokes aside one area this could be really worth money is predicting cycles of traffic and saving with ramp up and ramp down of server instances. It's the kind of work that if you're doing it out of your time the company would never give you greenlight it but if you pack it as a shelf product they would totally buy it.

As someone who is absolutely terrible at math, I envy the people who grasp or at least can learn this type of stuff and get an engineering degree and license.

All I really know about FFT is that is changes a signal, its somehow used in processing signals of some kind, and it apparently from what I heard was the key to detecting nuclear detonations back in the day.

The basic idea is this: (almost) any (useful) signal can be represented as a sum of sine waves with different frequencies and phases. For example, an electrical signal or a sound wave is a one-dimensional signal where the x-axis is time. This might look like a really complex squiggly line that's hard to work with. Using a Fourier transform, you can separate the individual frequencies of that time-based signal. Then, you can modify the specific frequencies however you want. For example, if you have a lot of random, spiky noise in the signal, that will show up as high frequencies. To clean it up, just do a Fourier transform, throw out any data with a frequency above a certain threshold, and then run an inverse Fourier transform on the remaining data to get back a smoother version of the original signal. This is called a low-pass filter, and it's more or less equivalent to taking a moving average of the original signal.

Where it gets really fun is that you can extend this, in a pretty straightforward way, to higher dimensions. A two-dimensional signal, where both the x- and y-axes are space, is just an image. JPEG compression is based on this concept: it removes the high-frequency signal in the image in order to store the data in a more compact form, at the expense of losing some fine detail (or creating those ring-like artifacts, if you throw out too much data). Add a third dimension for time, and now you have video. And so on.

The nice thing about all this is that it's very visual, so you can get a good intuition for it without having to know all the math inside and out. Here's a good page with lots of visualizations and interactive examples: https://www.jezzamon.com/fourier/index.html

And this 3Blue1Brown video does a good job of explaining it: https://youtu.be/spUNpyF58BY?si=dz0z-s8NftW3Htun

The Fourier transform (of which the FFT is a discrete version of) decomposes that 1D time-domain signal (e.g. an audio signal, time vs. displacement) into frequency vs. magnitude and phase components

The frequency is basically the pitch. So for a pure sine wave, or pure tone - which sounds like those "off air" TV signals we used to get late at night back in the day. You get a bunch of zeros and a single "spike" at the frequency of the tone. The larger the amplitude of the signal, the larger the magnitude of the spike will be. As the pitch (frequency) increases/decreases, the location of this spike moves up/down along horizontal axis

The phase is basically the time offset of the signal. A tone which was delayed somehow will show up as a different phase. Note this is a relative measure - not absolute. So you won't be able to tell if the signal was offset by 1s or 2s, etc. because it has units of radians(angle), which have to "reset" as the angle wraps around the circle.

So for one signal (time vs. amplitude), you actually get two pieces of information (frequency vs. magnitude/phase)

However if you understand imaginary numbers/complex variables, those two signals are really just the magnitude and argument of FFT output, which produces a complex function

Attention, by contrast, would treat those two occurrences similarly, with the only difference depending on positional encoding - so you can learn generalized patterns more easily.

You have seen this play out on a small scale, but if you calculate the size of the dense layers necessary to even theoretically replicate a big attention layer or even convolution, to say nothing of the data needed to train them without the help of the architecture's inductive bias, you will see that the clever architectures are quite necessary at scale.

The concept is fairly mainstream nowadays, to the degree that Jensen talked about it in his GTC keynote in 2021 [4] and there’s even a mainstage TED talk about its applications [5].

A nice property of doing things this way is that your model ends up being resolution-invariant which is particularly interesting for engineering domains. Scaling these methods has sparked the "let’s do a fully deep-learning-based weather model"-race [6][7].

As for using this on text data: my intuition would be that is going to not work as well because of a fairly unique property of text: for image, video and scientific data each individual element is of approximately equal importance, whereas in text you can have discrete tokens like a "not" somewhere in there that change the meaning of everything around it fairly significantly and you’d want that all to all interaction to capture that. Any kind of mixing that smoothes things out is going to inherently be at a disadvantage - probably true to some degree for most of those efficiency saving methods and why we’re seeing more limited adoption on text.

[1] https://arxiv.org/abs/2010.08895

[2] https://www.nature.com/articles/s42254-024-00712-5

[3] https://jmlr.org/papers/v22/21-0806.html

[4] https://www.youtube.com/watch?v=jhDiaUL_RaM&t=2472s

[5] https://www.ted.com/talks/anima_anandkumar_ai_that_connects_...

[6] https://arxiv.org/abs/2202.11214 (Feb 2022)

[7] https://www.wired.com/story/ai-hurricane-predictions-are-sto...

the default bias of -0.1 with relus and what i would expect to be a flattish spectrum also seems like it would make for a sparse representation in the fourier domain.

i assume this is learning the text embeddings at training time, if so, i'd be curious how the constraints of going through the fft and filtering magnitudes would/could change how the embeddings look.

https://docs.nvidia.com/cuda/cufft/

E.g. in a suitable space, one coordinate could represent the rotation of an object. You could do the transform and discard this dimension if your NN should be rotating invariant.

In other words, optimizes practical runtime through I/O reduction without altering asymptotic complexity

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

What Mamba does is take an initial state s_0 and an input u_0, to produce a new state s_1 and an output o_1. It's basically modeling a very complicated state machine. I can easily think of half a dozen applications where this is exactly what you want and it is better than transformers, but LLMs are not among them. Essentially most control problems boil down to what Mamba does. In fact, I would say that Mamba as an architecture is probably the non-plus ultra for modeling mechanical system dynamics.

This reminds me of some HN comments about rocketry ideas and in the thread one of the comments was “Everything in rocket science has been theorized/tried by some Russian scientist 40-50 years ago” and it still gives me a chuckle.

Arguably, the literature synthesis and knowledge discovery problem has been overwhelming in many fields for a long time; but I wonder if, in ML lately, an accelerated (if not frantic) level of competition may be working against the collegial spirit.

Stated another way, how can it be possible that it is more efficient to translate the sequence into a series of N variables, where the nth variable is the sum of every nth term of the sequence, if it is unlikely that any relationship between these variables holds for any fixed period? If I combine the 1st 4th 7th 10th .... elements of the sequence, how do we expect the addition of anything beyond the first two elements to add anything but noise?

Stated another another way, if I'm going to approximate a function as a sum of sine waves, this is most efficient when the function is periodic and requires more and more sine waves in the sum to approximate the function on a larger and larger domain when the function is not periodic.

1. Take FNet (https://arxiv.org/abs/2105.03824).

2. Replace the fixed (frequency-domain) convolution filter with one that is dynamically computed from the data.

3. Apply non-linear functions to both real and imaginary components, before mapping the convolved data back to the time domain.

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