Faster Fourier Transforms

The OpenAI algorithm for the FFT is less a breakthrough and more a malicious exploit.

Hi there, argmin readers! Today’s post looks at part of OpenAI’s math repository that claims to compute faster Fourier transforms. It’s more technical than usual, but I tried to add some tutorial material for people who need a refresher course on signal processing or computational complexity.

---

The Fast Fourier Transform is one of the most important innovations in digital signal processing and one of my favorite algorithms. The FFT is a fast way to extract the frequency content of signals, letting you rapidly analyze, filter, and manipulate frequencies across different bands of the spectrum.

The Fourier transform computes the energy in each frequency band through a simple dot product.¹ Let x denote your input, a length n array of samples, and f a frequency. Then the amount of frequency content in x at f can be computed by the formula:

For digital signals, a bit of math shows you only need to compute n of these dot products, one at each multiple of the frequency 2𝜋/n, to understand all of the frequency content. Naively, this requires n multiplications and additions for each frequency. Hence, computing the entire Fourier transform appears to require n² arithmetic operations.

The fast Fourier transform is a clever recursive procedure devised by James Cooley and John Tukey in 1965.² The main idea is that a length-n Fourier transform can be computed by shuffling the input vector, computing two Fourier transforms of length n/2 on the shuffled components, and then recombining the outputs using atomic arithmetic operations. The shuffles and recombinations take a linear number of arithmetic operations. Repeating this procedure iteratively, namely, log₂(n) times, computes the full discrete Fourier transform. With the bookkeeping, the FFT computes a length-n Fourier transform in fewer than 5 n log2 n arithmetic operations.

To make this acceleration concrete, when n is 1,000, n^2 is 1,000,000 and 5 * n log n is around 50,000, a 20-fold speedup. When n is 1,000,000, the speedup is 10,000-fold. These speedups can be the difference between a transform being computable or not given the constraints of a signal processing application.

Since the invention of the FFT, people have looked for even faster Fourier transforms. One question is just how fast you can go. It seems like you probably need at least n operations to compute the FFT, as it takes n steps just to write it down. The FFT is 5*log₂(n) times slower than that reasonable speed limit, and that 5*log₂(n) factor can be big. It’s 200 when n is a trillion. Can you do something clever to reduce that prefactor of 200?

Well, lo and behold, in the massive paper dump OpenAI took on the mathematics world last week, they claim to have a faster Fourier transform. The main claim from their discriminatively named “main.pdf” is

I was intrigued about what was going on here. The log(n) term, in theory, was a teeny tiny bit smaller than in the standard FFT.

Did I read this paper? Of course not. No one at OpenAI read this paper either, so why should I? I did what every other mathematician in the world does with AI slop mathematics: I fed it back into the slop machine and ran an information retrieval session with a chatbot interface to extract salient facts. Anthropomorphically speaking: I asked ChatGPT what it thinks about its own output. This is how we do mathematical research now. What a world.

Unfortunately, I did not find a faster Fourier transform. Instead,l I found the rot that develops inside applied mathematical theory when formalism becomes so detached from reality that a “breakthrough” is nothing more than an artifact of mathematicians not being able to properly specify the rules of their games in natural language.

First, “big-O” notation has been so abused that it has become meaningless. Let’s review the definition, which impressed me as an undergrad. An algorithm has running time T(n) = O(F(n)) if there exists an integer N and a constant C such that

That is, the number of steps the algorithm actually takes is upper bounded by a constant times some convenient function F(n) as long as n is large. F(n) is usually something familiar and interpretable, like a polynomial or exponential function. This notation says that we only care about what happens when the size of the computation is large. We care about the asymptotic growth rate of the computation time. All constants are equivalent.

Big-O notation is useful for shortcuts in algorithmic accounting, but it also allows for remarkable logical laziness. If we want a practically faster FFT, we want an algorithm that requires fewer than 50n operations for reasonably sized n. But O(n) does not mean 50 n. It could mean 10⁸⁰ n. This would be considered a “linear time” algorithm. An algorithm that requires n + 10⁸⁰ is also considered a linear time algorithm in the big-O regime. An algorithm that only has linear-time guarantees when n is greater than 10⁸⁰ is also considered linear time. 10⁸⁰ is approximately equal to the number of atoms in the known universe. That is why Richard Lipton and Ken Regan call algorithms with unfathomably large hidden constants galactic algorithms.

The OpenAI FFT algorithm is definitely galactic. The estimated values for C were 10¹⁰⁰ when N=10¹². So even when n=10¹⁰⁰, the venerable Cooley-Tukey-Gauss FFT would be 10⁹⁹ times faster.

So why is this new FFT result interesting? Well, note that in big-O notation, it is technically asymptotically faster than the Cooley-Tukey algorithm because

I mean, sure. But given the constants, the algorithm runs faster only when n is impossibly large. Roughly, you need

whatever the hell that number means.

Lipton and Regan argue galactic algorithms are useful because they spur research. Once you show a running time is asymptotically possible, you can spend your time finding an algorithm that practically achieves this provable running time. Maybe you can send your AI agent swarms after it. You do you. Maybe you can get a practical algorithm out, but I don’t know of any legitimate examples where this happened. I’m particularly doubtful here, because the model of “computation” OpenAI uses bears no resemblance to an actual computer.

“The model uses exact complex arithmetic.” That means it assumes you can store and multiply complex numbers at arbitrary precision. Indeed, the algorithm requires you to multiply complex numbers whose magnitudes grow superpolynomially with n. If you stored these numbers as bits, the memory requirement would effectively be exponential in the input length. It assumes you can multiply such arbitrarily large complex numbers together in a single operation. We do not have computers that can do this. So even if this theorem in main.pdf is “true” (no one knows, and I don’t care), it’s not actually solving the problem we set out to solve when looking for a faster FFT.

For people familiar with theoretical analyses of the FFT, that you need an absurd model of computation to break the FFT speed limit isn’t surprising. In 1973, Jacques Morgenstern proved that you couldn’t get a Fourier transform faster than ½ n log n if you required that complex coefficients used in the computation had bounded magnitude. That should have been the end of the story! But it wasn’t. People said Morgenstern’s restricted coefficient model was too restrictive. Forty years later, Nir Ailon showed that you couldn’t compute an FFT faster than n log n without severe numerical instabilities. This was also too restrictive for some people, I guess.

This new OpenAI result is thus less a mathematical breakthrough and more an oddity of computer scientists being bad at formalizing their design specifications. The “theoretical” definition of a computer is very far removed from the computers we actually build. The “faster” Fourier transform is merely an example where theory gets so unmoored from the original question that an “open problem” becomes nothing more than an academic status puzzle. The solution is like what happens when you set computational bot streams at impossible problems and find them engaging in illegal hacking.

Many of the other “big” results in this OpenAI slopository could be critiqued in the same way. For example, one of those results was a galactic algorithm to multiply two matrices in O(n^2.25) operations. The construction used in the paper does not let you even estimate the constant that hides inside big O.³ It may as well be infinite, computable only with the divine music of the spheres.

Still, if written substantially better, these papers would have made it into the most prestigious publication venues for the theory of computer science (i.e., refereed conference proceedings from STOC or FOCS).⁴ The matrix multiplication paper would have likely won awards. But neither of these has anything to do with computers!

This is because the theory of computer science has a culture that actively discourages running algorithms on a computer. It’s acceptable to write papers in theory conferences that assert an algorithm exists without ever writing it down. The theory of computer science has become a form of mathematics that doesn’t concern itself with computers, and it offers little reward for impact outside those mathematical pursuits. I explained this to a friend who remarked to me that “theory” has the transdisciplinary meaning of “hiding in obscurity of one’s own making.”

AI is really good at automating our worst tendencies. It amplifies the unspoken cultural practices no one likes, but no individual can reasonably deviate from. It exploits the mechanized traditions recalcitrant to collective action. In that vein, AI can now write useless theory papers. But perhaps in the absurdity of the distasteful OpenAI trash dump of proofs, we can all look up and realize together that we should consider doing something else.

1. Kids these days call it cosine similarity.

2. The wikipedia page says it should be credited to Gauss in 1805! Proper credit assignment is a perennial problem in academia.

3. That one shows that for every epsilon greater than 0, there is a constant C so that T(n) <= n^(2.25 +epsilon + C/log(n)). No matter which queries I try, I can’t get an OpenAI model to give a quantitative estimate of C. Whatever!

4. Another bad tradition is computer science choosing its most prestigious venues as hastily reviewed conference proceedings.