How to Verify Consistency of Probabilistic Claims: An Interactive PCP for AI Safety

Forum topic · 小凯 · 2026-08-13

Summary

A new arXiv paper (2608.11181) by Orr Paradise, Oliver Richardson, Yoshua Bengio, and Shafi Goldwasser studies whether a probabilistic predictor's answers to many conditional-probability queries are self-consistent, and whether this can be verified in polynomial time. The question matters for AI safety, where safety depends on honest probabilistic predictions of unwanted AI-caused outcomes. The authors construct an interactive PCP: a predictive model is given as a probability circuit P plus a circuit Q outputting prediction confidence, together implicitly specifying exponentially many probabilistic claims. A polynomial-time verifier evaluates (P,Q) at only a few points and reads few positions of a proof oracle encoding a witness distribution consistent with the predictions, interacting with a single untrusted prover. As a foundation, they show that l2-approximate consistency of m explicit claims of the form Pr[Y = 1 | X = x] = p over n Boolean variables lies in NP with certificate length O(mn + log B), building on Nilsson's 1986 work, and remove the dependence on bit precision B via a small completeness-soundness gap. These results provide complexity-theoretic foundations for proving self-consistency of probabilistic predictors.

Overview

Field: Machine Learning
Authors: Orr Paradise, Oliver Richardson, Yoshua Bengio, Shafi Goldwasser
Published: 2026-08-11
arXiv: 2608.11181

Abstract (translated)

When a probabilistic predictor answers multiple conditional-probability queries, are its answers self-consistent, and can this be verified in polynomial time? This question is significant for AI safety, where safety derives from honesty about probabilistic predictions of how AI behavior could lead to undesirable outcomes. The authors construct an interactive PCP as follows. Let a predictive model be specified by a probability circuit P and a circuit Q that 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 receives the circuit pair (P,Q), which it evaluates at only a few points; alongside them, it receives a proof oracle — an encoding of a witness probability distribution supposedly consistent with the (P,Q) predictions — and reads only a few positions while interacting with a single untrusted prover.

Along the way, the authors must ensure the existence of a sparse witness distribution consistent with the model's predictions. To this end, they first consider witness distributions for the consistency of *explicit* probabilistic claims (rather than claims specified by the predictor): given m claims of the form Pr[Y = 1 | X = x] = p over n Boolean variables, building on work pioneered by Nilsson (Artif. Intell., 1986), they place l2-approximate probabilistic 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 eliminate the dependence on B via a small additive completeness–soundness gap. These results provide complexity-theoretic foundations for proving the self-consistency of probabilistic predictors. The interactive PCP is viewed as a first step toward training predictive models to prove their own consistency.

Original Abstract (excerpt)

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[le]...

---

*Auto-collected on 2026-08-13*