The Turing Machine Is Not a CPU: OpenAI’s n log n Multiplication on AVX2

#

The previous post mined the constants out of OpenAI’s “integer multiplication below n log n” proof. But that proof is a statement about a multitape Turing machine. Real machines are out-of-order x64 cores with 256-bit SIMD, port-limited execution units, and a deep cache hierarchy. I took the paper’s primitives, built them on AVX2, and measured what actually survives the translation — and what doesn’t.

TL;DR

#

• The paper optimises bit operations on a multitape TM, where one “step” moves one bit on one tape. A real CPU step is a 256-bit op on 8 lanes, dispatched from separate ports (ALU / logic / shuffle / multiply / load / store). The objective function is completely different.
• I built the paper’s primitives on AVX2 (Raptor Lake i7-14700K) and measured them:
  • Butterfly (the H₀ layer): 2.3 elements/cycle — the arithmetic half maps perfectly to SIMD.
  • Port cost: vpaddd/vpxor = 1.0x, in-lane shuffle (vpshufb/vpunpckldq) = 1.5x, cross-lane shuffle (vpermd) = 3.0x, multiply (vpmaddwd/vpmuludq) = 1.9x.
  • “Address interchange” = transpose: naive is 17.9x slower than a streaming copy; cache-tiled blocking recovers ~6x. That is the CPU’s version of the paper’s central primitive.
• What survives: the arithmetic — packing (Kronecker → SIMD lanes), reduction to power-of-two butterflies (synthetic/Nussbaumer/Bluestein), and folding permutations into the transform (the paper’s §1.3) which on a CPU is Stockham autosort / DIF∘DIT.
• What does not survive: the rank-deficient linear network (s < Wm) that is the paper’s headline idea. It exists to beat a permutation lower bound on tape. A CPU does a full 8-lane permute in one vpermd, or a gather in one indexed load. The bound evaporates; the apparatus is unnecessary.
• The reframing: on a CPU the relevant n log n is a memory-traffic bound (log n passes over n data), and you beat it with cache tiling — a 6x-ish win, versus the paper’s (log n)^{−2⁻¹⁸²}. Constants and locality dominate by tens of orders of magnitude.

Background: two very different cost models

#

The paper counts bit operations on a fixed multitape Turing machine: one step reads/writes one cell (bit) on each tape and moves each head by one cell. Its whole saving comes from one observation — you can compute linear combinations of data instead of moving it — which lets a fixed network exchange two banks of values with s < W·m sub-operations, beating the permutation lower bound.

        MULTITAPE TURING MACHINE                    x64 CORE  (out-of-order, AVX2)
        ────────────────────────                    ─────────────────────────────
   tape  ···· 0 1 0 1 1 0 1 0 ····            ymm  [ a0 a1 a2 a3 a4 a5 a6 a7 ]  256-bit
               ▲                                      │   = 8 lanes in 1 uop
            head ─── moves 1 cell / step        ports  p0 p1 p5 ┊ p5 ┊ ld ┊ st
   cost = number of CELL-STEPS                cost = max over ports of uops/port

A real core is nothing like that:

• Word-at-a-time, not bit-at-a-time. One vpaddd adds 8 independent 32-bit integers.
• Free addressing. vpermd, vpshufb, vpgatherdd do arbitrary shuffles/gathers in one uop. There is no “tape head” that must walk to a cell.
• Ports, not steps. Throughput is set by how many uops of each class you can retire per cycle (ALU vs shuffle vs multiply vs load/store), not by a uniform “step” cost.
• A deep cache hierarchy. The dominant cost at real sizes is moving bytes between DRAM ↔ L3 ↔ L2 ↔ L1.

So the right question is not “does the paper’s bit-complexity translate” (it can’t — it’s a different machine), but “which of its techniques are still the right techniques, and what is the real bottleneck”.

The mapping: primitive → instruction

#

Let me back these with the actual benchmark. The core of it:

// E1: the H0 butterfly layer, split (SoA) lanes, in L1
__m256i ve = _mm256_load_si256((__m256i*)(e+i));
__m256i vo = _mm256_load_si256((__m256i*)(o+i));
_mm256_store_si256((__m256i*)(e+i), _mm256_srai_epi32(_mm256_add_epi32(ve,vo),1));
_mm256_store_si256((__m256i*)(o+i), _mm256_srai_epi32(_mm256_sub_epi32(ve,vo),1));

E1  H0 butterfly layer (SoA int32, in-L1)
    0.70 ns per 8-lane butterfly-pair   =>  ~11.4 elements/ns  =>  2.3 elems/cycle @ 5 GHz

   split (SoA) layout:   e = [ e0 e1 e2 e3 e4 e5 e6 e7 ]   <- one 256-bit register
                         o = [ o0 o1 o2 o3 o4 o5 o6 o7 ]
                                   │              │
                             vpaddd │        vpsubd │       (1 uop each, 8 lanes)
                                   ▼              ▼
              new e = (e+o)/2  [ . . . . . . . . ]     new o = (e-o)/2 [ . . . . . . . . ]
                                  └────────── 8 butterflies per instruction ──────────┘

That is the whole point of the paper’s “simultaneous butterfly layer”: once you’ve reduced the problem to power-of-two butterfly kernels, the hot loop is pure add/sub/shift and SIMD eats it. The arithmetic half of the paper is free in this sense.

For the instruction classes (inline-asm-guarded so the compiler can’t strength-reduce the loops):

E2  throughput by instruction class (8 independent chains, registers)
    vpaddd       alu                0.0836 ns/op  (1.00x)
    vpand        alu                0.0850 ns/op  (1.02x)
    vpxor        logic              0.0836 ns/op  (1.00x)
    vpunpckldq   shuffle-inlane     0.1254 ns/op  (1.50x)
    vpshufb      shuffle-inlane     0.1254 ns/op  (1.50x)
    vpermd       shuffle-crosslane  0.2509 ns/op  (3.00x)
    vpmaddwd     mul-8x16           0.1569 ns/op  (1.88x)
    vpmuludq     mul-4x32           0.1568 ns/op  (1.87x)

Insight one: the paper’s central trade-off — prefer computation over movement — is directionally correct on a CPU (logic 1.0x, movement 1.5–3.0x, multiply 1.9x), but the ratio is a small constant, not a power-saving. There is one shuffle port and several ALU ports, so shuffles are 1.5–3x the cost. That is the honest CPU version of “the tape head is expensive”.

Insight two: but the reason the paper prefers computation is a tape-specific lower bound. On a tape, an arbitrary permutation costs Ω(N log N) because the head must physically visit cells. On a CPU, vpermd permutes 8 lanes in one uop and a vpgatherdd fetches 8 arbitrary elements in one uop. The permutation lower bound that the paper’s s < Wm network is built to defeat does not exist at register or cache-line granularity.

What does not survive: the address interchange

#

This is the paper’s most distinctive contribution and, on a CPU, it is a solution to a problem that doesn’t exist. The paper spends enormous effort on the fact that on a tape, an address permutation costs O(V u^τ) with τ < 1, and its s < Wm rank-deficit network is what buys τ < 1.

On real hardware, an “address permutation” over a big array is a transpose, and the cost is not a combinatorial network question — it’s cache and TLB behaviour. Let me measure it directly:

E3  'address interchange' on a CPU: 2048x2048 float transpose (16 MiB)
    sequential copy        :   0.906 ms   ( 37.03 GB/s)
    naive transpose        :  16.245 ms   (  2.07 GB/s)  = 17.9x copy
    blocked transpose B=16 :   2.850 ms   ( 11.77 GB/s)  = 3.15x copy
    blocked transpose B=32 :   2.724 ms   ( 12.32 GB/s)  = 3.01x copy
    blocked transpose B=64 :   3.266 ms   ( 10.27 GB/s)  = 3.60x copy

The naive transpose is 17.9x slower than streaming — because each write lands in a different cache line, so every element is a cache miss. Blocking fixes it: 6x faster than naive, down to ~3x a plain copy (the residual is the strided side of the tile). This is the real “fast address interchange”: cache tiling.

   row-major:  B = [ row0 ][ row1 ][ row2 ] ...      each row = N floats = 8 KiB

   naive writes one COLUMN per inner step:
        B[i], B[N+i], B[2N+i], ...   jump of N floats = 8 KiB = NEW line every time
        ┌────┐  ┌────┐  ┌────┐  ┌────┐
        │ ●  │  │ ●  │  │ ●  │  │ ●  │  ...      → 1 cache miss per element   (17.9x)
        └────┘  └────┘  └────┘  └────┘

   blocked (32x32 tile):
        ┌───────────────┐
        │   32 × 32     │   32·32·4 = 4 KiB  → entire tile stays in L1d
        └───────────────┘   → the strided side hits L1, DRAM sees ~1 pass   (3x copy)

Insight three: the paper’s “faster interchange of address chunks” is, physically, cache blocking. And the prize is ~6x, not (log n)^{−2⁻¹⁸²}. The paper’s asymptotic machinery is an artifact of pretending memory is a flat tape with no cache — precisely the abstraction that makes the n log n “barrier” look like a combinatorial wall rather than a locality problem.

What does survive: the arithmetic half

#

Three of the paper’s ideas transfer directly and are the ones practitioners already use:

1. Packing (Kronecker substitution). The paper’s “signed coefficient packing” is exactly the trick behind fast big-integer multiplication: pack many small coefficients into wide words and let one multiply do many. On SIMD it is lane packing — vpmaddwd does 8 16×16 multiplies and adds adjacent pairs per instruction, vpmuludq does 4 32×32→64. Measured at 1.9x an ALU op, i.e. it buys 8 multiplies for ~2 ops. This is why GMP, and every NTT-based post-quantum scheme, packs.

   one ymm, 8 x 16-bit coefficients:   [c0 c1][c2 c3][c4 c5][c6 c7]
                                          x        x        x        x
                                       [k0 k1][k2 k3][k4 k5][k6 k7]
                                          │        vpmaddwd  (1 uop)
                                          ▼
                                       [c0k0+c1k1][c2k2+c3k3] ...   <- 8 mults + 4 adds

2. Reduce to power-of-two butterflies. The paper goes through Gaussian resampling + Bluestein chirps + synthetic (Nussbaumer) transforms specifically so that every transform length becomes a power-of-two butterfly kernel. On a CPU that means you can have one optimised radix-2/4 SIMD kernel and use it for every size, instead of a zoo of special cases. The chirp identity (turn a length-n transform into a length-2^k cyclic convolution) is exactly how you get this.

3. Fold the permutation into the transform. The paper keeps the source and target permutations inside the transform identity so they cancel across the forward transform, the pointwise product, and the inverse (§1.3). On a CPU this has a direct, measurable realisation: Stockham autosort, or the classic DIF-forward / DIT-inverse pairing, which needs no bit-reversal gather at all. The permutation cancels across the pipeline — the same idea, one abstraction level down.

   forward DIF   natural in  ──►  [ bit-reversed spectrum ]
                                          │   pointwise product
                                          │   (both sides already in the SAME order)
   forward DIF   natural in  ──►  [ bit-reversed spectrum ]
                                          ▼
   inverse DIT   bit-rev in  ──►  [ natural result ]
        ⇒  the bit-reversal is never materialised; it cancels across the three transforms

That last one is the most practically valuable transfer, and it’s the paper’s signature move. On a tape you’d remark: “why materialise a permutation when it cancels?” On a CPU: “why materialise a bit-reversal when the transforms cancel it?” Same insight.

The CPU’s real n log n: memory traffic

#

Here is the reframing that matters.

An FFT-based multiplication does log n passes over the data. If the data fits in cache, each pass is cheap. If it doesn’t, each pass is a full DRAM traversal — so the total memory traffic is Θ(n log n) bytes. That is a real n log n on a CPU, and unlike the paper’s bit-operation n log n, it is not a conjecture and not beatable by a cleverer linear network.

You beat this n log n by reducing the number of passes that touch DRAM — i.e. cache blocking / the four-step or six-step FFT, keeping subtiles resident in L1/L2 across multiple butterfly stages. Which is, again, the tiling measurement from E3. The paper and the practitioner are fighting the same log n factor, but the practitioner’s weapon is locality, not rank deficiency.

   FFT-based multiply = log n stages, each streaming the whole array:

      DRAM ════════════════════════════════════════════════════════════
        ▲        ▲          ▲                       ▲
        │ pass1  │ pass2    │   ...                 │  pass log n
      ┌────────┐┌────────┐┌────────┐          ┌────────┐
      │ stage1 ││ stage2 ││ stage3 │   ...    │ stage ℓ│        ℓ = log n
      └────────┘└────────┘└────────┘          └────────┘
        └──────────── every stage sweeps all of DRAM ────────────┘
        ⇒  Θ(n log n) bytes of DRAM traffic          (nothing stays resident)

   cache-blocked:  keep a sub-block in L1/L2 across several stages
        ┌───────┐
        │ tile  │  ◄── stages 1..k run on this tile without leaving cache
        └───────┘      ⇒ DRAM is touched ~once, not log n times

So the honest complexity picture is:

What I’d actually build

#

If the goal is fast multiplication on this machine, the paper’s shape — not its asymptotic claim — is the blueprint:

1. Kronecker-pack limbs into 32- or 64-bit words (vpmaddwd / vpmuludq).
2. Pick a power-of-two transform (an NTT mod a suitable prime for exactness, or a float FFT with splitting for size) so you get one SIMD butterfly kernel.
3. Fold the permutation — Stockham autosort, or DIF-forward + DIT-inverse so the bit-reversal cancels — so you never pay the 17.9x gather.
4. Tile so the working set stays in L1/L2 across stages, so you pay DRAM once, not log n times.

That is essentially what GMP and flint/ntl already do, which is the real tell: the practitioners arrived at the same algorithm the proof’s spirit implies, but for locality reasons, not because anyone needed to crack a bit-operation barrier.

Insights into complexity and algorithmic improvement

#

1. Complexity classes are machine definitions. “Multiplication can be done below n log n” is a statement about multitape Turing machines. Change the machine to a word-RAM-with-cache and both the bound and the winning technique change: the transposition⇔multiplication equivalence that the paper leans on (Harvey–van der Hoeven) simply doesn’t bind when a permutation is one instruction. A headline that sounds like “we broke a fundamental limit” is really “we broke a limit of an abstraction we invented for proofs”.

2. The paper’s cleverest idea is model-specific, and knowing why tells you when to use it. The s < Wm rank deficit exists to make permutations cheaper than the tape’s lower bound requires. On hardware where permutations are cheap, you don’t use it; you use tiling. On hardware where permutations are expensive (DPUs, some FPGAs, cross-node/network shuffles, distributed sorting), the idea might well be live again. The transferable content is “trade movement for computation when movement is the scarce resource”, not “use a subset-intersection network”.

3. Constants and locality beat asymptotics by ~10³⁰. The paper’s improvement is a factor (log n)^{−2⁻¹⁸²}. The gap between a naive transpose and a tiled one is ~6x today, and the gap between a scalar and SIMD implementation is ~8–16x. In practice you optimise the constants (packing, vectorisation, tiling, permutation-folding) and the asymptotic exponent simply doesn’t matter at any size you can reach.

4. The right “n log n” on a CPU is a bandwidth bound, and it’s beaten by locality. If you want a Hopcroft-style “is this optimal?” question for real hardware, ask “is this memory-traffic-optimal?” — and the answer is usually about blocking factors, not about linear algebra over F₂.

5. Packing is the great unifier. Kronecker substitution, SIMD lane packing, and vpmaddwd are the same idea, and it is the one technique that is simultaneously the asymptotic trick (it’s how the paper’s polynomial products work) and the practical workhorse. If you take one thing from the paper’s toolkit to real hardware, take packing.

What I Learned

#

1. Port the primitives, not the theorem. The theorem lives in a model you don’t have. The primitives (H₀ butterfly, packing, chirp-to-power-of-two, permutation cancellation) are the things that survive, and they’re all things you’d rediscover from first principles.
2. Measure the primitive classes before believing a trade-off. “Compute is cheaper than move” is true on a CPU (logic 1.0x vs shuffle 1.5–3.0x) but only by a small constant — the paper’s intuition about which is cheaper transfers; its intuition about how much does not.
3. A permutation lower bound is a tape artifact. vpermd in one uop is the whole rebuttal. Whenever an algorithm’s cleverness comes from beating a movement lower bound, check what “movement” costs on your actual machine before porting the cleverness.
4. The transpose is the tell. The paper’s “fast address interchange” is a transpose, and on a CPU a transpose is a cache problem with a 6x tiling win. The abstraction (flat tape) hid the cache; the fix is locality.
5. Cache blocking is the practical face of the paper’s layout work. The paper agonises over axis-major vs chunk-major ordering; the practitioner agonises over block sizes. It is the same concern, and the practitioner’s version is the one that pays.
6. Never optimise an exponent when a constant will do. A 2⁻¹⁸² exponent improvement is unobservable next to an 8x SIMD width, a 6x tiling factor, and a 10x packing factor. Know which lever your problem is actually on.

Benchmarks: i7-14700K (Raptor Lake, AVX2, no AVX-512), gcc 16.2 -O3 -mavx2 -march=native, best-of-9 wall-clock. Throughput figures for instruction classes are steady-state register-only loops guarded by inline asm. The transpose numbers are DRAM-bound global arrays. Sources for the paper side: OpenAI — Sharing AI progress in mathematics · the preprint · Harvey–van der Hoeven.