acceptodds
Under review as a conference paper at ICLR 2027

Online Preference Learning via Generalized Linear Models: Monotonicity and Convergence of SGD

Abstract

Learning from pairwise comparisons underlies applications ranging from sports rankings to preference-based finetuning of language models. We cast comparison-based models as Generalized Linear Models learned online by constant-stepsize Stochastic Gradient Descent, recovering Elo as a special case. We first establish convergence guarantees for the last iterate by applying existing results for SGD on the population loss. We then study monotonicity: upon a gradient step relative to “ is preferred to ”, how do the scores of , , and a third alternative evolve? We characterize notions of monotonicity along a training trajectory both geometrically and algebraically, giving conditions on alternatives' feature vectors. We then derive consequences: (i) the score difference between the preferred and rejected alternative always moves in the correct direction, (ii) stronger forms of monotonicity are impossible when the number of alternatives exceeds , where is the number of features; and (iii) complementarily, these stronger forms hold almost surely as , for independent subgaussian feature vectors. We conclude with experiments illustrating the convergence and monotonicity results.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
Preference learning, Bradley-Terry, Generalized Bradley-Terry, GLM, last iterate convergence

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_W3pPOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies online preference learning with GLMs, including Elo and Bradley-Terry models. The authors analyze the last-iterate convergence of SGD with constant learning rate using existing theoretical results. They also study different types of monotonicity and identify when they hold or fail depending on the geometry and dimension of feature vectors. Synthetic experiments are provided to support the theoretical results on convergence and monotonicity.

Critical strengths

[S1] Clear theoretical analysis of monotonicity.

The paper provides geometric conditions for monotonicity under online SGD. The impossibility result and high-probability guarantee for random features help explain when gap monotonicity can hold. I think these are the main theoretical contributions of this paper.

Critical weaknesses

[W1] Limited novelty compared to previous theoretical results.

I'm not sure that the novelty of theoretical analysis is enough for acceptance. Bareilles et al. (2025, Theorem 5) already provide similar gradient-based conditions for monotonicity, and the convergence guarantees in this paper are based on the existing SGD results. Although the paper includes additional geometric results and analyzes SGD trajectories, I believe the authors should better explain what is new compared to previous work.

[W2] Limited connection to practical LLM preference learning.

The paper motivates its analysis with RLHF and DPO, but the theoretical framework assumes fixed linear feature representations and i.i.d. observations. Also, all experiments are synthetic, so it is difficult to see how the theoretical assumptions apply to actual LLM preference fine-tuning. Along with this, I think the practical relevance of the theoretical findings is somewhat limited.

Questions for authors

[Q1] Novelty compared to previous monotonicity results

Theorem 1 seems closely related to the gradient-based monotonicity conditions in Bareilles et al. (2025, Theorem 5). Could you explain the main theoretical differences between these results? In particular, what is new beyond applying the existing conditions to linear feature representations? I believe it helps to clarify the novelty of this paper.

[Q2] Applicability to RLHF and DPO

In line with W2, could you explain under what assumptions DPO fine-tuning fits into this framework? Also, which monotonicity guarantees would still hold in this setting?

3 comments

We thank the reviewer for their review, and for finding our analysis of monotonicity clear. We answer each point below; the revised PDF shows all changes in blue.

[W1, first half.] Bareilles et al. (2025, Theorem 5) already provide similar gradient-based conditions for monotonicity [...]. Although the paper includes additional geometric results and analyzes SGD trajectories, I believe the authors should better explain what is new compared to previous work.

[Q1.] Novelty compared to previous monotonicity results: Theorem 1 seems closely related to the gradient-based monotonicity conditions in Bareilles et al. (2025, Theorem 5). Could you explain the main theoretical differences between these results? In particular, what is new beyond applying the existing conditions to linear feature representations? I believe it helps to clarify the novelty of this paper.

Theorem 1 and Bareilles et al. (2025, Theorem 5) are indeed related: both express monotonicity through gradient inner products. They differ in setting and in what they establish.

Bareilles et al. (2025) handle general, possibly non-linear and non-convex scores, and give sufficient conditions that are local: they hold at a fixed θ\theta, for a step size ε≤ε0\varepsilon \le \varepsilon_0 with ε0\varepsilon_0 not quantified. In that generality, nothing sharper can be expected.

In our setting, the feature representation is linear and the SGD update is explicit. This yields:

  • An exact (iff) characterization, not only sufficient conditions. It gives impossibility results: when the relevant feature angle is obtuse, monotonicity fails.
  • A global statement, valid at every θ\theta and every step size, with no ε0\varepsilon_0.
  • Geometric consequences: constraints on the angles between feature vectors, which are not available in the general non-convex setting. For instance, gap monotonicity with pairwise distinct features forces A≤2DA \le 2^D (Corollary 1).
  • A trajectory-level dichotomy (Proposition 3): either monotonicity holds at every step, or it almost surely fails at a positive asymptotic fraction of steps. Prior monotonicity guarantees concern loss minimizers (Noothigattu et al., 2020; Fageot et al., 2024, 2025; Bareilles et al., 2025, apart from their Theorem 5). We study the iterates of SGD, which are what is deployed.
  • A random-feature regime (Theorem 2): for sub-Gaussian features, monotonicity typically holds once D≫log⁡AD \gg \log A, with a phase transition.
  • An equivalence with the absence of likelihood displacement (new Proposition 7, Appendix E.4): with a softmax policy over the scores, gap monotonicity holds if and only if no update in which aa does better than predicted (δ>0\delta>0) can decrease the probability of aa, and symmetrically for δ<0\delta<0. This failure mode was documented in DPO by Razin et al. (2024), and the equivalence persists when only scores produced by the linear model are considered.

The monotonicity identity itself is elementary: it can be read directly off the update rule, and we do not claim technical difficulty. The value lies in the exact and global characterization that this simplicity enables, and in its geometric consequences. Our result is not a corollary of Theorem 5 of Bareilles et al. (2025), which is local and sufficient, and does not give these conditions.

We have added an explicit comparison with Bareilles et al. (2025) in the related work (Appendix A), stating that Theorem 1 follows directly from the update rule. We will also make clear which results are new and which are standard.

[W1, second half.] [...] and the convergence guarantees in this paper are based on the existing SGD results.

We agree, and the paper says so (Introduction, second contribution): Propositions 1 and 2 invoke recent results on constant-step SGD (Attia et al., 2025; Cortild et al., 2026). Our contribution there is to show that GLMs fit their hypotheses, with constants read off the CGF of the base distribution and the second-moment matrix of the features.

The revision goes further. These results require every sample loss to be uniformly smooth, which forces bounded features (L⋆=MRx2L_\star=MR_x^2). The new Appendix D removes this restriction in two regimes:

  • Strongly convex CGF, E∥x∥4<∞\mathbb E\|x\|^4<\infty (Proposition 4). We prove that GLM sample gradients satisfy an expected co-coercivity inequality (Lemmas 8–9), which is all the proof of Proposition 1 needs. Its bound then holds with L⋆L_\star replaced by an averaged constant Lˉ\bar L.
  • Bounded outcomes, E∥x∥2<∞\mathbb E\|x\|^2<\infty (Proposition 5). Stochastic gradients are then O(∥x∥)O(\|x\|) uniformly in the parameter (Lemma 10), which yields counterparts of both bounds of Proposition 2, with a uniform noise level in place of σ∗2\sigma_*^2.

Convergence and monotonicity guarantees thus now apply in the same feature regime. The main contribution of the paper nonetheless remains the monotonicity analysis discussed above.

[Q2.] Applicability to RLHF and DPO: In line with W2, could you explain under what assumptions DPO fine-tuning fits into this framework? Also, which monotonicity guarantees would still hold in this setting?

Our general response (section "Relevance to RLHF and DPO") answers both parts. In short:

  • Assumptions. DPO is exactly our update when the policy is log-linear in fixed features, training starts from the reference policy, and plain SGD processes one pair per step. A DPO step is then our Bradley–Terry SGD step, with features β2ϕ(y)\tfrac\beta2\phi(y) and outcome r=1r=1.
  • Monotonicity guarantees. All of them hold: the DPO margin always increases (weak gap monotonicity), and Theorem 1, Corollary 1, Theorem 2 and Proposition 7 apply as stated. In particular, DPO never lowers the probability of the preferred response if and only if the features are gap monotone. These results concern a single update, so they need neither i.i.d. data nor a well-specified model.
  • Convergence guarantees may not apply: DPO may lack a minimizer.

On fixed features (W2): for a trained network, Theorem 1 still describes one small step, to first order, with the gradients of the scores as features. Razin et al. (2024) find that the inner products of Theorem 1, computed on hidden embeddings, predict likelihood displacement in real models.

We hope these answers clarify the novelty of our results and their relevance to DPO. If they address your concerns, we would be grateful if you would consider raising your score. We are happy to discuss any remaining point.

Thank you for the detailed rebuttal.

I believe it helps to clarify on the theoretical contributions, particularly the global characterization of monotonicity, trajectory-level analysis, and the new connection to likelihood displacement (W1).

I also appreciate the clarification of the assumptions under which the results apply to DPO (W2). Although the applicability to practical LLM fine-tuning remains limited, I believe the theoretical contributions are still meaningful.

Therefore, I have decided to raise my score from 2 to 3.

Reviewer_GgQqOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies online preference learning from pairwise comparisons through the lens of generalized linear models (GLMs) learned by constant-step-size SGD. Casting the recent Generalized Bradley–Terry model as a GLM in canonical form (with Elo and RLHF/DPO as special cases), the paper makes two main moves. First, it applies recent constant-step-size SGD results to obtain non-asymptotic last-iterate convergence guarantees on the population loss, where the rate is governed by smoothness/strong convexity of the base distribution's cumulant generating function and by the Laplacian spectrum of the comparison graph. Second, and primarily, it analyzes monotonicity along the SGD trajectory: upon observing "a is preferred to b," how do the scores of a, b, and a third alternative c evolve? The paper shows (i) weak gap monotonicity holds universally; (ii) the stronger notion of gap monotonicity is impossible once the number of alternatives exceeds 2D2^D (via the Danzer–Grünbaum theorem on point sets with no obtuse angles); and (iii) conversely, for independent sub-Gaussian random features, individual and gap monotonicity hold almost surely when D=ω(log⁡A)D=\omega(\log A). Necessary and sufficient geometric conditions (Gram-matrix linear inequalities) are given, and a pathwise dichotomy shows trajectory monotonicity is no weaker than uniform monotonicity of the update operator. Synthetic experiments validate the convergence bias/variance decomposition, the dependence on comparison-graph connectivity, and the (A,D)(A,D) phase transition.

Critical strengths
  • S1. The phase-transition characterization of monotonicity is the real contribution, and it is both novel and precise. The combination of (a) weak gap monotonicity holding unconditionally, (b) gap monotonicity being impossible for A>2DA > 2^D via a classical but unexpected connection to Danzer–Grünbaum, and (c) almost-sure monotonicity for sub-Gaussian features at D=ω(log⁡A)D=\omega(\log A), gives a nearly tight two-sided picture. The fact that the possibility threshold (2D2^D) and the typicality threshold (log⁡A\log A) match up to constants is the kind of result that converts a qualitative folk tension ("shared features break monotonicity") into a quantitative theorem. This is what most strongly supports acceptance.

  • S2. It fills a gap that prior work explicitly left open. Fageot et al. (2025) characterize monotonicity of offline, batch-fitted estimators (MAP with a diffusion prior), and Bareilles et al. (2025) give sufficient conditions for gradient-descent monotonicity; this paper is, to my knowledge, the first to give a necessary-and-sufficient characterization of monotonicity along the online SGD trajectory with constant step size, together with matching impossibility and typicality results.

Critical weaknesses
  • W1. The convergence component is an application of existing theorems, and the paper's two halves do not overlap in regime. Propositions 1–2 are essentially direct invocations of Attia et al. (2025) and Cortild et al. (2026), as the authors themselves concede ("not to derive new convergence techniques"). More concerning: Assumption 1 requires bounded feature support (Rx<∞R_x < \infty), but Theorem 2's monotonicity guarantee concerns (unbounded) Gaussian/sub-Gaussian features. The flagship configurations of the two halves—bounded-support features for convergence, unbounded sub-Gaussian features for typicality—are disjoint (though Theorem 2 Case 3 shows bounded features can in principle satisfy both). It is thus unclear whether SGD converges (in the stated sense) in precisely the high-dimensional regime where monotonicity is typical for unbounded features.

  • W2. The distance to the stated RLHF/DPO motivation is large, and the normative status of monotonicity is assumed rather than argued. The model is a linear GLM over absolute strengths; in actual DPO, the documented failure mode (likelihood displacement) is substantially a softmax-normalization artifact—relative probabilities can drop even when the preferred completion's logit rises. The paper's monotonicity notions are defined on scores, so a model could be fully gap-monotone in the paper's sense while exhibiting a close analogue of the empirical phenomenon that motivates the work. Additionally, monotonicity is treated as an unquestioned axiom; in noisy or adversarial-preference regimes, some tolerance for reverse moves may be a feature (robustness), not a bug. Since the RLHF narrative drives much of the paper's framing, this gap is consequential for impact even if not for correctness.

Questions for authors
  • Q1. Regime mismatch: Can you state (even informally) last-iterate convergence guarantees under unbounded sub-Gaussian features, e.g., by trading the uniform smoothness constant L⋆=MRx2L_\star = M R_x^2 for a sub-Gaussian high-probability analysis? If the two halves of the paper indeed apply to disjoint feature regimes, the unified story needs revision.

  • Q2. Connection to the empirical failure mode: Can you give a simple example (linear model + softmax) showing whether gap monotonicity in scores is compatible with the probability of the preferred completion decreasing? If yes, the paper explains monotonicity in a sense that differs from the RLHF literature's usage—this should be acknowledged and discussed.

  • Q3. Relation to Fageot et al. (2025): Your Theorem 1 conditions are necessary and sufficient, while their "good embeddings" are sufficient. Are your conditions strictly weaker than theirs in the offline limit, or do the diffusion-prior regularization and the online setting genuinely change the geometry? A direct comparison would sharpen the boundary between the two papers.

4 comments

We thank the reviewer for their careful and constructive review, and for recognizing the phase-transition characterization as novel and precise. We answer each point below with new elements, that we hope answer your concerns.

[W1.] Assumption 1 requires bounded feature support, but Theorem 2's monotonicity guarantee concerns (unbounded) Gaussian/sub-Gaussian features. [...] It is thus unclear whether SGD converges (in the stated sense) in precisely the high-dimensional regime where monotonicity is typical for unbounded features. [Q1.] Q1. Regime mismatch: Can you state (even informally) last-iterate convergence guarantees under unbounded sub-Gaussian features, e.g., by trading the uniform smoothness constant L⋆=MRx2L_\star = M R_x^2 for a sub-Gaussian high-probability analysis? If the two halves of the paper indeed apply to disjoint feature regimes, the unified story needs revision.

We thank the reviewer for this observation, which inspired us to close the gap: bounded support was used only to supply uniform smoothness of the sample losses, and the new Appendix D removes it in two complementary regimes, preserving the rates of Propositions 1 and 2, respectively.

  1. Strongly convex CGF, E∥x∥4<∞\mathbb{E}\|x\|^4<\infty (Prop. 4). In this case, the sample gradients satisfy an expected co-coercivity inequality with constant Lˉ=(M2/μ) τ\bar L=(M^2/\mu)\,\tau, where τ=λmax⁡(H†/2KH†/2)\tau=\lambda_{\max}(H^{\dagger/2}KH^{\dagger/2}) compares K=E[∥x∥2xx⊤]K=\mathbb{E}[\|x\|^2xx^\top] to H=E[xx⊤]H=\mathbb{E}[xx^\top] and is finite as soon as E∥x∥4<∞\mathbb{E}\|x\|^4<\infty (Lemma 8). Since the proof of Proposition 1 uses uniform smoothness only through expected co-coercivity, its conclusion holds with L⋆L_\star replaced by Lˉ\bar L. Sub-Gaussian vectors have all moments finite, so this covers cases (1) and (2) of Theorem 2; case (3) has bounded features already.

  2. Convex CGF, bounded outcomes (Prop. 5). If supp⁡f⊆[rmin⁡,rmax⁡]\operatorname{supp}f\subseteq[r_{\min},r_{\max}] then ∥∇ℓx,r∥≤Rf∥x∥\|\nabla\ell_{x,r}\|\le R_f\|x\|, and both Proposition 2 bounds hold assuming only E∥x∥2<∞\mathbb{E}\|x\|^2<\infty. This covers every bounded outcome comparison model (rows 2–4 of Table 1, including Elo/Bradley–Terry).

Finally, we conjecture that a truncated variant of SGD, which skips the update whenever ∥xt∥\|x^t\| exceeds a threshold RR, would dispense with bounded outcomes altogether: truncation restores uniform smoothness with L⋆=MR2L_\star=MR^2, and the resulting bias can be controlled in terms of the tail probabilities of Px\mathbb{P}_x, with RR balancing the trade-off. We leave this to future work.

[W2, first half.] [...] The paper's monotonicity notions are defined on scores, so a model could be fully gap-monotone in the paper's sense while exhibiting a close analogue of the empirical phenomenon that motivates the work.

[Q2.] Connection to the empirical failure mode: Can you give a simple example (linear model + softmax) showing whether gap monotonicity in scores is compatible with the probability of the preferred completion decreasing? If yes, the paper explains monotonicity in a sense that differs from the RLHF literature's usage—this should be acknowledged and discussed.

We thank the reviewer for this question, which has a clear answer: no such example exists. With the softmax policy πθ(c)=eθc/∑deθd\pi_\theta(c)=e^{\theta_c}/\sum_{d}e^{\theta_d}, gap monotonicity is equivalent to the absence of likelihood displacement, so our notion coincides with the one used in the RLHF literature. The revised manuscript proves this in the new Appendix E.4 (Proposition 7): if ff is non-degenerate, the following are equivalent:

  1. U\mathcal U is gap monotone on P\mathcal P;
  2. no likelihood displacement occurs: for every θ∈RA\theta\in\mathbb R^{\mathcal A}, every (a,b)∈P(a,b)\in\mathcal P and every r∈Rr\in\mathbb R, with δ=δ(θ;a,b,r)\delta=\delta(\theta;a,b,r), δ [πUa,b,r(θ)(a)−πθ(a)]≥0;\delta\,\big[\pi_{\mathcal U_{a,b,r}(\theta)}(a)-\pi_\theta(a)\big]\ge 0;
  3. the same holds when only scores produced by the linear model, θc=⟨β,xc⟩\theta_c=\langle\beta,x_c\rangle, and outcomes r∈supp⁡fr\in\operatorname{supp}f are considered.

Two takeaways are:

  1. gap monotonicity rules out displacement (1 ⇒ 2),
  2. when gap monotonicity fails, displacement occurs in the linear model (3 ⇒ 1).

For 2., the simplest example has D=1D=1 and three responses with features xb=0x_b=0, xa=1x_a=1, xc=2x_c=2, Bradley–Terry outcomes and β0=0\beta^0=0. Observing a≻ba\succ b (r=1r=1, so δ=1\delta=1) gives β1=η\beta^1=\eta. The logit θa\theta_a rises from 00 to η\eta, but πθ1(a)=eη1+eη+e2η<13=πθ0(a),\pi_{\theta^1}(a)=\frac{e^{\eta}}{1+e^{\eta}+e^{2\eta}}<\frac13=\pi_{\theta^0}(a), as the difference is (eη−1)2/(3(1+eη+e2η))(e^\eta-1)^2/\big(3(1+e^\eta+e^{2\eta})\big). This is exactly the phenomenon described by the reviewer: the preferred response's logit rises while its probability drops. In our terms, the update is individually monotone (⟨xa−xb,xa⟩=1≥0\langle x_a-x_b,x_a\rangle=1\ge0) but not gap monotone (⟨xa−xb,xa−xc⟩=−1<0\langle x_a-x_b,x_a-x_c\rangle=-1<0): it raises cc more than aa.

Practical consequences are:

  • Individual monotonicity governs the logit θa\theta_a, while gap monotonicity governs the probability πθ(a)\pi_\theta(a) (Remark 8 makes this precise).
  • By Corollary 1, as soon as more than 2D2^D responses with distinct features can be compared, gap monotonicity fails on some pair, so likelihood displacement cannot be ruled out, whatever the feature map. Conversely, by Theorem 2, displacement is ruled out with high probability for random sub-Gaussian features when D=ω(log⁡A)D=\omega(\log A).
  • The equivalence also covers DPO with a log-linear policy πβ(y)∝e⟨β,xy⟩\pi_\beta(y)\propto e^{\langle\beta,x_y\rangle}. The normalizer cancels in log⁡πβ(yw)−log⁡πβ(yl)\log\pi_\beta(y_w)-\log\pi_\beta(y_l), so a DPO step on (yw,yl)(y_w,y_l) moves β\beta along xw−xlx_w-x_l with a positive coefficient, whatever the reference policy. It is therefore an update of the form U\mathcal U with δ>0\delta>0, so both results apply.

Changes to the manuscript. New Appendix E.4: Proposition 7, Lemma 12, and Remark 8 on logits versus probabilities. The related-work paragraph on likelihood displacement (Appendix A) now identifies it with failures of gap monotonicity.

[W2, second half.] Additionally, monotonicity is treated as an unquestioned axiom; in noisy or adversarial-preference regimes, some tolerance for reverse moves may be a feature (robustness), not a bug. Since the RLHF narrative drives much of the paper's framing, this gap is consequential for impact even if not for correctness.

We agree that monotonicity should be argued for case-by-case. Our general response gives the reasons; the main one for RLHF is Proposition 7 above. Here we address robustness.

  • Reverse moves driven by the data are allowed. Our notions are defined relative to the residual δ=r−Φf′(θa⊖b)\delta=r-\Phi_f'(\theta_{a\ominus b}), not the raw outcome. If aa does worse than predicted (δ<0\delta<0), monotonicity requires aa's score to drop. Robustness to noise then comes from the step size, which bounds each update and scales the stationary error of Propositions 1 and 2.
  • The reverse moves we rule out are not driven by the data. Whether a step moves a score against its residual depends only on the feature vectors (Theorem 1). It does not depend on θ\theta, on rr, or on the noise level. Such moves occur on clean and noisy data alike, so they cannot provide robustness.
  • They help adversaries. When gap monotonicity fails, a comparison in favor of aa can help a third alternative cc overtake aa (see the example in the general response). An adversary supporting cc can thus gain by praising aa.

[Q3.] Relation to Fageot et al. (2025): Your Theorem 1 conditions are necessary and sufficient, while their "good embeddings" are sufficient. Are your conditions strictly weaker than theirs in the offline limit, or do the diffusion-prior regularization and the online setting genuinely change the geometry? A direct comparison would sharpen the boundary between the two papers.

We thank the reviewer for this question. The two conditions can be compared precisely: they are the same inequality, applied to different matrices. Ours is the special case Y=0Y=0 of theirs.

Fageot et al. (2025) study the offline MAP estimator of a linear GBT model with a diffusion prior, fitted on the whole dataset, and show that adding a comparison in favor of aa cannot decrease the score of aa. Their sufficient condition is that the embedding is good: for every Laplacian matrix YY and every pair (a,b)(a,b), ea⊤(I+XY)−1X (ea−eb) ≥ 0,X=x⊤x.e_a^\top (I+XY)^{-1}X\,(e_a-e_b)\ \ge\ 0,\qquad X=x^\top x. Here Y=L+HY=L+H, where LL is some prior Laplacian matrix and HH is the Laplacian of the comparison graph weighted by Φf′′\Phi_f'': when a comparison is added, the offline estimator moves along x⊤Hβ−1x (ea−eb)x^\top H_\beta^{-1}x\,(e_a-e_b), where HβH_\beta is the Hessian of the MAP objective, so the Gram matrix XX is preconditioned by the curvature of the prior and of the data.

By contrast, an SGD step has no such preconditioning: it moves the score vector by ηδ X(ea−eb)\eta\delta\,X(e_a-e_b), so the condition of our Theorem 1(1), ⟨xa−xb,xa⟩=ea⊤X(ea−eb)≥0\langle x_a-x_b,x_a\rangle=e_a^\top X(e_a-e_b)\ge0, is exactly goodness restricted to Y=0Y=0. Hence:

  • Our condition is weaker: every good embedding satisfies it on all pairs.
  • Strictly weaker: Proposition 8 of Fageot et al. concatenates two one-hot class encodings of A=5A=5 alternatives into an embedding that is not good. It is a class-based embedding in the sense of our Example 6, so it satisfies both our individual and gap conditions (Appendix E.2).
  • They coincide in small cases: for A=2A=2 and for D=1D=1, the characterizations of goodness given by Fageot et al. (Propositions 5 and 6) are exactly our condition.

To answer the question directly: our conditions are strictly weaker, and the gap is geometric. The prior and, above all, the curvature of the likelihood of the whole dataset replace XX by (I+XY)−1X(I+XY)^{-1}X. The online update removes this preconditioning, which is what makes an exact characterization possible. Our condition is therefore not claimed to suffice for the offline estimator. The two results are complementary: theirs concerns the estimator fitted on a dataset, ours each step of the online learner.

Two further differences: our gap monotonicity also controls third alternatives cc, which Fageot et al. do not consider; and since our conditions are necessary, they yield the impossibility result of Corollary 1 and the trajectory dichotomy of Proposition 3. We will add this comparison to the related work.

Thank you again for these questions, which led to the new Appendices D and E.4. If our answers address your concerns, we would be grateful if you would consider raising your score.

Thank you for the detailed responses and added analyses. The new convergence results clarify when the guarantees extend beyond bounded features, and the softmax example directly addresses my concern about the connection between score-gap monotonicity and likelihood displacement. The comparison with Fageot et al. also makes the difference between the online and offline settings clearer. These additions strengthen the paper and clarify its scope. The convergence analysis still relies largely on existing results, and the unbounded-outcome case remains open, but these limitations do not change my overall positive assessment.

Reviewer_c3PBOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

Monotonicity is the property that an item should not be less preferred even though it was the winner of a comparison. Direct Preference Optimization (DPO) has slowly fallen out of favor due to its violation of monotonicty as empirical findings have shown that pairwise comparisons would decrease the probability of both items. In turn, this paper studies online preference learning using a generalized linear model with fixed item features and constant-step stochastic gradient descent (SGD). It uses existing SGD results to obtain convergence bounds, then describes when an update improves the pair’s score gap, the preferred item’s individual score, or its gap against every other item. Their GLM formulation recovers the familiar Elo update (such connection is already known and acknowledged by the authors).

Under strong convexity, the authors obtain geometric decay toward an error neighborhood. Under weaker assumptions, they give bounds for averaged and last iterates. The main contribution is that the compared pair’s gap always moves in the direction of the prediction residual. The monotonicity conditions reduce to simple inner-product inequalities involving the feature vectors. Their main geometric observation is that full gap monotonicity corresponds to non-obtuse features. This yields the sharp restriction A≤2DA\leq 2^D (A is number of items, D is the feature vector dimension) for distinct representations when monotonicity is required, with a complementary high-probability guarantee for sufficiently well-spread, independent random features.

Experiments are limited and synthetic so this paper remains a theory-focused paper. By testing SGD on 100 items with identity featuers, comparison graphs, and monte carlo of gaussian features, they show that sparser comparison graphs lead to slow learning and that higher dimensions promote better monotonicty. However, these settings largely follow from the theoretical setup, rather than showing that their method generalizes for assumptions beyond the theorems.

Critical strengths

The non-obtuse geometric connection and theorical results are standard and clear. Combining a sharp impossibility result with a positive random-feature result demonstrates when the chosen monotonicity property is feasible.

Critical weaknesses
  1. The analysis done in this work is an application of known results and feels quite standard, hence gives me the impression that the contribution is rather incremental. Incremental is fine, but the problem motivation doesn't come to me as particularly important. For example, the Elo from SGD connection is known folklore, which the authors acknowledge. The convergence is established via existing SGD theorems. The basic monotonicity identity is also immediate due to linearity. Though I am unfamiliar, Bareilles et al. (2025) seem to already study gradient-descent monotonicity using gradient inner products. Existing Elo work (Olesker-Taylor and Zanetti, 2024) also provides convergence rates, albeit for a different projected and time-averaged setting.

  2. The assumptions used in this paper stray far from real-world settings that motivate the paper. The statistical results concern a stationary, correctly specified model with fixed linear features. This is reasonable for a linear-model study, but they do not establish guarantees for feature learning for neural networks or general RLHF/DPO. The experiments stay within synthetic, correctly specified settings; the convergence experiments use identity features. In turn, they provide limited evidence that the proposed geometry explains failures in real models.

Questions for authors
  1. Why are the stronger monotonicity notions desirable? When do these violations indicate bad learning behavior or worse generalization? This is not immediately clear to me.

  2. The claimed dependence of the noise floor on the comparison graph seems to need some qualification. Section 5 says that the asymptotic floor scales with λmax⁡(LQ)\lambda_{\max}(L_Q), where LQL_Q is the Laplacian of the graph describing which pairs are compared. However, a graph-dependent upper bound does not establish that the actual stationary error depends on the graph in that way. In the paper's Gaussian setting, it does not even depend on λmax⁡(LQ)\lambda_{\max}(L_Q).

Let's assume unit-variance Gaussian outcomes and identity features such that each item has its own score parameter. For compared items aa and bb, write d=ea−ebd=e_a-e_b, and let e=β−β⋆e=\beta-\beta^\star be the parameter error after removing the unidentifiable common score offset. The update is

\qquad \varepsilon\sim N(0,1).$$ Because $\|d\|^2=2$, each individual pair update preserves the same centered Gaussian distribution with covariance $cI$ on the zero-sum parameter subspace, where $c=\frac{\eta}{2(1-\eta)}$ for $0<\eta<1$. For any fixed connected comparison distribution, this gives the stationary expected excess loss under uniform evaluation over distinct pairs: $$\mathbb E\!\left[L(\beta_\infty)-L(\beta^\star)\right] =\frac{\eta}{2(1-\eta)}.$$ This expression is independent of the comparison graph and $\lambda_{\max}(L_Q)$. Hence, the upper bound may be quite conservative under the paper's setting and may not be indicative of what actually happens in practice.
3 comments

We thank the reviewer for their detailed review, and in particular for the computation in Q2, which led to a new result in Appendix B. We answer each point below; the revised PDF shows all changes in blue.

[W1] The analysis done in this work is an application of known results and feels quite standard, hence gives me the impression that the contribution is rather incremental. Incremental is fine, but the problem motivation doesn't come to me as particularly important. For example, the Elo from SGD connection is known folklore, which the authors acknowledge. The convergence is established via existing SGD theorems. The basic monotonicity identity is also immediate due to linearity. Though I am unfamiliar, Bareilles et al. (2025) seem to already study gradient-descent monotonicity using gradient inner products. Existing Elo work (Olesker-Taylor and Zanetti, 2024) also provides convergence rates, albeit for a different projected and time-averaged setting.

Motivation. Our general response (section "Why monotonicity is desirable") explains why monotonicity matters. In particular, gap monotonicity is equivalent to the absence of likelihood displacement (new Proposition 7).

Elo as SGD, and convergence. We agree, and the paper says so: the Elo–SGD connection is folklore, and Section 3 applies existing SGD results. The revision goes further. The new Appendix D proves convergence beyond bounded features (Prop. 4 & 5); see our reply to Reviewer W3pP (W1, second half).

Thank you for pointing to these references; we have added a discussion of both to the related work (Appendix A).

Monotonicity identity. We agree it is elementary: it follows directly from the linearity of the update, and we now say so explicitly (Appendix A). The point of that result is what it enables: an exact (necessary and sufficient) characterization, valid globally for any step size, with impossibility results for obtuse angles, a dichotomy along SGD trajectories, a random-feature regime (D≫log⁡AD \gg \log A), and an equivalence with the absence of likelihood displacement (new Proposition 7).

Bareilles et al. (2025). Their Thm. 5 covers general non-linear models, but only gives sufficient conditions that are local (fixed θ\theta, small step ε≤ε0\varepsilon \le \varepsilon_0). It therefore cannot yield the exact, global statements or the impossibility results available in the linear case. Our result is not a corollary of their Theorem 5. We detail this comparison in our response to Reviewer W3pP (Q1).

Olesker-Taylor and Zanetti (2024). The rates are indeed similar in form (bias term in the step size, variance term in 1/t1/t, dependence on the spectral gap). Their setting is Elo clipped at a fixed level, with a time-averaged iterate, analyzed via Markov chain mixing. Their bound grows exponentially with the clipping level, and their analysis requires the clipping, which is "not usually implemented in practice" (their Remark 2.2). Ours is a GLM analysis with general features; for Elo, it bounds the population loss of the last iterate, without clipping. Our Appendix A stated that they give no convergence rate; we have corrected that statement, presenting our convergence result as complementary.

[W2] The assumptions used in this paper stray far from real-world settings that motivate the paper. The statistical results concern a stationary, correctly specified model with fixed linear features. This is reasonable for a linear-model study, but they do not establish guarantees for feature learning for neural networks or general RLHF/DPO. The experiments stay within synthetic, correctly specified settings; the convergence experiments use identity features. In turn, they provide limited evidence that the proposed geometry explains failures in real models.

We agree that we do not cover feature learning, and we will say so more clearly. Our general response (section "Relevance to RLHF and DPO") details what transfers. In short:

  • Stationarity and well-specification. Our monotonicity characterization does not use them. Theorem 1, Corollary 1, Theorem 2 and Proposition 7 concern a single update, at any parameter and for any outcome.
  • DPO with fixed features is exactly our update. For a log-linear policy started at the reference policy, a DPO step is our Bradley–Terry SGD step. All monotonicity results then apply.
  • Learned features. For a trained network, Theorem 1 still describes one small step, to first order, with the gradients of the scores as features.
  • Evidence from real models. Razin et al. (2024) predict likelihood displacement with a score built from hidden embeddings (CHES). This score is positive when our individual-monotonicity condition (Theorem 1) fails on these embeddings. On OLMo-1B, Gemma-2B and Llama-3-8B, it ranks training samples by the displacement they cause.
  • Experiments. Identity features appear only in the convergence experiments. The monotonicity experiments use random features: standard Gaussian in Figure 1, non-isotropic Gaussian in Figure 6 (Appendix F).

[Q1.] Why are the stronger monotonicity notions desirable? When do these violations indicate bad learning behavior or worse generalization? This is not immediately clear to me.

Our general response (section "Why monotonicity is desirable") answers both questions. In short:

Why the stronger notions. Weak gap monotonicity only guarantees that the gap between the two compared alternatives moves the right way. It says nothing about the score of aa itself, nor about its standing against other alternatives. Each stronger notion protects one of these.

  • Individual monotonicity protects the score: if aa does better than predicted, θa\theta_a does not decrease. This matters when scores are read on their own, like a player's rating.
  • Gap monotonicity protects the ranking: aa loses ground to no alternative cc. For a softmax policy over the scores, it is equivalent to the absence of likelihood displacement (new Proposition 7): the probability of aa never decreases.

The distinction is relevant. Take D=1D=1, features xb=0x_b=0, xa=1x_a=1, xc=2x_c=2, Bradley–Terry outcomes and β=0\beta=0. After a≻ba\succ b, both weak gap and individual monotonicity hold: θa−θb\theta_a-\theta_b and θa\theta_a increase by η\eta. Yet θa−θc\theta_a-\theta_c decreases by η\eta, and the softmax probability of aa drops from 1/31/3 to eη/(1+eη+e2η)<1/3e^\eta/(1+e^\eta+e^{2\eta})<1/3.

When violations indicate bad behavior. Violations do not mean that learning fails: our convergence results hold either way. Violations affect the online iterate, in use. If the update rule is not monotone, they almost surely recur at a positive fraction of SGD steps (Proposition 3). Points 1 and 3 of the general response give concrete consequences.

Generalization. Violations are not a symptom of poor generalization. Whether they occur depends only on features (Th. 1), not of how well the model fits. They are a side effect of the learning process that enables generalization: shared features let a comparison between aa and bb inform and update the score of cc. This side effect is unavoidable when A>2DA>2^D (Coro. 1), and vanishes for random features once D=ω(log⁡A)D = \omega(\log A) (Th. 2).

[Q2] The claimed dependence of the noise floor on the comparison graph seems to need some qualification. Section 5 says that the asymptotic floor scales with λmax(LQ)\lambda_{max}(L_Q), where LQL_Q is the Laplacian of the graph describing which pairs are compared. However, a graph-dependent upper bound does not establish that the actual stationary error depends on the graph in that way. In the paper's Gaussian setting, it does not even depend on λmax(LQ)\lambda_{max}(L_Q).

You are right that the asymptotic floor does not scale with λmax(LQ)\lambda_{max}(L_Q); we have withdrawn that statement (Section 5, paragraph "Dependence on the comparison graph"). In the Gaussian setting with identity features, the stationary distribution of the error is the same for every connected graph, and so are the stationary excess loss η2(1−η)\frac{\eta}{2(1-\eta)} and the stationary mean squared error (A−1)η2(1−η)\frac{(A-1)\eta}{2(1-\eta)}.

What the graph does affect: the transient. With et=βt−β⋆e^t=\beta^t-\beta^\star, we have E[et]=(I−ηLQ)te0\mathbb E[e^t]=(I-\eta L_Q)^te^0, and E[et(et)⊤]\mathbb E[e^t(e^t)^\top] converges to its stationary value geometrically, with ratio at most 1−2η(1−η)λmin⁡+(LQ)1-2\eta(1-\eta)\lambda^+_{\min}(L_Q). The algebraic connectivity, which enters our bounds through ν\nu, thus sets the convergence speed only. This is what Figure 3 shows. We have added this level as a dashed line to Figure 3.

Our bounds. As you note, they are upper bounds. In this Gaussian example:

  • the steady-state term of Proposition 2, ησ∗2/(2(1−ηL⋆))=η/(1−2η)\eta\sigma_*^2/(2(1-\eta L_\star))=\eta/(1-2\eta), does not depend on the graph, and is within a factor about 2 of the exact value;
  • the steady-state term of Proposition 1 bounds the mean squared error and scales as 1/ν=1/λmin⁡+(LQ)1/\nu=1/\lambda^+_{\min}(L_Q). It is within a factor 4/(1−η)4/(1-\eta) of the exact value for the complete graph, but conservative for sparse graphs.

Appendix B already noted that the bound on ν\nu is not tight, as it misses the interaction between the graph and the feature matrix. Following your remark, we have added the exact computation of the Gaussian case to Appendix B, together with the transient analysis above, and revised Section 5 accordingly.

We hope these answers address your concerns, in particular on the motivation for monotonicity and its relevance to RLHF. If so, we would be grateful if you would consider raising your score. We are happy to discuss any remaining point.

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of revisions (1/2)

We thank the reviewers for their careful reading. We have uploaded a revised PDF, with all changes shown in blue. Two new appendices shift the lettering: the monotonicity proofs are now in Appendix E (formerly D), and the complementary figures in Appendix F (formerly E). Our replies use the revised numbering.

New results.

  • Convergence beyond bounded features (new Appendix D; GgQq, W3pP, c3PB). Proposition 4 covers strongly convex CGFs with E∥x∥4<∞\mathbb E\|x\|^4<\infty, through an expected co-coercivity inequality for GLM gradients (Lemmas 8–9). Proposition 5 covers bounded outcomes with E∥x∥2<∞\mathbb E\|x\|^2<\infty (Lemma 10). Convergence and monotonicity guarantees now hold in the same feature regime.
  • Gap monotonicity and likelihood displacement (new Appendix E.4; GgQq, W3pP, c3PB). Proposition 7: for a softmax policy over the scores, gap monotonicity holds if and only if no update lowers the probability of the preferred alternative. The equivalence persists on scores actually produced by the linear model.
  • An exactly solvable case (Appendix B; c3PB). For Gaussian outcomes and identity features, the stationary error does not depend on the comparison graph; the graph only sets the speed of the transient. Figure 3 now shows this stationary level as a dashed line.

Corrections.

  • Section 5: we withdrew the claim that the asymptotic floor scales with λmax⁡(LQ)\lambda_{\max}(L_Q) (c3PB).
  • Remark after Proposition 2: the steady-state term was missing a factor σ∗2\sigma_*^2.
  • Appendix A: Olesker-Taylor and Zanetti (2024) give a convergence rate (c3PB).

Related work and positioning (Appendix A).

  • An explicit comparison with Bareilles et al. (2025, Theorem 5), stating that our Theorem 1 follows directly from the update rule (W3pP, c3PB).
  • Likelihood displacement is now identified with failures of gap monotonicity, with a pointer to Proposition 7 (GgQq).

For the final version.

  • A comparison with the good embeddings of Fageot et al. (2025) (GgQq).
  • The assumptions under which DPO is an instance of our update, and a qualified claim in the introduction (W3pP, c3PB).
  • A clearer separation between new and standard results (W3pP).

Why monotonicity is desirable

Reviewers GgQq and c3PB asked why monotonicity matters, and why its stronger forms do. We give four reasons.

1. Failure of gap monotonicity is a documented failure mode of preference fine-tuning. DPO can lower the likelihood of the preferred response (Pal et al., 2024; Razin et al., 2024). Razin et al. call this likelihood displacement. It can be harmful: training Llama-3-8B-Instruct to refuse unsafe prompts lowered its refusal rate from 74.4% to 33.4%. Our new Proposition 7 (Appendix E.4) shows that, for a softmax policy over the scores, gap monotonicity is equivalent to the absence of likelihood displacement. Our strongest notion is thus exactly the property whose failure the RLHF literature reports.

2. Non-monotone updates can be manipulated. If praising aa can hurt aa, evaluators gain from misreporting. Gap monotonicity matters here too. Take D=1D=1 and features xb=0x_b=0, xa=1x_a=1, xc=2x_c=2. Reporting a≻ba\succ b changes the gap θa−θc\theta_a-\theta_c by −ηδ<0-\eta\delta<0. A supporter of cc can thus help cc overtake aa by praising aa. This is why monotonicity is a classical axiom of social choice and tournament ranking (Zermelo, 1929; Moulin, 1988; Noothigattu et al., 2020).

3. Violations affect the model in use. Reviewer c3PB asked when violations indicate bad learning behavior. They do not degrade the population loss: our convergence results hold either way. They affect the iterate that is deployed. Elo ratings change after every game, and fine-tuned models are used after finitely many steps. A step in the wrong direction changes what users see at once. By Proposition 3, if the update rule is not monotone, almost every trajectory violates monotonicity at a positive fraction of its steps.

4. We characterize monotonicity; we do not impose it. Theorem 1 says when each notion holds. Corollary 1 gives the price: with distinct features, gap monotonicity allows at most 2D2^D alternatives. Theorem 2 shows the price is low: D=ω(log⁡A)D=\omega(\log A) suffices for random sub-Gaussian features. Weak gap monotonicity, which concerns only the compared pair, always holds. Reverse moves driven by the data also remain allowed (see our reply to Reviewer GgQq, W2).

AuthorsOpenReview ↗

Summary of revisions (2/2)

Relevance to RLHF and DPO

Reviewers W3pP and c3PB asked when DPO fits our framework, and which guarantees still hold.

When DPO is our update. Three assumptions suffice.

  • Fixed features. The policy is log-linear, πw(y)∝e⟨w,ϕ(y)⟩\pi_w(y)\propto e^{\langle w,\phi(y)\rangle}, with ϕ\phi fixed. This covers a linear head on a frozen model. It also covers the single-token setting of Razin et al. (2024, Section 4.2.1) when only the hidden embedding ww of the prompt is trained; ϕ(y)\phi(y) is then the unembedding of token yy.
  • Standard initialization. Training starts from the reference policy: πref=πwref\pi_{\rm ref}=\pi_{w_{\rm ref}}.
  • Plain SGD, one preference pair per step.

The normalizer then cancels in the DPO margin. With u=w−wrefu=w-w_{\rm ref}, a DPO step on y+≻y−y_+\succ y_- reads u←u+ηβ σ(−β⟨u,ϕ(y+)−ϕ(y−)⟩) (ϕ(y+)−ϕ(y−)).u\leftarrow u+\eta\beta\,\sigma\big(-\beta\langle u,\phi(y_+)-\phi(y_-)\rangle\big)\,\big(\phi(y_+)-\phi(y_-)\big). This is exactly our SGD step for the Bradley–Terry base distribution of Table 1, with features xy=β2ϕ(y)x_y=\tfrac\beta2\phi(y) and outcome r=1r=1. The residual δ=1−tanh⁡(θy+⊖y−)\delta=1-\tanh(\theta_{y_+\ominus y_-}) is always positive since tanh⁡(t)<1\tanh(t) < 1 for all tt real.

In that case, all monotonicity results hold. Theorem 1, Corollary 1, Theorem 2 and Proposition 7 concern a single update, at any parameter and for any outcome. They need neither i.i.d. data nor a stationary or well-specified model. For DPO, they give:

  • the DPO margin always increases (weak gap monotonicity);
  • DPO never lowers the probability of the preferred response if and only if the features are gap monotone (Proposition 7; Remark 9 handles the temperature β\beta);
  • with more than 2D2^D responses with distinct features, some pair can cause likelihood displacement (Corollary 1);
  • with random sub-Gaussian features, D=ω(log⁡A)D=\omega(\log A) rules it out with high probability (Theorem 2).

In that case, convergence results may not apply. Our convergence results assume i.i.d. data from the model. The SGD results we invoke need i.i.d. data and a minimizer. DPO may lack one: with deterministic preferences, its margins can grow without bound. Adam, mini-batches and learned representations are also outside our analysis. For a trained network, Theorem 1 still describes one small step, to first order, with xcx_c the gradient of the score of cc. This is the local regime of Bareilles et al. (2025).

Evidence from real models. Razin et al. (2024, Definition 2) predict likelihood displacement with their CHES score, ⟨h+,h−⟩−∥h+∥2\langle h_+,h_-\rangle-\|h_+\|^2, where h±h_\pm sums the hidden embeddings of response y±y_\pm. This score is positive when our individual-monotonicity condition ⟨xa−xb,xa⟩≥0\langle x_a-x_b,x_a\rangle\ge0 (Theorem 1) fails, with hidden embeddings as features. On OLMo-1B, Gemma-2B and Llama-3-8B, ranking training samples by CHES matches the displacement they cause. The inner products of Theorem 1 are thus what predicts likelihood displacement in real models.

We will state these assumptions in the paper, and qualify the claim in the introduction that DPO is a special case of our framework.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.