AI summaryⓘ
The authors study whether a probabilistic predictor’s many conditional probability answers are self-consistent and if this can be efficiently checked. They design a verification process using interactive proofs to confirm approximate consistency by examining only a few points and consulting a proof oracle that encodes a compatible probability distribution. To support this, they first analyze simpler explicit probabilistic claims and show their consistency checking lies in NP with manageable certificate sizes. Their work lays a theoretical foundation for certifying that predictive models are internally consistent, potentially enabling models to prove their own reliability. This contributes to AI safety by ensuring honesty in probabilistic predictions.
Probabilistic predictorConditional probabilitySelf-consistencyInteractive PCPPolynomial-time verifierProbability circuitProof oracleNP complexityCompleteness-soundness gapAI safety
Authors
Orr Paradise, Oliver Richardson, Yoshua Bengio, Shafi Goldwasser
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 oracle, an encoding of a witnessing probability distribution allegedly consistent with the predictions of (P,Q), which it reads at a few locations while interacting with a single untrusted prover. En route, we must ensure the existence of a sparse witnessing distribution consistent with the model's predictions. To do so, we first consider witness distributions for the consistency of explicit probabilistic claims, rather than claims specified by a predictor: say m claims, each of the form Pr[Y = 1 | X = x] = p, over n Boolean variables. Building on work initiated by Nilsson (Artif. Intell., 1986), we place l_2-approximate probabilistic consistency of explicit claims in NP, with certificates of length O(mn + log B) in the input bit-precision B; we further show how a small additive completeness-soundness gap removes the dependence on B. Together these results provide a complexity-theoretic foundation for certifying the self-consistency of probabilistic predictors. We view our interactive PCP as a first step toward training predictive models to prove their own consistency.