Paper 2026/1390

A Separation Principle for Lookup-Based zkML: Activation-Function Structure Cannot Reduce Per-Lookup Proving Cost

Abstract

In zero-knowledge machine learning (zkML), the dominant cost is generating the proof, not running the model, and it concentrates in the nonlinearities a transformer must evaluate inside the proof system. It is tempting to exploit a nonlinearity's mathematical structure (low degree, parity, or kernel form) to prove it more cheaply. We show this hope is misplaced for the dominant cost: in a Shout-style (one-hot) lookup argument the per-lookup proving work is a function of the access pattern alone, never of the table values, so function structure has zero leverage on it. This is a separation principle; structure can cheapen only a secondary, once-per-proof table term. That table term stays subordinate as models get deeper because the only data-dependent amplifier of per-layer error in a pre-LN transformer is the LayerNorm gain 1/σ: a σ-floor on typical inputs lets a single fixed proving precision suffice at every depth, keeping proof cost near-linear in the number of layers. Whether a fixed precision survives depth is a property of the network, shared by FHE and integer-quantized inference; what is paradigm-specific is the pricing: the leverage of structure inverts between FHE’s multiplicative-depth metric and the lookup address metric. We measure this depth-to-cost scaling on two independent proving systems (EZKL/halo2 and Jolt Atlas), and turn the one dial the separation leaves open, the committed address width, into a bit-exact, upstreamed reduction in prover time.