RAWR: Reward Assignment Without Rollouts in Verifiable Domains

Process supervision for chain-of-thought reasoning via Monte Carlo Net Information Gain introduces a novel, efficient method for automatically generating step-level labels to train Process Reward Models (PRMs), significantly improving the reliability and scalability of LLM reasoning supervision. This approach leverages information theory to estimate how much each reasoning step contributes to the likelihood of a correct final answer, achieving linear complexity while outperforming prior automatic labeling methods across diverse benchmarks.

How it works

The method introduces Monte Carlo Net Information Gain (MCNIG) as an extension of standard Information Gain (IG). Standard IG measures how much a partial reasoning prefix improves the model’s support for the ground-truth answer relative to a baseline with no reasoning, defined as:

IGi = Ii(y⋆) − I0(y⋆)

To make this signal more robust, MCNIG compares the information gained for correct answers against competing incorrect ones. It defines the Monte Carlo Net Information at step i as:

NetInfoi = max y∈Cq Ii(y) Cq largest correct information − max y∈Wq Ii(y) Wq largest incorrect information.

The final MCNIG is defined as the difference between this net information and that at step 0:

MCNIGi = NetInfoi − NetInfo0.

Label Assignment and Training

The continuous MCNIG signal is then projected into binary labels for PRM training. Labels are assigned based on a threshold, denoted as:

li = (1 if MCNIGi > τq, 0 otherwise).

These thresholds are chosen separately for each domain (mathematics, Python, SQL) to normalize scale differences. The PRM is then trained using these step-level labels. The input representation for training is constructed by concatenating the problem statement with the reasoning steps:

x1:N = q, r1,⟨sreq⟩, r2,⟨sreq⟩,..., rN,⟨sreq⟩.

The PRM acts as a binary classifier at each delimiter ⟨sreq⟩ to predict correctness via a softmax over reserved tokens ⟨sPOS⟩ and ⟨sNEG⟩. The training objective is the standard cross-entropy loss computed only at the tokens ⟨sreq⟩.

Efficiency and Complexity

The proposed method achieves linear complexity, denoted as O(N), in the number of reasoning steps N. This is a significant improvement over prior automatic labeling approaches:

MathShepherd (naive rollouts) costs O(MsN¯2), which is quadratic in N.

OmegaPRM (binary-search on first-failure) has an expected asymptotic complexity of O(N log N).

The MCNIG method processes the necessary information by evaluating the token log-probabilities of sampled answers conditioned on prefixes, resulting in a cost of approximately E[TokensMC-Net] = q + Ns¯+ (N + 1) S T. If S and T are treated as constants independent of N, this yields O(N) complexity.

Performance and Validation

The effectiveness of the MCNIG labels is validated across eight reasoning benchmarks spanning mathematics, programming, and scientific QA. The results show that PRMs trained on MCNIG labels consistently outperform those trained on standard Information Gain (IG) labels. Specifically:

Across all datasets, MCNIG provides more reliable labeling than IG.

The advantage of MCNIG is especially pronounced in code-generation tasks (Python and SQL). Furthermore, the method demonstrates resilience against failure modes observed in IG, such as cases where the estimated information trace increases monotonically toward an incorrect solution. The maximum operator used in MCNIG aggregation preserves the strongest competing alternative at each step, providing a sharper and more informative contrast with the correct trajectory.

Scaling and Robustness

The framework is designed for scalability. Performance improves consistently with increased data scale, indicating that larger preference-label datasets provide more robust learning signals. The method's approximation quality is also analyzed; empirical bias and variance decrease monotonically as the subsample size (s) increases, stabilizing below a 5% reduction in balanced accuracy for s ≥ 30. This demonstrates that the computational cost can be substantially reduced with minimal impact on performance when using a practical subsample size. The model's robustness is further confirmed by its superior out-of-distribution (OOD) generalization performance compared to baselines, reinforcing the value of more informative supervision for distribution shift.

Conclusion

The framework successfully constructs step-level supervision for CoT reasoning traces using information theory, enabling the training of competitive PRMs that exhibit better selection of reasoning trajectories in best-of-K settings across diverse domains.

As a fastidious and diligent researcher, I have analyzed the proposed framework, Process Supervision for Chain-of-Thought Reasoning via Monte Carlo Net Information Gain (MCNIG), and its implications. This approach fundamentally shifts process supervision from costly human annotation to an efficient, information-theoretic method.

Here are the specific improvements that can be made to AI systems using this paper, and what these improved systems can accomplish:

) 1. Implementation of Scalable, Automated Step-Level Supervision for LLMs:

The system gains the ability to generate high-quality training data for Process Reward Models (PRMs) automatically using MCNIG.

• An AI system can be trained on massive, diverse datasets (mathematics, code generation, text-to-SQL) with minimal human labeling effort.

• This enables the creation of robust PRM training sets that are scalable to millions of reasoning traces.

) 2. Enhanced Reliability in Chain-of-Thought Selection (Best-of-K):

The primary capability is significantly improved performance in best-of-K settings, especially for complex tasks where error propagation is severe.

• An AI system can intelligently select the most reliable reasoning path among several generated candidates by leveraging step-level quality signals derived from MCNIG.

• This leads to superior performance in benchmarks like MATH500, HumanEval, and BigCodeBench compared to existing methods (IG, ORM baselines).

) 3. Domain-Specific Robustness and Transfer Learning:

The system's supervision mechanism is domain-agnostic but performs exceptionally well across diverse reasoning tasks.

• The AI can effectively supervise reasoning in specialized domains like Python code generation and text-to-SQL, which are traditionally underserved by PRM research.

• The PRMs trained with MCNIG labels show strong generalization to out-of-distribution (OOD) settings (e.g., UGPhysics), ensuring the model's reasoning remains reliable in unseen contexts.

) 4. Mitigation of Error Propagation in Long and Complex Reasoning:

MCNIG provides a superior signal compared to standard Information Gain (IG) by explicitly contrasting correct and incorrect answers at every step, even when the correct solution is long or compositional.

• The AI system will be more resilient against subtle errors that cascade through multi-step reasoning processes (e.g., in complex SQL queries or long mathematical proofs).

• It prevents the failure mode where IG incorrectly suggests a trajectory is improving toward an incorrect solution, leading to better final answer selection.

) 5. Efficient and Computationally Scalable Labeling:

The method achieves linear complexity, O(N), in the number of reasoning steps, significantly outperforming prior methods like MathShepherd (O(N 2)) and OmegaPRM (O(N log N)).

• An AI system can rapidly generate step-level supervision signals during or after inference without incurring prohibitive computational costs.

• This makes PRM training feasible for real-time or high-throughput applications in LLM deployment, contrasting sharply with the labor intensity of human annotation.

) 6. Adaptive and Data-Efficient Model Training:

The system can be trained using progressively larger datasets (up to 1.2M samples) and scaled model sizes (e.g., from 8B to 14B parameters) while maintaining consistent performance gains, as demonstrated by the scaling results in Table 3.

• This allows for fine-tuning LLMs with high-fidelity process supervision signals, ensuring optimal alignment between the model's internal reasoning steps and the desired final outcome.