RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-Fold

Authors: amrith  setlur
saurabh  garg
young  geng
naman  garg
virginia  smith
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 09:06:37

Abstract: Training on model-generated synthetic data is a promising approach for finetuning LLMs, but it remains unclear when it helps or hurts. In this paper, we investigate this question for math reasoning via an empirical study, followed by building a conceptual understanding of our observations. First, we find that while the typical approach of finetuning a model on synthetic correct or positive problem-solution pairs generated by capable models offers modest performance gains, sampling more correct solutions from the finetuned learner itself followed by subsequent fine-tuning on this self-generated data doubles the efficiency of the same synthetic problems. At the same time, training on model-generated positives can amplify various spurious  correlations, resulting in flat or even inverse scaling trends as the amount of data increases. Surprisingly, we find that several of these issues can be addressed if we also utilize negative responses, i.e., model-generated responses that are deemed incorrect by a final answer verifier. Crucially, these negatives must be constructed such that the training can appropriately recover the utility or advantage of each intermediate step in the negative response. With this per-step scheme, we are able to attain consistent gains over only positive data, attaining performance similar to amplifying the amount of synthetic data by $\mathbf{8 \times}$. We show that training on per-step negatives can help to unlearn spurious correlations in the positive data, and is equivalent to advantage-weighted reinforcement learning (RL), implying that it inherits robustness benefits of RL over imitating positive data alone.

Main paper: 
 introduction: 
 Training large language models (LLMs) relies on the ability to train on large amounts of high-quality data. It is predicted that we will run out of high-quality internet data by 2026 [32, 58] , necessitating training on model-generated data, or what is commonly referred to as synthetic data. Recent trends illustrate that scaling up synthetic data can lead to improvements [8, 29] on hard reasoning problems, while other results illustrate that training on synthetic data can steer the performance of the model into a downward spiral [3, 17, 51] -amplying biases, misinformation, and undesired stylistic properties. Thus while in principle, synthetic data could potentially address data scarcity, it must be designed in an appropriate manner to be effective. However, this has been hard due to a lack of an understanding of how synthetic data contributes to LLM behavior.To provide clarity on how synthetic data contributes to performance, we aim to understand its impact on LLM capabilities via a study on math reasoning, a prevalent scenario where synthetic data is used. Typically, in this setting, synthetic data corresponds to correct or positive model-generated responses for a novel set of initial problems synthesized by prompting capable models [29, 31] . The resulting model is then evaluated on a held-out set of problems drawn from a test set. Perhaps as expected, we find that performance improves when finetuning models on positive synthetic responses, though the scaling rates for performance improvement are often substantially slower than those observed during pretraining. Concretely, we find that under the scaling law of Zhang et al. [71] , the error rate scales as ≈D -0.05 to D -0.15 in the size D of synthetic dataset. Second, we observe that not all types of positive synthetic data are equally effective: often positive responses self-generated by the learner itself are as effective as 2× synthetic data from bigger models in improving performance. This is because responses from a similar model are "easier-to-fit" than those from a more capable model, resulting in reduced memorization [26, 56] during finetuning. We also observe that if the positive response contains incorrect/irrelevant intermediate steps, training on such data often incentivizes the model to overfit on spurious correlations, leading to a flat or even inverse scaling with more data.Sample answers for same questions as in synthetic data and filter based on synthetic answersReasoning QnA pairs sampled from capable model, e.g., GPT Perhaps surprisingly, we find that the aforementioned pathologies of training on positive data only can be addressed if we also utilize synthetic negative responses: responses generated by the model that do not result in obtaining a correct final answer. One way to utilize negative responses is via methods such as direct preference optimization (DPO) [41] . While performance of standard DPO [41] largely flatlines as the number of synthetic problems are scaled up (Figure 5 ), we are able to attain consistent improvements if the negative data is generated appropriately. A solution trace for a math problem typically comprises of multiple reasoning steps corresponding to intermediate results. Our insight is that instead of contrasting arbitrary correct and incorrect responses, we should contrast those positive and negative responses that depict good and bad choices for the more "critical" intermediate steps: steps that the model must carefully produce so as to succeed at the problem. In other words, critical steps are those which the model is unable to recover from, and hence, must be emphasized. With this scheme, we are able to attain consistent gains over only positive data, attaining performance similar to scaling up positive synthetic data by 8×. We show that training on this sort of negative data evades spurious steps amplified by training on positive data alone.To theoretically understand our findings, we build a conceptual model of how training on this data benefits performance. Formally, we show that this construction of negative data, which emphasizes "critical" tokens (Figure 6 ) enables us to perform credit assignment, and is equivalent to training the model with per-step advantage-weighted reinforcement learning (RL) [40] on a mixture of positive and negative synthetic data. Specifically, these advantage values are computed under an optimal value function induced by sampling multiple responses under the SFT policy obtained by training on only the positive data. This reduction of using negative data to advantage-weighted RL enables us to conceptually compare it to training on positive data, which corresponds to imitation learning (i.e., behavioral cloning) on positive data. First, we are able to argue for the generalization gains of advantage-weighted RL through the lens of distribution robust objectives. Second, building on theoretical results in RL [27] , we are also able to show that when advantages can be estimated reliably, advantage-weighted RL will be significantly more sample-efficient compared to imitation. Overall, this model explains the utility of negative data over only positive data.Our contribution is a study of the role of synthetic data in improving math reasoning capabilities of LLMs. We derive scaling laws for positive and negative data on common reasoning benchmarks and observe that: (a) training on positive synthetic data from capable models results in scaling rates that are significantly slower than standard empirical risk minimization; (b) training on model-generated positive synthetic data can improve sample efficiency by 2× but also amplifies spurious correlations; (c) appropriate ways of constructing learner-specific negative data with emphasis on critical steps, results in a performance boost equivalent to scaling up positive data 8×; (d) training with negative data provides a mechanism to unlearn spurious correlations; and (e) we present a conceptual model inspired from RL to explain our observations on synthetic data and the generalization benefits we see. 
related work: 
 A standard procedure to finetune a pretrained LLM is teacher-forcing on expert data, i.e., maximizing the likelihood of the next token given all previous tokens [7, 61] . In Appendix G we discuss some failure modes of this procedure for math reasoning that positive or negative synthetic data can address.Positive synthetic data. Learning theory dictates that the SFT policy trained on more SFT data (e.g., 1.5M for DeepSeek-Math [5] ) would have improved math reasoning capbabilities. Thus, a common goal for generating synthetic data as close as possible to the SFT data [29, 31, 32] . That said, generating high quality math data can be challenging, since verification can often be hard. When synthetic data is verified by larger models [50, 59] , recent works [33, 66] observe scaling similar to finetuning LLMs on expert data [69, 71] , while another work [14] notes the compositional gains from SFT data for code generation. Common sources of "good" synthetic data include responses from stronger teachers [29, 30] , or data generated by the SFT policy itself, in the framework of reinforced self-training (ReST) and STaR [8, 52, 69, 70] . In our work, we study and compare the performance scaling with positive synthetic data from bigger models like GPT-4 and Gemini 1.5 Pro with self-generated positive data. We connect our findings to evidence showing "ease of learning" generalizable features on self-generated completions [26] which often prevents undesirable memorization [56] . Finally, our work also sheds light on several concerns about training on synthetic positive data amplifying biases [48, 63] , and leading to model collapse [13, 17] , especially due to overfitting on"spurious" intermediate steps. We conceptually explain this phenomenon and also discuss how negative model-generated responses can help identify and unlearn those spurious steps.Benefits and nuances of negative synthetic data. While most works on synthetic data [29, 32, 66, 69] train only on correct answers, our work also studies complementary gains from incorrect completions generated by the SFT policy [23, 38, 39, 68] . To leverage sub-optimal negative data, we adopt the framework of offline preference optimization [16, 41, 73] , where a preference pair is constructed using correct and incorrect responses for the same problem [38] . Despite numerous studies on preference data composition [8-10, 37, 54, 55, 60] , its unclear how to pose a reasoning problem as a preference optimization problem. Randomly pairing correct and incorrect completions in a preference pair can lead to poor performance [21, 38, 39, 64] due to objective mismatch [55, 72] and requires auxilliary losses to perform well. Another option is to use negative data for training verifiers [22, 65] but this line of work still only trains the policy using positive data. We introduce a conceptual model of negative data, where we understand how certain choices of negative data can assign per-step credits, which we use to establish the equivalence of preference optimization to advantage weighted RL. Self-explore method in Hwang et al. [23] can be viewed as an special instance of our general framework. Other works [34, 59] exploit per-step credit assignment through tree-based sampling. They identify the reasoning subsequence that led to the most incorrect answers under the SFT policy for training a reward model. While this is related, our conceptual model and analysis also understands why assigning per-step credits can generalize better by unlearning spurious correlations, e.g., when the credits are given by the Q-function of the "best-of-K" SFT policy.Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: Appendix A.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
problem setup and synthetic data generation pipeline: 
 Building on the recipe of Li et al. [29] , Liu et al. [31] , we use GSM8K [11] and MATH [19] to collect synthetic data consisting of both novel problems designed by capable models such as GPT4 [1] and Gemini 1.5 Pro [44] , and responses to these problems, obtained from the same models. Synthetic data pipeline. First, given a dataset D real = {(x r i , y r i )} of problems x r i ∼ p real (x) and solution traces y r i ∼ p real (y | x i ), we prompt one of the highly-capable models with a uniformly random sample (x r i , y r i ) ∈ D real and ask the model to generate a new problem x i such that it is similar to the real problem x r i , in a way that a feasible solution exists. Second, we ask the model to provide a solution trace answer y i with step-by-step reasoning (exact prompts for x i , y i are borrowed from Li et al. [29] , shown in Appendix H). We assume that the answers generated via this process are accurate, and perform lightweight filtering step to remove duplicates, badly-formatted answer traces, and model failures. Based on the above, for any synthetic problem and solution pair (x, y), we can define a binary reward function r(y, ŷ) ↦ {0, 1}, which verifies if a new solution trace ŷ is correct or not. This is implemented with a set of answer extraction and string matching tools borrowed from [29, 66] . We say that a new trace ŷ is a positive trace if it produces the correct final answer i.e., r(ŷ, y) = 1, and negative if it produces an incorrect final answer, i.e., r(ŷ, y) = 0. By definition, r(y, y) = 1, and the original trace y is always positive.Positive and negative datasets. The above process induces a joint distribution p syn (x, y), iid samples from which yields positive synthetic dataset D syn . We note that the sampling process for D syn is designed to ensure that the induced marginal distribution over synthetic problems p syn (x) is close to p real (x). We will use D + π to denote the positive dataset of (x, +ŷ) where +ŷ is a positive solution trace generated from some policy π(⋅ | x). For a positive +ŷ and negative -ŷ trace, sampled from the same policy π(⋅ | x), we denote a dataset over problems and solution pairs: (x, +ŷ, -ŷ) as D ± π .Reasoning steps. The trace y i consists of several intermediate steps, y i = [y i,1 , . . . , y i,L ]. We assume each trace has at most L steps, and use y 1∶t to denote the subsequence of first t steps. Since mathematical reasoning problems require step-by-step computation, simply arriving at an incorrect final answer does not mean that all steps in a negative ŷ are incorrect. Similarly, a positive ŷ may also have incorrect reasoning steps. In fact, even the original answers generated by more capable models in D syn may also contain incorrect reasoning steps, and training on such traces may actually lead to unintended consequences (Section 5).Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
learning from synthetic data: 
 In this section, we discuss various algorithms for learning from the synthetic dataset D syn discussed in the previous section, as well as positive and negative solution traces generated using a model.Given positive synthetic D syn , perhaps the most straightforward approach (and the most prevalent) is to learn π sft on this data via supervised next-token prediction: π sft (⋅|x) ∶= arg max π E x,y∼D syn [log π(y|x)]. Another option is to train via supervised next-token prediction on problems in D syn , but when using a positive solution trace ŷ sampled from π sft (⋅|x), instead of positive synthetic responses from the capable models in D syn . Akin to rejection finetuning (RFT [69] or STaR [70] ), sampling from π sft (⋅ | x) once is not guaranteed to give a positive response, and we instead sample M times for each x and construct the dataset D + π sft of SFT policy generated positive responses. Then, we apply the next-token prediction loss on D + π sft . Preference optimization. Beyond positive data, we can also learn from negative synthetic data generated from the SFT policy, especially when contrasted with positive responses. However, learning from negative data presents multiple open design questions pertaining to the construction of negative traces, and the choice of the loss function, and simple supervised fine-tuning will not be a good choice since it will incentivize the model to produce more errors. Therefore, we use a contrastive training approach, direct preference optimization (DPO [41] ) for incorporating negative data from π sft . In a nutshell, DPO trains a policy using the following preference optimization objective:EQUATIONWe consider two objectives that construct negative data and subsequently optimize Equation 1. The first variant is standard DPO [41] , which samples negative data -ŷ from the π sft (with rejection sampling) and adds (x, y, -ŷ) to D ± π sft . The second variant is per-step DPO [23] , which first samples a complete solution trace ŷ1∶L from π sft and then determines the "first pit" ŷc . The first pit ŷc is the step where any completion following the step: ŷc+1∶L ∼ π sft (⋅ | x, ŷ1∶c ) leads to incorrect answers in expectation under π sft . The triplet (x, y, ŷ1∶c ) is added to the preference dataset D ± π sft . 
positive data improves coverage, but amplifies spurious correlations: 
 We first analyze the influence of scaling up positive synthetic data on GSM8K and MATH. In this experiment, we fine-tune DeepSeek-Math-7B [5] and LLama2-7B [57] models (details in Appendix J) on varying sizes of D syn , constructed out of a 5:1 mixture of GPT-4-turbo [1] and Gemini-1.5 Pro [44] . We obtain a series of SFT policies on this data scaling ladder. We then train a series of models by running one iteration of RFT on data obtained from the SFT policies at each step.Scaling results with positive synthetic data GPT-4 and Gemini 1.5 Pro. Since we assume that the more capable models generate correct solutions for new problems, by scaling D syn we are increasing coverage under p real , i.e., adding new x, y with non-zero probability under p real . In Figures 2(a, b ), we plot the test error rate of the SFT policy as D syn is scaled. As expected, we observe that the test error rate on both GSM8K and MATH improves with more positive data. Further, by simply fitting the parametric scaling law from [71] , for D ∶= |D syn |, we find that the scaling trends decay as ≈D -0.15 on GSM8K and ≈D -0.05 on the harder MATH dataset, with similar trends for the corresponding pass@5 error rates. Since these scaling trends are much more underwhelming than those for pre-training [20] , this perhaps implies that samples in D syn are indeed improving coverage over samples in p real (x, y), but maybe not as efficiently as sampling iid samples directly from it.Scaling results with positive synthetic data from 7B SFT policy. Previously, we scaled problems in D syn by querying GPT-4 and Gemini-1. we generate verified positive solution traces ŷ ∼ π sft s.t. r(ŷ, y) = 1. Following Yuan et al. [67] , to ensure we sample enough correct responses, we sample 100 times from π sft and generate RFT datasets D + π sft , where each problem has atmost 4 correct and diverse solutions. Next, we finetune the pretrained DeepSeek-Math-7B model on these new series of RFT datasets and plot the performance on GSM8K and MATH (Figure 2(a, b )). First, we observe that for any size of D syn , the performance of the RFT model is better than the corresponding SFT model, and the difference remains consistent as we scale D syn . Surprisingly, this indicates that training on positive answer traces from the 7B π sft (y | x) can lead to better performing policies than capable models.What is the value of positives from π sft (y | x)? If sampling from π sft also improves coverage and performance, then should we scale problems and solutions in D syn , or just solutions in D + π sft ? To answer this, we need to assign a value to the RFT dataset D + π sft in terms of |D syn |. We do this by training SFT policies on D syn of sizes 8k and 16k, and then generating RFT datasets from the corresponding SFT policies where we only add more correct solution traces (for the same problems) and scale RFT data from 10k to 128k (unlike RFT data in Figure 2(a, b ) where both questions and answers scale). In Figure 2 (c) we plot the error rate of DeepSeek-Math-7B finetuned on the different sizes of D + π sft . Comparing the lowest values of the curves in Figure 2 (c) with D syn scaling in Figure 2(a, b ), we note that performance from D + π sft is 2× the size of D syn used to train π sft . We also note that performance can plateau (or worsen in the case of GSM8K) as we scale up D + π sft by a lot. This is because r(⋅, y) is unable to verify the correctness of each step in the positive solution traces in D + π sft . Later, we see how incorrect steps induce spurious correlations that get amplified as we scale positive data, explaining this drop. See Appendix C for more discussion. Why is self-generated positive data more sample-efficient? From our result above, we find that solutions sampled from π sft (trained on D syn ) yield better models, as good as those trained on 2 × |D syn |. This finding is surprising since one might expect more capable GPT-4/Gemini models to present better solutions, training on which should lead to good performance, akin to distillation [50] , but this is not the case. Our results are consistent with the study of memorization in LLMs [18, 26, 56] , which shows that pretrained (base) LLMs tend to memorize "hardto-fit" and "out-of-pretraining-distribution" responses during finetuning, resulting in imperfect generalization. In contrast, correct response traces produced by π sft on problems from D syn are not as hard-to-fit or as out-of-distribution, since they are obtained from a model that is "close" to the base LLM. We confirm this hypothesis with a histogram of negative log-likelihood values of the SFT and RFT data under the base LLM (Figure 3 ). Hence, we expect STaR/RFT to alleviate the memorization problem on a large chunk of examples. This finding also corroborates Yuan et al. [69] 's result that lower the perplexity of SFT data under the base model, the smaller the gap between SFT and RFT performance. Note that one may also attribute better performance of RFT to improved coverage from multiple answers in D + π sft for each question in D syn . But, we find that even when RFT data is restricted to one solution per question, LLM trained on it outperforms SFT consistently by > 1%. Since verification is cheap, we can sample more solutions and also benefit from coverage. SFT/RFT policy suffers from spurious correlations in positive synthetic data. While RFT data maybe "easier-to-fit", in Figure 2 (c) we also note that continuing to scale RFT data leads to test error saturation, or even worse test error. This is unlike scaling of problems and solutions in SFT data (in Figure 2(a, b )). This failure can be attributed to the presence of incorrect/irrelevant steps that are not detected by our verifier, since it only verifies the final answer (see Appendix J, K for examples). For a problem x, when the LLM is trained with supervised next-token prediction on some positive sub-optimal y in the RFT data, with incorrect step y k , it is likely to overfit on spurious correlations between the sub-optimal subsequence y 1∶k , and the following valid step y k+1 , when trying to maximize π(y k+1 |y 1∶k , x). To verify this hypothesis, we amplify the presence of these spurious steps. Specifically, for each question in D syn we sample "spurious steps" from π sft trained on it, i.e., steps which lead to the incorrect answer with high probability under π sft (we sample multiple completions conditioned on the same spurious step to check how likely it leads to the correct final answer). Then, we interleave the solution traces in the RFT data with these spurious steps. Note, that all traces in the RFT data are still positive since, they all lead to the correct answer eventually. We find that the LLM trained on this sub-optimal spurious RFT data performs worse than the π sft policy itself.Takeaways for scaling positive synthetic data• While positive data from GPT-4/Gemini-1.5 improves coverage over new problems and solutions, positive data from SFT policy trained on it is 2× more sample efficient. • Scaling positive data (∼ π sft ) that contains spurious steps, leads to worse test errors. 
negative synthetic data enables per-step credit assignment: 
 The spurious correlations from Section 5 correspond to intermediate irrelevant or incorrect steps that are able to still steer the model towards the correct response on some training problems, but derail it otherwise. In this section, we present a conceptual model for constructing negatives that enables us to perform per-step credit assignment, and show that this approach can help us address these failure modes of positive data. We show that per-step DPO from Section 3 is a variant of this more general approach. We will then analyze scaling laws with negative data and empirically demonstrate that carefully constructed negative data can address issues with memorization. Finally, we theoretically prove that negative data improves sample-efficiency of D syn .While naïvely contrasing an entire positive response +y against an entire negative response -y will increase the likelihood of each step that appears in +y (even when incorrect or irrelevant) and reduce likelihood on each step appearing in -y (even when accurate and relevant), it does not account for the importance of each step. Formally, given a negative solution trace -y, we would want to identify the first critical step where the model introduces a flaw -y, and emphasize alternate correct completions from this step that the model could have still produced. Likewise, given a positive solution trace, +y, we would like to identify if a given step +y i does not make progress towards the solution by identifying if there exist alternatives from its predecessor step, +y 1∶i-1 , which now presents a key decision-making point. What are these critical steps and how can we identify them procedurally? Value functions. We can formalize this notion of a critical step under the notion of value functions from reinforcement learning (RL). Recall that both +y and -y are sampled from π sft . For problem x, with correct solution y, a response ŷ with a sequence of steps ŷ1∶i-1 , and a candidate step ŷi , we define the value function for step y i , and previous steps under some policy π as:Q π (x, ŷ1∶i-1 state , ŷi action ) = E y new i+1∶L ∼π(⋅|x,ŷ 1∶i ) [r ([ŷ 1∶i , y new i+1∶L ], y) ]expected future reward under new actions sampled by policy πIntuitively, for any partial solution upto i steps, this Q-function evaluates the probability of succeeding at solving the problem given the remaining budget of Li more steps, in expectation over all possible futures sampled from some policy π. Our conceptual model treats the policy π as an algorithmic design choice that can differ for algorithms using negative data. As we see later, choosing π as the Best-of-K distribution around π sft (denoted as BoK(π sft )) enables a particularly interesting tradeoff between Q-value estimation and policy improvement. Another common choice is π sft itself. Now, per-step DPO (c) Figure 5 : Negative data scaling laws: We evaluate algorithms that consume negative data as we scale D syn , and compare them with only positive training (SFT) on D syn . On GSM8K (a) and MATH (b), we observe an 8× gain from per-step DPO (Section 4) which aligns with our model of negative data that enables per-step credit assignment. In (c) we compare different negative data construction algorithms, and particularly note that naïvely pairing positives and negatives [41] leads to worse performance as we scale D syn .for any given step ŷi , we can define its advantage as the relative change in Q π when adding step ŷi in comparison with other possible candidates for step i as follows:A π (x, ŷ1∶i-1 ; ŷi ) = Q π (x, ŷ1∶i-1 , ŷi ) -Q π (x, ŷ1∶i-2 , ŷi-1 ).(3) Equation 3 is identical to the definition of advantage of an action (i.e., ŷi ) at a state (x, ŷ1∶i-1 ) from RL [53] , in that it is the gap between the Q-value of a state-action pair and the value function of the state (which itself is equal to the Q-value of the previous step due to deterministic dynamics).C1: Let cost of 1 apple be x and 1 pear be y.C2: 4x+3y=25 (Eq 1) and 7x+6y=49 (Eq 2).C3: To remove y, multiple Eq1 by 2 and subtract Eq 2 from it. Critical steps, per-step DPO, and advantage-weighted RL. We can use advantages (Equation 3) to characterize critical steps. Steps that attain a higher advantage value than others are critical since they need to be generated more precisely to solve the problem. In contrast, steps that with very low advantage values are likely worse and must be unlearned.Our definition of the advantage function implies that one can calculate advantages for each step in a response via additional Monte Carlo rollouts starting from prefixes defined by partial solutions. One could then use these advantage estimates (Equation 3) for training the model, for example, by running advantage-weighted reinforcement learning [40] . An alternate option would be to skip the computation of advantage estimates but instead rely on implicit approaches that optimize the advantage-weighted objective without computing their values. Theorem 6.1 shows that DPO performed over a precise pair distribution contrasting positive and negative traces obtained via additional rollouts from π, on prefixes of a response sampled from π sft is equivalent to advantage-weighted RL. A proof of Theorem 6.1 is in Appendix E. Note that unlike the standard reduction of DPO to the RL objective under some reward function [41, 42] , Theorem 6.1 is stronger in that it identifies the value function induced by per-step DPO. Theorem 6.1 (Equivalence of advantage-weighted RL and DPO with per-step pairs). The optimal policy from Equation 1 with D ± π sft given by (x, [y 1∶i , +y i+1 ], [y 1∶i , -y i+1 ]) where the positive and negative traces share prefix y 1∶i ∼ π sft , and -y i+1 ∼ π sft (⋅|x, y 1∶i ), +y i+1 ∼ σ(A π (x, y 1∶i ; ⋅) -A π (x, y 1∶i ; -y i+1 )), is identical to the optima of the advantage-weighted RL objective:EQUATIONPractical instantation of DPO with per-step pairs. In most of our experiments, we instantiate a practical version of the above framework, following the scheme in Hwang et al. [23] . This is a special case (Part 1) of the complete algorithm shown in Algorithm 1 (see Appendix B). Unless otherwise mentioned, we use "per-step DPO" to refer to this version (Part 1 only) in practice. We will also experiment with the complete version (parts 1 and 2) later in Section 6.3.3. Instead of computing advantage estimates for each step, and then sampling preference pairs, as described in Theorem 6.1, we approximate this by only Q-value estimates on 8 negative responses for each question in the synthetic dataset, with π chosen to be the best-of-K policy, BoK(π sft ) where K = 5. There are two benefits associated with this choice of π, especially a higher value of K: (i) estimating the advantage in Equation 3with Monte Carlo rollouts exhibits lower variance when K is large, since a larger budget K would lead most steps to have higher Q-values and the variance of Bernoulli reduces as Q-value → 1; and (ii) Q BoK(π sft ) is a non-decreasing function in K for any state-action, which implies that the solution of advantage-weighted RL objective, in principle, can now improve over a better policy BoK(π sft ), compared to π sft . Next, we discuss scaling results for negative data, and then in Section 6.3 show how per-step credit assignment improves generalization and suppresses irrelevant and incorrect steps appearing in a response, extracting more gains from the same synthetic data.Observe in Figure 5 (a,b), that for both DeepSeek-Math-7B and LLama2-7B models, per-step DPO improves performance beyond the SFT policy and the performance continues to scale favorably as data size increases. In fact, for any given size of D syn , per-step DPO also substantially improves over RFT (Figure 2 ) on both datasets, and overall, while RFT improved effective data size of D syn by 2×, additionally training on negative data extends the performance improvement to 8× the size of D syn . Additionally, since per-step DPO estimates advantage of each step under the Best-of-5 policy, one might expect a saturation in the pass@5 performance of the per-step DPO solution. On the contrary, we find that pass@5 performance also improves consistently. In Appendix D we present results for a filtered version of RFT. Here, steps with high advantages from positive/negative data are cloned. This resolves the scaling issue seen when naively scaling positive data in Figure 2(c ).Choice of negative data matters. In Figure 5 (c) we plot negative data scaling laws where the choice of negative data (thereby pairs for DPO in Equation 1) differs. Observe that standard pairing of positive and negative responses in D ± π sft for DPO [41] does not improve over the SFT policy. As such, we tuned β in Equation 1 for DPO but could not fully avoid performance degradation. Our conceptual model explains this result: contrasting arbitrary positives and negatives would result in an incorrect induced advantage function, training with DPO will exacerbate spurious correlations that maximize this induced advantage function [39, 46, 64] . In fact, Pal et al. [38] also find similar concerns with random pairing and instead pair positives and negatives with highest edit distance, which leads to some improvement , but still performs poorer than per-step DPO that accounts for credit.Takeaways for scaling negative synthetic data • Negative data can identify high-advantage (critical) steps in model-generated responses.• We can construct negative data distribution that equates DPO to advantage-weighted RL.Negative data used in this way improves the sample efficiency of synthetic data by 8×.Our conceptual model illustrates that per-step DPO can perform credit assignment, and identify critical steps over irrelevant ones via advantage estimates. We saw that this improves test performance and scaling. Now, we attempt to understand why per-step credit assignment should improve generalization by understanding the generalization properties of advantage-weighted RL. We present two empirical studies below, and a formal theoretical guarantee combining these insights is shown in Appendix F. Our key insight is that spurious correlations emerge in monolithic SFT or RFT due to the well-known issue of causal confusion [12] in imitation learning: by memorizing incorrect or irrelevant steps and associating them with the correctness of the final answer, the model fails to generalize on novel problems, as we saw in Figure 4 . We now explain how online model-specific interventions and advantage estimation would address this issue. Consider π = π sft . As we show later, in under-trained models memorized steps are imperfectly cloned under π sft , implying that while teacher-forcing loss is low for some spurious, memorized step y s , sampling paths from π sft , conditioned on y 1∶s is likely to generate incorrect responses. This means y s attains a low advantage. On the other hand, for a correct step, whp estimated advantage is higher. Thus, training the model with advantage weighted RL would de-emphasize spurious steps and emphasize critical steps. Running per-step DPO on data generated by the RFT model that has overfit on spurious correlations improves accuracy by >6% (Figure 4 ). We visualize advantages in Appendix K. In Figure 7 , we plot the average Q-value of a step for different negative data schemes, and note that only per-step DPO improves over SFT at each step, as expected based on the connection to advantage-weighted RL (Theorem 6.1). Standard DPO fails to improve performance since it has poor success rate at earlier (critical) steps.In the previous section, we discussed how advantage-weighted RL preferentially weighs the nexttoken prediction loss at each step. Now, we attempt to conceptually understand why this could improve generalization. For this, we present an intuitive explanation by drawing a connection between advantage-weighted RL and a distributionally robust optimization (DRO) algorithm, named Group DRO, commonly used to improve worst-group robustness in supervised learning [43] .Intuitive explanation. During inference, the SFT policy can fail even on training problems, especially in scenarios where the SFT policy has failed to perfectly clone the next step at each intermediate step in the SFT data. As previously discussed, these steps also present with low advantage values. One way to reduce the chance of compounding inference time errors [45] is to preferentially minimize the negative log-likelihood loss more for the critical step, i.e., those steps from where the model is more likely to arrive at a wrong answer. If we iteratively update the policy with gradient steps computed over a re-weighted next-step prediction objective where each step is weighted by its advantage estimate, then the resulting algorithm intuitively exhibits this characteristic similarly to distributionally robust optimizers (DRO) [28] . Similar to how DRO solutions guarantee that all subpopulations -both majority and minority subpopulations -in the training data achieve low loss values, the solution for the advantage-weighted RL objective guarantees that the negative log-likelihood of the critical steps with high advantage estimates under π (which of per-step DPO is BoK(π sft )) is also low, to a similar extent as the other more prevalent non-critical steps.In other words, our insight is that weighting steps using advantages in Equation 4 upweights the likelihood of the underrepresented critical states while down-weighting it for the spurious ones. The guarantees on the training data (D syn ) also translate to the population level objective when the weights for on-policy samples (advantage estimates) are accurate [49] and the policy is sufficiently regularized [47] . Since correct behavior at critical steps determine the correctness of the overall solution, an elevated degree of correctness at executing critical steps at the population level implies a higher test accuracy on the reasoning task.The practical efficacy of algorithms that use negative data for credit assignment requires the advantage estimation error to be low with fewer rollouts from π. For discussion, consider π = π sft . When the initial advantage of a spurious step is incorrectly over-estimated, negative data algorithms up-weight the likelihood further. This only leads to further memorization. Hence, most Monte-Carlo rollouts from π sft would rely upon the memorized feature. Since the model generates the correct answer from the memorized feature, it would estimate higher A π sft , and this downward spiral of training with increasing weights on the spurious step leads to test-time model collapse. On the other hand, when π = BoK(π sft ) for a higher value of K, the Monte-Carlo advantage estimator has a lower variance (and error). This discussion also justifies the choice of K=5, an intermediate value, in per-step DPO.With the above insights, we now study the influence of π sft on the generalization effects of per-step DPO. For our analysis, we consider a didactic star graph problem (Appendix I) from Bachmann and Nagarajan [4] , where given a graph in the shape of a star and a query (center/end node), the model is asked to output the full path between the start/end nodes. This task highlights the failure of SFT at planning problems (akin to math reasoning). They show that π sft minimizes SFT loss by memorizing the "hard-to-predict" node adjacent to the center, and copying the rest from the input graph. It is clear that the failure stems from not being able to identify the critical adjacent token. We will show how credit assignment with negative data accurately upweights the critical token and unlearns the memorized token. To vary the choice of π sft , we choose several intermediate checkpoints obtained during supervised finetuning for synthetic negative data generation. We consider three initializations: early-stopping based on a held-out validation set, where the validation loss is the lowest, and (3) an over-trained SFT checkpoint, with a low training but high validation loss.(1) & ( 2): Training on negative data from an under-trained or early-stopped π sft improves both training loss and test performance. As shown in Figure 8(a, b ), we find that when training with negative data from iteration 60 (under-trained π sft ) and iteration 200 (early-stopped π sft ), utilizing per-step DPO reduces the training loss very aggresively. These benefits translate to test losses and performance as well (Figure 8 (b), orange and green). In contrast, supervised finetuning exhibits a nearly-flat test loss landscape, although the train loss reduces slowly. Upon a closer inspection, we find that training on positive data via SFT only tends to memorize the critical token in the training data using non-generalizable features, and hence, the resulting model does not generalize to novel problems. More training with SFT is unable to "unlearn" this spurious correlation and does not reduce the loss function. On the other hand, per-step DPO with negative data is able to unlearn this spurious feature and drives improvement, as evident by the drastic improvement on train and test.(3) Training on negative data from an over-trained SFT initialization leads to model collapse.When training with negative data on an over-trained π sft (iteration 580) in Figure 8 (c), we observe that both SFT and per-step DPO exhibit identical test errors since training with more negative data simply exacerbates the model's dependence on memorizing the critical token, which manifests in the form of lower test losses. This is also an example where Monte-Carlo samples from the over-trained checkpoint estimates a high advantage since Q-value is already high at iteration 500 (in (a)). This means that when the SFT policy has sufficiently memorized the training data using a spurious feature, training further is unable to unlearn this dependence. Hence, we find that in this regime, negative data leads to no improvement, capping performance at what was attained by fine-tuning on positive data.Advantage-weighted RL unlearns spurious steps and improves generalization when: (i) advantage estimation error is low; and (ii) the model is under-trained enough that imperfectly cloned spurious steps have low advantage, which can then be estimated with negative data.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: Experimental details are included in the main paper and in Appendix H and Appendix J Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
discussion and conclusion: 
 Our work studies the role of synthetic data for improving math reasoning capabilities of LLMs. We find that while the typical approach of collecting new questions and corresponding positive (correct) solutions from capable models like GPT-4/Gemini-1.5 presents underwhelming data scaling. The sample efficiency of the same data can be improved up to 2× by sampling more positive traces from the 7B sized models SFT-ed on the original data. However, training on positive self-generated synthetic data alone often amplifies the model's dependence on spurious steps, that erroneously appear to lead to a good solution but do not generalize to novel problems and hurt test performance. That said, surprisingly, we show that negative (incorrect) traces sampled from the same SFT model can be used to address the failure modes of training on only positive data. In particular, negative data can be used to estimate advantage values for every step, and using these advantage estimates via RL enables us to address this problem. We show how the advantages can be used implicitly by preference optimization objectives. We show how training on an instance of this objective leads to 8× improvements in sample efficiency of the synthetic data used.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: For experiments that were bottlenecked by computational resources, we were unable to run multiple experiments. However, since we perform experiments on wellestablished benchmarks, we could make comparisons with existing work to understand the significance of our performance. And hence, whenever needed we make sure to discuss observed performances and significance with existing work. Moreover, since we run experiments at different scales and dataset sizes, the trends observed implicitly normalize for error bars.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: We have added computational resources needed in the Appendix. Overall, to replicate our experiments, we need approximately 1000 hours of compute on H100 clusters with 8 GPUs. To generate our synthetic data, we need approximately 3000 USD worth of credits with the current pricing of GPT-4 model.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [NA] Justification: We do not do any experiments with human subjects. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: While our work provides some results and conceptual models to understand the role of synthetic data for reasoning, there are still many open questions that need to be answered to fully understand its utility. While synthetic data from LLMs like Gemini and GPT-4 holds great potential, for more complex reasoning problems (more complicated than the datasets evaluated in our work), synthetic data generated from more capable models can contain errors. Generating negative/positive data by referencing synthetic data answers can reinforce unwanted spurious correlations highlighted in our work. This means that novel recipes for generating synthetic problems may be utilized in the future, and our analysis might need to be re-done. That said, we believe that our insights about algorithmic behavior with synthetic data are still quite general and should transfer to these novel settings as well. Ultimately, we would want that training on synthetic data improves transfer and generalization abilities of the model in general reasoning scenarios, and to this end, an evaluation of transfer capabilities is an important avenue that future work should focus on. Compute the Monte Carlo estimate for Q π (x, -ŷ 1∶i-1 ; -ŷ i ) for each step -ŷ i .If -ŷ c is the first step with least 11:Q π (x, -ŷ 1∶i-1 ; -ŷ i ), then D ± π sft ← D ± π sft ∪ {(x, y, -ŷ 1∶c )}.for +ŷ ∶= [+ŷ 1 , . . . , +ŷ L ] ∈ C ′ (x) do 12:Compute the Monte Carlo estimate for Q π (x, +ŷ 1∶i-1 ; +ŷ i ) for each step +ŷ i .If +ŷ c is the first step with least Q π (x, +ŷ 1∶i-1 ; +ŷ i ), then D ± π sft ← D ± π sft ∪ {(x, y, +ŷ 1∶c )}.Recall from Section 5 we observed a 2× boost in sample efficiency (over π sft ) of the question/answer pairs in the synthetic data when we cloned positive solutions sampled from π sft . Note that one may also attribute better performance of RFT to improved coverage from multiple responses in D + π sft for each question in D syn . We find that even when RFT data is restricted to one solution per question, base LLMs finetuned on it outperform SFT consistently by > 1%. In Figure 9 , we plot the performance of DeepSeek-Math-7B finetuned on SFT data D syn and RFT data D + π sft where D + π sft has the same questions as D syn , and only one positive solution per question, sampled from π sft finetuned on D syn . Thus, both SFT and RFT datasets are of the same size. This means that a significant portion of the 2× sample efficiency gains we observe for RFT in Figure 2(a, b ) can be attributed to RFT data Improving per-step DPO [23] with a closer approximation of advantage-weighted RL (Parts 1 + 2 in Algorithm 1). Now, we discuss an experiment that improves the performance of per-step DPO [23] by running the full version of Algorithm 1. In particular, we add new preference pairs to the dataset of per-step DPO algorithm starting from positive samples. Recall from Section 4 and Algorithm 1, that for a problem x, with correct answer y given by SFT or RFT data, Part 1 of per-step DPO estimates the expected accuracy (Q-value) of each step in a negative rollout -ŷ ∼ π sft (⋅ | x) sampled from the SFT policy. For each step -ŷ c the Q-value is computed conditioned on x and previous steps -ŷ 1∶c-1 . It then adds the triplet (x, y, -ŷ 1∶c ) to the DPO dataset. We improve the coverage and accuracy of advantage estimates via Part 2, i.e., repeating this process for steps appearing on a positive trace +ŷ ∼ π sft (⋅ | x) as well. Specifically, we add (x, y, +ŷ 1∶c ) to the DPO dataset, where the step +ŷ c is the first step in the positive trace to have a low Q-value (as dicated by a relative threshold on the Q-value), which indicates that +ŷ c is likely a spurious step that the SFT model generated. For individual steps that are more likely to occur in either positive or negative traces we improve coverage of alternate possible steps, and for steps that occur in both positive and negative traces, we lower the variance (and error) of the advantage estimate. In Figure 10 , we compare the performance of per-step DPO runs with the datasets constructed from only negative vs. both positive and negative traces, and find that the latter has a lower test error for all sizes of D syn .Advantage filtered per-step RFT. We ran an experiment with advantage filtering on all the steps present in both positive and negative data from the SFT policy and cloned the filtered data. For this, we cloned responses with high advantage steps from positive and negative responses sampled from the SFT policy. We filter all steps where the minimum advantage across all steps is in the bottom 50% percentile. This "per-step RFT" outperforms standard RFT (Figure 11 ), indicating that training on useful steps from negative data can improve beyond only training on positive data alone. While per-step RFT is worse than per-step DPO, we believe that this only further hints at the point that even using low advantage steps (that per-step RFT filters) for training, can further improve. E Proof of Theorem 6.1We first restate the theorem statement and then provide a proof for this below. Our main goal in this theorem is to show that training with per-step DPO is equivalent to running advantage-weighted RL shown in the theoretical result. Theorem E.1 (Equivalence of advantage-weighted RL and DPO with per-step pairs). The optimal policy from Equation 1 with D ± π sft given by (x, [y 1∶i , +y i+1 ], [y 1∶i , -y i+1 ]) where the positive and negative traces share prefix y 1∶i ∼ π sft , and -y i+1 ∼ π sft (⋅|x, y 1∶i ), +y i+1 ∼ σ(A π (x, y 1∶i ; ⋅) -A π (x, y 1∶i ; -y i+1 )), is identical to the optima of the advantage-weighted RL objective:EQUATIONProof. To prove this statement, we make the following observation: DPO [41] is equivalent to optimizing a KL-divergence penalized expected reward objective in an induced Bradly-Terry model of preferences defined by the reward function. That is, for any reward function r(x, y) over contexts x ∼ µ and responses y, the optimal solution to the following RL objective:EQUATIONis given by the following advantage-weighted optimal policy, π * (⋅|⋅):EQUATIONand one can learn this optimal policy by running DPO on preference tuples (x, y 1 , y 2 ) sampled by the Bradly-Terry model [6] induced by the reward function r:EQUATION)Given this background information, we know that the optimal advantage-weighted RL policy optimizing Equation 5 is given by:EQUATIONCombining Equation 9with the equivalence between Equation 7and the Bradly-Terry model (Equation 8), we obtain that, if preference pairs (x, [y 1∶i , +y i+1 ], [y 1∶i , -y i+1 ]) were sampled from the SFT policy: +y i+1 ∼ π sft (⋅|x, y 0∶i ) and -y i+1 ∼ π sft (⋅|x, y 0∶i ), and labeled according to Equation 8 applied on advantage estimates, then we obtain the desired equivalence result.F Theory: Why Does Negative Data Improve Generalization?We saw in Section 6.3 that collecting negative data from an appropriate SFT policy π sft and an appropriate K, and training on this data improves generalization performance of the resulting model. In this section, building on the equivalence to advantage-weighted RL (Theorem 6.1), we attempt to formalize this observation into a performance guarantee. In particular, we show below that training on negative data implies that we are able to improve over the SFT policy, especially via the detection of critical steps, that attain high advantages, A π (x, y 0∶i-1 , y i ), that are otherwise not prioritized by training on positive data alone. Our theoretical result extends guarantees from the RL literature [27] comparing RL with imitation learning to show that indeed the use of RL (and hence negative data) improves over imitation alone.Notation and setup. Define the policy obtained after advantage-weighted RL training as π neg .Concretely, π neg (y|x) is given as:EQUATIONwhere the normalization factoris given by Z(x, y 0∶j ) for each of the per-step policy distributions. This normalization factor is a critical factor that will drive the core of the theoretical result. We also note that the normalization factor in Equation 10 is derived from empirical advantage estimates and not from the expected estimates for the advantage value. Following Agarwal et al. [2] , Kumar et al. [27] , we operate in a tabular setting with a discrete (but combinatorially-large and variable-length) action space of responses, and our proof follows Theorem 4.4 in Kumar et al. [27] .Theorem F.1 (Utility of negative data over positive data.). Let π neg denote the policy obtained after advantage-weighted RL (Equation 10) under an empirical distribution μ over prompts x. Then the difference between the expected reward (i.e., task success rate), J(⋅), attained by π neg and π sft is lower-bounded as:J(π neg ) -J(π sft ) ≳ β ⋅ E x i ∼μ,y i,0∶L ∼π neg (⋅|x i ) [ L ∑ j=1 log Z(x i , y i,0∶j )] -(overestimation in Âπ (x, y 0∶i-1 , y i )) + c 0 √ |D syn | ,where Z(♣, •) denotes the sum over exponentiated differences of the advantage and log likelihood values under π sft for all possible candidate steps given a problem ♣ and a partial solution•. That is, Z(♣, •) ∶= ∑ ♠∈ step candidates exp ( A π (♣, •; ♠) β + log π sft (♠|♣, •)) ,c 0 is a constant depending upon the Rademacher complexity of the space of policies π neg close to the SFT policy under the KL-divergence, |D syn | denotes the size of synthetic training prompts.Proof. To begin the proof, we recall that we are operating in a discrete action space of steps y i , although this space is exponentially large. Since we operate in discrete action spaces, we invoke Lemma 5 from Agarwal et al. [2] for analyzing softmax policy gradient methods (this Lemma was extended by Lemma B.11 from Kumar et al. [27] for comparing BC vs offline RL). Denote by Ĵ(π), the reward attained by policy π in expectation over the empirical distribution μ:EQUATIONWe utilize the performance difference lemma [25] on the MDP induced by the set of initial problems in the training distribution μ, and the model induced deterministic dynamics distribution:Ĵ(π neg ) -Ĵ(π sft ) = L ∑ j=1 E x∼ μ,y 0∶j-1 ∼π neg (⋅|x) ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ∑ y j π neg (y j |x, y 0∶j-1 ) Âπ (x, y 0∶i-1 , y i ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ = L ∑ j=1 E x∼ μ,y 0∶j-1 ∼π neg (⋅|x) ⎡ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ∑ y j π neg (y j |x, y 0∶j-1 ) log π neg (y j |x, y 0∶j-1 ) ⋅ Ẑ(x, y 0∶j ) π sft (y j |x, y 0∶j-1 ) ⎤ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ = β ⋅ L ∑ j=1 E x∼ μ,y 0∶j-1 ∼π neg (⋅|x) [D KL (π neg (⋅|x, y 0∶j-1 ), π sft (⋅|x, y 0∶j-1 )) + log Ẑ(x, y 0∶j )] ≥ β ⋅ L ∑ j=1 E x∼ μ,y 0∶j-1 ∼π neg (⋅|x) [log Ẑ(x, y 0∶j )] . = β ⋅ E x∼μ,y i,0∶L ∼π neg (⋅|x) [ L ∑ j=1 log Z(x, y 0∶j )] .Now, we can prove the desired result by accounting for the gap in the success rate between the actual distribution over x ∼ µ and the empirical distribution induced by problems in the dataset μ:J(π neg ) -J(π sft ) ≥ J(π neg ) -Ĵ(π neg ) (a) + Ĵ(π neg ) -Ĵ(π sft ) (b) -J(π sft ) -Ĵ(π sft ) (c) ≥ β ⋅ E x∼μ,y i,0∶L ∼π neg (⋅|x) [ L ∑ j=1 log Ẑ(x, y 0∶j )] - c 0 √ |D syn | ≥ β ⋅ E x∼μ,y i,0∶L ∼π neg (⋅|x) [ L ∑ j=1 log Z(x, y 0∶j )] - c 0 √ |D syn | + ∆,where c 0 is a constant that depends on the Rademacher complexity of the function class of policies π neg (coming from a uniform bound that we invokve to bound term (a), since π neg depends on the dataset samples), and this term arises since the empirical distribution over prompts is not the same as the true population. This concentration term decays as the size of the synthetic data (number of problems) are scaled up. The term ∆ denotes the overestimation error between the estimated advantages Âπ (x, y 0∶i-1 , y i ) and the true advantages A π (x, y 0∶i-1 , y i ), in expectation under the distribution of the learned policy. The estimation error ∆ depends on π sft and the value of K used if the rollout policy π corresponds to the BoK(π sft ) policy. This proves the theorem.Interpretation & perspectives. Also note that the improvement in performance between π neg and π sft depends on the advantage estimate: if the advantage estimates are high, then this term is large, meaning that the more the fraction of high-advantage critical states, the higher the improvement.In addition, the bound also says that if the over-estimation ∆ in the advantage estimate is large, the performance improvement is small. This is perhaps expected: consider the scenario when the BoK(π sft ) policy is used to collect data, for a large K. In this scenario, the divergence between the empirical advantage estimate Âπ and the expected estimate A π is likely large. In the worst case, the estimate Âπ can arbitrarily overestimate A π , as it would take on a high value even if there is just one sequence among the K rollouts that successfully solves the problem. For example, a spurious step may be labeled incorrectly as critical in this case and training on negative data may not improve (consistent with running per-step DPO on an over-trained SFT checkpoint in Figure 8 ). On the other hand, if advantages are more accurate, training on negative data should improve performance.Failure modes for supervised finetuning (SFT). First, since SFT induces an open-loop [62] nexttoken prediction loss, prediction errors on even a single token can snowball during inference, leading to poor performance on the prompts appearing in the dataitself [24, 45] . Second, even when an LLM has perfectly cloned the SFT data, it is prone to memorize "hard to learn" tokens [56] , especially in planning and lookahead tasks [35, 36] , which is critical for math reasoning. This leads to poor generalization [4, 15] and hallucination on new novel, test-tim prompts [26] . In this work, we study how synthetic data methods can address these failures via: (i) maximizing likelihood on positive data generated from both the SFT policy and a stronger teacher that enjoys improved coverage over new states, and (ii) preference optimization using the negative data generated from the SFT policy.Prompt used for GSM8K/MATH synthetic data [29] Please act as a professional math teacher. Your goal is to create high quality math problems to help students learn math. You will be given a math question. For GSM8K, we replace the phrase "Your goal is to create high quality math problems to help students learn math." with "Your goal is to create high quality math word problems to help students learn math.", as we found this to produce problems that were closer to GSM-style problems.To generate the synthetic data, we used OpenAI credits worth approximately 3000 US dollars.The star graph problem we study is borrowed from Bachmann and Nagarajan [4] , where given a graph in the shape of a star and a query (center/end node pair), the model is asked to output the full path between the start/end nodes.Goal. Bachmann and Nagarajan [4] show that π sft minimizes SFT loss by memorizing the "hard-topredict" node adjacent to the center, and copying the rest of the path from the input graph. This task is highlights the failure of SFT at planning problems (akin to math reasoning). Thus, we use this as a case study to understand:• when accurate advantage estimation is possible with few negative samples from the π sft model.• whether there are generalization benefits of advantage-weighted RL when advantage estimates are accurate• when advantage-weighted RL can unlearn the memorized feature that causes π sft to fail.SFT dataset. The data we use for supervised fine-tuning consists of 30000 of random star graphs (see examples below) where each graph has a centre node with out degree 2. Hence, there are two paths that originate from the centre node. Each path from the center to one of the end nodes is of length 4. Each node on the path is denoted with a randomly sampled number from 0 to 20. For example, in the sample "8,3|3,10|14,13|10,1|17,14|8,17/8,13=8,17,14,13". The graph is given by the adjacency list "8,3|3,10|14,13|10,1|17,14|8,17/8,13", the query is denoted by "8,13", and the correct path is given by "8,17,14,13".Test-time inference from the model. At test time, the input to the LLM is only thw graph and the query: "8,3|3,10|14,13|10,1|17,14|8,17/8,13=" and the model is expected to generate the full path from start node 8 to end node 13. When evaluating the test performance of an LLM, we calculate 0/1 accuracy averaged over 1000 test star graphs (that are different from train star graphs). The accuracy on a sample is 1 when the LLM accurately predicts all nodes in the graph.Failure models of the SFT model, π sft . A model with perfect accuracy (0 error) would be the one that has accurately learned the correct feature of backtracking the path from the end node to the start node, and then producing it in reverse. This computation is precisely what makes the adjacent token "hard-to-fit". On the other hand, if the LLM minimizes next-token prediction loss during SFT by instead memorizing the hard-to-fit adjacent token by overfitting on the random input graph instance, at test time the accuracy would be zero. SFT Training details. We finetune a pretrained GPT-2 model with 125 million parameters. We train with a batch size of 128, Adam without any weight decay, and a constant learning rate of 1e -5 .Advantage estimation and per-step DPO training equivalent to advantage-weighted RL. For a sample from π sft , we estimate the advantage of each step by sampling 5 rollouts conditioned on the subsequence uptill the step. We then pair subsequences with shared prefix, y 1∶i differing in the last step +y i+1 vs. -y i+1 , where the former is the one with the highest estimated advantage and the latter is the one with the lowest estimated advantage. Note that this preference pair construction, closely approximates the preference pair distribution in Theorem 6.1, which would imply that the DPO objective being optimized closely approximates advantage weighred RL in Equation 4.Given these pairs for a batch of star graph problems in SFT data, we update the model with a single gradient step on the DPO objective in Equation 1. In the next iteration, advantage is estimated and pairs are constructed on a fresh batch of star graphs. We set β = 0.1 in the DPO objective and use the same batch size (one preference pair per star graph). Starting from an SFT checkpoint we train in the above manner for at least 200 iterations. The SFT model is trained for over 600 iterations.Datasets and pretrained LLMs. We run all our experiments on GSM8K and MATH datasets. Justification: Claims from the introduction and abstract are reflected in the paper.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Justification: Our work is to study reasoning in large language models and it doesn't violate any code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 


Decision: The paper does a thorough exploration of when synthetic data can help for training LLMs on reasoning tasks, looking at GSM8K and MATH datasets. They first report interesting general findings -- e.g. that synthetic data from an LLM helps, but what helps even more is synthetic data from fine-tuned models, and then they present the critical finding of the paper, that negative data if generated and used carefully in step-by-step settings can lead to even further improvements. Here they focus primarily on  per-step DPO, but during rebuttal they also showed that similar findings hold for KTO and RFT. 
I think there are enough interesting observations and methodological contributions that make it an interesting paper, even if it is focussed very specifically on mathematical reasoning tasks. The authors reported a lot of interesting new experiments during the rebuttal period that was favorably received.

Reviews: review: paper_summary: paper_summary: This paper studies the effect of synthetic data on improving the reasoning abilities of LLMs. The authors have compared with multiple approaches including SFT, RFT, DPO, per-step DPO, etc., and characterized the model performance w.r.t. different scales of synthetic data under each training regime. Several practical findings about improving sample efficiency are presented, including leveraging the finetuned model to sample for positive samples, utilizing per-step negative examples to alleviate the spurious correlations that might appear in the synthetic positive data, etc.
strength_weakness: strength_weakness: - It seems that the authors wanted to cram lots of conclusions into a single paper. While I appreciate the incentive, the paper would make a much more academic read if more experimental results are clearly presented in tables. Currently, it seems that there are few quantitative results in the paper. This also led many specific concerns (see below).

- In Lines 242-245, it reads `But, we find that even when RFT data is restricted to one solution per question, LLM trained on it outperforms SFT consistently by > 1%. Since verification is cheap, we can sample more solutions and also benefit from coverage.` Where is the evidence to this claim? In this claim, does the size of D_{syn} equal that of D_{SFT}^{+}? 

- It makes me confused when I compare Lines 224-244 and Lines 245-263. 

    In Lines 224-244, the authors suggest that RFT outperforms SFT in terms of sample efficiency. But in Lines 245-263, the authors suggest that RFT data contain spurious correlations, and when manually raising the percentage of spurious correlations in RFT data, SFT would outperform RFT. Especially, in Lines 248-249, `This is unlike scaling of problems and solutions in SFT data (in Figure 2(a,b)).` Since RFT might even suffer from negative scaling because of spurious correlations, I don't think that RFT could be claimed to be `more sample-efficient`.

- Also about the artificial spurious correlation amplification experiments in Lines 257-263: Does Figure 4 show the experimental results (there's no reference in the paragraph)? Does the `D_{π}^{+} spurious` correspond to the construction of `for each question in D_{syn} we sample “spurious steps” from π_{sft}`? Does this "100% spurious correlation injection" represent the authentic "spurious steps" ratio in RFT data (and what is the authentic "spurious steps" ratio in RFT data?)? Does D_{syn} contain no spurious correlation steps? As the RFT data scaling leads to negative performance, will those RFT data with a less percentage of spurious correlation steps lead to a not-so-negative performance? If this is true, can we just use the advantage defined in Eq.(3) as a stronger filtering rule and apply on RFT data? A more in-depth quantitative study is required here, so that the importance of the use of negative examples in Section 6 is better revealed.

- Is the `per-step DPO` method used in the paper proposed in the cited [23] paper? If it is true, is it also true that no new method is proposed in Section 6? Note that it is fine to focus on analysis instead of proposing new techniques, but the author should make it more clear about this in the paper. It would also be helpful if the authors briefly introduce the per-step DPO method used in the paper in a background/methodology section.

- Are the advantage in Eq.(3) and the per-step DPO method applicable to other types of reasoning tasks in addition to MATH and GSM8K? For example, ARC requires LLM reasoning (LLM often conducts this task by writing codes). Are the methods and the analysis applicable to ARC?

- Lines 343-344: `As such, we needed to tune β in Equation 1 for DPO but could not fully avoid
344 performance degradation.` Where is the evidence to this claim? Experimental results with a sweep of β would be supportive. 


- Similarly, Lines 377-386 also require more experimental evidence. It would be helpful if quantitative observation is added to the claim like `When the initial advantage of a spurious step is incorrectly over-estimated, negative data algorithms up-weight the likelihood further. This only leads to further memorization. `, `leads to test-time model collapse`,  and `On the other hand, when \tilde{π} = BoK(π_{sft}) for a higher value of K, the Monte-Carlo advantage estimator has a lower variance (and error). This discussion also justifies the choice of K=5`.

- The paper lacks a Conclusion section, which I believe is because of the length limit of a submitted paper. But it is still better to add such a section and properly refactor the previous contents.


I encourage the authors to address my concerns, and I would consider raising my score provided that the issues I raised are resolved properly.

Others: Line 322: "instantation" --> "instantiation"
questions: questions: See the Weaknesses part.
limitations: limitations: The authors have addressed the limitations.
paper_summary: paper_summary: This paper investigates the impact of synthetic data on improving the reasoning capabilities of large language models (LLMs). The authors conduct an empirical study followed by a theoretical formalization to understand when and how synthetic data helps or hurts model performance on reasoning tasks.

Key findings include:-
(1) Finetuning on synthetic correct/positive problem-solution pairs offers modest gains, but sampling more correct solutions from the finetuned learner doubles sample efficiency.
(2) Training solely on model-generated positives can amplify spurious correlations, leading to flat or inverse scaling trends as data increases.
(3) Utilizing negative responses (incorrect model-generated responses) alongside positives, with appropriate credit assignment for intermediate steps, yields consistent gains over positive-only data.
(4) The proposed per-step negative data approach is equivalent to advantage-weighted reinforcement learning (RL) and helps unlearn spurious correlations.

The authors demonstrate that their per-step negative data approach improves sample efficiency by 8x compared to standard finetuning on positives. They also provide theoretical and empirical analyses to explain why credit assignment improves model generalization.
strength_weakness: strength_weakness: - While the focus on reasoning tasks is well-justified, it's unclear how well the findings generalize to other types of language tasks or domains.
- The study primarily uses 7B parameter models (DeepSeek-Math-7B and LLama2-7B). It would be valuable to see if the results hold for larger or smaller model sizes.
- The paper doesn't discuss the computational costs of their approach, which could be a significant factor in its practical application, especially for larger models or datasets.
- While the authors compare their method to several baselines, it would be beneficial to see comparisons with more recent techniques in synthetic data generation or model finetuning.
- The study doesn't address potential long-term consequences of training on synthetic data, such as potential drift or accumulation of errors over multiple generations of synthetic data.
questions: questions: None.
limitations: limitations: Yes.
paper_summary: paper_summary: The paper investigates how to effectively leverage synthetic data to improve reasoning capability in the GSM8K and MATH datasets. The authors identify that sampling correct synthetic data from a fine-tuned model is more sample-efficient but comes with the risk of overfitting artifacts in the synthetic data. Instead, they propose a per-step DPO to leverage negative synthetic data to enhance sample efficiency.
strength_weakness: strength_weakness: 1. Missing Relevant References: The paper lacks references to relevant literature. Scaling laws on how synthetic data plateaus or performs slower than real data during pretraining have been observed and analyzed in several studies [1][2]. Additionally, the observation that self-generated data is more sample-efficient has been noted in research on images and machine translation [3][4][5].
2. Unclear Per-Step DPO Definition: The per-step DPO is not fully defined. In Line 180, how is the “first pit” $\hat{y_c}$ determined? Does it involve looping over all intermediate steps from the beginning to find the smallest $c$? It would be helpful for the authors to provide an algorithmic outline in the appendix. In Theorem 6.1, the per-step DPO is trained with pairs (x, $[y_{1:i}, +y_{i+1}]$, $[y_{1:i}, -y_{i+1}]$), whereas Line 180 defines it as using $+y$ instead of $[y_{1:i}, +y_{i+1}]$. Which version is implemented in the experiments, and why?
3. Claims on Sample Efficiency: The improved performance on filtered $\mathcal{D}_{syn}$ from the fine-tuned model requires sampling 100 samples per question, and the per-step DPO samples require Monte Carlo rollouts for intermediate steps. This adds significant computational overhead during inference, much more than during the fine-tuning stage. A proper comparison of sample efficiency should include the inference compute spent generating these examples. Given the same computational resources, would DPO perform better as it does not require identifying the “first pit” while utilizing more synthetic data?
4. Explanation of Figure 7: The explanation of Figure 7 is unclear. How are the average Q-values calculated? What if a problem requires fewer than 8 steps in GSM8K? Will the average for step 8 be biased toward harder questions?

### Reference
[1] Dohmatob, Elvis, et al. "A tale of tails: Model collapse as a change of scaling laws." arXiv preprint arXiv:2402.07043 (2024).

[2] Fan, Lijie, et al. "Scaling laws of synthetic images for model training... for now." Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2024.

[3] Mobahi, Hossein, Mehrdad Farajtabar, and Peter Bartlett. "Self-distillation amplifies regularization in hilbert space." Advances in Neural Information Processing Systems 33 (2020): 3351-3361.

[4] Gu, Jiatao, et al. "Non-autoregressive neural machine translation." arXiv preprint arXiv:1711.02281 (2017).

[5] Zhou, Chunting, Graham Neubig, and Jiatao Gu. "Understanding knowledge distillation in non-autoregressive machine translation." arXiv preprint arXiv:1911.02727 (2019).
questions: questions: 1. Line 138: Why can we assume that the answers generated via this process are accurate? Is the model prompted with the correct solution?
2. Line 166: The sentence is not well-written.
3. DPO Suitability for Math: DPO is derived from the Bradley-Terry model, where preference follows a probabilistic distribution with softmax over reward values. For mathematical generation, however, correct answers should always be preferred over incorrect ones with probability 1. The framework, especially naive DPO, seems unsuitable for the math set, which might explain its weak performance. The KTO method, cited in the paper, proposes a different RLHF method that considers positive and negative distributions directly. How would the KTO method perform? Would the per-step version of KTO also outperform naive KTO?
4. Line 302: Why are the advantage values always non-positive?
5. Data Generation Protocols: It would be more self-contained to include critical data generation protocols in the paper rather than referencing “Training data for DPO is generated in the procedure outlined in [23]” in Appendix H at line 800.

The reviewer will consider increase the score if some of the weakness and questions are addressed.
limitations: limitations: Limitations are discussed.
paper_summary: paper_summary: There have been previous attempts at doing finetuning on positive synthetic examples to improve LM reasoning, but the performance gain from these attempts are generally quite limited (and possibly even negative). In this paper, the authors take a different approach which also accounts for negative examples and “critical” intermediate steps, improving upon previous approaches.
strength_weakness: strength_weakness: The biggest concrete thing that I felt was missing was discussion about computational costs. I think this is really important because I’d be interested in the scalability of approaches like the ones outlined in the paper. I think having some comparison of the overall FLOP required for finetuning (including the FLOP for synthetic data generation) would be very helpful. 

Another weakness is that in my understanding, the main approaches in the paper apply most directly to mathematics, since identifying critical steps involves checking results based on MC rollouts. There’s still a question about whether or not similar approaches can be applied to LMs in domains where outputs are harder to “verify” – though to be clear, I think it’s entirely reasonable that the authors focus on math in the context of this paper.

Lines 197-199: This compares the scaling exponent for data for the MATH and GSM8K datasets with the exponent from the Chinchilla paper (on MassiveText). How do we know that this implies improving coverage over samples? Other possible reasons for the different exponent come to mind – e.g. different functional forms for the scaling law in finetuning and pretraining, use of different datasets, etc.

As a minor comment, I think “It is predicted that we will run out of high-quality internet data by 2026” should be modified to be about human-generated public text data in particular, and it looks like the median year from source [53] is 2028 rather than 2026.
questions: questions: - Could the authors please provide some information about the computational costs of their approach? (perhaps comparing this for SFT, RFT, and per-step DPO)
- Clarification for lines 197-199: How do we know that this implies improving coverage over samples, rather than the other reasons I mentioned?
- Clarification for lines 203-204: Is it correct to interpret this as saying that “around 4% of sampled outputs from the SFT model are used for RFT”?
limitations: limitations: I think the authors did a fair job discussing the limitations of their work. One minor weakness is that the paper is framed around when synthetic data improves LM reasoning, but the investigation itself is more narrowly focused on mathematics.

Comments: title: Clarification on computational costs of per-step DPO and RFT
Thank you for your appreciation
Request for discussion
comment: Dear Reviewer,

We apologize for bothering you, but since there is only one day left in the discussion period, we wanted to check in with you to see if our rebuttal addresses all outstanding concerns and have a chance to address any new ones.

Thanks, 
Authors
Thank you for increasing your score! We will definitely add in these experiments and discussion, to the main paper and improve the presentation per the discussion above. 

Since there is still one more day, we are also wondering if there would be some other discussion or evidence that we can provide in this period to help improve your evaluation of our paper further. Please let us know. Thanks a lot!
I appreciate the authors for adding the experiments. I request the authors to add these experiments into the main paper to support the claims, and also improve the presentation of the paper. I've raised the score.
Thank you for your response and for increasing the score!

We are not sure if we fully follow your comment on the “computational efficiency” of RFT vs. per-step DPO, and might be misunderstanding your proposed variant of RFT, and the precise notion of “variance” being referred to. Therefore we request you to kindly correct us if the following response does not address your comment. **Please let us know.**

_We begin by belaboring that the goal of our work is not to propose “per-step DPO” as novel algorithm_, but more to highlight our conceptual framework of positive and negative synthetic data, where credit assignment with negative data can address issues caused by overfitting on spurious steps in positive synthetic data. This general point is also evidenced in our other comparisons: per-step RFT is better than RFT, and per-step KTO is better than KTO.

**Sampling new prompts is substantially more costly in our setting than sampling new responses.** We apologize if this was not clear but our claim “per-step DPO is more computationally efficient than RFT in our results” is only meant to apply to the setting with the **same set of synthetic prompts**. This is because obtaining new synthetic prompts requires querying more-capable models (like GPT-4, Gemini 1.5 Pro) in all of our experiments, which would incur a much higher factor times the computational cost of the 7B models that we study (these models are more capable than Llama2-70B, so it is safe to say that their sizes are at least 10x larger, which means at least 10x the computational cost for sampling more questions). 

While we agree that in some uses cases where sampling new prompts using a 7B model might be sufficient, there can be variants of RFT with more prompts (and less solutions per prompt) which could be more computationally efficient, this is not true in our setting, and we are not aware of any work that samples synthetic math questions (of the same quality as GPT/Gemini) with smaller scale models.

___

**Empirical justification for the cost comparison given same set of prompts:** Within the context of the same set of prompts, more samples for RFT (e.g., 100) should reduce variance, it might lead to overfitting as we have shown in Section 5. 
Our results in Figure 1c (1-page PDF) compares the best configuration of RFT (which uses 4 diverse and correct samples out of the 100 samples) with per-step DPO. Note that these 4 out of 100 samples are selected based on the techniques prescribed by Yuan et al. [68] to obtain the most competitive RFT performance. For comparison, in our experiments on the 8k sized synthetic data which has 8k prompts, we got best performance from RFT by sampling 100 responses per prompt (total of **8k * 100 = 800k**) and selecting 4 diverse and correct responses per prompt from them. On the other hand, for per-step DPO we only need one positive and one negative trace. Even accounting for the advantage estimation run on every step in the negative trace, we only needed to draw **578k samples** from the SFT policy in our experiments (indicating that our calculation in the previous response was already overestimating the _actual_ cost of per-step DPO). 

___

**Theoretical justification of the cost comparison given same set of prompts:** In general, when $p$ is the accuracy of the SFT policy, the number of samples needed to draw a single correct sample is a geometric distribution with mean $1/p$. Note, that we actually need $k$, way more than a single correct sample per prompt, to ensure there is enough diversity of solutions per prompt in RFT data (from these $k$ correct ones we selected 4 correct and diverse ones, as done in Yuan et al. [68]). From tail bounds on geometric distribution, to obtain at least $k$ positive samples per prompt, if we sample $\frac{k}{p} \cdot (1+\sqrt{\log(k/\delta)})$ samples from the SFT policy, then with probability at least $1- \delta$, we will have $k$ positive traces. On the other hand, per-step DPO requires only one positive and negative sample, obtaining which requires at most $\frac{2}{p} \cdot (1+ \sqrt{\log(2/\delta)})$ many samples with probability $\geq 1 - \delta$, when $p < 0.5$. For per-step DPO, we additionally require Monte Carlo advantage estimation, which requires sampling $M$ samples per step (with at most $L$ steps in the trace). Thus, the total number of samples (from SFT policy) needed to run per-step DPO is at most $\frac{2}{p} \cdot (1+ \sqrt{\log(2/\delta)}) + M \times L$. Note that for RFT we need about $k/p$, and since we follow Yuan et al. [68], we get the best performance of RFT when $k \approx 40$ at least, which puts the $k/p$ term in RFT around **70 to 100** for MATH and GSM8k. On the other hand the $M \times L$ in per-step DPO is **at most $50$** for both of these datasets in the experiments. Thus, even in the worst-case per-step DPO (which achieves 8x scaling) requires fewer samples than the best performing variant of RFT (which achieves 2x scaling).
Thank you immensely for your kind appreciation and very positive assessment of our work! To further improve our paper, we will incorporate the clarifications and discussion we provide in our responses. 

-Authors
I appreciate the response and the new experiments on KTO. However, I am not entirely convinced by the claim that "*per-step DPO is more computationally efficient than RFT in our results*" as the author is drawing 100 samples per prompt, which introduces the possibility of variance when drawing 10 samples per prompt while creating more prompts in RFT. This variant could potentially surpass the original RFT with 100 samples per prompt. The new experiments on the overfitting of RFT, however, demonstrate that given abundant compute resources, per-step DPO clearly outperforms. Consequently, I have increased my score.
Thanks for the really comprehensive response! I'll keep my official score at 8 - while I think the work is excellent, the description for a score of 9 requires the work to be "groundbreaking", which I think is a very high bar. However, I should emphasise that my main concerns have been addressed, and if it were possible I'd raise my score by 0.5 points to reflect this.
Dear reviewers,

Apologies for bothering you! Since we are getting close to the end of the discussion period, we would be grateful and would sincerely appreciate if you could respond to our rebuttal, leaving us enough time to address any remaining questions.

Thanks,
Authors