Clarification on computational costs of per-step DPO and RFT
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).