acceptodds
Under review as a conference paper at ICLR 2027

Interleaving and Process-Supervising Logical Reasoning with Verifiable Reasoning Structure

Abstract

Large language models have demonstrated strong reasoning capabilities through Reinforcement Learning with Verifiable Rewards (RLVR). However, RLVR typically uses outcome correctness as a binary reward and lacks a strict check on the logical validity of intermediate steps, which matters more in logical reasoning. In this paper, we propose VERST (VErifiable Reasoning Structure Training), a training framework that obtains a process supervision signal from a symbolic solver's strict verification. The framework introduces a lightweight verifiable structure of atomic facts and explicit inferences, which can be easily translated into SMT-LIB format and verified by a symbolic solver. Based on this, our two-stage approach applies: In Reasoning Structure Learning stage, the model is trained to interleave this structure with natural language by supervised fine-tuning. In Process-supervised RLVR stage, reinforcement learning is performed with a process reward scored by a symbolic solver on the generated structure. On five logical reasoning benchmarks, VERST improves Qwen3-4B-Instruct-2507 from to , outperforming Qwen3-235B-A22B () and becoming competitive with DeepSeek-V4-Pro-0813 () and GPT-5.6-sol (). Further analysis shows that it improves process quality and brings the impact to other reasoning domains.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
logical reasoning, Large Language Model, process supervision, symbolic verification

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_EyMWOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes VERST, a framework to obtain process rewards from a formal solver. The novelty lies in the simpler structure representation that can be formalized more easily and in the active path tracking.

Critical strengths

The presentation is okay, and the method seems sound. The performance outperforms the baseline in the experiments.

Critical weaknesses

Writing needs a lot of improvement, and some design choices are not specified or motivated. For example, the paper mentions in the introduction that it designs a simpler structure that can be formalized more easily, but it has not mentioned how and why it is easier to be translated. Besides, active facts and inferences seem to be another technical contribution, but the paper does not describe how it is implemented. Furthermore, it mentions “annotator is asked to stick to” in line 210, but I have no idea why it needs this annotator and how it works. Also, the consistency check in sec 5.4 does not seem to be mentioned in the methodology as well.

Questions for authors
  1. Do you have a human agreement rate with the LLM-judge in sec 5.3?
  2. I don’t understand Section 5.4. Are you checking the consistency between the original NL and the VERS structure? And I cannot follow the experiment you describe between lines 425 and 427. I think you need to explain why this is examining the consistency.
2 comments

We sincerely thank you for the careful reading and the constructive comments. We accept your criticism on the presentation, and we apologize for not explaining the choice and motivation of each design clearly. Below we explain these designs one by one and report a human agreement check for the LLM judge. We have revised the paper according to your suggestions.

Reply to Weakness 1

  1. How and why VERS makes formalization easier.

Natural-language reasoning is free-form: a single step mixes several facts with the inferences among them and contains vague references and anaphora, so the translator does not translate individual sentences. It must first recover the structure of the reasoning and extract the relevant statements. VERS represents this structure with atomic facts and explicit inferences, so translating a VERS reduces to translating individual atomic statements, at which LLM-based translators are already reliable. We have revised the introduction to explain this motivation.

  1. Details of the active inference check and the consistency check.

In Section 3.1.3 we introduced two notions, active facts and inferences, and consistency, which correspond to the two check components of the VERS Reward, namely the active inference check and the consistency check. They are also what Section 5.4 analyzes. Below we describe how the two components are implemented.

  • Consistency check. An off-the-shelf LLM is called for every step and returns a binary judgment on whether sis_i is consistent with nin_i, following the prompt in Appendix F.3, and only consistent steps are verified and rewarded.
  • Active inference check. Starting from the answer fact aa, we mark the facts and inferences that support it as active, recursively mark those that support active facts, and mark the rest as dead, and only active inferences can receive positive reward.

Both checks are critical for preventing reward hacking during RL. We have revised Section 3.1.3 to define the two components explicitly and added the ablation of the active inference check to Section 5.4.

  1. Why an annotator is needed, and how it works.

Writing a correct VERS for a natural-language reasoning step is non-trivial, and we therefore use an LLM with strong language understanding to annotate the VERS structures, so that the resulting annotations are of sufficient quality to serve as training data for reasoning structure learning. The procedure is as follows: we sample step-by-step chain-of-thoughts with step markers from the base model, pass the whole chain to the annotator, the annotator returns a VERS that follows the definition for each step, and the structures are then merged after the corresponding steps to obtain the reasoning traces with VERS. We have revised Section 3.2.1 to describe this procedure.

We thank you again for pointing out these issues in the paper. If anything remains unclear, please let us know, and we would be happy to explain it further and to improve the paper.

Reply to Question 1

We sampled 20 of the 100 problems in Section 5.3, collected the responses of Base, Outcome RL and VERST on them (60 responses in total), and manually scored them with the same rubric. The table reports the absolute difference ∣d∣|d| between the human score and the LLM score.

Dimension∣d∣=0\lvert d\rvert=0∣d∣≤1\lvert d\rvert\le 1∣d∣≤2\lvert d\rvert\le 2Mean ∣d∣\lvert d\rvertStd. ∣d∣\lvert d\rvert
Validity82%95%98%0.250.60
Faithfulness75%90%95%0.470.75
Completeness78%93%97%0.320.62
Conciseness67%85%97%0.550.80
Average score25%98%100%0.370.33

On the average process score, 98% of the responses have ∣d∣≤1|d| \le 1 and the mean difference is 0.37, which indicates that the LLM judge agrees closely with human scoring. The human scores of the three models also agree with the ranking of the LLM judge in Table 2 in paper:

ModelValidityFaithfulnessCompletenessConcisenessAvg.
Base4.353.954.552.953.95
Outcome RL4.153.704.452.503.70
VERST4.554.204.802.954.12

We have added this agreement analysis to Appendix E.3.

Reply to Question 2

We apologize for the confusion. The consistency check is a component of the VERS Reward, and it checks the consistency between the VERS structure and the original natural-language reasoning, including whether each inference corresponds to a derivation the natural language actually uses, whether each fact is equivalent to the information used in the natural language, and whether the granularity of the structure matches that of the reasoning.

The motivation for the consistency check is to avoid reward hacking. Since the reward is computed on the VERS that the model itself generates, the model can learn during RL to generate a VERS that is inconsistent with its natural-language reasoning but still passes formal verification, which earns a higher reward without improving the reasoning. The VERS then no longer reflects the natural-language reasoning, the formal verification result becomes unreliable, and the quality of the natural-language reasoning does not really improve.

Section 5.4 is the ablation of this component, and lines 425–427 in original paper describe the design of the experiment. It records, at each epoch of RL, the training reward together with a reasoning quality that is assessed independently on the natural-language reasoning alone (Figure 6). Without the consistency check, the reasoning quality does not rise together with the reward. With the check, the two rise together, which supports our claim that the consistency check prevents reward hacking.

Reviewer_aCLtOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

VERST trains language models to interleave natural-language reasoning with explicit facts and inference edges. Following structure-learning SFT, it combines outcome rewards with process supervision based on SMT translation, Z3 verification, and language–structure consistency checks. Across five logical-reasoning benchmarks, Qwen3-4B’s average accuracy improves from 75.2% to 86.5%, compared with 83.5% for Outcome RL. Further analyses examine formalization success, reasoning quality, and out-of-distribution generalization.

Critical strengths
  1. The representation substantially improves formalization success. Using VERS rather than natural-language steps increases Translator-4B’s valid SMT-LIB generation rate from 17% to 93% (§5.1, Figure 3A), providing a practical basis for incorporating solver feedback into training.
  2. Accuracy gains and ablations support the overall pipeline. Table 1 reports higher average accuracy than the backbone and prior training methods. Figure 4A shows that removing consistency checking increases training reward without corresponding improvements in independently assessed reasoning quality. However, the Outcome RL comparison does not isolate the process reward, as the methods use different initializations (§C.2).
Critical weaknesses
  1. Premise grounding is not established by the described checks. Appendix A.1 permits P-facts without incoming inferences, while the consistency judge receives the current step, its structure, and cited facts—not the original problem premises (Appendix F.3). An unsupported premise repeated in both representations may therefore pass consistency checking. Z3 can validate the resulting local entailment without establishing that the derivation follows from the original problem. A correct final label does not resolve this gap.
  2. Formalization success does not establish reward reliability. The 93% rate in §5.1 measures valid SMT-LIB output, not semantic fidelity or the correctness of the resulting reward judgments. The natural-language quality evaluation in §5.3 is informative but does not directly audit the translation-and-verification pipeline. Such validation is important to substantiate the central claim of reliable process supervision.
Questions for authors
  1. Premise grounding: Is there an additional check linking P-facts to the original premises or justified background knowledge? Please demonstrate how the implemented reward handles a few diagnostic traces containing an unsupported premise in both natural language and VERS while retaining the correct final answer. No additional training is requested.
  2. Reward reliability: Could the authors audit a small sample of saved steps receiving positive process rewards, such as 50, using their original problems and dependencies? Please assess premise grounding, translation fidelity, and inference validity, describe the sampling procedure, and distinguish incorrect reward judgments from translation failures. The same sample could address both concerns.
2 comments

We sincerely thank you for the detailed reading and the concrete suggestions. We acknowledge your recognition of the improvement in formalization success, the accuracy gains and the ablations, as well as your concern regarding premise grounding and the reliability of the reward signal. Below, we address these concerns one by one.

Reply to Weakness 1 and Question 1

We acknowledge that there is no additional check that ensures the premise grounding of the P-facts. Therefore, for a step whose natural language and VERS both contain the same unsupported premise, it may receive positive reward.

However, compared with standard outcome-based RLVR, which cannot distinguish two responses that both reach the correct answer, VERST already shows an improvement. Tabel 1 and Tabel 2 in paper show that VERST outperforms the OutcomeRL baseline in both answer accuracy and reasoning quality.

We also agree that an additional check on premise grounding would make the verification more complete and would let it identify more errors. A direct remedy is to collect all facts with no incoming inference and ask an LLM to judge, for each of them, whether it is supported by the original premises or is justified background knowledge. We will address it in future work.

Reply to Weakness 2 and Question 2

We agree that the results in Section 5.1 are not sufficient to establish the semantic fidelity of the translation and the correctness of the resulting reward judgments. Following your suggestion, we therefore manually audited a sample of the steps that received positive reward.

Sampling procedure and criteria.

We randomly sampled 100 steps that received positive process reward from the trajectories saved during RL training, twice the suggested number. For each step we made three independent judgments:

  1. Premise grounding: whether every fact used is supported by the original problem.
  2. Translation fidelity: whether the translation preserves the meaning of the fact.
  3. Inference validity: whether the inference from the source facts to the target fact is valid.
DimensionPass rate
Premise grounding91%
Translation fidelity95%
Inference validity97%

Of the 100 positively rewarded steps, 12 received an incorrect reward judgment: 9 use ungrounded premises, and 3 have invalid inferences but pass the verification because the translation is unfaithful.

The reward of VERST is reliable in most cases. Although the check on premise grounding is missing, ungrounded premises appear in only 9 of the 100 audited steps, and 88% of the positively rewarded steps passed the manual audit. This indicates that the translation-and-verification pipeline provides a largely reliable process reward.

Thank you for the clarification and the 100-step audit. The audit is useful, but it also confirms a central concern: 12% of positively rewarded steps received incorrect reward judgments, including 9 cases with ungrounded premises and 3 cases where translation errors masked invalid inferences. Since premise grounding is currently not checked, these are not merely rare formatting failures but direct errors in the process reward used for RL training. The proposed grounding check is left for future work, and the current results do not quantify how these incorrect rewards affect training or final performance. Therefore, I will keep my rating at 2.

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

The paper presents a promising training approach that obtains a process supervision signal from a symbolic solver’s strict verification. It shows improvement over 5 logical reasoning tasks.

Critical strengths
  1. The paper clearly identifies the weakness of existing RLVR pipelines and proposes a solution what shows improvement over the baselines.
Critical weaknesses
  1. I have concerns over the verification pipeline: VERST checks local entailments inside a model-generated representation without clearly establishing that this representation is grounded in the original problem, faithfully translated, and sufficient to justify the final answer. Thus, I am not sure if VERST is the optimal design.

  2. Four training benchmarks (QMFOL, FOLIO, ProofWriter, and ProverQA) include an Unknown label. However, the verification procedure in Section 3.1.2 is described primarily as checking positive entailment between source facts and a target.

Questions for authors

Could you provide a complete Unknown example, including the original premises, VERS trace, translated assertions, solver calls, and resulting step rewards?

1 comment

We sincerely thank you for the careful reading and the constructive feedback. We acknowledge your recognition of the weakness identified in existing RLVR pipelines and of the improvement over the baselines, as well as your concern regarding the soundness of the verification pipeline. In light of your concerns, we first clarify what VERST does and does not verify, then describe how responses with the Unknown label are processed, and finally provide the complete Unknown example.

Reply to Weakness 1

We first address your three sub-questions on the VERS representation in turn.

  1. Is it grounded in the original problem? No. VERST does not check whether the facts it uses are grounded in the original problem.
  2. Is it faithfully translated? Largely yes. In 100 manually checked translations from VERS to SMT-LIB, only 5% were unfaithful.
  3. Is it sufficient to justify the final answer? Not necessarily. The local entailments checked by VERST are not equivalent to a complete argument for the answer.

We acknowledge that VERST verifies only the local entailments within the reasoning, and that this may therefore miss errors that do not manifest as an invalid local entailment. However, compared with standard outcome-based RLVR, which cannot distinguish two responses that both reach the correct answer, VERST already shows an improvement. Table 1 and Table 2 in paper show that VERST outperforms the OutcomeRL baseline in both answer accuracy and reasoning quality.

We do not claim that the design of VERST is optimal. It is an improvement over standard outcome-based RLVR by adding a process reward computed from formal verification. Considering more possible error cases in the verification pipeline, instead of checking only the validity of local entailment, is one direction of our future work.

Reply to Weakness 2 and Question 1

For a problem with the Unknown label, the reasoning is not entirely made of entailments between logical objects. For example, a reasoning step may take the form "The premises do not mention X, so the answer is Unknown". To accommodate such steps, the VERS definition deliberately admits a broader form of facts and inferences: the prompts in Appendix F.1 and F.3 allow a fact to be a natural-language statement about the problem or about the reasoning itself, and allow an inference to be a causal link rather than a strictly logical entailment. A VERS may therefore contain facts such as "P1: The premises do not mention X". For such facts, the translator outputs a placeholder UNFORM for them, and any inference that uses an UNFORM fact skip the verification.

However, a response with the Unknown label is not left without a verification signal. Because the model does not output Unknown directly: it reasons through the premises before it concludes that they do not determine the answer, and those earlier steps are ordinary local entailments that the solver still checks. We counted the inferences that skip the verification because they cite an UNFORM fact, grouped by the answer label of the response:

Answer labelInferences with UNFORM facts
Unknown31.4%
Other labels8.4%

Among the responses that answer Unknown, 68.6% of the inferences still receive a verification signal, which is already a substantial improvement over outcome-based RLVR. We acknowledge that the current design may therefore miss errors that occur inside the remaining 31.4% inferences, and extending the verification to them is one direction of our future work.

As requested, we give a complete Unknown question from ProverQA in Appendix A.4 including the original premises, the VERS trace, the translated assertions, the solver calls, and the resulting step rewards.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Key updates of the paper

Thank all the reviewers for their comments, questions and suggestions. In this global response, we summarize the key updates we have made to the paper based on your feedback. All changes have been marked in blue in the updated PDF.

Introduction

We rewrote the introduction so that the design choices are better explained. It now states the practical obstacle to using formal verification for training, namely that a solver only reads a fixed format while the reasoning of the model is unstructured text, and explains why VERS removes this obstacle. The contributions of the paper are also stated more clearly.

We also split Figure 1 of the submitted version into two figures. In the updated version, Figure 1 introduces the problem, a trace whose final answer is correct while a middle step is not, and Figure 2 presents the VERS structure of one step together with its verification procedure.

Updated Method: More details about the implementation

  1. Handling of the Unknown label: In Section 3.1.2, we added the case of a fact that cannot be written as an SMT-LIB assertion, which is more frequent in responses with the Unknown label. The translator marks such a fact with the placeholder UNFORM, and an inference that cites it skips the verification.

  2. Two checks of the VERS reward: In Section 3.1.3, we now introduce the two checks of the VERS reward explicitly. The consistency check asks an off-the-shelf LLM whether the VERS of a step matches the natural-language reasoning of that step, and only consistent steps are verified and rewarded. The active inference check marks the facts and inferences that support the answer as active, and only inferences that contribute to the answer can receive a positive reward. Both checks serve to prevent reward hacking during RL.

  3. Details about the annotator: In Section 3.2.1, we detailed the motivation for choosing the annotator and the specific annotation procedure.

Updated Analysis: Ablation of the Active Inference Check

In Section 5.4, we supplemented the existing ablation of the consistency check with the ablation of the active inference check, so that the contribution of the two checks is clearer. Without either check, the training reward no longer rises together with the independently judged reasoning quality, which shows their role in preventing reward hacking.

New Appendix A.4: A complete example with the Unknown label

In response to Reviewer uJZy's question, we added Appendix A.4, which gives one complete example with the Unknown label from ProverQA, including the original premises, the VERS trace, the translated assertions, the solver calls, and the resulting step rewards.

New Appendix E.3: Human agreement rate with the LLM judge in Section 5.3

In response to Reviewer EyMW's question, we added Appendix E.3, which audits the LLM judge used in Section 5.3. The results show that the LLM judge closely matches human judgements, which supports its use in the analysis of Section 5.3.

AuthorsOpenReview ↗

Brief summary of our contributions and the discussion period

Dear Area Chair,

We thank you for your time and for handling our submission. Below, we summarize the core contributions of our work and the key points of the discussion period.

Our Contributions

  1. Designing VERS, a verifiable reasoning structure that is easier to translate into the SMT-LIB format for formal verification than unstructured natural language. (Section 3.1)
  2. Proposing VERST, a two-stage training method based on VERS that obtains a step-level process supervision signal from formal verification and uses it in RLVR. (Section 3.2)
  3. Training a 4B model that outperforms a model from the same family roughly 50 times its size and surpasses existing training methods. (Section 4)
  4. Conducting empirical analyses of each component of VERST and demonstrate its generalization to unseen datasets and its effect on other reasoning domains. (Section 5)

Summary of the discussion period

Strengths highlighted by the reviewers:

  • The paper identifies a clear weakness of outcome-only RLVR, and the proposed pipeline improves over the baselines. (uJZy, aCLt, EyMW)
  • The verifiable reasoning structure substantially improves formalization success over natural-language steps. (aCLt)
  • Accuracy gains and ablations support the overall pipeline. (aCLt)

We have provided responses to every Weakness and Question raised by the three reviewers. We summarize the important ones below:

Response to Reviewer uJZy:

  • Clarified the scope of the verification and the main claim of the method.
  • Explained how responses with the Unknown label are processed, and revised Section 3.1.2 to describe it.
  • Added Appendix A.4 with a complete Unknown example, including the original premises, the VERS trace, the translated assertions, the solver calls, and the step rewards.

Response to Reviewer aCLt:

  • Clarified the scope of the verification, and emphasized the improvement over standard outcome-based RLVR.
  • Reported a manual audit of positively rewarded steps along premise grounding, translation fidelity, and inference validity, which shows that the reward is reliable in most cases.

Response to Reviewer EyMW:

  • Specified the design choices of VERST and explained their motivation, and revised the introduction, Section 3.1.3, and Section 3.2.1.
  • Added Appendix E.3 with a human agreement audit of the LLM judge in Section 5.3.
  • Detailed the experimental design of Section 5.4 and explained the motivation of the consistency check.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.