acceptodds
Under review as a conference paper at ICLR 2027

An LLM with an REPL is a strong vericoding baseline in Lean

Abstract

LLMs are rapidly changing how software is written. However, testing alone is insufficient; formal verification is therefore needed to rigorously guarantee correctness. Given a specification as the source of truth, LLMs can synthesize both the implementation and proof of conformance, a paradigm recently termed vericoding. These proofs are machine-checkable via interactive theorem provers such as Lean. While existing LLM-based provers demonstrate remarkable performance, they often constrain how LLMs interact with Lean. We ask how far we can push LLM performance without sophisticated harnesses by enabling direct interactive Lean usage. Our baseline, Tiny Prover, combines an iterative agent loop with direct interactive access to Lean. On VERINA and VeriSoftBench, we observe that this setup saturates both benchmarks, surpassing more complex prover architectures.

Primary area:
foundation or frontier models, including LLMs
Keywords:
large language model, theorem prover, verifiable code generation, vericoding

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_ZPj6OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes Tiny Prover, a simple and conventional baseline that combines an off-the-shelf LLM with a Lean REPL in a standard iterative agent loop. The authors demonstrate that this straightforward setup, using GPT-5.4 and Claude Opus 4.6, can nearly saturate or fully saturate two existing benchmarks, VERINA and the Aristotle subset of VeriSoftBench, with GPT-5.4 achieving 100% on both. Overall, the methodological and experimental setup is highly conventional, relying entirely on existing models, tools, and benchmarks.

Critical strengths

To the best of my knowledge, this is the first work to report that a conventional iterative agent equipped with a standard Lean REPL and powerful frontier LLMs (GPT 5.4, Claude Opus 4.6) is sufficient to saturate both VERINA and the Aristotle subset of VeriSoftBench.

Critical weaknesses

Limited Novelty and Contribution. My primary concern is the limited novelty of this work. The entire novelty of the paper can essentially be summarized in the single observation I wrote in the Strengths section above. However, the strong capabilities of modern LLMs in interactive theorem proving have already been well demonstrated in prior work (e.g., APOLLO, A Minimal Agent for Automated Theorem Proving, and LEAP). Beyond reporting this particular empirical result, the paper offers neither a new methodology nor a sufficiently distinct scientific insight. I therefore remain unconvinced that the novelty and overall contribution of this work meet the bar for ICLR.

Questions for authors

The paper concludes that "a simple architecture (Tiny Prover) of an LLM with a REPL is a strong baseline solution that saturates VERINA and VeriSoftBench." This benchmark-saturation claim is based solely on experiments with GPT-5.4 and Claude Opus 4.6. Have the authors considered the possibility of training-data contamination in these frontier LLMs, given that both benchmarks were publicly available before the models were released? If so, how might potential contamination affect the validity of the paper's central conclusion?

1 comment

Weakness

While it is true that strong capabilities of modern LLMs in theorem proving have been established elsewhere, we argue that it is not the correct characterization of our work. To elicit these capabilities, these works typically propose an elaborate harness that captures aspects such as recursive decomposition, iterative refinement, search, etc. We ask if these harness complexity is necessary for modern LLM, instead of just allowing the LLM to use Lean's feature. For example, in the "A Minimal Agent for Automated Theorem Proving" work as suggested by the reviewer, the authors explicitly forbid the usage of sorry or suggestion tactics like apply?, even during the code-proof development process. We impose no such restriction when the model uses the REPL, and only forbid shortcuts (e.g., sorry, admit, axiom, etc.) in the final proof, which allow the model to freely use all available Lean features that the model finds useful, such as #find, #print, apply?, etc. Any harness design that requires the model to submit a complete proof without direct interactive Lean access will typically prevent the usage of these interactive features.

As explicitly stated in the title, Tiny Prover is not meant to be a state-of-the-art solver, but rather a baseline that more complex vericoding agentic provers should outperform to justify the additional complexity (lines 456-459). It makes little sense to just design another complex agentic prover for the sake of a novel harness. We first set up Tiny Prover to study the bottleneck of Lean vericoding that requires custom harnesses before designing our own. To our surprise, Tiny Prover effectively solves existing benchmarks like VERINA and VeriSoftBench (Aristotle). Furthermore, we chose GPT-5.4 and Claude Opus 4.6 as these models have been used in prior works but provide no evidence of saturating benchmarks like VERINA.  We hypothesise that the direct, unconstrained access to Lean's features is what helps elicit the LLM's inherent performance and study them correspondingly.

Benchmark leakage

We have several observations that suggest the current performance is not due to benchmark leakage:

  • The knowledge cutoff date for both GPT-5.4 and Claude Opus 4.6 is Aug 2025.
  • For VERINA, the first commit and preprint are from May 2025. However, there are no complete ground truths, and only a very small curated subset of VERINA Basic tasks has ground-truth proofs. Prior works have used GPT-5.4 and Claude Opus 4.6, but observe no saturation results (Table 1).
  • For VeriSoftBench, the first commit and preprint are from Feb. 2026.
  • We further evaluate Tiny Prover on AlgoVeri with the first commit from Dec. 2025 and the first preprint from Feb. 2026, and observe the same patterns. Please see the response to Q1 to reviewer YDam for the AlgoVeri result.
Reviewer_YDamOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates how far general-purpose LLMs can go in formally verified code generation when given direct interactive access to Lean. The authors introduce Tiny Prover, a relatively simple agent that uses a stateful Lean REPL to inspect definitions, experiment with intermediate lemmas, query proof states, and iteratively refine solutions.

The evaluation covers VERINA and the Aristotle subset of VeriSoftBench, achieving 100% pass@1 on VERINA with GPT-5.4 and 100% pass@2 on VeriSoftBench with both GPT-5.4 and Claude Opus 4.6. The authors also analyze tool usage, proof lengths, and behavior across different model capabilities.

The main takeaway is that strong foundation models, when given sufficiently flexible access to Lean, can already solve many vericoding tasks without specialized training or complicated prover architectures.

Critical strengths

1. A surprisingly strong result from a simple setup.

I really like the motivation behind this paper :) We spend a lot of effort designing increasingly complicated proving agents, but it is worth asking whether we are actually measuring the model's reasoning capabilities or the limitations of the environment we give it. The reported performance is impressive, especially the near-saturation of VERINA and VeriSoftBench without specialized fine-tuning.

2. Interesting analysis of how models interact with Lean.

I particularly appreciate the analysis of REPL usage, including inspection commands, temporary examples, auxiliary lemmas, and environment management. The observation that models frequently create fresh environments despite having access to persistent state is interesting! These results could inform the design of future verification agents, especially tools that expose Lean's internal information more efficiently.

Critical weaknesses

1. Limited benchmark coverage and unclear generalization beyond saturated tasks.

My biggest concern is that the paper evaluates only VERINA and the Aristotle subset of VeriSoftBench, both of which are essentially saturated by the proposed approach. While the results are impressive, I think this makes it difficult to assess how well Tiny Prover generalizes to genuinely challenging verification problems :) VERINA primarily consists of self-contained algorithmic tasks, while VeriSoftBench evaluates proof generation rather than joint code-and-proof synthesis.

I would have liked to see at least one substantially harder benchmark, such as CLEVER, or more realistic repository-scale tasks requiring changes to existing implementations, auxiliary invariants, and proofs across dependencies. Without this, I am not convinced that benchmark saturation alone establishes the effectiveness of the approach for more general vericoding.

2. The contribution of the REPL itself is not isolated.

The paper attributes the strong performance to direct interactive access to Lean, but there is no controlled comparison against simpler alternatives using the same models and inference budgets. How much of the improvement comes from stateful REPL access, ordinary iterative compilation feedback, built-in Lean tactics, or simply allowing up to 100 tool calls?

Interestingly, Figure 6 shows that most REPL calls create fresh environments. This makes me wonder whether persistent state is actually important, or whether ordinary stateless Lean execution with a flexible interface would perform similarly. I think a controlled ablation is necessary to substantiate the central claim.

3. Baseline comparisons and verification reliability need further clarification.

The comparisons in Table 1 involve different base models, tool budgets, and pass@k settings. This makes it difficult to attribute the reported improvements to the simplicity of Tiny Prover rather than stronger models or additional inference compute.

I also have some concerns about relying on an LLM-based semantic checker to detect verification loopholes. Lean compilation establishes that a theorem is accepted under the given environment, but the semantic validity of generated implementations and auxiliary declarations requires additional scrutiny. Given the unusually high success rates, I would appreciate more details about how the final artifacts were audited and whether the checker rejected any initially compiling solutions.

Questions for authors
  1. Broader benchmarks: Given that VERINA and the evaluated subset of VeriSoftBench are essentially saturated, could the authors evaluate Tiny Prover on harder settings, such as CLEVER or full repository-scale verification tasks? I am particularly curious whether the same simple architecture remains effective on longer-horizon problems :)

  2. REPL ablation: How much of the improvement specifically comes from the stateful REPL? Could the authors compare against stateless Lean compilation with iterative feedback, keeping the model and tool budget fixed?

  3. Inference efficiency: What are the average wall-clock time, token consumption, and cost per successfully verified task? How does Tiny Prover compare with existing approaches under equivalent inference budgets?

  4. Verification soundness: How many initially compiling submissions were rejected by the semantic checker? Were successful solutions independently examined for loopholes involving modified definitions, unsafe constructions, or auxiliary declarations that weaken the intended specification?

  5. Model versus harness: How much of the improvement over prior systems remains when controlling for the base model and pass@k? Could the authors provide a matched-model comparison to establish whether the simpler harness is genuinely better?

  6. Long-horizon verification: Have the authors tested whether Tiny Prover can handle modifications spanning multiple files, nontrivial loop invariants, or changes that require updating existing proofs? These seem closer to the practical vericoding setting motivating the paper.

2 comments

Q1

As explicitly stated in the title, Tiny Prover is not meant to be a state-of-the-art solver, but rather a baseline that more complex vericoding agentic provers should outperform to justify the additional complexity (lines 456-459). However, we understand the concerns that VERINA may be a simple benchmark compared to the reviewer-proposed ones, like CLEVER. However, the evidence in existing literature suggests the contrary. For example, in the benchmark AlgoVeri, the authors labeled CLEVER as basic and VERINA as medium. In the Goedel-Code-Prover work, most methods (except Goedel-Code-Prover) achieve better results on CLEVER compared to VERINA. However, to further assess Tiny Prover performance, we evaluate Tiny Prover on a more difficult AlgoVeri benchmark and compare it to the reported results in Inductive Deductive Synthesis and Goedel-Code-Prover below. Similarly, with a single run, Tiny Prover can solve most problems of AlgoVeri.

MethodAlgoVeri
Goedel-Code-Prover62.3% (pass@128)
Inductive Deductive Synthesis84.4%
Tiny Prover (GPT-5.4)94.8% (pass@1)

On AlgoVeri, Tiny Prover requires more calls and tokens compared to VERINA, with an average of 40.38 calls and 61010 tokens per problem.

Q2

The statefulness of the REPL is just one aspect of direct, unconstrained interactive Lean access. Removing the stateful capability, the REPL is essentially similar to a Lean compiler. From Figure 6b, we can see that GPT-5.4 tends to use the REPL as a compiler, and only use the stateful feature selectively, especially on harder problems what requires lots of REPL calls. However, using it selectively is different from not utilizing the feature at all. On the other hand, Claude Opus 4.6 uses this feature much more frequently. Each model has a different strategy in solving problems, and we impose no restriction on how to use the REPL. The usage of the remaining interactive capabilities can be observed in the right plot of Figure 5.

Q3

We report the total token usage of each model in Figure 4. Due to the iterative nature of Tiny Prover, most of these tokens are input tokens, so the cost is largely input-dominated. On average, both GPT-5.4 and Claude Opus 4.6 use less than 40,000 tokens per VERINA Advanced problem (Table 2).

Q4

For the final solution, the model can only provide code to the predefined slots and possesses no tools that can edit the specification or submission. The model is only provided with an REPL to test the solution, but the submission is completely separate and only accepts certain slots that the model has to fill in. The submission slot is checked for invalid proof attempts, e.g., using sorry, admit, axiom. The compiler verifies that the whole code-proof compiles. The semantic checker evaluates the remaining cases as can be observed in the prompt.

Q5

Tiny Prover only requires 1 or 2 attempts, compared to a much larger kk in some prior works. Prior work also evaluated on GPT-5.4 and Claude Opus 4.6, as mentioned in Table 1, which is partially the reason we select these two models. Table 2 also demonstrates the results using weaker models, but these models are still capable of solving a majority of the VERINA Advanced tasks. While a more controlled comparison is desirable, the current results do not undermine our claim.

Q6

We agree that the practical vericoding setting suggested by the reviewer is more challenging than the benchmarks Tiny Prover is evaluated on. However, at the time of submission, we were not aware of a benchmark that sufficiently captures these aspects. The core principle of Tiny Prover is simple, so while we were not able to evaluate Tiny Prover in such a setting, future work can straightforwardly extend Tiny Prover to serve as a baseline in those cases.

Thanks for the detailed response and for running the additional AlgoVeri experiments! :) The 94.8% pass@1 result is impressive, and I appreciate the clarification that CLEVER is not necessarily harder than VERINA. My main concern, however, remains the contribution of the REPL itself. The authors mention that GPT-5.4 often uses it essentially as a compiler, so I would still love to see a controlled comparison against ordinary iterative Lean compilation with the same model and compute budget. Without this, it's difficult to tell how much the interactive setup actually helps.

I understand that Tiny Prover is intended as a strong baseline, but I think that makes isolating the benefits of the setup even more important. I'm also still curious how well it would generalize to larger verification tasks with dependencies. Overall, I appreciate the new results, but these concerns remain, so I'm maintaining my original score! Thanks again! :)

Reviewer_BAbhOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents Tiny Prover, an iterative LLM agent equipped with an interactive Lean REPL for generating implementations and correctness proofs from provided Lean specifications, a task known as vericoding. With REPL access, the agent can inspect declarations and proof goals, test intermediate lemmas, and refine its solution using Lean feedback. With GPT-5.4, the system achieves 100% pass@1 on VERINA and 100% pass@2 on the Aristotle task (100 subset) of VeriSoftBench. Each attempt is a complete agent trajectory with up to 100 REPL calls. Additional experiments also evaluated two less powerful LLMs to show robustness against models, and characterized generated proofs and Lean usage patterns.

Critical strengths
  • The paper shows that a simple augmentation to existing agentic provers can serve as a strong baseline that future proving systems should compare against before attributing improvements to more sophisticated architectures.
  • The robustness experiments and measurements of token consumption and tool usage make the finding more convincing than those using only one frontier model.
Critical weaknesses
  • Limited contribution as an ICLR main paper. The architecture combines a standard agent loop with an existing Lean REPL, while the interaction analysis mainly describes tool usage without showing which capabilities explain the gains, leaving limited insight beyond the reported benchmark saturation. It seems that accessing the REPL is orthogonal to any existing baseline, and can be as trivial as adding a new prompt instruction by giving any agent the REPL access.
  • Uncontrolled comparisons: Table 1 mixes base models, inference budgets, and proof-only versus joint generation settings, and even its references to results using the same models come from prior reports rather than controlled experiments, making it difficult to attribute the improvements to Tiny Prover’s interface.
Questions for authors
  • How does Tiny Prover compare with Claude Code or Codex given the same models, comparable token budgets, access to the same REPL, with the same prompt instructions explicitly encouraging using REPL?
  • Could you present more detailed studies from the trajectories to illustrate the breakdown of contributions of each REPL calls? How much does each specific category of REPL calls contribute to the final success?
1 comment

W1

As explicitly stated in the title, Tiny Prover is not meant to be a state-of-the-art solver, but rather a baseline that more complex vericoding agentic provers should outperform to justify the additional complexity (lines 456-459). We first set up Tiny Prover to study the bottleneck of Lean vericoding that requires custom harnesses before designing our own. To our surprise, Tiny Prover effectively solves existing benchmarks like VERINA and VeriSoftBench (Aristotle). As observed by the reviewer, the components themselves already exist and are rather simple; hence the name "tiny".

However, to our best knowledge, such a simple baseline has been overlooked in existing vericoding works, which enables the state-of-the-art claim with unclear additional performance gain compared to the added complexity. We hypothesise that the direct, unconstrained access to Lean's features is what helps elicit the LLM's inherent performance and study them correspondingly. We impose no restriction on which features are allowed or not, so different models use different strategies, as can be inferred in Figures 5 and 6.

W2

Compared to mathematical theorem proving, there are limited prior works in the vericoding domain. Furthermore, the REPL calls are not the same as proof submissions, since the model may simply try importing a library using a call, which prevents comparing them to the number of attempts kk. We use the reported results and evaluated LLMs in prior works instead of stronger LLMs available at the time to show that those methods do not outperform the proposed baseline. Proof generation is the simpler setting compared to vericoding, so we are providing those results an advantage over Tiny Prover. A more controlled comparison is desirable, but do not undermine our claim.

Q1

Tiny Prover is a much simpler version of the reviewer-proposed setup, i.e., giving Claude Code or Codex access to the REPL. Tiny Prover is just an iterative LLM loop with access to only the REPL (and additionally a read-only POSIX shell on VeriSoftBench), which effectively isolates the contribution of unconstrained interactive Lean access. Adding REPL to Claude Code or Codex makes it harder to isolate the contribution. We emphasize that our goal is not to design a state-of-the-art harness, but to study whether the existing agentic provers for vericoding provide tangible benefits over a simple baseline.

Q2

The categories in Figure 5 are not for classifying a single REPL call. Each call may be a short or long Lean snippet, which uses various Lean's features, including any or all of those 6 categories. The category is defined post hoc after examining the run transcripts, and only the occurrence is counted rather than classifying any REPL calls.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.