OpenPRM: Building Open-domain Process-based Reward Models with Preference Trees

Q3: Additional Results from ORM in Table 3

In Figure 3, we compared various outcome-level reward models (ORMs) to evaluate their performance when scaling best-of-N selections. The results highlight the superior performance of OpenPRM. To improve readability, we will include some of these results in Table 3 for better reference. Regarding process-level beam search (PBS), scoring individual steps requires a reward model capable of evaluating partial outputs. Unfortunately, current outcome-level reward models are not designed for this purpose, which limits the comparison. Consequently, we have only included results for OpenPRMs, as no other open-domain PRMs are available for direct comparison.

We have analyzed the scaling effects of Process Beam Search (PBS), where beam search is conducted at the sentence level, selecting the top N generated outputs based on PRM rewards. As presented in the following table, the results indicate that OpenPRM consistently outperforms Bag of N-grams (BoN) in PBS settings, showcasing its effectiveness and reliability in these scenarios.

However, we also observed significant variance in the scaling effect of PBS across different tasks, in contrast to the more consistent scaling effect seen with best-of-N methods. This variance can likely be attributed to differences in the data distributions across tasks, which highlight the need for further investigation into handling data mixtures effectively. We plan to continue exploring this issue in future work to better understand and address these challenges.

We welcome further discussion on this topic and appreciate your interest in our results.

We sincerely thank you for your positive feedback and valuable suggestions. Below, we provide detailed responses to address your concerns and clarify our approach.

Q1: Comparsion with MCTS-based solutions

We compared the computational efficiency of our method with MCTS-based approaches under similar sampling budgets. The experimental setup and results are as follows:

A1. Sampling Settings:

• OpenPRM: We start from 60k samples, with 64 responses per sample, producing approximately 3.84M question-answer pairs in 24 hours. From this, 90k pairs were selected for training.
• MCTS: We start from 10k samples, with 4 responses per sample. Responses were split into sentences, resulting in 240k partial outputs. Sampling 8 full paths for each pair of partial outputs produced ~3.84M question-answer pairs in 24 hours. Of these, 97k pairs were used for training.

A2. Results: The results of PRM trained with OpenPRM and MCTS are shown below:

In fact, the MCTS method remains a powerful baseline but is significantly more resource-intensive, requiring up to 10 times the computational cost of our approach. With a larger sampling budget, the MCTS method could still be effectively utilized. However, our method offers a more efficient alternative and can be further optimized with more accurate similarity computation techniques, such as embedding-based methods. While these approaches may increase the time required to construct the tree, they hold great potential for improving performance.

We plan to explore these optimizations in future work to further enhance the efficiency and accuracy of our method.

Q2: Clarification of Comparisons in Table 2

We acknowledge that this is an important issue that warrants careful consideration. The use of different datasets for different models introduces challenges in achieving fully comparable ablations. To address this, we considered the backbone models (Intern-RM and FsFairX-RM) as baselines and further fine-tuned these models using datasets containing both outcome-level and process-level labels. For the ablation study, the dataset was split into two types: Preference Tree Pairs (process-level) and Outcome Pairs (outcome-level).

As shown in Figure 5(a), our results demonstrate that OpenPRM, trained on process-level labels (Preference Tree Pairs), outperforms models fine-tuned solely on outcome-level labels. This finding underscores the effectiveness of incorporating process-level training for enhancing performance.

Q3: Inference Details of PRM

For applying PRM to outcome-level pairs, we explored several aggregation strategies for calculating step-based rewards, as detailed below:

• Last Step: Use the reward of the final step as the overall reward, similar to ORM.
• Max/Min Step: Select the maximum or minimum reward among all steps.
• Simple Average: Calculate the average reward across all steps.
• Weighted Average: Apply a positional weight, giving later steps higher importance. The formula is: $r = \frac{1}{N} \sum_{i=1}^N \frac{i}{N} r_i$
• Dynamic Aggregation: Utilize uncertainty-weighted optimization (UWO) [1], which dynamically adjusts weights based on intra-ensemble variance. This penalizes policies generating outputs with high disagreement across steps.
• Max/Min Delta: Inspired by recent research, we also compute the delta (difference) between step rewards and use the maximum or minimum delta as the final reward.

[1] Reward Model Ensembles Help Mitigate Overoptimization. ICLR 2024 [2] Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning. Arxiv 2024

Q4: Example of Tree Building with Original Solutions

As illustrated in Figure 2 (segment and aggregate), we first split each answer into sentences and then merge similar sentences across all answers sequentially. For each merging operation, the candidate sentences are sourced from the same parent node and indexed consistently across their respective answers. To clarify, we provide a toy example along with the corresponding tree for merging three answers from ScienceQA.

We sincerely thank you for your positive feedback and valuable suggestions. Below, we provide detailed responses to address your concerns and clarify our approach.

Q1: Details on Tree Building for Training Data

A1: Temperature: Thank you for highlighting this issue. The temperature parameter indeed affects the diversity of generated responses. While higher diversity provides a more accurate estimation, it may also reduce similarity between spans, leading to fewer final pairs during merging. To address this, we employ a similarity-based method to merge different answer spans. Consequently, we choose a lower temperature to sample responses, ensuring a better balance between diversity and similarity.

A2. Edit Distance Analysis: Following prior studies, we determined that an edit distance above 0.8 (normalized to $[0, 1]$, where 1 indicates complete similarity) is preferable for sentence similarity. The distribution of edit distances for all sentence pairs follows a normal curve, centered around 0.88. Balancing similarity with dataset size, we chose 0.88 as our threshold. The statistical distribution of edit distances in UltraFeedback is presented below.

Q2: Training Details of PRM

When preparing the training data for the PRM, we reformat all process-level and outcome-level pairs into a unified format: $(Q, C, P_w, P_l)$, where $P_w$ and $P_l$ represent the chosen (preferred) and rejected (non-preferred) answers, respectively, based on the same context $C$. For outcome-level pairs, $[C, P_w]$ and $[C, P_l]$ represent the complete answers. For process-level pairs, these concatenations represent partial answers.

Using this unified format, we train the PRM using the Bradley-Terry objective as follows: $\mathcal{L}{\text{PRM}}(\theta) = -\frac{1}{N} \sum{i=1}^{N} \log \left( \sigma \left( r_\theta(q_i, c_i, p^i_w) - r_\theta(q_i, c_i, p^i_l) \right) \right)$

This formulation ensures consistent training across both process- and outcome-level dataset.

Node(Depth0): "Question:\nWhich logical fallacy is used in the text?\nBefore I refute my opponent's argument, I would like to draw attention to the fact that he is sweating and clearly does not have much experience on the debate team.\nOptions:\nA. ad hominem: an attack against the person making the argument, rather than the argument itself\nB. bandwagon fallacy: the assumption that the popular choice is automatically correct\nC. appeal to nature: the assumption that natural things are always good\nAnswer: Let's think step by step." | Reward: [] | Reply Indices: []

	Node(Depth1): "To identify the logical fallacy used in the text, let's analyze the situation step by step" | Reward: [0, 1] | Reply Indices: [0, 2]
	Similar sentences: "To identify the logical fallacy used in the text, let's analyze the situation step by step" ||| "To identify the logical fallacy in the text, let's break down the reasoning process step by step"

		Node(Depth2): "The text states that the speaker wants to refute their opponent's argument, but instead of addressing the argument itself, they choose to comment on their opponent's physical appearance (sweating) and a supposed lack of experience on the debate team. This kind of comment is meant to discredit the opponent rather than engaging with the argument they presented" | Reward: [0] | Reply Indices: [0]
			Node(Depth3): 'The key phrase here is "attack against the person making the argument, rather than the argument itself," which is the definition of the ad hominem fallacy. \n\nTherefore, the correct answer is:\nA. ad hominem: an attack against the person making the argument, rather than the argument itself.' | Reward: [0] | Reply Indices: [0]

		Node(Depth2): 'The text states, "Before I refute my opponent\'s argument, I would like to draw attention to the fact that he is sweating and clearly does not have much experience on the debate team." This statement does not address the opponent\'s argument itself but instead makes a personal attack on the opponent\'s appearance (sweating) and experience, implying that these characteristics make his argument weak' | Reward: [1] | Reply Indices: [2]
			Node(Depth3): "Now, let's analyze the options:\n\nA. ad hominem (A): This type of fallacy involves attacking the person making the argument rather than addressing the argument itself. In this case, the statement attacks the opponent's person (by mentioning their sweating and lack of experience) rather than addressing the merits of their argument" | Reward: [1] | Reply Indices: [2]
				Node(Depth4): "B. bandwagon fallacy (B): This fallacy occurs when it is assumed that something is correct or good because it is popular. There is no indication in the text that the opponent's argument is being rejected because it is unpopular, but rather because of personal characteristics" | Reward: [1] | Reply Indices: [2]
					Node(Depth5): 'C. appeal to nature (C): This fallacy involves assuming that something is good or true because it is natural. The text does not mention anything about what is natural or unnatural, so this option does not apply' | Reward: [1] | Reply Indices: [2]
						Node(Depth6): "Given the analysis, the correct answer is A. ad hominem, as the text attacks the opponent's person rather than addressing the argument itself." | Reward: [1] | Reply Indices: [2]

	Node(Depth1): "To identify the logical fallacy in the text, let's break it down step by step:\n\n1. **Identify the claim and the counterargument**: The text claims that the opponent's argument is flawed but before refuting it, it mentions that the opponent is sweating and lacks experience on the debate team. This is an attempt to undermine the opponent's credibility without addressing the argument itself" | Reward: [1] | Reply Indices: [7]
		Node(Depth2): "2. **Analyze the nature of the attack**: The attack is not on the argument's merits but on the opponent's character (sweating, lack of experience). Sweating can be a sign of nervousness, which isn't inherently indicative of the validity of one's argument. Lack of experience is also not directly related to the quality of the argument unless it's the first time the opponent is making an argument, which isn't specified" | Reward: [1] | Reply Indices: [7]
			Node(Depth3): '3. **Classify the fallacy based on the analysis**: The attack is focused on undermining the opponent personally rather than addressing the argument. This matches the description of the "ad hominem" fallacy, which involves attacking the person making an argument rather than addressing the argument itself' | Reward: [1] | Reply Indices: [7]
				Node(Depth4): 'Therefore, the logical fallacy used in the text is **ad hominem**' | Reward: [1] | Reply Indices: [7]
					Node(Depth5): 'The final answer is: A' | Reward: [1] | Reply Indices: [7]

We hope these responses address your concerns and provide further clarity. Thank you once again for your constructive feedback.

Node(Depth0): "Question:\nWhich logical fallacy is used in the text?\nBefore I refute my opponent's argument, I would like to draw attention to the fact that he is sweating and clearly does not have much experience on the debate team.\nOptions:\nA. ad hominem: an attack against the person making the argument, rather than the argument itself\nB. bandwagon fallacy: the assumption that the popular choice is automatically correct\nC. appeal to nature: the assumption that natural things are always good\nAnswer: Let's think step by step." | Reward: [] | Reply Indices: []

	Node(Depth1): "To identify the logical fallacy used in the text, let's analyze the situation step by step" | Reward: [0, 1] | Reply Indices: [0, 2]
	Similar sentences: "To identify the logical fallacy used in the text, let's analyze the situation step by step" ||| "To identify the logical fallacy in the text, let's break down the reasoning process step by step"

		Node(Depth2): "The text states that the speaker wants to refute their opponent's argument, but instead of addressing the argument itself, they choose to comment on their opponent's physical appearance (sweating) and a supposed lack of experience on the debate team. This kind of comment is meant to discredit the opponent rather than engaging with the argument they presented" | Reward: [0] | Reply Indices: [0]
			Node(Depth3): 'The key phrase here is "attack against the person making the argument, rather than the argument itself," which is the definition of the ad hominem fallacy. \n\nTherefore, the correct answer is:\nA. ad hominem: an attack against the person making the argument, rather than the argument itself.' | Reward: [0] | Reply Indices: [0]

		Node(Depth2): 'The text states, "Before I refute my opponent\'s argument, I would like to draw attention to the fact that he is sweating and clearly does not have much experience on the debate team." This statement does not address the opponent\'s argument itself but instead makes a personal attack on the opponent\'s appearance (sweating) and experience, implying that these characteristics make his argument weak' | Reward: [1] | Reply Indices: [2]
			Node(Depth3): "Now, let's analyze the options:\n\nA. ad hominem (A): This type of fallacy involves attacking the person making the argument rather than addressing the argument itself. In this case, the statement attacks the opponent's person (by mentioning their sweating and lack of experience) rather than addressing the merits of their argument" | Reward: [1] | Reply Indices: [2]
				Node(Depth4): "B. bandwagon fallacy (B): This fallacy occurs when it is assumed that something is correct or good because it is popular. There is no indication in the text that the opponent's argument is being rejected because it is unpopular, but rather because of personal characteristics" | Reward: [1] | Reply Indices: [2]
					Node(Depth5): 'C. appeal to nature (C): This fallacy involves assuming that something is good or true because it is natural. The text does not mention anything about what is natural or unnatural, so this option does not apply' | Reward: [1] | Reply Indices: [2]
						Node(Depth6): "Given the analysis, the correct answer is A. ad hominem, as the text attacks the opponent's person rather than addressing the argument itself." | Reward: [1] | Reply Indices: [2]

	Node(Depth1): "To identify the logical fallacy in the text, let's break it down step by step:\n\n1. **Identify the claim and the counterargument**: The text claims that the opponent's argument is flawed but before refuting it, it mentions that the opponent is sweating and lacks experience on the debate team. This is an attempt to undermine the opponent's credibility without addressing the argument itself" | Reward: [1] | Reply Indices: [7]
		Node(Depth2): "2. **Analyze the nature of the attack**: The attack is not on the argument's merits but on the opponent's character (sweating, lack of experience). Sweating can be a sign of nervousness, which isn't inherently indicative of the validity of one's argument. Lack of experience is also not directly related to the quality of the argument unless it's the first time the opponent is making an argument, which isn't specified" | Reward: [1] | Reply Indices: [7]
			Node(Depth3): '3. **Classify the fallacy based on the analysis**: The attack is focused on undermining the opponent personally rather than addressing the argument. This matches the description of the "ad hominem" fallacy, which involves attacking the person making an argument rather than addressing the argument itself' | Reward: [1] | Reply Indices: [7]
				Node(Depth4): 'Therefore, the logical fallacy used in the text is **ad hominem**' | Reward: [1] | Reply Indices: [7]
					Node(Depth5): 'The final answer is: A' | Reward: [1] | Reply Indices: [7]

Q2: Review of Previous Methods (Including MSE Loss)

We appreciate your comments regarding the review of MSE loss and its application in reward models (RMs) and Step-DPO. Here are our thoughts:

A1. MSE Loss for PRMs: While most Outcome-level Reward Models (RMs) are traditionally trained using the Bradley-Terry objective, Process Reward Models (PRMs) often utilize MSE loss for optimization. This approach is particularly suited to PRMs as they assign probabilities to individual steps in a sequence for questions with specific labels like math and code. For instance, given labels such as $(1, 1, 0, 0)$ for a sample with steps $(s_1, s_2, s_3, s_4)$, the PRM’s goal is to predict the probability of correctness for each step. The corresponding training objective can be expressed as: $\mathcal{L} = \sum_{t}^N \left(r(s_{0:t} \mid x) - y_t\right)^2$

Here:

• $r(s_{0:t} \mid x)$ represents the predicted reward probability for the sequence of steps up to $t$, given the input $x$.
• $y_t$ is the ground-truth label for step $t$.

This formulation ensures that the PRM learns to align its step-wise predictions closely with the provided labels, thereby improving process-level performance.

Recent works such as OVM [1] and AutoPSV [2], have explored MSE loss-based ORMs. Their training objective is: $\mathcal{L}{\text{total}}(Q) = \frac{1}{|Q|} \sum{q \in Q} \frac{1}{n} \sum_{i=1}^n \sum_{t=1}^{m_i} (f_{\theta} (S_i^{(1:t)};q) - y_i)^2$

where $n$ represents the number of solutions per question, and $m_i$ is the number of steps in the $i$-th solution. The output approximates the expected correctness probability for any partial content: $f_{\theta}(S^{(1:t)};q)$ Details of this derivation are provided in OVM [1]. Additionally, recent studies [3] have shown that binary classification models can be equivalent to BT models, further supporting the viability of MSE-based regression models.

A2. Step-DPO. We acknowledge the controversy regarding Step-DPO. While it does not explicitly define reward models, DPO models can be considered a type of implicit reward model [4]. They can assign outcome- or process-level rewards to samples, formulated as: $r(x,y) = \beta \log \cfrac{\pi_{\theta} (y|x)}{\pi_{\text{ref}} (y|x)} + \beta \log Z(x)$

[1] OVM, Outcome-supervised Value Models for Planning in Mathematical Reasoning. NAACL

[2] AutoPSV: Automated Process-Supervised Verifier. NeurIPS 2024

[3] Rethinking Bradley-Terry Models in Preference-Based Reward Modeling: Foundations, Theory, and Alternatives. Arxiv 2024

[4] Direct Preference Optimization: Your Language Model is Secretly a Reward Model. NeurIPS 2023

Q3: Computational Efficiency of the Proposed Method

We compared the computational efficiency of our method with MCTS-based approaches under similar sampling budgets. The experimental setup and results are as follows:

A1. Sampling Settings:

• OpenPRM: We start from 60k samples, with 64 responses per sample, producing approximately 3.84M question-answer pairs in 24 hours. From this, 90k pairs were selected for training.
• MCTS: We start from 10k samples, with 4 responses per sample. Responses were split into sentences, resulting in 240k partial outputs. Sampling 8 full paths for each pair of partial outputs produced ~3.84M question-answer pairs in 24 hours. Of these, 97k pairs were used for training.

A2. Results: The results of PRM trained with OpenPRM and MCTS are shown below:

In fact, the MCTS method remains a powerful baseline but is significantly more resource-intensive, requiring up to 10 times the computational cost of our approach. With a larger sampling budget, the MCTS method could still be effectively utilized. However, our method offers a more efficient alternative and can be further optimized with more accurate similarity computation techniques, such as embedding-based methods. While these approaches may increase the time required to construct the tree, they hold great potential for improving performance.

We plan to explore these optimizations in future work to further enhance the efficiency and accuracy of our method.

A3. Evaluation Metrics: For outcome-level reward benchmarks, such as RewardBench and UltraFeedback, we compute outcome-level accuracy. For process-level reward benchmarks like PRM800k, we construct a test set with samples in the form $(Q, C, P_1, P_2)$, where $Q$ is the question, $C$ represents the shared context, and $P_1$ and $P_2$ are the target steps. Similar to outcome-level benchmarks, we evaluate accuracy at this level.

A4. PRM Aggregation Strategies: For applying PRM to outcome-level pairs, we explored several aggregation strategies for calculating step-based rewards, as detailed below:

• Last Step: Use the reward of the final step as the overall reward, similar to ORM.
• Max/Min Step: Select the maximum or minimum reward among all steps.
• Simple Average: Calculate the average reward across all steps.
• Weighted Average: Apply a positional weight, giving later steps higher importance. The formula is: $r = \frac{1}{N} \sum_{i=1}^N \frac{i}{N} r_i$
• Dynamic Aggregation: Utilize uncertainty-weighted optimization (UWO) [1], which dynamically adjusts weights based on intra-ensemble variance. This penalizes policies generating outputs with high disagreement across steps.
• Max/Min Delta: Inspired by recent research, we also compute the delta (difference) between step rewards and use the maximum or minimum delta as the final reward.

[1] Reward Model Ensembles Help Mitigate Overoptimization. ICLR 2024

[2] Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning. Arxiv 2024

We sincerely thank you for your positive feedback and valuable suggestions. Below, we provide detailed responses to address your concerns and clarify our approach.

Q1: Details on Building the OpenPRM Dataset

We constructed the OpenPRM dataset following these steps:

A1. Edit Distance Analysis: Following prior studies, we determined that an edit distance above 0.8 (normalized to $[0, 1]$, where 1 indicates complete similarity) is preferable for sentence similarity. The distribution of edit distances for all sentence pairs follows a normal curve, centered around 0.88. Balancing similarity with dataset size, we chose 0.88 as our threshold. The statistical distribution of edit distances in UltraFeedback is presented below.

A2. Data Merging: As illustrated in Figure 2 (segment and aggregate), we first split each answer into sentences and then merge similar sentences across all answers sequentially. For each merging operation, the candidate sentences are sourced from the same parent node and indexed consistently across their respective answers. To clarify, we provide a toy example along with the corresponding tree for merging three answers from ScienceQA.

Q4: Additional Results on OffsetBias Datasets

In addition to benchmarks like RewardBench, UltraFeedback, and PRM800k, we evaluated our reward models using OffsetBias [1], which provides a more granular assessment of bias in reward models.

The results are summarized in the table below, showcasing the effectiveness of OpenPRM across various bias metrics:

[1] Park, Junsoo, et al. "Offsetbias: Leveraging debiased data for tuning evaluators." arXiv preprint arXiv:2407.06551 (2024).

Q5: Clarity of Figure 3

Thank you for this suggestion. We have revised Figure 3 to better visualize the BoN effects across different reward models. The updated graph now separately highlights the performance of our RM and includes detailed coverage curves for enhanced clarity.

Once again, we appreciate your valuable comments and constructive suggestions, which have helped us improve the quality and clarity of our work.

We sincerely thank you for your thoughtful feedback and the time and effort you have dedicated to reviewing our work. Below, we address your queries and provide additional clarifications where necessary.

Q1: Ablation Study on Outcome-Level Reward Model Performance

We consider the backbone models (Intern-RM, FsFairX-RM) as baselines, further fine-tuning these models using datasets with both outcome-level and process-level labels. For the ablation study, the dataset is divided into preference tree pairs (process-level) and outcome pairs (outcome-level).

As illustrated in Figure 5(a), our results demonstrate that OpenPRM, trained on our dataset with process-level labels (Preference Tree Pairs), outperforms models directly fine-tuned on data with outcome-level labels. This highlights the efficacy of process-level training in improving performance.

Q2: Performance of OpenPRM in the Chat Category

Thank you for highlighting this point. As shown in Table 2, OpenPRM’s scores in the Chat category decrease, while performance in the Chat Hard category improves. This reflects the inherent trade-off between optimizing for simpler conversational tasks (Chat Easy) and more complex reasoning tasks (Chat Hard), which is a known challenge in reward model optimization, as also noted in RewardBench [1].

The distinction between these categories lies in their data sources: the Chat category includes datasets like AlpacaEval and MT Bench, while Chat Hard is derived from MT Bench and LLMBar. The decreased scores in the Chat category are largely due to AlpacaEval, as there is a distributional shift between this dataset and our training data, which is sourced from UltraFeedback.

[1] Lambert, Nathan, et al. “RewardBench: Evaluating reward models for language modeling.” arXiv preprint arXiv:2403.13787 (2024).

Q3: Scaling Effects on Process Beam Search

We have analyzed the scaling effects of Process Beam Search (PBS), where beam search is conducted at the sentence level, selecting the top N generated outputs based on PRM rewards. As presented in the following table, the results indicate that OpenPRM consistently outperforms Bag of N-grams (BoN) in PBS settings, showcasing its effectiveness and reliability in these scenarios.

However, we also observed significant variance in the scaling effect of PBS across different tasks, in contrast to the more consistent scaling effect seen with best-of-N methods. This variance can likely be attributed to differences in the data distributions across tasks, which highlight the need for further investigation into handling data mixtures effectively. We plan to continue exploring this issue in future work to better understand and address these challenges.