V-STaR: Training Verifiers for Self-Taught Reasoners
Authors: Arian Hosseini
Xingdi Yuan
Nikolay Malkin
Aaron Courville
Alessandro Sordoni
Rishabh Agarwal
Venue: COLM (2024)
Keywords: Large Language Model, Self-improvement, Reasoning, verifier
TL;DR: We propose V-STaR which utilizes both the correct and incorrect solutions generated during self-improvement process to train a strong verifier.

Abstract: Common self-improvement approaches for large language models (LLMs), such as STaR (Zelikman et al., 2022), iteratively fine-tune LLMs on self-generated solutions to improve their problem-solving ability. However, these approaches discard the large amounts of incorrect solutions generated during this process, potentially neglecting valuable information in such solutions. To address this shortcoming, we propose V-STaR that utilizes both the correct and incorrect solutions generated during the self-improvement process to train a verifier using DPO that judges correctness of model-generated solutions. This verifier is used at inference time to select one solution among many candidate solutions. Running V-STaR for multiple iterations results in progressively better reasoners and verifiers, delivering a 4% to 17% test accuracy improvement over existing self-improvement and verification approaches on common code generation and math reasoning benchmarks with LLaMA2 models.

Published as a conference paper at COLM 2024
V-STaR: Training Verifiers for Self-Taught Reasoners
Arian Hosseini Xingdi Yuan
Nikolay Malkin
Aaron Courville
Alessandro Sordoni ह
Rishabh Agarwal O
Mila, Université de Montréal
Microsoft Research
University of Edinburgh
O Google Deepmind
Abstract
Common self-improvement approaches for large language models (LLMs), such as STaR (Zelikman et al., 2022), iteratively fine-tune LLMs on self- generated solutions to improve their problem-solving ability. However, these approaches discard the large amounts incorrect solutions generated during this process, potentially neglecting valuable information in such so- lutions. To address this shortcoming, we propose V-STaR that utilizes both the correct and incorrect solutions generated during the self-improvement process to train a verifier using DPO that judges correctness of model- generated solutions. This verifier is used inference time to select one solution among many candidate solutions. Running V-STaR for multiple iterations results in progressively better reasoners and verifiers, delivering 4% to 17% test accuracy improvement over existing self-improvement and verification approaches on common code generation and math reasoning benchmarks with LLaMA2 models.
1 Introduction
Learning to recognize and correct mistakes is feature of human intelligence (Metcalfe, 2017). When dealing with complex tasks, such as coding or solving a math problem, we can recognize errors in reasoning and explore alternative paths to a solution. To improve the reasoning performance of LLMs, several approaches exploit the ability of LLMs to produce solutions and check the correctness of these solutions during training, for example, using test cases for code generation. These self-improvement approaches, such as STaR Zelikman et al. (2022), RFT (Yuan et al., 2023), and ReSTEM (Singh et al., 2023), improve LLMs by fine-tuning them on their self-generated solutions and optionally iteratively running this process. However, all these approaches are data-inefficient in that they use only correct solutions, and discard incorrect solutions, which is often large portion of model-generated solutions, especially for challenging reasoning tasks.
Orthogonal to self-improvement, another promising direction to improve LLM reasoning is to use learned LLM verifiers test time (Cobbe al., 2021; Wang al., 2023b). Specifically, the LLM generates multiple candidate solutions and the verifier ranks these solutions and selects the best one. Such verifiers are trained by fine-tuning an LLM on dataset of solutions generated from frozen LLM, labeled with either final correctness (ORM, Cobbe et al., 2021) or step-by-step human annotations (Lightman et al., 2024), Using such verifiers allows LLMs to trade-off additional test-time compute for better performance.
We propose Verification for Self-Taugh Reasoners (V-STaR). The key idea in V-STaR is to utilize both the correct and incorrect LLM-generaeed solutions during the iterative self- improvement process to train a verifier using DPO (Rafailov et al., 2023), in addition to training LLM as generator using correct solutions (Fig. 1). The iterative self-improvement process yields progressively improved generators, trained on augmented data, which leads
*Correspondence to: sarran.hoseeini@@gmai...
and <ishabhggarvalegoolee.m.>
We also considered using this DPO setup to train generator in 54.6.
1

---

Published as a conference paper at COLM 2024
DoeN
Union
(Xp, (A2, 9 (x
(1 (rey Fi X (Ng,
(oe. Ri
(x,
SFT
Generate
Label
Filter
(K I3
G
(x, (x,
(x,9)
22
(x,ger)
V
V
DPO
DYeR
Training iteration
Inference
Figure 1: Generator and verifier training in V-STaR. Left: In each training iteration, the generator G' is fine-tuned (from pretrained LLM) on the current buffer of problem instances and correct solutions CEN. Generated solutions that yielded a correct answer are added to DGEN to be used in future iterations, and all the generated solutions (correct and incorrect) are added to DYER- The verifier V is trained using DPO with preference da tasas constructed from pairs of correct and incorrect solutions from DVER- Right: At test time, the verifier is used to rank solutions produced by the generator. Such iterative training and inference-time ranking yields large improvements over generator-only self-improvement.
to higher quality completions and more challenging negative examples for the verifier training. At test time, the verifier ranks multiple candidate solutions from the generator and selects the best one.
We empirically evaluate V-STaR to improve reasoning capabilities of LLMs: (1) Math problem-solving using GSM8K (Cobbe et al., 2021) and subset of MATH (Hendrycks al., 2021), and (2) Code-generation using MBPP (Austin et al., 2021) and HumanEval (Chen et al., 2021). Fine-tuning LLaMA2 (Touvron et al., 2023) and CodeLLaMA (Rozière et al., 2023), compare V-STaR to other self-improvement (RFT, STaR) and verification-based meth- ods (ORM), self-consistency (Wang et al., 2023a), and a non-iterative V-STaR baseline (RFT + Verifier) that uses the same number of generation samples to bootstrap generator and verifier. V-STaR works remarkably well, leading to 6% to 17% absolute improvement in test accuracy over prior self-improvement and verification-based methods for math reasoning, and 4% to 12% in code generation. Notably, 7B V-STaR surpasses base LLaMA2 70B (8-shot) GSM8K, and nearly match CodeL.LaMA 34B (zero-shot) on HumanEval.
Our contributions are:
We propose V-STaR, simple and effective approach, which uses iteratively generated correct and incorrect solutions from an LLM to train a better generator and verifier. V-STaR outperforms prior self-improvement approaches (RFT, STaR) as well as ORM verification (Cobbe et al., 2021) for math reasoning and code generation (Fig. 2). V- STaR better utilizes adaptive test-time compute for improving performance than strong baselines - ORM verification, RFT + verifier (Fig. 5), and self-consistency (Fig. 6, left). As secondary contribution, we find DPO to be more effective for training verifiers than the prevalent ORM approach by Cobbe et al. (2021). We also propose formula for Best-of-k (54.2), akin to Pass@k, to reliably evaluate test performance with verification.
2 Preliminaries
Given a pretrained language model G and the original training data of a task Dsrr (xx1y)), (2), (xN, WN)), where x is typically description of problem and y is the solution, such as chain-of-thought rationale or generated code. The de facto approach for such tasks with causal language models is supervised fine-tuning (SFT) with the negative log-likelihood objective on the training data:
(G) (xxy))~ Σ log G(y; Vctxx)
(1)
where is also referred to as generator in reasoning tasks. LLMs can be used to generate high quality ofain-of-thought rationales solutions for range of tasks. This observation
2

---

Published as a conference paper at COLM 2024
Table 1: Comparison of self-improvement and verification methods, showing the data used to train the generator and verifier (if applicable), and whether or not the method is iterative.
METHOD
GENERATOR DATA
VERIFIER DATA
ITERATIVE
SFT
DSFT
X
X
VERIFICATION
DSFT
DSFT GENERATED
STAR
CORRECT GENERATEDI-1
RFT (STAR"[1 (TER))
DSFT CORRECT GENERATED
STAR*
DSFT U CORRECT GENERATED
X
/
V-STAR [1 [TER]
DSFT U CORRECT GENERATED SSFT CORRECT GENERATED
DSFT GENERATED
X
V-STAR
DSFT U GENERATED
has motivated using correct generations from the model itself to bootstrap problem-solving and reasoning abilities (Zelikman et al., 2022; Singh al., 2023; Yuan et al., 2023).
2.1 Self-improvement approaches
Self-Taught Reasoner (STaR; Zelikman et al., 2022) corresponds to an iterative approach where language model improves itself using correctness feedback. In each iteration, one so- lution !/ is generated using greedy decoding from the generator G for each problem in train- ing dataset 'D. Having access to test cases or ground truth answers, generated solutions can be checked for their binary correctness label by pletion f is labeled correct if it has the same final answer as the ground truth answer for math problems, if it passes all the test cases for code generation problems. Only correct solutions
is_correct(1: 9),
E 1) A
(z ===1 1) are included in the dataset at iteration where Dj = {x1, f1), (x2, 12), .. (2), (xN, NN)
Then, the generator is fine-ture tne-ttned on this new dataset using (Eq. 1) where DSFT Dj. This fine-tuned generator is used in subsequent iterations.
Rejection Sampling Fine-tuning (RFT; Yuan et al., 2023) first fine-tunes a pretrained LM the training dataset DSFT to obtain G. For each problem x,, k solutions sampled (&e ~ G(y]x:)) and similar to STaR, only correct generated solutions (z 1) are kept. In RFT, the original dataset is then augmented with the correct completions to D;, and G is fine-tuned on the new D to obtain GREI- Unlike STaR, RFT is not an iterative approach.
STaR Each STaR iteration can be performed similarly to RFT, akin to ReSTEM (Singh et al., 2023). Since there could be multiple correct solutions for problem, one could sample solutions per problem at each STaR iteration, but this is not prescribed in the original STaR paper, which we will denote as STaR' for the rest of the paper.
2.2 Test-time verification
Cobbe et al. (2021) trained verifiers, which they refer as outcome-supervise reward model (ORM), that assess the probability that candidate solution correct for given problem. At test time, the language model G generates many candidate solutions and the one ranked highest by the verifier is selected, also known Best-of-k. To train a verifier V, similar to RFT, & candidate solutions are sampled from a generator G for each training problem and labeled for their correctness z to make the verifier training data DYER = {(x;, Zt,)) where Zi, is binary label indicating whether Di,j is correct or incorrect solution.
To train the verifier V, Cobbe et al. (2021) fine-tune LLM DYER using combination of language modeling (Eq. 1) and binary classification. The model is trained to predict Vi, given x; and Zij given {x;; 9i,}) with the language modeling and the classification objective, respectively. See $5 for more details.
2.3 Preference learning with DPO
Fine-tuning pretrained LLMs with human feedback can result in large performance gains in downstream tasks Ouyang et al. (2022); Bai et al. (2022). The typical framework to do is to
3

---

Published as a conference paper at COLM 2024
70
50
+25.0
135.2
60
STeR!
220.2
121.6
40
Verification
Test Accuracy
50
-18.1
+12.9
Test Accuracy
+13.1
30
20
20
10
GSMBK
MEPP
GSMBK + MATH subset MBPP Humanbval
Figure 2: Test accuracy of 7B V-STaR compared to self-improvement and verification baselines. We report Best-of-64 for verification-based methods and Pass@1 for others. All methods, except SFT, have access to the SFT baseline model and K 48 output generations per problem. STaRt and V-STaR are run for iterations, where each iteration uses K/3 16 samples. Verification corresponds to using test-time verifier trained on K generated com- pletions from the SFT generator. Numbers above each bar show the absolute improvement over SFT. (Left) Test accuracy on tasks used for V-STaR training. (Right) Transfer evaluation of GSM8K and MBPP trained models on MATH subset and HumanEval respectiveyy
collect paired human preferences for set of input prompts Prref = (x vy; ) train a reward model using D pref, and fine-tune the LLM using this reward (Stiennon et al., 2020).
More recently, Rafailov et al. (2023) proposed Direct Preference Optimization (DPO), which does not use a separately trained reward model during fine-tuning. DPO requires supervised fine-tuning (SFT) pretrained LLM on the downstream task to obtain GSFT, which is also used as a reference policy. Given the preference dataset 2 pref and GSFT, DPO's objective increases the log likelihood, relative to the reference policy, of preferred y+ to dispreferred completions. We present the DPO loss later in Eq. 2, in the context of training verifiers.
3 V-STaR: Verifiers for self-taught reasoners
Existing self-improvement methods, such as RFT, STaR, and RMSTEM, throw away incorrect model-generated solutions. However, incorrect solutions can also contain valuable infor- mation: language model could learn from discrepancies between correct and incorrect solutions for a given problem, and identify error patterns in generations, enhancing its abil- ity to provide more accurate solutions. In this work, propose V-STaR that utilizes both incorrect and correct generated solutions in an iterative process to train a better generator and verifier (see algorithm in appendix).
First, we fine-tune pretrained LLM Gbase on the original training data DSFT to obtain generator GSFT.
Next, we sample completions for each problem in the training data from the generator
(0i, ~ GGy]( where x E Dquery (see SD for an example).
Generated solutions labeled for their correctness using ground truth answers or test cases. We use only correct generated solutions (z = 1) to augment the generator training data DGEN (x; ft.)). Both correct and incorrect generated solutions are added verifier data DVER with their correctness label as (x, (t, so the verifier can learn from generator's mistakes.
In the next iteration I, the generator is obtained by fine-tuning the pretrained model Gbase on the augmented DGEN- We can sample solutions again from this generator Gf. This process repeated for up to T iterations to augment DGNN and DYER iteratively.
The final generator GT is obtained by using DGEN to fine-tune pretrained model Gbase- The verifier VT is obtained by using DVER to further train a model GSFT which was fine-tuned the original DsFT-
4

---

Published as a conference paper at COLM 2024
80
80
+22.7
+20
V-STaR [1 Iter]
Test Accuracy
Test Accuracy
V-STER
60
+21
60
+5.1
+5.6
+2.7
-7.6
40
40
7B
13B
7B
13B
(a) GSM8K for 7B and 13B sizes
(b) MBPP for 7B and 13B sizes
Figure 3: Pass@1 and Best-of-64 scores for generator-only and verifier-based methods. Numbers above each bar represent the absolute improvement over RFT. V-STaRj1 Iter] baseline is trained with data consisting of 3 x 16 completions per query for one iteration only. STaR and V-STaR are trained using iterative data collection (i.e. 16 completions generated per query at each iteration). At test time, Best-of-64 is calculated using Eq. 3 on 128 candidate answers sampled per problem from the generators. V-STaR 7B performs par with CodeLLaMA 34B, which has zero-shot Pass@1 of 55% on MBPP.
In our approach, the original training data is also included as correct solutions in both generator data and verifier data. The difference between V-STaR training and Cobbe al. (2021) is that our verifier training data is collected iteratively, each iteration from better generator, while ORM only collects data from a fixed generator that only fine-tuned on the original SFT data. We compare to this ORM approach as baseline, discussed in 54.1.
3.1 Training verifiers with DPO
Following Cobbe et al. (2021), current LLM verifiers are trained with a combination of language modeling and binary classification loss ($2.2). These two objectives can be unified via offline preference learning methods, such as DPO (Rafailov et al., 2023), where the proximity to the reference policy is proxy for the language modeling objective while the classification loss is proxy for reward modelling. Empirically, we found DPO verifiers to be better than ORM-style verifiers (54.4), when using LoRA adapters (Hu al., 2022).
To use DPO for training verifiers, construct preference pair dataset using collected solu- tions in DVER. We treat correct solutions as preferred and incorrect solutions as not preferred completions given the problem. Specifically, DVER = {x,, y ), (xi, Vi Vi.m J Ji=1 where m is the number of preference pairs which are from the Cartesian product of correct and incorrect solutions. We train our verifier using this constructed DVER and the SFT policy GSFT using the DPO objective, (Vro(V; GSFT):
V(yxx)
- -E y >~-DVER [logo (P(x,y' f(x,y ))], with P(x,)) = =Blog GSFT(y/a)
(2)
where o is the logistic function, and B hyper-parameter controlling the proximity to the reference policy GSET- The DPO objective steers the verifier towards increasing the likelihood of correct solutions y and decreasing the likelihood of incorrect solutions y for a problem x. At inference, we use the likelihood of generated solution given problem under the trained DPO verifier (i.e. (fflx)) as scores to rank candidate solutions.
4 Empirical results
To demonstrate the effectiveness of V-STaR, we conduct experiments on two widely used datasets: GSMSK (Cobbe et al., 2021) for solving math problems, and MBPP (Austin et al., 2021) for code-generation problems. We also evaluate the transfer generalization perfor- mance of V-STaR using Hendrycks' MATH (Hendrycks et al., 2021) and HumanEval (Chen et al., 2021). Specifically, for math reasoning, we only train our generators and verifiers

---

Published as a conference paper at COLM 2024
50
70
STaR!
V-STaR [1 Iter]
+11.8
+18.2
Test Accuracy
-8.4
Test Accuracy
30
50
+0.7
+19.1
+10.2
+18.7
+2.3
+2.1
10
30
7B
13B
7B
13B
(a) GSM8K MATH Subset
(b) MBPP HumanEval
Figure 4: Out-of-domain transfer evaluation: Pass@1 and Best-of-64 for generators and verifiers with absolute improvement over RFT shown above each bar. Models trained on GSM8K are evaluated on subset of MATH test set ($4), and models trained on MBPP are evaluate on HumanEval test set. V-STaR 7B performs close CodeLLaMA 34B which has zero-shot Pass@1 of 48% on HumanEval.
using GSM8K training data and evaluate them on the whole GSM8K test set and a subset of MATH test set?. For code generation, we train our models using the MBPP training data and evaluate them on the full test sets of MBPP and HumanEval.
Models For experiments, we fine-tune LLaMA2 (Touvron et al., 2023) and CodeLLaMA (Rozière et al., 2023) 7B and 13B models using LoRA (Hu et al., 2022). Generators trained with causal language modeling objective, and our baseline (V-STaR[1 Iter)) and V-STaR verifiers are trained using DPO. The reference policy GSrT for DPO is trained on the original training data for 2 and 3 epochs for GSM8K and MBPP, respectively. See $3.1 for details.
Data generation For each iteration, k = 16 completions are sampled per query from the previous iteration's generator. For GSM8K, the first iteration samples are from a generator trained solely on the original GSMSK training data for 2 epochs. For MBPP, this data is from a 3-shot pretrained CodeLLaMA (see ŞB). Completions are labeled for correctness by checking the final answer for math problems and running test cases for coding problems.
4.1 Baselines and metrics
We run V-STaR for 3 iterations and sample k = 16 solutions at each iteration to augment DGEN and DYER- To assess the gains from our iterative approach, we compare against number of baselines (Table 1):
Standard fine-tuning (Eq. 1) on training data without any self-improvement or test-time verification.
SFT:
STaR*: Bootstrapping a generator by sampling k = 16 completions per query for iterations, see $2.1.
RFT: Running STaRtby sampling x 16 completions for only iteration, see $2.1. 4. Verification (SFT Verifier): Generating x 16 completions using SFT generator to train verifier, as described in $2.3. This is similar to ORM verification approach by (Cobbe
et al., 2021) but empirically performs better (Fig. 5).
V-STaR [1 Iter]: Bootstrapping a generator and training verifier for iteration with k = 3 x 16 completions from GSFT, so that the total generation budget matches V-STaR. This baseline also corresponds to RFT + Verifier.
6. Self-consistency Majority Voting (Wang et al., 2023a): An alternative to use test-time
compute without verifiers: sample multiple solutions from STaRt generator and pick the majority-vote answer.
2his subset includes total 150 problems of Level 1 difficulty in MATH with question types of algebra, Counting & probability, prealgebra and number theory where the final answer is number and no latex exists in the question.

---

Published as a conference paper at COLM 2024
55
60
50
Best-of-k
V-STaR [1 Iter]
Best-of-k
V-STaR
ORM [1 iter]
V-STaR [1 Iter]
V-STaR
30
40
ORM [1 Iter]
8 16
32
64
8
16
32
64
Number of candidate solutions (k)
Number of candidate solutions (k)
(a) GSM8K Best-of-k
(b) MBPP Best-of-k
Figure Best-of-k test accuracy of V-STaR, V-STaR Iter], and outcome-supervised reward model (ORM) style verifier 7B models, measured by Eq. 3. Best-of-1 is equivalent to not having a verifier and is equal to Pass@1 of the generator.
At inference, generate 128 candidate solutions for each test problem using the generator. We report Pass@1 accuracy for the generators, which estimates the probability that an answer randomly sampled from the generator is correct. Best-of-64 accuracy used for all verifier-based methods, using the formula in (Eq. 3), as well as the self-consistency baseline.
4.2 Reliable estimation of Best-of-k accuracy
To estimate accuracy with test-time verifiers, Cobbe et al. (2021); Lightman et al. (2024) repeat the following procedure several times and average the results: sample k solutions, rank them using verifier and take the top scoring one as the predicted answer. However, computing this best-of-k accuracy can have high variance and is expensive. Instead, to measure the best-of-k accuracy reliably, we propose two methods, akin how Pass@K is computed (Chen et al., 2021). To do so, we estimate the probability that out of k samples drawn without replacement from a fixed set of N (for N > k) samples, the one with the highest verifier score is correct. The best-of-k is calculated by repeating this process M times and taking the average. Assuming there are no duplicate verifier scores this can be done efficiently (see SE in appendix), using the following formula:
W k 1 aj
Best-of-k =
(
where ( aN 1] are the binary correctness values (0 or 1) for the N candidates y; sorted in decreasing order by their verifier score. The numerator here can be derived by considering subsets where the top-ranked candidate is yi for all possible values of i {0, (O,...,N
4.3 V-STaR on Math Reasoning and Code Generation
As shown in Fig. 2, V-STaR shows consistent gains across GSM8K, MBPP, MATH subset and HumanEval test sets for LLaMA2 7B and 13B models (Fig. 8) over baselines. In math, we report absolute improvement of 6 to 17% test accuracy over STaRt and Verification, and 4 to 12% in code generation tasks. The gains over V-STaR [1 iter] in Fig. 3 show that iteratively generating solutions to collect verifier training data results better distribution and quality compared to a non-iterative approach with the same generation budget. We show gains in each iteration generator and verifier on MBPP in Fig. We also trained 4th iteration of generator and verifier MBPP which led to marginal gain of 0.3%.
Out-of-domain performance of V-STaR. The generators and verifiers trained on MBPP are evaluated on HumanEval, while those trained on GSMSK are evaluated on subset of MATH test set (see Fig. 2 and Fig. 4). In general, we observe lower absolute Pass@1 and Best-of-64 scores for all methods as these two tasks are considered to more difficult than GSMSK and MBPP. That said, Iterative V-STaR outperforms baselines, and V-STaR [1 iter] on both tasks and across model sizes. Utilizing incorrect solutions to train verifiers results in large improvements than just bootstrapping with correct model generated solutions using
7

---

Published as a conference paper at COLM 2024
62
60
60
50
A
Test Accuracy
Test Accuracy
40
B
58
A 1.0
30
56
20
Pass@1
Majority Voting
Best-af-64
54
V-STaR
10
V-STaR [1 Iter]
52
2k
12k
18k
24k
30k
Number of completions problem
Number of training updates
Figure 6: Left: Best-of-k test accuracy of 7B V-STaR compared to V-STaR[1 Iter] and self- consistency (Wang et al., 2023c) across different numbers of candidate solutions generated on GSM8K. We subsample solutions from N 1000 generations. V-STaR can rank over reasonably large number of candidate solutions. We compute 95% Cls for self-consistency using 256 trials. Right: Comparing DPO-based generator and verifier for V-STaR 7B, measured by Pass@1 and Best-of-64 respectively GSM8K. Best-of-64 accuracy rises significantly while the generation ability of DPO verifier degrades with only 2k updates.
STaR* or RFT. While we use LoRA adapters due to compute constraints, we hypothesize that gains from V-STaR could potentially be larger with full parameter fine-tuning.
Best-of-k accuracy. Fig. 5 shows test accuracy for k 1 to k 64, calculated from 128 candidate solutions per test problem, for 7B models on both tasks. Best-of-1 is equivalent to Pass@1 and ignores verifier scores. Best-of-k saturates for k 16 and the gap between V-STaR [1 Iter] and V-STaR stays consistent.
4.4 Comparing DPO vs. ORM verifiers
We trained ORM style verifiers, as described in 52.2, with LoRA adapters. These verifiers did seem to achieve relatively poor performance compared to DPO-based verifiers. Fig. 5a shows the comparison between the V-STaR Iter] trained with DPO and an ORM style verifier on the same training data. ORM fails to effectively search through generated candidate solutions for number of candidates above the GSM8K task. The ORM style verifier is also performing worse than our DPO based verifier in MBPP for number of candidate solutions above 16.
How many completions can V-STaR be extended to?
Fig. 6 shows the Best-of-K accuracy of V-STaR 7B on GSM8K, measured by Eq. 3 as a function of k. V-STaR outperforms majority voting (Wang al., 2023c) searching over a large number of candidate solutions (see SF in appendix). While V-STaR is far more effective than majority voting for k < 64, the performance gap starts slightly decrease for larger value of k, similar to performance decay reported in Cobbe et al. (2021). Furthermore, V-STaR can be used for any problem solving task where we can verify correctness while majority voting is not applicable to tasks such as code generation. We also tried combining verifier scores with reranking strategies, such as weighted reranking and weighted majority voting Liu et al. (2023), but did not observe performance gains.
4.6 Evaluating DPO verifier generator
Since DPO fine-tuned models can also be used as generators, we evaluate how good is the generation ability of DPO verifiers. Fig. 6 shows Pass@1 and Best-of-64 for V-STaR verifier over training updates, for three different ß coefficients for proximity to SFT policy in DPO objective ($3.1). The verifier's 's solving ability starts degrading only after small number of training updates. In contrast, using the DPO objective for verification seems to be sample efficient as the model's Best-of-64 increases significantly with only 2k training updates.
8

---

Published as a conference paper at COLM 2024
4.7 Should the verifier be in the training loop?
Optionally, one could train intermediate verifiers at each iteration and filter correct solutions to include in PGEN and DVeR provide feedback. This step seems more reasonable with sufficient exploration, that is larger values of k, when sampling k solutions from the generator in each iteration.
We tried putting the verifier in the training loop to filter correct solutions from the generator for the next training iteration. To do so, we sampled k = 64 completions per query from the generator, labeled their correctness, and took only the top 8 based on their verifier score. We take as many samples from the incorrect set so that the total number of correct and incorrect completions per query 16 or less. After running three iterations with verifier in the loop for MBPP, the final Best-of-64 accuracy and Pass@1 are 53.2 and 46.34 respectively.
Our results suggest that having the verifier in the training loop does not provide sub- stantial gain for this task. V-STaR is simpler without the verifier in the loop and there is no need to train a verifier at each iteration; however we did not experiment with other tasks and different sampling strategies from the generator at each iteration. We leave a more detailed study of this question to fu- ture work.
Ver.1
49.7
50.5
52.3
Ver.2
51.1
52.9
53.2
Ver.3
52.7
54.2
55.1
4.8
Gains across V-STaR iteration
Gen.1
Gen.2
Gen.3
Fig. 7 shows the improvements achieved from each iteration of the generator and ver- ifier on MBPP. The gains are larger across iterations of verifiers (from Ver.1 to Ver.3) than iterations of generators which high- lights the importance of verifiers.
Figure 7: Best-of-64 for each V-STaR iteration on MBPP. The performance gets better with each iteration of generator and verifier with- out showing signs of collapsing.
Related work
Challenging multi-step reasoning tasks has driven innovative research on LLMs, such as generating answers given questions via intermediate steps (Wei et al., 2022; Kojima et al., 2022). A large volume of recent work studies ways improve the correctness of these intermediate steps and reducing the cost of arriving at a correct solution.
Self-training and self-improvement. One family of methods, beginning with STaR (Zelik- man et al., 2022), reinforced self-training (Gulcehre et al., 2023), and rejection fine-tuning (Yuan et al., 2023), relies solutions generated by the LLM to update itself. These methods fine-tune the model on generated solutions that yield correct answer. ReSTEM (Singh et al., 2023) view this fine-tuning as expectatio-maxxiizatii solution solution-generating agent. Wang et al. (2023a) propose a contrastive loss make correct solutions more likely than incorrect ones, while Ni et al. (2023a) propose to use intermediate states of successful solutions as supervision to improve credit assignment. Discovery of successful solutions is a difficult exploration problem, and Luong et al. (2024) has shown that RL-based fine-tuning of LLM is difficult unless it is initialized by some steps of super- vised fine-tuning. In An et al. (2023), more powerful LLM was used to edit the incorrect rationales generated by a smaller model and provide positive data for its fine-tuning. How- ever, Huang et al. (2023) argued that LLMss limited in their ability to correct their own reasoning. V-STaR similar to self-improvement methods in that it uses its self self-generated solutions for fine-tuning, but also trains verifier using these solutions, including both correct and incorrect ones.
based RL fine-tuning of
Training verifiers.
Verifiers models that score rank reasoning chains with the aim of favouring successful rationales were introduced for mathematical reasoning tasks by Cobbe et al. (2021), who proposed to collect correct and incorrect rationales from tuned

---

Published as a conference paper at COLM 2024
generator and train verifier. They noted the importance of large training set for the success of the method. Uesato et al. (2022) found that process supervision - correctness of the rationale enhances the performance of fine-tuned LLMs relative to outcome supervision whether the answer is correct or not. Subsequent work correspondingly studied ways of deriving reward signals for individual reasoning steps (Li et al., 2023; Lightman et al., 2024; Yu et al., 2023), combining solution-level and step-level verifiers (Zhu et al., 2023), and augmenting verifiers with auxiliary information, such results of program execution (Ni et al., 2023b). In Ma et al. (2023); Wang et al. (2023b), rationale generation is treated as graph search problem, either using stepwise verifier to guide the search or estimating the quality of steps by Monte Carlo rollouts. In V-STaR, the verifier is trained with DPO, which enjoys high sample efficiency (see Fig. 6), and used for ranking LLM-ggnerated solutions at test-time.
The manner of training the verifier varies between works. The verifier can be viewed reward model trained on human annotations making the training of a generator that on
satisfies the verifier as an instance of RL with human feedback (Ziegler et al., 2019) synthetic data, leading to forms of RL with AT feedback (Bai et al., 2022; Yang et al., 2023). The verifier can alternatively be viewed as a generative model, such as by conditioning on control tokens indicating a positive or negative label of a solution (Korbak et al., 2023) or by extracting the score the likelihood of a special token following the candidate solution (Liu et al., 2023). V-STaR takes the unique approach of using DPO (Rafailov et al., 2023) to contrast the likelihoods of correct and incorrect solutions under the verifier (see $3.1).
6 Conclusion
We propose V-STaR, a data-efficient and simple to implement approach that utilizes correct and incorrect generated solutions from an iteratively trained generator to train strong verifier. We find training verifiers with DPO to be more effective than the common method by Cobbe et al. (2021). Our empirical results show the effectiveness of V-STaR over existing self-im colf-improvement and verification-based methods. V-STaR has the potential to improve existing eelf-improvement loops on wide range of problems with access to correctness feedback during training.
References
Shengnan An, Zexiong Ma, Zeqi Lin, Nanning Zheng, Jian-Guang Lou, and Weizhu Chen. Learning from mistakes makes Ilm better reasoner. arXiv preprint ar arXiv:2310.20689, 2023.
Jacob Austin, Augustus Odena, Maxwell Nye, Maarten Bosma, Henryk Michalewski, David Dohan, Ellen Jiang, Carrie Cai, Michael Terry, Quoc Le, et al. Program synthesis with large language models. arXiv preprint arXiv:2108.0773) 2021.
Yuntao Bai, Saurav Kadavath, Sandipan Kundu, Amanda Askell, Jackson Kernion, Andy Jones, Anna Chen, Anna Goldie, Azalia Mirhoseini, Cameron McKinnon, Carol Chen, Catherine Olsson, Christopher Olah, Danny Hernandez, Dawn Drain, Deep Ganguli, Dustin Li, Eli Tran-Johnson, Ethan Perez, Jamúe Kerr, Jared Mueller, Jeffrey Ladish, Joshua Landau, Kamal Ndousse, Kamile Lukosuite, Liane Lovitt, Michael Sellitto, Nelson Elhage, Nicholas Schiefer, Noemi Mercado, Nova DasSarma, Robert Lasenby, Robin Larson, Sam Ringer, Scott Johnston, Shauna Kravec, Sheer El Showk, Stanislav Fort, Tamera Lanham, Timothy Telleen-Lawton Tom Conerly, Tom Henighan, Tristan Hume, Samuel R Bowman, Zac Hatfield-Dodds, Ben Mann, Dario Amodei, Nicholas Joseph, Sam McCandlish, Tom Brown, and Jared Kaplan. Constitutional AI: Harmlessness from AI feedback. arXiv preprint ar Xri::2212.080777 2022.
Mark Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mo- hammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert- Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji,
10

---

Published as a conference paper at COLM 2024
Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Πlya Sutskever, and Wojciech Zaremba. Evaluating large language models trained on code. Xiv preprint ar Xxxt:22077.03374 2021.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint ar xrii:2210014166, 2021.
Caglar Gulcehre, Tom Le Paine, Srivatsan Srinivasan, Ksenia Konyushkova, Lotte Weerts, Abhishek Sharma, Aditya Siddhant, Alex Ahern, Miaosen Wang, Chenjie Gu, et al. Reinforced self-training (rest) for language modeling. arXiv preprint ar arXit:2308.0899 2023.
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the MATH dataset. Neural Information Processing Systems (NeurIPS) Datasets and Benchmarks, 2021.
Edward J. Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. International Conference on Learning Representations (ICLR), 2022.
Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. Large language models cannot self-correct reasoning yet. Xiv preprint ar Xrii:2330.00198, 2023.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. Large language models are zero-shot reasoners. Neural Information Processing Systems (NeurIPS), 2022.
Tomasz Korbak, Kejian Shi, Angelica Chen, Rasika Bhalerao, Christopher L. Buckley, Jason Phang, Samuel R. Bowman, and Ethan Perez. Pretraining language models with human preferences. International Conference on Machine Learning (ICML), 2023.
Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. Making language models better reasoners with step-aware verifier. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5315-5333, Toronto, Canada, July 2023. Association for Computational Linguistics. doi: 10.18653/v1/2023. acl-long.291. URL https: /ww.aaaaaaaaaaca.ca.acc...o wrw../r...../....... 2023 acl- molg- 291.
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harrison Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step. International Conference on Learning Representations (ICLR), 2024.
Yixin Liu, Avi Singh, C. Daniel Freeman, John D. Co-Reyes, and Peter J. Liu. Improving large language model fine-tuning for solving math problems. arXiv preprint 2xXx::23100100.. 2023.
Trung Quoc Luong, Xinbo Zhang, Zhanming Jie, Peng Sun, Xiaoran Jin, and Hang Li. ReFT: Reasoning with reinforced fine-tuning. Xiv preprint arXi::2401.0890 2024.
Qianli Ma, Haotian Zhou, Tingkai Liu, Jianbo Yuan, Pengfei Liu, Yang You, and Hongxia Yang. Let's reward step by step: Step-level reward model as the navigators for reasoning. arxio preprint arXio:2310.1008. 2023.
Janet Metcalfe. Learning from errors. Annual Review of Psychology, 68(1):465 489, 2017.
11

---

Published as a conference paper at COLM 2024
Ansong Ni, Jeevana Priya Inala, Chenglong Wang, Oleksandr Polozov, Christopher Meek, Dragomir Radev, and Jianfeng Gao. Learning math reasoning from self-sampled correct and cartially-correct solutions. International Conference Learning Representations (ICLR), 2023a.
Ansong Ni, Srini Iyer, Dragomir Radev, Ves Stoyanov, Wen-tau Yih, Sida Wang, and Xi Victoria Lin. LEVER: Learning verify language-to-code generation with execution. International Conference on Machine Learning (ICML), 2023b.
Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishknn, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul F. Christiano, Jan Leike, and Ryan Lowe. Training language models to follow instructions with human feedback. Neural Information Processing Systems (NeurIPS), 2022.
Rafael Rafailov, Archit Sharma, Eric Mitchell, Christopher D Manning, Stefano Ermon, and Chelsea Finn. Direct preference optimization: Your language model is secretly reward model. Neural Information Processing Systems (NeurIPS), 2023.
Baptiste Rozière, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Ttai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, Artyom Kozhevnikov, Ivan Evtimov, Joanna Bitton, Manish Bhatt, Cristian Canton-Ferrer, Aaron Grattafiori, Wenhan Xiong, Alexandre Défossez, Jade Copet, Faisal Azhar, Hugo Touvron, Louis Martin, Nicolas Usunier, Thomas Scialom, and Gabriel Synnaeve. Code llama: Open foundation models for code. ar Xiv preprint ar Xiv:2200.. 12950,, 2023.
Avi Singh, John D. Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil, Xavier Garcia, Peter Liu, James Harrison, Jaehoon Lee, Kelvin Xu, Aaron Parisi, Abhishek Kumar, Alex Alemi, Alex Rizkowsky, Azade Nova, Ben Adlam, Bernd Bohnet, Gamaleldin Elsayed, Hanie Sedghi, Igor Mordatch, Isabelle Simpson, Izzeddin Gur, Jasper Snoek, Jeffrey Pennington, Jiri Hron, Kathleen Kenealy, Kevin Swersky, Kshiteej Mahajan, Laura Culp, Lechao Xiao, Maxwell L. Bileschi, Noah Constant, Roman Novak, Rosanne Liu, Tris Warkentin, Yundi Qian, Yamini Bansal, Ethan Dyer, Behnam Neyshabur, Jascha Sohl- Dickstein, and Noah Fiedel. Beyond human data: Scaling self-training for problem-solving with language models. Xiv preprint ar Xrix:2312.066888 2023.
Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M. Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F. Christiano. Learning to summarize from human feedback. Neural Information Processing Systems (NeurIPS), 2020.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, Dan Bikel, Lukas Blecher, Cristian Canton-Ferrer, Moya Chen, Guillem Cucurull, David Esiobu, Jude Fernandes, Jeremy Fu, Wenyin Fu, Brian Fuller, Cynthia Gao, Vedanuj Goswami, Naman Goyal, Anthony Hartshorn, Saghar Hosseini, Rui Hou, Hakan Inan, Marcin Kardas, Viktor Kerkez, Madian Khabsa, Isabel Kloumann, Artem Korenev, Punit Singh Koura, Marie-Anne Lachaux, Thibaut Lavril, Jenya Lee, Diana Liskovich, Yinghai Lu, Yuning Mao, Xavier Martinet, Todor Mihaylov, Pushkar Mishra, Igor Molybog, Yixin Nie, Andrew Poulton, Jeremy Reizenstein, Rashi Rungta, Kalyan Saladi, Alan Schelten, Ruan Silva, Eric Michael Smith, Ranjan Subramanian, Xiaoqing Ellen Tan, Binh Tang, Ross Taylor, Adina Williams, Jian Xiang Kuan, Puxin Xu, Zheng Yan, Iliyan Zarov, Yuchen Zhang, Angela Fan, Melanie Kambadur, Sharan Narang, Aurélien Rodriguez, Robert Stojnic, Sergey Edunov, and Thomas Scialom. Llama 2: Open foundation and fine-tuned chat models. ar preprint ar arXiv:2307.09288 2023.
Jonathan Uesato, Nate Kushman, Ramana Kumar, H. Francis Song, Noah Y. Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process- and outcome-based feedback. arXiv preprint arXiv:2211.14225, 2022.
Peiyi Wang, Lei Li, Liang Chen, Feifan Song, Binghuai Lin, Yunbo Cao, Tianyu Liu, and Zhifang Sui. Making large language models better reasoners with alignment. arxio preprint ar XrX::22309.02 02144,, 2023a.
12

---

Published as a conference paper at COLM 2024
Peiyi Wang, Lei Li, Zhihong Shao, R. X. Xu, Damai Dai, Yifei Li, Deli Chen, Y. Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce LLMs step-by-step without human annotations. arXio preprint ar wix::2312.08933. 2023b.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. International Conference on Learning Representations (ICLR), 2023c.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoc V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. Neural Information Processing Systems (NeurlPS), 2022.
Kevin Yang, Dan Klein, Asli Celikyilmaz, Nanyun Peng, and Yuandong Tian. RLCD: Reinforcement learning from contrast distillation for language model alignment. ar preprint Xiv:2307. 12950, 2023.
Fei Yu, Anningzhe Gao, and Benyou Wang. Outcome-supervised verifiers for planning in mathematical reasoning. ar Xiv preprint arXio:2311.09772, 2023.
Zheng Yuan, Hongyi Yuan, Chengpeng Li, Guanting Dong, Keming Lu, Chuanqi Tan, Chang Zhou, and Jingren Zhou. Scaling relationship on learning mathematical reasoning with large language models. arXiv preprint ar xxxv:2308.01822 2023.
Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah D. Goodman. Star: Bootstrapping reasoning with reasoning. Neural Information Processing Systems (NeurIPS), 2022.
Xinyu Zhu, Junjie Wang, Lin Zhang, Yuxiang Zhang, Yongfeng Huang, Ruyi Gan, Jiaxing Zhang, and Yujiu Yang. Solving math word problems via cooperative reasoning induced language models. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 4471-4485, Toronto, Canada, July 2023, Association for Computational Linguistics. doi: 10.18653/vv acl-long. 245.
acl..llo..2..5.... 245. URL https: /aclss//oo/n org/
Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. Fine-tuning language models from human prefer- ences. Xiv preprint Xic::109.00599, 2019.
13

---

Published as a conference paper at COLM 2024
A
Algorithm
Algorithm V-STaR
Input: Original data DEFT, Training queries Qquery, base model Gbaser Num generations
Num iterations
DEN SFFT
GSFT - SFT Graser DSFT)
for iter 1 to I do
G + SFT GEN)
(fine-tune generator {generate candidates
S - sample(G, D Qquery, k)
D' - correcttsec))))ss
{score candidates to get z coorect solutions + buffer)
DGEN & DGEN U D [2-1]
{
DYER +- DVER D
fall solutions + DPO buffer)
end for
D pref + preference pairs(DVER) V - DPO(G Prref)
B The prompt used for MBPP few-shot generation.
Following Ni et al. (2023b), we use the following prompt to sample completions per problem for data generation during training.
Write Python function complete the task and pass the assertion tests
Task Start ###
# These are the assertions for your fanction:
assert similar. ((3, 4, 5, 6).(5, 7, 4, 10)) = (4,
... Write function to find the similar elements from the ginen two taple lists. def elements (test_tupl, test.tup2):
res = tuple (stt & set(test.tup2)) return (res)
*8U Task End #80
*н# Task Start ###
These are the assertions for your fanction: is.not.prime
False
*.. Write python function identify nou-prime numbers. *e* import math
def is io.tot.pr (n):
result False
for i in range int (math, (n)) + 1): if
0:
return result = True
### Task End ###
#NB Task Start ###
# These are the assertions for your fanction:
heap-queue.largest [25, 22, 14. 75, 22, 58].3)==185, 75.
... Write function find largest integers from ginen of numbers using heap guene algorithm.
import heapq as hg
def heap queqquuueeu.. wtw.uuuelagesttnmm.e....... largestt
largest.nums = hq nlargest nums)
return largest.nums
#8# Task End ###
14

---

Published as a conference paper at COLM 2024
C
Test accuracy of 13B V-STaR and baselines
80
60
SFT
+30.6
-2..5
STaR!
Test Accuracy
60
-15.0
+14.0
+22.8
Test Accuracy
50
V-STaR
Verification
+14.6
+22.0
50
+17.0417.3
30
20
10
GSM8K
MBPP
GSMBK MATH subsel
MBPP HumanEval
Figure 8: Test accuracy of 13B V-STaR compared to baselines. We report Best-of-64 for verification--ased methods and Pass@1 for others. (Left) Test accuracy for training tasks. (Right) Transfer evaluation of GSM8K and MBPP trained models on MATH subset and HumanEval respectively.
D Candidate solutions y, and ý2 for GSM8K problem
x= Andy walks 50 meters from his house to school. After school, he comes back to the house and goes to the market. If he walks 140 meters total, how many meters is the distance between the house and the market?
y1 = He walks to school and back, which is 2 x 50 meters 100 meters. So he walks 140 meters 100 meters 40 meters to the market. Answer=40
ÿ2 If he walks 50 meters from his house to school, and 140 meters in total, he walks 140 50 = 90 meters from the school to the market. Answer=90
E Example for Best-of-k using Eq. 3
verifier scores
[9, 7, 3..3 3, 2, 2, 0.
0, 2, 3, 4, 5. 6, 7, 8.9
sorted correctness a
[1.0, 1, 0, 0, 1, 0.
1
+ 0
X
+
+
0
3 3
Best-of-4
3
3
10
Figure 9; An example showing how Eq. estimates Best-of-k accuracy efficiently and without variance for k = 4 from N 10 candidate solutions.
15

---

Published as a conference paper at COLM 2024
F
V-STaR us. majority voting example
Every day, Wendi feeds each of her chickens three cups of mixed chicken feed, containing seeds, mealworms and vegetables to help keep them healthy. She gives the chickens their feed in three separate meals. In the morning, she gives her flock of chickens 15 cups of feed. In the afternoon, she gives her chickens another 25 cups feed. How many cups of feed does she need to give her chickens in the final meal of the day if the size of Wendi's flock is 20 chickens?
V-STaR solution Wendi feeds each of her 20 chickens 3 cups of feed per day for a total 20x3=60 cups of feed. She gives the chickens 15 cups in the morning and 25 cups in the afternoon for total of 15+25=40 cups. Therefore, she needs to give the chickens 60-40=20 cups of feed in the final meal of the day. Answer=20
Majority voting solution = The total amount of feed Wendi gives the chickens is 15 25 40 cups of feed. Wendi has 20 chickens she needs to give each chicken 40 / 20 2 cups of feed. Answer=2
G Best-of-k using Eq. us. Best-of-k from Lightman et al. (2024)
0.64
0.6
Test Accuracy
0.55
0.5
Best-of-k (à la Lightman et al., (2024))
Best-of-k (formula)
0.45
1
8
16
32
64
Number of candidate solutions (k)
Figure 10: Eq. 3 estimates Best-of-k accuracy efficiently and without variance. For Best-of-K accuracy without the formula, the process is repeated 32 times.
16


Reviews:
[{"review_id": "1M2gMwpJY6", "reviewer": "Reviewer_THgs", "summary": "The paper introduces a method that leverages the incorrect reasoning paths generated by LLM during SFT progression to train a Verifier. This Verifier, in turn, helps in selecting the correct answer during inference. The experimental results demonstrate a significant improvement in performance on both the math dataset and the code generation dataset, and the model also exhibits strong performance in transfer experiments.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": true, "final_justification": "", "rebuttal": "**Summary:** Added self-eval comparison, transfer to Mistral and addressed concerns\n\nThank you for your comments. We are glad that the reviewer finds our method pioneering the utilization of negative data and our improvement significant.\n\n**Comparison with self-evaluation:** Based on your suggestion, we tried using the last generator (iteration 3) of GSM8k as the verifier to pick the best answer using the log-probability of the answer under the generator. This self-evaluation method outperforms pass@1 but substantially underperforms majority-voting and V-STaR. \n\nPass@1: 45.6   \nMajority@64: 60.9   \nSelf-evaluation@64: 50.9  \nV-STaR@64 : 62.7 \n\n**Transferability of verifier:** To do so, we tested our 7B Llama2-based verifier on candidate answers from Mistral 7B on GSM8K (8 shot). This verifier outperforms Majority-voting on Mistral 7B. This shows the transferability of our verifiers to other LLMs\n\nMistral 7B 8-shot:  \nPass@1: 32.2  \nMaj@64: 58.6  \nVer@64: 60.2  \n\n**Models:** As mentioned earlier, our preliminary results on Mistral 7B show the transferability of our verifiers. For clarification, Mistral 7B Maj@64 is well below that of our iteration 3 generator based on LLama2 7B. All of the baselines to which we compare V-Star to are finetuned LLama 2 or CodeLlama models.\nExperiments on Gemma could not have been done as it was released too late (Feb 21st), and we did not have the time or computation to experiment with it.\n___\n\n_We hope that most of your concerns have been addressed and, if so, we would appreciate it if you could reconsider your assessment. We’d be happy to engage in further discussions._", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. This paper pioneers the utilization of incorrect labels to train a verifier, showcasing its potential utility across various scenarios.\n2. The experimental results reveal a significant improvement in performance for Llama2 across both the math and code datasets.", "reasons_to_reject": "1. The effectiveness of the verifier remains underexplored. While the paper compares it with majority voting in their baseline, further investigation is warranted given the crucial role the verifier plays. For instance, it is imperative to determine whether the verifier outperforms self-evaluation when selecting answers [1] and during decoding [2] [3]. Failure to do so may leave the utility of the verifier incompletely assessed.\n2. The transferability of the verifier remains unexplored. Demonstrating its ability to be transferred to other models would be valuable, as it would reduce the need to train independent verifiers for each model, thereby streamlining the process.\n3. The method is tested on Llama2 whose reasoning ability is far from the sota model such as mistral and gemma, which may make the method less general.\n\n[1] Adaptation with Self-Evaluation to Improve Selective Prediction in LLMs, EMNLP 2023\n\n[2] Tree of Thoughts: Deliberate Problem Solving with Large Language Models, Neurips 2023\n\n[3] Self-Evaluation Guided Beam Search for Reasoning, Neurips 2023", "questions_to_authors": "Please refer to questions.", "extra_scores": {}}, {"review_id": "JutfB30XPt", "reviewer": "Reviewer_zjMQ", "summary": "The paper modifies STaR (Zelikman et al., 2022) to make use of the sampled incorrect solutions by training an additional verifier that is used at test time to rank candidate solutions. To make use of both correct and incorrect solutions, the authors propose to train the verifier as a reward model using Direct Preference Optimization. During each iteration of STaR, the verifier is trained on a union of the collected samples so far from the policy model.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Summary:** Figure showing verifier performance for each iteration, justifying DPO, answered questions\n\nThank you for your valuable feedback. We are glad that the reviewer finds our paper well written with a clear motivation and contribution, and finds our proposed method of leveraging preference optimization to learn from correct and incorrect solutions interesting.\n\n**Training iterations:** We trained only for 3 iterations due to computation limits similar to Yuan et al., (2024). In [this](https://ibb.co/Y8rCsBY) plot we show the gains in each iteration for MBPP. We also trained a 4th iteration of generator and verifier for MBPP, and only observed a marginal improvement of 0.3% in Ver@64. We will update the paper with this figure.\n\n**Why DPO:** The classification loss and the language modeling loss of typical verifiers could be joined as the DPO objective. The task of learning a verifier seems like a reward modeling task, and we made this connection to train with DPO. We found DPO trained verifiers to be more robust than ORM style verifiers for math and coding problems (Figure 5 in the paper). This could be partly due to using LoRA adaptors or the contrastive nature of DPO’s objective. Due to compute constraints, we are not able to test DPO verifiers against ORMs (à la Lightman et al., 2024) without LoRA adapters. Coincidentally, some of the top reward models on Reward Bench (Lambert et al., 2024) are also DPO based. \n\n**ORM as PRM:** Since our verifier outputs a log-probability for a candidate answer, we can only use them as ORMs to rank candidate solutions. That said, we manually inspected a number of model generated solutions under the verifier to see if the log-probability starts to drop at a certain step for wrong solutions, but this was not the case.\n\n**ORM details and false positives:** We train our ORMs using a combination of language modeling and a classification objective as discussed in sec. 2.2. Our ORMs are trained with the same data as our DPO based verifiers. It is possible that DPO is more robust against false positives since DPO’s contrastive objective only assumes that a false positive is **better** than an incorrect response, but ORM assumes that a false positive response **is correct**.\n\nLightman et al., 2024 Let's Verify Step by Step  \nLambert et al., 2024 RewardBench  \nYuan et al., 2024 Self-Rewarding Language Models\n ___\n_We hope that your concerns/questions have been addressed. We’d be happy to engage in further discussions._", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* Paper is well written with a clear motivation and contribution\n* Impressive performance boost on different reasoning tasks. \n* The direction of leveraging preference optimization approaches for learning from suboptimal solutions is interesting and exciting.", "reasons_to_reject": "* Why use DPO? I feel the justification for using DPO is not clear, and no analysis is done to understand why it is performing better than standard ORM.\n* Lack of analysis on the trained verifier. It would be very interesting to see if the trained verifier was able to learn a process reward model (PRM) by only training using final answer labels.", "questions_to_authors": "* How was the ORM trained? and what is the intuition behind why it performs very poorly compared to DPO? Khalifa et al., 2023 mentions that ORM can perform poorly if many of the correct solutions involve bad reasoning and the LM was able to reach these solutions arbitrarily. Do you have a similar observation? It would be interesting to draw connection with existing work.  \n* Why train only for 3 iterations? What happens to the verifier performance if you train for more iterations? I'm surprised you do not have a plot showing verifier performance after each STaR iteration.   \n\n**References:**\n\nKhalifa et al., \"Discriminator-guided multi-step reasoning with language models.\" arXiv preprint arXiv:2305.14934 (2023).", "extra_scores": {}}, {"review_id": "gR2MnCgkSN", "reviewer": "Reviewer_opuK", "summary": "The paper presents an iterative approach to train LLMs to become better at math and code tasks by utilizing the models own generations. Concretely, the approach makes use of multiple samples generated by the model, keeping only the correct generations, and then training the model with this new subset. Additionally, the approach relies on a test time candidate selection model which is trained using the model generations using DPO, thereby further improving performance. The approach presents strong test accuracy improvement on popular math and code benchmarks.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Summary:** Added transfer to Mistral, gains in each V-Star iteration, and addressed concerns\n\nWe thank the reviewer for their insightful comments. We are glad that the reviewer likes our proposal of leveraging both positive and negative samples for self-improving the model. We are happy that the reviewer finds our improvements strong on hard in-distribution and out-of-distribution tasks.\n\n**Regarding training iterations:** We trained only for 3 iterations due to computation limits similar to Yuan et al., (2024). In [this](https://ibb.co/Y8rCsBY) plot we show the gains in each iteration for MBPP. We also trained a 4th iteration of generator and verifier for MBPP, and only observed a marginal improvement of 0.3% in Ver@64. The performance gets better with each iteration of generator and verifier without the models showing signs of collapsing. We will update the paper with this figure.\n\n**Other models:** Thank you so much for this suggestion. We tested our 7B Llama2-based verifier on candidate answers from Mistral 7B on GSM8K (8 shot). This verifier outperforms Majority-voting on Mistral 7B. This shows the transferability of our verifiers to other LLMs.\n\nMistral 7B 8-shot:  \nPass@1: 32.2  \nMaj@64: 58.6  \nVer@64: 60.2  \n\n**Regarding Fig.6:** We do compute 95% CI in this figure as mentioned in the caption. The CI is extremely small. \n\n**DPO verifier as generator:** It is often the case that during training with DPO, the log-probability of preferred/correct samples goes down. This is observed in a number of works such as Rafailov et al., 2024. This could explain why our DPO trained verifier does poorly on generation. \n\n**Manually filtering data for verifier-in-the-loop:** Indeed this is a great suggestion. Experimenting with different sampling and filtering strategies at each iteration would be interesting and we hope that our work serves as the foundation for future work.\n\n**Emergence of linguistic patterns:** This is an interesting suggestion. We manually checked a few samples across iterations but did not identify any specific linguistic patterns.\n\n\nYuan et al., 2024 Self-Rewarding Language Models  \nRafailov et el., 2024 : From r to Q∗: Your Language Model is Secretly a Q-Function. \n\n\n___\n\n_We hope that your concerns/questions have been addressed. We’d be happy to engage in further discussions._", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- Simple method which works. Authors continually train generators by sampling trajectories and manually filtering the correct answers, thereby making the generator more tuned to output the correct answers.\n- Combined with a verifier which is trained on DPO, the VSTAR approach makes good use of the verifier during testing to further prune likely incorrect solutions.\n- Strong improvements on hard tasks such as GSM8k, MBPP (in-distribution) and MATH, HumanEval (out-of-distribution).", "reasons_to_reject": "- It is not clear how many iterations ($T$) of training V-STAR is optimal. Authors use three iterations, but more study needs to be done on the impact of the number of iterations to find the ceiling of performance.\n- Ablations are needed to understand how many iterations ($T$) of data collections are needed for the verifier as well. As the generator gets better at each iteration, the verifier should get harder data, thereby improving its performance.\n- A small limitation of this paper is that the proposed approach is only verified against Llama 2 and CodeLLama. It is unclear whether this approach is general across several openly available models.", "questions_to_authors": "_Questions_\n\n- Fig 6 is missing the 95% CI done over 256 trials - it would be good to add them here.\n- Section 4.6 is confusing to me: why does the DPO trained verifier does poorly on generation? The model gets good at assigning log likelihoods to correct and incorrect trajectories, so wouldn't the generation reflect that too?\n- Adding the verifier in training not getting substantial gain is a bit obvious, right? The verifier initially is noisy as it doesn't do a good job at filtering the correct solutions. Did you try a schedule of training verifier with manually filtered data from generation, and then using it during training?\n\n_Suggestions_\n\n- It would be interesting to measure the forgetting effect with more and more iterations. Does the model collapse when trained for increasing number of iterations?\n- Does any linguistic pattern of the solutions emerge with increasing iterations?", "extra_scores": {}}, {"review_id": "zTlUcWEndR", "reviewer": "Reviewer_H7mN", "summary": "This paper proposes V-STaR, an approach to boost small LMs' reasoning performance by combining two lines of existing work---1) Self-Taught Reasoner/Rejection Sampling Fine-tuning, where LMs are iteratively fine-tuned only on correct self-generated solutions and 2) Oversample-then-rerank, where multiple solutions are sampled for each test question and a verifier scores the correctness of each solution. Both in-domain and cross-domain evaluation results suggest the effectiveness of their approach across math reasoning and code  generation tasks. The intuition behind the improvement is that the verifier training learns from mistakes in the incorrect generations discarded by the STaR/RFT training.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback. \n\nWe are glad that the reviewer finds our approach simple, effective and improvements to be significant. As such, we believe that it will be straightforward for other people to adopt and extend our method.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. A simple yet effective approach that combines the benefits of both STaR and verification to boost reasoning in fine-tuned smaller LMs.\n2. The paper highlights the superiority of the DPO-based verifier over the previous ORM-based one, which is a novel discovery for me.\n3. Improving reasoning in LLM is an important topic of widespread interest within the community. This paper will establish foundations for future work in this field.", "reasons_to_reject": "1. While the improvements over the baseline are significant, the technical contribution is somewhat less exciting due to the straightforward combination of existing STaR and Verification techniques.", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper introduces V-STaR to enhance the reasoning capabilities of small LMs on math and code reasoning tasks by leveraging their own generations. V-STaR integrates two main strategies: 1) Self-Taught Reasoner/Rejection Sampling Fine-tuning, where LMs are iteratively fine-tuned on correct self-generated solutions, and 2) Oversample-then-rerank, where multiple solutions are generated and a verifier scores each solution to identify the most accurate one. This verifier is trained using a combination of correct and incorrect solutions to discern the quality of generated outputs. Experimental results demonstrate significant improvements in performance on both in-domain and cross-domain tasks. 

Overall, this paper is novel in terms of using incorrect responses in training a verifier, which shows substantial improvements in Llama2 performance. The approach is simple yet effective, with the results demonstrating significant performance boosts on challenging tasks and showing promise in boosting reasoning capabilities in smaller fine-tuned LMs. There are several places the work can improve:

- The effectiveness and capabilities of the verifier can be further explored. 

- Moreover, analysis of why DPO is preferred over ORM and whether the verifier can function effectively as a process reward model is needed to justify the contribution of the proposed method.

- Further experiments are needed to apply the methods beyond Llama2.
Decision: Accept