A look at the math that OpenAI claims computes faster Fourier transforms
argmin.net
argmin.net
PS. I can have this view while simultaneously thinking that Ben is a badass.
It seems like rather than coming up with more "galactic" algorithms, a more useful thing to do might be to come up with a replacement for big-O that's not so exploitable, and to convince theoreticians to play that game instead.
Much of our 'practical' understanding of algorithms also in part came from theoretical advances.
Well that's certainly not the claim. Think about it, that would mean the whole thing is trivially O(1), so why would they be bothering with the rest?
You've missed part in the analysis, or I believe added an assumption they're not making (the constant-time-multiply one, specifically).
This all _is_ almost certainly impractical, but it's for the usual reason of it only being faster for numbers nobody could ever care about. It's theoretically _quite_ interesting though, because hey...what _is_ the fastest you can actually multiply numbers if it's not O(n lg n) as many ~assumed.
You don't need to care. But every so often breakthroughs in theory can be turned into breakthroughs in practice.
> It seems like rather than coming up with more "galactic" algorithms, a more useful thing to do might be to come up with a replacement for big-O that's not so exploitable, and to convince theoreticians to play that game instead.
There's plenty of replacements.
Btw, we already have the optimal (in big-O terms) algorithm for every NP hard problem. We just don't know whether it runs in polynomial time or takes longer. And, yes, that algorithm called Levin's Universal Search is a galactic algorithm. Simplifying a lot, Levin's Universal Search does some clever interleaving to essentially try all possible algorithms in sort-of parallel.
Lo and behold, even the theorists you complain about don't see that 'loophole' as a solution, declare victory and go home. They still keep researching.
"Ok, here's an optimal SAT algorithm (universal search)".
"Nice, but what is the big O complexity of universal search for SAT?".
"Nobody knows".
You're no better off than before if you wanted an answer like "exponential". On the other hand a provably sub-exponential SAT algorithm would be a huge theoretical breakthrough even if "galactic". Same for a proof that P=NP where the exponent in the P-time SAT algorithm was the 5000th busy beaver number, or whatever.
Also empirically, pretty much any provably polynomial algorithm we have found for anything has fairly tame exponents. That's a big part of why 'polynomial' works as a short-hand for 'tractable' that also has nice theoretical properties.
Btw, I don't know whether the tame exponents are in some sense natural, or whether they are a product of how humans find and design algorithms. Perhaps AI will change that.
https://cstheory.stackexchange.com/questions/6660/polynomial...
Doing theory is what gives you a chance to push the envelope to places you can’t even imagine when you’re knee deep in real world problems. And proving something is possible (if impractical) gives an incentive to find a better algorithm and may attract others.
For example see the first graph here: http://klotza.blogspot.com/2016/06/the-fall-of-twin-prime-ga...
Who knows how often really impactful tech is gated behind some non-obvious thing which we never follow up on.
I mean Douglas Engelbart basically bet his entire career behind the Mother of All Demos[0], if it had flopped, modern computing as we know it would be fundamentally different, same with Hiroo Kinoshita and Extreme Ultraviolet Lithography[1][2], we just would have had Moore's law falling off a cliff.
-[0]: [The Mother of All Demos, presented by Douglas Engelbart (1968)](https://www.youtube.com/watch?v=yJDv-zdhzMY)
-[1]: https://spie.org/news/photonics-focus/mayjune-2023/developin...
-[2]: [The Closest Thing We Have to Alien Technology by Veritasium](https://www.youtube.com/watch?v=MiUHjLxm3V0)
Of course, the good-old-fashioned retrograde of Mercury would still be a real puzzler in that timeline, too.
Still, how long would it take someone to work it out empirically enough to have confidence that there wasn’t just some bug somewhere? Maybe they would mothball the GPS project for not working before figuring it out? It’s hard to know, 50 years in an alternate timeline allows for a lot of domino effect
They probably would just assume that it's a bug at first, since "our clock is slightly broken" is far more likely than "we've discovered some cool new physics". But I don't think that that would be an issue here, since even if they thought it was a bug, they'd still try to work around it.
> Maybe they would mothball the GPS project for not working before figuring it out?
I doubt it, since if you think about all the possible issues after sending a complex untested satellite to space, a 40μs clock discrepancy is fairly minor.
... at least in a way less intrusive than https://www.sciencedirect.com/science/article/pii/0021916964...
Like imagine Einstein without access to geometry work. You had others point you to number theory. What about Boole's algebra.
There is a pretty big list of seemingly useless pure math things suddenly finding a very practical use. Sometimes quite a bit later too. And we have no way of knowing beforehand.
And it's fine to not want to do such work yourself. But to dismiss it is, well, not very thoughtful.
The lack of mathematical tools posed no special challenge for any of them. They invented the math they needed to do their work.
You are presenting a false alternative history, where they would not be capable of making great insights without the math coming first. But the causality is often the other way around.
" 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"
I highly doubt this is going to somehow inspire people to make faster algorithms than the mathematical bound...
I have no problem with pure mathematics, my training was in it; but it seems very possible to me that most people funding theoretical computer science (as opposed to pure maths) probably assume the work has a more realistic computational model backing it up.
fun f(x1, x2, x3, ...):
t1 = 3*x1 + 2*x2
t2 = 4*t1 + 5*x3
...
return (some subset of t vars)
The cost model is just the number of additions performed.
Most people getting funding for pure maths probably just lie and/or stretch the truth that it tangentially has some relation to or possible benefit to practical things like cryptography. It doesn't need to actually be true. It just needs to feel true enough.
It is almost completely impossible, and therefore a waste of time, to attempt to gatekeep what other people wish to spend their time and energy on.
There's no single hand holding the pursestrings of research. There's no single path to implementation of theory IRL.
Talking about what "should" be studied is arrogant at best.
The problem is that proving an algorithm is necessarily galactic is incredibly hard. If you knew how to do this, you would become one of the most celebrated complexity theorists of the age. Stanford would be calling.
It's extremely hard to know what mathematics may be useful in the future or not.
If you can do arithmetic on arbitrarily large integers in constant time, you can sort lists in linear time.
Also, consider this: it would have been trivial to get a so-called "better bound" on FFT if such a "cheat" were what people allowed.
To put it another way, the constants inside a big-O are not really constant: they depend on what you assume is a constant-time operation.
The simple idea is that the most basic thing, that is reading the number "n" depends on the number of digits, so that's a log.
But in most algorithms, the "n" refers to the size of a data set. This set is usually stored in some kind of memory, and memory is a physical array of little cells in 3D space. Accessing that cell means travelling through the array, with a time to reach it proportional to its distance, and since capacity increases with the cube of the distance, the time it takes to get the data is proportional to the cube root of n.
The conclusion, to me, is that when complexity gets down to less than a cube root, mathematical abstractions start to break down and you need to consider the actual machine, in particular its cache architecture.
The amount of information at high enough amounts scales with the volume in which it is stored.
Because of the need to be able to reach the cells that store information, the density of information is normally high in 2 directions an low in the 3rd direction.
This is why it is useful to distinguish between the density of information per area, which is determined by things like the size of a magnetic head or the resolution of a photolithographic process, and the density of information per volume, which is determined by the density of information per area and by some kind of layer thickness, which is usually determined by mechanical considerations, e.g. to ensure enough strength for a tape or a disk or an integrated circuit package.
Like I have said, at high enough amounts of information you reach an almost constant information density per volume, like in a rack full with HDDs or in a magnetic tape robotic library.
The amount of information you are talking about is quite a bit lower than the amount I'm talking about. Big O is about limits, so if we're going to bring physical limitations into play to say there's some limit to density, you'd might as well go all the way. It's not limit as n -> 10^18; it's limit as n->infinity. You can't keep adding information and still get cubic scaling.
Ordinary memory is not a list. It's a flat space read in O(1).
In theory. In practice there are multiple levels of cache, and cached reads will be much, much faster than main memory reads.
So if your entire data structure lives in cache and you repeatedly loop through it, it's going to be processed much more quickly than a bigger and more spread-out structure.
There's also paging, and alloc/dealloc to consider, and maybe garbage collection.
By the time you include all of that big-O estimates can become wildly misleading generalisations, unless your n is always >a million or so.
For small n it can be way off.
Sequential reads from adjacent cells will be pipelined, so they can have a throughput that does not depend on the distance in address, but the latency to start another sequential read stream from a different address must depend on the address, for very big memories, e.g. of rack size, where the propagation from a corner of the rack to the other corner takes a long time in comparison with the memory clock.
And in the general case, memory reads do depend on distance. Hence:
> In practice there are multiple levels of cache, and cached reads will be much, much faster than main memory reads.
This is why we have the cache levels in the first place. And the hierarchy continues: L1, L2, RAM, block of spinning rust in the closet, "the cloud" somewhere... There is only so much storage you can fit close to core! More = physically bigger = physically further away.
Sure, within a level might feel like constant time. But that's because the optimal case for that level is slowed down to match the suboptimal cases. The step discontinuities in access time are caused by our inability to engineer a system to manage this tradeoff continuously, not a fundamental law.
If you build a computer with DRAM 10 cm away from the CPU and static RAM 50 cm away, access times for the static RAM will still be much lower than access times for the DRAM.
Why don't we just build all RAM as static? Because it's more expensive per bit, it uses more energy, and it requires a great deal more silicon area.
First, find a sufficiently large base b so that no intermediate calculation exceeds b-1 (one pass over the matrices should do the trick). Then encode each row of the left matrix as a big value A_i = sum_k a_ik * b^k. Encode each column of the the right matrix as B_j = sum_k b_kj * b^(n-k). Compute A and B explicitly (takes O(n^2) integer operations).
Now you extract the answer one element at a time. A_i * B_j has a bunch of terms including sum_k a_ik * b_kj * b^n. All other terms have different powers of b. So do an integer division by b^(n-1), discard the remainder, then take the result mod b, and that gives (a*b)_ij, costing one integer multiplication and two divmod operations per output element. Problem solved. Can I publish in FOCS?
This is, of course, a wild cheat: even with OpenAI’s latest and greatest galactic integer multiplication algorithm, this would be asymptotically slower than the plain high school matrix multiplication algorithm in any remotely realistic model of a computer.
I wonder whether the OpenAI papers contain cheats quite as outrageous as mine :)
(The moral here is that exact math is quite powerful, and exact math in time sublinear in the number of bits of precision is a great way to steal some performance.)
TL;DR - time complexity calculations ignore constant values. So if algorithm A takes 10^10 + n number of iterations to do something, and B does n^2, in theory B is worse, because n < n^2. But in practice, you’d be waiting a very long time for the first iteration of A to even be useful.
So in other words, time complexity gives you how well an algorithm can scale beyond the first iteration. What it doesn’t tell you is if you’d have to wait until the end of the universe to even get started.
Well, I want openAI to focus on these things instead, so it is not a totally unreasonable thing to advocate against their current focus
Yeah? Seems more like an ass.
> theory gets so unmoored from the original question that an “open problem” becomes nothing more than an academic status puzzle...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 thought it is common knowledge (and a common warning from profs to first-year CS students) that computer science has very little to do with computers. The very concept of Turing machines and decidability are mathematical in nature, far removed from how computers these days are run. The undecidability of Wang tiling, for example, is definitely a notable CS result, but it has nothing to do with computers." It is essentially a branch of mathematics. "Computer Science Is Not About Computers, Any More Than Astronomy Is About Telescopes" is a famous quote attributed to Dikstra. There is even famous MIT Open Courseware clip: https://youtu.be/2Op3QLzMgSY?t=30
Also, while I am not an expert, I suspect it is frequently useful to understand how telescopes actually work when you're trying to do astronomy with them.
I don't think the author is "wrong" about the gap between theoretical discussions computation and the actual design constraints of building usable computers. I don't know if that's really a general refutation of proving new things mathematically though. The word "computer" doesn't appear once in the paper OpenAI released, nor do they make any claims specifically about "computer science": https://github.com/openai/math/blob/main/preprints/An-explic...
It's a novel bit of math. Whether or not it means anything in the context of writing software realistically is an interesting conversation, but it doesn't have much bearing on the substance of the result itself. OpenAI is pretty explicit that they view these as research results in the domain of mathematics.
Within computer science, there is a clear mathematical tradition, an engineering tradition, and a social science tradition. There are also plenty of applied computer scientists who use computer science to study topics in other fields.
> 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.
Another way to think about what the author said, imagine you had access to an oracle which could execute arbitrary precision arithmetic expressions in constant time. You could encode a wide range of computations in these and execute impossible algorithms.
Many compsci researchers like the word-ram model of computation to avoid a bunch of extraneous log factors and to apply exactly the intuition you're describing, so that hashtables are actually O(1). That's not a bad habit. It introduces extra log factors in other places though, so I think it's a bit of a wash, and given that it doesn't model the actual register machines we use it feels a bit intellectually dishonest to me.
If Dijkstra was so confident that he was right, he should have started a business and put his money where his mouth was. Hell, any True Believer of Dijkstra's could have done the same in the last 60 years. The fact that they haven't - or they've never succeeded enough for me to know of any - speaks volumes about their effectiveness.
What basic science does is open up new areas and new ideas. And you and I benefit from those foundations.
Dijkstra's proof methods derived from higher math sophistication than most programmers before, and today, have. Like, in one short essay he showed what invariants mean. He made formal theory accessible to mere non-pure-math mortals. You and I today know what invariants are. That's just one example.
This one is just not true. Here it is in 255 lines of well commented Go code: https://github.com/ncruces/sort/blob/v1.0.3/quick/quick.go
It's worse case linear, as used for sorting it beats the Go standard library on the average and worst cases, lagging a bit on the best cases.
In my experience, median-on-ninthers (which is only slightly more complicated than median-of-medians) definitely beats both heap sort and particularly heap select as a fall back for the degenerate case.
And it's not just academic: I've sped up significant stuff at work by switching from sorting to partial sorting and/or selection.
https://en.wikipedia.org/wiki/Median_of_medians
That's pretty much what I posted: median-of-ninthers is an evolution of median-of-medians, that I use to pick a better pivot whenever the pivot supplied by median-of-3 turns out to be bad.
Using it all the time would simply make quicksort/quickselect about twice as slow as it is now, but still faster than heapsort/heapselect. It's a better backstop algorithm than the common introsort/introselect.
There's also no randomisation, the implementation is completely deterministic, and depends exclusively on the input order.
And median-of-ninthers is faster, but median-of-medians is far from terrible, so calling it a galactic algorithm or completely useless in practice is far from the truth, IMO.
In my understanding, the article wants to raise awareness of the potential dynamics of a mathematics/theoretical computer science field governed by the imperfect rules (as they must be) of human sensemaking when the merit system (publication and community standards) are hacked by a machines for which the cost-benefit calculation is very different than for human reseachers for which the rules were invented / sedimented in the first place.
The foregoing discussion above about the emergent utility of now seemingly wasteful theoretical research is as old as any other, but equally predicated on human effort/apability ratios. And AI should invite us to rethink, because to be relevant to humans, its unwieldy results will have to be judged by humans, on their timescales and effort budgets. So we are discussing whether SPAM or HAM before we literally spend our lives as human critics of what ultimately could just be a reward hacking exercise by somebody with access to free tokens.
Nobody really likes the definition of Big-O. It's been unmoored from actual computing performance ever since caches were invented...
edit: by "things equivalent to" I really mean universal register machines, something that operates on integers and not directly on real numbers.
At most you use them for stuff like P vs NP, because Turing machines are 'only' polynomially slower than register machines, so it doesn't matter.
But when you are talking about linear vs quadratic on something resembling real computers, Turing machines are the wrong model.
And exact arithmetic on Q + i*Q (complex numbers but the coordinates are rational numbers, not real numbers) is perfectly feasible.
Of course, in a real computer, long rational numbers take longer to manipulate than short rational numbers. But it's just a model. Similar to how we often assume we can handle arbitrary integers in unit time, but in reality longer integers also take longer to handle on a real computer (or we just refuse to handle them and stick to u64 only.)
> Why? It's just a model.
Either a model can be wrong or it is just a model. If it's the former, it matters whether Turing machines are less wrong than exact complex arithmetic machines.
There is, of course, the very rich field of Numerical Analysis which deals with how we actually represent these things in real life, but for a starting point assuming this sort of thing is par for the course.
Err... doesn't that completely invalidate the big-O analysis!?
I suspected that these Open AI "proofs" of sub-nlogn times were cheating somehow, by sweeping something under a rug. This seems to be it!
This is a common thing in complexity, and I think even the abstract says it is talking about “length n” and not “magnitude n”
Thus, the magnitudes of the numbers being multiplied grow superpolynomially with n (the DFT problem size): because the robot's stuffing its work in there and using it as an oracle.
Did I get that much right? What a cool hack.
That unintentional mockery of a repo is 262million lines of such moves and growing. I don’t think for a second anyone involved has a clue about complexity theory though or they’d just jump to the obvious “O(1) time complexity using an O(2^n) lookup table to cover all possible n bits of input” which is the final end state of Blums speedup theorem.
When you can start doing A₁₂ ⟨M⟩₃† (complete made up nonsense) in your code or just comments without going latex etc it comes more naturally as you wont have to switch context so often.
The same applies to the precision of floating point numbers. What Ben is arguing is happening in this case is the AI has found a way to hide work by moving it into operations that, in one (unrealistic) model of computation, are assumed to cost the same regardless of how large or precise the numbers are. Other models of computation have a more accurate model of the cost of these things, but that was not the model the AI chose to apply in this case.
> 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.
"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."
it's like in my company, where some software developers get frustrated with an LLM that writes poor code. Understanding what you want—and providing the right examples and explanations—is crucial !
Related, another article about proofs that may depend on bad formalizations:
https://news.ycombinator.com/item?id=49994145 - Navier-Stokes Lost in Translation (5 days ago, 237 comments)
AI seems to be very good at getting answers, but not always answers to the correct questions. These remind me of Deep Thought from The Hitchhiker's Guide to the Galaxy, where they got an answer to the ultimate question before actually knowing what the ultimate question is.
I don't think that's an accurate summary of the article you linked. The Lean proof solved the exact problem it was supposed to, it just had minor discrepancies from the writeup of the proof (on the level of saying a theorem requires m+4 derivatives when it actually requires m+5 derivatives). Obviously a problem but not really a bombshell.
Perfectly summarizes the post, which I'd qualify as a rant (the author's main gripe seems to be that it's a galactic algorithm that assumes exact complex multiplication). The theory of computer science literally started with a mathematical model by Alan Turing that has nothing to do with computers (ones that we could physically build, anyway; and even if we brush aside the infinite tape, it's just architecturally completely different from any computers we've ever built for practical purposes).
If you don't like mathematics without direct applicability, you do you, but it's a legitimate mathematical undertaking and cheap way to rant against this AI drop. Do the work and show us if there's a mistake in the argument, missing attribution or whatever actual problems with the paper, but spare us your sour grapes.
> “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.
This in particular is the kind of thing that I'd expect a human would at least pause on and ideally note as a severe caveat to any claimed asymptotic improvement. I don't know off the top of my head if the story is as simple as "you can tuck part of the asymptote into your presumed constant arithmetic", but it sounds kinda plausible?
This is a superfluous remark because the article already said it. He criticizes theoretical computer science for doing it, not just OpenAI.
“breakthrough” is nothing more than an artifact of mathematicians not being able to properly specify the rules of their games in natural language… the theory of computer science has a culture that actively discourages running algorithms on a computer.
Wake me up when someone has understood the proof.
A good one though. A theoretical computer science which researchs "algorithms" which are impossible to run on a real computer has gone astray.
That field being exacerbated by the deluge of OpenAI papers. There is a pretty direct tie-in.
I expect though it will be the theoretical computer scientists that we'll hear the most from in the coming days/years in this new era of LLM papers.
As the argmin suggests Writing computational complexity in Big O isn't great here.
since we generally see the interms of no.of complex additions and no.of Multiplications in the FFT algorithm.