Two Futures for LLMs in Mathematics

This week, we've seen two very different approaches to LLMs for math/theoretical computer science.

In one corner, Anthropic dropped a result to Josh Alman (Columbia) and his former advisor at MIT, Virginia Williams, who are both known for having shown that matrix multiplication could be done slightly more cheaply than previously thought. They did so through very careful counting of how many operations were actually needed in various parts of the existing "laser" method of matrix multiplication, finding that you could shave off a hair here and there.

These two researchers looked at the result from Anthropic and turned it into a fully-fleshed-out paper. The new paper wasn't a matmul result directly; it was a way to use a particular flavor of matrix product to break some bounds that had held so long people were starting to build theory around their hardness, such as 3SUM:

For decades, nobody could figure out how to do 3SUM faster in sub-quadratic time, i.e., something like O(n^{2 - e}) time for some value of e > 0, though we hadn't specifically proved that it needed it. This new paper showed that it doesn't. The work has a very similar feel to some of their previous matrix multiplication work, in the sense that it's also using very careful counting of operations to drop things from O(n²) to O(n^1.9992). That beats O(n²) by only a tiny hair, but that hair is important, because it means our assumptions were wrong, and a bunch of other previously-conjectured hardnesses were reduced along with it using the same technique. This is quite a big result in its subfield.

In the other corner, OpenAI dumped a repository of over 700 PDFs of highly varying quality, some with accompanying Lean proofs, some without, few with clear human review. Some of the claimed results are nearly breathtaking, if they're true. One that jumped out was about matrix multiplication, the area of expertise of the above two researchers. The straightforward way of multiplying matrices is O(n³) for two square n × n matrices: You have n² output cell values, each of which results from the dot product of two size-n inputs (requiring n multiplies). But we've known for a while there's some redundant computation in there; that exponent, which we term omega (ω) is less than three, but it's unknown exactly what it can be. There have been a series of series of some practical and mostly theoretical optimizations that resulted in the previous state-of-the-art upper bound, the somewhat ungainly O(n^2.371177).

OpenAI's PDF claims to reduce ω to 2.25, or 9/4. This would be several things. First, it would be literally the largest reduction we've seen since Schönhage's reduction to 2.522 in 1981; second, the first "large" reduction at all since Coppersmith and Winograd brought things to 2.3755 in 1990. And it would be incredibly satisfying to have something that's a rational number bound of 9/4, not the least because it seems more likely to me to intuitively illustrate some missed structure in the problem.

Allow me to illustrate these papers with a few snippets from the introductory material of the papers. Take a peek and read them, asking if you understand what they're saying. From Alman and Williams:

3SUM: Given n numbers, decide whether three of them sum to 0. This is a classical problem with a long history, and it is central to computational geometry (see [GO95]). Despite many decades of research, the O(n²)-time algorithm taught in algorithms classes has only been sped up by polylogarithmic factors [BDP08, GP18, Cha20].

From OpenAI's pdf dump:

The exponent ω of matrix multiplication over ℂ is the infimum of the real numbers τ such that, for every ε > 0, two n × n matrices can be multiplied in O_ε(n^{τ + ε}) scalar arithmetic operations. The dimension n tends to infinity; the algorithm and its constants may depend on ε.

I mean, true, but this is not how you'd write the first paragraph of a paper written for humans. Contrast that with one of Williams' human-written papers about the same topic:

Multiplication of matrices is a fundamental algebraic primitive with applications throughout computer science and beyond. The study of its algorithmic complexity has been a vibrant area in theoretical computer science and mathematics ever since Strassen’s [Str69] 1969 discovery that the rank of 2 by 2 matrix multiplication is 7 (and not 8), leading to the first truly subcubic, O(n2.81)-time algorithm for multiplying n × n matrices. Fifty-five years later, researchers are still attempting to lower the exponent ω, defined as the smallest real number for which n × n matrices can be multiplied in O(nω+ε) time for all ε > 0.

I can read that! I like it! I want to read more!

And the OpenAI paper is rife with things I find confusing. For example, consider this line:

We write products either by juxtaposition or by ⊗. The zero tensor is 0, the scalar tensor xyz is 1, and the integer m ≥ 0 denotes the direct sum of m copies of 1. Thus mA = A^⊕m.

I think this is intentional use of the notation, but as a human, when you introduce a symbol to me and then use a tiny-font subtly different symbol in the next line that you've never introduced, my head hurts a little. (Note that they introduced circled-times and then used circled-plus in their explanation of the integer-matrix product). And their notation there is confusing overall to me.

This is one example of many, and probably one of the better-confidence ones at that, given that at least this one has a Lean version that proves something (what it proves I am not yet certain—does it prove the 2.25 result? That's going to take some time and expert evaluation). The internet is aflutter with people finding flaws in these papers; three of them have already been withdrawn due to errors that rendered them invalid. The writing in these PDFs is very AI-slop-feeling.

I like to point out that when you write, you're responsible for making sure your audience understands what you've written. There's one of you putting in some time, and potentially thousands of people reading what you've written. Their collective effort to understand you is far higher than the time it takes you to be clear.

And the same thing applies here, but perhaps at 100x magnification: Thousands of people will have to waste time reading this dump and possibly trying to determine if it's correct, and that's really hard work. That time would have been much better spent by having an expert or two review, revise, and present the material cleanly before throwing an unfiltered dump at the world.

We've seen two ways of having your internal advanced AI interact with the world of research, and I know which one I prefer: The one that produced a human-centered result that was informative and interesting to read and where I have much higher confidence I didn't waste my time reading something broken.