Efficient Scalable Oversight via Rewinding

What it claims

Guan, Kalai, Rothblum and Xi (MIT) propose rewindable interactive proofs (RIPs), posted to the IACR Cryptology ePrint Archive as Paper 2026/2703 in November 2026. RIPs are presented as an alternative to debate for scalable oversight. Debate is efficient but assumes one of two powerful provers is truthful. Earlier relativizing proofs that drop that assumption, for certain classes of oracle-aided computations, cost substantially more. The authors claim their RIP construction removes the truthful-prover assumption at lower cost than those earlier proofs. They also claim that an implemented RIP can run faster than a state-of-the-art deployed proof system.

How it works

The verifier saves a snapshot of the prover's state during the interaction. It can later restore that snapshot and continue the interaction from the earlier point. The construction applies only to oracle-aided computations whose outputs stay the same when a small fraction of oracle answers change. The honest prover's cost is linear in the original computation. After a one-time preprocessing step, the verifier's cost is nearly linear in the input length, which the authors note can be much smaller than the computation itself. The protocol uses no cryptographic assumptions.

How to use it

Rewinding requires that the verifier control the prover's machine. The authors name two settings where this holds: a prover running on trusted hardware, or a prover running in a virtual machine whose state can be checkpointed. A deployment where the prover's state cannot be snapshotted and restored falls outside the model. The paper is licensed CC BY.

Limits

This page carries only the abstract. It gives no runtime figures, does not name the deployed proof system used for the speed comparison, and gives no MNIST task details or accuracy numbers. The authors call the MNIST experiment preliminary. The guarantee covers only computations that tolerate changes to a small fraction of oracle answers, and the abstract does not say which practical AI workloads meet that condition. The cost of the one-time preprocessing step is not stated. The paper is a preprint in the ePrint "Foundations" category, received 30 October 2026 and approved 4 November 2026.