No. 03 · The observatory
Why published speedups rarely cut your bill
Eight AI-found speedups look big on paper and vanish at real sizes. Real savings come from AI search pointed at your own workloads.
- Status
- Open
- Families
- 107, 109, 120, 121, 124, 130, 138, 142
- Verification
- Lean checks on 4 of 8: 107, 121, 124, 130
- Time to market
- None soon. 120 and 121 are indirect, long horizon.
- Worst exponents
- 150,020 for scheduling, 10^12 for factoring
Why won’t a faster algorithm cut my compute bill?
Keep your compute budget plans. None of these eight results changes them.
Eight families claim faster methods for problems firms pay to compute.
They cover Fourier transforms, large-number and matrix multiplication, and Subset Sum. They also cover matching, string comparison, scheduling and polynomial factoring. Several settle questions open for decades.
Every paper either admits no practical crossover or gives an unusable exponent. Scheduling runs in time with exponent 150,020. Factoring has exponent 10^12.
Your cloud bill pays for libraries like FFTW, GMP, GPU BLAS and OR solvers. Their authors tune them for memory traffic, hardware and real problem sizes. These papers improve a different number.
What does “faster on paper” actually mean?
Ask four questions of any “AI found a faster algorithm” headline before you act.
Theorists measure how cost grows as the input heads to infinity.
“Below n log n” means cost eventually grows more slowly for large inputs. It says nothing about the constant in front. It ignores the size where the new method starts to win. It ignores floating-point hardware too.
A fast algorithm on paper and in a data centre are different products. Four questions sort the two.
- What is the gain at my problem size? Plug a real n into the exponent.
- Does the paper state a crossover size? If it says “no useful crossover”, that settles it.
- Does the model match my hardware? Exact complex arithmetic and Turing machines are not GPUs.
- Is it a small recipe or an asymptotic exponent? Small recipes, like AlphaTensor’s 4x4 matrix product, can enter a library. Exponent bounds almost never do.
How big are the gains at real sizes?
Plug your own problem size into any claimed exponent. Most gains vanish there.
At sizes anyone runs, the savings shrink to almost nothing.
| Family | Claim | Gain at a realistic size |
|---|---|---|
| 130 Fourier transform | Below n log n | Saving factor about 1.0000000000004 |
| 109 Integer multiplication | Below n log n on multitape machines | Saving factor indistinguishable from 1 |
| 107 Matrix multiplication | Exponent at most 9/4, from about 2.371 | 3x at n = 10,000, with zero overhead |
| 138 Subset Sum | 2^0.49n, from 2^0.5n | 2x at n = 100, before overheads |
| 120 Matching | Almost-linear time on general graphs | The paper does not quantify it |
| 121 Edit distance | Almost-linear (1+ε) estimate | Only above “very large” thresholds |
| 124 Three-machine scheduling | Polynomial time | Exponent 150,020 |
| 142 Polynomial factoring | Deterministic polynomial time | Exponent 10^12 |
The papers say so themselves. The Fourier paper gives “no useful crossover estimate.” The scheduling paper states: “No practical running-time claim is made.” The factoring paper calls its exponent “deliberately generous.”
Our deep reads moved 11 of 25 pathway families to no pathway. Huge exponents like these drove many of those moves.
A close read moved 11 of 25 families to no pathway
Label changes after deep reads of 25 pathway families. 18 families changed.
- Before
- After
How to readEach row shows a family's label before and after the close read.
NoteMost moves made labels stricter, never looser.
SourceOur deep reads, research/deep in the atlas repo
What do production libraries do instead?
Track small concrete recipes, like AlphaTensor and AlphaEvolve finds. Those can enter real kernels.
Production code wins on hardware and real sizes.
- FFTW times candidate plans on the actual machine. Its authors found “no longer any clear connection between operation counts and FFT speed.”
- GMP moves from schoolbook to Karatsuba, Toom and FFT at tuned thresholds.
- Production BLAS uses the classical method, sometimes with a few Strassen levels. Strassen can pay off from about 500x500.
- Matching libraries ship blossom-type algorithms. Boost uses Galil’s O(V^3) method.
- Genomics tools need exact alignments. Edlib reports 2.5 to 250x speedups over SeqAn.
- Schedulers use constraint programming, such as OR-Tools CP-SAT.
- NTL factors polynomials with the fast, randomized Cantor–Zassenhaus approach.
The old multiplication record shows the gap. It beat existing methods only above 2^(1729^12) bits. The matrix result rests on an existence argument with no competitive size. Chipmakers still build GPUs around the classical method.
Can we trust these proofs, and who should act?
Read “AI beat a 50-year bound” as news about discovery costs. These eight papers leave products unchanged.
The proofs are mostly solid. The business case for these eight is absent.
Press coverage shows the pattern to watch. OfficeChai’s headline promised “a far faster way to multiply matrices.” Its subtitle conceded it “won’t speed up your chatbot tomorrow.”
- CEOs and CFOs: ask the four questions of any pitch deck that cites these results.
- AI infrastructure and HPC teams: no action. Watch concrete small-size recipes, which can enter kernels.
- Investors: treat these as evidence about the cost of discovery.
- Theory groups: check these families first. Several have Lean proofs, and the techniques may spread.
Published algorithms rarely ship, but the same AI search already pays on private problems. Google’s AlphaEvolve found a Gemini kernel 23% faster and recovers 0.7% of Google’s compute. Klarna doubled its training throughput, by vendor-reported figures.