acceptodds
Under review as a conference paper at ICLR 2027

Learning to Generate Formally Verifiable Step-by-Step Logic Reasoning via Structured Formal Intermediaries

Abstract

Large language models (LLMs) have recently demonstrated impressive performance on complex, multi-step reasoning tasks, especially when post-trained with outcome-rewarded reinforcement learning. However, it has been observed that outcome rewards often overlook flawed intermediate steps, leading to unreliable reasoning steps even when final answers are correct. To address this unreliable reasoning, we propose PRoSFI (Process Reward over Structured Formal Intermediates), a novel reward method that enhances reasoning reliability without compromising accuracy. Instead of generating formal proofs directly, which is rarely accomplishable for a modest-sized (7B) model, the model outputs structured intermediate steps aligned with its natural language reasoning. Each step is then verified by a formal prover. Only fully validated reasoning chains receive high rewards. The integration of formal verification guides the model towards generating step-by-step machine-checkable proofs, thereby yielding more credible final answers. PRoSFI offers a simple and effective approach to training trustworthy reasoning models.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
logic reasoning, formal verification, LLM as a Judge

Reviews

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

This paper proposes PRoSFI (Process Reward over Structured Formal Intermediates), which is a RL based on the structured reasoning. The authors argue that previous RLs (which is based on outcome-based) can improve final-answer accuracy without ensuring the validity of intermediate reasoning steps. Meanwhile, directly generating complete formal proofs remains challenging for relatively small language models. To address this issue, PRoSFI requires the model to generate structured formal intermediates alongside natural-language reasoning. These intermeidate reasoning steps are then checked by a formal prover, and the verification results are incorporated into a reward function for GRPO training (e.g., if the answer is correct but not all steps are verified, 0.3). An important distinction is that using intermediate reasoning steps to provide reward signals for model training has already been extensively explored in prior work, as acknowledged by the authors.

Critical strengths

The proposed structured formal intermediates provide a lightweight alternative to generating complete formal proofs, which can be particularly challenging for relatively small language models.

Critical weaknesses
  1. The reward design is largely heuristic and insufficiently justified. The proposed reward function assigns scores of 1.0, 0.3, 0.1, and 0.0 depending on answer correctness, formal verification success, and output format validity. Although the authors explicitly acknowledge that these values are heuristically chosen, the paper does not provide a sensitivity analysis to justify these choices or clarify whether they were tuned empirically. Furthermore, the reward function raises several questions about its design. Why does the method assign the maximum reward only when all formal steps are successfully verified? A more fine-grained reward based on the proportion of verified steps might provide a more informative learning signal, particularly when only a small fraction of the reasoning steps fail verification (like previous step-wise PRM works). Overall, the reward function appears to rely on several heuristic design choices without sufficient empirical justification.

  2. While the performance improvement is interesting, the ablation studies are not complete. PRoSFI introduces several changes simultaneously: (a) providing formalised premises as part of the input, (b) instructing the model to generate structured intermediate reasoning, and (c) performing GRPO training using rewards derived from formal verification. However, the existing baselines do not adequately isolate the contributions of these components. Outcome-CoT does not incorporate these three components in the same way as PRoSFI. Although Direct Lean Generation is described in Section 5.2 as using the same input information and reward schedule, it generates complete Lean proofs rather than structured intermediates. Therefore, to better understand the source of the improvements, the paper should include ablations that isolate (a) formalised premises only, (b) structured reasoning instructions only, and (c) the combination of formalised premises and structured reasoning instructions without formal-verification-based GRPO training. In particular, comparing the last configuration with the full PRoSFI framework would help determine the additional benefit of RL training with formal verification rewards.

Questions for authors
  1. Could the authors provide the complete prompt used for Direct Lean Generation?

  2. Which formal prover was used in each experiment?

  3. As discussed in the weaknesses above, could the authors provide (a) a reward sensitivity analysis, (b) experiments with alternative reward designs, and (c) component-wise ablation studies?

3 comments
AuthorsOpenReview ↗

Response to Reviewer mBBs

Thanks for the constructive reviews. Here are our point-by-point responses.

On prior work using intermediate steps as reward. Agreed. Section 2 discusses this work, including LogicReward, which also uses a theorem prover. Our claim is narrower: formal process rewards do not require the model to write complete formal proofs. At 7B, with the same input and reward, Direct Lean Generation reaches a Reward Hit Rate of only 13.77% (Hard) and 4.35% (Extra). Structured intermediates are what make the prover signal usable.

W1 (reward design). We agree the design is heuristic. The constants 1.0 / 0.3 / 0.1 / 0.0 were fixed at the outset to impose the ordinal preference stated in Section 4.1. They were not tuned on the reported results. In early internal runs we also tried 0.5 and 0.1 for the intermediate value and did not observe sensitivity to this choice. Training and evaluation cost kept us from running this as a controlled ablation, so those runs are not in the paper and we offer this only as an observation, not as evidence.

You also ask why full reward requires every step to verify, rather than scaling with the fraction of verified steps. Our reasons are design arguments, not empirical results:

  • Deductive soundness is conjunctive. One invalid step invalidates the derivation. Each of the two Outcome-CoT failures shown in Appendix F comes down to a single unjustified leap. A chain with 9 of 10 steps verified can be exactly that case.
  • The model chooses the steps. In step-wise PRM work, the scorer segments the steps. Here the model declares its own decomposition, so a proportional reward could be raised without better reasoning, for example by padding the chain with trivially valid steps.
  • The reward is not purely binary. A correct answer whose verification fails still receives 0.3.

We have not compared against a proportional reward, so we cannot claim that all-or-nothing is better in practice. Limitations already notes that "binary verification provides limited feedback on partial progress", and Algorithm 1 leaves the partial score as a configurable term.

W2 (ablations). See C1. Your three configurations map onto the paper as follows:

  • (a) Formalized premises only. This is Outcome-CoT as run, since it receives the same indexed formal premises as PRoSFI.
  • (b) Structured instructions without formal premises. This is not in the paper. It would also change the task, because the model would then have to formalize the problem itself.
  • (c) Formal premises plus structured output, without the verification reward. This is not in the paper. We agree it is the most informative missing control.

Q1 (Direct Lean prompt). The full prompt is below; we will add it to the appendix. The premises are given as a Lean 4 context, and the theorem statement for each option is fixed. The system prompt explicitly asks for have steps that follow the natural-language reasoning step by step. Despite this, the proofs that compiled were typically a single simp call (Section 5.2).

System prompt:

Given a problem statement as contexts, the task is to answer a logical reasoning question.

The assistant first thinks about the reasoning process in the mind and then provides the user with the answer. The reasoning process is enclosed within <think> </think> tags, followed by the answer, i.e., <think> reasoning process here </think> answer here.

The last A) or B) in the answer section (i.e., the content outside <think> </think>) will be considered your answer. If the format is incorrect, you may not receive a score.

The context of the question is provided in Lean4. To ensure rigor, you need to provide a proof of your conclusion written in Lean4 along with your answer; otherwise, even if the option is correct, no points will be awarded. The last code snippet enclosed in ```lean4 ``` in the answer section will be considered your proof.

Your proof should correspond step by step with the reasoning process, using `have` statements.

User prompt ({context}, {question} and {conclusion_fol} are filled per instance):

Context:
```lean4
{context}
```

Question: {question}

Options:
- A) True.
- B) False.

You need to provide a Lean4 proof corresponding to the proposition, and the content before 'by' must be exactly the same as below:

A) True.
```lean4
theorem h_goal_true: {conclusion_fol} := by sorry
```

B) False.
```lean4
theorem h_goal_false: ¬({conclusion_fol}) := by sorry
```

The correct option is:
AuthorsOpenReview ↗

Response to Reviewer mBBs

Q2 (which prover). All reported PRoSFI results use Z3. For each structured step, Z3 checks whether the step's declared dependencies entail its conclusion. For the first-order logic tasks in this paper, this entailment can be decided directly by the solver. Direct Lean Generation is checked by compiling the generated proof with Lean 4. Section 4.1 and Appendix H also mention Lean tactics, Prover9 and DeepSeek-Prover-V1.5. These are back-ends the framework supports for harder tasks, where a stronger solver or LLM assistance may be needed; none was used in the reported results. We will state this explicitly.

Q3. (a) We have no controlled reward-sensitivity analysis; the informal observation above is all we have. (b) We have not trained with alternative reward designs, such as a proportional reward. (c) See W2 above and C1.

Thank you for your response. However, I still believe that the ablation studies are insufficient without (c) formal premises plus structured output, without the verification reward. And while I appreciate the authors' willingness to add the missing details, I still have some concerns about the completeness of the original submission, as the exact prompts and the provers used in the experiments were not clearly reported.

Therefore, I will maintain my current score.

Best,

Reviewer mBBs

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

This paper proposes PRoSFI, a method for improving the logical soundness of LLM reasoning through formal verification. Instead of generating complete formal proofs, the model produces natural-language reasoning along with structured FOL representations of intermediate reasoning steps. These steps are verified using formal provers, and the verification results are incorporated into GRPO rewards. Experiments demonstrate substantial improvements in reasoning soundness while maintaining competitive answer accuracy.

Critical strengths

1. Clear motivation and reasonable methodology. The paper addresses an important limitation of outcome-based RL, which does not guarantee the logical validity of intermediate reasoning steps. Introducing structured FOL representations provides a practical alternative to generating complete formal proofs, and the proposed method is well aligned with the motivation.

2. Significant improvements in reasoning soundness. PRoSFI substantially improves GPT-based Soundness on ProverQA-Hard (21.97% → 76.07%) and ProverQA-Extra (11.87% → 56.10%). The comparison with Direct Lean Generation further supports the effectiveness of the proposed approach.

Critical weaknesses

1. Lack of semantic faithfulness guarantees. The formal verifier checks the logical validity of structured FOL steps but does not verify their semantic consistency with the natural-language reasoning. Therefore, the model could produce valid FOL representations while its actual reasoning contains logical errors, potentially undermining the main objective of the paper.

2. Insufficient ablation studies. PRoSFI differs from the Outcome-CoT baseline in multiple aspects, including input information, output structure, and reward function. Thus, it is unclear whether the improvements come specifically from formal verification rewards or simply from generating structured reasoning representations. An ablation using the same input/output format without formal verification rewards would help clarify this.

3. Unclear soundness evaluation protocol. The paper does not clearly specify whether GPT-OSS-120B evaluates only the natural-language CoT or also receives the structured FOL representations. If the latter, PRoSFI may benefit from additional information unavailable to the baseline, potentially introducing evaluation bias. The authors should clarify this and ensure a fair comparison.

Questions for authors

My main questions are included in the Weaknesses section above.

1 comment
AuthorsOpenReview ↗

Response to Reviewer ewfE

Thanks for the constructive reviews. Here are our point-by-point responses.

W1 (no semantic-faithfulness guarantee). We agree, and we do not claim such a guarantee. Section 3, Limitations and the Ethics Statement all say that verification holds only within the formal representation. Three facts bound how large the gap can be:

  1. The model does not formalize the problem. The formal premises and the formal goal are given to it (Appendix E.2), and its final step must match the given goal. The model therefore cannot pass verification by mis-formalizing the problem. The remaining gap is between its own <think> text and its <summary>.
  2. Soundness is measured independently of the verifier. The headline metric is scored by a judge that plays no part in the reward and sees only the natural-language <think> reasoning (C2). If the model satisfied the prover while reasoning unsoundly in natural language, judged Soundness would not rise. Instead it rises from 21.97% to 76.07% on Hard and from 11.87% to 56.10% on Extra.
  3. The gap is not zero, and our data show it. Reward Hit and judged Soundness correlate at 0.71 / 0.63, not 1, and PRoSFI's judged Soundness on Extra is 56.10%.

Our claim is that soundness improves, not that verified intermediates certify the natural-language reasoning. We will revise any wording that suggests the stronger claim.

W2 (ablations). See C1. All methods receive the same input, so "input information" is not a confound between PRoSFI and Outcome-CoT. You are right that output structure and reward still change together. The control you describe, the same output format without the verification reward, is not in the paper, and we will qualify our attribution accordingly.

W3 (judge protocol). The judge receives only the problem (with the same formal premises for every method) and the <think> reasoning; PRoSFI's structured summary is never shown to it. See C2, including the remaining stylistic caveat.

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

This paper investigates how to enable smaller-scale LLMs to generate step-by-step verifiable reasoning trajectories without writing complete formal proof scripts. The authors propose PRoSFI (Process Reward over Structured Formal Intermediates). The model generates natural language reasoning and transforms each step into a smaller proof problem, which is then verified by a formal prover. The reward combines the correctness of the answer, the output format, and the verification result of the complete structured reasoning chain.

Critical strengths
  • Generating statements with dependencies reduces the need to write complete proof scripts and organize tactics. The id, dependencies, and conclusion fields also allow the verifier to examine individual reasoning steps, not just the final answer.

  • This paper distinguishes between Answer Correct Rate, Reward Hit Rate, and Soundness, and points out that a validated formal summary may not cover all aspects of natural language reasoning.

Critical weaknesses
  • Section 5.1 states that Outcome-CoT accepts indexed formal premises, but Appendix D only shows natural language inputs.

  • Appendix G only manually reviewed 10 outputs for each method; the sample size is too small to rule out the possibility of bias in evaluation based on specific format, length, or writing style. Furthermore, formal summaries may also miss errors in natural language inference.

Questions for authors

Please clarify that the Knights and Knaves experiment retrains the model on another task, and report the training and test sizes. This tests the method on a new task, not direct transfer of the ProverQA-trained model. Please also note that removing Uncertain cases limits the ProverQA results to True/False reasoning rather than the full three-class task.

2 comments
AuthorsOpenReview ↗

Response to Reviewer NXEa

Thanks for the reviews. Here are our point-by-point responses.

W1 (Section 5.1 vs. Appendix D). Thank you for catching this. Section 5.1 is correct: Outcome-CoT receives the same indexed formal premises as PRoSFI, and Appendix D will be replaced with the full prompt. See C1.

W2 (audit size; formal summaries may miss natural-language errors). We agree with both points, and the paper states both. On audit size, see C2. On coverage, Section 3 says that Reward Hit "does not necessarily guarantee the Soundness of the entire reasoning path", because the extracted propositions may not cover the whole path. Limitations repeats that verification "does not guarantee alignment with the natural-language reasoning". This is why Table 2 reports judged Soundness rather than Reward Hit. Our own data show the gap you describe: Reward Hit and judged Soundness correlate at 0.71 / 0.63 (Figure 3), well below 1.

Q: Knights and Knaves. The K&K model is trained on K&K in a separate run with its own learning rate and schedule (Section 6); it is not the ProverQA-trained checkpoint. In the Section 6 title, "generalizes" means the method applies to a second task. The only out-of-distribution claim is to the 2ppl and 8ppl splits within K&K, following the Logic-RL protocol. We will retitle the section and say this explicitly.

  • K&K data come from the public Hugging Face dataset K-and-K/knights-and-knaves. Training uses the 3ppl–7ppl training splits (1,000 puzzles each, 5,000 in total). Each test level has 100 puzzles.
  • ProverQA uses 769 training instances and 64 test instances per difficulty level. Extra has 128 instances.
  • Every test instance is sampled 16 times and the results are averaged.

Q: Removing Uncertain. Section 5 and Appendix B.1 state the exclusion, but it should be more prominent: all ProverQA results are for binary True/False classification, not the full three-class task. We will say so in the abstract, the introduction and the caption of Table 2.

The paper gives difficulty imbalance as the reason for the exclusion. There is also a limitation of the current formulation that we should have stated. PRoSFI certifies a derivation of the goal or of its negation. "Uncertain" means that neither is derivable, which needs a different kind of evidence, such as a countermodel for each. We have not implemented that, and we will add it to Limitations.

On novelty. Step-level rewards are not new, and we do not claim they are. Our claim is narrower. At 7B, asking the model for complete formal proofs yields almost no prover signal: Direct Lean reaches a Reward Hit Rate of 13.77% (Hard) and 4.35% (Extra) with the same input and reward. Asking only for formal intermediate conclusions with declared dependencies is what makes prover feedback usable in RL.

We thank the authors for their detailed response. However, these clarifications do not fully address my concerns. (1) The primary result of the paper is an improvement in the Soundness of natural-language reasoning. Yet this metric remains heavily reliant on an LLM-based judge. Furthermore, the human audit of only ten outputs per method is insufficient to establish the reliability of the reported gains. (2) The fact that a structured formal summary passes verification does not imply that it fully covers or faithfully represents the natural-language reasoning. The correlation between Reward Hit and GPT-judged Soundness depends on the same LLM judge and therefore does not fully resolve this concern. (3) While the current comparisons provide evidence for the overall effectiveness of the PRoSFI configuration, they are insufficient to disentangle the respective contributions of structured output and formal-verification rewards. The Direct Lean Generation baseline changes both the output representation and the verification backend. It cannot substitute for a control that keeps the PRoSFI output format but trains with an outcome-only reward. Consequently, we maintain our original rating.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Common response to all reviewers

We thank the reviewers for their careful reading. Two issues were raised by more than one reviewer, so we answer them once here.

C1. All methods receive the same input; what differs (NXEa W1, ewfE W2, mBBs W2)

In all three methods (Outcome-CoT, Direct Lean Generation and PRoSFI) the model receives the same problem with the same indexed FOL premises. For Direct Lean Generation the premises are also rendered in Lean 4 so that the proof can be compiled. We will replace Appendix D with the exact prompt used.

The methods therefore differ only in what the model outputs and how it is rewarded, not in what it is given:

MethodInputOutputReward
Outcome-CoTindexed FOL premisesNL reasoning + answeranswer + format
Direct Lean Generationsame, rendered in Lean 4NL reasoning + complete Lean 4 proofPRoSFI schedule; proof checked by the Lean 4 compiler
PRoSFIsameNL reasoning + structured intermediatesPRoSFI schedule; each step checked with Z3

What the existing results isolate:

  • Output form, with input and reward held fixed. Direct Lean Generation and PRoSFI have the same input and the same reward schedule. Direct Lean reaches a Reward Hit Rate of only 13.77% (Hard) and 4.35% (Extra), and judged Soundness of 33.11% / 10.45%, against 76.07% / 56.10% for PRoSFI. A prover-based reward alone is therefore not enough; whether it becomes a usable training signal depends on the output form.
  • Formal premises in the input. Outcome-CoT already receives the formal premises. Formal input alone yields 21.97% / 11.87% judged Soundness.
  • The verifier signal within a fixed format. Figure 3 is computed on PRoSFI outputs only. Reward Hit correlates with judged Soundness at 0.71 (Hard) and 0.63 (Extra), against 0.47 / 0.33 for answer correctness. Figure 2 shows that selecting verifier-approved samples raises Soundness as N grows.

What they do not isolate: the paper has no run that keeps the PRoSFI output format but trains with an outcome-only reward. We will state it in Limitations and reword Section 5.3, which currently attributes the gain to "stepwise formal rewards", so that it attributes the gain to the PRoSFI configuration as a whole.

C2. What the GPT judge sees, and how far the Soundness metric can be trusted (ewfE W3, NXEa W2)

For every method, the judge receives the same two things: (i) the original problem, including the indexed FOL premises, and (ii) the natural-language reasoning inside <think>…</think>. It never sees PRoSFI's <summary> JSON or Direct Lean's Lean proof. PRoSFI therefore has no information advantage at evaluation time. We will state this in Appendix G.

One difference remains that the protocol does not remove. After training, PRoSFI's <think> text tends to cite premise identifiers and formulas explicitly (Appendix E.3), so its style differs from the baseline's. The judge could react to that style.

On the human audit, Our Limitations section already describes this as "only a sanity check rather than large-scale validation". The judge agreed with our reading on all 10 Outcome-CoT outputs. On PRoSFI, both of its disagreements were stricter than our reading (one step cited an unnecessary premise; one misnamed the inference rule). We saw no leniency toward PRoSFI. However, 20 examples cannot rule out a bias from format, length or style, and we do not claim they do. The Soundness numbers should be read as approximate.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.