arXiv cs.AI· Ziyi Guan, Yael Tauman Kalai, Ron Rothblum, Zoe Xi·· 14 小时前AI 评分32
可回卷交互证明（RIPs）：用回卷实现高效可扩展监督
Efficient Scalable Oversight via Rewinding
AI 导读
研究者提出可回卷交互证明（RIPs），允许弱验证者在交互中把 AI 证明者回卷到先前状态再继续，从而在无需假设证明者诚实、也不使用密码学的前提下实现可扩展监督。该构造中诚实证明者运行时间为原始计算的线性时间，验证者一次性预处理后接近输入长度的线性时间，并已在 MNIST 初步实验中显示可快于现有部署的证明系统。
正文 · 原文
Abstract:Scalable oversight asks how a weak verifier can check the outputs of computations performed by more powerful AI systems. One proposed approach uses relativizing interactive proofs, in which a weak verifier checks the output of a complex oracle-aided computation by interacting with one or more powerful provers. A prominent example is debate, which is highly efficient but assumes that one of two powerful AI models, or provers, is truthful. For certain classes of oracle-aided computations, this assumption can be removed, but at substantially greater computational cost.
In this work, we introduce \emph{rewindable interactive proofs} (RIPs), a new model of relativizing interactive proofs for scalable oversight. In an RIP, the verifier may rewind the prover to an earlier state of the interaction and continue from there. This is possible when the prover is an AI model, since the verifier can save a snapshot of the model's state and later restore it. We construct a relativizing RIP for computations whose outputs are robust to changing a small fraction of oracle answers. Our construction is more efficient than prior relativizing proofs that do not assume a truthful prover, and it uses no cryptography.
In our construction the honest prover runs in time linear in that of the original computation, and the verifier, after a one-time preprocessing step, runs in time nearly linear in the input length (which can be much smaller than the computation itself). We implement our protocol, report a preliminary MNIST experiment, and show that an RIP can be faster than a state-of-the-art deployed proof system.
RIPs may be of independent interest. Rewinding is possible whenever the verifier controls the prover's machine, for example when the prover runs on trusted hardware or in a virtual machine whose state can be checkpointed.
| Subjects: | Artificial Intelligence (cs.AI); Computational Complexity (cs.CC); Cryptography and Security (cs.CR) |
| Cite as: | arXiv:2610.40535 [cs.AI] |
| (or arXiv:2610.40535v1 [cs.AI] for this version) | |
| https://doi.org/10.48550/arXiv.2610.40535 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Ziyi Guan [view email]
[v1]
Thu, 29 Oct 2026 17:34:28 UTC (54 KB)
来源：arXiv cs.AI · arxiv.org