Verifiable Process Rewards for Agentic Reasoning
Huining Yuan, Zelai Xu, Huaijie Wang, Xiangmin Yi, Jiaxuan Gao, Xiao-Ping Zhang, Yu Wang, Chao Yu, Yi Wu Tsinghua University Project Page Code Models · 2026
Read Verifiable Process Rewards for Agentic Reasoning by Huining Yuan, Zelai Xu, Huaijie Wang, Xiangmin Yi, Jiaxuan Gao, Xiao-Ping Zhang, Yu Wang, Chao Yu, Yi Wu Tsinghua University Project Page Code Models (2026) 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-2605-10325.txt.
Introduction
Huining Yuan and eight colleagues tackle a credit problem in agentic AI reasoning. Learning from verifiable rewards usually gives feedback only at the end of a run. A long reasoning run can then fail despite many correct mid-steps, or succeed despite flawed ones, leaving the model unsure what to credit. Their 2026 paper proposes Verifiable Process Rewards, or VPR, for densely checkable tasks.
VPR turns symbolic or algorithmic oracles, checkers that can verify mid-steps by rule, into dense turn-level supervision. The authors test it in three settings: search-based checks for dynamic deduction, rule-based checks for logical reasoning, and posterior-based checks for chance inference. Theory shows that dense checker-grounded rewards improve long-run credit assignment, with gains tied to checker quality. In tests VPR beat end-only and rollout-based baselines and transferred to general and agentic reasoning tests.
Catalog record
| CREATOR | Huining Yuan, Zelai Xu, Huaijie Wang, Xiangmin Yi, Jiaxuan Gao, Xiao-Ping Zhang, Yu Wang, Chao Yu, Yi Wu Tsinghua University Project Page Code Models |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.10325
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Verifiable Process Rewards for Agentic Reasoning Huining Yuan, Zelai Xu, Huaijie Wang, Xiangmin Yi, Jiaxuan Gao, Xiao-Ping Zhang, Yu Wang, Chao Yu, Yi Wu Tsinghua University Project Page Code Models Abstract Reinforcement learning from verifiable rewards (RLVR) has improved the reasoning abilities of large language models (LLMs), but most existing approaches rely on sparse outcome-level feedback. This sparsity creates a credit assignment challenge in long-horizon agentic reasoning: a trajectory may fail despite containing many correct intermediate decisions, or succeed despite containing flawed ones. In this work, we study a class of densely-verifiable agentic reasoning problems, where intermediate actions can be objectively checked by symbolic or algorithmic oracles. We propose Verifiable Process Rewards (VPR), a framework that converts such oracles into dense turn-level supervision for reinforcement learning, and instantiate it in three representative settings: search-based verification for dynamic deduction, constraint-based verification for logical reasoning, and posterior-based verification for probabilistic inference. We further provide a theoretical analysis showing that dense verifier-grounded rewards can improve long-horizon credit assignment by providing more localized learning signals, with the benefit depending on the reliability of the verifier. Empirically, VPR outperforms outcome-level reward and rollout-based process reward baselines across controlled environments, and more importantly, transfers to both general and agentic reasoning benchmarks, suggesting that verifiable process supervision can foster general reasoning skills applicable beyond the training environments. Our results indicate that VPR is a promising approach for enhancing LLM agents whenever reliable intermediate verification is available, while also highlighting its dependence on oracle quality and the open challenge of extending VPR to less structured, open-ended environments. † † footnotetext: ∗ Equal contribution: {yuanhuining0, zelai.eecs}@gmail.com † † footnotetext: † Corresponding authors: [email protected], [email protected], [email protected] 1 Introduction Reinforcement learning from verifiable rewards (RLVR) has recently emerged as a powerful paradigm for improving the reasoning abilities of large language models (LLMs) 4 ; 6 . By replacing subjective human preferences with objective correctness signals, RLVR enables models to optimize against rewards that are difficult to hack and easy to verify, such as exact answers in mathematical reasoning or unit-test outcomes in coding. Recent breakthroughs in mathematical reasoning 21 demonstrate that outcome-level verifiable rewards can drive models to discover complex reasoning behaviors. However, most existing RLVR methods rely primarily on outcome-level rewards : the model receives feedback only after or completing an entire trajectory. While outcome-level verification is effective for single-turn tasks, it becomes insufficient in long-horizon agentic reasoning. As LLM research shifts toward agentic tasks involving tool use, interaction, and multi-turn planning 34 ; 7 , an LLM agent must make a sequence of decisions, such as selecting actions, updating beliefs, maintaining constraints, or planning several steps ahead. A trajectory may fail despite many correct intermediate decisions, or succeed despite flawed ones. This creates a fundamental credit assignment problem: sparse terminal feedback cannot reliably identify which intermediate actions should be reinforced. Process supervision offers a natural way to address this challenge by providing feedback at intermediate steps. Existing Process Reward Models (PRMs) 15 ; 26 , however, often rely on learned reward models, LLM-as-a-judge evaluations, or Monte Carlo rollouts. Learned or generative process rewards may be noisy, biased, or vulnerable to reward hacking 38 ; 5 , while rollout-based estimates can be computationally expensive and high-variance as they require sampling multiple completions per state for value estimations 9 ; 28 . As a result, dense feedback alone is not sufficient: for process rewards to improve long-horizon reasoning, they must also be reliable and objectively grounded. In this work, we study a class of densely-verifiable agentic reasoning problems , where intermediate actions can be objectively checked by symbolic or algorithmic oracles. Such settings arise when the task has explicit structure: search algorithms can verify strategic decisions in dynamic environments, constraint solvers can verify consistency in logical reasoning tasks, and inference engines can verify decisions under uncertainty. These verifiers make it possible to move beyond sparse outcome rewards and construct dense, turn-level supervision that remains objective and grounded. We propose Verifiable Process Rewards (VPR), a framework that converts symbolic or algorithmic oracles into turn-level reward signals for reinforcement learning. Figure 1 contrasts VPR with outcome-level rewards and rollout-based process rewards: instead of waiting for a sparse trajectory-level signal, or relying on noisy rollout estimates, VPR checks each intermediate action against a task-specific verifier and returns a dense, noise-free reward whenever the action is valid or optimal under that verifier. We instantiate VPR in three representative forms of agentic reasoning: search-based verification for dynamic deduction , instantiated with Monte Carlo Tree Search (MCTS) 11 to evaluate strategic optimality; constraint-based verification for logical reasoning , which checks whether an action remains consistent with the global solution space; and posterior-based verification for probabilistic inference 8 , which evaluates whether an action is optimal under the current belief state. We complement these instantiations with a theoretical analysis explaining why dense verifiable feedback improves credit assignment. Since each turn carries its own oracle-grounded signal, VPR localizes the policy-gradient update, controls bias through verifier reliability, and can yield more favorable horizon scaling than outcome-level rewards. We evaluate VPR in controlled densely-verifiable environments designed to isolate three core reasoning abilities: Tic-Tac-Toe for dynamic deduction, Sudoku for logical reasoning, and Minesweeper for probabilistic inference. Across these environments, VPR outperforms outcome-level RL and rollout-based process reward baselines, demonstrating the benefit of reliable turn-level supervision. Importantly, models trained with VPR also improve on general reasoning benchmarks and agentic reasoning tasks, suggesting that verifiable process supervision in densely-verifiable reasoning tasks can foster general reasoning capabilities beyond the training environments. We further analyze training dynamics and oracle quality, showing that VPR leads to more stable learning and that weaker verifiers substantially reduce performance. Overall, our results suggest that densely-verifiable agentic reasoning provides a useful path for studying how dense, objective process feedback can improve the general reasoning abilities of LLM agents. At the same time, VPR depends on the availability and quality of intermediate verifiers, and extending it to less structured, open-ended environments remains an important challenge. Our contributions are summarized as follows: • We introduce Verifiable Process Rewards (VPR), a framework for deriving process rewards from symbolic or algorithmic verifiers in densely-verifiable agentic reasoning problems. • We instantiate VPR in three representative reasoning settings: search-based verification for dynamic deduction, constraint-based verification for logical reasoning, and posterior-based verification for probabilistic inference. • We provide a theoretical analysis giving an intuition for why dense verifiable feedback improves long-horizon credit assignment, and showing that the verifier-induced gradient bias scales linearly with verifier disagreement and that dense rewards have more favorable horizon scaling than outcome-level rewards. • We empirically show that VPR outperforms outcome-level RL and rollout-based process reward baselines in controlled densely-verifiable environments, while also improving transfer to general and agentic reasoning benchmarks. 2 Method Figure 1 : Three reward designs for long-horizon reasoning. Left: outcome-level reward (OR) only fires at trajectory end, leaving intermediate decisions uncredited. Middle: rollout-based process rewards score each step via additional policy rollouts, providing dense feedback but with finite-sample noise (yellow). Right: Verifiable Process Rewards (VPR) score each step against a task-specific oracle verifier, producing dense and noise-free turn-level supervision (green). In this section, we present Verifiable Process Rewards (VPR), a framework for converting symbolic or algorithmic verifiers into dense turn-level