How to Verify Consistency of Probabilistic Claims: An Interactive PCP for AI Safety
Forum topic · 小凯 · 2026-08-13
Summary
This paper addresses whether a probabilistic predictor's answers to many conditional-probability queries are self-consistent, and whether such consistency can be verified in polynomial time—a question central to AI safety, where honesty about predicted probabilities of harmful outcomes matters. The authors construct an interactive PCP (probabilistically checkable proof) protocol in which a polynomial-time verifier checks approximate consistency of a predictive model specified by a probability circuit P and a confidence circuit Q. The verifier evaluates (P,Q) at only a few points and interacts with a single untrusted prover that reads few bits, given access to an alleged sparse witness distribution encoded consistently with the model's predictions. To establish that such sparse witnesses exist, the authors analyze explicit probabilistic claims of the form Pr[Y=1 | X=x]=p over n Boolean variables. Building on Nilsson (1986), they show l2-approximate consistency of m explicit claims lies in NP with certificate length O(mn + log B), where B is input bit precision, and remove the dependence on B via a small additive completeness-soundness gap. Together, these results provide a complexity-theoretic foundation for proving self-consistency of probabilistic predictors.
Key points
- Problem setting. A probabilistic predictor answers many conditional-probability queries. The authors ask two questions: (1) Are the answers self-consistent? (2) Can consistency be verified in polynomial time? The motivation is AI safety, where safety relies on honesty about probabilistic predictions of unwanted outcomes potentially caused by an AI action.
- Model. A predictive model is specified by a pair of circuits: a probability circuit P and a confidence-output circuit Q. Together, (P, Q) implicitly specify exponentially many probabilistic claims.
- Main protocol: Interactive PCP. The authors construct a protocol in which a polynomial-time verifier checks the approximate consistency of (P, Q). The verifier:
- Receives the pair of circuits (P, Q) and evaluates them at only a few points.
- Receives a proof oracle—claimed to encode a witness probability distribution consistent with the predictions of (P, Q).
- Interacts with a single untrusted prover that reads only a few locations.
- Sparse witness requirement. A key technical step is ensuring the existence of a sparse witness distribution that agrees with the model's predictions. The authors establish this by first analyzing witness distributions for explicit probabilistic claims rather than those implicitly defined by the predictor.
- Explicit-claims complexity result. Consider m claims of the form Pr[Y = 1 | X = x] = p, covering n Boolean variables. Building on Nilsson's 1986 work in *Artificial Intelligence*:
- l2-approximate consistency of m explicit claims lies in NP.
- Certificate length is O(mn + log B), where B is the input bit precision.
- The dependence on B is removed via a small additive completeness-soundness gap.
- Significance. The interactive PCP is presented as a first step toward training predictive models to prove their own self-consistency. The explicit-claims results supply the complexity-theoretic foundation needed to make this approach viable.
Source metadata
- Field: Machine Learning
- Authors: Orr Paradise, Oliver Richardson, Yoshua Bengio, Shafi Goldwasser
- Posted: 2026-08-11
- arXiv: 2608.11181
- Auto-collected: 2026-08-13
This page is an English static mirror generated for search and AI citation.
It may be a full translation or structured summary of the Chinese original.
Canonical interactive discussion lives on the Chinese page:
https://zhichai.net/topic/178633406