Can a proof make a GPU faster?

Contents
  1. A proof, not a recipe
  2. Running the pieces
  3. Searching inside the coefficients
  4. Where the time goes
  5. Don't write it down
  6. Does the model agree?
  7. So how much could it save?
  8. The other optimization
  9. On two more GPUs
  10. What it doesn't say
  11. Checked exactly
  12. What might come next
  13. Stop re-encoding the weights
  14. Score recipes by time, not by products
  15. Back to the question
  16. Thanks
  17. Further reading
  18. 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 n×nn \times n matrices the way you learned at school takes n3n^3 multiplications. On 7 October, OpenAI published a proof that it can be done in about n9/4n^{9/4}. 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 n×nn \times n matrices grows like nωn^{\omega}, and a whole field is about how small the exponent ω\omega can be. The school method gives ω=3\omega = 3. Strassen found the first shortcut in 1969, at ω≈2.807\omega \approx 2.807, and decades of work since had brought the bound down to about 2.371. The new proof says ω≤9/4\omega \le 9/4.

The exponent matters because it compounds. Double the size of both matrices and the work grows by a factor of 2ω2^{\omega}:

23=8against29/4≈4.762^{3} = 8 \qquad\text{against}\qquad 2^{9/4} \approx 4.76

But ω\omega 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 4×24 \times 2 grid of blocks times a 2×62 \times 6 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 AA into a 3×23 \times 2 grid of blocks and BB into a 2×42 \times 4 grid. Each block of the answer CC 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:

The recipe, one product at a time
211332

A

12132131

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.

From the paper's construction to a recipe that wins
StepBlock productsAgainst ordinary GPU multiplication
The paper's tripling construction, simplified2,0002–51× slower
Products that share a factor, merged exactly1,6503.7–42× slower
Exact rewrites, down to the school method's count288At best 31% slower
Strassen's 2 × 2 trick (1969), found inside2521.03× faster; 1.09× with fused additions
A 20-product piece, Hopcroft and Kerr's count (1971)2401.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 2×22 \times 2 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 3×23 \times 2 by 2×42 \times 4 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:

What one layer does to a prompt

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:

GPU time saved and spent per prompt, before fusion
  • Saved by 20 products
  • Encoding inputs
  • Encoding weights
  • Decoding outputs

128K prompt, 130,976 tokens

Saved1.02 s
Spent1.35 s

0.33 s more GPU work than without the recipe

256K prompt, 261,905 tokens

Saved2.02 s
Spent2.70 s

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
PromptSavedEncoding inputsEncoding weightsDecoding outputs
128K1.021 s0.456 s0.219 s0.672 s
256K2.019 s0.914 s0.438 s1.345 s

The products keep their promise. Twenty products where there were 24 should take 20/24=0.83320/24 = 0.833 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:

One MLP layer, before and after fusing the middle

Before

Encode20 productsgate and upDecodeWrite gate and up in fullSiLU(gate) × upWrite the result in fullEncode20 productsdownDecode

Middle stage 0.00 ms

After

Encode20 productsgate and upDecode, SiLU(gate) × up and encodeone kernel, nothing written in full20 productsdownDecode

Middle 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 ff of the time, then even with free extra work, the recipe can save at most

saved  ≤  f (1−2024)  =  f6.\cG{\text{saved}} \;\le\; \cY{f}\,\Bigl(1 - \frac{\cB{20}}{\cB{24}}\Bigr) \;=\; \frac{\cY{f}}{6}.

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:

What the recipe can save, as a dial
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:

Reading the whole prompt on one H100
  1. Native, optimizedcompiled, CUDA graphs

    15.72 s

  2. Native, compiledcompiled, no CUDA graphs

    15.71 s

  3. Recipe, compiledfused MLP, compiled, no CUDA graphs

    15.31 s

Played 5× faster than the H100 ran.

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.

The same recipe on three GPUs
GPUEager recipe vs eager nativeCompiled recipe vs normal servingAt 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 measured2.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

    Philip Kiely. Baseten, 2026. Free online.

    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

    Wen-mei W. Hwu, David B. Kirk & Izzat El Hajj. Morgan Kaufmann, 5th ed., 2026.

    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

    Nicholas J. Higham. SIAM, 2nd ed., 2002.

    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

    Markus Bläser. Theory of Computing Library, Graduate Surveys 5, 2013. Free online.

    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:

On running them: