- Rating
- 1(−1)
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
This paper, if I understand correctly, attempts to strip away the implementation-specific factors of Interactive Theorem Proving (ITP) across different systems (e.g., Lean) by returning to the underlying theoretical structure of ITP, and thereby, from the perspective of Theoretical Computer Science (TCS), proposes a way to measure the "tool-agnostic ability of LLM agents to construct verifiable proofs."
The benchmark itself is organized into three tiers: (1) implementing six classes of classical, widely studied algorithms (like network flow); (2) solving six classes of canonical Interactive Proof (IP) problems from computational complexity theory (like those used in crypotograph); and (3) in line with existing ITP and ATP benchmarks, a set of proof tasks for Lean, Dafny, and DRAT. Tier 3 by itself is fairly conventional.
Critical strengths
- To me, it is novel to use notions from TCS (e.g., the IP class) to systematically construct a benchmark.
- The authors' goal of measuring the "tool-agnostic ability of LLM agents to construct verifiable proofs" is meaningful from a theoretical standpoint.
Critical weaknesses
- The authors' methodology is questionable with respect to achieving the goal they set out.
It should be noted that research in the ITP community draws its tools mainly from proof theory (a branch of mathematics), rather than being based on the IP class. Research in the ITP field rarely relies on the notion of IP, let alone uses it directly. The six problem families the authors present in Tier 2 are generally not regarded as representative proof challenges within the ITP community. The reviewer thus finds that the paper lacks sufficient justification for the claim that algorithm implementation (Tier 1) and IP-class problems (Tier 2) can represent the "ability of LLM agents to construct verifiable proofs" as that ability is understood in day-to-day ITP practice.
- It is unclear exactly which capability of LLMs the authors intend their benchmark to measure.
The "tool-agnostic ability of LLM agents to construct verifiable proofs" is too broad, because ITP is used across many different application domains: some benchmarks measure the ability to do frontier mathematical research (e.g., FATE, PutnamBench), some measure program verification ability (those based on Dafny and Verus), and some measure LLMs' reasoning ability on logical puzzles. Could the authors clarify which specific LLM capability their benchmark is meant to measure, and further justify why algorithm implementation (Tier 1) and IP-class problems (Tier 2) indeed represent the capability they target?
Many of the problems in Tier 1 and Tier 2 have been extensively studied in the literature. An LLM agent under evaluation could achieve high scores simply by reproducing existing state-of-the-art results; going beyond those scores, on the other hand, would amount to making progress on classical problems that are each of considerable research value in their own right, which is extremely difficult and, if achieved, would itself be a remarkable breakthrough in the field of Theoretical Computer Science (TCS). This further confuses the reviewer as to exactly which capability of the agent the benchmark is meant to measure, and whether it can represent, as the authors mention at the outset, theorem proving for frontier mathematics and program verification.
- The paper's comparison with prior work (Table 1) is not really defensible.
The paper criticizes MiniF2F for not being "agent-oriented," yet much recent work tackles MiniF2F precisely with agents (Delta Prover, AoA, Numina-Lean-Agent); on SATBench and similar benchmarks, one could take SAT/SMT solvers as baselines and require LLM agents to invoke SAT/SMT solvers in order to outperform the scores of the solvers alone. The paper criticizes SATBench, etc provide no "rigorous certificate," but they are verified by SAT solvers, despite differences in the trusted base that are acceptable in most cases. The paper emphasizes "scalable synthesis," but the authors' benchmark is likewise generated from only a handful of problem families, while using LLMs to synthesize miniF2F-like data has already become standard practice.
Questions for authors
I would invite the authors to respond my concerns in the weakness section.
6 comments
Rebuttal (2/2)
W3. The paper's comparison with prior work (Table 1) is not really defensible.
-
Regarding whether MiniF2F is agent-oriented, we would emphasize the word oriented. In our response to all reviewers, we give two criteria.
(1) A bare LLM, without a harness or tools, has difficulty solving the benchmark problems. (2) When LLM agents can write code and search the web, the benchmark still distinguishes their performance.
MiniF2F was originally designed without agents in mind and appears to fall short of these criteria. In our Case Study 1, we show that a bare LLM can solve many MiniF2F-style problems. And when we allow LLM agents to search the web for answers, they can solve nearly all of them.
-
Regarding rigorous certification in SATBench, the original paper requires the LLM being evaluated to provide its reasoning for an UNSAT instance. An LLM judge checks that reasoning. This step falls short of our definition of rigorous certification.
Subsequent studies using SATBench, such as VeriTrans (Liu et al. 2026), use a somewhat different evaluation setup from the original paper. SATBench generates test instances in three steps. (1) It generates UNSAT instances containing contradictory clauses. (2) It removes some clauses from an UNSAT instance and retains the result as a SAT instance if a SAT solver confirms it is satisfiable. (3) It converts all instances into natural language puzzles to test the model's reasoning ability. Since a SAT solver can distinguish the resulting instances, an agent can translate the natural language puzzle into CNF and call the same solver. This departs from the benchmark's original aim of evaluating the model's reasoning ability. Our assessment of the first three papers highlights what we see as a fundamental limitation of using only NP problems to evaluate models. When obtaining answers is too costly, agent-oriented evaluation, rigorous certification, and scalable synthesis cannot all be achieved at once. This motivates our use of for model evaluation.
-
Regarding scalable synthesis, our benchmark contains only 15 problem families, but it supports synthesis at two levels. (1) Each test case specifies a way to generate a series of instances with a given property. In this sense, each test case offers data generation capabilities comparable to those of a benchmark such as SATBench. (2) The data construction pipeline in Section 3.2 can generate test cases at scale within a single family. The original MiniF2F draws on a finite collection of mathematics olympiad problems. Synthesizing further problems also entails a trade-off between generating answers, so that the designer knows a test statement is true, and retaining the benchmark's ability to distinguish among agents. For these reasons, we consider the original MiniF2F to fall short of our scalable synthesis criterion.
Thank you again for your detailed feedback. We welcome any further questions you may have. If you feel that your questions have been addressed, we hope you will consider raising your score.
[1] Liu et al. 2026. VeriTrans: Fine-Tuned LLM-Assisted NL-to-PL Translation via a Deterministic Neuro-Symbolic Pipeline.
I do not think one of my major concerns has been addressed. In their rebuttal, the authors attempt to clarify the distinction between interactive proofs (IP) and interactive theorem proving (ITP). However, the main claimed novelty, the unified proof ability, rests solely on the former, while the abstract and introduction motivate the work almost entirely through the latter, ITP and program verification (see, e.g., the opening sentence of the abstract: “Recent advances in LLM-assisted theorem proving and program verification…”). This creates a mismatch between how the work is framed and what it actually contributes. In particular, it remains unclear why IP-based benchmark cases can be representative of day-to-day ITP practice. To be candid, the framing gives the impression that the paper leverages the current momentum around ITP and program verification to motivate a benchmark that, in practice, serves a different purpose.
Rebuttal (1/2)
Thank you for the detailed feedback and valuable perspective. We would first like to clarify our interpretation of the issues you raise.
We first clarify the distinction between interactive proofs and ITP. In interactive theorem proving, a prover establishes a proposition in a language such as Lean. The prover interacts with the system of the proof assistant. The system presents the current goal, the prover supplies the tactics to apply next, and the system updates the goal until it becomes ⊤ (or no goal remains, which indicates the proof term passes the kernel's type-checking). Lean, for example, implements a deterministic algorithm based on the Calculus of Constructions, whose soundness follows directly from that of the underlying type theory. In the language of TCS, when the verifier in an interactive proof protocol is deterministic, the complexity class of problems it can verify is analogous to DIP=NP⊆IP.
We define unified proof ability in item 1 of our response to all reviewers. The interactive proof framework contains but is not limited to the ITP protocols you describe and other forms of verification. Consider the claim that an LLM agent holds the private key of a public-key cryptosystem. The verifier repeatedly sends the prover a random ciphertext c=Enc(m), asks it to compute Dec(c), and checks whether the result equals m. We believe our IP-based framework is better suited than ITP to formalizing this kind of practical interaction.
As you point out, our Tier 1 and Tier 2 problems are not standard proof challenges in the ITP community. However, this is consistent with our motivation. TCS offers a wide range of IP problems for which our framework can generate instances in bulk. We therefore ask whether these sources of problems can provide a suitable dataset both for benchmarking and, potentially, for post-training. We designed the transfer experiment in Case Study 3 (Section 5.3) to test this idea. After we distilled lessons from proof transcripts on Tiers 1 and 2, the models' performance on Tier 3 also improved.
We evaluate unified proof ability as we define it. Conducting frontier mathematics research, constructing mathematical objects, and writing code are distinct capabilities, and we caution against interpreting unified proof ability as a combination of those capabilities. We gave the following definition in our response to all reviewers.
The verifier is free to specify the protocol, which can extend beyond a particular formal verification system such as Lean. In practice, the human verifier and the LLM agent indeed agree on a protocol Π and interact according to it. If the interaction meets the agreed conditions, the verifier accepts the claim. The protocol can cover rigorous mathematical proofs, formal verification code, and tasks that allow small completeness and soundness errors (such as our GNI task). Bounding the number of rounds and the verification cost of Π by low-degree polynomials gives the setting of our benchmark. Our benchmark therefore evaluates this ability.
Regarding the concern in your second paragraph, asking an LLM to reproduce state-of-the-art results from TCS research would mischaracterize our evaluation goal. We can select benchmark instances with particular mathematical structures. Even when a solver cannot handle a problem at the chosen scale, an LLM can examine the structure of the instance and devise a proof strategy tailored to it. Identifying that structure is itself a necessary and nontrivial part of solving problems and developing verification strategies in practice. Case Study 2 (Section 5.2) provides evidence for this point. When we gave the LLM agents a hint identifying the hidden structure, their scores improved substantially.