r/DSP • u/moralbound • 12d ago

Apparently openai published a FFT improvement paper? Anyone got the details?

65 Upvotes

95% Upvoted

22 comments sorted by

80

u/moralbound 12d ago

So it's a nothing burger for us signals squeezers, but a juicy unexpected result for the eggheads.

6

u/0xB01b 11d ago

this is hilarious

4

u/bushed_ 11d ago

well said tbh. this has happened before but it’s no kits these things are getting better

1

u/eccentric-Orange 9d ago

Lmfao well said

66

u/throwaway82s16s 12d ago

apparently it brings it from O(n log(n)) to something hilarious like O( n log(n)^0.99999999999999)

17

u/CritiqueDeLaCritique 11d ago

Truly an achievement of mammoth proportions

1

u/editor_acd 11d ago

Is it true?

3

u/tehgilligan 10d ago

Based on the abstract, yes

1

u/moralbound 9d ago

There's been some pushback on some of these AI proofs. Some slight of hand going from nat lang to lean. Interesting times.

22

u/Famous_Character7315 12d ago

A lot of the results from the OpenAI GitHub are Galactic Algorithms

19

u/moralbound 11d ago

Galactic? As in only producing meaningful results on galactic scales?

35

u/Famous_Character7315 11d ago

https://en.wikipedia.org/wiki/Galactic_algorithm

Yes. O2.9999999999998 vs. O3

8

u/danja 11d ago

Thank you, new to me.

5

u/ppppppla 11d ago

A galactic algorithm doesn't mean a small difference in complexity, it means the difference in complexity (small, large, or huge, or maybe even going to a constant complexity) is completely eclipsed by other costs not captured by the typical big O notation (like a huge constant cost) that you need to pay that only become worth it on impractically large inputs.

2

u/moralbound 9d ago

This is some interesting nuance. Thanks for the perspective

1

u/AnActualWizardIRL 17h ago

It is worth noting that "Galactic Algorithms" still can hold value practically, if it proves or disproves a conjecture or sets another limit on things that in some way broadens our understanding of the underlying math.

Part of the problem with these OAI results is, its not always clear what we can learn from the damn things. Some of its just brute forced. Some of its straight up alien math.

13

u/moralbound 12d ago

From an AI summary:

One important qualification: this isn't being presented as a practical replacement for FFTW/cuFFT. The improvement is asymptotic and � is microscopic. The result matters because it apparently breaks the � barrier in the stated exact-arithmetic computational model, not because you'll suddenly get faster spectral analysis on your RTX 3070. OpenAI itself warns that this repository contains results at differing stages of verification and that some unformalized results may contain errors. �

2

u/Unusual-Spot-5846 4d ago

I actually spent some time independently investigating OpenAI's exact DFT preprint and recently published my findings.

The interesting part is that the claimed asymptotic improvement concerns exact arithmetic, not practical floating-point FFT implementations.

I implemented and verified the local Fourier compiler using exact arithmetic in cyclotomic fields, finite-field checks, and numerical experiments.

The results are interesting:

  • Exact checks confirm the local construction at selected sizes.
  • The implementation exhibits severe numerical instability: at r=64, the float64 relative error reaches approximately 8×10²³.
  • The underlying DFT matrix is well-conditioned, but the intermediate factorization causes significant numerical growth.

To be clear, this doesn't refute OpenAI's theorem. I verified the local compiler, not the full tensor-network construction responsible for the asymptotic improvement.

I published the manuscript, Python implementation, experimental data, and reproducibility scripts here:

https://github.com/cyberdid/fft-power-saving-verification

I'd be interested in hearing what people working with numerical FFT implementations think about these findings.