PaperlayerView exact revision on arXiv

Source-linked AI summary

Inference-Time Nash Alignment

Hadi Hosseini, Debmalya Mandal, Duohan Zhang

arXiv:2609.08082v1cs.AI

TL;DR

Preference-based fine-tuning is costly and requires parameter access, while existing inference-time alignment is limited by scalar reward models and cannot express general preferences. This paper formulates black-box inference-time alignment as a Nash game, proposes BoN and NMD, and shows tight theoretical guarantees plus strong empirical performance. The methods improve over SFT across three datasets, match DPO’s expected win-rate in the reported comparison, and NMD is robust across regularization.

  • Problem

    Existing preference fine-tuning requires substantial data, computation, and parameter access, while inference-time methods commonly rely on restrictive scalar Bradley–Terry rewards.

  • Method

    The paper formulates generalized-preference inference-time alignment as a two-player zero-sum Nash game and proposes Best-of-Nash and Nash Mirror Descent.

  • Results

    Both methods outperform the SFT base across TLDR, HelpSteer2, and UltraFeedback, while matching LLaMA3-DPO’s expected win-rate with reasonable sampling.

  • Takeaways & Limitations

    Inference-time alignment can approach fine-tuned performance without parameter updates, and NMD remains robust across the regularization parameter.

  • Takeaways & Limitations

    Performance depends on preference-model quality and base-policy coverage; unreachable high-quality responses cannot be recovered, leaving fine-tuning necessary.

Abstract

from arXiv · show

Preference-based fine-tuning methods such as RLHF and DPO require substantial compute and large preference datasets. They also need direct access to the model parameters which are not provided by many state-of-the art models. Inference-time alignment offers a cost-effective alternative without updating model parameters. However, existing inference-time methods rely on a scalar reward model derived under a Bradley-Terry assumption, which cannot represent general preferences. Following recent work on fine-tuning with generalized preferences, in this work, we initiate the study of inference-time alignment under general preferences. We formulate the problem as obtaining a Nash equilibrium of a two-player zero-sum game between policies. We propose two algorithms: Best-of-Nash (BoN) and Nash Mirror Descent (NMD). We prove that both algorithms achieve a duality gap that matches the problem lower bound. Empirically, we implement the two methods on three datasets, which shows that our methods substantially outperform the base policy, converging to the performance of the fine-tuned models. Moreover, our results show that NMD remains robust across the regularization parameter.

1 Introduction

The paper studies inference-time alignment for generalized preferences, addressing the costs, black-box access constraints, reward hacking, and Bradley–Terry limitations of existing approaches. It formulates alignment as a zero-sum Nash game and introduces BoN and NMD, with theoretical and empirical guarantees.

  • Motivation: Preference fine-tuning requires substantial human-data collection, computation, and white-box access to model parameters.Inference-time methods avoid updating model parameters and can operate with black-box models.
  • Motivation: Best-of-N can suffer reward hacking because increasing estimated reward may coincide with declining true task performance.The issue arises when the reward model is an imperfect proxy for human preferences.
  • Problem: Bradley–Terry scalar rewards cannot represent general preferences, including potentially intransitive aggregated group preferences.The paper identifies generalized preferences in inference-time alignment as an open challenge.
  • Approach: The paper models alignment as computing a Nash equilibrium in a two-player zero-sum game using an imperfect preference oracle and a queryable base policy.The objective is to efficiently approximate the equilibrium at inference time.
  • Contributions: BoN computes an empirical minimax solution, while NMD applies KL-regularized mirror-descent updates in self-play.Both methods target generalized preferences without changing model parameters.
  • Theory and evaluation: Both methods achieve a duality-gap upper bound of O(ε(x)Cuni(x)), and the matching lower bound shows this rate is tight.Experiments evaluate both methods on TLDR, HelpSteer2, and UltraFeedback, reporting improvements over SFT and robustness for NMD across regularization.

2 Preliminary

The preliminary framework defines generalized preferences, the zero-sum game, the duality gap, and coverage relative to a base policy. It identifies preference-oracle error and universal coverage as the central difficulty parameters.

  • Preference model: The framework uses a base policy πref over responses and an unknown skew-symmetric preference oracle P∗.The proxy oracle bP is also skew-symmetric and estimates pairwise population preferences.
  • Game formulation: The expected win-rate defines a two-player zero-sum game in which the row player maximizes and the column player minimizes.A Nash equilibrium exists under the skew-symmetric preference structure.
  • Evaluation criterion: The duality gap measures a policy’s regret relative to its strongest adversary and weakest dominance under the true preference model.The gap is nonnegative and equals zero at the Nash policy.
  • Objective: The goal is to generate a policy with a small duality gap using the reference policy and imperfect preference oracle.This formalizes inference-time alignment as approximate Nash computation.
  • Coverage: Coverage measures how much a policy reweights probability mass relative to πref, while universal coverage maximizes this quantity over policies.Universal coverage captures the difficulty of recovering a Nash policy from samples drawn under πref.
  • Difficulty factors: Preference-oracle error and universal coverage jointly limit alignment quality: high oracle error or poor response coverage prevents a good Nash approximation.These parameters are presented as fundamental difficulties of inference-time alignment.

3 The Best-of-Nash Algorithm

Best-of-Nash replaces Best-of-N’s scalar-reward selection with an empirical preference-game equilibrium over sampled responses. It uses pairwise preference queries and linear programming, with guarantees controlled by oracle error and coverage.

  • Motivation: Standard Best-of-N selects one sampled response by scalar reward, which can condense preference information and enable reward hacking.BoN instead retains sample-and-rank sampling while using the full pairwise preference structure.
  • Core idea: BoN outputs a distribution over N sampled responses that solves the Nash equilibrium of their empirical preference game.This replaces argmax selection with equilibrium computation.
  • Algorithm: BoN draws N i.i.d. responses from πref and queries the preference oracle on each ordered pair.The resulting preference matrix defines a two-player zero-sum game.
  • Algorithm: The empirical Nash equilibrium is computed by linear programming from the queried preference matrix.The algorithm returns an equilibrium policy supported on the sampled candidate responses.
  • Guarantee: BoN’s duality-gap guarantee is controlled by preference-oracle error ε(x) and universal coverage Cuni(x).The sample-size condition scales with coverage and the inverse oracle-error logarithm.
  • Caveat: An approximate LP solution adds 2ϵLP to the duality-gap bound.The exact-solution theorem therefore has an explicit computational-approximation caveat.

4 The Nash Mirror Descent Algorithm

Nash Mirror Descent replaces Best-of-Nash’s linear program with iterative KL-regularized self-play while preserving the same theoretical duality-gap guarantee. Its practical performance is robust to the regularization parameter.

  • Algorithm: Nash Mirror Descent uses closed-form KL-regularized mirror-descent updates instead of Best-of-Nash’s linear program.The algorithm maintains two coupled policies over sampled responses and iteratively updates them through self-play.
  • Complexity: NMD and BoN have identical query complexity, but NMD replaces BoN’s O(N^3.5 log(1/ϵ)) post-query LP with iterative updates.NMD uses T updates of O(N^2) each, yielding lower post-query computational growth than the LP-based method.
  • Algorithm: NMD samples N responses from the reference policy, initializes two uniform policies, and repeatedly estimates each response’s win probability against the current policy.The estimated win probability is computed from the preference oracle before each update.
  • Guarantee: NMD achieves a duality gap bounded by O(ε(x)Cuni(x)) under the stated parameter settings and sample-size condition.The theorem sets β = 2 and T = ⌈2 log N+1/2 ε(x)Cuni(x)⌉, with an additional lower bound on N.
  • Empirical behavior: NMD’s empirical performance remains flat across β, reducing the need for regularization-parameter tuning.This empirical robustness contrasts with the theory’s prescribed β = 2.

5 Lower Bound

The lower-bound analysis shows that inference-time alignment with general preferences cannot improve beyond the scale ε(x)Cuni(x) in the worst case. Together with the algorithmic upper bounds, this establishes the optimal rate for BoN and NMD.

  • Lower bound: Any inference-time alignment algorithm can incur duality gap Ω(ε(x)Cuni(x)) on constructed problem instances.The lower bound uses preference oracles with controlled error and a uniformly supported reference policy.
  • Lower-bound construction: The construction creates two indistinguishable preference worlds in which opposite responses are dominant, forcing every algorithm to leave a gap of at least δ0.The adversary chooses the larger gap from the algorithm’s probability assignment, minimized at p = 1/2.
  • Optimality: Combining the lower bound with the upper bounds yields the tight optimal rate Θ(ε(x)Cuni(x)) for general-preference inference-time alignment.Both Best-of-Nash and Nash Mirror Descent achieve this rate.
  • Comparison: Unlike reward-based alignment, general-preference alignment depends on universal coverage, making poor base-policy coverage more damaging in this setting.The comparison distinguishes universal coverage from single-policy coverage used in reward-based alignment.

6 Experiments

Experiments on TLDR, HelpSteer2, and UltraFeedback show that BoN and NMD improve over the SFT base policy and approach fine-tuned performance. NMD is also robust to regularization, while its post-query runtime scales more favorably than BoN’s.

  • Main results: BoN and NMD outperform the SFT base policy across all three datasets, improving by roughly 10% on TLDR and approximately 24% on HelpSteer2 and UltraFeedback.The two methods achieve similar expected win-rates across datasets.
  • Main results: BoN and NMD match LLaMA3-DPO’s expected win-rate on TLDR with a reasonable number of samples and without parameter updates.The comparison uses LLaMA3-SFT as the reference policy and LLaMA3-PM as the preference oracle.
  • Sample size and regularization: BoN’s EWR rises from 62.9% at N = 1 to 73.5% at N = 64, approaching the DPO baseline.The observed scaling is consistent with better approximation of the Nash equilibrium as sample size increases.
  • Sample size and regularization: NMD’s EWR remains flat across β, indicating robustness to the regularization parameter and reducing hyperparameter-tuning requirements.The experiments test the regularization parameter on TLDR.
  • Model choices: LLaMA3-PM and the much smaller PairRM produce similar TLDR EWRs, whereas Mistral-Instruct ranks above LLaMA3-SFT and Gemma-SFT among base models.The preference-model comparison fixes LLaMA3-SFT, while the base-model comparison fixes LLaMA3-PM.
  • Runtime: BoN’s post-query time grows rapidly with N, while NMD’s remains nearly flat, matching their respective complexity analyses.Both methods use the same query complexity but differ in post-query computation.

7 Conclusion and Limitations

The paper formulates black-box inference-time alignment under generalized preferences as a two-player zero-sum game and proposes BoN and NMD with tight duality-gap guarantees. It also identifies preference-model error, base-policy coverage, per-prompt analysis, and query cost as important boundaries.

  • Conclusion: BoN and NMD formulate generalized-preference inference-time alignment as computing a Nash equilibrium under an imperfect preference oracle.The methods target black-box alignment without updating model parameters.
  • Conclusion: Both algorithms achieve a duality gap of O(ε(x)Cuni(x)), matching a problem lower bound.Their post-query procedures differ: BoN solves a linear program, whereas NMD performs iterative updates.
  • Limitations: The guarantees depend on preference-model error, and poor proxies can make the methods inherit biases outside the model’s training distribution.The limitation is expressed through ε(x), which measures preference-model quality.
  • Limitations and efficiency: BoN post-query time scales rapidly with N, while NMD remains nearly flat as N grows.Figure 3 compares post-query time for varying candidate-set size N.
  • Limitations: Inference-time alignment cannot recover high-quality responses that the base policy assigns negligible probability, leaving fine-tuning necessary in that case.The methods can only re-weight responses reachable under the base policy.
  • Future directions: Both methods require O(N^2) preference queries, motivating active pair selection to reduce query cost.The paper also suggests combining inference-time theory with fine-tuning and exploiting cross-prompt structure.

B Omitted Proofs from Section 3

The omitted proofs establish BoN’s duality-gap analysis by coupling rejection sampling with a pure best response and comparing the true and estimated preference games. They show that candidate coverage and preference-model error control the resulting bound.

  • BoN proof: The duality gap equals twice the true preference of a pure best response over the returned policy, minus one.This reduction uses the fact that a linear functional over policies is maximized at a point mass.
  • Rejection-sampling coupling: Rejection sampling constructs an intermediate policy concentrated on accepted candidates and the best-response response, enabling comparison with the returned policy.Conditioned on the candidate set, the induced distribution is supported on the sampled candidates.
  • Preference-game comparison: The estimated preference matrix forms a constant-sum game on the sampled candidate set, where the computed Nash equilibrium controls the estimated best-response value.The proof then bounds the discrepancy between estimated and true preference values.
  • Preference-game comparison: The proof combines Nash optimality in the estimated game with the preference-model discrepancy to upper-bound the true best-response probability.The resulting inequality compares the true and estimated preference probabilities against the returned policy.
  • BoN proof: When N is sufficiently large relative to ε(x) and Cuni(x), rejection sampling approximates the pure best response closely enough to yield the stated duality-gap guarantee.The proof bounds the rejection-sampling failure probability through binomial counts and total variation distance.

C Omitted Proofs from Section 4

The omitted NMD proofs use optimistic mirror descent with KL-based Bregman divergence to control iterative updates on the sampled preference game. With suitable β, T, and sample size, they derive the algorithm’s duality-gap bound.

  • NMD analysis: NMD analyzes policies over the sampled candidate set using a KL-divergence mirror-descent framework.The regularizer is written as ψ(π) = Σ_y π(y) log π(y).
  • NMD analysis: The technical lemma bounds the cumulative progress of the optimistic mirror-descent iterates against any comparator policy.This bound is then applied to the sampled preference game.
  • NMD guarantee: Setting β = 2 and T = ⌈(2 log N + 1/2)/ε⌉ provides the iteration schedule used in the NMD guarantee.The schedule is selected for a sufficiently small ε and candidate-set size N.
  • NMD guarantee: Theorem 2 establishes NMD’s duality-gap result when N is at least 4 log(2/ε(x)) · Cuni(x).The displayed theorem statement supplies the required sample-size condition.
  • NMD guarantee: The proof transfers the iterative bound to the true preference game through the rejection-sampling comparison used for the sampled candidate set.The resulting argument bounds the best-response probability against the returned policy.

D Omitted Proofs from Section 5

The lower-bound proof constructs two preference worlds that are difficult to distinguish through an imperfect oracle, forcing any alignment algorithm to retain a nonzero duality gap. The construction uses a dominant response under the estimated preferences but different true-preference winners.

  • Lower-bound setup: Theorem 3 constructs preference oracles with ε(x) = ε0 for which every alignment algorithm faces a nonzero lower bound.The reference policy is uniform over K responses, so Cuni(x) = K.
  • Two-world construction: Under the estimated oracle, y1 is the unique dominant strategy, while the true oracle is allowed to differ in two constructed worlds.The two worlds agree with the estimated oracle except on selected comparisons.
  • Two-world construction: In World A, y1 remains dominant, whereas in World B, y2 beats y1 and becomes dominant.These alternatives make the same estimated preference information compatible with different true-preference optima.
  • Lower-bound argument: The duality-gap lower bounds in the two worlds depend on the algorithm’s probability p of selecting y1.The adversary chooses the worse world for the algorithm, and the algorithm minimizes the worst case at p = 1/2.
  • Evaluation implementation: The empirical preference judgments use DeepSeek-V4-Flash with temperature 0 and at most four output tokens, under a fixed pairwise comparison prompt.The judge outputs exactly one character indicating which response is better.

E.2 Additional Experiments

Additional experiments compare BoN and NMD with Borda and reward-based selectors, and with a fine-tuned Nash-MD baseline. The results examine when methods agree and whether inference-time equilibrium computation outperforms alternative selection and fine-tuning approaches.

  • Experimental comparisons: The experiments compare BoN and NMD with Borda Best-of-N, standard reward-based Best-of-N, and fine-tuned Nash-MD.These comparisons use preference datasets and held-out HelpSteer2 prompts, with tables reporting expected win-rate comparisons.
  • Borda comparison: In 73.8% of N = 64 sub-samples, the Borda winner is also a Condorcet winner, causing Borda Best-of-N and Nash methods to return the same response.On the remaining non-Condorcet sub-samples, argmax-style rules carry no guarantee.
  • Reward-based comparison: Best-of-Nash attains a 4.0% higher win rate than reward-based Best-of-N.The reward-based selector uses a fine-tuned Bradley–Terry reward model, while the methods are compared under matched candidate-generation settings.
  • Fine-tuned Nash-MD comparison: Against fine-tuned Nash-MD-PG on HelpSteer2, fine-tuning reaches 40.5% EWR, while BoN and NMD reach 50.5% and 52.0%.All three methods use the same preference model in this comparison, while BoN and NMD make no parameter updates.
  • Fine-tuned Nash-MD comparison: Nash-MD’s gain comes largely from converting losses into draws, whereas BoN and NMD raise the outright win rate.Nash-MD has a 59.0% draw rate versus 42.3% for the base policy, while the inference-time methods increase wins themselves.
Loading 2609.08082v1…