Can a proof make a GPU faster?
Contents
- A proof, not a recipe
- Running the pieces
- Searching inside the coefficients
- Where the time goes
- Don't write it down
- Does the model agree?
- So how much could it save?
- The other optimization
- On two more GPUs
- What it doesn't say
- Checked exactly
- What might come next
- Stop re-encoding the weights
- Score recipes by time, not by products
- Back to the question
- Thanks
- Further reading
- Papers
Updated 9 October 2026: the compiled-vLLM comparison is in. The recipe now beats normal serving on an H100, though not on a B200. See The other optimization and On two more GPUs.
Multiplying two matrices the way you learned at school takes multiplications. On 7 October, OpenAI published a proof that it can be done in about . Most of the arithmetic in a language model is matrix multiplication. So does the proof make a language model faster?
"Yes, eventually" is wrong, because the proof doesn't contain an algorithm you can run. "No" is wrong too, because something buried in its coefficients did make a 27-billion-parameter model read long prompts faster. This post is about what that something was, and why it was worth about 2%, not 25%.
The setting is one model and one job, mostly on one GPU: reading a long prompt before writing the first word of the reply. Every recipe below was checked exactly before it was timed, and every timing includes all of the work, not just the flattering part.
A proof, not a recipe
The cost of multiplying matrices grows like , and a whole field is about how small the exponent can be. The school method gives . Strassen found the first shortcut in 1969, at , and decades of work since had brought the bound down to about 2.371. The new proof says .
The exponent matters because it compounds. Double the size of both matrices and the work grows by a factor of :
But describes a limit, as the matrices grow without end. The proof shows that a good enough recipe exists at some size. It doesn't say what size, and it doesn't write the recipe down; the paper says as much on its second page. Its last step picks a finite recipe out of an existence argument, the way you can prove that two people in London have exactly the same number of hairs without naming them.
So the first job was to make the pieces run. The paper builds its argument from a few concrete constructions, starting with ordinary polynomial multiplication, and each of those became exact code. Put together, they give finite recipes that can at least be counted. The best one I could count reaches an exponent below 2.6, at a matrix size far too large to store.
Running the pieces
One construction does run at a sensible size. The paper's tripling step, with one ingredient swapped for a smaller exact substitute found by search, computes six matrix products at once, each a grid of blocks times a grid. The school method needs 288 block products for that. The construction needed 2,250, which simplified to 2,000.
It was correct: all 497,664 coefficients of the result checked out exactly. It was also between 2 and 51 times slower than the GPU's own multiplication.
The reason is the shape every fast recipe has. Here is the one this post ends up using. Cut into a grid of blocks and into a grid. Each block of the answer is a sum of two block products, so the school method does 24 of them. A cleverer recipe does 20. Below, each block is a single number, so the whole multiplication fits on screen. Press play, then switch to the school method and compare:
A
B
C
Press Play, or step through with Next. Each block here is a single number; on the GPU it would be a grid of millions.
- Multiplications
- 0 of 20
- Block additions
- 0
- Blocks of C that match the answer
- 0 of 12
Additions count each sum as if it were formed on its own. The coefficients are the certified recipe the GPU runs, on a 3 × 2 by 2 × 4 grid of blocks.
A recipe trades block products for extra work: sums of blocks before the products, and sums of products after. Here, 4 fewer multiplications cost 81 more additions. Watch C halfway through, too: some of its blocks are wrong, even negative, because the recipe's terms only cancel once the last product lands. On paper the products are the expensive part. On a GPU, every one of those sums means reading blocks from memory and writing a new one back, and a modern GPU can multiply far faster than it can move memory. A recipe with 2,000 products, and the sums to feed them, never had a chance.
Searching inside the coefficients
A recipe is a list of coefficients, and there are exact ways to rewrite one list into another that computes the same thing. The best known are Kauers and Moosbauer's flip graphs, from 2022: small moves that keep the product exactly right, and now and then let two products merge into one. Every rewrite below was checked, coefficient by coefficient, before anything was timed.
| Step | Block products | Against ordinary GPU multiplication |
|---|---|---|
| The paper's tripling construction, simplified | 2,000 | 2–51× slower |
| Products that share a factor, merged exactly | 1,650 | 3.7–42× slower |
| Exact rewrites, down to the school method's count | 288 | At best 31% slower |
| Strassen's 2 × 2 trick (1969), found inside | 252 | 1.03× faster; 1.09× with fused additions |
| A 20-product piece, Hopcroft and Kerr's count (1971) | 240 | 1.13–1.17× faster |
Six independent products at once on a laptop GPU, with every addition and product timed. The school method needs 288 block products. Both wins are for the larger double-precision case; single precision never beat the GPU library in this series.
Below the school method's own count of 288, the search found something it could use: Strassen's seven-product trick for blocks, from 1969, hidden in the coefficients. Then it found pieces that use 20 products where the school method uses 24.
Here is the twist. The 20-product piece isn't new. Hopcroft and Kerr published a 20-product recipe for exactly this shape, a by block product, in 1971, and the search had found its way back to their count. Every speedup in the rest of this post comes from that piece. The 9/4 proof was where the search started, not where the speed came from.
Two more things made it work. Every coefficient in the 240-product table is 0, 1 or −1, so the extra work is pure addition and subtraction, with no scaling. And the wins were in double precision on a laptop GPU, which does double-precision arithmetic slowly. When multiplying is slow, saving multiplications pays. In single precision the library won every time.
Where the time goes
A laptop's double-precision arithmetic isn't what language models run on. The real test was Qwen3.8-27B, served with vLLM (2023) on one H100, in bfloat16, the 16-bit format models actually use. Before a model writes a word, it reads the whole prompt, pushing every token through all 64 of its layers. Here is what one layer does:
5,120 numbers in every row
Each token of the prompt becomes a row of 5,120 numbers. A 128K-token prompt is a table of 130,976 rows like these, read 32,768 rows at a time.
The MLP in each layer is the SwiGLU layer (Shazeer, 2020), and its two matrix products are where the recipe goes. I replaced both.
The first attempt took 31.4 seconds to read a 128K-token prompt, against 17.8 seconds without the recipe. A round of engineering on the kernels and their memory brought that down to 2.2% slower at 128K tokens, and 0.8% slower at 256K. Still slower. A profile of the GPU's time says why:
- Saved by 20 products
- Encoding inputs
- Encoding weights
- Decoding outputs
128K prompt, 130,976 tokens
0.33 s more GPU work than without the recipe
256K prompt, 261,905 tokens
0.68 s more GPU work than without the recipe
Qwen3.8-27B on one H100, every MLP layer using the recipe, summed over the whole prompt. The products deliver almost exactly the saving the theory promises; the additions around them cost about a third more than that.
Show data
| Prompt | Saved | Encoding inputs | Encoding weights | Decoding outputs |
|---|---|---|---|---|
| 128K | 1.021 s | 0.456 s | 0.219 s | 0.672 s |
| 256K | 2.019 s | 0.914 s | 0.438 s | 1.345 s |
The products keep their promise. Twenty products where there were 24 should take of the time, and they take 0.829 and 0.831 of it. It's the extra work around them that costs a third more than they save.
Don't write it down
The biggest item in that ledger is decoding outputs, and the MLP makes it worse than it needs to be. Without fusion, the gate and up results are decoded and written to memory in full, read back for the activation, written out again, then read a third time to be encoded for the second product. At 32K tokens per chunk, those two intermediate matrices take 3.42 GB.
The fix is to never write them. One GPU kernel reads the products, decodes them, applies the activation and encodes the result for the second product, in a single pass. Run one layer and watch the middle:
Before
Encode20 productsgate and upDecodeWrite gate and up in fullSiLU(gate) × upWrite the result in fullEncode20 productsdownDecodeMiddle stage 0.00 ms
After
Encode20 productsgate and upDecode, SiLU(gate) × up and encodeone kernel, nothing written in full20 productsdownDecodeMiddle stage 0.00 ms
With 32K tokens per chunk, the middle stage falls from 4.43 to 2.08 ms, and 3.42 GB of intermediate matrices are never allocated. The outputs match the unfused path bit for bit. The run plays the middle at its measured speed; only its total was measured, so the five unfused steps share it equally, and the steps around it take the same time in both.
The kernel has to round exactly as the separate steps do, including the two roundings to bfloat16 inside vLLM's activation, and it does: its outputs match the unfused path bit for bit. On its own, the complete MLP with this kernel now beats PyTorch's by 3.1% with 16K tokens per chunk and 5.3% with 32K. It still loses by 16% with 4K, where the products are small and the extra work weighs more.
Does the model agree?
In the real server, with both sides running eager, the fused recipe reads a 128K-token prompt in 16.9 seconds instead of 17.3, and a 256K-token prompt in 43.9 seconds instead of 44.7. That's 2.4% and 1.8% less time, and all twelve paired comparisons favoured the recipe. A second session, in the race further down, reproduced it at 2.4% and 1.9%.
So the gain is real. Is it big?
So how much could it save?
Back to the guess. A sixth fewer products doesn't make the whole prompt a sixth faster, because the products are only part of the work. If the MLP products take a share of the time, then even with free extra work, the recipe can save at most
That's Amdahl's law, from 1967: speeding up part of a job can only save that part's share of the time. And the share shrinks as prompts grow, because attention compares every token with every earlier one. The MLP products take 35% of the GPU's time at 128K tokens and 27% at 256K, so the ceiling is 5.8% and 4.5%.
So the answer to the opening question is at most 4.5% for a 256K-token prompt, not a sixth, and that's with free additions. The fused recipe gets about 40% of the way there at both lengths.
Turn the dials yourself. The presets are the measured runs, before and after fusion:
- Most it could save
- 5.8%
- Given back
- 3.5%
- Prompt time saved
- 2.4%
This is the measured 128K, fused run: the recipe saved 2.4% of the prompt's time. The dashed mark is where the bar would end without the recipe.
The other optimization
There's a catch in "both sides running eager". vLLM doesn't normally run eager. It compiles the model with PyTorch's compiler (2023) and replays the GPU work as CUDA graphs, which removes much of the overhead of launching thousands of small kernels. My first version of the recipe opted out of both, and normal serving's optimizations are worth 10.1% at 128K tokens and 7.6% at 256K: more than the recipe could save even with free extra work. Run eager, the recipe lost to normal serving by 8.5% and 6.1%.
So I moved the recipe inside the compiled engine. It still runs without CUDA graphs, but for reading a long prompt they barely matter: compiled native without them is within 0.05% of normal serving. With the compiler on both sides, the recipe reads a 128K-token prompt in 15.3 seconds instead of normal serving's 15.7, and a 256K-token prompt in 40.8 seconds instead of 41.6. That's 2.6% and 1.8% less time, and every recipe sample beat every native sample. Race them, or switch to the eager session to see the earlier loss:
Native, optimizedcompiled, CUDA graphs
15.72 s
Native, compiledcompiled, no CUDA graphs
15.71 s
Recipe, compiledfused MLP, compiled, no CUDA graphs
15.31 s
With the compiler on both sides, the recipe saves 2.6% against normal serving and 2.5% against compiled native without CUDA graphs. Normal serving ran before and after the other arms; its two medians differ by under 0.25%.
The eager loss was never the recipe's fault. Eager execution itself costs about 1.8 seconds at 128K tokens, and the recipe saves about 0.4 seconds either way.
On two more GPUs
If the extra work really is memory traffic, that's testable. An H200 has the same compute as the H100 but 43% more memory bandwidth, so the recipe should gain more there. I wrote that prediction down before running it, and it held, modestly: the eager gain grew from 2.4% and 1.9% to 2.8% and 2.2%. The profile shows why. The products saved the same time as on the H100, while the extra work got 12% cheaper. Not 43% cheaper, so memory speed is only part of the story.
A B200 is a newer generation, with matrix units more than twice as fast. There the recipe lost: 2.3% and 2.1% slower than normal serving, compiled on both sides. Faster matrix units shrink the time its skipped products would have taken to between a half and two-thirds of the H100's, while its extra work shrinks by only 10 to 17%. The trick that pays on a Hopper GPU costs time on a Blackwell one.
| GPU | Eager recipe vs eager native | Compiled recipe vs normal serving | At 256K: products save, extra work costs |
|---|---|---|---|
| H100 | +2.4% / +1.9% | +2.6% / +1.8% | 2.02 s, 2.70 s |
| H200 | +2.8% / +2.2% | not measured | 2.04 s, 2.38 s |
| B200 | −0.4% / −0.2% | −2.3% / −2.1% | 1.27 s, 2.43 s |
Latency change at 128K / 256K tokens; plus means the recipe is faster. One session per GPU; the compiled comparison on the H200 wasn't made. The last column is profiled GPU time for one 256K-token prompt, before fusion.
What it doesn't say
- It isn't 9/4. No practical algorithm came out of the proof. The speed comes from tricks that Strassen (1969) and Hopcroft and Kerr (1971) published first.
- It isn't free. In bfloat16, the recipe's MLP output is about four times further from the exact answer than the library's: 1.52% relative error against 0.39%. Whether that changes what the model says hasn't been tested. Every reply was "OK", which isn't evidence. Peak memory also rose, from 77.3 GB to 82.6 GB.
- It isn't a serving result. One request at a time on one GPU, synthetic prompts, and only the reading of the prompt; writing the reply wasn't measured. Each GPU was measured in a single session.
- It doesn't hold on every GPU. On a B200 the recipe is slower than normal serving.
- It's only checked at these shapes: one model's widths, prompts of 128K and 256K tokens, and chunks of up to 32K.
Checked exactly
Every recipe in this post was checked before it was timed, with exact integer arithmetic rather than floating point:
- Each recipe reproduces the school method coefficient by coefficient, including every zero that keeps independent products from mixing.
- Integer inputs come out with zero error.
- The fused kernel matches the unfused path, and the compiled MLP matches the eager one, bit for bit.
The checks also caught a bad run. In one compiled run, the recipe's server quietly reused the native server's saved compiled code, so the recipe never ran at all. The run stopped because the recipe's hook never reported in; now every server compiles from scratch.
Not checked: the 9/4 theorem itself. OpenAI's proof is written in the Lean theorem prover, and I read the parts that pick the finite recipe, but I didn't build it. At several steps I also asked an AI model for advice. Its suggestions were checked like everything else, and the wrong ones are kept next to their corrections.
What might come next
Stop re-encoding the weights
The model's weights don't change while it reads a prompt, yet every call encodes them again: 0.22 seconds of GPU time per 128K-token prompt and 0.44 per 256K. Encoding them once would save that time. But encoded weights take more memory than the originals, and a 27B model on one 80 GB card doesn't have much to spare.
Score recipes by time, not by products
The search counted products. A search that timed each candidate on the GPU, as AlphaTensor did in 2022, might prefer a recipe with more products and fewer additions.
Back to the question
Can a proof make a GPU faster? This one hasn't, yet. Searching its coefficients turned up a trick first published in 1971, and on an H100 it made a 27-billion-parameter model read long prompts about 2% faster than normal serving. On a B200 it made it slower. The multiplications were never the hard part. Moving the numbers around them was.
Thanks
Every cloud measurement in this post, on the H100, H200 and B200, ran on Modal. Thank you to Modal for the GPUs; everything else ran on one laptop.
The inference side of this post owes a lot to Philip Kiely's Inference Engineering (Baseten, 2026), a guide to the hardware, software and techniques it takes to run models in production. It's first on the shelf below, and free to read online.
Further reading
Four books, from the general to the technical:
- Inference Engineering
The hardware, software and techniques it takes to run a model in production: the world every measurement in this post lives in. The inference side of this post leans on it.
- Programming Massively Parallel Processors
How a GPU actually runs a matrix product: tiles, shared memory, and why moving data costs more than the arithmetic. The background to every timing in this post.
- Accuracy and Stability of Numerical Algorithms
Its chapter on fast matrix multiplication explains why recipes like Strassen's lose accuracy: the price this post's recipe pays too.
- Fast Matrix Multiplication
Sixty pages from Strassen's trick to the exponent ω and the methods behind its bounds. Free to read from the publisher.
Papers
On the recipes:
- Strassen, Gaussian elimination is not optimal, Numerische Mathematik 13 (1969). The first recipe with fewer than multiplications: seven products for a block product instead of eight.
- Hopcroft & Kerr, On minimizing the number of multiplications necessary for matrix multiplication, SIAM Journal on Applied Mathematics 20 (1971). The first 20-product recipe for the block shape used in this post.
- Kauers & Moosbauer, Flip Graphs for Matrix Multiplication, ISSAC (2023). The exact rewriting moves behind the search.
- Fawzi et al., Discovering faster matrix multiplication algorithms with reinforcement learning, Nature 610 (2022). AlphaTensor, which searched for recipes, including some tuned to the measured speed of particular hardware.
- OpenAI, An Upper Bound of 9/4 for the Matrix Multiplication Exponent (2026). The proof this post started from.
On running them:
- Amdahl, Validity of the single processor approach to achieving large scale computing capabilities, AFIPS Spring Joint Computer Conference (1967). The ceiling on what speeding up part of a job can save.
- Higham, Exploiting fast matrix multiplication within the level 3 BLAS, ACM Transactions on Mathematical Software 16 (1990). Strassen's method inside a standard linear-algebra library, and what it costs in accuracy.
- Benson & Ballard, A Framework for Practical Parallel Fast Matrix Multiplication, PPoPP (2015). Generated code for dozens of rectangular recipes like Hopcroft and Kerr's, measured on CPUs.
- Huang, Smith, Henry & van de Geijn, Strassen's Algorithm Reloaded, SC16 (2016). Folding Strassen's additions into the multiplication kernel itself, a close cousin of the fused kernel here.
- Shazeer, GLU Variants Improve Transformer (2020). The gated MLP layer the recipe replaces.
- Kwon et al., Efficient Memory Management for Large Language Model Serving with PagedAttention, SOSP (2023). The paper behind vLLM, the serving engine used here.