V-STaR: Training Verifiers for Self-Taught Reasoners

Authors: arian  hosseini
xingdi  yuan
nikolay  malkin
aaron  courville
alessandro  sordoni
rishabh  agarwal
google  deepmind
Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-22 21:01:36

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.

Main paper: 
 introduction: 
 Learning to recognize and correct mistakes is a 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 ReST EM (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 a 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 at test time (Cobbe et al., 2021; Wang et 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 a dataset of solutions generated from a 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-Taught Reasoners (V-STaR). The key idea in V-STaR is to utilize both the correct and incorrect LLM-generated solutions during the iterative selfimprovement process to train a verifier using DPO 1 (Rafailov et al., 2023) , in addition to training a LLM as generator using correct solutions (Fig. 1 ). The iterative self-improvement process yields progressively improved generators, trained on augmented data, which leads We empirically evaluate V-STaR to improve reasoning capabilities of LLMs: (1) Math problem-solving using GSM8K (Cobbe et al., 2021) and a subset of MATH (Hendrycks et 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) , we compare V-STaR to other self-improvement (RFT, STaR) and verification-based methods (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 a 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) on GSM8K, and nearly match CodeLLaMA 34B (zero-shot) on HumanEval.Our contributions are:• We propose V-STaR, a 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 a 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 a formula for Best-of-k ( §4.2), akin to Pass@k, to reliably evaluate test performance with verification. 
preliminaries: 
 Given a pretrained language model G and the original training data of a task D SFT = {(x 1 , y 1 ), (x 2 , y 2 ), • • • (x N , y N )}, where x is typically a description of a 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:EQUATIONwhere G is also referred to as generator in reasoning tasks. LLMs can be used to generate high quality chain-of-thought rationales or solutions for a range of tasks. This observation D SFT ✗ ✗ VERIFICATION D SFT D SFT ∪ GENERATED ✗ STAR CORRECT GENERATED t-1 ✗ ✓ RFT (STAR † [1 ITER]) D SFT ∪ CORRECT GENERATED ✗ ✗ STAR † D SFT ∪ CORRECT GENERATED <t ✗ ✓ V-STAR [1 ITER] D SFT ∪ CORRECT GENERATED D SFT ∪ GENERATED ✗ V-STAR D SFT ∪ CORRECT GENERATED <t D SFT ∪ GENERATED <t ✓has motivated using correct generations from the model itself to bootstrap problem-solving and reasoning abilities (Zelikman et al., 2022; Singh et al., 2023; Yuan et al., 2023) .Self-Taught Reasoner (STaR; Zelikman et al., 2022) corresponds to an iterative approach where a language model improves itself using correctness feedback. In each iteration, one solution ŷ is generated using greedy decoding from the generator G for each problem x in training dataset D. Having access to test cases or ground truth answers, generated solutions can be checked for their binary correctness label z by z = is correct(x, ŷ), z ∈ {0, 1}. A completion ŷ is labeled correct if it has the same final answer as the ground truth answer for math problems, or if it passes all the test cases for code generation problems. Only correct solutions (z = 1) are included in the dataset at iteration j whereD j = {(x 1 , ŷ1 ), (x 2 , ŷ2 ), • • • (x N , ŷN )}.Then, the generator is fine-tuned on this new dataset using (Eq. 1) where D SFT = D j . This fine-tuned generator is used in subsequent iterations.Rejection Sampling Fine-tuning (RFT; Yuan et al., 2023) first fine-tunes a pretrained LM on the training dataset D SFT to obtain G. For each problem x i , k solutions are sampled { ŷi,j ∼ G(y|x i )} k j=1 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 j , and G is fine-tuned on the new D j to obtain G RFT . Unlike STaR, RFT is not an iterative approach.STaR † . Each STaR iteration can be performed similarly to RFT, akin to ReST EM (Singh et al., 2023) . Since there could be multiple correct solutions for a problem, one could sample k 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. Cobbe et al. (2021) trained verifiers, which they refer as outcome-supervised reward model (ORM), that assess the probability that a candidate solution is correct for a 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 as Best-of-k. To train a verifier V, similar to RFT, k candidate solutions are sampled from a generator G for each training problem and labeled for their correctness z to make the verifier training data D VER = {(x i , ŷi,j , z i,j )} N i=1 , where z i,j is a binary label indicating whether ŷi,j is a correct or incorrect solution.To train the verifier V, Cobbe et al. (2021) fine-tune a LLM on D VER using a combination of language modeling (Eq. 1) and binary classification. The model is trained to predict ŷi,j given x i and z i,j given {x i ; ŷi,j } with the language modeling and the classification objective, respectively. See §5 for more details.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 so is to D pref = {(x i , y + i , y - i )} N i=1, 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) a pretrained LLM on the downstream task to obtain G SFT , which is also used as a reference policy. Given the preference dataset D pref and G SFT , DPO's objective increases the log likelihood, relative to the reference policy, of preferred y + to dispreferred y -completions. We present the DPO loss later in Eq. 2, in the context of training verifiers. 
v-star: verifiers for self-taught reasoners: 
 Existing self-improvement methods, such as RFT, STaR, and ReST EM , throw away incorrect model-generated solutions. However, incorrect solutions can also contain valuable information: a language model could learn from discrepancies between correct and incorrect solutions for a given problem, and identify error patterns in generations, enhancing its ability to provide more accurate solutions. In this work, we propose V-STaR that utilizes both incorrect and correct generated solutions in an iterative process to train a better generator and verifier (see algorithm 1 in appendix).• First, we fine-tune a pretrained LLM G base on the original training data D SFT to obtain generator G SFT . • Next, we sample k completions for each problem in the training data from the generator { ŷi,j ∼ G(y|x i )} k j=1 , where x ∈ D query (see §D for an example). • Generated solutions are labeled for their correctness z using ground truth answers or test cases. We use only correct generated solutions (z = 1) to augment the generator training data D GEN as (x i , ŷi,j ). Both correct and incorrect generated solutions are added to verifier data D VER with their correctness label as (x i , ŷi,j , z i,j ), so the verifier can learn from generator's mistakes.• In the next iteration t, the generator G t is obtained by fine-tuning the pretrained model G base on the augmented D GEN . We can sample solutions again from this generator G t . This process is repeated for up to T iterations to augment D GEN and D VER iteratively.• The final generator G T is obtained by using D GEN to fine-tune a pretrained model G base .The verifier V T is obtained by using D VER to further train a model G SFT which was fine-tuned on the original D SFT . baseline is trained with data consisting of 3 × 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 on par with CodeLLaMA 34B, which has a 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 et al. ( 2021) is that our verifier training data is collected iteratively, each iteration from a better generator, while ORM only collects data from a fixed generator that is only fine-tuned on the original SFT data. We compare to this ORM approach as a baseline, as discussed in §4.1.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 a proxy for the language modeling objective while the classification loss is a proxy for reward modelling. Empirically, we found DPO verifiers to be better than ORM-style verifiers ( §4.4), when using LoRA adapters (Hu et al., 2022) .To use DPO for training verifiers, we construct a preference pair dataset using collected solutions in D VER . We treat correct solutions as preferred and incorrect solutions as not preferred completions given the problem. Specifically,D VER = {(x i , y + i,1 , y - i,1 ), • • • , (x i , y + i,m , y - i,m )} N i=1, where m is the number of preference pairs which are from the Cartesian product of correct and incorrect solutions. We train our verifier V using this constructed D VER and the SFT policy G SFT using the DPO objective, L DPO (V; G SFT ):EQUATION)where σ is the logistic function, and β is a hyper-parameter controlling the proximity to the reference policy G SFT . 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 a generated solution given a problem under the trained DPO verifier (i.e. V( ŷ|x)) as scores to rank candidate solutions. 
empirical results: 
 To demonstrate the effectiveness of V-STaR, we conduct experiments on two widely used datasets: GSM8K (Cobbe et al., 2021) for solving math problems, and MBPP (Austin et al., 2021) for code-generation problems. We also evaluate the transfer generalization performance 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 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 are trained with a causal language modeling objective, and our baseline (V-STaR[1 Iter]) and V-STaR verifiers are trained using DPO. The reference policy G SFT for DPO is trained on the original training data for 2 and 3 epochs for GSM8K and MBPP, respectively. See §3.1 for details.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 GSM8K 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.We run V-STaR for 3 iterations and sample k = 16 solutions at each iteration to augment D GEN and D VER . To assess the gains from our iterative approach, we compare against a number of baselines (Table 1 ):1. SFT: Standard fine-tuning (Eq. 1) on training data without any self-improvement or test-time verification. 2. STaR † : Bootstrapping a generator by sampling k = 16 completions per query for 3 iterations, see §2.1. 3. RFT: Running STaR † by sampling 3 × 16 completions for only 1 iteration, see §2.1. 4. Verification (SFT + Verifier): Generating 3 × 16 completions using SFT generator to train a verifier, as described in §2.3. This is similar to ORM verification approach by (Cobbe et al., 2021) but empirically performs better (Fig. 5 ). 5. V-STaR [1 Iter]: Bootstrapping a generator and training a verifier for 1 iteration with k = 3 × 16 completions from G SFT , 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 STaR † generator and pick the majority-vote answer. At inference, we 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 is used for all verifier-based methods, using the formula in (Eq. 3), as well as the self-consistency baseline.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 a 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 to 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 §E in appendix), using the following formula:Best-of-k := 1( N k ) N-k ∑ i=0 N -i -1 k -1 α i (3)where [α 0 , . . . , α N-1 ] are the binary correctness values (0 or 1) for the N candidates y i sorted in decreasing order by their verifier score. The numerator here can be derived by considering subsets where the top-ranked candidate is y i for all possible values of i ∈ {0, . . . , Nk -1}.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% in test accuracy over STaR † 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 in a better distribution and quality compared to a non-iterative approach with the same generation budget. We show gains in each iteration of generator and verifier on MBPP in Fig. 7 . We also trained a 4th iteration of generator and verifier on MBPP which led to a 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 GSM8K are evaluated on a 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 be more difficult than GSM8K 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 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 = 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.We trained ORM style verifiers, as described in §2.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 [1 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 4 in 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.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 et al., 2023c) at searching over a large number of candidate solutions (see §F in appendix). While V-STaR is far more effective than majority voting for k ≤ 64, the performance gap starts to 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.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 solving ability starts degrading only after a 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.Optionally, one could train intermediate verifiers at each iteration and filter correct solutions to include in D GEN and D VER to 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 is 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.Figure 7 : Best-of-64 for each V-STaR iteration on MBPP. The performance gets better with each iteration of generator and verifier without showing signs of collapsing.Our results suggest that having the verifier in the training loop does not provide a substantial 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 future work.Fig. 7 shows the improvements achieved from each iteration of the generator and verifier on MBPP. The gains are larger across iterations of verifiers (from Ver.1 to Ver.3) than iterations of generators which highlights the importance of verifiers. 
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 to 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 (Zelikman et al., 2022) , reinforced self-training (Gulcehre et al., 2023) , and rejection fine-tuning (Yuan et al., 2023) , relies on solutions generated by the LLM to update itself. These methods fine-tune the model on generated solutions that yield a correct answer. ReST EM (Singh et al., 2023) view this fine-tuning as expectation-maximization based RL fine-tuning of a solution-generating agent. Wang et al. (2023a) propose a contrastive loss to 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 a LLM is difficult unless it is initialized by some steps of supervised fine-tuning. In An et al. ( 2023), a more powerful LLM was used to edit the incorrect rationales generated by a smaller model and provide positive data for its fine-tuning. However, Huang et al. (2023) argued that LLMs are limited in their ability to correct their own reasoning. V-STaR is similar to self-improvement methods in that it uses its self-generated solutions for fine-tuning, but also trains a verifier using these solutions, including both correct and incorrect ones.Training verifiers. Verifiers -models that score or 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 a tuned generator and train a verifier. They noted the importance of a 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 as results of program execution (Ni et al., 2023b) . In Ma et al. (2023) ; Wang et al. (2023b) , rationale generation is treated as a graph search problem, either using a 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 a high sample efficiency (see Fig. 6 ), and is used for ranking LLM-generated solutions at test-time.The manner of training the verifier varies between works. The verifier can be viewed a reward model trained on human annotations -making the training of a generator that satisfies the verifier as an instance of RL with human feedback (Ziegler et al., 2019) -or on synthetic data, leading to forms of RL with AI 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 as 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). 
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 a 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-improvement and verification-based methods. V-STaR has the potential to improve existing self-improvement loops on a wide range of problems with access to correctness feedback during training.  
 
 Appendix: D GEN ← D SFT G SFT ← SFT(G base , D SFT ) for iter = 1 to T do G ← SFT(G base , D GEN ) {fine-tune generator} S ← sample(G, D query , k) {generate candidates} D ′ ← label correctness(S) {score candidates to get z} D GEN ← D GEN ∪ D ′ [z=1] {correct solutions → buffer} D VER ← D VER ∪ D ′ {all solutions → DPO buffer} end for D pref ← preference pairs(D VER ) V ← DPO(G SFT , D pref )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.# W r i t e Python f u n c t i o n t o c o m p l e t e t h e t a s k and p a s s t h e a s s e r t i o n t e s t s .# ## T a s k S t a r t ### # T h e s e a r e t h e a s s e r t i o n s f o r y o u r f u n c t i o n : a s s e r t s i m i l a r e l e m e n t s ( ( 3 , 4 , 5 , 6 ) , ( 5 , 7 , 4 , 1 0 ) ) == ( 4 , 5 ) """ W r i t e a f u n c t i o n t o f i n d t h e s i m i l a r e l e m e n t s f r o m t h e g i v e n two t u p l e l i s t s . """ def s i m i l a r e l e m e n t s ( t e s t t u p 1 , t e s t t u p 2 ) : r e s = t u p l e ( s e t ( t e s t t u p 1 ) & s e t ( t e s t t u p 2 ) ) r e t u r n ( r e s ) # ## T a s k End ### # ## T a s k S t a r t ### # T h e s e a r e t h e a s s e r t i o n s f o r y o u r f u n c t i o n : a s s e r t i s n o t p r i m e ( 2 ) == F a l s e """ W r i t e a p y t h o n f u n c t i o n t o i d e n t i f y non-p r i m e numbers . """ import math def i s n o t p r i m e ( n ) : r e s u l t = F a l s e f o r i in range ( 2 , i n t ( math . s q r t ( n ) ) + 1 ) : i f n % i == 0 : r e s u l t = True r e t u r n r e s u l t # ## T a s k End ### # ## T a s k S t a r t ### # T h e s e a r e t h e a s s e r t i o n s f o r y o u r f u n c t i o n : a s s e r t h e a p q u e u e l a r g e s t ( [ 2 5 , 3 5 , 2 2 , 8 5 , 1 4 , 6 5 , 7 5 , 2 2 , 5 8 ] , 3 ) = = [ 8 5 , 7 5 , 6 5 ] """ W r i t e a f u n c t i o n t o f i n d t h e l a r g e s t i n t e g e r s f r o m a g i v e n l i s t o f numbers u s i n g h e a p q u e u e a l g o r i t h m . """ import heapq as hq def h e a p q u e u e l a r g e s t ( nums , n ) : l a r g e s t n u m s = hq . n l a r g e s t ( n , nums ) r e t u r n l a r g e s t n u m s # ## T a s k End ### F V-STaR vs. majority voting example x = 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 of 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? This subset includes a 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 a number and no latex exists in the question. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
3. 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.

[1] Adaptation with Self-Evaluation to Improve Selective Prediction in LLMs, EMNLP 2023

[2] Tree of Thoughts: Deliberate Problem Solving with Large Language Models, Neurips 2023

[3] Self-Evaluation Guided Beam Search for Reasoning, Neurips 2023
questions: questions: Please refer to questions.
paper_summary: paper_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.
strength_weakness: strength_weakness: * 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.
* 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: questions: * 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.  
* 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.   

**References:**

Khalifa et al., "Discriminator-guided multi-step reasoning with language models." arXiv preprint arXiv:2305.14934 (2023).
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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.
- 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: questions: _Questions_

- Fig 6 is missing the 95% CI done over 256 trials - it would be good to add them here.
- 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?
- 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?

_Suggestions_

- 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?
- Does any linguistic pattern of the solutions emerge with increasing iterations?
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

Comments: title: Reply to Authors
Re-self evaluation results
Reply to Rebuttal
Thanks for the response
comment: Thank you for the further clarification and explanation. This addresses some of my concerns about the self-evaluation experiments. I would probably still suggest including experiments comparing to other standard baselines (like Tree-of-Thought or Self-Evaluation Beam Search) in the next version.
There might be some confusion about our self-evaluation results. 

As mentioned by the reviewer, we ignored the verifier indeed and used the self-evaluation of the model (which we call generator), using the log probability of generated solution under the model, to score 64 solutions and pick the one with highest self-evaluation score. We found that doing so (self-eval@64) was better than pass@1 performance but worse than using the verifier (verifier@64) to pick the solution. Here, our generator correspond to running STaR for 3 iterations (and does not involve the verifier). 

Hope this clarifies the results we reported in the rebuttal. Please let us know if you were thinking something else for the self-evaluation baseline.
Thank you for incorporating additional experiments, which partially address my concern. Taking into account the transferability of the verifier, which is beneficial for the scalability and applicability of the method, I have revised my score to 6. However, the self-evaluation experiments are not convincing. My initial thought was to not use the verifier that you trained at all, but to use the self-evaluation of the model itself as the verifier.
We are grateful for all of the reviewers' constructive and valuable comments. The reviewers consider V-STaR to be simple, effective, and foundational for future work in this field. We are happy that they find our improvements impressive and strong on hard math and coding tasks. Based on reviewers’ feedback, we have made following main changes:
* **Comparison with self-evaluation** showing that it substantially underperforms majority-voting and V-STaR.
* We will add [this plot ](https://ibb.co/Y8rCsBY) **showing gains in each V-STaR iteration** for MBPP. 
* We also trained a 4th iteration of generator and verifier for MBPP which led to a marginal improvement of 0.3% in Ver@64. 
* **Transferability of the verifier** by testing our 7B LLama2-based verifier on candidate answers from Mistral 7B on GSM8k. This verifier outperforms Majority-voting on Mistral 7B.
Thanks for the detailed response and incorporating the suggestions. Adding the transferability results to the paper would be quite useful!
Thank you for your further comments.

Our main contribution is training verifiers using negative data generated during the self improvement process. As such, how we train verifiers is an empirical choice and depends on several factors such as using full or parameter efficient fine-tuning. Nevertheless, we compared two methods of training verifiers: (1) ORM (Cobbe et al, 2021) which corresponds to reward modeling combined with SFT, (2) DPO. Empirically, we found that when using LoRA, DPO results in better verifiers for GSM8K and comparable on MBPP, as shown in Figure 5.

That said, V-STaR can be instantiated with any approach for training verifiers, and we have launched verifier training with contrastive loss used by Khalifa et al, as we believe it would make our work stronger! We’d include these results in the revision and post here as well if the experiments finish in time.
Dear Reviewer THgs,

We would like to thank you again for your detailed reviews. 

In short, we added comparison with self-evaluation based on your suggestion, transferability of verifier to Mistral 7B on GSM8K, and addressed your concerns about using other models.

We would be happy to do any follow-up discussion or address any additional comments.
Thank you for the rebuttal and the clarifications. 

I'm still not convinced as to why DPO was chosen to train the verifier as opposed to a simple contrastive objective such as $\log({\sigma(r(y^+)) - \sigma(r(y^-))})$ as was used by Khalifa et al, and others. My intuition is that this will perform just as well as DPO if not better. I believe this is a crucial baseline.