Proving inference · Operator atlas · The memory wall

The memory wall

scale out, or scale down

$$\textbf{DeepProve — scale out.}\quad \text{partition the operator DAG into chunks of consecutive layers} \\[3pt] \text{verifier checks } \mathrm{chunk}_i.\mathrm{out\_commit} = \mathrm{chunk}_{i+1}.\mathrm{in\_commit} \\[10pt] \textbf{Jolt Atlas — scale down.}\quad \tilde T(x) = \sum_i \prod_{j=1}^{C} s_{i,j}\big(x^{(j)}\big) \\[3pt] \text{peak memory } O(|T|) \rightarrow O\big(|T|^{1/C}\big), \qquad \text{time } O(C|T|)$$

The algorithm

Not an optimisation — a necessity. DeepProve needs 147 GB of RAM for Gemma 3 at sequence length 512, and estimates that a 3B-parameter model would need over a terabyte.

Why it resists a proof

Many SNARKs materialise large portions of the witness and intermediate polynomials in memory to commit and open them. Memory utilisation, not prover time, is what actually stops you.

Cryptographic toolbox

  • Horizontal DAG partitioning; commit to chunk boundaries
  • Single-round aggregation for WAN tolerance
  • Prefix-suffix table decomposition ⇒ streaming prover
  • Space-efficient or disk-based SNARKs (open)

How each scheme proves it

Fit on one GPU. tlookup's memory efficiency keeps a 13B proof under 23 GB — a V100 or A100. No distribution.

  • Peak memory ≤ 23.1 GB for LLaMa-2 13B. Committing to the model takes up to ~20 min; the per-prompt proof is 1–15 min.
  • About 50× faster than zkML on 10× larger models at identical hardware, because tlookup and zkAttn avoid the lookup-table blowup. This is the same memory-vs-throughput split as Jolt Atlas (scale down) against DeepProve (scale out).
LLaMa-2 13B: prover 803 s, proof 188 kB, verify 3.95 s, memory 23.1 GB (GPU).

Scale out. Partition the DAG horizontally, prove chunks in parallel, concatenate. One round of communication.

This makes memory utilization the main bottleneck of our prover (e.g., proving models with more than 3 billion parameters, such as GPT-J, would likely require over a terabyte of RAM). We leave as an interesting future direction efficiently reducing total memory utilization using space-efficient or disk-based SNARKs.

DeepProve · §5
  • All three proving steps — witness commitment, PIOP, PCS opening — work on a subgraph with little added cost and no dependence on the underlying cryptography.
  • Committing to each chunk's inputs and outputs makes chunks independent, so they prove simultaneously. The coordinator streams each subtrace to its worker as soon as it is ready, overlapping proving with inference.
  • The verifier must check that the partition is consistent with the real model DAG (no dropped nodes) and that each chunk's input commitment matches the previous chunk's output commitment.
  • 1855 TPM with 17 machines (10.6× speedup); 1079 TPM with 9. Total communication equals the proof size (43–54 MB). At 100 Mb/s WAN, only a 2% slowdown.
  • The authors name space-efficient and disk-based SNARKs as the open direction for attacking memory directly — which is precisely what Jolt Atlas does.
96 GB (BaseFold) / 147 GB (HyperKZG) single-machine RAM at Gemma 3, seq 512.

Scale down. Decompose the lookup tables so the prover streams, and the whole thing fits on a laptop.

This enables streaming provers that trade time (typically $O(C)$ streaming passes) for space, reducing peak memory from $O(|T|)$ to roughly $O(|T|^{1/C})$ while incurring total prover time on the order of $O(C|T|)$ field operations. This directly motivates Jolt Atlas's focus on "streaming" proving for large models on constrained devices.

Jolt Atlas · §1.1

Unlike Jolt, our computational model doesn't require us to commit to the full witness at once, but rather to the inner values of tensors. Dory, the polynomial commitment scheme used in Jolt, is only justified for witnesses over $2^{26}$ elements. We therefore replace it with HyperKZG.

Jolt Atlas · §1.2

On-Chain Verification: Deploying proofs on Ethereum is challenging due to HyperKZG's $\mathbb{G}_T$ operations. Replacing HyperKZG with a lattice-based PCS may also mitigate this limitation.

Jolt Atlas · §7
  • Prefix-suffix decomposition lets a large table's MLE factor into components over smaller domains, enabling a streaming prover: peak memory falls from $O(|T|)$ to roughly $O(|T|^{1/C})$ at a cost of $O(C|T|)$ field operations, for tunable $C$.
  • They also replace Jolt's Dory PCS with HyperKZG, arguing Dory "is only justified for witnesses over $2^{26}$ elements", and that the tensor model doesn't require committing to the full witness at once — only to the inner values of tensors. Trading a transparent setup for pairing-based succinct openings suited to on-chain verification.
  • Result: GPT-2 (125M) proves end-to-end in ~38 s on a MacBook Pro M3 with 16 GB RAM. nanoGPT (~0.25M) in 14 s, versus EZKL's 237 s — a ~17× speedup before counting EZKL's >400 s of key generation.
  • Cost of the pairing choice: they flag that on-chain Ethereum verification is challenging because of HyperKZG's $\mathbb{G}_T$ operations, and float lattice-based PCS (Hachi, ABBA) as future work for post-quantum security and on-chain viability.
  • The streaming claim is visible in the code's shape: the prefix-suffix Shout machinery lets a large table's read-checking run over small prefix/suffix tables refreshed every couple of sumcheck rounds, so the prover never materializes the full table — which is exactly why the whole GPT-2 proof fits in 16 GB on a laptop.
GPT-2 (125M) breakdown: sumcheck ~16 s, witness gen ~7.5 s, reduction opening ~7 s, commitment ~3.5 s, HyperKZG ~3 s.

The opposite trade from every SNARK here: the sVOLE prover streams, so memory is small and the transcript is enormous. Scale is bounded by the network, not by RAM.

  • The paper's stated motivation for choosing sVOLE over a zk-SNARK is precisely the memory wall: it argues a state-of-the-art SNARK prover's memory scales with the statement, putting a billion-constraint statement far out of reach of commodity hardware.
  • Result: ResNet-101 proves inside a fraction of a 32 GB machine -- no cluster, no distributed prover, no partitioning of the operator DAG. DeepProve needs to scale out to 17 machines; Jolt Atlas needs prefix-suffix streaming to scale down. Mystique needs neither, because the witness was never materialised as a committed polynomial.
  • The cost simply moves to the wire. Where DeepProve ships a proof measured in tens of megabytes and Jolt Atlas ships one measured in kilobytes, Mystique's ResNet-101 interaction exchanges gigabytes. Prover memory and transcript size are the two ends of the same seesaw, and this is the far end.
ResNet-101 uses about 12 GB of the 32 GB machine; the interaction exchanges 0.99-1.98 GB depending on whether the model is public or private.