On the Irreducible Overhead of Zero-Knowledge Proofs for Neural Network Inference

Abstract

We establish an information-theoretic lower bound on the prover overhead of any zero-knowledge proof system that verifies arbitrary neural network inference. We prove a minimum multiplicative overhead of 2x for general circuits, rising to 4x for neural networks with ReLU activations due to activation encoding, weight commitment, and layer dependency costs. We further prove that composing ZK with fully homomorphic encryption produces multiplicative overhead blowup, making ZK+FHE verification impractical beyond approximately 10^4 gates. We survey six contemporary proof systems and show their observed overheads are consistent with our bounds. Our results formalize the intuition that free verification of AI computation is impossible and provide concrete bounds for system designers.