arXiv:2605.22964 · v2

Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization

首次提交 2026-05-22 02:49

版本更新 2026-11-11 03:18

雷达观测 2026-11-13 11:12

摘要

As state-of-the-art neural networks are deployed on reasoning and algorithmic tasks, exactness guarantees become increasingly important. However, high average-case accuracy can still mask incorrect behaviors. This motivates exact certification, which asks for the smallest set of labeled examples needed to certify that a learned hypothesis equals the target. We show that while some hypotheses are easy to certify, even minimal overparametrization can make certification exponentially hard across several hypothesis classes. For threshold circuits of depth $\ge 2$, adding a single extra gate can force certificate sizes exponential in the input dimension. We show an analogous hardness result for log-precision Transformers with only constant architectural overhead. We also characterize approximate certification, showing that allowing only polynomially many mistakes still requires exponentially large certificates, whereas constant relative-error guarantees can hide exponentially many failures. Empirically, we study binary-addition recognition using threshold circuits and Transformers trained with strong supervision. We find that incorrect models can survive extensive checks, with errors that often occur on different inputs and are difficult to detect through uniform sampling.

作者备注：NeurIPS 2026. 31 pages, 2 figures