Bengio and Goldwasser put probabilistic self-consistency in NP, with a verifier that checks exponentially many implied claims in polynomial time

arXiv·medium signalXBlueskyLinkedInCopy link

Submitted August 11 by Orr Paradise, Oliver Richardson, Yoshua Bengio and Shafi Goldwasser, this paper asks whether a predictor answering many conditional-probability queries is self-consistent and whether that can be checked efficiently. Using an interactive PCP framework they construct a protocol where a polynomial-time verifier certifies approximate consistency of predictions specified by circuits, even though those circuits implicitly define exponentially many claims; for explicit claims (m conditional probabilities over n Boolean variables) they place ℓ2-approximate consistency in NP with certificates of length O(mn + log B), and show a small completeness-soundness gap removes dependence on bit-precision B. The stated motivation is AI safety and honest uncertainty quantification — a theoretical foundation for making a model prove its own calibration rather than being sampled for it.