Proving inference · Operator atlas · Memory & read consistency

Memory & read consistency

KV cache, tensor reads — what a read owes you

$$\widetilde{\mathrm{Val}}(r_{\mathrm{addr}}, r_{\mathrm{cycle}}) \;=\; \sum_{j} \mathrm{Inc}(j)\cdot \mathrm{Wa}(j)\cdot \mathrm{Lt}(j, r_{\mathrm{cycle}}) \\[8pt] \mathrm{Wa}(j) = \widetilde{\mathrm{eq}}(r_{\mathrm{addr}},\, \mathrm{td}(j)) \quad\text{(does cycle } j \text{ write this address?)} \\[4pt] \mathrm{Lt}(j, r_{\mathrm{cycle}}) \quad\text{(the "less-than" MLE: only writes before the queried cycle)}$$

The algorithm

If your computational model has tensor buffers that get written and later read — Gather, Select, any data-dependent index — you must prove every read returned the value most recently written to that address.

Why it resists a proof

This is the classical offline memory-checking problem, and it is expensive: naive approaches commit to auxiliary bookkeeping linear in the number of accesses. Whether you owe it at all depends on whether your model of computation has mutable state.

Cryptographic toolbox

  • Twist and Shout: one-hot addressing, structured increments
  • Read/write consistency as a sumcheck DAG
  • Booleanity + Hamming-weight checks on one-hot address polynomials
  • Or: choose a computational model with no mutable state

How each scheme proves it

Sidesteps the obligation entirely. There is no RAM, so there is nothing to check.

To realize KV-caching, the prover has to emulate read/write RAM operations within the SNARK circuit. This complicates the prover's logic and leads to large concrete overheads even when using state-of-the-art protocols for emulating RAM (e.g., via lookup arguments) as they require the prover to commit to additional auxiliary data that scales linearly to the number of reads/writes.

DeepProve · §1.1
  • Proving proceeds layer-by-layer, backwards, GKR-style. Each operator converts a claim about its output into a claim about its input. No addresses, no cycles, no mutable buffers.
  • This is exactly why the certification trick matters: emulating a KV cache would introduce RAM into a model that otherwise has none, "requiring the prover to commit to additional auxiliary data that scales linearly to the number of reads/writes."
  • Embedding — the one genuinely data-dependent read — is reformulated as a sparse one-hot matmul the verifier checks locally, so it needs no memory argument.

Inherited from Jolt's Twist and Shout, adapted from CPU RAM to ONNX tensor buffers. It is Stages 4 and 5 of the proof.

Although ONNX computation removes general-purpose registers and arbitrary RAM access, we still need a notion of consistency of reads and writes over tensor buffers; the lesson from Twist and Shout is that domain-specific access patterns admit much cheaper consistency proofs than prior offline memory checking arguments.

Jolt Atlas · §1.1
  • ONNX removes general-purpose registers and arbitrary RAM, but reads and writes over tensor buffers still need consistency. The lesson taken from Twist and Shout is that domain-specific access patterns admit much cheaper consistency proofs than generic offline memory checking.
  • Stage 4 batches RASumCheck (virtualising $D=8$ per-chunk one-hot address polynomials into groups) with MemoryDag (read-write consistency).
  • Stage 5 evaluates the memory-value polynomial: $\mathrm{Inc}$ is the committed increment, $\mathrm{Wa}$ the write-allocation indicator, and $\mathrm{Lt}$ the less-than MLE selecting only writes before the queried cycle.
  • Supporting checks: BooleanitySumcheck forces $ra_i(k)^2 = ra_i(k)$, and HammingWeightSumcheck forces $\sum_k ra_i(k) = 1$ — together, each address polynomial is genuinely one-hot.
  • This is the substrate under everything. The same Shout read-checking + RAF sumcheck (with the booleanity / hamming-weight / ra-virtualization trio) proves every table lookup in the system — exp, SatClamp, UnsignedLessThan, ReLU, the activation tables. Large tables never materialize: their MLE is prefix-suffix decomposed.
joltworks/src/subprotocols/shout.rs · 308-320
// val (public table MLE) and int (identity / read-back index) are
// recomputed by the verifier; only ra_claim is prover-supplied and
// is constrained by the booleanity + hamming-weight + ra-virtual sumchecks.
let expected = rv_claim + gamma * raf_claim;
The verifier recomputes the public table value and the identity (address) MLE itself; only ra_claim comes from the prover, gated by the one-hot sumchecks.
Audit surface

The one-hot address ra is the only prover-committed object in most lookups; its honesty is entirely the booleanity + hamming-weight + ra-virtualization trio. Those three sumchecks are soundness-critical, not completeness — a gap in any one lets a prover forge a non-one-hot address and read an arbitrary table value. When auditing any operator above, the question reduces to: is its lookup's one-hot trio present and complete?