A look at the math that OpenAI claims computes faster Fourier transforms
TL;DR Highlight
OpenAI's 'faster FFT' wins only under an unrealistic computation model, critic says
Who Should Read
A backend developer deciding how far to trust AI-generated math and algorithm 'breakthrough' claims
Core Mechanics
- FFT cut n² down to 5n log n
- Cooley and Tukey devised the recursive method in 1965.
- It is about 20x faster at n=1,000 and about 10,000x at n=1,000,000.
- The OpenAI algorithm's constants are galactic
- The estimated C is 10^100 when N=10^12.
- The author says even at n=10^100, the classic FFT would be 10^99 times faster.
- Big-O treats all constants as equal
- An O(n) algorithm can hide a constant like 10^80.
- So asymptotically faster does not mean practically faster.
- The computation model differs from real computers
- It assumes complex numbers of arbitrary precision multiplied in a single operation.
- The magnitudes the algorithm multiplies grow superpolynomially with n.
- Under constraints, FFT limits are already proven
- In 1973 Morgenstern proved nothing beats ½ n log n with bounded coefficient magnitudes.
Community Reactions
- Opinion that the post unfairly dismisses theory
- Some said STOC/FOCS aren't about practical algorithms, and huge constants are fine as long as they are constants.
- Others noted median of medians and the 2019 Harvey–van der Hoeven multiplication are also galactic and unused.
- Opinion that the critique has little to do with AI
- Some said the same conclusion follows without AI and the author simply dislikes theoretical CS.
- One commenter said it critiques the whole field rather than the paper.
- Explanation that practical and galactic algorithms are distinguished
- A comment noted TCS separates galactic algorithms from feasible ones like Karatsuba or Strassen that speed up real inputs.
- Comment explaining the mechanism
- One reading is that DFT work is shifted into multiplication, which counts as O(1) in the exact arithmetic model.
- The explanation says the growing numbers act like an oracle that holds the work.
How to Apply
- Check the computation model of AI claims first
- Today, find the cost assumptions (precision, number size) in an algorithm claim and write them down.
- Check whether the numbers being multiplied grow with n.
- Require real benchmarks next to big-O
- Ask for timings over realistic n ranges in performance PRs.
- Don't adopt a claim based on asymptotics alone when hidden constants aren't visible.
- Cross-check AI output with another AI pass
- Given a paper or proof, have an LLM extract assumptions, constants, and implementability.
- Treat the answer as a draft and verify the key assumptions yourself.
Try It
# Paste into Claude or ChatGPT as-is (simplified version of the post's critique method)
Review the algorithm/paper claim below from a practicing developer's perspective.
{{paper summary or claim}}
Answer with these items.
1. The claimed complexity and any constants hidden in the big-O, with their size if present
2. How large n must be for the asymptotic advantage to appear
3. The computation model assumptions (number precision, size of multiplied numbers, exact arithmetic)
4. Whether those assumptions hold on real computers
5. Whether a real implementation or benchmark exists
Don't guess unknown values; write 'not in the paper'.
Next to try: ask the same questions about performance claims of a library you useTerminology
Related Papers
The Judge Can Debias Itself: Awareness and Self-Debiasing for Reliable LLM-as-a-Judge
Warning an LLM judge about bias or letting it self-critique improved 20 of 21 model–bias combinations.
90% of US working hours are spent on tasks not covered well by AI benchmarks
Mapping 29 benchmarks to job tasks shows 90% of US working hours lack good coverage
Postgres 19 delayed after AI reviewers find more bugs than humans can fix
LLM code review surfaced so many bugs that Postgres 19 slipped to November and 8-10 features were reverted
Show HN: Gemini 4 Argon plays StarCraft
LLMs wrote StarCraft bots in one hour; GPT-6 Astra scored highest.
A Plausible Explanation Is Enough to Mislead Multimodal Judges
Adding plausible explanations to fixed answers cut MLLM judges' wrong-answer rejection by 12.7–13.8 points.
Neural networks are clean
Looking at neurons directly shows most have one main job, challenging superposition.