Advancing Process Verification for Large Language Models via Tree-Based Preference Learning

Following the best-of-N evaluation protocol proposed by Lightman et al. (2023), we generate $N$ candidate solutions $\{y^{(1)},y^{(2)},\ldots,y^{(N)}\}$ from the generator model for a given input $x$. Each solution $y$ consists of a sequence of steps $\{y_{1},y_{2},\ldots,y_{n}\}$. These solutions are then ranked by the verifier, and the highest-rated one is selected as the most plausible solution.

To provide precise step-level preference feedback, we implement a best-first tree search algorithm designed to generate paired data critical for preference learning. As Figure 2 depicts, our method constructs a reasoning tree step-by-step, where each node represents a reasoning step. Expansion starts from the root of the tree at each search iteration.

At step $i$ of the tree expansion, we have a partial solution $y_{1:i-1}$ consisting of the previous $i-1$ reasoning steps. We use a reward function $\mathcal{R}(y_{i}|x,y_{1:i-1})$ to evaluate the quality of the next potential step $y_{i}$, given the input $x$ and the current partial solution $y_{1:i-1}$. The tree search proceeds by expanding the most promising node at each iteration, i.e., the node whose child (the next potential step) has the highest reward according to $\mathcal{R}$. This guided exploration allows us to construct high-quality reasoning paths through the tree, providing paired data for preference learning between competing steps.

The traditional approaches regard the correctness of a step as its quality, relying on metrics like perplexity (PPL) or self-evaluation by LLMs to design the reward function $\mathcal{R}$. However, recent studies have shown that LLMs frequently struggle to effectively recognize errors (Huang et al., 2023; Hong et al., 2023; Ren et al., 2023b), which can degrade performance. To address this, we leverage the model’s look-ahead capability to assess a step’s quality by its potential to lead to the correct conclusion. Specifically, to evaluate a candidate step $y_{i}$, we use the same model to simulate $N$ subsequent reasoning trajectories starting from $y_{i}$, denoted as $N$ completions $\mathcal{P}_{i}=\{P_{i}^{1},P_{i}^{2},\ldots,P_{i}^{N}\}$. The quality of the step $y_{i}$ is quantified by the proportion of trajectories reaching the correct answer:

where $a[P_{i}^{j}]$ is the outcome of the $j$-th trajectory $P_{i}^{j}$ and $g$ represents the golden answer.

After determining the node with the highest reward value according to $\mathcal{R}(y_{i}|x,y_{1:i-1})$, we expand the tree by generating new child nodes. To achieve this, we sample $k$ potential subsequent reasoning steps $y_{i+1}^{j}\sim\pi_{\theta}(y_{i+1}|x,y_{1:i})$ for $j=1,\ldots,k$, where $\pi_{\theta}$ is the language model used for reasoning. Each of these candidate steps $\{y_{i+1}^{j}\}_{j=1}^{k}$ becomes a new child node connected to the previously selected node. If the selected node represents the last step, indicating the end of the reasoning chain, we omit the expansion phase, and this iteration concludes. Guided by the reward function $\mathcal{R}$, this approach ensures a systematic exploration and expansion of reasoning paths in the search tree.

A reasoning tree illustrates all potential reasoning paths, starting from the root and branching out to various leaf nodes. Our objective is to create a dataset $\mathcal{D}_{\mathrm{pair}}$ consisting of pairs that express preferences of reasoning paths. We generate this dataset by tracing each unique path from the root to the leaves of the tree. Within this dataset, each entry consists of a triplet in the form $\{(x,y^{+},y^{-})\}$, where $x$ denotes the initial problem statement, $y^{+}$ is the preferred reasoning sequence that leads to an accurate solution, and $y^{-}$ is a less desirable reasoning chain that results in an incorrect answer.

To collect the paired data $\{(x,y^{+},y^{-})\}$, we conduct pairwise comparisons between sibling nodes at each decision point along the tree. Sibling nodes are the various possible next steps in the reasoning process branching from the same prior context $y_{1:i-1}$. If the reward difference between a preferable step $y_{i}^{+}$ and a less preferable step $y_{i}^{-}$ meets the minimum margin $\alpha$, we create a pair $(x,y^{+},y^{-})$ that includes the initial problem $x$, the superior reasoning sequence $y^{+}$, and the inferior alternative $y^{-}$. Specifically, for the preferable step $y_{i}^{+}$, we sample a path that leads to a correct solution among its completions $\mathcal{P}_{i}^{+}$. This constitutes the complete reasoning path $y^{+}$. Conversely, the less preferable step $y_{i}^{-}$ is assembled with one of the subsequent paths $\mathcal{P}_{i}^{-}$ that begins from it to form $y^{-}$, which ultimately leads to incorrect outcomes. Based on the pairwise instance data $\{(x,y^{+},y^{-})\}$, we gather two types of step preferences during our training. The first type is derived from the reward function $\mathcal{R}$ for the current step $y_{i}$, which assesses the choices at each decision point. The second type of preference implicitly decomposes the outcome-guided instance preference into step-by-step comparisons, examining each potential path leading to possible outcomes. This breakdown allows us to allocate the instance preference to both the decision points and the completion steps in the reasoning process, ensuring that steps on the correct path are preferred over those on the incorrect path.

The verifier is built upon a large language model with an additional randomly initialized linear layer that outputs a scalar value. During evaluation, we take the value linked to the end token to represent the aggregate reasoning score.

We train the verifier using a step-level ranking loss function designed to promote the choice of the most effective solutions, defined as:

Here, $d$ is the index where the two reasoning paths diverge, and $r_{\phi}(x,y_{1:i})$ represents the output of our verifier for an input $x$ and a sequence of steps $\{y_{1},\ldots,y_{i}\}$ with parameters $\phi$.

The number of candidate solutions impacts the performance of verification. As the number of solutions increases, more potentially superior candidates are introduced. However, there’s a trade-off, as more solutions mean higher computational overhead and diminishing performance gains. For our study, we set a maximum of 64 solutions. As shown in Figure 3, we found that all methods show an enhancement in performance as the number of solutions increases and finally stabilizes at 64, consistent with Wang et al. (2023)’s findings. Throughout the study, the Tree-PLV method consistently outperforms the others across all quantities of solutions. Remarkably, as the number of solutions rises, Tree-PLV continues to widen the performance gap, underscoring its robustness and superior capacity to leverage a greater number of solutions.

We further analyze the appropriate granularity for applying preference learning, aiming to determine the most effective level of feedback for Tree-PLV. Specifically, we compare our step-level preference with instance-level and conventional token-level training methods (Christiano et al., 2017; Ouyang et al., 2022). Additionally, we include a verifier trained using instance-level binary classification in our comparison for a comprehensive analysis. The results presented in Figure 4 demonstrate that verifiers trained with preference learning consistently outperform those trained using binary classification across all levels of granularity. This finding suggests that preference learning is better aligned with the ranking evaluation pattern. Furthermore, step-level guidance exhibits the best performance, indicating that it represents the most suitable granularity. In contrast to instance-level sparse supervision, it provides more detailed and informative feedback. Moreover, in step-by-step inference scenarios, stepwise preference proves to be more reasonable than token-level supervision, and such step-level alignment is also more consistent with the intuitive human process of evaluating reasoning.

Recent studies have highlighted the difficulties large language models encounter in accurately identifying their errors Huang et al. (2023); Hong et al. (2023). To assess our verifier’s effectiveness, we generate reasoning paths using greedy decoding, which are then scored by the original model’s generation confidence and by Tree-PLV. We compare the score distributions from both methods. Figure 6 shows Tree-PLV’s capability to separate correct and incorrect reasoning paths. In contrast, generation confidence scores produce overlapping distributions for both categories, highlighting their limited differentiation capacity. Specifically, Tree-PLV increases the scores of correct paths by 35%, whereas the confidence scores show only a marginal 2% higher score for them. This pronounced disparity between the two methods not only confirms the superior performance of Tree-PLV in evaluating the quality of reasoning paths but also emphasizes the critical need for an effective verifier to accurately assess model outputs.

Our proposed reward function $\mathcal{R}$ evaluates the quality of the current step by assessing the proportion of its latent complete paths that reach accurate conclusions. Some research demonstrates the advantages of integrating models’ self-evaluation capabilities into inference to enhance accuracy (Hao et al., 2023; Ren et al., 2023a; Xie et al., 2023). Inspired by this, we also developed a reward function that relies on self-evaluation. As per Hao et al. (2023), we first construct a reasoning tree based on Monte Carlo Tree Search (MCTS) that incorporates self-evaluation. We then collect preference data from each step of this tree to train a verifier under the same setting. The results, as shown in Figure 5, reveal that the self-evaluation-based reward does not perform as effectively as our proposed reward function. This trend is consistent across different generators, where the performance of the verifier trained with self-evaluation rewards significantly lagged behind our Tree-PLV. Our comparative analysis reveals that relying solely on the model’s intrinsic ability to evaluate reasoning steps falls short in reliability. Additional results on the MATH500 dataset are provided in the Appendix C.

We delve deeper into the analysis by applying varying margins to filter data. As shown in Figure 7, increasing the margin value raises the proportion of paired data with more noticeable path differences, thereby reducing noise and improving the performance of the verifier. However, when the margin value reaches 0.5, the verifier’s performance declines, indicating that excessively high margins can diminish the comparison of similar paths and reduce the richness of the data. Results on the MATH500 dataset are provided in the Appendix C.

We further analyze our tree-based framework across the dimensions of data generation efficiency. We compare the average number of training data per problem generated by different methods over 10 iterations, as shown in Figure 8. Math-Shepherd consistently labels ten paths. In contrast, Self-Explore struggles with datasets where the model already performs well, as it inherently relies on incorrect paths to form pairs. Our framework enhances the utilization of single paths through the branching structure of a tree, demonstrating significant scalability and efficiency in data generation.