# VeriBound: PAC-Bayesian Generalization Bounds for Process Reward Models Trained with Formal Verification Tools

arXiv: https://arxiv.org/abs/2606.20740 · HTML: https://mlsanity.com/paper/2606.20740/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Reinforcement learning for reasoning, one of 17 directions in LLM reasoning.
- Builds on 41 of its 51 references that are in the map.
- First posted on arXiv 17 Jun 2026.

## Placed in

- LLM reasoning / [Reinforcement learning for reasoning](https://mlsanity.com/lr/reinforcement-learning-for-reasoning/)
- LLM alignment / RLHF / preference optimisation / [Process reward models for reasoning](https://mlsanity.com/alignment/process-reward-models-for-reasoning/)

## Builds on (most cited first, 30 of 41)

- [REASONING GYM: Reasoning Environments for Reinforcement Learning with Verifiable Rewards](https://mlsanity.com/paper/2505.24760/) (2025)
- [DeepSeekMath-V2: Towards Self-Verifiable Mathematical Reasoning](https://mlsanity.com/paper/2511.22570/) (2025)
- [ReasonFlux-PRM: Trajectory-Aware PRMs for Long Chain-of-Thought Reasoning in LLMs](https://mlsanity.com/paper/2506.18896/) (2025)
- [R-PRM: Reasoning-Driven Process Reward Modeling](https://mlsanity.com/paper/2503.21295/) (2025)
- [Dynamic Scaling of Unit Tests for Code Reward Modeling](https://mlsanity.com/paper/2501.01054/) (2025)
- [MM-PRM: Enhancing Multimodal Mathematical Reasoning with Scalable Step-Level Supervision](https://mlsanity.com/paper/2505.13427/) (2025)
- [Uncertainty-Aware Step-wise Verification with Generative Reward Models](https://mlsanity.com/paper/2502.11250/) (2025)
- [Hard2Verify: A Step-Level Verification Benchmark for Open-Ended Frontier Math](https://mlsanity.com/paper/2510.13744/) (2025)
- [Safe: Enhancing Mathematical Reasoning in Large Language Models via Retrospective Step-aware Formal Verification](https://mlsanity.com/paper/2506.04592/) (2025)
- [Evaluating LLM-driven User-Intent Formalization for Verification-Aware Languages](https://mlsanity.com/paper/2406.09757/) (2024)
- [GM-PRM: A Generative Multimodal Process Reward Model for Multimodal Mathematical Reasoning](https://mlsanity.com/paper/2508.04088/) (2025)
- [Linking Process to Outcome: Conditional Reward Modeling for LLM Reasoning](https://mlsanity.com/paper/2509.26578/) (2025)
- [Is PRM Necessary? Problem-Solving RL Implicitly Induces PRM Capability in LLMs](https://mlsanity.com/paper/2505.11227/) (2025)
- [Beyond Outcome Verification: Verifiable Process Reward Models for Structured Reasoning](https://mlsanity.com/paper/2601.17223/) (2026)
- [PRM-BAS: Enhancing Multimodal Reasoning through PRM-guided Beam Annealing Search](https://mlsanity.com/paper/2504.10222/) (2025)
- [Accurate and Diverse LLM Mathematical Reasoning via Automated PRM-Guided GFlowNets](https://mlsanity.com/paper/2504.19981/) (2025)
- [Efficient PRM Training Data Synthesis via Formal Verification](https://mlsanity.com/paper/2505.15960/) (2025)
- [TIM-PRM: Verifying multimodal reasoning with Tool-Integrated PRM](https://mlsanity.com/paper/2511.22998/) (2025)
- [Fin-PRM: A Domain-Specialized Process Reward Model for Financial Reasoning in Large Language Models](https://mlsanity.com/paper/2508.15202/) (2025)
- [Neural Theorem Proving: Generating and Structuring Proofs for Formal Verification](https://mlsanity.com/paper/2504.17017/) (2025)
- [The Hidden Signal of Verifier Strictness: Controlling and Improving Step-Wise Verification via Selective Latent Steering](https://mlsanity.com/paper/2605.20745/) (2026)
- [SoK: Attacks on Industrial Control Logic and Formal Verification-Based Defenses](https://mlsanity.com/paper/2006.04806/) (2020)
- [I-RAVEN-X: Benchmarking Generalization and Robustness of Analogical and Mathematical Reasoning in Large Language and Reasoning Models](https://mlsanity.com/paper/2510.17496/) (2025)
- [Monitor-Generate-Verify (MGV): Formalising Metacognitive Theory for Language Model Reasoning](https://mlsanity.com/paper/2511.04341/) (2025)
- [ConfSpec: Efficient Step-Level Speculative Reasoning via Confidence-Gated Verification](https://mlsanity.com/paper/2602.18447/) (2026)
- [VeriGate: Verifier-Gated Step-Level Supervision for GRPO](https://mlsanity.com/paper/2605.30451/) (2026)
- [From <Answer> to <Think>: Multidimensional Supervision of Reasoning Process for LLM Optimization](https://mlsanity.com/paper/2510.11457/) (2025)
- [Adaptive Coopetition: Leveraging Coarse Verifier Signals for Resilient Multi-Agent LLM Reasoning](https://mlsanity.com/paper/2510.18179/) (2025)
- [DreamPRM-Code: Function-as-Step Process Reward Model with Label Correction for LLM Coding](https://mlsanity.com/paper/2512.15000/) (2025)
- [A Framework for the Verification of Certifying Computations](https://mlsanity.com/paper/1301.7462/) (2013)

## Built on by (most cited first, 1 of 1)

- [Scaling Large Reasoning Models beyond Human Supervision: A Path toward Superintelligence](https://mlsanity.com/paper/2608.31075/) (2026)

## Abstract (arXiv)

Process Reward Models (PRMs) provide step-level verification for Large Language Model (LLM) reasoning, yet their training data acquisition remains a bottleneck: human annotation is costly and Monte Carlo roll-out estimates are noisy. A recent approach, FOVER, trains PRMs on step-level error labels automatically annotated by formal verification tools such as Z3 and Isabelle, and empirically observes cross-task generalization from symbolic tasks to diverse reasoning benchmarks. However, this generalization phenomenon lacks any theoretical explanation, and no formal bounds exist on the generalization error, sample complexity, convergence rate, or downstream Best-of-K performance of such PRMs. We propose VeriBound, a theoretical framework that provides PAC-Bayesian generalization bounds for PRMs trained with formal verification tools. We establish four main results: (i) a PAC-Bayesian generalization bound that relates the empirical verification error on formal-verification-annotated training data to the expected error on unseen reasoning tasks, with the bound depending on the formal verification accuracy and the divergence between training and test task distributions; (ii) a sample complexity result showing that O(d log(d/δ) / ε2) formal-verification-annotated examples suffice to achieve generalization error ε with probability 1-δ, where d is the complexity of the PRM hypothesis class; (iii) a convergence analysis proving that PRM training with formal verification labels converges at a linear rate under L-smoothness and bounded variance conditions; and (iv) an error propagation bound that relates step-level verification error to Best-of-K performance degradation.