ZK-Circuit-Aware NAS: A Cost Model, Benchmark, and Proxy Study for Provable Inference
Choosing a network architecture for zero-knowledge (ZK) proofs of inference needs a circuit-cost estimate that can be checked against the prover, yet NAS work on ZK has relied on untested cost proxies. We study ezkl, a Halo2-based prover, on CIFAR-10 MLPs, CNNs and ResNet-style networks. (1) Cost model. A parametric model of assigned cells, with coefficients fitted on 180 trained, calibrated networks and evaluated on 54 held-out ones, matches ezkl-calibrated logrows exactly for 39 and within one for 51 (Spearman 0.84; cross-validated over all 234 networks: 70% exact, 95% within one). The mismatches have a mechanism: on 72 dumped ezkl settings, logrows is exactly the maximum of four resource requirements (rows, constants, lookup table, range-check table; 72 of 72 sampled networks at logrows 19–23), of which cell count is one. (2) A negative result. Width-matched, ReLU and x² networks have the same calibrated logrows (all 5 skeletons; 45 of 50 matched pairs in the sweep), contradicting the assumption that polynomial activations are cheaper to prove in ezkl; unnormalized x³ + x networks calibrate to a circuit up to 16× larger at equal cell count because their range-check table spans 2²² + 1 values. (3) Benchmark. We release zkml-bench, 474 networks with two training seeds and proxy scores. NEAR predicts accuracy only for ReLU networks (ρ = +0.70) and is indistinguishable from zero on all three polynomial families; a Zen-style score (our variant, not the published Zen-Score protocol) is anti-correlated on polynomial networks; a sign-pattern NASWOT variant is negatively correlated on polynomial networks; ZiCo’s apparent success on x³ + x disappears once failed training runs are removed. Between 39% and 60% of polynomial networks fail to train. (4) Search. With budgets set on ezkl-calibrated circuit size, a tuned joint accuracy-cost proxy almost always reduces to NEAR-only and shows no consistent gain over it, while NEAR-only beats random selection; we withdraw an earlier claim of a joint-proxy gain. Filtering by the cost model’s estimate removes most but not all budget violations. Scope: CIFAR-10, one ezkl version, calibration on trained networks with real inputs, real proofs for seven architectures.