acceptodds
Under review as a conference paper at ICLR 2027

Perfect Preference Fit, Wrong Policy: Limits of DPO under Aggregation

Abstract

Can a policy fit every observed preference perfectly and still allocate its probability mass incorrectly? We study population direct preference optimization (DPO) after response identities are replaced by semantic classes, using the class allocation from fine-policy optimization as the benchmark. Sparse comparison designs separate three guarantees: fitting preferences, repairing one environment, and preserving the target across environments. On paths, small within-class variation produces sharp regret despite exact fitting and optimal choices of positive weights, temperature, and regular proper loss. This rate persists under arbitrary small offsets to the repeated class means. Closing the path restores preservation at the symmetric baseline, but nearby environments expose a gap: each admits exact recovery by balanced weights, while every shared balanced weighting has a worst-case lower bound even with a separately optimized temperature. Equal weights attain a matching upper bound. A variance-factored link representation extends the cycle rates to every sufficiently small-support common reward law, uniformly in graph size and atom masses. The benchmark measures loss of a KL-regularized objective; it can be positive with unchanged expected reward. Tree and dense-graph upper bounds give complementary positive cases, while sharp prediction on general sparse graphs remains open.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Direct Preference Optimization, Preference Aggregation

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_cxVkOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies population DPO when comparisons retain semantic classes but discard individual response identities. It benchmarks against the class allocation obtained by optimising the fine policy. It proves sharp path regret despite exact preference fitting, shows how closing the path permits recovery, and separates environmental specific reweighting from shared balanced weights.

Critical strengths
  1. Theorem 1 identifies a precise failure mechanism: exactly fitted comparisons accumulate into allocation error that neither reweighting nor any global temperature removes. The sharp dependence on graph size and within-class variance, together with Corollary 4's uniform perturbation result, makes this substantially more informative than an isolated counterexample.

  2. Theorem 3 provides the strongest contribution: each nearby environment admits exact recovery, yet every shared balanced weighting fails on one of two fixed environments, even with separately optimized temperatures. The proof handles graph-size uniformity and temperature limits, while the tree/star bounds show complementary cases where distortion is controlled.

Critical weaknesses

The sharp cycle separation retains special two-region means and equal-target anchors, even after Corollary 5 extends the reward law. It therefore does not determine whether an irregular sparse comparison design will suffer comparable amplification. This limits the breadth of the design implications, although it does not undermine the stated theorems. Unlike the path result, graph size uniform robustness to arbitrary mean perturbations remains unresolved.

Questions for authors

Why does the cycle argument require equal-target anchors? Would perturbing them break the shared-weight separation itself, or only the current proof?

1 comment
AuthorsOpenReview ↗

Official Comment by Authors

Perturbing the anchors breaks an exact cancellation in the proof, but need not break the shared-weight separation.

In fact, arbitrary perturbations of all class means of size cκξc_\kappa \xi around the two witness environments preserve the sharp rate, with cκ>0c_\kappa > 0 independent of graph size and within-class variance. We agree that this is a statement about a neighborhood of the constructed cycle; it does not predict amplification on an arbitrary sparse graph.

Why the proof uses anchors.

Write Dijx=xi−xjD_{ij} x = x_i - x_j, and fix the target coefficient β=1\beta = 1. The two-region ordering makes local score distortions accumulate before they cancel around the cycle. For every shared weighting, Eq. (117) identifies two sets of block starts A,BA, B, each containing a positive fraction of the vertices, such that Dij(v+−v−)≥G,G≍κnVξ,i∈A, j∈B.D_{ij} (v^+ - v^-) \ge G, \qquad G \asymp_\kappa n V \xi, \qquad i \in A,\ j \in B. Here V=ϵ2V = \epsilon^2 in Theorem 3. The equality of the anchor targets matters at the next step. If pa=softmax⁡(va/τa)p^a= \operatorname{softmax}(v^a/\tau_a) and qa=softmax⁡(μa)q^a=\operatorname{softmax}(\mu^a), then τaDijlog⁡(pa/qa)=Dijva−τaDijμa.\tau_a D_{ij}\log(p^a/q^a)=D_{ij}v^a-\tau_aD_{ij}\mu^a. At the original anchors, Dijμa=0D_{ij}\mu^a=0 in both environments. Thus even separately chosen temperatures cannot explain the score contrast by a genuine target contrast. The sizes of A,BA,B also matter: they turn the contrast into a KL lower bound without losing a factor 1/n1/n.

What survives when the ties are broken.

Take the two witnesses at amplitude ξ/2\xi/2, leaving room inside the original ξ\xi-neighborhood, and perturb them to μ~a=μa+ha\widetilde\mu^a=\mu^a+h^a, where δ=max⁡a∣ha∣∞\delta=\max_a|h^a|_\infty. The key is to control the refitted score after subtracting the movement hah^a of the target itself.

To see this, write di=μi+1−μid_i=\mu_{i+1}-\mu_i, bi=(nwi)−1b_i=(nw_i)^{-1}, and express each fitted increment as di+Ei(di,j)d_i+E_i(d_i,j), where

\qquad \sum_i E_i(d_i,j)=0.$$ On the local parameter range, $|F_\nu-\sigma|{C^1}=O(V)$. Since $b_i\in[\kappa^{-1},\kappa]$, the root satisfies $j=O\kappa(V)$; hence $\partial_d E_i=O_\kappa(V)$ and $\partial_j E_i\asymp_\kappa1$. Changing each $d_i$ by at most $2\delta$ therefore changes the root by $O_\kappa(V\delta)$. Summing the resulting increment errors gives $$\operatorname{osc}!\left(\widetilde v^a-v^a-h^a\right) \le C_\kappa nV\delta .$$ It remains to account for temperature selection. Let $R$ be the larger of the two perturbed regrets and $\ell^a=\log(\widetilde p^a/\widetilde q^a)$. For small $R$, the endpoint conditioning used in Eq. (118) confines both temperatures to $[1/4,4]$. Within each block, the endpoint mean gap is bounded away from zero and its fitted score gap differs by $O_\kappa(V)$. Binary Pinsker and the positive lower bound on $\sigma'$ over the resulting compact logit range then give $|1-\tau_a|\le C_\kappa(V+\sqrt R)$. Consequently, for $i\in A,j\in B$, $$D_{ij}(\tau_+\ell^+-\tau_-\ell^-) \ge G-C_\kappa\delta(nV+\sqrt R).$$ If $R\le\min{G^2,1}$ and $\delta\le c_\kappa\xi$, the right-hand side is at least $G/2$ for sufficiently small $c_\kappa$. Every perturbed target probability is still comparable to $1/n$. The KL argument of Eq. (120) therefore gives $$\inf_{w\in\mathcal W_\kappa(n)} \max_{a\in{+,-}}\inf_{\tau_a>0} \operatorname{Reg}{\widetilde\mu^a,1} (\widetilde p^{,a}{w,\tau_a}) \gtrsim_\kappa \min{n^2V^2\xi^2,1}.$$ All anchor means can thus be distinct. Instancewise recovery remains exact by Corollary 1 because both perturbed environments stay inside its neighborhood. Proposed revision. We will state this perturbation corollary after Theorem 3 and add the proof to Appendix C.4. We will distinguish its scope from Corollary 5, which varies the reward law. The tolerance here is proportional to $\xi$: a radius independent of $\xi$ cannot protect against arbitrary changes to all means, since an $O(\xi)$ change can move both witnesses back to the baseline where equal weights recover exactly. The two-region placement remains substantive: Corollary 2 shows that even on the same equal-weight cycle, alternating the same blocks can prevent accumulation.
Reviewer_LKXhOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies DPO when individual response identities are discarded and only semantic classes and preference labels remain. The target is the class distribution obtained by optimizing at the original response level and then aggregating. For path graphs, the paper establishes a sharp regret bound of Θ(min⁡n2V2,1)\Theta(\min\\{n^2V^2,1\\}), where nn is the number of classes and VV is the within-class reward variance, despite exact preference fitting. For cycle graphs, it shows that equal weights and a calibrated temperature achieve exact recovery in the symmetric setting, but small perturbations can lead to nonzero regret. It also shows that instance-dependent weights can achieve exact recovery, whereas any fixed balanced weighting incurs a nonzero worst-case regret under perturbations.

Critical strengths
  • The paper addresses a timely problem concerning the limitations of RLHF/DPO under aggregation, and the graph-based approach is interesting.
  • The paper provides sharp regret bounds and offers insights into how comparison graph structures affect policy recovery.
Critical weaknesses
  • The main results rely on specific graph constructions and reward structures, which raises concerns about their generality. It is also unclear how these theoretical findings could be used to modify practical preference-learning algorithms to reduce regret, as the results are primarily negative. The practical significance of the regret criterion is somewhat unclear.
  • I found it difficult to evaluate the significance of individual theorems and the tightness of their bounds due to the heavy mathematical notation and technical statements. More intuition and discussion of the implications of each result would improve the presentation.
Questions for authors
  • Why and how should individual responses be grouped into semantic classes? Why is pβFp_\beta^F the appropriate target class policy, and could the authors provide a practical use case for this setting?

  • Could the authors comment on how their theoretical results might inform the design of algorithms?

  • The analysis assumes exact population preference probabilities. How would the presented regret bounds be affected in a finite-sample setting?

4 comments

Thank you for raising these questions. We agree that the manuscript should make two things easier to see: what decision the regret measures, and what a practitioner could change as a result. One concrete implication is that a path and a star use exactly the same number of comparison types, yet one can incur nonvanishing regret while the other has vanishing regret on the same classes, rewards, and reference policy. We will bring this comparison forward and explain the scope of the sharp lower bounds separately.

Why group responses, and why is pβFp_\beta^{\mathrm F} the target?

Consider a tutoring system that first chooses an instructional action, ask a clarifying question, give a hint, or show a worked solution, and then generates its wording. The router controls the frequency of these actions. An evaluator compares two actual replies, independently sampled from the reference generators for their respective actions, but the training record retains only the action IDs and the winner. This gives precisely the experiment in the paper: the probability that action jj beats action ii averages over the possible wordings of both. Two hints need not be equally good for “give a hint” to be a meaningful routing decision.

Here the application defines the classes before preference fitting: the class ID is the action the router can select. We do not propose clustering responses by reward, assume that a semantic classifier is error-free, or recommend discarding response identities when they are available. We will make this distinction explicit in the example.

The choice of target depends on the intended use of the router. If the goal is to preserve how often a system optimized at the individual-response level would choose each action, the target is its class marginal. The reason to measure β,KL(p∣pβF)\beta, \mathrm{KL}( p | p_\beta^{\mathrm F}) is the following exact identity. For Jβ(π)=Eπr−β,KL(π∣πref)J_\beta(\pi)=\mathbb E_\pi r-\beta,\mathrm{KL}(\pi|\pi_{\rm ref}),

\operatorname{Reg}\beta(p) = J\beta(\pi_\beta^{\mathrm F}) - \max_{\pi:, C_\\# \pi = p} J_\beta(\pi) = \beta, \mathrm{KL}(p | p_\beta^{\mathrm F}).

Thus, once the router commits to allocation pp, this is the objective loss that even the best possible choice of wording within each action cannot undo.

There is also a different, legitimate deployment goal: optimize the router while keeping the reference renderer fixed. Writing ρz\rho_z for the reference action probability and mzm_z for its mean reward, that router’s optimum is pβrouter(z)∝ρzemz/βp_\beta^{\rm router}(z)\propto\rho_z e^{m_z/\beta}. It can differ from pβFp_\beta^{\mathrm F} in general. In the main constructions they coincide, because each class reward has the form mz+Um_z+U with the same law of UU; the factor EeU/β\mathbb E e^{U/\beta} cancels. On these instances, our regret is also exactly the objective loss relative to the best router with that same fixed renderer. It is not necessarily a loss in expected reward: at the calibrated path temperature in Eq. (28), the expected class reward is unchanged, but probability shifts between equally rewarded blocks and incurs a larger KL cost. We will state this interpretation alongside the definition of regret.

AuthorsOpenReview ↗

Official Comment by Authors

What is sharp, and how far does it generalize?

We will introduce the theorems with the following guide. Here nn is the number of classes, VV is the within-class reward variance, and ξ\xi is the size of the perturbation from the symmetric cycle. The rates below are at fixed target coefficient β=1\beta=1.

ResultQuestion it answersMeaning of the bound
Theorem 1: pathCan perfect comparison fit and temperature tuning suffice?Every edge probability is fitted exactly. Even the best positive weights, temperature, and loss in the stated logistic-link family have regret Θ(min⁡{(nV)2,1})\Theta(\min\{(nV)^2,1\}).
Theorem 2: closing the pathCan adding one comparison type repair the allocation?Yes, exactly at the symmetric baseline. Nearby, equal weights give an upper bound O(min⁡{(nVξ)2,1})O(\min\{(nV\xi)^2,1\}) for every allowed perturbation; a particular two-region arrangement attains that order even after temperature tuning.
Theorem 3: shared weightsDoes a repair that exists for each environment transfer across environments?Each environment admits exact recovery with its own weights. For every shared weighting of fixed balance, one of two predetermined environments incurs Ωκ(min⁡{(nVξ)2,1})\Omega_\kappa(\min\{(nV\xi)^2,1\}), even with separate score fits and temperatures. Equal weights attain the matching worst-case upper bound.
Theorem 4: three classesIs the failure solely due to discarding information?No. In an explicit family, the retained probabilities identify the target, yet the specified optimizer family cannot attain it. Knowing what to estimate and optimizing an objective that returns it are separate issues.

The intuition behind the two rates is simple. On the path, the fitted score drifts by order VV every three edges between classes with the same target reward. Increasing temperature suppresses this drift but also flattens the real reward differences the policy should retain. Closing the cycle cancels the baseline drift; the residual displacement can then be of order nVξnV\xi instead of nVnV. The matching bounds establish that these scales are real on the stated constructions. They do not predict the loss of every sparse graph. Corollary 4 removes exact repetition of the path means in a neighborhood independent of nn; Corollary 5 removes the two-point-law restriction on the cycle. Neither implies a sharp cycle lower bound for arbitrary reward arrangements. We will distinguish these extensions from that open question.

How could the results change an algorithm?

First, one can change which pairs are collected without changing DPO or knowing the target. For a tree of diameter DD and common translated rewards with bounded centered support, Proposition 2 gives Reg⁡β(pDw,β)=O(D2V2/β)\operatorname{Reg}\beta(p^{\rm D}{w,\beta})=O(D^2V^2/\beta). A star compares each class to a common reference class, so D=2D=2. For example, take V=1/nV=1/n in the path construction. With n−1n-1 comparison types, the path has Θ(1)\Theta(1) best regret, while the star on the same classes has O(n−2)O(n^{-2}) regret. The actionable distinction is the length of the chain along which local errors accumulate, not the number of comparison types alone. With finite data, the reference class should also yield informative comparisons: win probabilities near zero or one make log-odds difficult to estimate.

Second, if the comparison graph is fixed but the common reward-noise law ν\nu is known, one can change the fitted link. For independent U,U′∼νU,U'\sim\nu, let Fν(d)=E[σ(d+U′−U)]F_\nu(d)=\mathbb E[\sigma(d+U'-U)]. Then

\quad\Longrightarrow\quad m_j-m_i=F_\nu^{-1}(Q_{ij}).$$ Integrating these differences on a spanning tree recovers the means up to an irrelevant additive constant, hence the target policy. This works even on the path where ordinary logistic DPO has the sharp lower bound. It requires additional information about the link. Likewise, the environment-specific weights in Theorem 3 require target residuals; their existence does not give a procedure for learning them from class labels alone. We will distinguish the comparison design one can implement directly from the corrections that require calibration information.

What changes with finitely many preference labels?

The population analysis isolates a systematic error: more labels estimate QeQ_e more accurately, but do not turn the mixed link FνF_\nu into the logistic link. A finite dataset can nevertheless either reinforce or partially cancel the population distortion. We will add a finite-sample clarification that separates these effects.

Suppose each edge has at least NN independent Bernoulli labels. With probability at least 1−δ1-\delta, the empirical win rates for both of the two fixed environments satisfy

\le u_N,\qquad u_N=\sqrt{\frac{\log(4|E|/\delta)}{2N}}.$$ For ordinary empirical DPO on a tree, suppose the true win rates are bounded away from zero and one and $u_N$ is small enough that the empirical rates are interior. Let $L$ bound the derivative of the logit on this interval. The empirical fit uses the edge differences $\operatorname{logit}(\widehat Q_e)$ exactly. On each edge, aggregation contributes at most $K_hV$ score error, where $K_h$ depends only on the common support bound $h$; sampling contributes at most $Lu_N$. Summing along a path of length at most $D$ and applying the score-to-regret inequality gives $$\operatorname{Reg}\beta(\widehat p^{\rm D}{w,\beta}) \le \frac{D^2}{8\beta}\bigl(K_hV+Lu_N\bigr)^2.$$ This also explains when the population lower bounds remain visible. On the constructed path, the drift per three-edge block is $d_\nu\asymp V$, and sampling changes it by at most $3Lu_N$. If $3Lu_N\le d_\nu/2$, the drift retains its sign and at least half its magnitude; the within-block reward contrasts still rule out flattening it by temperature alone. On the two cycle instances of Theorem 3, the scalar cycle stationarity equation changes each fitted edge increment by $O_\kappa(u_N)$, uniformly over the allowed shared weights. Thus sampling changes the score contrast used in the proof by at most $O_\kappa(nu_N)$, against a population contrast of order $nV\xi$. Consequently, $u_N\le cV$ on the path and $u_N\le c_\kappa V\xi$ on the paired cycles are sufficient for the respective lower bounds to persist up to constants with high probability. These are per-edge resolution conditions for the stated constructions, not necessary sample sizes or minimax claims. For the link-corrected estimator, the conclusion is different. If the link is supplied and its derivative is at least $\ell>0$ on the feasible reward-gap interval, clipping and inverting the empirical frequencies on a spanning tree gives $$\operatorname{Reg}\beta(\widehat p_{\rm corrected}) \le \frac{D^2}{16\beta\ell^2N} \log!\frac{2(n-1)}{\delta}$$ with probability at least $1-\delta$ in the common-law setting. Here the bound vanishes with $N$ at fixed graph size. We will place these two guarantees side by side: collecting more labels improves the precision of either estimator; changing the comparison design or supplying the correct link addresses the systematic error that additional labels alone cannot remove.

Thank you for the detailed clarifications and revisions to the manuscript. I believe the contributions are clearer now, but my main concern about the presentation of the work remains. I will keep my rating for now but remain open to updating it based on other reviewers' discussion.

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

The paper studies preference aggregation when response identities are replaced by known semantic classes. Annotations compare two representatives from the reference conditionals, but only class labels and the winner are retained.

The benchmark is the class allocation of the fine-level KL-regularized optimum.

Main results include:

  1. On periodic paths with small within-class variation, regret is θ(min(n2,V2,1))\theta(min(n^2,V^2,1)) despite exact fitting of every comparison. This holds for all positive weights, all regular proper losses, and all temperatures, and it survives small offsets to the means.
  2. Closing the path into a cycle permits exact recovery. With equal weights, the regret under mean perturbations is O(n2ϵ4ξ2)O(n^2\epsilon^4ξ^2), with a matching lower bound.
  3. Instancewise reweighting recovers the target exactly, whereas every shared balanced weighting has a worst-case lower bound of the same order.

The paper contains no experiments.

Critical strengths
  1. Separating the comparison fitting, one environment reparing, and the target preserving across environments is conceptually clarifying.

  2. The paper is honest about its scope.

Critical weaknesses
  • The relevance of the setting and of the lower bound constructions to practice is unclear. The lower bounds depend on these specific arrangements, and general sparse graphs remain open. Furthermore, there is no numerical illustration of the magnitudes for realistic parameters.

  • The contribution is incremental relative to prior work, and the presentation is too hard to understand.

Questions for authors
  • Please provide exact population computations of regret versus n for small graphs at ralistic V.

  • Is there any existing pipeline in which this class-level aggregation actually occurs?

2 comments

Thank you for asking us to distinguish a worst-case result from a likely deployment loss. We checked the aggregation step in a published routing pipeline and computed population regret both for the paper’s construction and for every placement of the same rewards on two small graphs.

Does an existing pipeline actually discard the answers being judged?

Yes. In RouteLLM (Ong et al., ICLR 2025, §§3–4.1), Arena users compare two actual answers to their prompt. To address sparse model-pair comparisons, the authors group generators into tiers and train a router on the query and the strong/weak/tie outcome, excluding the answer texts. The evaluator thus judges individual realizations, while the learner receives a class-level preference. RouteLLM uses generator classes and a binary cost threshold, not DPO over a many-class graph.

For literal semantic grouping, a recent preprint by Verma et al. (2026, §3) groups reasoning traces by final-answer equivalence to construct DPO labels, but retains the traces for training. The distinction is useful: RouteLLM documents the loss of answer identity; Verma et al. document semantic grouping in preference learning. Neither is evidence of long-path regret in deployment.

How large is the regret on small graphs?

We chose two illustrative scales from Arena’s published rating gaps: 6 Elo between two GPT-3.5-Turbo versions and 49 Elo between two GPT-4 versions. Each pair falls within one RouteLLM tier (Appendix A). For two equally likely representatives with centered rewards U=±hU=\pm h, matching a gap of Δ\Delta Elo gives 2h=Δlog⁡(10)/4002h=\Delta\log(10)/400 and V=h2V=h^2. The two cases give V=0.0002982V=0.0002982 and 0.019890.01989, or win probabilities of 50.86% and 57.01% for the better representative. These historical ratings average over prompts. They anchor the units; they are not measurements of within-class reward variance at a fixed prompt. To estimate that quantity directly, one could retain several answers from each class for a fixed prompt and obtain repeated blind comparisons of those answers.

The table gives population regret in nats, min⁡τ>0KL(pτD∥q)\min_{\tau>0}\mathrm{KL}(p^{\mathrm D}_\tau\|q), with equal edge weights. Here τ\tau is the training temperature and qi∝eμiq_i\propto e^{\mu_i} is the fine-optimal class allocation at β=1\beta=1 with uniform reference. In the baseline path the class means repeat (0,1,2)(0,1,2). The last two columns use exactly the same perturbed means: triples (0,a,2a)(0,a,2a) with a=1.025a=1.025 in the first half and a=0.975a=0.975 in the second. The only change between those columns is adding the endpoint comparison; all existing win probabilities and the target policy stay fixed.

Classes nnBaseline path, 6 EloBaseline path, 49 EloPerturbed path, 49 EloSame path closed, 49 Elo
62.94×10−102.94\times10^{-10}1.26×10−61.26\times10^{-6}1.49×10−61.49\times10^{-6}3.83×10−93.83\times10^{-9}
121.47×10−91.47\times10^{-9}6.30×10−66.30\times10^{-6}6.73×10−66.73\times10^{-6}5.18×10−95.18\times10^{-9}
246.17×10−96.17\times10^{-9}2.64×10−52.64\times10^{-5}2.72×10−52.72\times10^{-5}1.06×10−81.06\times10^{-8}
482.50×10−82.50\times10^{-8}1.07×10−41.07\times10^{-4}1.08×10−41.08\times10^{-4}3.21×10−83.21\times10^{-8}

At n=48n=48, the target assigns 51.968% of its mass to the first half of the perturbed graph. The fitted policy assigns 52.603% on the path and 51.972% after closure. Thus the additional comparison substantially reduces the allocation error, but the initial error here is about 0.635 percentage points. Reporting both quantities matters for judging practical significance.

These are rounded evaluations of the finite population, not Monte Carlo estimates or substitutions into the asymptotic bound. For a mean gap dd, the exact win probability is Fh(d)=14σ(d−2h)+12σ(d)+14σ(d+2h).F_h(d)=\tfrac14\sigma(d-2h)+\tfrac12\sigma(d)+\tfrac14\sigma(d+2h). On trees, we sum the fitted log-odds gh(d)=logit⁡Fh(d)g_h(d)=\operatorname{logit}F_h(d) along edges. On the cycle, we solve for the common residual that makes the fitted differences sum to zero. We compute KL directly and check that the temperature optimum is global. The cycle entries evaluate equal weights on the specified instance; they do not certify the minimax bound.

Is the periodic path representative?

At n=12n=12 and 49 Elo, we enumerated all 12!/(4!)3=34,65012!/(4!)^3=34{,}650 assignments of four means of each value 0,1,20,1,2 to the path. The median optimized regret was 7.23×10−77.23\times10^{-7}; the maximum was 6.46×10−66.46\times10^{-6}. The six largest values came from exactly the six orderings that repeat a permutation of (0,1,2)(0,1,2). The paper’s ordering attained 6.30×10−66.30\times10^{-6}, or 97.5% of the maximum. Its position near the extreme has a simple explanation: its true increments +1,+1,−2+1,+1,-2 sum to zero, but the fitted increments sum to 2gh(1)−gh(2)≠02g_h(1)-g_h(2)\ne0. Each triplet repeats that error.

We also evaluated every assignment on the binary tree with parent ⌊(i−1)/2⌋\lfloor(i-1)/2\rfloor for vertex i>0i>0. Its median was 6.39×10−76.39\times10^{-7} and its maximum 2.86×10−62.86\times10^{-6}, yet it had higher regret than the path on 40.2% of the paired assignments. These percentages count placements equally; they are not deployment frequencies. Even at fixed graph size, reward variance, and number of comparison types, the arrangement matters. Neither graph is uniformly preferable.

What goes beyond prior work?

Shirali et al. (2025, Prop. 5.1 and Eq. 14) show that anonymous heterogeneous preferences need not identify the mean-reward ranking, and derive a variance correction to the comparison link. Gölz et al. (2025, Thm. 9 and Appendix F) establish multiplicative average-utility distortion when comparisons concentrate near a path. We will move this comparison ahead of the theorem statements.

Theorem 1 quantifies what can still be lost when every observed probability is fitted exactly and all majority directions are correct. Even the best temperature leaves sharp additive policy regret Θ(min⁡(nV)2,1)\Theta(\min{(nV)^2,1}) on the construction. At the calibrated temperature, the fitted and target policies even have identical expected class-mean reward. Theorem 3 asks whether a repair transfers. For a fixed weight-balance bound κ\kappa and sufficiently small mean perturbations of size ξ\xi in the stated neighborhood, each environment admits zero regret with its own weights. Yet the same two environments witness a lower bound cκmin⁡(nVξ)2,1c_\kappa\min{(nV\xi)^2,1} for every shared weighting obeying that balance, even when scores and temperature are refit separately. Equal weights give the matching worst-case upper bound.

We will introduce the results through three questions in the revised manuscript: What does exact fit preserve? What can one additional comparison type repair? Does the same repair work across environments? We will place the numerical comparison next to the first construction, explain regret as an allocation loss there, and distinguish the identities valid on every tree from the sharp rates that require particular arrangements. A sharp prediction for general sparse graphs remains open.

Comments on the paper

1 comment

We thank all three reviewers for helping us clarify when aggregation changes a policy, how large that change can be, and what a learner can do about it. All additions and revisions are marked in red in both the main text and the appendices. The revised introduction organizes Theorems 1–3 around three questions: What does fitting every comparison preserve? What can adding one comparison repair? Does that repair transfer across environments? Figure 1 illustrates the construction, and Table 1 summarizes the assumptions and scope of each bound.

1. Equal-target anchors and generality of the cycle result. Equal-target anchors simplified the original proof: with uniform reference, two classes with equal target mass must have equal fitted scores at any finite temperature. Corollary 6 (Appendix G) shows that exact equality is unnecessary. We independently perturb every class mean in each of the two witness environments by up to aκξa_\kappa\xi, where ξ\xi is the original perturbation scale and the radius is independent of the number of classes nn and within-class variance VV. All means may then be distinct. Each environment still admits exact recovery with its own weights, yet every shared weighting of fixed balance κ\kappa incurs regret at least cκmin⁡{(nVξ)2,1}c_\kappa\min\{(nV\xi)^2,1\} in one of the two, even after scores and temperature are refitted separately. The two-region arrangement still generates the drift; a sharp characterization of arbitrary sparse graphs remains open. Separately, Corollary 7 (Appendix J) extends the sharp path rate to small class-specific changes in reward spread, even when these changes also move the target policy.

2. Choice of classes, practical design, and finite samples. The tutoring example makes the grouping decision concrete: a router can choose to ask a clarifying question, offer a hint, or give a worked solution. The target pβFp_\beta^F asks whether retaining only those class labels preserves the action frequencies obtained by optimizing individual answers. We distinguish this target from the best router with a fixed response generator and explain why positive KL regret can coexist with unchanged expected reward. The design implications also differ: a star limits error accumulation using the same n−1n-1 comparison types as a path; exact reweighting requires target information; and a known comparison link can be inverted. Appendix H separates sampling error from aggregation bias. Up to a logarithmic factor, V−2V^{-2} independent labels per edge on the path, or (Vξ)−2(V\xi)^{-2} on the two cycle witnesses, suffice for the respective lower bounds to persist with high probability. These are sufficient sample sizes, not claims of necessity.

3. Numerical magnitude, practical precedent, and novelty. Table 2 (p. 7) reports exact population computations for n=6,12,24,48n=6,12,24,48, optimizing temperature in every cell. At n=48n=48 and V≈0.01989V\approx0.01989, adding only the endpoint comparison reduces regret from 1.08×10−41.08\times10^{-4} to 3.21×10−83.21\times10^{-8} nats. In policy terms, the first half of the graph should receive 51.968% of the mass; it receives 52.603% on the path and 51.972% after closure. The variance scales are informed by historical Elo gaps, not measured within-prompt variances. Appendix I.1 also checks all 34,650 placements on each of two 12-class trees: the six highest-regret path placements are precisely the six periodic orderings. This identifies the construction as an extreme case rather than a typical one. Appendix K separately gives a conservative numerical certificate covering all shared weights at κ=3\kappa=3.

For a documented example of the information loss, we now discuss RouteLLM (Ong et al., 2025, §4.1), whose router learns from prompts and preference outcomes between generator groups while omitting the judged answer texts. Its objective differs from ours; we do not infer deployment regret from that example. Finally, the revised related-work discussion distinguishes earlier results on ranking nonidentification and multiplicative utility distortion from our sharp additive policy regret Θ(min⁡{(nV)2,1})\Theta(\min\{(nV)^2,1\}): on the path, every observed probability is fitted and every majority direction is correct, yet even the best temperature leaves an allocation error.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.