RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-Fold
Authors: Amrith Setlur
Saurabh Garg
Xinyang Geng
Naman Garg
Virginia Smith
Aviral Kumar
Venue: NeurIPS 2024 poster (2024)
Keywords: Synthetic data
math reasoning
reinforcement learning
large language models
Primary area: natural_language_processing

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.

RL on Incorrect Synthetic Data Scales the Efficiency of LLM Math Reasoning by Eight-Fold
Amrith Setlur" *1 Saurabh Garg's
Xinyang (Young) Geng Naman Garg"
Virginia Smith
Aviral Kumar Google DeepMind
CCaneegie Mellon University
MuultiOn
Abstract
synthetic data is promising approach for finetuning LLMs, but remains unclear when 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 finetuming 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 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., mooeel-genertte responses that are deemed incorrect by 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 8x. We show that training on per-step negatives can help to unlearn spurious correlations in the positive data, and is equivalent that it inherits robustness benefits of RL over imitating positive data alone.
Training on
waaanttg-weighhee reinforcement learning (RL), implying
Introduction
Training large language models (LLMs) relies the ability to train large amounts of high-quality data. It is predicted that we will run out of high-quality internet data by 2026 [32, 58], necessitating 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] ammplying 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 lack of an understanding of how synthetic data contributes to LLM behavior.
training on model-generated data, or what commonly referred
To provide clarity on how synthetic data contributes to performance, we aim to understand its impact on L.M capabilities via study on math reasoning, prevalent scenario where synthetic data used. responses
Typically, in this setting, synthetic data corresponds to correct or positive model-generte for 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 0..15 in the size D of synthetic dataset. Second, we observe that not all types scales as > D 00.05 D -0015
Corresponding author. Please send correspondences to asetlur andrew edu.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

of positive synthetic data are equally effective: often positive responses self- generated by the learner itself are as effective as 2x synthetic data from bigger models in improving performance. This is because responses from a similar model are "easier-to-fi"" 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/irelleant 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 re- sponses: responses generated by the model that do not result in obtaining correct final answer. One way to utilize negative responses is via meth- ods such as direct preference optimiza- tion (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 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 unable 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 8x. We show that training on this sort of negative data evades spurious steps amplified by training on positive data alone.
Negative Data
Alber negothv colouisting pen. step ciedi?
Synthetic
Samplled data
Tratane madel
SFT Model
Feeturm
Per-step DPO Model
quistiins avevehers dato and lie beseliss
Reasoning
pains sampled from capabte model, 4.g. 6PT-4
Positive Data
RFT Model
Treetme
SErrect BEOVEES
and (. (b
Figure 1: Positive and negative synthetic data: Pictorial repre- sentation of positive/negative synthetic data definitions how they are fed to SFT, RFT and DPO.
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 devaantgg--eiihheee
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 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-weightt RL through the lens of distribution robust objectives. Second, building on theoretical results RL [27], we are also able to show that when advantages can be estimated reliably, ad advantage-weighte RL will be significantly more sample-efficient compared to imitation. Overall, this model explains the utility of negative data over only positive data.
dirrantage-weighee RL enables
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 geder-generated positive synthetic data can improve sample efficiency by 2x but also amplifies spurious correlations; (c) appropriate ways of constructing learner learner-speeific negative data with emphasis on critical steps. results in a performance boost equivalent to scaling up positive data 8x; (d) training with negative data provides mechanism 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.
2 Related Work
A standard procedure finetune pretrained LLM is 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 Meah [5]) would have improved math reasoning capbabilities. Thus,
2

---

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 L.MMs on expert data [69, 711, 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, 70J. 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- eeff-generated positive data. We connect our findings to evidence showing "ease of learning" generalizable features on self- self-generated completions [26] which often prevents undesirable memorization [56]. Finally, our work also sheds light several concerns about training 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
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 a preference optimization problem. Randomly pairing correct and incorrect completions in 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 negative data for training verifiers [22, 65] but this line of work still only trains the policy using positive data. We introduce 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 al. [23] can be viewed as an special instance of our general framework. Other works [34, 59] exploit per-step credit assignment through brse- sampling. They identify the reasoning subsequence that led to the most incorrect answers under the SFT policy for training 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.
3 Problem Setup and Synthetic Data Generation Pipeline
Building on the recipe of Li et al. [29], Liu et al. [31]. 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.
GSMSK [1 [] and MATH [19] to collect
Synthetic data pipeline. First, given a dataset Dreat = {(x,, vt)} of problems æf Preal and solution traces y/ Preal (3/ x;),, we prompt one of the highly-capable models with a uniformly random sample (x. ; y.) E Dreat and ask the model to generate a new problem æ; such that it is similar to the real problem æ;, in way that feasible solution exists. Second, we ask the model to provide solution trace answer y, with step-by-step reasoning (exact prompts for 2;, y are borrowed from Li et al. [29]. shown in Appendix H). We assume that the answers generated via this process accurate, and perform lightweight filtering step to remove duplicates, sadly-formatted answer traces, and model failures. Based the above, for any synthetic problem and solution pair (a,, y), we can define a binary reward function r rl. ÿ) + {0, 1}. which verifies if a new solution trace ÿ is correct or not. This is implemented with 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 r(y y) 1, and negative if it produces an incorrect final answer, i.e., r( y) = 0. By definition, r r(y. y) = 1, and the original trace is always positive.
Positive and negative datasets. The above process induces joint distribution Payn (x. 8). tid samples from which yields positive synthetic dataset Dayn- We note that the sampling process for Dayn is designed to ensure that the induced marginal distribution over synthetic problems Psy((x)) is close to (z). We will use D" to denote the positive dataset of (zz, +ÿ) where +ú is a positive solution trace generated from some policy x(- x). For a positive +ú and negative- - trace, sampled from the same policy T(. | x)), we denote dataset over problems and solution pairs: (xx +ÿ, -ÿ) as D
3

---

Reasoning steps. The trace y, consists of several intermediate steps, y; = [ 1......... V.r.l We assume each trace has at most L steps, and use VIut to denote the subsequence of first steps. Since mathematical reasoning problems require step-by-step computation, simply arriving at an incorrect final answer does not mean that all steps also have incorrect reasoning steps. In fact, even the original answers generated by more capable models in D Say may also contain incorrect reasoning steps, and training on such traces may actually lead to unintended consequences (Section 5).
negative y are incorrect. Similarly, a positive y may
4 Learning from Synthetic Data
In this section, we discuss various algorithms for learning from the synthetic dataset Dayn discussed in the previous section, well as positive and negative solution traces generated using model.
Supervised and rejection finetuning (SFT and RFT). Given positive synthetic Paya. perhaps the most straightforward approach (and the most prevalent) is to learn Teft. on this data via supervised next-token prediction: (-1=) := arg max, En - [log x (y)
[=]] Another option is to train via supervised next-token prediction on problems in Day Dayn, but when using positive solution trace y sampled from (- instead of positive synthetic responses from the capable models in Dayn- Akin to rejection finetuning (RFT [69] or STaR [70]), sampling from T | x) once is not guaranteed to give positive response, and we instead sample M times for each æ and construct the dataset D of SFT policy generated positive responses. Then, we apply the next-token prediction loss on D att
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 Taf. In a nutshell, DPO trains a policy using the following preference optimization objective:
T T( x) Taft (+y x)
Teft( (- x) )]
x(- x))
min (T) == Bee, (t.., DD. a Blg
3 log
(1)
We consider two objectives that construct negative data and subsequently optimize Equation 1. The first variant standard DPO [41], which samples negative data -ÿ from the Teft (with rejection sampling) and adds (x. y. -g)) to aea The second variant is per-step DPO [23], which first samples a complete solution trace 91-r from Jaft and then determines the "first pit" y. The first pit D. is the step where any completion following the step: De+I:L ~ a- x; 91:e) leads to incorrect answers in expectation under Taft- The triplet (æ, y, Dree) is added to the preference dataset D
5 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-7BB [57] models (details in Appendix J) on varying sizes of D Daym: constructed out of 5:1 mixture of GPT-4-turbo [1] and Gemini- 1.5 Pro [44]. We obtain series of SFT policies on this data scaling ladder. We then train 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 Dayn we are increasing coverage under Preals i.e., adding new æ, y with non-zero probability under Preat. In Figures 2(a.b), we plot the test error rate of the SFT policy as Daya is scaled. As expected, we observe that the test eиror rate on both GSM8K and MATH improves with more positive data. Further, by simply fitting the parametric scaling law from [71], for := [Daym I. we find that the scaling trends decay GSM8K and =D =0.05 on the harder MATH dataset, with similar trends for the
as = -0.15 10.15 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 Daym are indeed improving coverage over samples in Preat(:: xx 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 Dayn by querying GPT-4 and Gemini- Now, for existing problems in Dayn we generate new responses by sampling from the Jaft trained on problems+solutions in D Dayn. For any (x,, y) E D sayn

---

GSM8K
MATH
RFT Soeling (iised questiona/ promple)
0.00
SET Llama?
888
0130
SPT Limn?
0.62
MK1H jeseiges
10k prompte
0,38
0:60
Test otre
0.27
SPT Deeplbon
SFT DeepStek Diepseck
Test arror
0.24
RET DospSeck
0.00
0.58
0.21
Test
0.67
CS335K jeoriges
101
0:28
0.18
SPT DeeppSek Pooeic
0:30
0.54
0:43
SFT DorpBick Possti
0:26
0.21
0.06
0:35
0.22
Sc10k
315
6ik
128k
sktok
57k
66k
1.88
10620k:33k oTL DEL
125k
Syathotic datasen sise (1Paa))
Syuthotic datuset size (Payn))
RFT dataset (PLD
(a)
(h)
(c)
Figure 2: Positive data sealing laws: On GSM8K (a) and MATH (b), we evaluate SFT trained on Daya and
RFT that uses SFT policy generated positives (D ). as scale Peyn. observing D to be 2x effective
as D Payn. In (c), we plot performance of RFT the number of correct solutions in Di... are scaled, for fixed set of 8k/16k problems from Paya. observing that scaling model positives can amplity spurious correlations.
we generate verified positive solution traces D Taft s.t. r(ğ. y) 1. Following Yuan et al. [67], to ensure we sample enough correct responses, we sample 100 times from Tah. and generate RFT datasets Dt* Tun? where each problem has atmost correct and diverse solutions. Next, we finetune the pretrained DeepSeck-Math-7BB model on these new series of RFT datasets and plot the performance on GSM8K and MATH (Figure 2(). First, we observe that for any size of Dayus the performance of the RFT model is better than the corresponding SFT model, and the difference remains consistent as we scale Dayn. Surprisingly, this indicates that training on positive answer traces from the 7B Tate æ) can lead to better performing policies than capable models.
What is the value of positives from Tan (y/ | x)? sampling from Tsh. also improves coverage and performance, then should we scale problems and solutions in Payu. or just solutions in D ? To answer this, we need to assign a value to the RFT dataset D= in terms of [D We do this by training SFT policies on D Payn 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- -ath-7B finetuned on the different sizes of D Comparing the lowest values of the curves in Figure 2(c) with D Dayn scaling in Figure 2(a,b), we note that performance from D Jaft is 2x the size of Dsyn used to train Tah We also note that performance can plateau (or worsen in the case of GSM8K) lot. This is because r(., y) is unable to verify the correctness of each step in the positive solution traces in D "ats" 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.
scale up Di.... by
Why is self- geff-gene positive data more sample-efficintt? From our result above, we find that solutions sampled from Taf (trained on Dayn) yield better models, as good as those trained on 2 x (D |Day I. This finding is surprising since one might expect more capable GPT-4/Gemini models to present better solutions, training 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 "hard- to-fit" and "fut-of- teitto-f-peerrainnng... pretraining-distribuutoo ddisrrbbuutrion responses during finetuning, resulting in imperfect generalization. In contrast, correct response traces produced by Taft problems from Dayn are not as hard-to-fit or as out-o--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 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 Dt for each question in Dayn. 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.
SPT data
0.00
RFT dads
0.26
D.04
0.02
0.00
0.0
02
0.4
0.5
0.8
10
12 1.4
Negariv Log Libeihood
Figure 3: Under base LLM, Diaa has higher likelihood than Daym-
5

---

SFT/RFT policy suffers from spurious correlations in posi- tive 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,
HFT
0.00
0.00
This failure can be attributed to the presence of incorrect/ireel- evant steps that are not detected by our verifier, since it only verifies the final answer (see Appendix J, K for examples). For a problem æ, when the LLM is trained with supervised next-token prediction on some positive sub-optimal y in the RFT data, with incorrect step y/-- it is likely to overfit on spurious correlations between the sub-optimal subsequence VI:k- and the following valid step yk-1- when trying to maxi- mize π (1y==11911s .)) To verify this hypothesis, Specifically, for each question in Deyn we sample "spurious steps" from Taft trained on it, i.e., steps which lead to the incorrect answer with high probability under Taft (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 Jah. policy itself.
OSMEER
MATH
Figure 4: Spurious correlations in RFT data hurt performance.
amplify the presence of these spurious steps.
Takeaways for scaling positive synthetic data
While positive data from GPT-4/Gemini-11. improves coverage over new problems and solutions, positive data from SFT policy trained on it is 2x more sample efficient. Scaling positive data (- *sft that contains spurious steps, leads worse test errors.
Negative Synthetic Data Enables Per-Step Credit Assignment
The spurious correlations from Section correspond to intermediate irrelevant or incorrect steps that are able still steer the model towards the correct response on some training problems, but derail 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 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 Daya.
6.1 Conceptual Model: Constructing Negatives to Enable Per-Step Credit Assignment
While naively 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 - (even when accurate and relevant), it does not account for the importance of each step. Formally, given negative solution trace yy, would want to identify the first critical step where the model introduces flaw -y. and emphasize alternate correct completions from this step that the model could have still produced. Likewise, given positive solution trace, +y. we would like to identify if a given step +y; does not make progress towards the solution by identifying if there exist alternatives from its predecessor step. #::--11 which now presents key decision- maaiingnmmaingg point. What are these critical steps and how can we identify them procedurally?
Value functions. We can formalize this notion of critical step under the notion of value functions from reinforcement learning (RL). Recall that both +y and -y are sampled from Teft- For problem x, with correct solution y, response ÿ with sequence of steps Ú 11:-11 and candidate step ú., define the value function for step ys. and previous steps under some policy ग as:
Q# D1:-11 Ú, )=
E New - At-1 ....) ([01:: v.4r..l.))
statle
action
expocted future reward under new actions sampled by policy &
Intuitively, for any partial solution upto i steps, this f-function evaluates the probability of succeeding at solving the problem given the remaining budget of L - i 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 Tat (denoted as BoK (Ta)) enables a particularly interesting tradeoff between Q- Q-value estimation and policy improvement. Another common choice is Taf itself. Now,

---

GSMBK
MATH
Choice of Negation Data on MATH
Clandd
0.90
SPT Land
DEC
0163
0.72
0.79
RPO (Rabsher st al (263))
Test ater
0.25
0.6
SET DeepSenn DLN)
0.07
UPO (Pai (285))
0.21
Tedt
0.68
0.56
8X
Test
0.00
prrstop
0.77
0.18
6.6127
0.52
0.00
0.00
0.00
0:30
0.53
0.01
0.37
Sc10k
61k
1286
31%
6ik
1186
8616k
35%
6ikk
1284
Syathotic danaset (1Pgg))
Synthotic dasasee size ((Paa))
Synthetic dataset size (Pan))
(a)
(b)
(c)
Figure 5: Negative data scaling laws: We evaluate algorithms that consume negative data as we scale D Dan and compare them with only positive training (SFT) D Pay.. On GSM8K (a) and MATH (b), observe 8x 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 naively pairing positives and negatives [41] leads to worse performance as we scale Dayn-
for any given step D., we can define its advantage the relative change in Q+ when adding step 9; in comparison with other possible candidates for step as follows:
Aa 11:-1: ú:) = Q2 (1r, 1 ú.) - Qa (1. Ø1H-2: Úi-1)-
Equation 3 is identical to the definition of advantage of action (i.e., ÿ,) at state (æ. U 1 from RL [53]. in that it is the gap between the Q-value of state-action pair and the value function of the state (which itself is equal to the Q-value of the previous step due deterministic dynamics).
Critical steps, per-step DPO, and ad wedianttge-wiighedd 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 pre- cisely 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 response via additional Monte Carlo rollouts starting from pre- fixes defined by partial solutions. One could then use these advantage estimates (Equation 3) for training the model, for example, by running advantage- 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-weighie values. Theorem 6. shows that DPO performed over precise pair distribution contrasting positive and negative traces obtained via additional rollouts from म. on prefixes of a response sampled from Tat is equivalent to addantage-weighted RL. A proof of Theorem 6. 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.
Ouention: and peano cos 849, What the appter?
pours 5es, apples
Conract
C. cest of opein
Correct but cisractinng stop that may donal the modol
Inconed step
Tcehe,, lisey 74.
Oy 2--0 G4 anl
Whong solucion
Se 6/
To sancess en ligl Feet
X
Artentiage funet on aetrrisee
Aeto, G.-2) 2.3 la love johtnn keads woog adiutio)
Worg ROLLDOO
AetTU Ga3l mirrage
and woog sokkior
A MM) belww (nace wrong soluttor)
Autous - <a la Hish boads a0 the comnec aevrte))
Conect solution
Figure 6: Illustration of advantage estimation from negative data on a didactic example in synthetic model generations. Critical steps are those with high advantage values.
objective without computing their
Theorem 6.1 (Equivalence of advantage-weighted RL and DPO with per-step pairs). The optimal [ [V1s: -y++1]) where the positive and negative traces share prefix Vıs Taft and -Yi+1 aat (-(ar, Vr:). +Y+-1 ~ a aAA vrsi-)
policy from Equation I with D Din given by (vr, +U++1
Ag (x. Viai I),,)),, is identical to the optima of the advantage- RL. objective:
Σ log 7 ( vox-1) exp (Aa(#, vo.-1i9))13)
max Ex ( (-an)-(-a)))
(4)
Practical instantation of DPO with per-step pairs. In most of our experiments, we instantiate a practical version the above framework, following the scheme 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 only) in practice. We will also experiment with the complete version (parts I and 2) later in Section 6.3.3. Instead of computing
7

---

advantage estimates for each step, and then sampling preference pairs, as described in Theorem 6. 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, (oK(Tatt) where K' = 5. There are two benefits associated with this choice of मं, especially a higher value of K: (i) estimating the advantage in Equation 3 with 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) (Bok(T is non-decreasing function in K for any state-action, which implies that the solution of advantage-weighhed RL objective, in principle, can now improve over a better policy BoK(TTa)) compared to Tafe- Next, we discuss scaling results for negative data, and then in Section 6.3 show how per-step credit assigmment improves generalization and suppresses irrelevant and incorrect steps appearing in a response, extracting more gains from the same synthetic data.
6.2 Scaling Results for Negative Data
Observe in Figure 5(,,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 Dayn. per-step DPO also substantially improves over RFT (Figure 2) on both datasets, and overall, while RFT improved effective data size of Dayn by 2x, additionally training on negative data extends the performance improvement to 8x the size of D Panu. Additionally, since per-step DPO estimates advantage of each step under the Best-of-5 policy, one might expect saturation in the pass @5 performance of the per-step DPO solution. On the contrary, we find that pass@5 5 performance also improves consistently. In Appendix D we present results for 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 = for DPO [41] does not improve over the SFT policy. As such, tuned 3 in Equation 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 8x.
6.3
Why Does Credit Assignment from Negative Data Improve Model Generalization?
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-wedt weighted RL. We present two empirical studies below, and formal theoretical guarantee combining these insights is shown in Appendix F.
6.3.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 [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 Figure 4.
10.50
af
0.45
We now explain how online model-speciff interventions and advantage estimation would address this issue. Consider स = Tsh. As we show later, in under-trained models memorized steps are imperfectly cloned under Tat. implying that while teacher-foreing loss is low for some spurious, memorized step y.: sampling paths from Teft. conditioned on V1:, is likely to generate incorrect responses. This means y. attains low advantage. On the other
(latake plos
0.35
100 (H4) (RAA))
0.30
Figure 7: Per-step DPO improves Q-values at each step, standard DPO only improves irrelevant steps.
8

---

also low, to a similar hand, for 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 ddvantage-weighhe RL (Theorem 6.1). Standard DPO fails to improve performance since it has poor success rate at earlier (critical) steps.
6.3.2 Why Does Generalization Improve?: Connecting Advantage-Weightel RL to DRO
In the previous section, we discussed how advantage-weightne RL preferentially weighs the next- token 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- advantage-weighted 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 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- oogliiklihood loss more for the critical step, i.c., those steps from where the model is more likely 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 - the training data achieve low loss values, the solution for the
RL objective guarantees that the negative log-likelihood of the critical steps with high advantage estimates under मे (which of per-step DPO is BoK (Te(t) 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- down-weighting it for the spurious ones. The guarantees on the training data (Dsyn) 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.
6.3.3 But, Attaining Low Generalization Error Requires 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 ग = Taft- When the initial advantage of spurious step incorrectly over-estimated, negative data algorithms up- upeweight the likelihood further. This only leads to further memorization. Hence, most Monte-Carlo rollouts from Tsh. would rely upon the memorized feature. Since the model generates the correct answer from the memorized feature, it would estimate higher Ary. . and this downward spiral of training with increasing weights on the spurious step leads to test-time model collapse. On the other hand, when f = BoK (n,)( for higher value of K, the Monte-Carlo advantage estimator has lower variance (and error). This discussion also justifies the choice of K=5, an intermediate value, in per-step DPO.
6.3.4 Validating Claims About Generalization: Controlled Analysis on a Didactic Problem
With the above insights, we now study the influence of Taft on the generalization effects of per-step DPO. For our analysis. we consider 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 Tah minimizes SFT loss by memorizing the "hard-to tord-to-pur 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 Taft. we choose several intermediate checkpoints obtained during supervised finetuning for synthetic negative data generation. We consider three initializations: (1) an ander-trained SFT model with large training and test loss, and (2) an SET model obtained by

---

0.30
0.25
SFT low
0.8
SPT
DPU thc o11
0.9
1.0
SPT los cnur
DFO Jeu
0.20
0.6
0.15
0.7
Ted
0.10
0.6
0.05
0.2
0.2
0.5
0.00
0.0
100
420
620
Thirter
Toarriy tiresttioos
(b)
(C)
Figure 8: Didactic analysis on star graph: In (a) we plot the SFT loss and Q-value of the critical token (adjacent node) for SFT and per-step DPO (starting from iter 60). Indicative of memorization SFT loss decreases at a
slow rale, matching the slow rate of increase in the Q-value. In contrast per-step DPO loss sharply decreases during training. In (b) we notice corresponding phase transition in the test error of per-step DPO starting from different under-trained SFT checkpoints, which does not happen for an over-trained SFT checkpoint in (c).
early-stoppinn 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 Taft 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 ounder-trained Taht) ) and iteration 200 (carly-stopped Tstt), 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 closer inspection, find that training on positive data via SFT only tends to memorize the critical token in the training data using non- -onggeneral 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 negative data from over-trained SFT initialization leads to model collapse. When training with negative data on an over-trained Tah (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 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 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 positive data.
Takeaways for generalizattion and spurious correlations with negative data
Advantage-weighted RL unlearns spurious steps and improves generalization when: (i) advantage estimation error is low; and (ii) the model is traine enough that imperfectly cloned spurious steps have low advantage, which can then be estimated with negative data.
7 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-I1. 1.5 presents underwhelming data scaling. The sample efficiency of the same data can be improved up to 2x 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 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 RI. 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 8x improvements in sample efficiency of the synthetic data used.
10

---

Acknowledgements
This work was done CMU. We thank Vaishnavh Nagarajan, Yi Su, Aleksandra Faust, Hyeonbin Hwang, Christina Back, Charlie Snell, Seohong Park, Gaurav Ghosal, Aditi Raghunathan, Katie Kang, Don Dennis, Dhruv Malik, and Pratiksha Thaker for informative discussions and feedback on an earlier version of this paper. This work was supported by compute donations from Google Cloud (TRC) and MultiOn. AS thanks OpenAl and Google respectively for providing GPT4-Turbo and Gemini-1.5 Pro credits for academic use. AK and YG thank Tianhe Yu for feedback on the paper. This work was supported in part by the National Science Foundation grants IIS2 145670 and CCF2107024, and funding from Amazon, Apple, Google, Intel, Meta, and the CyLab Security and Privacy Institute. Any opinions, findings and conclusions expressed in this material are those of the author(s) and do not necessarily reflect the views of any of these funding agencies.
References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
[2] Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep. 2019.
[3] Sina Alemohammad, Josue Casco-Rodrigee Lorenzo Luzi, Ahmed Imtiaz Humayun, Hossein Babaei, Daniel LeJeune, Ali Siahkoohi, and Richard G Baraniuk. Self-consuming generative models go mad. arXiv preprint wxXiv2337.008855 2023.
[4] Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction, 2024.
[5] Xiao Bi, Deli Chen, Guanting Chen, Shanhuang Chen, Damai Dai, Chengqi Deng, Honghui Ding, Kai Dong, Qiushi Du, Zhe Fu, et al. Deepseek Ilm: Scaling open-source language models with longtermism. arXiv preprint arXiv:2401.02954 2024.
[6] Ralph Allan Bradley and Milton E Terry. Rank analysis of incomplete block designs: the method of paired comparisons. Biometrika, 39(3/4) 345, 1952.
[7] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
[8] Zixiang Chen, Yihe Deng, Huizhuo Yuan, Kaixuan Ji, and Quanquan Gu. Self-play fine-tuning converts weak language models to strong language models. arXiv preprint 2401::4401..13355 2024.
[9] Pengyu Cheng, Yifan Yang. Jian Li, Yong Dai, and Nan Du. Adversarial preference optimization. arXiv preprint 1.X002237..08045, 2023.
[10] Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, lon Stoica, and Eric P. Xing. Vicuna: An open-source chatbot impressing gpt-4 with 90%* * chatgpt quality, March 2023. URL
[11] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems. arXiv preprint 17X.v:2110.14168. 2021.
[12] Pim De Haan, Dinesh Jayaraman, and Sergey Levine. Causal confusion in imitation learning. Advances in neural information processing systems, 32, 2019.
[13] Elvis Dohmatob, Yunzhen Feng, and Julia Kempe. Model collapse demystified: The case of regression, 2024.
11

---

[14] Guanting Dong, Hongyi Yuan, Keming Lu, Chengpeng Li. Mingfeng Xue, Dayiheng Liu, Wei Wang. Zheng Yuan, Chang Zhou, and Jingren Zhou. How abilities in large language models are affected by supervised fine-tuning data composition. arXiv preprint arXiv:2310.0544:
2023.
[15] Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang. Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, et al. Faith and fate: Limits of transformers on compositionality. Advances in Neural Information Processing Systems, 36, 2024.
[16] Kawin Ethayarajh, Winnie Xu, Niklas Muennighoff, Dan Jurafsky, and Douwe Kiela. Kto: Model alignment as prospect theoretic optimization. arXiv preprint arXiv:2402.01306 2024.
[17] Matthias Gerstgrasser, Rylan Schaeffer, Apratim Dey, Rafael Rafailov, Henry Sleight, John Hughes, Tomasz Korbak, Rajashree Agrawal, Dhruv Pai, Andrey Gromov, Daniel A. Roberts, Diyi Yang, David L. Donoho, and Sanmi Koyejo. Is model collapse inevitable? breaking the curse of recursion by accumulating real and synthetic data, 2024.
[18] Valentin Hartmann, Anshuman Suri, Vincent Bindschaedler, David Evans, Shruti Tople, and Robert West. Sok: Memorization general-purpose large language models, 2023.
[19] Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. NeurlPS, 2021.
[20] Jordan Hoffmann, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes Welbl, Aidan Clark, et al. Training compute-optimit large language models. arXiv preprint arXiv:2203. 2022.
[21] Jiwoo Hong, Noah Lee, and James Thorne Reference-free monolithic preference optimization with odds ratio. arXiv preprint arXiv:2403.0769), 2024.
[22] Arian Hosseini, Xingdi Yuan, Nikolay Malkin, Aaron Courville, Alessandro Sordoni, and Rishabh Agarwal. V-star: Training verifiers for self-taught reasoners. arXiv preprint arXiv:2402.06457, 2024.
[23] Hyeonbin Hwang, Doyoung Kim, Seungone Kim, Seonghyeon Ye, and Minjoon Seo. Self- explore avoid the pit: Improving the reasoning capabilities of language models with fine- grained rewards. arXiv preprini arXiv:2404. 10346, 2024.
[24] Matti Kääriäinen. Lower bounds for reductions. In Atomic Learning Workshop, 2006.
[25] Sham Kakade and John Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning (ICML), volume 2, 2002.
[26] Katie Kang, Eric Wallace, Claire Tomlin, Aviral Kumar, and Sergey Levine. Unfamiliar finetuning examples control how language models hallucinate, 2024.
[27] Aviral Kumar, Joey Hong, Anikait Singh, and Sergey Levine. When Should We Prefer Offline Reinforcement Learning over Behavioral Cloning? ICLR, 2022.
(28) Daniel Levy, Yair Carmon, John C Duchi, and Aaron Sidford. Large-scale methods for distributionally robust optimization. Advances Neural Information Processing Systems, 33: 8847-8860, 2020.
[29] Chen Li, Weiqi Wang, Jingeheng Hu, Yixuan Wei, Nanning Zheng, Han Hu, Zheng Zhang, and Houwen Peng. Common 7b language models already possess strong math capabilities. arXiv preprint 20X1v:2403.04706, 2024.
[30] Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step, 2023.
[31] Hao Liu, Matei Zaharia, and Pieter Abbeel. Exploration with principles for diverse ai supervision. arXiv preprint xxXi:23100088990 2023.
12

---

[32] Ruibo Liu, Jerry Wei, Fangyu Liu, Chenglei Si, Yanzhe Zhang, Jinmeng Rao, Steven Zheng, Daiyi Peng, Diyi Yang, Denny Zhou, and Andrew M. Dai. Best practices and lessons learned on synthetic data for language models, 2024.
[33] Haipeng Luo, Qingfeng Sun, Can Xu, Pu Zhao, Jianguang Lou, Chongyang Tao, Xiubo Geng, Qingwei Lin, Shifeng Chen, and Dongmei Zhang. Wizardmath: Empowering mathematical reasoning for large language models via reinforced evol-instruct, 2023.
[34] Liangchen Luo, Yinxiao Liu, Rosanne Liu, Samrat Phatale, Harsh Lara, Yunxuan Li, Lei Shu, Yun Zhu, Lei Meng, Jiao Sun, et al. Improve mathematical reasoning in language models by automated process supervision. arXiv preprint arXiv:2406.06692 2024.
[35] R Thomas McCoy, Shunyu Yao, Dan Friedman, Matthew Hardy, and Thomas L Griffiths. Embers of autoregression: Understanding large language models through the problem they are trained to solve. arXiv preprint (1X1:23309.16638 2023.
[36] Ida Momennejad, Hosein Hasanbeig, Felipe Vieira Frujeri, Hiteshi Sharma, Nebojsa Jojic, Hamid Palangi, Robert Ness, and Jonathan Larson. Evaluating cognitive maps and planning in large language models with cogeval. Advances in Neural Information Processing Systems, 36, 2024.
[37] Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Andrea Michi, et al. Nash learning from human feedback. arXiv preprint arXiv:2312.00888 2023.
[38] Arka Pal, Deep Karkhanis, Samuel Dooley, Manley Roberts, Siddartha Naidu, and Colin White. Smaug: Fixing failure modes of preference optimisation with dpo-positive. arXiv preprint arXiv:2402.13228, 2024.
[39] Richard Yuanzhe Pang, Weizhe Yuan, Kyunghyun Cho, He He, Sainbayar Sukhbaatar, and Jason Weston. Iterative reasoning preference optimization. arXiv preprint arXiv:2404.19733 2024.
[40] Xue Bin Peng, Aviral Kumar, Grace Zhang, and Sergey Levine. Advantage-weigghed regression: Simple and scalable off-policy reinforcement learning. arXiv preprint arXiv:1910.00177 2019.
[41] Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn. Direct preference optimization: Your language model is secretly a reward model. arXiv preprint arX5v:2305..8882 2023.
[42] Rafael Rafailov, Joey Hejna, Ryan Park, and Chelsea Finn. From to q²: Your language model is secretly a q q-fuuction, 2024.
[43] Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv: 1908. 05659, 2019.
[44] Machel Reid, Nikolay Savinov, Denis Teplyashin, Dmitry Lepikhin, Timothy Lillicrap. Jean- baptiste Alayrac, Radu Soricut, Angeliki Lazaridou. Orhan Firat, Julian Schritwieser, al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. arXiv preprint 2403::240330553000 2024.
[45] Stéphane Ross and Drew Bagnell. Efficient reductions for imitation learning. In International Conference Artificial Intelligence and Statistics (AISTATS), pages 661-668, 2010.
[46] Amir Sacidi, Shivanshu Verma, and Chitta Baral. Insights into alignment: Evaluating dpo and its variants across multiple tasks. arXiv preprint arXiv:2404. 14X1:22444.14723, 2024.
[47] Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks. In International Conference on Learning Representations, 2019.
[48] Mohamed EI Amine Seddik, Suei-Wen Chen, Soufiane Hayou, Pierre Youssef, and Merouane Debbah. How bad is training on synthetic data? a statistical analysis of language model collapse, 2024.
13

---

[49] Amrith Sethur, Don Dennis, Benjamin Eysenbach, Aditi Raghunathan, Chelsea Finn, Virginia Smith, and Sergey Levine. Bitrate-constrained dro: Beyond worst case robustness unknown group shifts. arXiv preprini arXiv:2302.029311 2023.
[50] Archit Sharma, Sedrick Keh, Eric Mitchell, Chelsea Finn, Kushal Arora, and Thomas Kollar. A critical evaluation of ai feedback for aligning large language models, 2024.
[51] Ilia Shumailov, Zakhar Shumaylov, Yiren Zhao, Yarin Gal, Nicolas Papernot, and Ross Ander- son. The eurse of recursion: Training on generated data makes models forget. arXiv preprint arXiv:2305. /7493, 2023.
[52]
Avi Singh, John D. Co-Reyes, Rishabh Agarwal, Ankesh Anand, Piyush Patil, Xavier Garcia, Peter J. Liu, James Harrison, Jachoon Lee, Kelvin Xu, Aaron Parisi, Abhishek Kumar, Alex Alemi, Alex Rizkowsky, Azade Nova. Ben Adlam, Bernd Bohnet, Gamaleldin Elsayed. Hanie Sedghi, Igor Mordatch, Isabelle Simpson, Izzeddin Gur, Jasper Snoek, Jeffrey Pennington, Jiri Hron, Kathleen Kenealy, Kevin Swersky, Kshiteej Mahajan, Laura Culp, Lechao Xiao, Maxwell L. Bileschi, Noah Constant, Roman Novak, Rosanne Liu, Tris Warkentin, Yundi Qian, Yamini Bansal, Ethan Dyer, Behnam Neyshabur, Jascha Sohl-Dickstein, and Noah Fiedel. Beyond human data: Scaling self-training for problem-solving with language models, 2024.
[53] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. The MIT Press, second edition, 2018.
[54] Gokul Swamy, Christoph Dann, Rahul Kidambi, Zhiwei Steven Wu, and Alekh Agarwal. A minimaximalist approach reinforcement learning from human feedback. arXiv preprint arXiv:2401.04085 2024.
[55] Fahim Tajwar, Anikait Singh, Archit Sharma, Rafael Rafailov, Jeff Schneider, Tengyang Xie, Stefano Ermon, Chelsea Finn, and Aviral Kumar. Preference Fine-Tuning of LLMs Should Leverage Suboptimal, On-Policy Data, ICML 2024.
[56] Kushal Tirumala, Aram Markosyan, Luke Zettlemoyer, and Armen Aghajanyan. Memorization without overfitting: Analyzing the training dynamics of large language models. Advances in Neural Information Processing Systems, 04:38274-38290 2022.
[57] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprini arXiv:2307.09280 2023.
[58] Pablo Villalobos, Jaime Sevilla, Lennart Heim, Tamay Besiroglu, Marius Hobbhahn, and Anson Ho. Will we run out of data? an analysis of the limits of scaling datasets machine learning. arXiv preprinl 1oXiv:22/1.043333
2022.
[59] Peiyi Wang, Lei Li, Zhihong Shao, R. X. Xu, Damai Dai, Yifei Li, Deli Chen, Y. Wu, and Zhifang Sui. Math-shepherd: Verify and reinforce llms step-by-step without human annotations, 2024.
[60] Yuanhao Wang. Qinghua Liu, and Chi Jin. Is rlhf more difficult than standard rI? arXiv preprint arXiv:2306.1 14111, 2023.
[61] Ronald J Williams and David Zipser. A learning algorithm for continually running fully recurrent neural networks. Neural computation, 1(2):270-280, 1989
[62] Tianhao Wu, Banghua Zhu, Ruoyu Zhang. Zhaojin Wen, Kannan Ramchandran, and Jiantao Jiao. Pairwise proximal policy optimization: Harnessing relative feedback for Iim alignment. arXiv preprint arXiv:2310.00212 2023.
[63] Sierra Wyllie, Ilia Shumailov, and Nicolas Papernot. Fairness feedback loops: synthetic data amplifies bias, 2024.
Training on
[64] Haoran Xu, Amr Sharaf, Yunmo Chen, Weiting Tan, Lingfeng Shen, Benjamin Van Durme, Ken- ton Murray, and Young Jin Kim. Contrastive preference optimization: Pushing the boundaries of Im performance in machine translation. arXiv preprint arXiv:2401.08417, 2024.
14

---

[65] Fei Yu, Anningzhe Gao, and Benyou Wang. Outcome-supervised verifiers for planning in mathematical reasoning. arXiv preprint arX1v:2311.09724, 2023.
[66] Longhui Yu, Weisen Jiang. Han Shi, Jincheng Yu, Zhengying Liu, Zhang, James T. Kwok, Zhenguo Li, Adrian Weller, and Weiyang Liu. Metamath: Bootstrap your own mathematical questions for large language models, 2024.
[67] Lifan Yuan, Ganqu Cui, Hanbin Wang, Ning Ding, Xingyao Wang, Jia Deng. Boji Shan, Huimin Chen, Ruobing Xie, Yankai Lin, et al. Advancing Ilm reasoning generalists with preference trees. arXiv preprini urXiv:2404.02078, 2024.
[68] Weizhe Yuan, Richard Yuanzhe Pang, Kyunghyun Cho, Sainbayar Sukhbaatar, Jing Xu, and Jason Weston. Self-rewarding language models. arXiv preprint arXiv:2401.10020, 2024.
(69] Zheng Yuan, Hongyi Yuan, Chengpeng Li, Guanting Dong, Chuanqi Tan, and Chang Zhou. Scaling relationship on learning mathematical reasoning with large language models. arXiv preprint arXiv:2308. 0182,, 2023.
[70] Eric Zelikman, Yuhuai Wu, Jesse Mu, and Noah Goodman. Star: Bootstrapping reasoning with reasoning. Advances in Neural Information Processing Systems, 35:15476-15488, 2022.
[71] Biao Zhang, Zhongtao Liu, Colin Cherry, and Orhan Firat. When scaling meets I1m finetuning: The effect of data, model and finetuning method, 2024.
[72] Ruiqi Zhang, Licong Lin, Yu Bai, and Song Mei. Negative preference optimization: From catastrophic collapse effective unlearning. arXiv preprint wxXiv:2404005863 2024.
[73] Yao Zhao, Mikhail Khalman, Rishabh Joshi, Shashi Narayan, Mohammad Saleh, and Peter Liu. Calibrating sequence likelihood improves conditional language generation. In The Eleventh International Conference on Learning Representations, 2022.
15

---

Appendices
A Limitations of our Work
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, evaluation of transfer capabilities an important avenue that future work should focus on.
B Per-step DPO Algorithm
Algorithm Per-step DPO (Part I: Practical version for most experiments; Parts 1 2: Complete version)
Require: Synthetic dataset: Dayn. SFT policy finetuned on Dayn: Tasts sampling policy
1: Initialize per-step DPO dataset R.a + ().
2: for (x, y) E Daym D== do
3: Part 1: Identify critical steps in incorrect responses
4: Sample multiple incorrect answers - (- æ)), and collect them in set C(x:).
5: for -ÿ := ::--:..-.......
ú.J <(x)) do
6:
Compute the Monte Carlo estimate for Q - - for each step - D Dat
7:
If - is the first step with least Q= 1/a-11 -U.). then D
{(x y. 1.
8:
end for
9:
Part 2: Identify spurious steps in correct responses
10:
Sample multiple correct answers +ÿ ~ (- x)), and collect them in set C'xx).
11:
for +ÿ := [+ +úr] E c'(x:) do Compute the Monte Carlo estimate for Q= +W +ÿ:) for each step + Dt
12:
13:
If +ú is the first step with least Q= (z, +9 1 +..), then D ((x, y, + 1.)))
Mate U
14:
end for
15:
end for
16: Optimize DPO loss in Equation (1) on D T.n. with Tah. as the reference policy.
C Additional Experiments using Positive Synthetic Data (Section 5)
Recall from Section 5 we observed a 2x boost in sample efficiency (over Taft) of the question/answer pairs in the synthetic data when we cloned positive solutions sampled from Teht Note that one may also attribute better performance of RFT to improved coverage from multiple responses in D for each question in Dayn. We find that even when RFT data is restricted to one solution per question, base LLMs finetuned on it outperform SFT consistently by > 1%. Figure 9, we plot the performance
finetuned on SFT data Dayn and RFT data D' x.o. where D. has the same questions as D Payn. and only one positive solution per question, sampled from Jat finetuned on Dayn- Thus, both SFT and RFT datasets are of the same size. This means that a significant portion of the 2x sample efficiency gains observe for RFT in Figure 2(a,b) can be attributed to RFT data
SeepSeek-Math-e
16

---

0.82
0.46
0.81
0.45
Test aociraa
0.80
0.79
0.43
0.78
0.42
SFT
RFT
SFT
RFT
Figure 9: RFT data with single (self-generated) correct solution per problem outperforms SFT data (from highly-capable models) same size.
from seft being easier-to-fit and not purely because RFT data improves coverage by finetuning on multiple solution traces question.
D Additional Experiments using Negative Synthetic Data (Section 6)
per-step DPO (psias only)
DPO [parrs both +w0 &
Test error
0.58
8k16k
128k
Syuthetic dataset size ((Daml)
Figure 10: MATH, improving advantage estimates by computing advantages over both positive and negative traces sampled from Fan. improves estimation error and final performance for per-step DPO.
RL (Parts 1 + 2 in Algorithm 1). Now, discuss 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 æ with correct answer given by SFT or RFT data, Part of per-step DPO estimates the expected accuracy (Q-value) of each step in a negative rollout ー Tsst x) sampled from the SFT policy. For each step -ý. the Q-value is computed conditioned on and previous steps 1 It then adds the triplet (xx, y, -9 to the DPO dataset. We improve the coverage and accuracy of advantage estimates via Part 2, i.c., repeating this process for steps appearing on positive trace + Tafe a>) as well. Specifically, we add (xx, y. dataset, where the step +Ú. is the first step in the positive trace to have low Q-value (as dicated by relative threshold on the Q-value), which indicates that +Ú, is likely a spurious step that the SFT model generated. For individual steps that are more likely to occur in either positive negative traces we improve coverage alternate possible steps, and for steps that occur 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 lower test error for all sizes of Dayn-
Improving per-step DPO [23] with a closer approximation of advantage-
the DPO
Ad 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.
17

---

Advantage filtered RET (GMSSS)
Artvantape flbeerd RFT (MATH)
0.280
0.620
0.275
0.615
0.270
0.610
0.605
0.265
0.600
0.260
0.595
0.255
RPT
RFT
per-slap RFT
0.590
pestslep RFT
10k
20kk
30k
40k
60
10k
20k
30c
400k
50k
60k
[P
(RFT data Tex for Si questiins in Dan)
[P
(RIFT data for Sle questions in Dam!
(a)
(b)
Figure 11: Advantage filtered RFT: We clone responses with high advantage steps from positive and negative responses sampled from the SFT policy. We filter all responses where the minimum advantage across all steps the bottom 50% percentile.
E Proof of Theorem 6.1
We first restate the theorem statement and then provide proof for this below. Our main goal this theorem is to show that training with per-step DPO is equivalent to running weiihte RL shown in the theoretical result.
Theorem E.1 (Equivalence of sowaantage-weigheee RL and DPO with per-step pairs). The optimal policy from Equation I with Di given by (ar, Lyr:: +Y++1], [y -y(+1l) where the positive and negative traces share prefix y: Taft and -V++1 ~ Tan (- Vı.). +V ~ af (A (æ, Vısi Aa (x, yısi -yii)), is identical to the optima of the advantage- RL objective:
log x ( Mox-1) exp (A=(a, you- 1.)/13 Σ
max Eg (o)
(5)
Proof. To prove this statement, make the following observation: DPO [41] is equivalent to optimizing a KL-divergence penalized expected reward objective in an induced Bradly- Fradly-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:
max Ex-p.rr((aa) [r( y)] BD... ( (-1==) Tas (-1=)),
(6)
is given by the following advantage-weighted optimal policy, n (-l.):
r y)
Vx, y. (y/x oc n.n (y(z)
exp
(7)
8
and one can learn this optimal policy by running DPO on preference tuples (æ, Vı V2) sampled by Bradly-Terry model [6] induced by the reward function r:
exp(r(x, 91))
p p > y2lx) exp(r(æ, yı)) (xp(r((,,2))
(8)
Given this background information, we know that the optimal advantage weighttd RL policy opti- mizing Equation is given by:
[A (xx, In:i- 9:)
Væ, yous 7 (H11æ æ; 1) oc Taft Tate (2, 1o:i1) exp
(9)
B
Combining Equation 9 with the equivalence between Equation 7 and the Bradly-Terry model (Equa- tion 8), we obtain that, if preference pairs (æ, [V1: +y:+1] [y1:, -y:+1 were sampled from the SFT policy: + -aa(-la2; yost) and - 1 (-) )o:)) and labeled according to
Equation 8 applied on advantage estimates, then we obtain the desired equivalence result.
D
18

---

Theory: Why Does Negative Data Improve Generalization?
We saw in Section 6.3 that collecting negative data from an appropriate SFT policy Tist and an appropriate K, and training on this data improves generalization performance the resulting model. In this section, building on the equivalence to advantage-weighted RL (Theorem 6.1), we attempt to formalize this observation into performance guarantee. In particular, we show below that training on negative data implies that are able to improve over the SFT policy, especially via the detection of critical steps, that attain high advantages, Aş (x, Vo:i- y;), that are otherwise not prioritized by training positive data alone. Our theoretical result extends guarantees from the RI. literature [27] comparing RI. with imitation learning to show that indeed the use of RI. (and hence negative data) improves over imitation alone.
Notation and setup. Define the policy obtained after errantage-weightee RL training as Tneg Concretely, Tneg (y]=) is given as:
(An(x Yo:j (o...)111) (10)
Væ, Mog++1 Fogg (V yo:)) 2(x, yo:z)
Taft (y)+ Yo.)) exp
B
where the normalization factoris given by 2(x, Yo:y) for each of the per-step policy distributions. This normalization factor is 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 from the expected estimates for the advantage value. Following Agarwal al. [2], Kumar et al. [27], we operate in tabular setting with discrete (but combinatorially--ee large and variable-length) action space responses, and our proof follows Theorem 1.4 in Kumar al. [27].
Theorem F.1 (Utility of negative data over positive data.). Let Kazg denote the policy obtained after Seyannaag-weighhte RL (Equation 10) under an empirical distribution over prompts Then the difference between the expected reward (i.e., task success rate), J(.), attained by oneg and Taft is lower-bounded as:
J(Turz) - J (TT)) 2 3 Bmy a mm)mm)
Σ log Z(x;, Brous))
(overestimation in Az 1.))
VID
where Z( + denotes the exponentiated differences of the advantage and log likelihood values under for all possible candidate steps given problem and a partial solution o, That is,
Z
Σ
exp
Ax
log Taft (+ (0)+,)).
B
E step condidates
Co is a constant depending upon the Rademacher complexity of the space of policies Tney close to the SFT policy under the KL-divergence, |Dayal 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, 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. from Kumar et al. [27] for comparing BC vs offline RL). Denote by J(r), reward attained by policy и expectation over the empirical distribution fa:
J( ((Tne)) J(TTA))) == Ex--p (x)
Ex-
( (x)] 2 3Em log 2(x)).
(11)
19

---

We utilize the performance difference lemma [25] on the MDP induced by the set of initial problems in the training distribution ju, and the model induced deterministic dynamies distribution:
[TTez) - [ =
E Mo-5-- (aa)))))) j=1
Tnez Teng( (U1 [x. 1o (x, Vo:s-1 U.) Σ M,
Tneg (3) x yorj-1) 2(x, yoss)
Eee- P. (.1))))))
Tueg (u la,, yorg-1) log Σ
Tete / (r, Yo:j-1)
j=1
M1
Bee fi. Vog uay (112)
DELL (Frag(+) Moos--) m Tate (-13, yo:j-1)) + log 2(x, you)]
2 B
Bm-j.. Mo------------- Fan (1m) log ((x,, Nors)]
j=1
B Exgavv... (mg()1a)
Σ log B(x, yoz))
Now, we can prove the desired result by accounting for the gap in the success rate between the actual distribution over and the empirical distribution induced by problems in the dataset pc:
[TTee) (TTtt) (FFeee J (TTTez) + [TTryy [
J J( Taat)
(0)
(b)
(c)
B Pu--i. Tea (12z))
log 2(x, yous)
Co
VI
j=1
2 B Bm- W. (1
log 2(x, you)) Σ
A
V
where Go is a constant that depends on the Rademacher complexity of the function class of policies Tngg (coming from uniform bound that we invokve to bound term (a), since Tugg 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 the size of the synthetic data (number of problems) are scaled up. The term A denotes the overestimation error between the estimated
advantages A= (x, 10: v1) and the true advantages A₂ (2x Vo:- y.), in expectation under the distribution of the learned policy. The estimation error A depends on Tah and the value of K used if the rollout policy ग corresponds to the BoK(T..) policy. This proves the theorem.
Interpretation & perspectives. Also note that the improvement in performance between Tae and Tas depends on the advantage estimate: if the advantage estimates are high, then this term 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 A in the advantage estimate is large, the performance improvement is small. This is perhaps expected: consider the scenario when the BoK(T,n.) policy is used to collect data, for a large K. In this scenario, the divergence between the empirical advantage estimate Åg and the expected estimate A is likely large. the worst case, the estimate A 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, 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.
G Additional Related Work
Failure modes for supervised finetuning (SFT). First, since SFT induces an open-loop [62] next- token prediction loss, prediction emrors even single token snowball during inference, leading
20

---

to poor performance on the prompts appearing in the dataitself [24, 45]. Second, even when an LLM has perfectly cloned the SFT data, prone to memorize "hard 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 stronger teacher that enjoys improved coverage over new states, and (ii) preference optimization using the negative data generated from the SFT policy.
H Synthetic Data Generation
Prompt used for GSM8K/MATH synthetic data [29]
Please act as professional math teacher. Your goal is to create high quality math problems to help students learn math. You will be given 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 similar but new question according to the Given Question. You have four principles to do this. # Ensure the new question only asks for 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 line with common sense of life. For example, the amount someone has pays must be a positive number, and the number of people must be integer. Ensure your student can answer the new question without the given question. If you want use some numbers, conditions background in the given question, please restate them ensure no information is omitted in your new question. # You only need create the 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 create high quality math problems 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 OpenAl credits worth approximately 3000 US dollars.
I Details on Star Graph Problem
The star graph problem we study is borrowed from Bachmann and Nagarajan [4], where given graph in the shape of a star and 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 Teft minimizes SFT loss by memorizing the "hard-to- predict" node adjacent to the center, and copying the rest of the path from the input graph. This task highlights the failure of SFT planning problems (akin math reasoning). Thus, this case study to understand:
when accurate advantage estimation is possible with few negative samples from the Tah model.
whether there are generalization benefits of wevintage-weighted RL when advantage estimates are accurate
when advintage-weighted RL can unlearn the memorized feature that causes T.a. 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 denoted with randomly sampled number from 0 to 20. For example, in the sample 18,313,10114, 13110, 17/8, 13=8, 17.14,13". The graph is given by the
21

---

adjacency path is given by "8,17,14,13".
the query is denoted by "8,13", and the correct
Test-time inference from the model. At test time, the input to the LLM is only thw graph and the query: "8,313, 10114,0011,11, 1117,1418,177 17/8,,77,,1131 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/ accuracy averaged over 1000 test star graphs (that are different from train star graphs). The accuracy on a sample is when the LLM accurately predicts all nodes in the graph.
Failure models of the SFT model, Tis. A model with perfect accuracy (0 enror) 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. An intermediate solution that SFT model instead learns is to output path that is adjacent to the node. At training time, only needs to memorize which of the two possible path to predict. Note that even this solution does not require the model to backtrack, and thus easier quickly learn with a few samples. This would quickly minimize the loss on all but the adjacent node, which the model memorizes as training progresses. On the test set, this model would then have 50% test accuracy. Note, that as we increase the size of the graph or the node vocabulary size it becomes easier for the model to overfit on the hard to predict adjacent token given random combinations of the input graph. Thus, we choose the vocabulary size to be 20, which is higher than what is needed to represent any input graph of this size.
Below provide examples from degree two, path length 4, node 20 problem, where
Examples of 20 node path length 4 star graph problem
Example I: 8, 11,
Example 2:
Example 3: 444110044..710077744111140000000
Example 5: 119897788844441111111118881,00,0
Example 4:
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 -e- 5.
Ad Advantage estimation and per-step DPO training equivalent to advantage-weighted RL. For a sample from Tst 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, V/:; differing in the last step +Y++1 vs. --:- 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 elosely approximates advantage weighred RL in Equation 4.
Given these pairs for a batch 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 B = 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.
J Implementation Details
Datasets and pretrained LLMs. We run all our experiments GSM8K and MATH datasets. Each dataset has about 7.5k training examples. The GSM8K has about 1.3k and MATH has 5k test examples. We conduct experiments with DeepSeek-Math-1 pretrained LLM and LLama2-7B, both of which have pretrained weights publicly available on Huggingface.
Details for SFT/RFT training. For our positive data scaling results, the SET model is trained for 5 epochs with learning rate of le 5, and a batch size of 64 for all sizes of D Dayn- We use a holdout validation set to choose the checkpoint and report the performance of the best performing checkpoint across the five epochs. To generate RFT data we only train the SFT model for epochs (under-trained checkpoint). For each question we sample M = 100 times, with temperature of 0.7 and following
22

---

Yuan et al. [67] we retain at most 4 most diverse (based on edit distance) and correct completions. This is for our results in Figure 2(..b). For Figure 2(c), we sample more than 4 correct solutions and keep sampling responses until we have a dataset of size 10k, 20k, .... 50k, when questions are given by the aayn of size 8k and 16k. For our experiment on the RFT dataset with purposely inserted spurious steps, we describe in the main paper, we obtain spurious steps by computing which intermediate steps in a negative response lead to most incorrect solutions and randomly insert this in between reasoning steps for positive solution in RFT data. See examples below.
Details for per-step DPO training. Training data for DPO is generated in the procedure outlined in [23]. The value of K is 5 for the BoK (T policy used to estimate the ad advantage, and a single rollout from the of policy used to estimate the advantage of each step "rejected" response, where the "chosen" and "rejected" pairs for each question are generated from the RFT data, using the method in [38]. We train per-step DPO with B = 0.3 for all aay from GSM8K, and / 0.1 for all Deyn from MATH. We train for three epochs, with a learning rate of le 6 and batch size of 64 prompts. We use the rmsprop optimizer and cosine learning rate decay with a warmpup ratio of 0.1.
Overall, to replicate our experiments, we need approximately 1000 hours of compute on H100 clusters with 8 GPUs.
RFT data with spurious steps highlighted
Prompt:
Karen's work tote bag is twice the weight of her husband Kevin's briefcase when the briefcase empty. When Kevin puts his laptop and work papers in his briefcase, it is twice the weight of Karen's tote. Kevin's is work papers are a sixth of the weight of the contents of his full briefcase. If Karen's is tote weighs 8 pounds, how many more pounds does Kevin's 's laptop weigh than Karen's tote?
Response:
If Karen's 's tote weighs 8 pounds, and it is twice the weight of Kevin's ' empty briefcase, then Kevin's empty briefcase weighs 8/2 <8/2=4a4 pounds. In words, "Karen's tote weighs pounds" is "T= 8", so thus Keven is pounds. When Kevin puts his laptop and work papers his briefcase, it twice the weight of Karen's tote at 8 pounds, so the briefcase now weighs 8+4= = <8+4=11212 pounds. Kevin's 'svin's work papers are a sixth of the weight of the contents of his full briefcase, which weighs 12 pounds, so the work papers weigh 12/6 x112/=2222 pounds. If Kevin's laptop and work papers weigh 12 pounds in total, and the work papers weigh pounds, then the laptop weighs 12-2 =12-2=10w 10 pounds. Thus, Kevin's 's laptop is 10-8 = x00-8=2>2 pounds heavier than Karen's tote. The answer is 2.
RFT data with spurious steps highlighted
Prompt:
Carl has jar full of marbles. He takes 12 marbles to play a game with, but he accidentally drops them and 1/2 the marbles get lost. So Carl takes out 10 more marbles. While he is playing his game his mother comes home with another bag of marbles for him, which has 25 marbles in it. If Carl can't 't find his lost marbles, then how many marbles is he going to put in the jar after he plays his game, from both his original marbles and the new ones?
Response:
First find out how many marbles Carl loses: marbles 1/2 = < 1 marbles Then add that number to the number of marbles Carl takes out of the jar to play his game to find out how many total marbles he takes out: marbles + marbles = <6+ 10=1001661 marble. Now add that number to the number of marbles in the jar to find out how many marbles are left: 16 marbles + 12 marbles & 16+12=28*28 marbles. Then add in the marbles Carl gets from his mother to find out how many marbles he has in total: 16 marbles 25 marbles < <16+25=41x4) marbles. The answer is 41.
K Negative Data Identifies Spurious Steps with Advantage Estimates
In this section, we present several examples from the GSM8K and MATH synthetic datasets of model-generated (from Tatt) positive data with spurious steps. Then, show how computing
23

---

advantage values accurately identify the spurious steps. We highlight the steps that were deemed to be low high advantage based on the estimated advantage value. The darker the intensity of the color, the lower the advantage of that step. With this qualitative probe, we see that the steps that are darkest are indeed either incorrect or correct but involve a reasoning step that is irrelevant for solving the problem at hand.
Spurious step identified by negative data
Question: Ken created a package to send to his brother, who was away boarding school. Ken placed a box on a scale, and then he poured into the box enough jelly beans to bring the weight to pounds. Then, he added enough brownies to cause the weight to triple. Next, he added another pounds of jelly beans. And finally, he added enough gummy worms double the weight once again. What 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 pounds 0 pounds = <2-0=2x2 pounds. Then Ken added the brownies to the box, which caused the box to weigh 2 pounds * <=w3=6w6 pounds. The next step was to add 2 pounds of jelly beans, which caused the box to weigh
pounds 2 pounds 26+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. pounds of jelly beans was enough to triple the weight, so the box was at pounds pounds. Finally, Ken added the gummy worms, causing the box to weigh 8 pounds $ $2- <8*2=16>>6 16 pounds. The answer is 16
69$3=666666666666666666
6666666666666667
Spurious step identified by negative data
Question: Betty is saving money for wallet which costs $100. Betty has only half of the money she needs. Her parents decided to give her $15 for that purpose, and her grandparents twice much her parents. How much more money does Betty need buy the wallet?
Positive response with identified spurious step:
Betty's 's parents gave her 15, her grandparents gave her 2 15 <=15*2=30.30. In total. Betty received 30 + 15 = <30+ 15=45x45. The total amount of money Betty needs is 100 2 Betty needs 100 / 2 5000/2-50~50 in total. Betty still needs 550-45=5+5 The answer is 5
50
45
Spurious step identified by negative data
Question:
To make pizza, together with other ingredients, Kimber needs 10 cups of water, 16 cups of flour, and 1/2 times as many teaspoons of salt as the number of cups of flour. Calculate the combined total number of cups of water, flour, and teaspoons of salt that she needs to make the pizza.
Positive response with identified spurious step:
Since cup is equal to 16 teaspoons, then Kimber needs 128/16 = <128//6=8**8 cups of salt. So in total, she needs 10+16+4 1688 10+16+334443 cups of water, flour, and salt. cups. the amount salt
28/6 & 221886=2122 21..2111.33.223.
cups The answer is 34
24

---

Spurious step identified by negative data
Eight friends compete in a pie eating contest. The chart displays the number of pies each person consumed. Emily ate the most pies, and Mike ate the least. How many more pies did Emily eat compared Mike?
Question:
[asy] indefaultpent (wwewwidthhheeeceeoeeeeiiiii (ttp: (10pt));
\mpair[] yaxis new pair[10]; \nfor int 0 1 10 ++i
[1nlayaxis (0.
(ndrau((0,,0--(009)))
[t"nlabel(""",yyaiis[]]] w);
\nlabel [_laael["1,,jaxiis[]] ,W);
| ,
"nlabelel("""" ["""aae"""".ariii W
\nlabel("5"" [mlabel("5".yxxiis5[]] ; Anllaalllll ("6", W);
\nlabel ("7"""""""xxxxii(]]___1" ( Anlaabl(""""" yaxis ;V)
Inlabel ("#rriondd//Parrcciaassss (8.tttt),)
Inlabel ("Results of a Pie Eating Contest", (8.5,9),M) ;N); Inlabel (rotate(90)**
of Pies Eaten", (-1,4.5), ,W); [/asy]
Positive response with identified spurious step:
To solve this problem, we need to identify the number of pies Emily and Mike consumed, and then find the difference between their consumption. From the chart provided: Emily:
Consumed 8 pies. Mike: Consumed pie. To determine how many more pies Emily ate
compared Mike,
first identify how many pies each person atc. Emily atc pies Mike ate pie, Now, calculating the difference between Emily's 's and Mike's 's consumption: Difference Emily's consumption Mike's consumption 8 7. Therefore, Emily 7 more pies than Mike. The answer is r
Spurious step identified by negative data
Question: When the base-16 number 1AB3 written in base 2, how many base-2 digits (bits) does it have?
Positive response with identified spurious step:
To solve this problem, we first need to convert the base- 16 number IAB3_(N to base-2.
Step I: Convert each digit of the number from base-16 to base-2, The number IAB3_(15
consists of the digits 1, A, B, and 3. Step 2: Convert each digit individually to base-2
representation. 1 1 0001 2 A_ [ 1010
[6] 1011 3_(16)
1001122 Step 3: Combine the base-2 representations of each digit. Concatenating the individual base-2 representations, we get: 1AB3 [16] 0001101010110011 Step 4: Count the total number of digits in the base-2 representation.
The base-2 representation (1A33 [6] can be written
of 11B3_B[aa0] [16] is: 00011010101 1001 The base- 16 number
base 10 decimal as: times 63 times 62 times 16 where and B
are decimal digits. This sequence digits has total digits.
The answer boxed 16
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
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 perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings.
is fine to include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
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 not discussed in the paper.
The authors are encouraged to create 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might 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 address problems of privacy and faimess.
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 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
26

---

Theorem statements are included in the main paper and detailed proofs are included in Appendix and Appendix E.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Experimental details are included the main paper and Appendix and Appendix J
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
27

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [No]
Justification: While the code and dataset generated are not yet ready for anonymous open soureing, we plan open-source the code with appropriate licensing and the generated synthetic data with the updated version the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (uttps://nips.cm cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to reproduce the results. See the NeurlPS code and data submission guidelines (https: //n //nips. httpssccppbblccgeeieeeeeeeeeeeee htt.:gguuiddesoddSuubbbiiiiii
/CodeSubmis iatimmsssiooni wasssooooicyyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Experimental details included in the main paper and in Appendix and Appendix J
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
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, were unable to run multiple experiments. However, since we perform experiments on well- established benchmarks, we could make comparisons with existing work understand the significance of our performance. And hence, whenever needed we make sure to discuss observed performances and significance with existing work. Moreover, since run experiments at different scales and dataset sizes, the trends observed implicitly normalize for error bars.
Guidelines:
28

---

The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by emror bars, confi- dence 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, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call 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 the standard error of the mean.
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 96% CI, if the hypothesis of Normality of errоrs is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
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 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 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 the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https /ttr//euurpp...e www.eerwss..ppp....eeeeeeeeeeeee Cewublic/thiissuideellll
Answer: [Yes]
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 reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special cireumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
29

---

Question:
Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We discuss limitations of our work in Appendix A. Since work is about empirical and theoretical study of reasoning in LLMs, we do not believe that there are any direct negative implications.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Our work is not focused towards releasing novel pretrained language models, image generators or scraped datasets. For the synthetic dataset obtained for reasoning tasks by prompting large models, we believe there are no risks of misuse.
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
30

---

Justification:
We make sure to cite relevant and related work. Our code base builds on top open-source code repositories that allow free access for research purposes. When open-source our code with the updated version, we will make sure that all the credits are appropriately attributed.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is available online, the authors are encouraged to reach out the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not release any new assets, For the dataset generated in our work, we include prompts mentioned in Appendix H.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
We do not do any crowdsourcing experiments.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
31

---

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 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 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 the institution conducting the review.
32


Reviews:
[{"review_id": "Dd3LOQHSuR", "reviewer": "Reviewer_jvk2", "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.", "questions": "See the Weaknesses part.", "limitations": "The authors have addressed the limitations.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "- The paper studies an important problem.\n- The conceptual model of negative sample construction covered in Section 6.1 is an interesting read, as the authors formally express the synthetic data problem in the context of RL.", "weaknesses": "- 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).\n\n- 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}^{+}? \n\n- It makes me confused when I compare Lines 224-244 and Lines 245-263. \n\n    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`.\n\n- 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.\n\n- 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.\n\n- 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?\n\n- Lines 343-344: `As such, we needed to tune β in Equation 1 for DPO but could not fully avoid\n344 performance degradation.` Where is the evidence to this claim? Experimental results with a sweep of β would be supportive. \n\n\n- 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`.\n\n- 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.\n\n\nI encourage the authors to address my concerns, and I would consider raising my score provided that the issues I raised are resolved properly.\n\nOthers: Line 322: \"instantation\" --> \"instantiation\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the review! To address the concerns, we add many results for RFT, spurious correlations, per-step RL, and advantage estimation, which we believe improve the quality of the paper. We will use the 1 extra page in the final to incorporate them, along with a conclusion, and clarifications shown below. **Please let us know if your concerns are addressed, and if so, we would be grateful if you are willing to raise your score.** \n\n## [New exp.] L242-245 RFT data w/ 1 sample / problem; RFT is 2x as efficient as SFT, L224-244 vs. 245-263.\n\nWe compare SFT & RFT, when the RFT data is the same size as SFT (128k). For each prompt, we only include one response for RFT. On MATH we see: **44.09 (SFT) vs 45.17 (RFT)** and on GSM8K: 80.18 (SFT) to 81.27 (RFT). As said in L242-245, we observe a >1% gain. \n\nOur definition of efficiency compares performance from training on a fixed set of synthetic problems, while allowing for as many responses per problem. This is because synthetic questions are obtained by querying proprietary models, which is expensive in terms of both FLOPs and cost, and may require human verification in practice. In contrast, sampling responses from SFT policy only requires running inference against a 7B model. Please see the global response for a comparison of costs between SFT, RFT, and DPO. Fig 2 a,b shows that for an appropriate number of self-generated samples per question, RFT matches the performance of SFT with 2x more questions, hence the 2x efficiency. \n\nOf course, as we scale up RFT data, we also amplify spurious correlations as discussed in L245-263 (and per-step filtering can fix this), but for the right number of samples per prompt, **RFT does as well as SFT with 2x data**. Thus, **L224-244 & 245-263 are not contradictory**: they apply to different settings with different #samples per prompt.\n___\n\n## [New exp.] Per-step RFT weighted by advantage\n\nWe ran an experiment with advantage filtering on all the steps present in **both** positive & negative data from the SFT policy and cloned the filtered data. This “*per-step RFT”*  outperforms standard RFT (Fig 1 in 1-page PDF), 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.   \n___\n\n## Fig 4; Artificial spurious correlations.\n\nWe will update the paper to refer to Fig. 4 in L257-263. As you noted, in these experiments, we artificially injected an arbitrary step from an incorrect response produced by SFT policy, into a positive solution trace. While this artificial injection does not necessarily reflect the proportion of spurious steps in $D_\\text{syn}$, it still does provide a controlled proof-of-concept to illustrate that RFT can amplify spurious steps when present, and perform worse than SFT as a result. \nTo show the presence of spurious steps in $D_\\text{syn}$, we sample 128k RFT data (16 responses per prompt), and find RFT to degrade drastically (Fig 3b in 1-page PDF). For both these cases,  per-step RFT does not fall prey to spurious steps and consistently improves over SFT (Figs 1a,b, 3c in 1-page PDF). \n___\n\n##  [New exp.] Per-step DPO: algorithm box, comparison w/ Hwang et al.\n\nTo avoid confusion, we provide an algorithm box for our per-step DPO in Panel 5 (PDF). As you note, our main focus is to analyze the importance of negative data and not to propose a new algorithm. For our experiments, we use the method from Hwang et al. [23], as this was more convenient for experimentation. That said, we have now run another version of per-step DPO (Panel 5 in 1 page PDF) derived from the advantage-weighted RL objective (Thm 6.1) and find that it improves efficiency further by 1.5-2x on MATH, supporting the efficacy of our framework.\n___\n\n## [New exp.] Tuning $\\beta$ for DPO (L343-344)\n\nWe run DPO and per-step DPO run with different $\\beta$ on 128k problems (same setting as Fig 5c of the paper). Even for the best value of $\\beta=0.2$ at 128k, DPO performs worse than per-step DPO and also DPO on 8k problems.\n\n| $\\beta$ | DPO | per-step DPO |\n|:-------:|:--------:|:-----------------:|\n|   0.05  |   35.58  |       45.11       |\n|   0.1   |   36.18  |       47.64       |\n|   0.2   |   36.21  |       46.52       |\n|   0.3   |   35.17  |       45.89       |\n|   0.5   |   34.49  |       45.93       |\n___\n\n## [New exp.]  L377-386: Concrete evidence\n\n**When adv. estimation error is high…memorization is amplified**: To support this, we add a new result on the didactic star graph. We train on negative data with per-step DPO, but instead of using 5 samples for advantage estimation (as in original Fig 8), we only use 1 sample (fewer samples ⇒ larger error), and find that per-step DPO no longer learns the generalizable feature, and instead only reduces training loss by memorizing the “hard/critical’ token”, with accuracy of per-step DPO around 50%. This underscores the advantage estimation error (Fig 2a in PDF).\n\n**For a fixed sample size, advantage estimation error drops as we increase $K$.**: Based on the above observation that higher estimation error leads to memorization, we suggest computing advantages under a higher $K$. To show this, we add a new result plotting the variance of the advantages given by two independent runs of advantage estimation for each value of $K$, averaged over all steps in the SFT data (Fig 2b in PDF). As claimed, we find that $K=5$ has an estimation error that is $<25%$ of the estimation error for K=1, with larger $K$ doing better.\n___\n\n## Applicability to ARC.\n\nWe believe that per-step RL should carry over to any task where we can break the response into steps, including code, where each line or function call can correspond to a step (e.g., prior work StepCoder (Ma et al. 23) trains process reward models for code using a similar framework).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RkR2xDbt64", "reviewer": "Reviewer_e455", "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.\n\nKey findings include:-\n(1) Finetuning on synthetic correct/positive problem-solution pairs offers modest gains, but sampling more correct solutions from the finetuned learner doubles sample efficiency.\n(2) Training solely on model-generated positives can amplify spurious correlations, leading to flat or inverse scaling trends as data increases.\n(3) Utilizing negative responses (incorrect model-generated responses) alongside positives, with appropriate credit assignment for intermediate steps, yields consistent gains over positive-only data.\n(4) The proposed per-step negative data approach is equivalent to advantage-weighted reinforcement learning (RL) and helps unlearn spurious correlations.\n\nThe 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.", "questions": "None.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The work reveals important nuances in using synthetic data, particularly the value of leveraging negative examples and the importance of credit assignment for intermediate steps.\n- The findings offer concrete guidance for improving LLM training with synthetic data, potentially addressing data scarcity issues in language model development.\n- The authors conduct extensive experiments, including scaling studies and comparisons with various baselines, strengthening the validity of their claims.", "weaknesses": "- 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.\n- 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.\n- 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.\n- 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.\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback. To address your concerns, we clarify and add several new results to show how per-step RL on negative data can fix issues caused by accumulation of errors from training on multiple generations of positive synthetic data, and also respond to the other concerns on choice of tasks/model size, baselines, and their computational costs, and will add this discussion to the paper. **Please let us know if your concerns are addressed, and if so, we would be grateful if you are willing to raise your score.**\n\n___\n## [New exp.] Model collapse from training on synthetic data.\n\n**As we already discussed in the submission, our study of negative synthetic data in Sec 6 precisely addresses the concern of amplifying model biases when scaling positive synthetic data.** For this, we introduce a conceptual framework that uses negative data to identify model biases (spurious/incorrect steps) and down-weights them appropriately with step-level advantage-weighted RL. Details below: \n\nWe discuss spurious correlations in Section 5, where we discuss how naively scaling data by sampling more responses for the same set of synthetic questions leads to a drop in performance (Fig 2c). We explain this finding with an experiment where we finetune on positive data with spurious steps (Fig 4). Thus, as we scale synthetic data more spurious steps creep into the training data and corrupt final performance. To further show the amplification of model biases, we add a new experiment (Fig 3a in 1-page PDF) where we train on a large amount of self-generated RFT data (128k samples) on 8k/16k questions. Note the sharp increase in test error of RFT compared to training on just 10k or 20k RFT data points (1 or 2 responses per prompt). \n\nWe also add a new result in Fig 1 in the PDF to show that per-step advantage filtering of this model-generated positive and negative data allows us to address this issue of amplification of spurious steps, leading to improved test error as we scale up the number of model samples.This shows that our conceptual framework allows us to help address model biases, amplified by training on positive data alone. We will add these to the paper.\n\n___\n## Computational cost \n\nFor a fixed size of synthetic dataset the training FLOPs for all methods SFT, RFT and all variants of DPO are identical. The main difference lies in the inference compute spent on collecting model-generated responses for RFT/DPO.\n\nFor DPO, if the accuracy of $\\pi_\\mathrm{sft}$ is $p$, then with high probability, identifying a single positive and negative sample for a prompt takes $max(1/p, 1/(1-p))$ samples. For per-step DPO, we additionally spend $5$ samples per step to estimate advantage, for a maximum of 10 steps per question. Finally for RFT we collect positive training data, by sampling 100 prompts per question. Thus, in total, DPO requires $max(1/p, 1/(1-p))$, and  per-step DPO requires $max(1/p, 1/(1-p)) + 50$  samples per question, both of which are smaller  than $100$ for RFT, when we plug in $p \\approx  0.4$ and $p \\approx 0.7$ for MATH and GSM8K respectively. **Thus, per-step DPO is more computationally efficient than RFT in our experiments.**\n\n___\n## Comparisons with more recent techniques in synthetic data generation or model finetuning\n\nOur technique for synthetic data generation for math follows the pipeline established in Li et al. [28], Yu et al. [61], Liu et al. [30], and Wang et al. [54]. These studies already compare various ways of prompting for new questions, and thus we rely on their findings to generate synthetic problems, but we study scaling behaviors on this data. **Crucially, we also study scaling for model-generated positive data and negative data, which these prior works don’t study.**\n\nWhile SFT does not have many variants, we already compare w/ two different DPO baselines (Fig 5c), to underline the importance of per-step advantage computation and step-level preference pairs. We also add a new result with per-step RFT and find it improves the efficiency of RFT (Fig 1 in 1-page PDF) while addressing spurious correlations. We also add a new result showing the efficacy of per-step KTO over naive KTO alone, further strengthening our claims.\n\nIf the reviewer could elaborate on specific baselines or comparisons they would like to see, we will include them in the final version. \n\n___\n## Justifying the choice of tasks/domains and model size used for experiments.\n\nFaced with computational constraints, at the beginning of the project, we had the choice of performing an in-depth analysis on one domain (math) or a shallow analysis over many domains. We chose the former to be able to provide detailed insight for future work on RL and synthetic data for math capabilities, which is an active area as well as to provide a roadmap for running similar analyses in other areas. Within math reasoning, our study is of a similar scope to Li et al. [28], Hwang et al. [23], etc. Finally, MATH and GSM8K datasets are the default standard for several papers. We agree that extending our analysis to other domains is interesting, and will add this as an avenue for future work.\n\nWe also clarify that our conceptual framework of using positive and negative data for advantage estimation, spurious correlations in RFT, and per-step RL does not assume anything about the underlying task beyond the access to a final answer checker. Thus, our framework should be helpful for guiding algorithm design in other domains. **We also analyze how credit assignment disincentivizes memorization using a star-graph problem (Sec 6.3): while this problem is very different from the math tasks we study, we still draw conclusions that explain both of these phenomena.**\n\n**Regarding model size,** our experiments on the didactic setup uses GPT-2, so we already show that our analysis holds for smaller model sizes and reasoning tasks beyond math too (e.g., graph search). Due to computational constraints, we cannot run SFT/DPO beyond 7B.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "y4TyIdTTFQ", "reviewer": "Reviewer_8A1v", "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.", "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?\n2. Line 166: The sentence is not well-written.\n3. 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?\n4. Line 302: Why are the advantage values always non-positive?\n5. 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.\n\nThe reviewer will consider increase the score if some of the weakness and questions are addressed.", "limitations": "Limitations are discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Synthetic data for reasoning is a highly important topic.\n2. The idea is straightforward and effective.\n3. The experiments are extensive, with comprehensive ablation studies.", "weaknesses": "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].\n2. 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?\n3. 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?\n4. 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?\n\n### Reference\n[1] Dohmatob, Elvis, et al. \"A tale of tails: Model collapse as a change of scaling laws.\" arXiv preprint arXiv:2402.07043 (2024).\n\n[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.\n\n[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.\n\n[4] Gu, Jiatao, et al. \"Non-autoregressive neural machine translation.\" arXiv preprint arXiv:1711.02281 (2017).\n\n[5] Zhou, Chunting, Graham Neubig, and Jiatao Gu. \"Understanding knowledge distillation in non-autoregressive machine translation.\" arXiv preprint arXiv:1911.02727 (2019).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback. To address the concerns, we add new results applying per-step RL to KTO and RFT as well, and compare computational costs. We also clarify the per-step DPO algorithm, advantage functions and Fig 7. **Please let us know if these responses address your concerns, and if so, we would be grateful if you are willing to raise your score.**\n\n___\n## [New exp.] Per-step DPO definition, KTO results (W2, Q3)\n\nAs we understand, there are two concerns: \n- (1) does per-step DPO work well because DPO is a weak baseline, and would the benefits of per-step RL translate to other RL methods?; \n- (2) the exact formulation of per-step DPO.\n\nTo answer (1), we show that per-step variants of other RL methods also improve over them. We add new results extending RFT and KTO to their corresponding per-step variants using both positive and negative data. We find that their respective per-step variants outperform both RFT (Fig 1 in PDF) and KTO (Fig 4 in PDF) on both GSM8K and MATH. For RFT, the per-step variant exactly optimizes a sampled estimate of Thm 6.1. \n\nIn Fig 4 (in PDF), we find that while KTO is slightly worse than DPO, the per-step version of KTO consistently outperforms KTO. That said, we still emphasize that **our point is not to propose per-step DPO as an algorithm, but to show that our conceptual model of per-step advantages and negative data can enhance the efficiency of synthetic data.** We chose DPO as a base algorithm, but this is not the only choice.\n\nRegarding (2), we clarify that our implementation of per-step DPO is the one in L180. To avoid confusion, we present it as an algorithm box (Panel 5 in 1-page PDF). While this does deviate a little from Thm 6.1, it allowed us to build on Hwang et al. 2024’s codebase while still conforming to our conceptual model. In our implementation, we generated preference pairs using only negative responses. When we also consider low-advantage steps in positive data to construct preference pairs (closer to formulation in Thm 6.1), we see a further improvement of 1.5-2x (Panel 5). We also note that **our formulation from Thm 6.1 has been successfully utilized by [a paper that appeared on arXiv after NeurIPS deadline](https://arxiv.org/pdf/2406.18629), confirming the efficacy of our framework as well.**  \n\n___\n## Claims on sample efficiency, cost of per-step DPO vs RFT (W3)\n\nTo clarify, when we say per-step DPO is more efficient than RFT/SFT, we mean that per-step DPO achieves better accuracy _for the same number of synthetic prompts_, vs SFT or RFT. We consider only the number of synthetic prompts here as these require querying proprietary models, which costs inference FLOPs, and hence is more expensive than sampling the SFT model. \n\nHowever, for a fixed set of synthetic problems, we can compare the efficiency of per-step DPO & RFT, in terms of the number of samples from the SFT policy used. For RFT, to collect enough positives from SFT, we draw 100 samples per prompt & filter correct ones. For DPO, if the accuracy of SFT is $p$, then with high probability, identifying *one* positive and negative sample takes $max(1/p, 1/(1-p))$ samples / prompt. For computing advantages in the negative response, we set the maximum number of steps per generation as 10 and sample 5 MC rollouts from each step. Thus, in total per-step DPO requires $max(1/p, 1/(1-p)) + 5* 10$ samples per prompt, which is smaller than $100$ for RFT, when we plug in $p \\approx  0.4$ and $p \\approx 0.7$ for MATH and GSM8K respectively. **Thus, per-step DPO is more computationally efficient than RFT in our results.**\n\n**Please see global response for more details.**\n___\n## Explanation of Fig. 7\n\nIn Fig. 7, our main claim is that the per-step approach of using positive and negative data uniformly improves Q-values across all steps compared to the SFT policy. This should be expected since advantage-weighted RL optimizes the RL expected reward objective. On the other hand, standard DPO which does not maximize the per-step RL objective does not improve Q-values over that of the SFT policy, at earlier steps. \n\nThe avg. Q-value at step $T$ is averaged over only those responses with $\\geq T$ steps. We agree that later steps may only appear in harder problems & may have lower Q-values, but our goal is to compare per-step RL with the SFT policy (gray dashed line) *for the same step* and not to compare Q-values across different steps. \n\n___\n## Why are advantages non-positive?\n\nIn RL, advantages under the optimal policy are non-negative since the advantage is given by the difference between Q-value for an action and the maximum of Q-value at that state. In contrast, our definition in Eq. 3 relies on the choice of $\\tilde{\\pi}$, so you are correct that Eq. 3 may not always be non-positive for arbitrary $\\tilde{\\pi}$. However, when setting $\\tilde{\\pi} = \\mathrm{BoK}(\\pi_\\mathrm{sft})$, and when $K$ is large, w.h.p. we would expect Eq. 3 to be non-positive since $\\tilde{\\pi}$ should improve over the choice of step $\\hat{y}_{i-1}$ prescribed by the SFT policy. This may not be true when $K$ is small or when sampling error is present, and we will clarify this in the paper.\n\n___\n## Clarifications about Line 138.\n\nIn general, we cannot guarantee that generated data will be correct, but we follow the recipe of Li et al. 2024 that asks the model to also verify its responses. Li et al. 2024, Liu et al. 2023 follow the same data protocol and show that scaling up synthetic data this way can improve 7B models to beyond GPT4 performance, indicating that data quality may not be as bad.\n\n___\n## Missing references.\n\nThanks for pointing out these references, we will cite & discuss them. We believe our contributions go beyond these works: for e.g., while [1, 2] find slower convergence with synthetic data, and [3, 4, 5] discuss efficiency of self-gen. data, neither of them study how to use negative data or propose a conceptual framework to understand it. None of these focus on reasoning with modern LLMs.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "56kgSzykTV", "reviewer": "Reviewer_iuJa", "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.", "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)\n- Clarification for lines 197-199: How do we know that this implies improving coverage over samples, rather than the other reasons I mentioned?\n- 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": "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.", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "I was really impressed by this paper – at least for me, it contains quite a lot of insights, and is substantially better than most papers on synthetic data that I’ve seen in the past. \n- I thought the idea of using negative data was fairly natural but also good, and I’m glad to see it implemented in practice\n- I found that the proposed link to model collapse seemed really interesting, which allegedly can occur if a model generating synthetic data has memorized the training data using a spurious feature. \n- I really liked the idea of looking at “critical steps”, and I thought the approach of relating this to credit assignment was impressive.\n\nMore generally, I liked that the authors really made clear attempts to both quantify and explain their empirical observations. For example, I appreciated the section comparing the sample efficiency of self-generated and GPT-4/Gemini 1.5 Pro synthetic data, which does both.", "weaknesses": "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. \n\nAnother 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.\n\nLines 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.\n\nAs 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the feedback and for the positive assessment of our paper! We are grateful to you for the comments and kind words regarding the contribution of our paper. To address the questions, we have added a discussion of computational costs below and answer the other questions raised. **Please let us know if your questions are addressed, and if so, we would be grateful if you might be willing to increase the score further.** \n\n___\n\n## Scalability of approaches; comparison of the overall FLOP required for fine-tuning\n\nThanks for the question! We will add a more formalized version of the discussion below to the final version of the paper. To understand the scalability of SFT, RFT, and per-step DPO, we make the following comparisons. First, SFT exclusively uses synthetic prompts and responses generated from more capable models. Assuming inference FLOPs are $2 \\times N \\times D$, this cost scales with the parameter size ($N$) of the more capable model used to generate the data for every new synthetic question, whereas RFT and per-step DPO only require running more rollouts with a much smaller 7B model for fewer questions, not incurring the inference FLOPs of the more capable model. Thus in a FLOPs-matched comparison, RFT / per-step DPO should have an even bigger edge over SFT.\n\nNow we perform a comparison of FLOPs / compute costs for  RFT and per-step DPO, for a fixed number of synthetic prompts. We can break the total FLOPs into two parts: **(a)** inference FLOPs needed to generate data from the SFT policy for running RFT and per-step DPO, and **(b)** training FLOPs for RFT and per-step DPO. \n\n**Regarding (b),** we train both RFT and per-step DPO for an equal number of steps, with an identical number of forward and backward passes through the model: more precisely, since the DPO loss utilizes two samples together, we run DPO with half the batch size to fit on the GPU memory. Put together, this should lead to an equal number of forward and backward passes for per-step DPO and RFT. The training FLOPs are typically given by $6 \\times N \\times D$, which should be the same for both RFT and per-step DPO. \n\n**Regarding (a),** we compare the number of samples that need to be drawn from the SFT policy for both RFT and per-step DPO. For RFT, to collect enough positives from $\\pi_\\mathrm{sft}$, we draw 100 samples per question and filter for positive ones. For DPO, if the accuracy of $\\pi_\\mathrm{sft}$ is $p$, then with high probability, identifying a single positive and negative sample for a prompt takes $\\approx max(1/p, 1/(1-p))$ samples. Now, for computing advantage estimates of each step in the negative response, we set the maximum number of steps per generation as 10 and sample 5 MC rollouts conditioned on each step. Thus, in total per-step DPO requires $\\approx max(1/p, 1/(1-p)) + 50$ samples per question, which is a value smaller than $100$ for RFT, when we plug in $p \\approx  0.4$ and $p \\approx 0.7$ for MATH and GSM8K respectively (this is the accuracy of the SFT model in our experiments). **Thus, DPO is more computationally efficient than RFT in our experiments.**\n\n___\n## Clarification for lines 197-199: How do we know that this implies improving coverage over samples, rather than the other reasons I mentioned?\n\nThanks for bringing this up! Indeed the difference in scaling law exponents can come from a different functional form of the scaling law. We originally wrote this statement because the approx. exponent of the scaling law of Llama2-70B on GSM8K (derived from training on 1, ½, ¼ subsets of only real GSM8K training data) is -0.3 (following the result from Yuan et al. [68]) and -0.105 for DeepSeek-7B on MATH (see below for the result), whereas we observed -0.15 with synthetic data on GSM8K and -0.05 on MATH, which is substantially lower. Since the only difference is in the datasets (at least for MATH), we attributed this to the coverage of samples. That said, you are right that a comparison with pre-training scaling laws may not be correct here, so we will update this line to note the difference against training models on real math data, rather than contrasting it with pre-training scaling laws.\n\n| Training data fraction |   1   |  1/2  |  1/4  |  1/8  |  1/16 |  1/32 |\n|:----------------------:|:-----:|:-----:|:-----:|:-----:|:-----:|:-----:|\n|       Test error       | 0.624 | 0.671 | 0.742 | 0.788 | 0.832 | 0.905 |\n\n___\n##  The main approaches in the paper apply most directly to mathematics, since identifying critical steps involves checking results based on MC rollouts.\n\nWe only study our approach on MATH and GSM8K due to computational constraints associated with running it on other domains, and are happy to change the title of the paper to include “math reasoning” instead of “reasoning” to clearly scope the contributions of the paper, if the reviewer thinks that would be more appropriate. That said, we do think that identifying critical steps using MC rollouts and per-step RL can also be used for coding problems, where each line or each function call can correspond to a step (e.g., see StepCoder (Ma et al. 2023), which runs a similar style of MC rollouts to collect data for training process reward models on coding problems). We will add a discussion of this in the paper.\n\n___\n## Clarification for lines 203-204:\n\nYes, your interpretation is correct in that only 4 out of the 100 sampled responses are used for training with RFT, following the procedure in Yuan et al. 2023.\n\n___\n## Typo / minor concern: “It is predicted that we will run out of high-quality internet data by 2026\n\nThanks for catching the typo! We will update the statement to reflect 2028, the median year in that reference and use the term “human-generated public text data” instead of internet data to address the concern.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank all reviewers for their detailed feedback, and in particular would like to highlight the the positive assessment of our work by Reviewer iuJa: **“contains quite a lot of insights, and is substantially better than most papers on synthetic data that I’ve seen in the past”**.

To address the reviewers' concerns, we have added several new experiments, which we believe substantially improve the quality of our paper. The results are shown in the 1-page PDF which we will incorporate using the extra page in the final version. We also discuss a common question on the computational cost of collecting positive and negative synthetic data and running per-step RL in this global response as well. **We hope that these responses address the reviewers' concerns and look forward to the discussion period.**

___

## **List of new experiments in 1-page PDF**

- **Figure 1:** We clone responses with high advantage steps from positive and negative responses sampled from the SFT policy. We filter all responses where the minimum advantage across all steps is in the bottom 50% percentile.

- **Figure 2:** (Top) We analyze the effects of running per-step DPO on our didactic star-graph problem when advantages are computed using a single rollout and as a result are likely incorrect. (Bottom) We compute the variance of advantage estimates as we increase K for $BoK(\pi_{\mathrm{sft}})$. 

- **Figure 3:** We scale up RFT to 128k data points by sampling answers from the SFT policy for only 8k/16k questions in $\mathcal{D}_\mathrm{syn}$ (left). The performance degradation for RFT is now severe, and similar to what we observe when running RFT dataset where we synthetically inject spurious steps (right). In the same figure, we also see that per-step RFT (described above) is able to filter responses with low-advantage, spurious steps and is able to almost match the performance of per-step DPO.

- **Figure 4:** We compare KTO with per-step KTO and find that the benefits of our conceptual framework of step-level credit assignment is agnostic of the choice of the underlying RL algorithm (DPO/KTO). 

- **Panel 5:** We show an algorithm box for the per-step DPO algorithm used in our experiments. Note that in this algorithm we compute step-level advantages over only negative responses, consistent with Hwang et al. [23]. To more closely approximate the theoretically optimal version (mimicking advantage weighted RL) in Thm 6.1, we run a modified version of this algorithm where we also compute advantages for steps in positive rollouts. This modified version performs even better than per-step DPO validating the utility of our framework in Sec 6. 

___

## **Computational costs of SFT, RFT, per-step RL**

To understand the computational costs of SFT, RFT, and per-step DPO, we make the following comparisons. First, SFT exclusively uses synthetic prompts and responses generated from more capable models. Assuming inference FLOPs are $2 \times N \times D$, this cost scales with the parameter size ($N$) of the more-capable model used to generate the data for every new synthetic question ($D$), whereas RFT and per-step DPO only require running more rollouts with a much smaller 7B model for fewer questions, not incurring the inference FLOPs of the more capable model. Thus in a FLOPs-matched comparison, RFT / per-step DPO should have an even bigger edge over SFT.

Now we perform a comparison of FLOPs / compute costs for  RFT and per-step DPO, for a fixed number of synthetic prompts. We can break the total FLOPs into two parts: 
- **(a)** training FLOPs for RFT and per-step DPO. 
- **(b)** inference FLOPs needed to generate data from the SFT policy for running RFT and per-step DPO, and 

**Regarding (a),** we train both RFT and per-step DPO for an equal number of steps, with an identical number of forward and backward passes through the model: more precisely, since the DPO loss utilizes two samples together, we run DPO with half the batch size to fit on the GPU memory. Put together, this should lead to an equal number of forward and backward passes for per-step DPO and RFT. The training FLOPs are typically given by $6 \times N \times D$, which should be the same for both RFT and per-step DPO. 

**Regarding (b),** we compare the number of samples that need to be drawn from the SFT policy for both RFT and per-step DPO. For RFT, to collect enough positives from $\pi_\mathrm{sft}$, we draw 100 samples per question and filter for positive ones. For DPO, if the accuracy of $\pi_\mathrm{sft}$ is $p$, then with high probability, identifying a single positive and negative sample for a prompt takes $ \approx(1/p, 1/(1-p))$ samples. Now, for computing advantage estimates of each step in the negative response, we set the maximum number of steps per generation as 10 and sample 5 MC rollouts conditioned on each step. Thus, in total per-step DPO requires $ \approx(1/p, 1/(1-p)) + 50$ samples per question, which is a value smaller than $100$ for RFT, when we plug in $p \approx  0.4$ and $p \approx 0.7$ for MATH and GSM8K respectively (this is the accuracy of the SFT model in our experiments). **Thus, per-step DPO is more computationally efficient than RFT in our experiments.**

Meta-review: 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.
Decision: Accept (poster)