💬 NLP

Efficient PRM Training Data Synthesis via Formal Verification

This paper introduces FoVer, a framework that efficiently synthesizes high-quality Process Reward Model (PRM) training data by leveraging formal verification tools to automatically annotate step-level errors in formal reasoning tasks, thereby improving PRM performance across diverse natural language reasoning benchmarks without requiring human annotation or additional LLM calls.

Original authors: Ryo Kamoi, Yusen Zhang, Nan Zhang, Sarkar Snigdha Sarathi Das, Ranran Haoran Zhang, Wenpeng Yin, Rui Zhang

Published 2026-04-10

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Ryo Kamoi, Yusen Zhang, Nan Zhang, Sarkar Snigdha Sarathi Das, Ranran Haoran Zhang, Wenpeng Yin, Rui Zhang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Problem: Teaching AI to "Think" Step-by-Step

Imagine you are teaching a very smart, but slightly chaotic, student (an AI) how to solve a complex math problem. The student doesn't just give you the final answer; they write out their entire thought process on a whiteboard.

To help the student get better, you need a Process Reward Model (PRM). Think of a PRM as a strict, super-attentive tutor who walks down the line of the student's work, step by step, and puts a green checkmark (✅) or a red X (❌) on every single line.

The Catch:
Currently, creating this "super-tutor" is a nightmare.

Human Annotation: You have to hire real humans to read thousands of math problems and check every single step. This is incredibly expensive and slow. Plus, humans get tired and disagree with each other (is this step really wrong?).
Monte Carlo Roll-outs (The "Guessing Game"): To avoid hiring humans, some researchers ask the AI to solve the problem 100 different ways. If 90 of those ways lead to the right answer, they assume the first step was good. This is like flipping a coin 100 times to see if it's fair. It's computationally expensive (wastes a lot of electricity) and often gives "noisy" (uncertain) results.

The Solution: FOVER (The "Math Police")

The authors propose a new framework called FOVER. Instead of using tired humans or a coin-flipping guessing game, they use Formal Verification Tools (like Z3 and Isabelle).

The Analogy: The Unblinking Robot Judge
Imagine a robot judge that speaks a strict, unambiguous language (Formal Logic).

If you say, "The sky is blue," the robot checks its database of facts.
If you say, "2 + 2 = 5," the robot instantly screams "FALSE!" with 100% certainty.
It doesn't get tired, it doesn't have an opinion, and it doesn't need to flip a coin.

How FOVER Works:

Translation: The AI (the student) solves a problem, but it has to write the solution in a strict, formal language that the Robot Judge understands (like writing code instead of a casual essay).
The Audit: The Robot Judge (Z3 or Isabelle) reads the AI's step-by-step solution. Because the language is strict, the Robot can mathematically prove whether Step 1 leads to Step 2, and if Step 2 is true.
The Label: The Robot instantly stamps every step with a perfect ✅ or ❌.
The Training: The "Super-Tutor" (PRM) is trained on these perfect Robot labels.

The Magic Trick: "Formal-to-Informal" Transfer

Here is the most surprising part of the paper.

The Robot Judge only understands Formal Logic (strict math and symbols). But in the real world, we ask AI to solve Informal Problems (word problems written in natural English, like "Sarah went to the art show...").

The Analogy: Learning Chess to Play Poker
Usually, you think learning Chess (strict rules) won't help you play Poker (bluffing and psychology). But FOVER shows that training the AI on the strict, perfect rules of Chess actually makes it a better Poker player.

Why?

By learning to spot a logical error in a strict math proof, the AI learns the fundamental structure of reasoning.
It learns to say, "Wait, if A is true, B must be true. If the next step says C, that's a break in the chain."
This skill transfers! Even when the AI is reading a casual English story, it can now spot logical gaps it would have missed before.

The Results: Faster, Cheaper, Better

The paper tested this on 12 different reasoning benchmarks (math, logic, reading comprehension).

Cost: FOVER is cheap. It doesn't need humans. It doesn't need the AI to guess 100 times. It just runs the Robot Judge once.
Accuracy: The labels are 100% correct because they are mathematically proven.
Performance: The AI trained with FOVER beat the AI trained with human labels or the "guessing game" method. It got better at math, logic, and even general reasoning tasks it had never seen before.

Summary in One Sentence

FOVER teaches AI to be a better reasoning tutor by having it practice on strict, robot-verified math proofs, which surprisingly makes it much better at spotting errors in everyday language problems, all without needing expensive human teachers.

1. Problem Statement

Process Reward Models (PRMs) are critical for improving Large Language Model (LLM) reasoning by providing fine-grained supervision at the step level of a reasoning trace. However, constructing high-quality PRM training data faces two major bottlenecks:

High Cost: Traditional methods rely on human annotation, which is expensive and suffers from low inter-annotator agreement (e.g., discarding 30% of data due to disagreement).
Noise and Inefficiency: Automated alternatives like Monte Carlo (MC) roll-outs (e.g., Math-Shepherd) require multiple LLM calls per step to estimate correctness. This is computationally expensive and produces noisy, probabilistic labels rather than ground truth.

The core challenge is how to synthesize accurate, step-level error labels for PRM training efficiently, without relying on expensive human labor or noisy sampling methods.

2. Methodology: The FOVER Framework

The authors propose FOVER (Formal Verification for PRM), a framework that synthesizes PRM training data by leveraging formal verification tools to annotate step-level errors in formal reasoning tasks.

Core Mechanism

Instead of relying on probabilistic sampling or human judgment, FOVER uses deterministic formal solvers to verify the logical validity of each reasoning step.

Task Selection: The framework focuses on formal reasoning tasks where ground truth can be mathematically proven:
- Formal Logic: First-order logic entailment tasks (using the FLDx2 dataset).
- Formal Theorem Proving: Mathematical word problems converted into formal proofs (using GSM8K, MetaMathQA, and Big-Math).
Data Synthesis Pipeline:
- Step 1 (Generation): An LLM (e.g., Llama 3.1 8B or Qwen 2.5 7B) generates a step-by-step formal solution to a problem.
- Step 2 (Verification): A formal verification tool checks the logical validity of each individual step independently.
  - Tools Used: Z3 (SMT solver) for formal logic and Isabelle (Interactive Theorem Prover) for theorem proving.
  - Logic: For a step $s_i$ , the tool checks if the premises (context + previous steps) logically entail the conclusion of $s_i$ . If the implication is valid, the label is correct (1); otherwise, incorrect (0).
- Step 3 (Training): The resulting dataset, FOVER-40K (40,000 steps), is used to fine-tune LLMs to act as PRMs. The model learns to predict binary labels ("correct"/"incorrect") for each step.

Key Technical Adaptation

While tools like Z3 and Isabelle are typically designed for solution-level verification (checking the final answer), FOVER adapts them for step-level verification.

For Z3: It constructs a logical formula combining the premises and the negation of the current step's conclusion to test for satisfiability.
For Isabelle: The authors implement wrapper code that inserts sorry (a placeholder for unproven steps) for all steps except the target one, allowing the prover to verify the specific step in isolation.

3. Key Contributions

FOVER Framework: A novel method for generating accurate PRM training data using formal verification, eliminating the need for human annotation or repeated LLM calls (MC roll-outs).
FOVER-40K Dataset: A large-scale dataset of 40,000 reasoning steps with ground-truth error labels derived from Z3 and Isabelle, covering formal logic and theorem proving.
Formal-to-Informal Transfer: Demonstrated that PRMs trained on formal (symbolic) data generalize effectively to informal (natural language) reasoning tasks.
Cross-Task Generalization: Showed that PRMs trained on logic/math tasks improve performance on completely different domains like Natural Language Inference (NLI) and Big-Bench Hard (BBH).

4. Experimental Results

The authors evaluated FOVER-PRMs (fine-tuned on FOVER-40K) against baselines (raw LLMs and existing PRMs trained via human annotation or MC roll-outs) across 12 benchmarks.

Formal-to-Informal Transfer (RQ1):
- On informal logic (FOLIO, LogicNLI) and math (GSM8K, MATH, AIME) benchmarks, FOVER-PRMs significantly outperformed baseline PRMs.
- Example: On the MATH dataset, FOVER-Llama3.1-8B-PRM achieved 66.2% Best-of-7 accuracy vs. 53.0% for the baseline.
- On ProcessBench (step-level error detection), FOVER-PRMs showed statistically significant improvements in AUROC.
Cross-Task Generalization (RQ2):
- FOVER-PRMs were evaluated on tasks unrelated to the training data (NLI, MMLU-Pro, BBH).
- They outperformed baselines and were competitive with, or superior to, existing PRMs (e.g., RLHFlow, Skywork-PRM) that required much higher training costs (human annotation or massive MC roll-outs).
- Example: On BBH (Temporal Tracking), FOVER-PRMs achieved 80.0% vs. 74.0% for the baseline.
Efficiency & Robustness:
- Cost: FOVER requires only 1 LLM call per solution (to generate the trace) plus deterministic verification, whereas MC roll-outs require $N \times K$ calls.
- Data Efficiency: Ablation studies showed that training on just 10K steps yielded performance comparable to the full 40K dataset.
- Backbone Robustness: The method improved PRMs based on both weaker (Llama 3.1 8B) and stronger (Qwen 3 4B) backbone models.

5. Significance and Implications

Paradigm Shift: FOVER challenges the notion that PRM training must rely on expensive human labeling or noisy sampling. It proves that deterministic formal verification can serve as a scalable, noise-free supervisor for LLM reasoning.
Generalization: The results suggest that the logic of error detection learned from formal systems transfers remarkably well to natural language reasoning. This implies that the "reasoning capability" of a PRM is domain-agnostic to some extent, provided the training data is logically rigorous.
Scalability: By removing the dependency on human annotators and reducing LLM inference costs, FOVER offers a practical path to scaling PRM training for complex reasoning tasks.
Limitations: The current approach is limited to tasks that can be formalized (logic/math). It may struggle with tasks requiring subjective judgment or common sense that lacks a formal ground truth. Additionally, the authors note a potential side effect where PRMs might become "overly strict" on intermediate steps (e.g., penalizing rounding) if the formal verifier is rigid.

In conclusion, FOVER establishes a new standard for efficient PRM construction, demonstrating that formal verification tools can bridge the gap between symbolic correctness and natural language reasoning supervision.