Learning to Reason by Failing: Offline RL on Sub-optimal Rollouts Scales Synthetic Data by 8x

Venue: ICML_cc_2024_Workshop_AI4MATH
Published: 2024-05-31 04:00:48

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 for reasoning problems via an empirical study, followed by a theoretical formalization. 
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 **doubles** the sample efficiency of synthetic data. At the same time, training on model-generated positives can amplify  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, \ie model-generated responses that are deemed incorrect via final answer checking. Crucially, these negatives must be constructed such that the training can appropriately recover the utility or credit of each intermediate step in the negative response. With this \emph{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 **8x**. 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 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 (Villalobos et al., 2022; Liu et al., 2024) , 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 (Li et al., 2024; Chen et al., 2024) on hard reasoning problems, while other results illustrate that training on synthetic data can steer the performance of the model into a downward spiral (Shumailov et al., 2023; Alemohammad et al., 2023; Gerstgrasser et al., 2024) -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, due to a lack of an understanding of how synthetic data contributes to LLM behavior, it is unclear how to best use synthetic data in practice.To provide clarity on the role of synthetic data, we aim to understand its impact on LLM capabilities via a study on reasoning problems, 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 (Li et al., 2024; Liu et al., 2023) . 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 substantialy slower than those observed during pretraining. Concretely, we find that under the scaling law of Zhang et al. (2024a) , 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 sampled from the learner 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 (Kang et al., 2024; Tirumala et al., 2022) 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. 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) (Rafailov et al., 2023) . While performance of standard DPO (Rafailov et al., 2023) largely flatlines as the synthetic problems are scaled up (Figure 5 ), we are able to attain consistent improvements if the negative data is generated appropriately. Our intuition is that instead of contrasting arbitrary correct and incorrect responses, we contrast positive and negative responses that depict good and bad choices for the more "critical" intermediate steps (Hwang et al., 2024) : 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 also show that training on this sort of negative data evades spurious correlations introduced by training on positive data alone via a controlled study.To theoretically understand our empirical 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) (Peng et al., 2019) 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 expert data. Building on theoretical results in RL (Kumar et al., 2022) , we are also able to show that when advantages can be estimated reliably, advantageweighted RL will be significantly more sample-efficient compared to imitation learning. Overall, this abstraction and conceptual model explains the utility of negative syn-thetic data over only positive synthetic data.Our contribution is a study of the role of synthetic data in improving reasoning capabilities of LLMs. We derive scaling laws for positive and negative data on common reasoning benchmarks such as GSM8K (Cobbe et al., 2021) and MATH (Hendrycks et al., 2021) , 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 for synthetic data. 
synthetic data generation pipeline: 
 Our goal in this paper is to understand the role of synthetic data in producing strong language model reasoners. Building on the recipe of Li et al. (2024) ; Liu et al. (2023) , we collect synthetic data consisting of both novel problems designed by capable models such as GPT4 (Achiam et al., 2023) and Gemini 1.5 Pro (Reid et al., 2024) , and responses to these problems, obtained from the same models. Concretely, we focus on two mathematical reasoning benchmarks: GSM8K (Cobbe et al., 2021) and MATH (Hendrycks et al., 2021) . Synthetic data pipeline. Our synthetic data generation is done in two phases. 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. (2024) , shown in Appendix E). 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 (Yu et al., 2024; Li et al., 2024) . 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 solution trace has at most L steps, an2d use y 1∶t to denote the subsequence of first t steps in the trace. Since mathematical reasoning problems require step-by-step computation, simply arriving at an incorrect final answer does not mean that all individual steps in a negative ŷ are incorrect. In fact, given previous steps ŷ1∶t-1 the following intermediate calculation ŷt is often correct. 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 4). 
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 (Yuan et al., 2023) ) or STaR (Zelikman et al., 2022) , 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 utilize a contrastive training approach, direct preference optimization (DPO (Rafailov et al., 2023 )) for incorporating negative data from π sft . In a nutshell, DPO trains a policy using the following preference optimization objective:E D ± π sft [σ (β log π(+y | x) π sft (+y | x) -β log π(-y | x) π sft (-y | x) )] . (1)We consider two objectives that construct negative data -ŷ in distinct ways and subsequently train the model on that data using Equation 1. The first variant we study is naïve DPO, which simply samples negative data -ŷ ∼ π sft (y | x) from the SFT policy and adds (x, y, -ŷ) to D ± π sft . The second variant is per-step DPO (Hwang et al., 2024) , which first samples a complete solution trace ŷ1∶L from π sft and then determines the "first pit" ŷc , such that any completion ŷc+1∶L ∼ π sft (⋅ | x, ŷ1∶c ), sampled conditioned on x, and previous steps ŷ1∶c leads to incorrect answers for a majority of the Monte-Carlo rollouts. Given the first pit ŷc , the triplet (x, y, ŷ1∶c ) is added to the negative dataset D ± π sft . 
positive data improves coverage, but: 
 Amplifies Spurious CorrelationsWe first analyze the influence of scaling up positive synthetic data on GSM8K and MATH. In this experiment, we fine-tune DeepSeek-Math-7B (Bi et al., 2024) and LLama2-7B (Touvron et al., 2023) models (details in Appendix H) on varying sizes of D syn , constructed out of a 5:1 mixture of GPT-4-turbo (Achiam et al., 2023) and Gemini-1.5 Pro (Reid et al., 2024) . 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 (Zhang et al., 2024a) , 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 (Hoffmann et al., 2022) , 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.5. Now, for existing problems in D syn we generate new responses by sampling from the π sft trained on problems+solutions in D syn . For any (x, y) ∈ D syn we generate verified positive solution traces ŷ ∼ π sft s.t. r(ŷ, y) = 1. Following Yuan et al. (2024a) , 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 50k (unlike RFT data in Figure 2(a, b ) where both questions and answers scale). In Figure 2(c amplified as we scale positive data, explaining this drop.Why is self-generated positive data more sampleefficient? 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 (Sharma et al., 2024) , but this is not the case. Our results are consistent with the study of memorization in LLMs (Kang et al., 2024; Hartmann et al., 2023; Tirumala et al., 2022) , which shows that pretrained (base) LLMs tend to memorize "hard-to-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. (2023) '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 "easierto-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 H, F 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. • When positive data from π sft contains spurious steps, scaling leads to worse test errors. 
negative synthetic data enables per-step credit assignment: 
 The spurious correlations from Section 4 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 2 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 π (2) Intuitively, for any partial solution upto i steps, this Qfunction 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, for any given step ŷi , we can define its advan-tage as the relative change in Q π when adding step ŷi in comparison with other possible candidates for step i: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 (Sutton & Barto, 2018) , 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).Critical steps, per-step DPO, and advantage-weighted RL. We can use advatanges (Equation 3) to characterize critical steps. While the advantage values will always be non-positive by definition, steps that attain a higher advantage value than others are more critical to precisely execute. In contrast, steps that with very low advantage values are likely worse and must be unlearned. Our definition of the advantage function and this connection also implies that one can calculate advantages for each step in a response via additional Monte-Carlo rollouts starting from prefixes defined by partial solutions. These advantage estimates (Equation 3) can then be used for training the model by running advantage-weighted RL. However, in Theorem 5.1 we formally show that DPO on per-step pairs, which contrasts positive and negative traces obtained via additional rollouts from policy π, on prefixes of a response sampled from π sft is equivalent to advantage-weighted RL. A proof of Theorem 5.1 is in Appendix C. Note that unlike the standard reduction of DPO to the RL objective under some reward function (Rafailov et al., 2023; 2024) , Theorem 5.1 is stronger in that it identifies the value function induced by per-step DPO.Theorem 5.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:EQUATION)Practical instantation of DPO with per-step pairs. Our practical implementation of per-step DPO is an approximation of the above scheme, with π chosen to be a particular policy. Concretely, the practical implementation of per-step DPO sets π to be the best-of-K policy, BoK(π sft ) where K = 5. There are two advantages for choosing a higher value of K: (i) estimating the advantage in Equation 3with Monte-Carlo rollouts has lower variance; 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 will only improve, in the neighborhood of the SFT policy π sft that appears in the regularization term. We will next discuss scaling results for negative data, and then in Section 5.3 show how per-step credit assignment improves generalization and builds robustness to spurious correlations.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, also note that 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.Choice of negative data has significant impact. In Figure 5 (c) we plot negative data scaling laws where the choice of negative data (and thereby pairs for DPO in Equation 1) differs. Observe that standard pairing of positive and negative responses in D ± π sft for DPO (Rafailov et al., 2023) does not improve upon the SFT policy. As such, we needed to tune β in Equation 1 for DPO but could not fully avoid performance degradation. Our conceptual model explains this result: since 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 (Saeidi et al., 2024; Pang et al., 2024; Xu et al., 2024) . In fact, Pal et al. (2024) also find similar concerns with random pairing and instead pair positives and negatives that with highest edit distance, which leads to some improvement over standard DPO (Figure 2(c )) but still performs poorer than per-step DPO that accounts for credit.Takeaways for scaling negative synthetic data , we observe an 8× gain from per-step DPO (Section 3) 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 (Rafailov et al., 2023) leads to worse performance as we scale D syn .W 4 C 1 W 1 W 2 S 1 S 2 W 3 C 2 C 3 C 4 C 5 C 6Wrong solution 𝐴 ! " (𝐶 % , 𝐶 % → 𝑊 $ ) is low (leads to a wrong sol.)𝐴 ! " (𝐶 % , 𝐶 % → 𝐶 & ) is high (leads to the correct sol.)𝐶 % → 𝐶 & is criticalInformally, step is reasoning operation performed as a part of solving the problem, e.g. if previous state was 2x-5 = 1, then one step can be calculating value of x.𝐶 # → 𝐶 % is criticalFigure 6 : Illustration of advantage estimation from negative data for identifying critical steps in synthetic model generations.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 D.1) Advantage-weighted RL de-emphasizes spurious steps and emphasizes critical steps. Our key insight is that spurious correlations emerge in monolithic SFT or RFT due to the well-known issue of causal confusion (De Haan et al., 2019) 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 teacherforcing 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 F. In Figure 8 , 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 5.1). Standard DPO fails to improve performance since it has poor success rate at earlier (critical) steps.2) Generalization depends on low advantage estimation error. 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 Didactic analysis. With the above insight, 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 G) from Bachmann & Nagarajan (2024) , 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 "hardto-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: (1) an under-trained SFT model with a large training and test loss, and (2) an SFT model obtained by 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 undertrained or early-stopped π sft improves both training loss and test performance. As shown in Figure 7(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 7 (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, perstep 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 7 (c), we observe that both SFT and per-step DPO exhibit identical test errors since training with more negative data exacerbates the model's dependence on memorizing the critical token, which manifests in the form of lower train 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)). Thus, when the SFT policy has sufficiently memorized the training data using a spurious feature, training further is unable to unlearn this dependence. Hence, in this regime, negative data leads to no improvement, capping performance at what was attained by fine-tuning on positive data.Takeaways for generalization with negative 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.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 (Williams & Zipser, 1989; Brown et al., 2020) . First, we discuss some failure modes of this procedure for math reasoning that positive or negative synthetic data can address.Failure modes for supervised finetuning (SFT). First, since SFT induces an open-loop (Wu et al., 2023) next-token prediction loss, prediction errors on even a single token can snowball during inference, leading to poor performance on the prompts appearing in the dataitself (Kääriäinen, 2006; Ross & Bagnell, 2010) . Second, even when an LLM has perfectly cloned the SFT data, it is prone to memorize "hard to learn" tokens (Tirumala et al., 2022) , especially in planning and lookahead tasks (McCoy et al., 2023; Momennejad et al., 2024) , which is critical for math reasoning. This leads to poor generalization (Bachmann & Nagarajan, 2024; Dziri et al., 2024) and hallucination on new novel, test-tim prompts (Kang et al., 2024) . 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. Positive synthetic data. Learning theory dictates that the SFT policy trained on more SFT data (e.g., 1.5M for DeepSeek-Math (Bi et al., 2024) ) would have improved math reasoning capbabilities. Thus, a common goal for generating synthetic data as close as possible to the SFT data (Li et al., 2024; Liu et al., 2023; 2024) . That said, generating high quality math data can be challenging, since verification can often be hard. When synthetic data is verified by larger models (Sharma et al., 2024; Wang et al., 2024) , recent works (Luo et al., 2023; Yu et al., 2024) observe scaling similar to finetuning LLMs on expert data (Zhang et al., 2024a; Yuan et al., 2023) , while another work (Dong et al., 2023) notes the compositional gains from SFT data for code generation. Common sources of "good" synthetic data include responses from stronger teachers (Li et al., 2024; Lightman et al., 2023) , or data generated by the SFT policy itself, in the framework of reinforced self-training (ReST) and STaR (Zelikman et al., 2022; Singh et al., 2024; Chen et al., 2024; Yuan et al., 2023) . 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 (Kang et al., 2024) which often prevents undesirable memorization (Tirumala et al., 2022) . Finally, our work also sheds light on several concerns about training on synthetic positive data amplifying biases (Seddik et al., 2024; Wyllie et al., 2024) , and leading to model collapse (Dohmatob et al., 2024; Gerstgrasser et al., 2024) , 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 for math reasoning (Yu et al., 2024; Li et al., 2024; Liu et al., 2024; Yuan et al., 2023) focus on training on positive (correct) answers, our work also studies complementary gains from negative (incorrect) completions generated by the SFT policy (Hwang et al., 2024; Pal et al., 2024; Yuan et al., 2024b; Pang et al., 2024) . To leverage sub-optimal negative data, we adopt the generic framework of offline preference optimization (Rafailov et al., 2023; Ethayarajh et al., 2024; Zhao et al., 2022) , where a preference pair is constructed using correct and incorrect responses for the same problem (Pal et al., 2024) . Despite numerous studies on preference data composition (Chen et al., 2024; Cheng et al., 2023; Tajwar et al., 2024; Chiang et al., 2023; Wang et al., 2023; Munos et al., 2023; Swamy et al., 2024) , it remains unclear what is the best approach 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 (Pang et al., 2024; Hong et al., 2024; Xu et al., 2024; Pal et al., 2024) due to objective mismatch (Tajwar et al., 2024; Zhang et al., 2024b) and requires auxilliary losses to perform well. Another option is to utilize negative data for training verifiers (Hosseini et al., 2024; Yu et al., 2023) 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 then use to establish the equivalence of preference optimiztion to to advantage weighted RL. Self-explore method in Hwang et al. (2024) can be viewed as an special instance of our general framework. Another work exploiting per-step credits is Wang et al. (2024) : through tree-based sampling they identify and use the reasoning subsequence that led to the most incorrect answers under the SFT policy for training a reward model. While this is indeed related, our conceptual model and analysis also aims to understand 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.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 and generating negative/positive data by referencing synthetic data answers can reinforce unwanted spurious correlations highlighted in our work. This means that other novel recipes for generating synthetic problems may be utilized in the future, and our analysis might need to be re-done with those novel recipes. 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.Broader impact. Our work focuses purely on understanding the role of synthetic data in improving reasoning capabilities of LLMs. While excessive use of synthetic data can have unintended side effects upon deployment (e.g., fitting onto spurious correlations as we illustrate in Section 4) and advanced reasoning capabilities may have the potential to affect economy, human life, and society in both good and bad ways, we believe that these societal impacts are not unique or special to our work when compared to other works studying similar problems. In fact, with capabilities in foundation models improving day-by-day, future research and policy decisions would only benefit from more conceptual models to understand how algorithms operate and how data affects performance, which our work attempts to study.We 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 C.1 (Equivalence of advantage-weighted RL and DPO with per-step pairs). The optimal policy from Equation 1with 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 advantageweighted RL objective:EQUATIONProof. To prove this statement, we make the following observation: DPO (Rafailov et al., 2023) 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 (Bradley & Terry, 1952) induced by the reward function r:EQUATIONGiven this background information, we know that the optimal advantage-weighted RL policy optimizing Equation 5 is given by:EQUATIONin 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 7 ). On the other hand, if advantages are more accurate, training on negative data should improve performance.Prompt used for GSM8K/MATH synthetic data (Li et al., 2024) 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. Please create a new question based on the Given Question and following instructions.To achieve the goal, you have one job. # Please generate a similar but new question according to the Given Question.You have four principles to do this. # Ensure the new question only asks for one thing, be reasonable, be based on the Given Question, and can be answered with only a number(float or integer). For example, DO NOT ask, 'what is the amount of A, B and C?'. # Ensure the new question is in line with common sense of life. For example, the amount someone has or pays must be a positive number, and the number of people must be an integer. # Ensure your student can answer the new question without the given question. If you want to use some numbers, conditions or background in the given question, please restate them to ensure no information is omitted in your new question. # You only need to create the new question. Please DO NOT solve it. Given Question: <insert question from original dataset here> Your output should be in the following format: CREATED QUESTION: <your created 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.In this section, we present several examples from the GSM8K and MATH synthetic datasets, and higlight the steps that were deemed to be low or high advantage based on the estimated advantage value. The darker the intensity of the color, the lower the advantage of that step.Question: Ken created a care package to send to his brother, who was away at boarding school. Ken placed a box on a scale, and then he poured into the box enough jelly beans to bring the weight to 2 pounds. Then, he added enough brownies to cause the weight to triple. Next, he added another 2 pounds of jelly beans. And finally, he added enough gummy worms to double the weight once again. What was the final weight of the box of goodies, in pounds? Positive response with identified spurious step:When the weight was originally on the scale, the box weighed 0 pounds. After Ken added the jelly beans to the box, its weight was 2 pounds -0 pounds = «2-0=2»2 pounds. Then Ken added the brownies to the box, which caused the box to weigh 2 pounds * 3 = «2*3=6»6 pounds. The next step was to add 2 pounds of jelly beans, which caused the box to weigh 6 pounds + 2 pounds = «6+2=8»8 pounds. First, we need to figure out what the weight of the box was when Ken put the jelly beans in it. 2 pounds of jelly beans was enough to triple the weight, so the box was at 2 pounds / 3 = «2/3=.6666666666666667».6666666666666667 pounds. Finally, Ken added the gummy worms, causing the box to weigh 8 pounds * 2 = «8*2=16»16 pounds. The answer is 16Anonymous Institution, Anonymous City, Anonymous Region, Anonymous Country. Correspondence to: Anonymous Author <anon.email@domain.com>. Preliminary work. Under review by the International Conference on Machine Learning (ICML). Do not distribute. 
 
 Appendix:  


Decision: This paper investigates the helps/hurts of training models on model-generated synthetic data for math reasoning. They first conduct an empirical study and then propose to construct negative samples to address spurious correlations in SFT/RFT policy. The reviewers agree that the research problem is significant. The observations are insightful and are well-motivated and grounded with theorems, explanations, and experiments. The proposed method is effective and promising. I believe this study is valuable and inspiring for the community.

Reviews: review: paper_summary: paper_summary: This paper empirically presents the scaling laws of using two types of positive examples to improve models and suggests an approach per-step DPO to address spurious pattern issue, in math word problems. It shows that while learning from self-generated positive examples brings a better scaling law than from strong models (like GPT-4)-generated examples, it suffers from amplifying spurious patterns, which hurts its scalability. And it proposes a conceptual model to suggest that per-step DPO is equivalent to advantage-weighted RL that can de-emphasize spurious steps and emphasize critical steps.
strength_weakness: strength_weakness: 1.	Hard to follow. There are many sentences hard to understand and exist some logical jump.

For example, 

(1)	It’s hard to understand the sentence “the training can appropriately recover the utility or credit of each intermediate step in the negative response” in Abstract.

(2)	What is “per-step DPO”? This name is used without definition.

(3)	“The advantage values will always be non-positive by definition” in line 288-290. Why?

(4)	Equation 3 directly replace the state-value expression with action-value expression, without demonstrating the intermediate step. 

(5)	The last paragraph in the Page 5, why use best-of-K as the policy, rather than the sft model?

(6)	“… This means ys attains a low advantage. On the other hand, for a correct step, whp estimated advantage is higher” The advantage is a concept defined based on comparison, but the statement here is telling “xx has a low/high advantage” due to the absolute property (i.e. correct/incorrect) rather than comparison.

(7)	Do per-step DPO method leverage the identified “critical steps”?

2.	Lack of method and implementation details, hard to examine the experiment results, analysis, and conclusions.

For example,

(1)	In Figure 2, what are the training datasets of SFT and RFT? Do they share the same problem set and only differ in solutions, or they also have a different problem set? For each problem, are there multiple solutions , or only one solution?

(2)	What is a “step”? Token? Sentence?

(3)	How to select the best when using best-of-K?

(4)	How to estimate Q-value and the advantage in this paper?

(5)	What is per-step DPO algorithm? How are the negative examples collected?
questions: questions: See the questions above
paper_summary: paper_summary: This paper studies finetuning LLM with synthetic data for (math) reasoning problems. Specifically, this paper shows that using synthetic positive data from a fine-tuned learner has better sample complexity than using data from capable LLMs (e.g. ChatGPT). This paper further proposes to incorporate negative samples to eliminate spurious correlations, by identifying the 'critical step' and applying per-step DPO. The overall gain is to save 8 times of the sample complexity on synthetic data.
strength_weakness: strength_weakness: Currently the paper only experiments on two datasets, it will be interesting to see how the scaling factor/sample complexity changes for other datasets. However, given the extensive computation resource demand of training/finetuning LLM, it is fine to defer them to future work.
questions: questions: I found the idea of using the value function to identify critical steps very neat. I have a question: suppose we just use $\pi_{sft}$ to compute the Q function, then we may expect a large estimation error in Q due to a large estimation error in $\pi_{sft}$, at the early stage of the training. As a result, we essentially introduced bad samples to the model at the early stage of training, I am wondering if this is a problem, and if so, can we address it?