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

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.

Scalability of approaches; comparison of the overall FLOP required for fine-tuning

Thanks 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.

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) 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.

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.

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.

Clarification for lines 197-199: How do we know that this implies improving coverage over samples, rather than the other reasons I mentioned?

Thanks 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.

The main approaches in the paper apply most directly to mathematics, since identifying critical steps involves checking results based on MC rollouts.

We 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.

Clarification for lines 203-204:

Yes, 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.

Typo / minor concern: “It is predicted that we will run out of high-quality internet data by 2026

Thanks 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.

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.

[New exp.] Per-step DPO definition, KTO results (W2, Q3)

As we understand, there are two concerns:

• (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?;
• (2) the exact formulation of per-step DPO.

To 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.

In 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.

Regarding (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, confirming the efficacy of our framework as well.

Claims on sample efficiency, cost of per-step DPO vs RFT (W3)

To 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.

However, 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.

Please see global response for more details.

Explanation of Fig. 7

In 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.

The 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.

Why are advantages non-positive?

In 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.

Clarifications about Line 138.

In 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.

Missing references.

Thanks 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.

Thank you for your response and for increasing the score!

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

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

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

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

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

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

I appreciate the response and the new experiments on KTO. However, I am not entirely convinced by the claim that "per-step DPO is more computationally efficient than RFT in our results" as the author is drawing 100 samples per prompt, which introduces the possibility of variance when drawing 10 samples per prompt while creating more prompts in RFT. This variant could potentially surpass the original RFT with 100 samples per prompt. The new experiments on the overfitting of RFT, however, demonstrate that given abundant compute resources, per-step DPO clearly outperforms. Consequently, I have increased my score.

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.

[New exp.] Model collapse from training on synthetic data.

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:

We 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).

We 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.

Computational cost

For 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.

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 $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.

Comparisons with more recent techniques in synthetic data generation or model finetuning

Our 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.

While 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.

If the reviewer could elaborate on specific baselines or comparisons they would like to see, we will include them in the final version.

Justifying the choice of tasks/domains and model size used for experiments.

Faced 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.

We 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.

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.

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.

[New exp.] L242-245 RFT data w/ 1 sample / problem; RFT is 2x as efficient as SFT, L224-244 vs. 245-263.

We 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.

Our 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.

Of 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.

[New exp.] Per-step RFT weighted by advantage

We 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.

Fig 4; Artificial spurious correlations.

We 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. To 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).

[New exp.] Per-step DPO: algorithm box, comparison w/ Hwang et al.

To 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.

[New exp.] Tuning $\beta$ for DPO (L343-344)

We 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.

[New exp.] L377-386: Concrete evidence

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).

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.

Applicability to ARC.

We 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).

Dear reviewers,

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

Thanks, Authors