acceptodds
Under review as a conference paper at ICLR 2027

Partial Soundness: Natural Language Theorem Proving with Machine-Checked Logical Structure

Abstract

Large language models are increasingly proficient in mathematical reasoning tasks in natural language, but such outputs can lack formal guarantees, whereas fully formal theorem proving remains difficult due to various factors. We introduce Partial Soundness, a theorem-proving framework that bridges these settings through machine-checked proof structure. Given a theorem, the framework decomposes it into intermediate subgoals, formalizes the subgoals in Lean, and verifies that they are sufficient to derive the target theorem before any natural language proof is generated. Natural language proofs are then produced and assembled into a complete proof. This yields a partial soundness guarantee: while leaf-level reasoning remains informal, the logical dependency structure of the proof is formally verified. We also introduce INFormalRA, a dataset of 114 undergraduate real analysis theorems paired with Lean formalizations. Experiments on INFormalRA and existing benchmarks demonstrate that the proposed framework produces proofs with machine-checked logical structure and more interpretable intermediate reasoning while displaying reasonable proof-generation performance. These results suggest that Partial Soundness provides a practical middle ground between unconstrained natural language theorem proving and fully formal proof generation.

Primary area:
applications to computer vision, audio, language, and other modalities
Keywords:
Theorem proving, Natural language theorem proving, Large language models, Formal verification, Proof decomposition, Partial soundness

Reviews

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

This paper presents partial soundness, a theorem-proving framework that bridges natural-language proof generation and Lean4 verification of proof structure. The framework first decomposes a theorem into intermediate subgoals and then formalizes them in Lean. Then it uses Lean to verify whether the decomposed subgoals can prove the theorem. This results in a partial soundness guarantee: the logical dependency structure is machine-verified, while leaf-level reasoning must be verified manually. The work also introduces the InformalRA dataset, which contains 114 undergraduate analysis theorems with human-reviewed Lean formalizations. The experiment indicates that partial soundness achieves performance comparable to direct generation.

Critical strengths
  1. Interesting problem setup: The proposed partial soundness framework offers a middle ground between unconstrained informal proving and fully formalized proofs. It has the potential for LLMs for math with partial formal guarantees
  2. Human evaluation effort: The author team performs extensive human-in-the-loop evaluation for both dataset construction and evaluation, which is worth acknowledging, since evaluating informal proofs remains difficult to automate reliably.
Critical weaknesses
  1. Small and limited dataset: Despite the Lean formalizations being human-reviewed, the InformalRA dataset contains only 114 problems and covers only basic topics in classical analysis from a single textbook. Each problem also includes only the natural language statement and the Lean4 theorem statement. It has no aligned gold subgoal decomposition in either natural language or Lean, which has the closest connection to the paper's partial soundness contribution of the paper.
  2. Unclear positioning of experiments:
    1. The experimental section mainly compares the overall correctness of partial soundness (PS) and direct generation (DG), which are nearly identical. It does not clearly demonstrate why the method is working or in what sense it is superior.
    2. Both methods are saturated on all the evaluated datasets, with manual evaluation accuracy above 97% for both PS and DG. Comparing on these datasets leaves little room to differentiate the two methods, which weakens the experimental evidence.
Questions for authors
  1. Can the authors clarify the intended use of InformalRA? In particular, does it differ from existing benchmarks, given that both PS and DG achieve similar, saturated performance on them?
  2. Can the authors compare PS and DG on harder benchmarks, or with weaker or open-source models instead of only GPT-5.5? Settings where DG is far from saturated would better reveal whether and when the verified decomposition helps.
  3. Can the authors provide a more detailed case analysis? The appendix presents several examples but does not systematically analyze which aspects of the framework they reflect or how representative they are.
2 comments
AuthorsOpenReview ↗

Response to Reviewer krQm

Thank you for your valuable feedback. We respond to the concerns you have raised below.

Response to Weaknesses 1 and 2.2:

InformalRA is not meant as a difficulty benchmark for frontier models; as you note, GPT-5.5 saturates it. Its intended uses are:

(i) evaluating proofs under fixed textbook definitions (we release the definitions used, since textbook definitions may differ from those in formal libraries) and

(ii) paired natural-language and human-reviewed Lean statements with one objective per problem, which enable studies of formalization fidelity.

We do not prescribe gold decompositions, since a theorem may admit multiple valid proof structures. InformalRA is intended to support the generation and verification of such decompositions rather than comparison against a single reference outline.

Response to Weakness 2.1:

We tried to point out a qualitative difference between PS and DG. Section 4 pinpoints some characteristics of PS, while Table 2 (Section 7.2) and Table 3 (Section 7.3) compare additional qualitative features, such as Completeness, Correctness, Clarity, and proof length.

Response to Question 1:

For the intended use of InformalRA, see the above response to weaknesses 1 and 2.2. InformalRA overlaps in spirit with the analysis portion of ProofNet; the differences are course-centered coverage of one textbook and the accompanying definition file.

Response to Question 2:

We agree that this is a worthy point of comparison and is potentially enlightening. However, it may be difficult to present these comparisons within the discussion period – we will try to integrate such studies in updates/edits.

Response to Question 3:

Below, we clarify what some of the examples in the appendix illustrate and how representative they are.

(i) Explicit stepwise structure (App. B.2, Fig. 3, Sec. 4.2): PS proofs state their intermediate claims as labeled steps or cases (on average 6.6–8.5 per proof, and at least three in 91–100% of proofs in every dataset and trial), whereas no DG proof contains labeled intermediate claims. This structure follows from the framework’s design, so the example is representative of PS outputs in this respect. The examples of errors in monolithic proofs (App. B.3) illustrate a related issue: the difficulty of locating errors without such a structure. These errors are rare with GPT-5.5 (7 of 1,456 DG proofs were judged incorrect), so the examples illustrate how difficult an error can be to locate when one occurs, rather than how often errors occur.

(ii) Effect of Lean verification (App. B.4, Fig. 4, Sec. 4.3): Fig. 4 presents a controlled example illustrating the effect of Lean verification. To contextualize this example, Lean rejected the first candidate composition for 11–38% of problems in our GPT-5.5 runs. In a separate LLM-judged rerun on Putnam, about 90% of the failed attempts were attributed to Lean-level errors and the rest were indeterminate; none were attributed to logically insufficient decompositions.

Thanks a lot for your response. Most of my concerns remain unresolved, especially regarding the small, saturated benchmark and the paper's unclear positioning. Thus, I have decided to maintain my current score.

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

Partial Soundness (PS) first decomposes a theorem into several proof blocks (or, equivalently, subpropositions), formalizes the statements of these blocks, and then uses Lean to verify whether the blocks, if proven, are sufficient to establish the target. It then generates a natural-language subproof for each block and assembles the final proof. The paper also introduces InFormalRA, a benchmark consisting of 114 undergraduate real-analysis problems, and compares PS with Direct Generation (DG) on four datasets.

Critical strengths
  1. A verified proof outline serves as a useful, checkable intermediate artifact. Distinguishing whether each proof block is true from whether these blocks are sufficient to establish the target provides a clear object for verification.

  2. The examples and prompts facilitate understanding of the entire process, including the distinction between failure to verify an outline and falsity of the theorem. The evaluation across four datasets, combining human judgment with additional automated scoring, supports the conclusion that the final proofs achieve broadly comparable correctness (vs DG), while candidly reporting the associated costs, including longer outputs and imperfect intermediate steps.

Critical weaknesses
  1. Formal guarantees are not explicitly carried through to the final proof. Lean only verifies that the formalized subgoals are sufficient to derive the target theorem. It does not check whether the semantic formalization of those subgoals is accurate, nor does it verify that the final natural-language proof faithfully follows the checked derivation. In particular, the assembly stage treats the Lean skeleton as a non-authoritative reference, leaving the paper’s claimed final proof without sufficient guarantees for its formal logical structure.

  2. Key ablation studies are missing. PS simultaneously introduces theorem decomposition, multi-stage generation, and Lean feedback retries, whereas DG does not employ these mechanisms. Without a decomposition-only baseline, it is impossible to disentangle the contributions of Lean verification itself from those of decomposition-based generation. I think the most important ablation study should be theorem decomposition or no.

  3. The practical benefits in readability and checkability lack empirical support. PS produces 3.28–3.73 times as many sentences as DG, on average, and receives lower Clarity scores on all four datasets. Although this does not directly demonstrate that PS proofs are harder to check, the paper also does not validate its core claimed advantage using metrics such as human checking time or error-localization efficiency. The paper shows in figure 3 that the DG "yields a monolithic proof, so locating the error (red) and tracing its effects requires reading it in full", but in clarity score, DG is higher?

  4. The non-triviality of verified proof outlines is not adequately evaluated. Lean kernel only ensures that the subgoals are sufficient to derive the conclusion. The paper mentions filtering degenerate outlines, but it provides neither concrete criteria nor an analysis of their effectiveness.

Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

Response to Reviewer Bt29

Thank you for your valuable feedback. We respond to the concerns you have raised below.

Response to Weakness 1:

This description of current partial soundness of our framework is mostly correct, and we are making an effort to obtain "stronger" partial soundness and will report the results in future edits.

As for the use of Lean skeleton as a non-authoritative reference, this is our design choice, and most likely stays that way. This is because the authoritative objects are the natural-language steps. The Lean skeleton is their formalization and may add Lean-specific glue (about 40% of compositions add auxiliary facts proved in Lean), which we did not want imported into the natural-language proof.

Response to Weakness 2:

We worked on an additional ablation study, involving DG with Lean in order to address this. (See our response to Reviewer pf3f).

Response to Weakness 3:

We would like to first mention that Clarity is not designed to measure what Fig. 3 illustrates. In the DeepTheorem rubric, Clarity is a holistic rating of whether a proof is "clear, unambiguous, and well-explained”. It does not measure how an error is located or which other parts of the proof depend on it.

Fig. 3 illustrates a property other than Clarity: how the proof is organized for checking. In a PS proof, each step is stated explicitly with its own subproof, and later steps cite earlier ones by name (e.g., "By Step 3"). A reader can check the step statements and how they combine (the part the Lean check targets), and then check each subproof against its own statement. If a subproof is wrong, the later steps that depend on it can usually be found through these citations. In a monolithic proof, intermediate claims are often implicit, so tracing an error typically means rereading the whole proof.

Admittedly, the illustration of Fig. 3 is rather qualitative, and further analysis would be helpful. We will try to add some in our future edits.

Response to Weakness 4:

The filtering criteria will be added in future edits. The implementation will also be included in the released code.

Thanks for your response. However, I think your response cannot address my concerns so far. Looking forward to more experiments result or revision (like your response to krQm's Q2).

I think your paper should also be self-contained, which means you should state the DeepTheorem criteria (you use them as evaluation scores in your experimental results table, but never explain what they mean) somewhere in the paper, rather than asking me to download the DeepTheorem paper to check them (I really did it...). This is why I gave a 2 for the Presentation score.

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

The paper introduces PARTIAL-SOUNDNESS, a Lean tool that bridges the gap between natural language theorem proving and formal proof generation. It proposes an LLM-assisted framework to decompose a theorem into intermediate subgoals, solves the subgoals in Lean, and combines the solutions from Lean to a full proof for the given theorem. The baseline in the paper is the direct generation of proofs (without subgoals) using LLM. It also proposes a dataset of 114 undergraduate theorems with Lean formalizations.

Critical strengths
  • The framework aims to show a practical research gap between natural language and fully formal theorem proving by leveraging intermediate subgoals.
Critical weaknesses
  • The paper doesn't clearly show why the pipeline needs subgoals. The result is not promising: direct generation's correctness is slightly lower than the proposed method, but very minimal. Also, there is no clear cost or efficiency comparison.

  • The paper compares PS with direct generation (no decomposition, no lean verification). There is no evaluation to show the role of Lean verification. It should include more ablation: PS (decomposition + lean), direct generation (no decomposition + no lean), decomposition + no lean, and no decomposition + lean

  • The pipeline has limited novelty. Most of the steps are performed by LLM. The paper uses only GPT, and there is also no comparison across multiple LLMs. What if the direct generation on other LLMs performs better than the proposed pipeline?

Questions for authors
  • Q1: How do the two methods compare in terms of computational cost and efficiency (e.g. inference time and token consumption)?

  • Q2: In Intermediate Verification Stage, there is formal proof construction module, so why do we need Lean Verification module? What if this step is removed?

  • Q3: What is the main difference and advantage of Partial Soundness and Hilbert (ICLR 2026)?

2 comments
AuthorsOpenReview ↗

Response to Reviewer pf3f

Thank you for your valuable feedback. We respond to the concerns you have raised below.

Response to Weaknesses:

It is true that our accuracy gain is small, but the intended benefit of our approach is a checkable artifact: a decomposition whose final step (deriving the theorem from the stated intermediate claims) is machine-checked, while the leaf proofs remain in natural language.

It is also true that most of our modules use LLM calls, and the only non-LLM component is the Lean verifier module. Our contribution is the flow (the outline is checked before any proof is written) and the resulting certificate, not a new model component. Compared with prior work, some (such as DSP and Hilbert) use informal reasoning to produce formal proofs, while others (such as ProofFlow) formalize an existing natural-language proof. PS instead keeps the output in natural language and attaches a checked final entailment, without a specialized prover.

We agree that more ablation studies would be illuminating, but, due to the time constraint, the only additional ablation study we performed is the "No Decomposition + Lean" case, which gave us 95 successful Lean-verified proofs out of 114 problems (over two trials).

Response to Q1:

PS is more computationally expensive than DG. On the Putnam benchmark, our sequential GPT-5.5 runs took approximately 9 minutes per problem for PS, compared with 45 seconds for DG. Total token consumption has not yet been quantified. While final-answer accuracy is comparable, PS additionally provides machine-checking of the proof’s logical structure.

Response to Q2:

Let us try to clarify the difference between the Formal Proof Construction Module and the Lean Verification Module. The Formal Proof Construction Module is responsible for proposing a candidate Lean outline (with the formal language subgoals/building blocks from the previous Lean Formalization Module), generated through an LLM. The Lean Verification Module, on the other hand, involves/consults with the Lean compiler itself (not an LLM) to check if it actually compiles. In other words, the Lean Verification Module is critical in validating the outline of the formal proof generated in the Formal Proof Construction Module.

Omitting the Lean Verification Module means that our pipeline would still present a formal proof outline, but it would not have a certification that those subgoals would interact with each other to form a valid formal proof. Technically, it could be removed, but it would also remove the “soundness” aspect of the pipeline as well.

Response to Q3:

PS and Hilbert share a similar mechanism, using a Lean sketch laying out subgoals and checking that they entail the desired theorem. The main difference is the role this verified sketch plays and what fills in the outline.

Each subgoal in Hilbert must be closed in Lean and the output is either a complete Lean proof or no proof, while PS uses the outline as a gate and a roadmap for generating the natural language proof (cf. Section 2.1). In PS, each subgoal is proved in natural language, and the result is a single natural language proof with a machine-checked logical structure.

When Hilbert succeeds, its guarantee is strictly stronger. In PS, the leaf-level arguments and correspondence between natural language subgoals and their formalized subgoals are not machine-checked. However, PS has two main advantages:

(i) Applicability: when a full formal proof is out of reach or unnecessary, PS can still return a natural-language proof with a machine-checked structure, since only the outline, not every leaf, needs to compile. Hilbert's own failure analysis on PutnamBench (Hilbert, App. A.7) shows that the most common failure stage is discharging already-decomposed subgoals in Lean, which is exactly the step PS replaces with natural language subproofs.

(ii) Readability: Hilbert's PutnamBench proofs average 1,454 lines of Lean (Hilbert, App. A.8), whereas PS returns a stepwise proof in mathematical prose that can be read without knowledge of Lean.

Thanks for the response. For the current results, PS achieves slightly higher correctness than DG but takes 10 times longer and produces 3 times longer proofs. So to me it does not justify the high cost. And as mentioned, I think further ablations should be done to demonstrate the generalizability of your approach (e.g. not relied on only the GPT model in experiment) and the effectiveness of intermediate components.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.