Verifiable ML Without Determinism: Tolerance-Aware Optimistic Verification (arxiv.org)

Researchers introduced NAO (Nondeterminism-Aware Optimistic verification), a protocol and PyTorch-compatible runtime for verifying floating-point neural network inference run on untrusted, heterogeneous hardware without requiring deterministic kernels or trusted hardware. Instead of demanding bitwise equality, NAO defines principled operator-level acceptance regions and accepts outputs within those regions. When results fall outside empirical tolerances, a Merkle-anchored, threshold-guided dispute game recursively bisects the computation graph until a single operator is isolated for adjudication—resolved either by a lightweight IEEE-754 theoretical-bound check or a small honest-majority vote. Unchallenged outputs finalize after a challenge window, enabling an “optimistic” low-cost common case. Technically, NAO combines sound per-operator worst-case IEEE-754 bounds with tight empirical percentile profiles calibrated across accelerators to separate acceptable nondeterminism from evidence of tampering or degradation. The authors implemented NAO as a runtime that instruments graphs and runs unmodified vendor FP32 kernels, plus a contract layer deployed on the Ethereum Holesky testnet. Over CNNs, Transformers and diffusion models on A100/H100/RTX-class GPUs, empirical thresholds were 100–1,000× tighter than theoretical bounds, runtime overhead was negligible (~0.3% on Qwen3-8B), and bound-aware adversarial attacks achieved 0% success. NAO thus offers a scalable, practical path for verifiable ML-as-a-Service in real-world, nondeterministic floating-point environments.