The paper introduces Rewindable Interactive Proofs (RIPs), a new model for scalable oversight where a weak verifier can rewind a powerful AI prover to an earlier state during interaction. RIPs enable verification of oracle‑aided computations that are robust to small changes in oracle answers, achieving near‑linear verifier time without relying on cryptography. The authors provide a construction, implement it on MNIST, and demonstrate that RIPs can outperform existing proof systems in practice.
By Ziyi Guan, Yael Tauman Kalai, Ron Rothblum, Zoe Xi
arXiv:2607. 03561v1 Announce Type: new Abstract: As AI models continue to develop powerful capabilities, it becomes critical that we are able to verify that their output is aligned with our intentions.
By Liyan Chen, Yael Tauman Kalai, Zoe Xi
The paper investigates whether interactive arguments for oracle‑aided AI computations can be zero‑knowledge, meaning the verifier learns nothing beyond the correctness of the output. It proves that, in general, zero‑knowledge proofs for all oracle‑aided computations are impossible, even in the random oracle model, and this impossibility extends to debate protocols. However, if the oracle signs each answer with a cryptographic signature, then every oracle‑aided computation can be verified in zero‑knowledge with efficient provers and verifiers, assuming only collision‑resistant hash functions.
By Alessandro Chiesa, Ziyi Guan, Burcu Yildiz
arXiv:2607. 06341v1 Announce Type: cross Abstract: Formal verification offers the strongest guarantee of software correctness, but it does not scale: the proofs demanded by interactive theorem provers such as Coq require enormous expert effort.
By Shuangxiang Kan, Shuanglong Kan, Sebastian Ertel
Formal verification offers the strongest guarantee of software correctness, but it does not scale: the proofs demanded by interactive theorem provers such as Coq require enormous expert effort. Large language models (LLMs) promise to generate these proofs automatically, yet existing approaches wire a fixed, human-designed proof strategy into the system and constrain the model to follow it (retrieving premises and predicting tactics one step at a time, or splitting goals by divide-and-conquer), and still prove only a fraction of their target theorems.
arXiv:2607. 16372v1 Announce Type: cross Abstract: Interactive theorem proving (ITP) underpins program verification and formalized mathematics, but its manual effort limits scalability.
By Qiyuan Xu, Joshua Ong Jun Leang, Renxi Wang, Wenda Li, Haonan Li, Luke Ong, Conrad Watt
arXiv:2608.28639v1 Announce Type: new
Abstract: Formal theorem proving with large language models remains challenging due to the difficulty of navigating large proof search spaces efficiently. Existi...
By Bodla Krishna Vamshi, Haizhao Yang
arXiv:2607. 05397v1 Announce Type: cross Abstract: Agent systems increasingly execute rather than advise.
By James Rhodes, George Kang
arXiv:2607. 12650v1 Announce Type: cross Abstract: Tool access alone does not make LLM empirical reasoning governable: accepted outputs need not descend from attested evidence, and accepted deductions need not hold up under formal scrutiny.
By Junyu Ren
arXiv:2605.22875v2 Announce Type: replace
Abstract: Long-horizon mathematical reasoning fails less often because a model cannot produce a valid next step than because an agent fails to maintain and e...
By Zelin Zhao, Bo Yuan, Yuchen Zhu, Jaemoo Choi, Yongxin Chen
Agentic systems use large language models (LLMs) to carry out concrete tasks. Prior work often borrows abstractions such as scheduling, caching or isolation piecemeal from operating systems, so the me...
arXiv:2602. 20064v2 Announce Type: replace-cross Abstract: Large language models are increasingly deployed as agents: they plan, call tools, read untrusted data, and act on the results.
By Zac Garby, Andrew D. Gordon, David Sands