Paper deep dive
Inference-Time Nash Alignment
Hadi Hosseini, Debmalya Mandal, Duohan Zhang
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 9/13/2026, 6:14:17 AM
Summary
This paper introduces Inference-Time Nash Alignment, a framework for aligning Large Language Models (LLMs) at inference time without updating model parameters, addressing the limitations of existing methods that rely on scalar reward models and white-box access. The authors propose two algorithms, Best-of-Nash (BoN) and Nash Mirror Descent (NMD), which formulate alignment as finding a Nash equilibrium in a two-player zero-sum game under generalized preferences. Theoretical analysis proves that both algorithms achieve a duality gap matching the problem lower bound, dependent on preference oracle error and data coverage. Empirical results on TLDR, HelpSteer2, and UltraFeedback datasets demonstrate that these methods outperform base policies and converge to the performance of fine-tuned models, with NMD showing robustness across regularization parameters.
Entities (12)
Relation Signals (12)
Nash Mirror Descent → evaluatedon → HelpSteer2
confidence 95% · We evaluate our proposed mechanisms BoN and NMD on three preference datasets: TLDR, HelpSteer2, and UltraFeedback.
Best-of-Nash → evaluatedon → TL;DR
confidence 95% · We evaluate our proposed mechanisms BoN and NMD on three preference datasets: TLDR, HelpSteer2, and UltraFeedback.
Best-of-Nash → evaluatedon → UltraFeedback
confidence 95% · We evaluate our proposed mechanisms BoN and NMD on three preference datasets: TLDR, HelpSteer2, and UltraFeedback.
Best-of-Nash → isa → Inference-Time Alignment Method
confidence 95% · We propose two algorithms: Best-of-Nash (BoN) and Nash Mirror Descent (NMD).
Nash Mirror Descent → isa → Inference-Time Alignment Method
confidence 95% · We propose two algorithms: Best-of-Nash (BoN) and Nash Mirror Descent (NMD).
Inference-Time Alignment → avoids → Model Parameter Updates
confidence 93% · Inference-time alignment offers a cost-effective alternative without updating model parameters.
Nash Mirror Descent → achieves → Nash Equilibrium
confidence 92% · Nash Mirror Descent... a self-play algorithm that achieves the same duality gap bound
Best-of-Nash → achieves →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2609.08082v1
- Canonical: https://arxiv.org/abs/2609.08082v1
Trouble viewing inline? Open PDF directly →
Full Text
73,799 characters extracted from source content.
Expand or collapse full text
Inference-Time Nash Alignment Hadi Hosseini Affiliation: Penn State University, USA Email: hadi@psu.edu Debmalya Mandal Affiliation: University of Warwick, UK Email: Debmalya.Mandal@warwick.ac.uk Duohan Zhang †thanks: Corresponding author. Affiliation: Penn State University, USA Email: dqz5235@psu.edu Abstract 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 Preference-based fine-tuning methods such as Reinforcement Learning with Human Feedback (RLHF) (Christiano et al., 2017) and Direct Preference Optimization (DPO) (Rafailov et al., 2023) have become quintessential for aligning Large Language Models (LLMs) with human preferences. These methods have proven highly effective across several domains including mathematical reasoning and finance. However, they require substantial effort in acquiring high-quality human data, along with considerable computational costs for training LLMs. For example, fine-tuning LLMs with either Proximal Policy Optimization (PPO) (Schulman et al., 2017) or Group Relative Policy Optimization (GRPO) (Shao et al., 2024) requires a large number of samples and often leads to instability in training. Equally importantly, these approaches rely on white-box access to model parameters, whereas many state-of-the-art models (e.g., GPT-5.4 Thinking (OpenAI, 2026), Gemini 3.1 Pro (Google, 2026), and Claude Opus 4.7 (Anthropic, 2026)) are only accessible as black-box APIs. To bridge this gap, inference-time alignment has recently drawn much attention. Unlike preference-based fine-tuning, inference-time alignment modifies the generation process at run time without updating model parameters. A popular line of work adopts a sample-and-rank paradigm, of which Best-of-N sampling (Stiennon et al., 2020; Nakano et al., 2021; Huang et al., 2025) is the most widely used – N candidate responses are drawn for a given prompt and the one with the highest score under a reward model is returned. While simple in its nature, Best-of-N alignment is vulnerable to reward hacking: as N grows, the estimated reward of the selected response increases monotonically while its true task performance can degrade (Gao et al., 2023; Stroebl et al., 2024; Chow et al., 2024). This phenomenon arises because reward model is at best an imperfect proxy for the true human preference distribution, a manifestation of Goodhart’s law. Furthermore, most inference-time methods exclusively assume that preferences can be modeled by a scalar reward function under the Bradley-Terry model (Bradley and Terry, 1952). This assumption is restrictive: even when individual preferences are transitive, aggregated group-level preferences need not be (Munos et al., 2024). Generalized preference models, which directly specify a probability that one response is preferred to another, have recently been studied for fine-tuning in, e.g., Nash Learning from Human Feedback (NLHF) (Munos et al., 2024). To the best of our knowledge, tackling generalized preferences remains an open challenge in inference-time methods. In this work, we initiate the study of black-box inference-time alignment under generalized preferences. The preference model ℙ∗P^* takes two responses y and y′y conditioned on a prompt x, and evaluates the score ℙ∗(y≻y′|x)P^*(y y |x) as the probability that a randomly chosen human prefers response y over y′y given prompt x. Then we formulate inference-time alignment with generalized preferences as a two-player zero-sum game ℙ∗(π≻π′|x):=y∼π,y′∼π′ℙ∗(y≻y′|x)P^*(π π |x):=E_y π,y π P^*(y y |x) between row player’s policy π and column player’s policy π′π under the true preference ℙ∗P^*. However, we do not have access to ℙ∗P^*, and instead, use an imperfect preference model ℙ P (e.g. one learned from preference data (Jiang et al., 2023; Dong et al., 2024; Munos et al., 2024)) to query at inference time. Specifically, we ask the following question: Given a base policy πref _ref from which we can query responses and an imperfect preference model ℙ P, can we design an efficient algorithm to approximate the Nash equilibrium at inference time? 1.1 Our Contributions Prior work has explored Nash-based objectives in the fine-tuning setting (Munos et al., 2024) and has separately identified reward hacking as a key vulnerability of inference-time methods like Best-of-N (Stroebl et al., 2024; Chow et al., 2024). We connect these two threads by proposing new inference-time methods with general preference models that achieve optimal regret. On the technical front, we link the alignment problem to the policy coverage and preference model error, which we will define formally in Section 2. In particular, our main contributions are the following. 1. Best-of-Nash (BoN): We propose Best-of-Nash Alignment method which computes a minimax solution from N samples according to an estimate of the preference matrix ℙ P. We show that the duality gap of BoN alignment is at most O(ε(x)uni(x))O( (x)C_uni(x)) on a given prompt x, where ε(x) (x) is the error in the preference oracle, and uni(x)C_uni(x) is a measure of data coverage. 2. Nash Mirror Descent (NMD): As a more computationally efficient alternative, we propose Nash Mirror Descent, a self-play algorithm that takes a KL-regularized mirror descent step iteratively. We show that NMD is faster to implement, and the upper bound on the duality gap of NMD is at most O(ε(x)uni(x))O( (x)C_uni(x)), matching the exact Best-of-Nash bound. 3. Matching Lower Bound: We then show that the upper bound of BoN and NMD is essentially optimal by constructing problem instances with lower bound at least Ω(ε(x)uni(x)) ( (x)C_uni(x)). 4. Experimental Evaluation: We evaluate our proposed mechanisms BoN and NMD on three preference datasets: TLDR, HelpSteer2, and UltraFeedback. We show that both methods substantially improve over the SFT base model, and match the win-rate of the fine-tuned alternative on TLDR. We also show that the win-rates of NMD are robust across the regularization parameter, removing the need for hyperparameter tuning. 1.2 Related Work Fine-tuning with General Preferences. Azar et al. (2024) initiated the study of general preferences in LLM fine-tuning, and proposed an algorithm that maximizes the KL-regularized objective against a fixed policy. A subsequent line of works (Munos et al., 2024; Ye et al., 2024; Calandriello et al., 2024; Rosset et al., 2024; Wu et al., 2024; Zhang et al., 2024; Zhang et al., 2025; Swamy et al., 2024; Zhou et al., 2025) formulated the alignment problem as a two-player zero-sum game, and proposed fine-tuning algorithms to learn the Nash policy. Maura-Rivero et al. (2025) connected this line of works to social choice theory, showing that the Nash policy approximates maximal lottery outcomes. Inference-Time Alignment and Reward Hacking. Best-of-N sampling is a popular inference-time alignment approach, but it is vulnerable to reward hacking problem (Skalse et al., 2022), when an LLM exploits the learned reward model rather than the ground-truth reward. Huang et al. (2025) showed that Best-of-N incurs suboptimal regret relative to the problem’s lower bound, and proposed a χ2χ^2-regularized algorithm that implements pessimism in the face of uncertainty to close this gap. Yu et al. (2026) took a different route, using lower confidence bounds on value estimates to mitigate reward hacking. Gui et al. (2024) combined RLHF with Best-of-N sampling to improve fine-tuning, however, they are concerned with reward-based setting. Finally, there is inference-time method based on search (Khanov et al., 2024; Yao et al., 2023) and rejection sampling (Chen et al., 2024; Shi et al., 2024), but these approaches don’t handle general preferences. Learning in Zero-sum Games. The central ingredient of our approach is no-regret learning algorithm for solving zero-sum games. Freund and Schapire (1999) showed that multiplicative weights update has no-regret guarantee. We use Mirror descent algorithm (Nemirovski, 2004; Nesterov, 2009; Rakhlin and Sridharan, 2013) for inference-time alignment. Our second algorithm is inspired by the optimistic variants of Mirror descent algorithm (Rakhlin and Sridharan, 2013). Mirror Prox algorithm in Nemirovski (2004) is an extragradient type of method and closely related to optimistic MD (with similar convergence rate). It queries the gradient twice whereas we use the same gradient twice (predicted and current). 2 Preliminary Denote X as the prompt space and Y as the response space. We begin with a base policy πref:→Δ() _ref:X→ (Y), where πref(y|x) _ref(y|x) is the probability that the base policy πref _ref generates a response y given the prompt x. We also assume that there exists an unknown true preference oracle ℙ∗:×→[0,1]P^*:X×Y×Y→[0,1], where ℙ∗(y≻y′|x)P^*(y y |x) denotes the probability that the population prefers response y to y′y given a prompt x. We assume that the preference model is skew-symmetric: ℙ∗(y≻y′|x)+ℙ∗(y′≻y|x)=1,∀x,y,y′,P^*(y y |x)+P^*(y y|x)=1,∀ x,y,y , which implies ℙ∗(y≻y|x)=1/2P^*(y y|x)=1/2. As a proxy, we have access to an imperfect preference oracle ℙ^:×→[0,1] P:X×Y×Y→[0,1], also assumed skew-symmetric. For a given prompt x, we measure the quality of the oracle ℙ P via the square error with respect to ℙ∗P^*, where responses are drawn independently from the base policy πref _ref: ε2(x):=y∼πref(⋅|x),y′∼πref(⋅|x)[(ℙ^(y≻y′|x)−ℙ∗(y≻y′|x))2]. ^2(x):=E_y _ref(·|x),y _ref(·|x)[( P(y y |x)-P^*(y y |x))^2]. Nash Equilibrium and Duality Gap. We formulate the problem as a two-player zero-sum game. Given row player’s policy π and column player’s policy π′π , we denote the expected win-rate as ℙ∗(π≻π′|x):=y∼π(⋅|x),y′∼π′(⋅|x)[ℙ∗(y≻y′|x)].P^*(π π |x):=E_y π(·|x),y π (·|x)[P^*(y y |x)]. Here the row player aims to maximize the win-rate, and the column player aims to minimize the win-rate. It is well-known that there exists a Nash Equilibrium (NE) of the game: π1∗,π2∗:=argmaxπ1argminπ2ℙ∗(π1≻π2|x). _1^*, _2^*:=argmax_ _1argmin_ _2P^*( _1 _2|x). We denote the Nash Equilibrium as π∗=π1∗=π2∗π^*= _1^*= _2^* due to the skew-symmetric nature of ℙ∗P^*. To measure how close a given policy π is to π∗π^*, we use the duality gap. It captures the regret of policy π as the gap between its strongest adversary and its weakest dominance under the true preference model: DualGap(π):=maxπ1ℙ∗(π1≻π|x)−minπ2ℙ∗(π≻π2|x) (π):= _ _1P^*( _1 π|x)- _ _2P^*(π _2|x) The duality gap is nonnegative and DualGap(π)=0 (π)=0 if π=π∗π=π^*. Now given a reference policy πref _ref, an imperfect preference oracle ℙ P, and a prompt x∈x , our goal is to generate a high-quality policy π π with small duality gap: DualGap(π^)≤ϵ. ( π)≤ε. We say π π is an ϵε-approximate Nash policy. Universal Coverage. Coverage plays a significant role in the analysis of inference-time alignment (Huang et al., 2025). It measures how much a policy, π concentrates probability mass relative to a reference policy, πref _ref, upweighting outcomes that are more likely under π. We define the coverage of policy π as the ratio of π(y|x)π(y|x) over πref(y|x) _ref(y|x), where y is sampled from π(⋅|x)π(·|x): π(x):=y∼π(⋅|x)[π(y|x)πref(y|x)].C^π(x):= E_y π(·|x) [ π(y|x) _ref(y|x) ]. Coverage is closely related to the chi-square divergence: a direct calculation gives χ2(π(⋅|x),πref(⋅|x))=π(x)−1,χ^2(π(·|x), _ref(·|x))=C^π(x)-1, where the chi-square divergence is defined as χ2(π(⋅|x),π′(⋅|x))=y∼π′(⋅|x)[(π(y|x)π′(y|x)−1)2]χ^2(π(·|x),π (·|x))=E_y π (·|x)[( π(y|x)π (y|x)-1)^2]. Thus, we have π(x)≥1C^π(x)≥ 1 and the equality holds if and only if π(y|x)=πref(y|x)π(y|x)= _ref(y|x) for all y. Inspired by literature in offline learning in zero-sum games (Cui and Du, 2022; Zhong et al., 2022; Zhang et al., 2023), we also define the universal coverage as the maximum coverage over any policy: uni(x):=maxπy∼π(⋅|x)[π(y|x)πref(y|x)].C_uni(x):= _π E_y π(·|x) [ π(y|x) _ref(y|x) ]. Intuitively, uni(x)C_uni(x) captures the difficulty of recovering a Nash policy from samples drawn under πref _ref. The two quantities ε(x) (x) and uni(x)C_uni(x) are the fundamental difficulty of inference-time alignment: no algorithm can output a good Nash approximation when the preference oracle ℙ P has high error or when πref _ref poorly covers the response space. 3 The Best-of-Nash Algorithm The inference-time Best-of-N alignment method relies on a scalar reward function by drawing N samples from policy πref _ref and selecting a single response by taking the argmaxargmax under a reward model. However, it condenses the preference information into one number and could result in reward hacking. We propose an alternative approach, namely Best-of-Nash (Algorithm 1), that retains the sample-and-rank structure, but replaces the argmaxargmax with an equilibrium computation solely based on preference data: instead of picking one response, we output a distribution over the N samples that solves the Nash equilibrium of the empirical preference game. Formally, given an input x, we draw N candidate responses ^N=(y1,…,yN)∼πref(⋅|x) Y_N=(y_1,…,y_N) _ref(·|x) i.i.d. We then construct a probability matrix by querying ℙ P on each ordered pair, i.e. ℙ^(yi≻yj) P(y_i y_j) for 1≤i≤j≤N1≤ i≤ j≤ N. The Nash equilibrium of the resulting two-player zero-sum game can be computed by Linear Programming (LP) (Adler, 2013). Algorithm 1 Best-of-Nash (BoN) Alignment 1: Input: Prompt x, reference policy πref _ref, preference oracle ℙ P, sample size N. 2: Draw ^N=(y1,…,yN)∼πref(⋅|x) Y_N=(y_1,…,y_N) _ref(·|x) i.i.d. 3: Query P^ij←ℙ^(yi≻yj∣x) P_ij← P(y_i y_j x) for all 1≤i<j≤N1≤ i<j≤ N, and set P^ji←1−P^ij P_ji← 1- P_ij, P^ii←12 P_i← 12. 4: Compute a Nash Equilibrium π π by solving the linear program maxπ∈Δ(^N),v∈ℝvs.t.∑j=1Nπ(yj)P^ji≥v∀i∈[N]. _π∈ ( Y_N),\,v v .t. _j=1^Nπ(y_j)\, P_ji≥ v ∀\,i∈[N]. 5: Return π π. We provide the duality gap guarantee for BoN. The bound depends on the two fundamental parameters: the preference-oracle error ε(x) (x) and the universal coverage uni(x)C_uni(x). Theorem 1. For any prompt x, the policy π π returned by Algorithm 1 satisfies DualGap(π^)≤3ε(x)uni(x) ( π)≤ 3 (x)C_uni(x) when N≥4log(2ε(x))⋅uni(x)N≥ 4 ( 2 (x))·C_uni(x). We provide the full proof below, and defer omitted lemmas to Appendix B. Proof. We omit the dependence on x for cleanliness. From now on we write S:=NS:=Y_N as the candidate set, and we write π^S π_S to denote the dependence on S. By skew-symmetry of the zero-sum game, it suffices to upper-bound ℙ∗(π~S≻π^S)−1/2P^*( π_S π_S)-1/2, where π~S:=δy∗ π_S:= _y^* with y∗∈argmaxyℙ∗(y≻π^S∣x)y^*∈ _yP^*(y π_S x). The central difficulty is a support mismatch: π^S π_S is supported on the N sampled responses, while π~S π_S may place mass anywhere in Y. To bridge this, we introduce πR,S _R,S, the distribution induced by approximate rejection sampling (Block and Polyanskiy, 2023; Huang et al., 2025) of π~S π_S from πref _ref. Specifically, we denote πR,S _R,S as the distribution induced by RejectionSamplingN−1,M(π~Sπref,πref,x)RejectionSampling_N-1,M( π_S _ref; _ref,x) (Algorithm 3) as an approximation to π~ π. Then we decompose the probability that ℙ∗(π~S≻π^S)≤ℙ∗(πR,S≻π^S)+|ℙ∗(π~S≻π^S)−ℙ∗(πR,S≻π^S)|.P^*( π_S π_S) ^*( _R,S π_S)+|P^*( π_S π_S)-P^*( _R,S π_S)|. We bound the first term ℙ∗(πR,S≻π^S)≤12+ε(x)uni(x)P^*( _R,S π_S)≤ 12+ (x)C_uni(x) by Lemma 1. Then we bound the second term |ℙ∗(π~S≻π^S)−ℙ∗(πR,S≻π^S)| |P^*( π_S π_S)-P^*( _R,S π_S)| ≤∑y|π~S(y)−πR,S(y)|∑y′π^S(y′)ℙ∗(y≻y′) ≤ _y| π_S(y)- _R,S(y)| _y π_S(y )P^*(y y ) ≤∑y|π~S(y)−πR,S(y)| ≤ _y| π_S(y)- _R,S(y)| ≤2DTV(π~S,πR,S), ≤ 2D_TV( π_S, _R,S), where the total-variation distance is defined as DTV(π,π′):=12∑y|π(y)−π′(y)|D_TV(π,π ):= 12 _y|π(y)-π (y)|. Thus, the second term is reduced to the TV distance between π~S π_S and πR,S _R,S, and then can be bounded due to the fact that πR,S _R,S is an approximation to π~S π_S. By Lemma 2, We have DTV(π~S,πR,S)≤14ε2(x)uni(x)D_TV( π_S, _R,S)≤ 14 ^2(x)C_uni(x) by setting M=N−1log(4/ε2(x))M= N-1 (4/ ^2(x)) and N≥4log(2ε(x))⋅uni(x)N≥ 4 ( 2 (x))·C_uni(x). By aggregating the bounds for both terms, we derive the upper bound DualGap(π^S) ( π_S) ≤2ℙ∗(π~S≻π^S)−1 ≤ 2 P^*( π_S π_S)-1 ≤2(ε(x)uni(x)+12ε2(x)uni(x)) ≤ 2( (x)C_uni(x)+ 12 ^2(x)C_uni(x)) ≤3ε(x)uni(x). ≤ 3 (x)C_uni(x). For any fixed y, linearity gives ℙ∗(y≻π^)=ℙ∗(y≻S[π^S])=S[ℙ∗(y≻π^S)].P^*(y π)=P^*(y _S[ π_S])=E_S[P^*(y π_S)]. Finally, we take the expectation over the randomness of S: DualGap =2maxyS[ℙ∗(y≻π^S)]−1 =2 _yE_S[P^*(y π_S)]-1 ≤2S[maxyℙ∗(y≻π^S)]−1 ≤ 2E_S[ _yP^*(y π_S)]-1 =S[DualGap(π^S)] =E_S[ ( π_S)] ≤3ε(x)uni(x) ≤ 3 (x)C_uni(x) and the proof is complete. ∎ Remark 1. In Theorem 1 we assume that the LP solution is exact. When Algorithm 1 returns an ϵLP _LP-approximation equilibrium, then we have DualGap≤3ε(x)uni(x)+2ϵLP ≤ 3 (x)C_uni(x)+2 _LP. 4 The Nash Mirror Descent Algorithm Best-of-Nash requires solving a linear programming with post-query time O(N3.5log(1/ϵ))O(N^3.5 (1/ε)) via interior-point methods. In this section, we propose Nash Mirror Descent (Algorithm 2), a self-play algorithm that achieves the same duality gap bound while replacing the LP with a sequence of closed-form updates. NMD is inspired by Rakhlin and Sridharan (2013) for solving zero-sum games. The algorithm maintains two coupled policies: πt _t and πt′π _t, both supported on the N sampled responses. At each iteration, πt+1′ _t+1 takes a mirror-descent step from πt _t while staying close to πt′π _t: πt+1′=argmaxπ∈Δ(N)ℙ^(π≻πt|x)−β⋅KL(π,πt′),π _t+1=argmax_π∈ (Y_N) P(π _t|x)-β·KL(π,π _t), and πt+1 _t+1 takes the same mirror descent step but stays close to πt+1′π _t+1: πt+1=argmaxπ∈Δ(N)ℙ^(π≻πt|x)−β⋅KL(π,πt+1′). _t+1=argmax_π∈ (Y_N) P(π _t|x)-β·KL(π,π _t+1). Here πt+1′π _t+1 aims to maximize the (estimated) probability that it wins against policy πt _t, with an KL regularization term ensuring staying close to πt′π _t (KL divergence is defined as KL(π,π′):=∑yπ(y)log(π(y)π′(y))KL(π,π ):= _yπ(y) ( π(y)π (y))). Both updates admit closed-form solutions. Denote r^t(y):=ℙ^(y≻πt|x)=y′∼πt[ℙ^(y≻y′|x)],∀y∈N r_t(y):= P(y _t|x)=E_y _t[ P(y y |x)],∀ y _N, we have πt+1′=argmaxπ∈Δ(N)∑ir^t(yi)π(yi)−β⋅∑iπ(yi)log(π(yi)πt′(yi)),π _t+1=argmax_π∈ (Y_N) _i r_t(y_i)π(y_i)-β· _iπ(y_i) ( π(y_i)π _t(y_i)), and the solution is πt+1′(yi)=πt′(yi)exp(r^t(yi)/β)∑jπt′(yj)exp(r^t(yj)/β).π _t+1(y_i)= π _t(y_i) ( r_t(y_i)/β) _jπ _t(y_j) ( r_t(y_j)/β). Algorithm 2 Nash Mirror Descent Alignment 1: Input: Prompt x, reference policy πref _ref, preference oracle ℙ P, sample size N, regularization parameter β. 2: Sample N data N=y1,y2,…,yNY_N=\y_1,y_2,…,y_N\ i.i.d. from πref(⋅|x) _ref(·|x). 3: Initialize π1′π _1 and π1 _1 as the uniform distribution on NY_N. 4: for t=1,…,T−1t=1,…,T-1 do 5: Calculate r^t(y)=ℙ^(y≻πt|x)=y′∼πt[ℙ^(y≻y′|x)],∀y∈N r_t(y)= P(y _t|x)=E_y _t[ P(y y |x)],∀ y _N. 6: Calculate πt+1′=argmaxπ∈Δ(N)⟨π,r^t⟩−β⋅KL(π||πt′)π _t+1=argmax_π∈ (Y_N) π, r_t -β·KL(π||π _t). 7: Calculate πt+1=argmaxπ∈Δ(N)⟨π,r^t⟩−β⋅KL(π||πt+1′) _t+1=argmax_π∈ (Y_N) π, r_t -β·KL(π||π _t+1). 8: end for 9: Calculate π^(y|x)=1T∑t=1Tπt(y|x),∀y∈N π(y|x)= 1T _t=1^T _t(y|x),∀ y _N. 10: Return π π. Theorem 2. For any prompt x, by setting β=2β=2, T=⌈2logN+1/2ε(x)uni(x)⌉T= 2 N+1/2 (x)C_uni(x) , the policy π π returned by Algorithm 2 has the duality gap DualGap(π^)≤5ε(x)uni(x). ( π)≤ 5 (x)C_uni(x). when N≥4log(2ε(x))⋅uni(x)N≥ 4 ( 2 (x))·C_uni(x). We provide a proof sketch below, and defer the whole proof to Appendix C. Proof Sketch. The structure parallels the proof of Theorem 1. By the skew-symmetry of the zero-sum game, it suffices to upper-bound ℙ∗(π~≻π^)−1/2P^*( π π)-1/2, where π~:=δy∗ π:= _y^* with y∗∈argmaxyℙ∗(y≻π^∣x)y^*∈ _yP^*(y π x). Introducing the rejection-sampling approximation πR _R, we decompose ℙ∗(π~≻π^)≤ℙ∗(πR≻π^)+|ℙ∗(π~≻π^)−ℙ∗(πR≻π^)|.P^*( π π) ^*( _R π)+ |P^*( π π)-P^*( _R π) |. The second term is controlled by the property of approximate rejection sampling, similarly to that in Theorem 1. For the first term, we further decompose ℙ∗(πR≻π^)≤ℙ^(πR≻π^)+|ℙ^(πR≻π^)−ℙ∗(πR≻π^)|,P^*( _R π)≤ P( _R π)+ | P( _R π)-P^*( _R π) |, bounding the empirical term via the cumulative-regret guarantee of Nash Mirror Descent on the game ℙ P, and the transfer term by uni(x)ε(x)C_uni(x) (x). ∎ Remark 2. Our theory prescribes a specific β=2β=2. In practice, our experiments (Section 6) show that the performance of NMD is empirically robust to the choice of β. Remark 3 (Comparison of BoN and NMD). Theorem 1 and Theorem 2 give the same duality gap bound O(ε(x)uni(x))O( (x)C_uni(x)), and both algorithms share the same query complexity: O(N)O(N) samples from πref _ref and O(N2)O(N^2) preference queries to ℙ P. The two algorithms differ in post-query complexity: BoN solves an LP in O(N3.5log(1/ϵ))O(N^3.5 (1/ε)) time, while NMD runs T=O(log(N)ε(x)uni(x))T=O( (N) (x)C_uni(x)) updates of O(N2)O(N^2) each, for a total of O(N2logNε(x)uni(x))O( N^2 N (x)C_uni(x)). 5 Lower Bound The upper bounds in Theorems 1 and 2 show that both BoN and NMD achieve duality gap O(ε(x)uni(x))O( (x)C_uni(x)) with an appropriate choice of parameters. A natural question is whether this rate is optimal. In this section, we answer this affirmatively by constructing problem instances on which any inference-time algorithm must incur duality gap Ω(ε(x)uni(x)) ( (x)C_uni(x)). Theorem 3. Given a prompt x and K responses y1,…,yK\y_1,…,y_K\, let πref(yi|x)=1/K _ref(y_i|x)=1/K for all i∈[K]i∈[K]. For any alignment algorithm A and any ε0∈(0,2/(3K)] _0∈(0, 2/(3K)], there exist preference oracles ℙ∗P^* and ℙ P with ε(x)=ε0 (x)= _0 such that: DualGap((ℙ^))≥ε0⋅uni(x)22. (A( P))≥ _0·C_uni(x)2 2. Proof Sketch. We set the construction: ℙ^(y1≻yj)=12+δ0,∀j≥2 P(y_1 y_j)= 12+ _0,∀ j≥ 2, and ℙ^(yj≻yk)=12,∀j,k≥2 P(y_j y_k)= 12,∀ j,k≥ 2 for a small value δ0=ε0uni(x)/(22) _0= _0C_uni(x)/(2 2). This makes y1y_1 the dominant strategy under ℙ P. We assume that p:=π^(y1)p:= π(y_1). Then we construct two real worlds A and B. In world A, ℙA∗P^*_A amplifies y1y_1’s margin over y2y_2, keeping y1y_1 dominant. In world B, ℙB∗P^*_B flips the (y1,y2)(y_1,y_2) entry so that y2y_2 narrowly beats y1y_1, making y2y_2 the new dominant strategy. The duality gaps in the two worlds scale as 2(1−p)δ02(1-p) _0 and 2pδ02p _0 respectively, and the adversary picks the larger. The algorithm minimizes the maximum at p=1/2p=1/2, leaving a duality gap of at least δ0=ε0uni(x)/(22) _0= _0C_uni(x)/(2 2). ∎ The full proof is relegated to Appendix D. Remark 4 (Optimality of BoN and NMD). Combining Theorem 3 with Theorem 1 and Theorem 2 yields a tight characterization: the optimal duality gap for inference-time alignment with general preferences is Θ(ε(x)uni(x)) ( (x)C_uni(x)), achieved by both of our algorithms. Remark 5 (Contrast with reward-based alignment.). The duality gap Ω(ε(x)uni(x)) ( (x)C_uni(x)) stands in sharp contrast to the optimal rate for the reward-based inference time alignment, which (Huang et al., 2025) show is Θ(εRM(x)π∗(x)) ( _RM(x) C^π^*(x)). Here εRM(x) _RM(x) is the reward model error, and π∗π^* is the comparator policy. Two structural differences are notable. First, the coverage dependence is linear in uni(x)C_uni(x) in our setting versus π∗(x) C^π^*(x) in the reward setting. This implies that bad coverage of the base policy hurts more when preferences are general than when they are scalar. Second, our relevant coverage quantity is the universal coverage uni(x)C_uni(x), not single-policy coverage π∗C^π^*, reflecting that inference-time alignment with general preferences is fundamentally harder than its reward-based counterpart. 6 Experiments We evaluate our proposed alignment algorithms, Best-of-Nash and Nash Mirror Descent, on three datasets and study how their performance varies with sample size N, regularization parameter β, and the choice of base models and preference models. 6.1 Setup Datasets and Models. We conduct experiments on three preference datasets that are commonly used for training and evaluating LLM alignment: TLDR (text summarization), HelpSteer2 (general-purpose helpfulness) (Wang et al., 2024b), and UltraFeedback (Cui et al., 2023) (instruction following). We sample 100100 prompts for evaluation in each dataset. In our experiments, we consider three supervised fine-tuned (SFT) models as base models: LLaMA3-SFT (8B) (Dong et al., 2024), Mistral-Instruct (7B), and Gemma-SFT (2B). Two aligned models are selected as our estimate preference oracle, ℙ P: LLaMA3-PM (8B) (Dong et al., 2024) and PairRM (0.4B) (Jiang et al., 2023). Evaluation. Our headline metric is expected win rate (EWR := win + draw/2). Results in the main paper mainly use LLaMA3-SFT as the base model until otherwise stated. We also compare results to LLaMA3-DPO (8B), a fine-tuned version of LLaMA3-SFT, to illustrate the performance of our algorithm against a model fine-tuned on preference data. We use an LLM as a judge (zheng2023judging) since alignment is inherently preference-based, and LLMs provide a scalable and consistent proxy for human evaluations of model outputs. Concretely, we compare each generated response against a reference answer from the dataset, with judgments produced by DeepSeek-V4-Flash. To control positional bias (zheng2023judging; Wang et al., 2024a), we query the judge twice per pair with orderings swapped, counting a win/loss only when both orderings agree and a draw otherwise. 6.2 Main Results. Dataset Base SFT BoN NMD TLDR 62.9% 73.5% 73.1% HelpSteer2 44.1% 68.8% 67.8% UltraFeedback 23.9% 48.8% 46.7% Table 1: Comparison of expected win-rate (EWR) across three datasets. BoN and NMD sample N=64N=64 responses from LLaMA3-SFT and we use LLaMA3-PM as preference model; β=1β=1 for NMD. 11footnotetext: LLaMA3-DPO model was fine-tuned on HelpSteer2 and UltraFeedback, making direct comparison unfair on these datasets. Table 1 presents our headline comparison: BoN and NMD against the SFT base policy across all three datasets. Both BoN and NMD outperform the base SFT across all three datasets: both algorithms have an improvement of roughly 10%10\% in TLDR, and ≈24%≈ 24\% in HelpSteer2 and UltraFeedback. BoN and NMD have similar expected win-rates on all three datasets, consistent with the theoretical guarantees in Theorem 1 and Theorem 2. Comparison to DPO Figure 1 shows that BoN and NMD match the expected win-rate of LLaMA3-DPO with a reasonable number of samples, without any parameter updates. This suggests that careful inference-time alignment can substitute for fine-tuning when the preference oracle is sufficiently strong. Sample size N and regularization β. Figure 1(a) shows BoN’s expected win-rate on TLDR as N increases. EWR rises monotonically from 62.9%62.9\% at N=1N=1 to 73.5%73.5\% at N=64N=64, approaching the DPO baseline. This confirms the predicted scaling: with more samples, BoN better approximates the Nash equilibrium. Figure 1(b) shows that NMD’s EWR is flat across β, thus removing the need for hyper-parameter tuning. (a) BoN with varying sample size N. (b) NMD with varying β and fixed N=64N=64. Figure 1: Win/Draw/Lose distribution and expected win-rate (Win + Draw/2) on the TLDR dataset. The dashed line indicates the baseline score for LLaMA3-DPO. We use LLaMA3-SFT as the reference policy and LLaMA3-PM as the preference oracle ℙ P. Figure 2: Win/Draw/Lose distribution on the TLDR dataset. Left: we compare the Llama3-PM and PairRM for preference model, with the base model = LLama3-SFT. Right: we compare LLama3-SFT, Mistral-instruct, and Gemma-SFT for base model, with the preference model = LLama3-PM. Preference oracle and base model. We show the effect of the preference model ℙ P and base model πref _ref in Figure 2. The left panel compares LLaMA3-PM (8B) and PairRM (0.4B) as the preference oracle with LLaMA3-SFT fixed as the base model: despite the 20 times difference in size, the two yield rather similar EWRs on TLDR for both BoN and NMD. The right panel compares the three base models with LLaMA3-PM fixed as the preference oracle: Mistral-Instruct attains the highest EWR, followed by LLaMA3-SFT, with Gemma-SFT trailing by a clear margin. Figure 3: Post-query time comparison of BoN and NMD for varying size N. Post-query alignment run-time. As we show in Remark 3, BoN and NMD share the same query complexity, but differ in post-query computation. Figure 3 compares the post-query time of the two algorithms as N grows: BoN scales rapidly with N, while NMD remains nearly flat. This is consistent with our time complexity analysis. Omitted experiment details and additional experiments are deferred to Appendix E, including comparing our methods against three baseline methods. 7 Conclusion and Limitations We initiate the study of inference-time alignment under general preferences, formulating the problem as computing a Nash equilibrium of a two-player zero-sum game between policies under an imperfect preference oracle. We propose two algorithms, Best-of-Nash (BoN) and Nash Mirror Descent (NMD), and prove that both algorithms achieve a duality gap of O(ε(x)Cuni(x))O( (x)C_uni(x)), which we show to be tight via a matching lower bound. The two algorithms differ in post-query computation: BoN solves a linear programming in O(N3.5log(1/ϵ))O(N^3.5 (1/ε)) time, while NMD requires O(N2ε(x)Cuni(x)log(N))O( N^2 (x)C_uni(x) (N)) time. Our work has several limitations. First, our theoretical guarantees depend on the quality of preference models via ε(x) (x). When ℙ P is a poor proxy for the true preference ℙ∗P^*, for example, on prompts that fall outside the distribution on which ℙ P is trained, the methods may inherit the biases of ℙ P. Second, inference-time alignment can only re-weight responses that are reachable under πref _ref. When the base policy assigns negligible probability to high-quality responses, neither BoN nor NMD can recover them, and fine-tuning remains necessary. Lastly, our analysis treats each prompt independently and provides per-prompt guarantees, thereby neglecting shared structure across prompts such as similar tasks or styles. We end this section with a few future directions. Both BoN and NMD require O(N2)O(N^2) pairwise queries to ℙ P, which can be a huge query cost; reducing this cost via active selection of pairs is an interesting direction. Another direction is to combine our inference-time theory with fine-tuning with general preferences. Finally, exploiting structure across prompts could improve sample-efficiency beyond the per-prompt rates we establish here. Acknowledgments We thank the anonymous reviewers for their comments and constructive feedback. H acknowledges support from the National Science Foundation, NSF Awards IIS-2144413 and IIS-2107173. References Adler (2013) I. Adler The equivalence of linear programs and zero-sum games. International Journal of Game Theory 42 (1), p. 165–177. Cited by: §3. Anthropic (2026) Anthropic Introducing Claude Opus 4.7. Note: https://w.anthropic.com/news/claude-opus-4-7 Cited by: §1. Azar et al. (2024) M. G. Azar, Z. D. Guo, B. Piot, R. Munos, M. Rowland, M. Valko, and D. Calandriello A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics, p. 4447–4455. Cited by: §1.2. Block and Polyanskiy (2023) A. Block and Y. Polyanskiy The sample complexity of approximate rejection sampling with applications to smoothed online learning. In The Thirty Sixth Annual Conference on Learning Theory, p. 228–273. Cited by: Appendix A, §3. Bradley and Terry (1952) R. A. Bradley and M. E. Terry Rank analysis of incomplete block designs: i. the method of paired comparisons. Biometrika 39 (3/4), p. 324–345. Cited by: §1. Calandriello et al. (2024) D. Calandriello, D. Guo, R. Munos, M. Rowland, Y. Tang, B. A. Pires, P. H. Richemond, C. L. Lan, M. Valko, T. Liu, et al. Human alignment of large language models through online preference optimisation. arXiv preprint arXiv:2403.08635. Cited by: §1.2. Chen et al. (2024) R. Chen, X. Zhang, M. Luo, W. Chai, and Z. Liu Pad: personalized alignment of llms at decoding-time. arXiv preprint arXiv:2410.04070. Cited by: §1.2. Chow et al. (2024) Y. Chow, G. Tennenholtz, I. Gur, V. Zhuang, B. Dai, S. Thiagarajan, C. Boutilier, R. Agarwal, A. Kumar, and A. Faust Inference-aware fine-tuning for best-of-n sampling in large language models. arXiv preprint arXiv:2412.15287. Cited by: §1.1, §1. Christiano et al. (2017) P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei Deep reinforcement learning from human preferences. Advances in neural information processing systems 30. Cited by: §1. Cui et al. (2023) G. Cui, L. Yuan, N. Ding, G. Yao, W. Zhu, Y. Ni, G. Xie, Z. Liu, and M. Sun UltraFeedback: boosting language models with high-quality feedback. External Links: 2310.01377 Cited by: §6.1. Cui and Du (2022) Q. Cui and S. S. Du When are offline two-player zero-sum markov games solvable?. Advances in Neural Information Processing Systems 35, p. 25779–25791. Cited by: §2. Dong et al. (2024) H. Dong, W. Xiong, B. Pang, H. Wang, H. Zhao, Y. Zhou, N. Jiang, D. Sahoo, C. Xiong, and T. Zhang Rlhf workflow: from reward modeling to online rlhf. arXiv preprint arXiv:2405.07863. Cited by: §1, §6.1. Freund and Schapire (1999) Y. Freund and R. E. Schapire Adaptive game playing using multiplicative weights. Games and Economic Behavior 29 (1-2), p. 79–103. Cited by: §1.2. Gao et al. (2023) L. Gao, J. Schulman, and J. Hilton Scaling laws for reward model overoptimization. In International Conference on Machine Learning, p. 10835–10866. Cited by: §1. Google (2026) Google Gemini 3.1 Pro Model Card. Note: https://storage.googleapis.com/deepmind-media/Model-Cards/Gemini-3-1-Pro-Model-Card.pdf Cited by: §1. Gui et al. (2024) L. Gui, C. Gârbacea, and V. Veitch Bonbon alignment for large language models and the sweetness of best-of-n sampling. Advances in Neural Information Processing Systems 37, p. 2851–2885. Cited by: §1.2. Huang et al. (2025) A. Huang, A. Block, Q. Liu, N. Jiang, A. Krishnamurthy, and D. J. Foster Is best-of-n the best of them? coverage, scaling, and optimality in inference-time alignment. arXiv preprint arXiv:2503.21878. Cited by: Appendix A, §1.2, §1, §2, §3, Remark 5. Jiang et al. (2023) D. Jiang, X. Ren, and B. Y. Lin Llm-blender: ensembling large language models with pairwise ranking and generative fusion. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 14165–14178. Cited by: §1, §6.1. Khanov et al. (2024) M. Khanov, J. Burapacheep, and Y. Li Args: alignment as reward-guided search. arXiv preprint arXiv:2402.01694. Cited by: §1.2. Maura-Rivero et al. (2025) R. Maura-Rivero, M. Lanctot, F. Visin, and K. Larson Jackpot! alignment as a maximal lottery. arXiv preprint arXiv:2501.19266. Cited by: §1.2. Munos et al. (2024) R. Munos, M. Valko, D. Calandriello, M. G. Azar, M. Rowland, Z. D. Guo, Y. Tang, M. Geist, T. Mesnard, C. Fiegel, et al. Nash learning from human feedback. In Forty-first International Conference on Machine Learning, Cited by: §E.2, §E.2, §1.1, §1.2, §1, §1. Nakano et al. (2021) R. Nakano, J. Hilton, S. Balaji, J. Wu, L. Ouyang, C. Kim, C. Hesse, S. Jain, V. Kosaraju, W. Saunders, et al. Webgpt: browser-assisted question-answering with human feedback. arXiv preprint arXiv:2112.09332. Cited by: §1. Nemirovski (2004) A. Nemirovski Prox-method with rate of convergence o (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization 15 (1), p. 229–251. Cited by: §1.2. Nesterov (2009) Y. Nesterov Primal-dual subgradient methods for convex problems. Mathematical programming 120 (1), p. 221–259. Cited by: §1.2. OpenAI (2026) OpenAI GPT-5.4 Thinking System Card. Note: https://deploymentsafety.openai.com/gpt-5-4-thinking/gpt-5-4-thinking.pdf Cited by: §1. QwenTeam (2025) QwenTeam Qwen3 technical report. External Links: 2505.09388, Link Cited by: §E.2. Rafailov et al. (2023) R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn Direct preference optimization: your language model is secretly a reward model. Advances in neural information processing systems 36, p. 53728–53741. Cited by: §1. Rakhlin and Sridharan (2013) S. Rakhlin and K. Sridharan Optimization, learning, and games with predictable sequences. Advances in Neural Information Processing Systems 26. Cited by: Appendix C, §1.2, §4, Lemma 3. Rosset et al. (2024) C. Rosset, C. Cheng, A. Mitra, M. Santacroce, A. Awadallah, and T. Xie Direct nash optimization: teaching language models to self-improve with general preferences. arXiv preprint arXiv:2404.03715. Cited by: §1.2. Schulman et al. (2017) J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: §1. Shao et al. (2024) Z. Shao, P. Wang, Q. Zhu, R. Xu, J. Song, X. Bi, H. Zhang, M. Zhang, Y. Li, Y. Wu, et al. Deepseekmath: pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300. Cited by: §1. Shi et al. (2024) R. Shi, Y. Chen, Y. Hu, A. Liu, H. Hajishirzi, N. A. Smith, and S. S. Du Decoding-time language model alignment with multiple objectives. Advances in Neural Information Processing Systems 37, p. 48875–48920. Cited by: §1.2. Skalse et al. (2022) J. Skalse, N. Howe, D. Krasheninnikov, and D. Krueger Defining and characterizing reward gaming. Advances in Neural Information Processing Systems 35, p. 9460–9471. Cited by: §1.2. Stiennon et al. (2020) N. Stiennon, L. Ouyang, J. Wu, D. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano Learning to summarize with human feedback. Advances in neural information processing systems 33, p. 3008–3021. Cited by: §1. Stroebl et al. (2024) B. Stroebl, S. Kapoor, and A. Narayanan Inference scaling flaws: the limits of llm resampling with imperfect verifiers. arXiv preprint arXiv:2411.17501 3 (8), p. 14. Cited by: §1.1, §1. Swamy et al. (2024) G. Swamy, C. Dann, R. Kidambi, Z. S. Wu, and A. Agarwal A minimaximalist approach to reinforcement learning from human feedback. arXiv preprint arXiv:2401.04056. Cited by: §1.2. Wang et al. (2024a) P. Wang, L. Li, L. Chen, Z. Cai, D. Zhu, B. Lin, Y. Cao, L. Kong, Q. Liu, T. Liu, et al. Large language models are not fair evaluators. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p. 9440–9450. Cited by: §6.1. Wang et al. (2024b) Z. Wang, A. Bukharin, O. Delalleau, D. Egert, G. Shen, J. Zeng, O. Kuchaiev, and Y. Dong Helpsteer2-preference: complementing ratings with preferences. arXiv preprint arXiv:2410.01257. Cited by: §6.1. Wu et al. (2024) Y. Wu, Z. Sun, H. Yuan, K. Ji, Y. Yang, and Q. Gu Self-play preference optimization for language model alignment. arXiv preprint arXiv:2405.00675. Cited by: §1.2. Yao et al. (2023) S. Yao, D. Yu, J. Zhao, I. Shafran, T. Griffiths, Y. Cao, and K. Narasimhan Tree of thoughts: deliberate problem solving with large language models. Advances in neural information processing systems 36, p. 11809–11822. Cited by: §1.2. Ye et al. (2024) C. Ye, W. Xiong, Y. Zhang, N. Jiang, and T. Zhang A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.07314 4 (5), p. 10. Cited by: §1.2. Yu et al. (2026) Z. Yu, Z. S. Wu, and A. Block From curiosity to caution: mitigating reward hacking for best-of-n with pessimism. arXiv preprint arXiv:2604.04648. Cited by: §1.2. Zhang et al. (2023) Y. Zhang, Y. Bai, and N. Jiang Offline learning in markov games with general function approximation. In International Conference on Machine Learning, p. 40804–40829. Cited by: §2. Zhang et al. (2025) Y. Zhang, D. Yu, T. Ge, L. Song, Z. Zeng, H. Mi, N. Jiang, and D. Yu Improving llm general preference alignment via optimistic online mirror descent. arXiv preprint arXiv:2502.16852. Cited by: §1.2. Zhang et al. (2024) Y. Zhang, D. Yu, B. Peng, L. Song, Y. Tian, M. Huo, N. Jiang, H. Mi, and D. Yu Iterative nash policy optimization: aligning llms with general preferences via no-regret learning. arXiv preprint arXiv:2407.00617. Cited by: §1.2. Zhong et al. (2022) H. Zhong, W. Xiong, J. Tan, L. Wang, T. Zhang, Z. Wang, and Z. Yang Pessimistic minimax value iteration: provably efficient equilibrium learning from offline datasets. In International Conference on Machine Learning, p. 27117–27142. Cited by: §2. Zhou et al. (2025) R. Zhou, M. Fazel, and S. S. Du Extragradient preference optimization (egpo): beyond last-iterate convergence for nash learning from human feedback. arXiv preprint arXiv:2503.08942. Cited by: §1.2. Appendix A Rejection Sampling In this section, we introduce the rejection sampling algorithm (Algorithm 3) [Block and Polyanskiy, 2023, Huang et al., 2025]. The algorithm draws N samples i.i.d. from πref(⋅|x) _ref(·|x). For each yiy_i, it samples a Bernoulli random variable ξi _i where ℙ(ξi=1∣yi)=minw(yi∣x)M,1P( _i=1 y_i)= \ w(y_i x)M,1 \. The algorithm returns yiy_i if the Bernoulli random variable ξi=1 _i=1. If ξi=0 _i=0 for ∀i∈[N]∀ i∈[N], then the algorithm randomly samples a response from the reference policy πref _ref. The main purpose of the rejection sampling algorithm is to approximate a target policy π(⋅|x)π(·|x) from πref _ref by setting w(⋅|x)=π(⋅|x)πref(⋅|x)w(·|x)= π(·|x) _ref(·|x). In the analysis of this paper, we mainly use the distribution induced by rejection sampling as an intermediate step. Algorithm 3 Rejection Sampling (RejectionSamplingN,M(w,πref,x)RejectionSampling_N,M(w; _ref,x)) 1: Input: Prompt x, base policy πref _ref, importance weight w, truncation level M. 2: Draw =(y1,…,yN,yN+1)∼πref(⋅∣x)=(y_1,…,y_N,y_N+1) _ref(· x) i.i.d. 3: for i=1…Ni=1… N do 4: Sample Bernoulli random variable ξi _i such that ℙ(ξi=1∣yi)=minw(yi∣x)M,1P( _i=1 y_i)= \ w(y_i x)M,1 \ 5: if ξi=1 _i=1 then 6: Return response y=yiy=y_i. 7: end if 8: end for 9: Return response y=yN+1y=y_N+1. Appendix B Omitted Proofs from Section 3 In this section, let N=y1,…,yNY_N=\y_1,…,y_N\ denote the candidate set drawn i.i.d. from πref(⋅∣x) _ref(· x), let π π be the policy returned by Algorithm 1, and let π~=δy∗ π= _y^* with y∗∈argmaxy∈ℙ∗(y≻π^|x)y^*∈ argmax_y P^*(y π|x) denote a pure best response to π π under the true preference. Since the maximum of the linear functional π↦ℙ∗(π≻π^|x)π ^*(π π|x) is attained at a point mass, we have that DualGap(π^)=2ℙ∗(π~≻π^|x)−1 ( π)=2P^*( π π|x)-1. We define πR _R as the distribution induced by RejectionSamplingN−1,M(π~πref,πref,x)RejectionSampling_N-1,M ( π _ref; _ref,x ) run on the same candidate set NY_N. Under this coupling, every branch of Algorithm 3 returns an element of NY_N, so conditionally on NY_N we have πR|N∈Δ(N) _R _N∈ (Y_N). We write DTV(π~,πR|N)D_TV( π, _R|Y_N) for the TV distance between π~ π and πR _R given NY_N. Lemma 1. With π^,π~ π, π, and πR _R as defined above, we have ℙ∗(πR≻π^|x)≤12+ε(x)uni(x)P^*( _R π|x)≤ 12+ (x)C_uni(x) Proof. All displays below hold conditionally on NY_N, and taking expectation over the draw of NY_N at the end yields the stated bound. By the construction, ℙ^(yi≻yj|x)i∈[N],j∈[N]\ P(y_i y_j|x)\_i∈[N],j∈[N] is a two-player constant-sum matrix game with domain on the dataset N=yii∈[N]⊆Y_N=\y_i\_i∈[N] . Since (π^,π^)( π, π) is a Nash Equilibrium computed by Algorithm 1, we have (π^,π^)=argmaxπ∈Δ(N)argminπ′∈Δ(N)ℙ^(π≻π′).( π, π)=argmax_π∈ (Y_N)argmin_π ∈ (Y_N) P(π π ). Since πR|N∈Δ(N) _R _N∈ (Y_N), the definition of the Nash equilibrium gives ℙ^(πR≻π^|x)−ℙ^(π^≻π^|x) P( _R π|x)- P( π π|x) =Ny∼πR|N,y′∼π^|N,y′∼π^|N[ℙ^(y≻y′|x)−ℙ^(y′≻y′|x)] =E_Y_NE_y _R|Y_N,y π|Y_N,y π|Y_N[ P(y y |x)- P(y y |x)] ≤0. ≤ 0. More concretely, given the column player’s policy π π, the best policy that the row player takes should be π π. On the other hand, conditioned on NY_N, we calculate that |ℙ∗(πR≻π^|)−ℙ^(πR≻π^|)| |P^*( _R π|Y_N)- P( _R π|Y_N)| ≤y∼πR|Ny′∼π^|N|ℙ∗(y≻y′|x)−ℙ^(y≻y′|x)| _y _R _NE_y π _N|P^*(y y |x)- P(y y |x)| ≤y∼πrefy′∼πref[πR(y∣N)πref(y|x)π^(y′|N)πref(y′|x)|ℙ∗(y≻y′|x)−ℙ^(y≻y′|x)|] _y _refE_y _ref[ _R(y _N) _ref(y|x) π(y |Y_N) _ref(y |x)|P^*(y y |x)- P(y y |x)|] ≤y∼πref[(πR(y|N)πref(y|x))2]y′∼πref[(π^(y′|N)πref(y′|x))2]y∼πrefy′∼πref[|ℙ∗(y≻y′|x)−ℙ^(y≻y′|x)|2] ≤ E_y _ref[( _R(y|Y_N) _ref(y|x))^2]E_y _ref[( π(y |Y_N) _ref(y |x))^2] E_y _refE_y _ref[|P^*(y y |x)- P(y y |x)|^2] ≤y∼πR[πR(y|N)πref(y|x)]y′∼π^[π^(y′|N)πref(y′|x)]⋅ε(x) ≤ E_y _R[ _R(y|Y_N) _ref(y|x)] E_y π[ π(y |Y_N) _ref(y |x)]· (x) ≤uni(x)ε(x). _uni(x) (x). Combining the above computation, we have ℙ∗(πR≻π^|x) ^*( _R π|x) ≤N[ℙ^(πR≻π^∣N)+|ℙ∗(πR≻π^∣N)−ℙ^(πR≻π^∣N)|] _Y_N[ P( _R π _N)+|P^*( _R π _N)- P( _R π _N)|] ≤N[ℙ^(π^≻π^∣N)+|ℙ∗(πR≻π^∣N)−ℙ^(πR≻π^∣N)|] _Y_N[ P( π π _N)+|P^*( _R π _N)- P( _R π _N)|] ≤12+N[|ℙ∗(πR≻π^|x)−ℙ^(πR≻π^|x)|] ≤ 12+E_Y_N[|P^*( _R π|x)- P( _R π|x)|] ≤12+ε(x)uni(x), ≤ 12+ (x)C_uni(x), and the proof is complete. ∎ Lemma 2. With π~ π and πR _R as defined above with M=N−1log(4/ε2(x))M= N-1 (4/ ^2(x)), and any σ(N)σ(Y_N)-measurable policy π^∈Δ(N) π∈ (Y_N), we have that DTV(π~,πR)≤14uni(x)ε2(x)D_TV( π, _R)≤ 14C_uni(x) ^2(x) when N≥4log(2ε(x))⋅uni(x)N≥ 4 ( 2 (x))·C_uni(x). The statement holds for the output of Algorithm 1 and Algorithm 2. Proof. We omit the dependence on x. First, the condition on N implies N−1≥2unilog(2/ε)=unilog(4/ε2)N-1≥ 2C_uni (2/ )=C_uni (4/ ^2), i.e. M≥uni≥1/πref(y)M _uni≥ 1/ _ref(y) for any y∈y ; hence w(y)/M≤1w(y)/M≤ 1 for all y and the acceptance probability in Algorithm 3 is exactly w(y)/Mw(y)/M. Since w=π~/πrefw= π/ _ref is supported on the single point y∗y^*, only candidates equal to y∗y^* can be accepted. Therefore, conditioned on NY_N, we have πR|N=qδyN+(1−q)δy∗,q=(1−1Mπref(y∗))m(y∗), _R|Y_N=q _y_N+(1-q) _y^*,\ q=(1- 1M _ref(y^*))^m(y^*), where m(y)=#i≤N−1:yi=ym(y)=\#\i≤ N-1:y_i=y\, and consequently DTV(π~,πR|N)≤qD_TV( π, _R|Y_N)≤ q. Then we bound q: q≤∑y∈(1−1Mπref(y))m(y).q≤ _y (1- 1M _ref(y))^m(y). For any fixed y, m(y)∼Bin(N−1,πref(y))m(y) (N-1, _ref(y)), and the probability generating function of the binomial gives [(1−1Mπref(y))m(y)]=(1−πref(y)⋅1Mπref(y))N−1=(1−1M)N−1≤e−(N−1)/M.E[(1- 1M _ref(y))^m(y)]=(1- _ref(y)· 1M _ref(y))^N-1=(1- 1M)^N-1≤ e^-(N-1)/M. By the definition of uni(x)C_uni(x) we have uni(x)≥1πref(y)C_uni(x)≥ 1 _ref(y) for any y, which along with ∑yπref(y)=1 _y _ref(y)=1 implies ||≤uni|Y| _uni. By substituting M=N−1log(4/ε2)M= N-1 (4/ ^2), we bound DTV(π~,πR) D_TV( π, _R) ≤[q] [q] ≤unie−(N−1)/M _unie^-(N-1)/M ≤uni⋅ε24. _uni· ^24. Then we take the expectation on NY_N and derive the desired result. ∎ Appendix C Omitted Proofs from Section 4 The following technical lemma takes the result from optimistic mirror descent literature [Rakhlin and Sridharan, 2013] that studies the general Bregman divergence. The KL divergence can be written by the Bregman divergence property: KL(π∥π′)=Dψ(π,π′)=ψ(π)−ψ(π′)−⟨∇ψ(π′),π−π′⟩,KL(π\|π )=D_ψ(π,π )=ψ(π)-ψ(π )- ∇ψ(π ),π-π , where ψ(π)=∑yπ(y)logπ(y)ψ(π)= _yπ(y) π(y). Lemma 3 (Corollary of Lemma 1 in Rakhlin and Sridharan [2013]). Denote πt _t and r^t r_t as is computed in Algorithm 2. For any π′∈Δ(N)π ∈ (Y_N), we have that ∑t=1T⟨π′−πt,r^t⟩≤β⋅KL(π′∥π1′)+1β∑t=1T∥r^t−r^t−1∥∞2−β4∑t=2T∥πt−πt−1∥12. _t=1^T π - _t, r_t ≤β·KL(π \|π _1)+ 1β _t=1^T\| r_t- r_t-1\|_∞^2- β4 _t=2^T\| _t- _t-1\|_1^2. In the following, we provide a technical lemma that quantifies the samples required to compute an approximate Nash policy under the zero-sum matrix game ℙ P. Lemma 4. Denote π^=1T∑t=1Tπt π= 1T _t=1^T _t as the policy returned by Algorithm 2. Given data size N and a sufficiently small value ϵ>0ε>0, we set β=2β=2 and T=⌈(2logN+1/2)/ϵ⌉T= (2 N+1/2)/ε . Then for any π′∈Δ(N)π ∈ (Y_N), we have ℙ^(π′≻π^)≤12+ϵ. P(π π)≤ 12+ε. Proof. Define r^0:=0 r_0:=0. Recall that π^=1T∑t=1Tπt π= 1T _t=1^T _t. For any policy π′∈Δ(N)π ∈ (Y_N), we have that ℙ^(π′≻π^) P(π π) =1T∑t=1Tℙ^(π′≻πt) = 1T _t=1^T P(π _t) ≤12+1T∑t=1T[ℙ^(π′≻πt)−ℙ^(πt≻πt)] ≤ 12+ 1T _t=1^T[ P(π _t)- P( _t _t)] ≤12+1T∑t=1T⟨π′−πt,r^t⟩. ≤ 12+ 1T _t=1^T π - _t, r_t . Note that for any π′∈Δ(N)π ∈ (Y_N) and π1′π _1 is a uniform distribution on NY_N, we have KL(π′∥π1′)≤log(N).KL(π \|π _1)≤ (N). For t≥2t≥ 2, we have |r^t(y)−r^t−1(y)|=|∑y′P^(y≻y′)(πt(y′)−πt−1(y′))|≤‖πt−πt−1‖1| r_t(y)- r_t-1(y)|=| _y P(y y )( _t(y )- _t-1(y ))|≤\| _t- _t-1\|_1. Substituting into Lemma 3, for any β≥2β≥ 2: ∑t=1T⟨π′−πt,r^t⟩≤βlogN+1β‖r^1‖∞2+(1β−β4)∑t=2T‖πt−πt−1‖12≤βlogN+1β _t=1^T π - _t, r_t ≤β N+ 1β\| r_1\|_∞^2+ ( 1β- β4 ) _t=2^T\| _t- _t-1\|_1^2≤β N+ 1β where the last inequality holds because ‖r^1‖∞≤1\| r_1\|_∞≤ 1 and, for any β≥2β≥ 2, 1β−β4≤0 1β- β4≤ 0. Setting β=2β=2 and T=⌈(2logN+1/2)/ϵ⌉T= (2 N+1/2)/ε yields P^(π′≻π^)≤12+1T∑t=1T⟨π′−πt,r^t⟩≤12+ϵ P(π π)≤ 12+ 1T _t=1^T π - _t, r_t ≤ 12+ε for all π′∈Δ(N)π ∈ (Y_N). ∎ With the above technical lemma, we can finally show the duality gap bound for NMD. See 2 Proof. First fix data size N. For any π∈Δ(N)π∈ (Y_N), we have that ℙ∗(π≻π^) ^*(π π) ≤ℙ^(π≻π^)+|ℙ^(π≻π^)−ℙ∗(π≻π^)| ≤ P(π π)+| P(π π)-P^*(π π)| ≤ℙ^(π≻π^)+uni(x)ε(x) ≤ P(π π)+C_uni(x) (x) ≤12+2uni(x)ε(x). ≤ 12+2C_uni(x) (x). Here the third line follows from Lemma 4, and the second line is the same computation as in Lemma 1 so we omit the details. Let π~=δy∗ π= _y^* be a pure best response to π π and πR _R the coupled rejection-sampling law, both as defined at the head of Appendix B. Conditioned on NY_N, ℙ∗(π~≻π^|N) ^*( π π|Y_N) ≤ℙ∗(πR≻π^|N)+|ℙ∗(πR≻π^|N)−ℙ∗(π~≻π^|N)| ^*( _R π|Y_N)+|P^*( _R π|Y_N)-P^*( π π|Y_N)| ≤ℙ∗(πR≻π^∣N)+2DTV(π~,πR|N) ^*( _R π _N)+2\,D_TV( π, _R|Y_N) ≤12+2uni(x)ε(x)+2DTV(π~,πR|N), ≤ 12+2C_uni(x) (x)+2\,D_TV( π, _R|Y_N), where the last inequality applies the first display of this proof to the policy πR|N∈Δ(N) _R _N∈ (Y_N). Taking expectation over NY_N and applying Lemma 2 with M=N−1log(4/ε2(x))M= N-1 (4/ ^2(x)), ℙ∗(π~≻π^∣N)≤12+2uni(x)ε(x)+12uni(x)ε2(x)≤12+52uni(x)ε(x),P^*( π π _N)\;≤\; 12+2C_uni(x) (x)+ 12C_uni(x) ^2(x)\;≤\; 12+ 52C_uni(x) (x), and hence DualGap(π^)=2[ℙ∗(π~≻π^∣N)]−1≤5ε(x)uni(x) ( π)=2\,E[P^*( π π _N)]-1≤ 5 (x)C_uni(x). ∎ Appendix D Omitted Proofs from Section 5 See 3 Proof. Set δ0:=ε0K/(22)≤1/6 _0:= _0K/(2 2)≤ 1/6 by the assumption on ε0 _0. Define the imperfect oracle: ℙ^(y1≻yj)=12+δ0for all K≥j≥2,ℙ^(yj≻yk)=12for all K≥j,k≥2. P(y_1 y_j)= 12+ _0 all K≥ j≥ 2, P(y_j y_k)= 12 all K≥ j,k≥ 2. Response y1y_1 is the unique dominant strategy by ℙ P. Now write π^(y1)=p,π^(y2)=q, π(y_1)=p, π(y_2)=q, for some p,q∈[0,1]p,q∈[0,1]. In the following, we construct two true preference oracles in two worlds A and B. In the world A, ℙA∗P^*_A agrees with ℙ P except ℙA∗(y1≻y2)=12+3δ0,ℙA∗(y2≻y1)=12−3δ0.P^*_A(y_1 y_2)= 12+3 _0, ^*_A(y_2 y_1)= 12-3 _0. In the world B, ℙB∗P^*_B agrees with ℙ P except ℙB∗(y1≻y2)=12−δ0,ℙB∗(y2≻y1)=12+δ0.P^*_B(y_1 y_2)= 12- _0, ^*_B(y_2 y_1)= 12+ _0. Since δ0≤1/6 _0≤ 1/6, both PA∗P^*_A and PB∗P^*_B take values in [0,1][0,1]. Now we compute the oracle quality εA2(x) _A^2(x) and εB2(x) _B^2(x): εA2(x)=εB2(x)=8δ02K2=ε02. ^2_A(x)= ^2_B(x)= 8 _0^2K^2= _0^2. In World A, y1y_1 remains strictly dominant, so we compute: ℙA∗(y1≻π^)=p2+q(12+3δ0)+(1−p−q)(12+δ0)≥12+(1−p)δ0.P^*_A(y_1 π)= p2+q( 12+3 _0)+(1-p-q)( 12+ _0)≥ 12+(1-p) _0. Therefore, we lower bound the duality gap in world A: DualGapA(π^)≥2ℙA∗(y1≻π^)−1≥2(1−p)δ0. _A( π)≥ 2P^*_A(y_1 π)-1≥ 2(1-p) _0. In World B, y2y_2 beats y1y_1 by margin δ0 _0, while y2y_2 ties with yjy_j for j≥3j≥ 3, thus y2y_2 is dominant. So we compute ℙB∗(y2≻π^)=p(12+δ0)+q2+(1−p−q)⋅12=12+pδ0.P^*_B(y_2 π)=p( 12+ _0)+ q2+(1-p-q)· 12= 12+p _0. Therefore, we lower bound the duality gap in world B: DualGapB(π^)≥2ℙB∗(y2≻π^)−1≥2pδ0. _B( π)≥ 2P^*_B(y_2 π)-1≥ 2p _0. The adversary selects the world that is worse for the algorithm: DualGap(π^)≥max(2(1−p)δ0, 2pδ0). ( π)≥ (2(1-p) _0,\;2p _0 ). The algorithm minimizes this by setting p=1/2p=1/2, yielding: DualGap(π^)≥δ0=ε0K22=ε0uni22 ( π)≥ _0= _0K2 2= _0\,C_uni2 2 since uni(x)=KC_uni(x)=K. ∎ Appendix E Additional Empirical Results E.1 Further Experimental Details All win/draw/lose judgments are produced by DeepSeek-V4-Flash (temperature = 0, at most 44 output tokens). The verbatim prompt given to the judge: System: You are an impartial expert judge evaluating the quality of two AI assistant responses to the same user prompt. Judge which response better follows the user’s instructions and is more helpful, correct, coherent and appropriately detailed for the request. Do not let the length of a response, the order in which the responses are presented, or stylistic flourishes bias your decision. Output exactly one character: ’A’ if Response A is better, or ’B’ if Response B is better. Do not output anything else. User: [User Prompt] prompt [Response A] a [Response B] b Which response is better? Answer with a single letter: A or B. E.2 Additional Experiments In this section, We compare our methods against three baselines: Borda Best-of-N, standard reward-based Best-of-N, and a fine-tuned Nash-MD-PG model [Munos et al., 2024]. Algorithm 4 Borda Best-of-N 1: Input: Prompt x, reference policy πref _ref, preference oracle ℙ P, sample size N. 2: Draw ^N=(y1,…,yN)∼πref(⋅|x) Y_N=(y_1,…,y_N) _ref(·|x) i.i.d. 3: Query P^ij←ℙ^(yi≻yj∣x) P_ij← P(y_i y_j x) for all 1≤i<j≤N1≤ i<j≤ N, and set P^ji←1−P^ij P_ji← 1- P_ij, P^ii←12 P_i← 12. 4: Compute the Borda score for each response: r^(yi)←1N−1∑j≠iP^ij,∀i∈[N]. r(y_i)← 1N-1 _j≠ i P_ij, ∀\,i∈[N]. 5: Return y^←argmaxy∈^Nr^(y) y← _y∈ Y_N r(y). A New Borda Best-of-N Baseline. To control the oracle strength, we propose a Borda Best-of-N method under the same preference oracle, shown in Algorithm 4. We report the result in Table 2. We find that Borda Best-of-N attains win-rates close to Best-of-Nash and NMD across all three datasets. To understand this, we ran a diagnostic on the dataset: in 73.8%73.8\% of N=64N=64 sub-samples, the Borda winner is a Condorcet winner of the empirical preference matrix—it beats every other candidate pairwise—in which case the Nash equilibrium of the sub-game is exactly the pure strategy on that response, so all three methods return the same response. The agreement is thus a structural property of the data rather than evidence that the equilibrium computation is redundant. On the remaining non-Condorcet sub-samples, argmax-style rules carry no guarantee. Dataset Base SFT Best-of-Nash Borda Best-of-N TLDR 62.9% 73.5% 72.5% HelpSteer2 44.1% 68.8% 67.9% UltraFeedback 23.9% 48.8% 45.7 % Table 2: Comparison of expected win-rate (EWR) across three datasets. Best-of-Nash and Borda Best-of-N sample N=64N=64 responses from LLaMA3-SFT and we use LLaMA3-PM as preference model. Standard Best-of-N. We implement the standard Best-of-N method under a fine-tuned Bradley–Terry reward model. We train the reward model and a pairwise preference model under an identical protocol, differing only in architecture: both fine-tune the same backbone (Qwen3-4B-Instruct-2507 [QwenTeam, 2025]) with a six-criterion linear head on the same HelpSteer2 training pairs. we draw N=128N=128 candidates per prompt from the base policy (LLaMA3-SFT, temperature 1.01.0) and compare three selectors: base SFT, Best-of-N under the Bradley-Terry reward, and Best-of-Nash under the pairwise preference matrix. We report the expected win rate (EWR) against the prompt’s human-preferred response, following the protocol of Section 6. Table 3 reports the results: both methods improve over the base policy by 1717–2121 percent, confirming that a well-trained oracle of either form provides a strong selection signal. Best-of-Nash attains a 4.0%4.0\% higher win rate than reward-based Best-of-N. Selector Expected win rate Base policy (random candidate) 47.0% Best-of-N (Bradley–Terry reward) 64.0% Best-of-Nash (pairwise preference) 68.0% Table 3: Comparison of Best-of-N and Best-of-Nash on held-out HelpSteer 2 prompts. A Fine-tuned Nash-MD Baseline. Finally, we compare our methods against fine-tuning with general preferences: we fine-tune the base policy with Nash-MD-PG method [Munos et al., 2024] on HelpSteer2 and evaluate it against Best-of-Nash and NMD applied to the same base policy at inference time. We use Qwen3-0.6B as the base policy and LLaMA3-PM as the preference model. For the Nash-MD-PG method, we train the total of 11 epoch with learning rate of 2e-6, KL regularization coefficient of 0.01, a mixture coefficient of 0.50.5, and temperature 0.70.7. We report the result in Table 4. Fine-tuned Nash-MD-PG improves over the base policy (40.5%40.5\% vs. 34.2%34.2\% EWR), while Best-of-Nash and NMD—using the same preference model and no parameter updates—improve substantially further (50.5%50.5\% and 52.0%52.0\%). Notably, Nash-MD’s gain comes largely from converting losses into draws (a 59.0%59.0\% draw rate vs. 42.3%42.3\% for the base) while its outright win rate does not increase, whereas Best-of-Nash and NMD raise the win rate itself. At this model scale and training budget, inference-time equilibrium computation thus extracts more from the same preference model than fine-tuning on it. Thus, we read this as evidence that our methods are a strong training-free alternative. Method Win Draw Lose EWR Base policy 13.0% 42.3% 44.7% 34.2% Nash-MD (fine-tuned) 14.0% 55.0% 31.0% 41.5% Best-of-Nash (N=64N=64) 29.0% 43.0% 28.0% 50.5% NMD (N=64,β=1N=64,β=1) 33.0% 38.0% 29.0% 52.0% Table 4: Comparison of Best-of-Nash, NMD, and a fine-tuned Nash-MD on HelpSteer2. Best-of-Nash and NMD sample N=64N=64 responses from Qwen3-0.6B and we use LLaMA3-PM as preference model.