Overview of the performance work on the GKR prover: gkr_reduce in the prover and verifier, and crates/gkr. Part of #41.

Benchmark

cargo bench -p prover --bench prover -- gkr, shape (10, 15), M3 Pro (5 performance + 6 efficiency cores).

All numbers are medians. The last two rows were measured on 2026-10-22. For one thread, #55 used single_threaded.patch and the later rows RAYON_NUM_THREADS=1.

Done

• Grand product GKR: core structure #40: Core structure of the grand product GKR.
• GKR integration #49: GKR integrated into the prover and verifier. Removed the deallocations and the deque from the prove layer. Replaced the m-table with a factored claim discharged through the PCS.
• GKR: benchmark and profiling setup + improvements #55: Benchmark and profiling setup: divan bench, profiling example, and single_threaded.patch. Also:
  • transposed the bit table before leaf construction, so the walk is sequential;
  • fixed the exponential over-allocation in SuffixTable::new;
  • made the m-table accumulation branchless;
  • zeroed vectors with bytemuck's zeroed_vec.
• GKR: Second optimisation set #60: Second pass over the round loop:
  • SuffixTable flattened into one preallocated buffer, reused across layers;
  • batched_eval consumes the circuit instead of cloning the leaves;
  • eq_factor inlined in closed form;
  • rayon fold replaced by 2-wide interleaved PMULL chains, with a fused multiply-reduce in mul3_wide;
  • layer sumcheck chunked to reduce variance.

No longer applies

• m-table items (add assign, bit enumerator): GKR integration #49 removed the m-table.
• Branchless leaf construction: the leaves are not built after GKR: lookup tables and bucketing #146.

In progress

• Separate Bit Transpose from Bittable #137: Separates the bit transpose from BitTable. BitTable stays the protocol's view of the witness, and BitMatrix does the bit operations. The witness is read as u128 words. This prepares the lookup tables in GKR: lookup tables and bucketing #146.
• GKR: lookup tables and bucketing #146 (draft, on top of Separate Bit Transpose from Bittable #137): Lookup tables for the bottom three layers.
  • Layers 0–2 (the leaves and the two layers above them) are never built. Their nodes come from 16-entry lookup tables indexed by nibbles of the transposed bits.
  • Round 1 of the sumchecks of layers 0–2 reads the nibbles and the lookup tables directly.
  • The lookup tables, layer 3 and the layers above it are built in parallel.
  • Round 1 of the leaves and of layer 1 splits eq into eq_hi · eq_lo.
  • Covers the old "Sumcheck → LUT" and "lazy levels d, d-1, d-2" items. Partially covers Split Suffix Table optimisation #58, Generate GKR product forests with lazy L2/L4/L8 storage #107, Use bit-selected lookup prefixes in the GKR sumcheck #108 and Parallelize forest construction and select public lazy schedules #116.

To do

Follow-ups to #146

At (10, 15) on all threads, about 25 of the 68 ms run on a single thread. Removing that would bring the bench to about 43 ms.

• Eq tables: EqTables::new takes about 18.5 ms, all of it serial.
  • Don't build the top table, which round 1 of the leaves and of layer 1 never reads (about 7 ms).
  • Parallelise the doubling.
  • Or split the table (Split Suffix Table optimisation #58), which makes both of the above moot.
• Zeroing with calloc runs on one thread (about 4.3 ms): eq_memory, bound_children and layer 3 are fully written before they are read. This is what's left of the old "allocation-free intermediate layers" item.
• Parallel bit transpose in GrandProductCircuit::new (about 2.1 ms).
• Don't split the dense round loops below 2^15 lanes (about 0.45 ms per proof).
• Fuse bind with the next round's sums (Fuse GKR dense folding with the next round message pass #109). round_sums and bind are bound by memory bandwidth.
• Construction (at most about 1 ms): fold layer 4 in layer 3's pass, or don't materialise layer 3 at all.

Ports from the BitZ-PoC (audit of 2026-09-23)

Each issue owns its own scope. Dependencies are in parentheses.

• Split Suffix Table optimisation #58 Split the eq (suffix) table. GKR: lookup tables and bucketing #146 does round 1 of the leaves and of layer 1.
• Generate GKR product forests with lazy L2/L4/L8 storage #107 Lazy L2/L4/L8 storage. GKR: lookup tables and bucketing #146 has one fixed schedule.
• Use bit-selected lookup prefixes in the GKR sumcheck #108 Bit-selected lookup prefixes (Generate GKR product forests with lazy L2/L4/L8 storage #107, Split Suffix Table optimisation #58). GKR: lookup tables and bucketing #146 has one bit-driven round per layer.
• Fuse GKR dense folding with the next round message pass #109 Fuse dense folding with the next round's message (Split Suffix Table optimisation #58)
• Execute two GKR dense rounds from one bivariate grid pass #110 Two dense rounds from one bivariate grid pass (Split Suffix Table optimisation #58, Fuse GKR dense folding with the next round message pass #109)
• Fuse lazy GKR materialization with message and grid accumulation #111 Fuse lazy materialisation with message and grid accumulation (Generate GKR product forests with lazy L2/L4/L8 storage #107, Use bit-selected lookup prefixes in the GKR sumcheck #108, Fuse GKR dense folding with the next round message pass #109, Execute two GKR dense rounds from one bivariate grid pass #110)
• Skip structurally padded all-one GKR trees analytically #112 Skip padded all-one trees analytically (Generate GKR product forests with lazy L2/L4/L8 storage #107, Split Suffix Table optimisation #58)
• Select compact GKR lookup layouts by measured table footprint #113 Choose compact lookup layouts by table footprint (Use bit-selected lookup prefixes in the GKR sumcheck #108)
• Tile shared GKR lookups across trees and preweight fold stashes #114 Tile shared lookups across trees (Use bit-selected lookup prefixes in the GKR sumcheck #108, Select compact GKR lookup layouts by measured table footprint #113)
• Gate AArch64 GKR gather prefetch by measured table footprint #115 AArch64 gather prefetch (Generate GKR product forests with lazy L2/L4/L8 storage #107, Tile shared GKR lookups across trees and preweight fold stashes #114)
• Parallelize forest construction and select public lazy schedules #116 Parallel forest construction and schedule selection (Generate GKR product forests with lazy L2/L4/L8 storage #107). GKR: lookup tables and bucketing #146 builds in parallel but doesn't select a schedule.
• Prepare fixed GKR challenges and add whole-buffer AArch64 kernels #117 Fixed-challenge AArch64 kernels (Fuse GKR dense folding with the next round message pass #109, Execute two GKR dense rounds from one bivariate grid pass #110)
• Add x86 carryless-multiply kernels to the GKR field backend #118 x86 carryless-multiply kernels
• GKR: evaluate a fourth bit-driven leaf round #128 Experiment: a fourth bit-driven leaf round (Generate GKR product forests with lazy L2/L4/L8 storage #107, Use bit-selected lookup prefixes in the GKR sumcheck #108)
• GKR: evaluate a versioned arity-four forest #129 Experiment: an arity-four forest with a versioned proof format (Generate GKR product forests with lazy L2/L4/L8 storage #107, Use bit-selected lookup prefixes in the GKR sumcheck #108, Execute two GKR dense rounds from one bivariate grid pass #110)

Related

• Prover and verifier optimisation: tracking issue #41: prover and verifier optimisation tracker
• Size the rayon pool to the performance cores #48: size the rayon pool to the performance cores