Technical Summary: Verifiable Process Rewards for Agentic Reasoning

Problem Statement

Reinforcement Learning from Verifiable Rewards (RLVR) has successfully enhanced the reasoning capabilities of Large Language Models (LLMs) by replacing subjective human preferences with objective correctness signals (e.g., exact math answers or unit test outcomes). However, existing RLVR approaches predominantly rely on sparse outcome-level feedback, where a reward is only provided upon the completion of an entire trajectory.

This sparsity creates a fundamental credit assignment problem in long-horizon agentic reasoning. In multi-step tasks involving tool use, planning, or belief updates, a trajectory may fail despite containing many correct intermediate decisions, or succeed despite containing flawed ones. Sparse terminal feedback cannot reliably identify which specific intermediate actions should be reinforced or penalized. While Process Reward Models (PRMs) attempt to address this by providing step-level feedback, they often rely on learned reward models, LLM-as-a-judge evaluations, or Monte Carlo rollouts. These methods introduce noise, bias, vulnerability to reward hacking, or high computational variance.

The paper identifies a gap: there is a need for dense, turn-level supervision that remains objective and grounded in the task structure, rather than relying on learned approximations or expensive sampling.

Methodology: Verifiable Process Rewards (VPR)

The authors propose Verifiable Process Rewards (VPR), a framework that converts symbolic or algorithmic oracles into dense, turn-level reward signals for reinforcement learning. VPR operates under the assumption of densely-verifiable agentic reasoning problems, where intermediate actions can be objectively checked by a task-specific verifier $V: S \times A \to \{0, 1\}$.

Core Mechanism

Instead of waiting for a trajectory-level signal or estimating values via rollouts, VPR checks each intermediate action against a verifier. If an action is valid, useful, or optimal under the verifier's logic, it receives a dense, noise-free reward ($r_t^{VPR} = V(s_t, a_t)$).

The framework is instantiated in three representative settings:

1. Search-Based Verification (Dynamic Deduction): Implemented in Tic-Tac-Toe. The verifier uses Monte Carlo Tree Search (MCTS) to evaluate strategic optimality. An action is rewarded if it matches the MCTS-optimal move ($Q_{MCTS}$), encouraging the agent to avoid locally appealing but strategically losing moves.
2. Constraint-Based Verification (Logical Reasoning): Implemented in Sudoku. The verifier checks if a filled digit is consistent with the unique global solution grid ($G^*$). An action is rewarded if it matches the correct digit for a cell ($G^*[i, j] = d$), providing dense supervision for constraint satisfaction.
3. Posterior-Based Verification (Probabilistic Inference): Implemented in Minesweeper. The verifier calculates the posterior probability of mines based on revealed observations. An action is rewarded if it reveals a cell with the minimum posterior mine probability (risk-minimizing) or flags a cell with probability 1. This encourages the agent to update its belief state and act according to uncertainty.

Optimization

The policy is optimized using a turn-level variant of Group Relative Policy Optimization (GRPO). For each turn $t$, rewards are normalized across a group of trajectories to compute a turn-level advantage ($A_{i,t}$). Unlike outcome-level RL, this allows correct intermediate steps to be reinforced even if the trajectory eventually fails, and invalid steps to be penalized even if the trajectory succeeds by chance.

Theoretical Analysis

The paper provides three key theoretical insights:

1. Imitation-like Update: VPR acts as an on-policy filtered imitation update, where every step contributes its own oracle-grounded credit signal.
2. Bias Scaling: The gradient bias introduced by an approximate verifier scales linearly with the verifier's disagreement rate ($\bar{\epsilon}$). This contrasts with learned or rollout-based rewards where noise can propagate more unpredictably.
3. Signal Accumulation: In long-horizon tasks, the VPR signal accumulates linearly with the horizon ($T$), whereas the outcome-level reward (OR) signal is diluted exponentially ($p^T$) because success requires every step to be correct. This explains why VPR offers superior credit assignment for long trajectories.

Key Contributions

1. Framework: Introduction of VPR, a method to derive process rewards from symbolic or algorithmic verifiers in densely-verifiable agentic reasoning problems.
2. Instantiations: Demonstration of VPR in three distinct reasoning domains: search-based (Tic-Tac-Toe), constraint-based (Sudoku), and posterior-based (Minesweeper).
3. Theory: A theoretical analysis showing that dense verifiable feedback improves long-horizon credit assignment by localizing policy-gradient updates and providing favorable horizon scaling compared to outcome-level rewards.
4. Empirical Validation: Comprehensive evaluation showing VPR outperforms both outcome-level RL and rollout-based process reward baselines in controlled environments, with successful transfer to general and agentic reasoning benchmarks.

Experimental Results

The authors evaluated VPR using the Qwen3-4B model across three training environments and tested transfer to general reasoning and agentic tasks.

In-Domain Performance

• Tic-Tac-Toe: VPR approached the optimal return (0) and was the only method performing strongly as both the first and second player. Outcome-level (OR) and Monte Carlo Process Reward (MC-PR) baselines lagged, particularly for the second player where dense credit assignment is critical.
• Sudoku: While the base model had a moderate completion rate, it solved almost no puzzles. VPR significantly improved both Success Rate (SR) and Completion Rate (CR). Notably, MC-PR underperformed OR, suggesting that noisy step-level estimates can be detrimental in strict constraint-satisfaction tasks.
• Minesweeper: VPR showed the largest gains in Completion Rate, indicating agents made more valid local deductions and survived longer in uncertain states compared to baselines.

Out-of-Domain Generalization

Models trained with VPR demonstrated superior transfer capabilities:

• General Reasoning: VPR-trained models achieved the highest average scores across 7 benchmarks (GSM8K, MATH-500, AIME24/25, GPQA-D, BBH, MMLU-P). Improvements were most pronounced on harder benchmarks (AIME, GPQA), suggesting VPR strengthens multi-step reasoning rather than uniformly boosting all tasks.
• Agentic Tasks: VPR models outperformed baselines on ALFWorld (embodied text-based planning) and WebShop (goal-directed web interaction), domains structurally distant from the synthetic training games. This indicates that VPR fosters general reasoning skills applicable beyond the training environment.

Oracle Quality Ablation

A critical finding regarding Oracle Quality:

• High-Quality Verifiers (N=10,000 MCTS simulations): Yielded the best performance in both in-domain and out-of-domain settings.
• Weak Verifiers (N=100): Actively harmed training. Models trained with weak verifiers performed worse than the base model in both the training environment and on general reasoning benchmarks.
• Conclusion: Dense supervision is only beneficial if the verifier is reliable. Noisy process supervision from a misaligned oracle can degrade general reasoning capabilities more than sparse outcome supervision.

Significance and Claims

The paper claims 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.

• Practical Recipe: The authors propose a practical approach: identify environments where intermediate correctness can be objectively verified, supervise the reasoning process rather than just the final answer, and transfer these skills to broader agentic settings.
• Limitations and Challenges: The paper modestly acknowledges that VPR is dependent on the availability and quality of intermediate verifiers. Extending VPR to less structured, open-ended environments where symbolic or algorithmic oracles are not readily available remains an open challenge.
• Impact: The work highlights that while verifiable process supervision can foster general reasoning skills, the quality of the "oracle" is paramount; without reliable verification, dense feedback can be counterproductive.