Paper Overview
- Field: Machine Learning
- Authors: Orr Paradise, Oliver Richardson, Yoshua Bengio, Shafi Goldwasser
- Published: 2026-08-11
- arXiv: 2608.11181
Summary
When a probabilistic predictor answers many conditional-probability queries, are its answers self-consistent, and can this be verified in polynomial time? This problem is of interest for AI safety, where safety is derived from honesty about probabilistic predictions of unwanted outcomes potentially caused by an AI action.
The authors construct an interactive PCP as follows. Let a predictive model be specified by a probability circuit P and a circuit Q which outputs confidence in predictions. Together, P and Q implicitly specify exponentially many probabilistic claims. They show a protocol in which a polynomial-time verifier can verify the approximate consistency of (P,Q). The verifier is given the pair of circuits (P,Q), which it evaluates at only a few points; alongside them it is given a proof oracle — an encoding of a witness probability distribution allegedly consistent with (P,Q)'s predictions — and reads only a few locations while interacting with a single untrusted prover.
Along the way, one must ensure that a sparse witness distribution consistent with the model's predictions exists. To this end, the paper first considers witness distributions for consistency of explicit probabilistic claims: given m claims, each of the form Pr[Y = 1 | X = x] = p, over n Boolean variables. Building on work pioneered by Nilsson (Artif. Intell., 1986), the authors place l2-approximate consistency of explicit claims in NP with certificate length O(mn + log B), where B is the input bit-precision; they further show how to remove the dependence on B via a small additive completeness-soundness gap.
These results provide a complexity-theoretic foundation for proving self-consistency of probabilistic predictors. The authors view the interactive PCP as a first step toward training predictive models to prove their own self-consistency.
Original Abstract
When a probabilistic predictor answers many conditional-probability queries, are its answers self-consistent, and can this be verified in polynomial time? This problem is of interest for AI safety, where safety is derived from honesty about probabilistic predictions of unwanted outcomes potentially caused by an AI action. We construct an interactive PCP as follows. Let a predictive model be specified by a probability circuit P and a circuit Q which outputs confidence in predictions. Together, P and Q implicitly specify exponentially many probabilistic claims. We show a protocol in which a polynomial-time verifier can verify the approximate consistency of (P,Q). The verifier is given the pair of circuits (P,Q), which it evaluates at only a few points; alongside them it is given a proof orac...
---
*Auto-collected on 2026-08-13*