- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper provides a new approach for scalable oversight, that is, to show how a weak verifier can check the outputs of a more advance AI systems, using multi-prover interactive proofs via two isolated copies of an AI model, or by "rewinding" a single model. The paper has established a concrete theoretical framework that, given that the outputs of the model is robust, the proposed approach can efficient verify the outputs with theoretical guarantees on correctness and efficiency. The authors also provide a preliminary MNIST experiment to demonstrate the computational efficiency of the protocol.
Critical strengths
The studied problems are very important, and the provided theoretical guarantees appear to be interesting. I could foresee the use-case of the studied theory and the problem being applicable in the near future. Additionally, the author spent substantial effort on the theoretical contributions, which is commendable. The proposed "rewinding" approach is understandable and is intuitive.
Critical weaknesses
There are several critical weaknesses of the paper I would like to point out. One big potential issue is the limited empirical validation. The studied problem seems to be very interesting and would be very much applicable to verifying proofs on generated lean4 code, and the described AI models could potentially be frontier LLMs. However, the author only conducts limited research over MNIST with a highly simplified evaluation. I understand that this is a theoretical paper, but the lack of empirical validation makes it difficult to assess the practical significance of the proposed framework.
Additionally, one other critical issue lies in the assumptions of the outputs, i.e., the robustness. It is unclear how restrictive this assumption is and whether realistic AI reasoning satisfies it, as to me, the robustness assumption makes up the groundwork of the theoretical framework, yet it might be way too restrictive for practice.
Finally, presentation-wise, I found the connection between the theoretical construction and practical scalable oversight somewhat difficult to follow. Could the author explain more on how the theoretical framework could indicate our practical usage on real AI systems, such as usage over LLM?
Questions for authors
Can the authors provide examples of realistic LLM-based tasks that satisfy the required robustness assumption? Can the authors provide more realistic experiments to demonstrate the practical benefits beyond the MNIST setting?
2 comments
Thank you for the detailed response and substantial additional experiments. While I still have some reservations regarding the practical applicability of the framework, particularly whether the robustness assumption extends beyond simple aggregation tasks to more complex LLM reasoning, I find the theoretical contributions interesting, and the additional experiments and clarifications have addressed several of my original concerns. I have therefore decided to raise my rating to 3.
Thank you for your comments. We have updated our submission to include an appendix (Appendix F) containing additional experimental results and a table comparing the parameters of our protocol to those of Chen, Kalai and Xi’s single-prover protocol. We have also updated the supplementary material to include code for reproducing the new experiments. We respond to the points you raised below:
We agree that our experiments are limited, and we intended them as an initial proof of concept. Our implementation uses general circuit-based prover and verifier algorithms, rather than algorithms specific to MNIST. In our additional experiments, we use the same underlying machinery with different circuits and oracle inputs.
Following your suggestion, we added an LLM-as-judge experiment using Claude to judge preference pairs (Appendix F.4). When oracle calls are expensive, the prover’s additional computation is small relative to the cost of obtaining the judgments: the prover and direct evaluation each require one oracle call per pair, while proving adds only 0.37–1.04 ms of computation. The verifier requires only 76–84 oracle calls. Even at 256 pairs, it uses about 30% as many calls as direct evaluation; at 16,384 pairs, it uses about 0.51% as many.
These protocol timings use cached judgments; separately, we measured an actual sequence of 84 Claude calls, which took 179 seconds. Unlike the MNIST experiment, where oracle calls are inexpensive, Claude calls dominate the prover’s additional computation. In realistic oversight settings, oracle calls may similarly involve expensive human or model judgments. This highlights the practical value of reducing oracle calls even at relatively small input sizes.
Following reviewer B’s suggestion, we also added a hash-chain experiment (Appendix F.3) to address the limitation that, in the original majority-vote example, the verifier could estimate the answer by sampling oracle calls itself.
Finally, we have also improved the MNIST implementation (Appendix F.1): at 2^{26} views, the verifier takes 1.884 ms, compared with 15.51 ms for direct evaluation, and the prover takes 0.911 seconds; the verifier makes 80 oracle queries. The measurements exclude actual machine-state restoration.
Robustness was originally considered by Chen, Kalai, and Xi (ICML 2026). They note that, especially in the case when the oracle represents human judgment, it makes sense to assume that the computation is robust: human judgment is already unstable and error-prone, so as a safeguard, the output of the computation should not change if a small number of the human answers change, otherwise the output is not very meaningful.
One possible way to achieve robustness in a realistic task is to ask multiple oracles the same question (note that we can simulate multiple oracles with one oracle) and then aggregate their answers, for example by taking a majority vote. If the majority is sufficiently far from a tie, then the circuit is robust to changing a small fraction of oracle answers. More generally, the computation could involve applying complicated functions to the oracle answers, as long as the final output is not too sensitive to changes in a small fraction of them. For example, robustness can arise when aggregating preference judgments, as in RLHF and our new LLM-as-judge experiment.
We agree that not all realistic AI tasks will satisfy the robustness assumption. Our result shows that for computations satisfying this assumption, efficient verification is possible without assuming that any of the provers is truthful. We hope that our work will provide a theoretical foundation for future work studying which realistic tasks can be modeled as robust oracle computations.
Yes, we could view the provers as two isolated instances of an LLM that is trained to produce an output together with a label for the output, and the verifier as a smaller model that engages in an interactive protocol (that might rely on human judgment, or some other oracle) with the provers to verify that this label is correct.
We could also imagine this protocol being used in RLHF to efficiently reward the actions of an agent. Now instead of computing the reward directly, we could have the agent propose a reward and engage in an interactive protocol with two isolated copies of the agent as provers to verify that this reward is accurate