Efficient PRM Training Data Synthesis via Formal Verification

Ryo Kamoi 1, Yusen Zhang 2, Nan Zhang 1, Sarkar Snigdha Sarathi Das 1, 2 Columbia University · 2025

Read Efficient PRM Training Data Synthesis via Formal Verification by Ryo Kamoi 1, Yusen Zhang 2, Nan Zhang 1, Sarkar Snigdha Sarathi Das 1, 2 Columbia University (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15960.txt.

Introduction

Ryo Kamoi and co-authors found a cheaper, cleaner way to build training data for process reward models, the scorers that grade each step of a language model's reasoning. Labeling reasoning steps normally takes human annotators or many rounds of model sampling, and the labels come out noisy. Their framework, FoVer, instead builds tasks in formal logic, where verification software can check each step mechanically and mark errors exactly.

Training data from logic and theorem-proving tasks was then used to fine-tune step scorers. Across twelve benchmarks the scorers improved not only on math and logic but also on language understanding tests quite unlike the training material. The authors conclude that formal precision at data creation buys general reasoning quality.

Catalog record

CREATORRyo Kamoi 1, Yusen Zhang 2, Nan Zhang 1, Sarkar Snigdha Sarathi Das 1, 2 Columbia University
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15960

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient PRM Training Data Synthesis via Formal Verification Ryo Kamoi 1, Yusen Zhang 2, Nan Zhang 1, Sarkar Snigdha Sarathi Das 1, 2 Columbia University Abstract Process Reward Models (PRMs) have emerged as a promising approach for improving LLM reasoning capabilities by providing process supervision over reasoning traces. However, existing approaches for constructing PRM training data remain costly and noisy, as they typically rely on human annotation or sampling-based labeling methods that require repeated LLM calls. In this work, we propose FoVer , a framework that synthesizes PRM training data from formal reasoning tasks by annotating step-level error labels using formal verification tools such as Z3 and Isabelle. By leveraging formal verification, FoVer enables efficient and accurate PRM data construction without requiring human annotation or additional LLM calls. Using FoVer , we create PRM training data from formal logic and theorem proving tasks. Experiments on 12 reasoning benchmarks show that fine-tuning on our training data improves PRMs not only on math and logic reasoning tasks, which are informal variants of the training tasks, but also on NLI and BBH benchmarks, which differ substantially from the tasks used to construct the training data. These results demonstrate the practical effectiveness of FoVer , showing that PRM training data created using formal verification improves PRMs on informal reasoning tasks written in natural language. The datasets, models, and code are provided at https://github.com/psunlpgroup/FoVer . Figure 1: Comparison of FoVer with existing methods for PRM training data creation. FoVer efficiently produces accurate PRM training data for formal reasoning tasks by leveraging formal verification tools. In contrast, existing methods are costly and produce noisy labels, as they rely on human annotation or repeated LLM calls. 1 Introduction Process Reward Models (PRMs) have recently emerged as a promising approach for improving the reasoning capabilities of LLMs. They provide fine-grained process supervision over intermediate reasoning steps during training and inference ( Uesato et al., 2022 ; Lightman et al., 2024 ) . In practice, PRMs are usually created by fine-tuning LLMs to classify the correctness of individual reasoning steps, using training datasets annotated with step-level error labels on LLM-generated reasoning traces ( Wang et al., 2024 ; Zhang et al., 2025 ) . (a) PRMs based on Llama 3.1 8B (b) PRMs based on Qwen 2.5 7B Figure 2: Best-of-7 results across 5 categories of 12 reasoning benchmarks. PRMs trained with FoVer outperform baseline PRMs on average, showing that our training data created from formal reasoning improves PRMs on widely used reasoning benchmarks. Details are in Section 4 . Despite their growing adoption, creating PRM training data remains costly and noisy. Early studies ( Uesato et al., 2022 ; Lightman et al., 2024 ) create PRM training data via human annotation, which is particularly expensive for obtaining step-level error labels and suffers from low inter-annotator agreement ( Zheng et al., 2025 ) . Although Monte Carlo roll-outs ( Wang et al., 2024 ; Luo et al., 2024 ) , also known as Math-Shepherd, provide an annotation-free alternative for training data creation, it requires multiple LLM calls to label each step and generates noisy training labels. To address this gap, we propose FoVer , a novel framework for efficiently creating accurate PRM training data. As shown in Figure 1 , FoVer leverages formal verification tools to assign accurate step-level error labels to reasoning traces for formal reasoning tasks such as logic and theorem proving, without relying on human annotation or repeated LLM calls. Using FoVer , we create PRM training data named FoVer -40K by annotating step-level error labels on LLM responses to formal logic and theorem proving tasks using Z3 ( de Moura and Bjørner, 2008 ) and Isabelle ( Nipkow et al., 2002 ) . We then fine-tune Llama 3.1 8B ( Llama Team, 2024 ) and Qwen 2.5 7B ( Qwen Team, 2024 ) on FoVer -40K to use them as PRMs, which we refer to as FoVer -PRMs. Although FoVer creates PRM training data from formal reasoning tasks, PRMs are typically used to detect mistakes in informal reasoning tasks written in natural language. Therefore, in our experiments, we evaluate PRMs trained with FoVer on widely used informal reasoning benchmarks. First, we evaluate FoVer -PRMs on informal logic and mathematical reasoning benchmarks. These benchmarks can be regarded as informal variants of the training tasks, as FoVer -40K consists of formal logic and theorem proving tasks. We conduct evaluations on 6 widely used benchmarks, including LogicNLI ( Tian et al., 2021 ) , AQuA-RAT ( Ling et al., 2017 ) , and AIME ( Art of Problem Solving, 2025 ) . Using Best-of-K ( Cobbe et al., 2021 ; Li et al., 2023 ) , a standard evaluation approach for PRMs ( Lightman et al., 2024 ; Wang et al., 2024 ) , we show that FoVer -PRMs outperform baseline PRMs based on LLMs without additional fine-tuning. Second, we evaluate FoVer -PRMs on informal reasoning benchmarks involving tasks that substantially differ from those used to construct FoVer -40K. We use six benchmarks, including HANS ( McCoy et al., 2019 ) , MMLU ( Paech, 2024 ) , and BBH ( Suzgun et al., 2023 ) . The results show that FoVer -PRMs outperform baseline PRMs and achieve performance competitive with existing PRMs ( Xiong et al., 2024 ; Zhang et al., 2025 , e.g.,) , whose training data is constructed via human annotation or Monte Carlo roll-outs that require substantially higher cost than FoVer . Together, as shown in Figure 2 , our experiments demonstrate the practical effectiveness of FoVer in improving PRMs on widely used informal reasoning benchmarks. These results showcase formal-to-informal transfer and cross-task generalization in PRM training using formally verified labels annotated on formal reasoning tasks. Our main contributions are as follows: • We propose FoVer , a method that efficiently constructs accurate PRM training data from formal reasoning tasks using formal verification, addressing the annotation cost and labeling inaccuracy of existing approaches. • Our experiments show the practical effectiveness of FoVer , with PRM training data from formal reasoning tasks improving performance on informal reasoning tasks written in natural language, demonstrating formal-to-informal transfer and cross-task generalization in PRM training. 2 Background and Related Work PRMs for reasoning tasks are typically created by fine-tuning LLMs on the classification task to detect errors in reasoning traces at the step level ( Lightman et al., 2024 ; Wang et al., 2024 ) . Training data for PRMs are often constructed by annotating step-level error labels on reasoning traces generated by LLMs. Given a problem p\in\mathcal{P} from a reasoning task, an LLM generates a step-by-step solution consisting of k steps: s=[s_{1},s_{2},\ldots,s_{k}]\sim\mathrm{LLM}(p) . We then assign step-level error labels [y_{s_{1}},y_{s_{2}},\ldots,y_{s_{k}}]\in\{0,1\}^{k} , which serves as the supervision signal for PRM training. Here, we consider binary labels of correct and incorrect. Despite extensive research on PRM training data construction, obtaining reliable step-level labels remains challenging. Existing approaches are costly and noisy, as they often rely on human annotation or computationally expensive automatic methods. Human annotation. Human annotation ( Uesato et al., 2022 ; Lightman et al., 2024 ) is the primary approach used in early studies. However, for step-level reasoning tasks, it is particularly costly, and achieving high inter-annotator agreement

Read the complete text