PaperlayerView exact revision on arXiv

Source-linked AI summary

Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences

Corby Rosset, Ching-An Cheng, Arindam Mitra, Michael Santacroce, Ahmed Awadallah, Tengyang Xie

arXiv:2404.03715v1cs.LGcs.AIcs.CL

TL;DR

Reward-based RLHF has limited expressivity, while efficient scaling of general-preference optimization remains unclear. This paper introduces DNO, a batched regression-based contrastive approach, and reports a 33% win-rate for a 7B Orca-2.5 model against GPT-4-Turbo on AlpacaEval 2.0.

  • Problem

    Reward-based RLHF has limited expressivity, and efficient scaling of general-preference optimization remains unclear.

    Source: §1 · p. 2

  • Method

    DNO approximates soft policy-iteration updates with a batched regression-based contrastive objective for general-preference optimization.

    Source: §1 · p. 2, §7 · p. 17

  • Results

    33% win-rate against GPT-4-Turbo on AlpacaEval 2.0, even after controlling for length, and an over 26% absolute gain (7%→33%) over the initialized 7B Orca-2.5 model.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Optimizing general preference functions can be reduced to finding a Nash equilibrium of a two-player preference-payoff game and solved by a single-play algorithm.

    Source: §7 · p. 17

    Errors in preference annotation can propagate across iterations, requiring rollback to the iteration that introduced them and risking wasted time and cost.

    Source: §5.2 · p. 15

Abstract

from arXiv · show

This paper studies post-training large language models (LLMs) using preference feedback from a powerful oracle to help a model iteratively improve over itself. The typical approach for post-training LLMs involves Reinforcement Learning from Human Feedback (RLHF), which traditionally separates reward learning and subsequent policy optimization. However, such a reward maximization approach is limited by the nature of "point-wise" rewards (such as Bradley-Terry model), which fails to express complex intransitive or cyclic preference relations. While advances on RLHF show reward learning and policy optimization can be merged into a single contrastive objective for stability, they yet still remain tethered to the reward maximization framework. Recently, a new wave of research sidesteps the reward maximization presumptions in favor of directly optimizing over "pair-wise" or general preferences. In this paper, we introduce Direct Nash Optimization (DNO), a provable and scalable algorithm that marries the simplicity and stability of contrastive learning with theoretical generality from optimizing general preferences. Because DNO is a batched on-policy algorithm using a regression-based objective, its implementation is straightforward and efficient. Moreover, DNO enjoys monotonic improvement across iterations that help it improve even over a strong teacher (such as GPT-4). In our experiments, a resulting 7B parameter Orca-2.5 model aligned by DNO achieves the state-of-the-art win-rate against GPT-4-Turbo of 33% on AlpacaEval 2.0 (even after controlling for response length), an absolute gain of 26% (7% to 33%) over the initializing model. It outperforms models with far more parameters, including Mistral Large, Self-Rewarding LM (70B parameters), and older versions of GPT-4.

1 Introduction

DNO targets the limits of scalar-reward RLHF by directly optimizing general preferences with an efficient, scalable procedure. Its design combines batched on-policy regression with the flexibility to use teacher-generated samples.

Introduction

  • Scalar reward functions cannot express all pairwise preferences, including intransitive or cyclic ones, and can become stale as policy distributions shift, exposing training to reward hacking.The introduction also notes that reward optimization can produce problematic behavior even when preferences are perfectly expressible by reward-based Bradley-Terry models.Source: §1 · p. 2
  • The authors are motivated by unclear paths to scaling optimization for general preferences and seek a solution under that framework with efficiency and scalability comparable to recent reward-based methods such as DPO.Source: §1 · p. 2
  • DNO uses batched on-policy iterations with a binary cross-entropy regression objective, self-play, optional teacher samples, and filtering for preference pairs with a sufficiently large margin.The regression aligns the policy’s internal reward with its expected win-rate against itself, while repeated regression updates make the procedure scalable.Source: §1 · p. 3
  • DNO converges on average to the intended Nash equilibrium, improves monotonically across iterations, and has a finite-sample bound on per-iteration approximation error.The practical implementation uses GPT-4 as preference oracle and compares on-policy outputs with teacher outputs, training only on large-margin pairs.Source: §1 · p. 3
  • 33% win-rate against GPT-4-Turbo on AlpacaEval 2.0, including after controlling for response length, gives DNO-aligned Orca-2.5 a 26% absolute gain over its 7% initializing-model win-rate.The 7B model also outperforms Mistral Large, GPT-4-0613, and the 70B Self-Rewarding LM. Figure 1 reports state-of-the-art raw and length-controlled win-rates above 30%.Source: Figure 1 · p. 2, §1 · p. 3

2 Preliminaries

The preliminaries distinguish reward-based RLHF from direct optimization of general preferences, which may be intransitive and therefore calls for Nash-equilibrium objectives. They define the contextual-bandit setup and review PPO, DPO, SPO, and Nash-MD.

2 Preliminaries

  • The setup treats prompts as drawn from ρ without distribution shift, responses as actions, and the LLM as a policy π in class Π.The paper uses the contextual-bandit setup and does not distinguish RLHF from RLAIF in its discussion.Source: §2 · p. 4

2.1 RLHF Based on Reward Models

  • The standard reward-model approach learns a reward from preference pairs, commonly assuming Bradley-Terry, then fine-tunes the LLM with RL using the PPO objective.The PPO objective uses a coefficient β to mitigate reward-model overoptimization.Source: §2.1 · pp. 4–5
  • DPO combines PPO’s two-step procedure into a single objective by using the closed-form policy solution to optimize directly from preferences.DPO is attributed to Rafailov et al. (2023).Source: §2.1 · p. 5

2.2 RLHF with General Preferences

  • General preferences can be cyclic, so their optimization target can be a Nash equilibrium rather than a point-wise reward maximum.The section frames this equilibrium using Minimax Winner or von Neumann Winner concepts.Source: §2.2 · p. 5
  • SPO approximates a general-preference Nash equilibrium with no-regret updates and a uniform mixture of policies, while Nash-MD uses mirror descent with a last-iteration guarantee.SPO is attributed to Swamy et al. (2024), and Nash-MD to Munos et al. (2023).Source: §2.2 · pp. 5–6

3 Direct Nash Optimization

Direct Nash Optimization (DNO) replaces two-timescale Nash-equilibrium updates with iterative regression on preference-based rewards. Its batched on-policy design supports monotonic improvement when each update accurately approximates the soft policy iteration target, while finite-sample analysis characterizes that approximation and informs sampling choices.

3 Direct Nash Optimization

  • DNO iteratively computes preference-based rewards, updates its policy, and returns a uniform mixture of the iteration policies, avoiding the two-timescale updates that can complicate tuning and destabilize performance.The algorithm is inspired by SPO and can be adapted to Nash-MD for regularized preferences with a last-iteration guarantee.Source: §3 · p. 6

3.1 Derivation of Algorithm 1

  • Regressing internal rewards toward preference-based rewards fits the soft policy iteration target without its partition function, and the offline objective is independent of response-sampling distributions.Sampling can still affect sample complexity through coverage; unlike pushing the policy toward the target, this regression does not require on-policy response sampling.Source: §3.1 · p. 7
  • Batched on-policy updates yield monotonic improvement when each learned policy accurately approximates the soft policy iteration target; validation data can select the best policy across iterations.The paper contrasts this single-timescale design with potentially unstable, purely on-policy Nash-equilibrium algorithms and notes that DNO's returned average policy may be impractical to deploy.Source: §3.1 · p. 8

3.2 Theoretical Analysis

  • Under realizability and boundedness assumptions, Theorem 1 bounds the finite-sample total-variation error between DNO's regression update and the soft policy iteration target.The resulting error is additive to the Nash-equilibrium convergence guarantees cited for the returned policy mixture.Source: §3.2 · p. 8
  • The concentrability analysis guides response-sampling choices, and DNO's soft-policy-iteration objective can favor near-on-policy response distributions rather than the distinct distributions preferred for Bradley-Terry reward estimation.The authors identify this as the first theoretical result illustrating the importance of on-policy sampling beyond policy-optimization-style RLHF algorithms.Source: §3.2 · p. 9

4 Practical Algorithm – Iterative Contrastive Self-Improvement

DNO-Prct makes DNO practical as batched on-policy iterative contrastive self-improvement, using designed sampling, filtering, and pair construction to avoid explicit reward-function values. Its design resembles iterative DPO while accommodating general preferences.

Practical algorithm

  • DNO-Prct samples K current-policy responses per prompt, ranks them with a teacher response by pairwise win-rate, selects large-margin pairs, and contrastively trains the next policy.The procedure iterates from the reference policy and returns the best iteration on validation data.Source: §4 · pp. 9–10

Batched on-policy sampling

  • Because exact P(y ≻ y′ | x) values are impractical to access, DNO-Prct estimates r_t using sampled preference judgments on responses drawn from the current policy.Batched on-policy sampling is also chosen for sample efficiency when approximating Eq. (13).Source: §4 · p. 9

Preference pair construction

  • Large-margin filtering makes the pure contrastive objective approximate DNO’s regression objective without requiring an excessively large learning rate.Because r_t is bounded, scaling it and the learning rate together can preserve the policy-iteration target, but a larger learning rate worsens sample complexity; filtering instead favors pairs with sufficiently large r_t.Source: §4 · p. 10

Relationship between DNO-Prct and DPO

  • DNO-Prct intentionally resembles iterative DPO (Rafailov et al., 2023; Yuan et al., 2024), but uses rankings from pairwise win-rates to handle general preferences.The paper reports that carefully designed iterative DPO could approach the Nash equilibrium for general preferences.Source: §4 · p. 10
  • The broader DNO framework supports regularized preferences and advanced sampling, while its KL regularization arises from online learning, unlike DPO/PPO’s approximation to a total-variation penalty for monotonic improvement.The cited online-learning foundations include mirror descent (Nemirovski and Yudin, 1983) and FTRL; DPO/PPO’s monotonic-improvement rationale cites Kakade and Langford (2002) and Schulman et al. (2015, 2017).Source: §4 · pp. 10–11

5 Experiments

The experiments evaluate batched, iterative DNO using GPT-4-Turbo preference judgments and compare it with supervised, offline, and alternative on-policy approaches. They report stronger AlpacaEval 2.0 and MT-Bench results for DNO than the 70B Self-Rewarding model, while also examining pair construction, data scaling, and limitations.

5 Experiments

  • DNO uses three phases per iteration—sampling, preference annotation, and training—and starts iteration 0 by sampling from the initial SFT model.Experiments mainly use UltraFeedback’s 60k prompts and GPT-4-Turbo annotations, split into three non-overlapping input partitions; GPT-4-Turbo outputs are collected as gold responses when absent.Source: §5 · p. 11, §5.1 · p. 11

5.2 Results and Analysis

  • 24.97 AlpacaEval 2.0 win-rate and 7.46 MT-Bench score for 7B DNO exceed the 70B Self-Rewarding model’s 20.44 and 7.25, respectively.The authors attribute part of the advantage to higher-quality preference annotations; DNO showed a slight gain rather than a drop on ARC-Challenge and HellaSwag.Source: Table 1 · p. 12, §5.2 · p. 14
  • 24.97 win-rate for DNO exceeds SPIN’s 16.13 and DNO-Restrictive’s 19.21, supporting comparisons where students can be preferred over teachers.By iteration 3, over 64% of DNO training pairs (32k pairs) had the student preferred over the teacher; SPIN automatically assigns teacher outputs as positive, while DNO-Restrictive admits only teacher-preferred pairs.Source: Table 1 · p. 12, Table 2 · p. 13, §5.2 · p. 14

5.1 Experimental Setup

  • GPT-4-Turbo judges five sampled student outputs and one gold response, and only scores of 5 or 6 qualify as positive training examples.Pairs require the negative to score at least two points lower, relaxed to one point when the positive is student-generated; training uses at most one epoch on new pairs, with batch size 64.Source: §5.1 · p. 12

5.2 Results and Analysis

  • 11.60 AlpacaEval 2.0 win-rate for large-margin-filtered Offline DPO exceeds 9.60 for the unfiltered control, while on-policy methods, especially DNO, surpass four-epoch Offline DPO.The filtered treatment used 42k pairs with at least a 1.0-point preference margin, versus all 63k pairs for the control; on-policy models had three iterations, each using a third of UltraFeedback’s inputs.Source: Table 1 · p. 12, §5.2 · pp. 13–14
  • 24.97 to 18.18 AlpacaEval 2.0 win-rate for DNO-Lookahead contrasts with MT-Bench improvement from 7.48 to 7.70.The authors note MT-Bench has 80 examples versus roughly ten times as many for AlpacaEval 2.0, and regard the latter’s findings as more reliable.Source: §5.2 · p. 15
  • 10x more instruction data in DNO-More-Data scales across six non-overlapping input partitions of roughly 100k prompts each.The experiment retained Epoch 1 of Orca-2.5 SFT as its initialization; Table 4 reports an absolute AlpacaEval 2.0 win-rate delta of 27.39 (22.29 length-controlled).Source: §5.2 · p. 15, Table 4 · p. 15
  • Student output lengths at least double after the first contrastive-training iteration, then inch down; the authors interpret the spike as wasted optimization toward a spurious signal.They also report that teacher scores decline as the student improves, large-margin pair counts tend to decrease, and annotation errors can propagate across iterations and require costly rollbacks.Source: §5.2 · pp. 14–15

6 Related Work

Related work spans reward-based and contrastive preference learning in offline and online settings. The closest on-policy methods optimize general preferences or use iterative contrastive updates, but prior approaches lack DNO’s student-versus-teacher comparisons.

Online RLHF algorithms

  • RLHF aligns models to human preferences but is unstable and memory-intensive; RAFT and RRHF instead rank sampled outputs with a reward model and SFT-train on the best.The RLHF setup requires the policy, reward, and advantage models on device; RAFT and RRHF’s offline approach resembles iterative behavior cloning.Source: §6 · p. 16

Offline Contrastive Preference Learning

  • Offline contrastive methods include DPO and SLiC, IPO’s direct optimization of preference probabilities, and extensions to ranked lists or unpaired good and bad outputs.RSO creates training pairs from ranked samples and unifies DPO and SLiC; LIPO and PRO learn list-wise preferences, while KTO optimizes pools of good and bad outputs without paired examples.Source: §6 · p. 16

Iterative Reward-based Finetuning

  • ReST iteratively grows samples from the current policy, then uses reward-model filtering and offline RL to improve it; follow-up work uses AI feedback instead of reward ranking.The two stages are described as “Grow” and “Improve.”Source: §6 · p. 16

On-policy Contrastive Learning

  • Self-Rewarding Language Models resemble DNO’s iterative on-policy contrastive training, but use the policy as annotator, while SPIN and APO assume the teacher is better than the student.Self-Rewarding Language Models train on preferences from recent-policy samples, but begin with weak preference signals; SPIN and APO use contrastive losses in iterative training.Source: §6 · p. 16
  • Cringe Loss contrasts the correct next token with a high-logit incorrect token, and Pairwise Cringe Loss adapts it to iterative self-improving training.Cringe Loss is token-level; Pairwise Cringe Loss applies it in an iterative training style.Source: §6 · p. 16

On-Policy General Preference Optimization

  • Prior on-policy general-preference methods target Nash equilibria, but their data efficiency and implementation can suffer, and existing online feedback methods omit teacher comparisons.Nash-MD uses policy gradients and mixture sampling; SPO is a no-regret two-player game, while IPO-MD uses on-policy IPO updates. The cited studies form pairs from student-versus-student samples or student-versus-initial-reference samples, not with a stronger teacher; the paper says omitting student-versus-teacher preferences may hinder performance.Source: §6 · pp. 16–17

7 Conclusion

The paper presents Direct Nash Optimization (DNO) as a practical, scalable way to post-train LLMs for general preferences, reducing preference optimization to a Nash-equilibrium problem. It reports strong AlpacaEval 2.0 performance and theoretical convergence and finite-sample guarantees.

7 Conclusion

  • A 7B LLM trained with DNO achieves state-of-the-art AlpacaEval 2.0 performance, exceeding Mistral Large and older versions of GPT-4.The conclusion does not report numerical win rates for these comparisons.Source: §7 · p. 17
  • DNO approximates soft policy iteration with a batched regression-based contrastive objective, reducing the implementation difficulty and instability of on-policy, two-timescale updates.The approach builds on reducing general-preference optimization to finding a two-player game's Nash equilibrium, solvable with a single-play algorithm.Source: §7 · p. 17
  • DNO converges to the Nash equilibrium on-average, while in practice it exhibits monotonic improvement across iterations.At any iteration t, the paper establishes an eO(1/N) concentration bound on squared total variation error between the learned policy and the target soft policy iteration update.Source: §7 · p. 17
  • The paper provides finite-sample analysis and discusses practical design choices intended to support future iterative self-improving algorithms.Source: §7 · p. 17

Appendix · A Extension to Regularized Preferences

The appendix extends DNO to regularized preferences and gives both a theoretical algorithm and a practical implementation. It distinguishes on-average from last-iteration convergence and notes the sampling implications of the latter.

A Extension to Regularized Preferences

  • Unlike SPO, Nash-MD uses the smoothed policy for both reward construction and soft policy iteration, yielding a late-iteration guarantee.SPO uses the last-iteration policy for both steps.Source: A Extension to Regularized Preferences · p. 24
  • For on-average convergence, regularized-preference symmetry may allow a simpler SPO adaptation that coincides with OMD from Munos et al. (2023).This variant constructs rewards against πt and uses πt only in the soft policy iteration step.Source: A Extension to Regularized Preferences · p. 24
  • Algorithm 3 estimates rewards against πt for on-average convergence or the smoothed policy πτ_t for last-iteration convergence.The algorithm returns the uniform mixture of policies across iterations.Source: A Extension to Regularized Preferences · p. 24
  • The DNO framework is extended to regularized preferences in Algorithm 3, and its practical implementation is given in Algorithm 4; these preferences are defined in Eq. (5).Algorithm 3 takes a KL-regularization coefficient τ as input.Source: A Extension to Regularized Preferences · p. 24
  • Algorithm 4 samples K responses per prompt, ranks them with pairwise win rates, forms large-margin preference pairs, and updates the policy contrastively.The ranking includes the gold response, and sampling uses either πt or the smoothed policy according to the convergence option.Source: A Extension to Regularized Preferences · p. 25
  • The last-iteration practical option requires sampling from the smoothed mixture of πt and πref, with token-level mixture sampling suggested as an alternative by Munos et al. (2023).The implementation returns the best policy on validation data.Source: A Extension to Regularized Preferences · p. 25

B Detailed Proofs

Appendix B gives detailed proofs for the theoretical results, defining the feasible policy spaces and assumptions used in a one-iteration guarantee. The analysis is intentionally simplified rather than exhaustive.

B Detailed Proofs

  • The definitions and assumptions draw on version-space and concentrability ideas, but the presentation is simplified and a full exhaustive analysis is outside the paper’s scope.The authors note that discussion beyond finite Π is omitted and point to Foster and Krishnamurthy (2021) for more in-depth treatment of log-loss regression.Source: B Detailed Proofs · pp. 25–26
  • Each iteration’s feasible space Π_t contains the policy produced by Algorithm 1, and the assumptions impose realizability and boundedness conditions over these spaces.The appendix describes Π_t as analogous to a version space and assumes boundedness for a log-probability expression.Source: B Detailed Proofs · pp. 25–26
  • Theorem 2 states a result under Assumptions 1 and 2 for arbitrary iteration t ∈ [T], with π_{t+1} from Line 4 of Algorithm 1 and C_t defined in Definition 2.The comparison policy π⋆_{t+1} is defined in Eq. (9).Source: B Detailed Proofs · p. 26
  • The proof proceeds from regression with log loss to a squared-error bound, then uses concentration in policy space to relate the learned and comparison policies.The appendix invokes standard concentration for squared loss and bounds involving the feasible-space concentrability coefficient.Source: B Detailed Proofs · pp. 26–28

C Additional Experimental Details

The appendix describes batched GPT-4 preference annotation and reports the time and cost of sampling, annotation, and training for each of six iterations in the 600k-input experiment.

Batched Prompting

  • To reduce annotation overhead, GPT-4 receives candidate responses side-by-side and scores each under the rubric in one context window rather than annotating every pair separately.Figure 3 shows the prompt, including a GPT-4 output alongside outputs from the current policy.Source: C Additional Experimental Details · p. 28, Figure 3 · p. 29

Cost Analysis

  • For each iteration, sampling five outputs for 100k examples took 18–24 hours and cost about $6,000; annotation averaged 450M prompt and 60M completion tokens, costing about $34,000; training took 12–24 hours.Sampling used 10 8xA100 80GB pods; training used two 8xA100 80GB nodes and was the cheapest step.Source: C Additional Experimental Details · p. 28

Related papers

Loading 2404.03715v1…