- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
The paper studies how many repeated pairwise comparisons are needed to rank models by average utility under heterogeneous user preferences. It shows that naive MLE-based aggregation can require repetitions, where is the minimum average-utility gap. The authors propose two improved MLE-based methods and a Russian Roulette algorithm achieving the optimal repetition budget, with the latter using repetitions in expectation.
Critical strengths
- The research question is well motivated, and the algorithms and main theoretical results are clearly presented.
- The idea of using harmonic numbers for preference aggregation is interesting.
Critical weaknesses
- Some modeling, algorithmic choices, and experimental details would benefit from further explanation. Please see the questions below.
- The literature review could be more thorough. Beyond recent alignment papers, connections to classical work on ranking recovery and preference aggregation would be helpful.
Questions for authors
-
Does explicitly separating users and tasks play an essential role in the analysis, or could the results be formulated equivalently using a single context variable ?
-
In line 200, why is aggregation relative to a fixed reference model considered the natural choice? Wouldn't averaging the estimated utility differences across all other models also recover the population-average utility ranking?
-
I believe many applications are concerned only with identifying the welfare-maximizing model (i.e., the top choice) rather than recovering the full ranking. Could the guarantees or ideas in this paper be extended to this setting?
-
I noticed that Sections 5 and 6 of Shirali et al., "Direct Alignment with Heterogeneous Preferences" (NeurIPS 2025), seem relevant to this work. Could the authors comment on how their work relates to this paper?
-
The experimental setup is insufficiently described in the main text. For example, the procedure for determining the reported repetition budget is essential for interpreting the results but is omitted from the main text. For example, the procedure for determining the reported repetition budget is essential for interpreting the results but is omitted. Could the authors provide more details on this? Could they also provide more details on why MLE-CAL has a flat curve in Figure 3 and why MLE-UNCONST and TRR: maximum have identical repetition budgets?
-
Minor errors / typos:
- Lines 183–184: The statement is potentially misleading. Does it mean that defining gives ?
- Lines 225, 232: The same equation appears twice.
3 comments
The experimental setup is insufficiently described in the main text. For example, the procedure for determining the reported repetition budget is essential for interpreting the results but is omitted from the main text. For example, the procedure for determining the reported repetition budget is essential for interpreting the results but is omitted. Could the authors provide more details on this? Could they also provide more details on why MLE-CAL has a flat curve in Figure 3 and why MLE-UNCONST and TRR: maximum have identical repetition budgets?
We thank the reviewer for pointing this out, and we will make sure to make the experimental setup more clear in the final version.
In terms of our reported repetition budgets in the experiments, these are actually estimates. We consider a grid of repetition budgets and for each possible value, we compute the population-level expected scores of each algorithm. We then report the first budget in the grid for which an algorithm obtains the correct ranking. It is certainly possible that the true budget lies in between two grid values.
Regarding why MLE-CAL has a flat curve, the reason for this is that we use the same calibration table across values of and . To see why, notice that once and are fixed, and since we consider the same minimum utility gap within each experiment, the caliration function is independent of the distribution over contexts. Thus, as this distribution varies, the required repetition budget remains constant.
To see why MLE-UNCONST and TRR overlap, notice that both algorithms have the same estimate for the context-level utility difference in expectation: the first terms of the infinite series that represents the true utility difference (see lines 350-355). Since we use these values to estimate the required repetition budget in the experiments, the two algorithms achieve the same guarantees because they are mathematically equivalent at this level. However, the key idea about TRR is that it uses fewer repetitions than MLE-UNCONST in expectation. Further, the variance of the statistics in the two algorithms is different, so given a fixed number of sampled contexts, their probability of recovering the correct ranking can differ, but this is not what our experiments seek to highlight. We are primarily focused on the repetition budget.
Minor errors / typos:
We thank the reviewer for pointing these out and will fix them in the final version. Regarding lines (183-184), we define to refer to the relative utility difference of with respect to . So but it need not be the case that . We will make this clear.
Thank you for the detailed response. As most of my concerns have been addressed, I will increase my rating to weak accept but remain open to revising it based on discussions with other reviewers.
We sincerely thank the reviewer for their time and feedback.
We included some references to classical work on ranking from pairwise comparisons in the Additional Related Works section (Appendix A). We will be sure to include any additional works we missed and move this to the main paper if you feel this is better.
Thank you for this question. No, separating users and tasks is not important to the analysis. In fact, throughout the theoretical analysis, we commonly associate a context (ij,tj) with the index j, so we can easily describe things in terms of a single context variable, as you have proposed. The reason we separate users and tasks is for narrative purposes. It is natural to separate users and tasks when motivating our setting of eliciting pairwise comparison feedback. We will clarify this in the final version.
Yes, averaging estimated utility differences across all other models can also recover the population-average utility ranking. We use a fixed reference model primarily for simplicity. Within each context, pairwise comparisons identify utilities only up to an additive constant, so ∣M∣−1 independent utility differences suffice. Choosing m0 provides this representation. Estimating all (2∣M∣) pairwise differences instead introduces redundant quantities, since every pairwise difference can be expressed using the differences relative to m0. Thus, using a fixed reference is a convenient modeling choice rather than a requirement for ranking recovery.
Yes. Since our algorithms recover the full ranking, they can immediately be used to recover the top-ranking model. In fact, our lower bound construction uses just two models, so recovering the full ranking in this case is equivalent to identifying the top-ranking model. Thus, the lower bound on the repetition budget for recovering the top-ranking model is still Ω(log(1/ϵ)).
We thank the reviewer for directing us to this paper, and we will include it in the related works in the final version. Shirali et al. also identifies that under heterogeneity, learning the Bradley-Terry win probabilities does not equate to learning the population-expected rewards/utilities. Their paper studies whether we can learn a policy to maximize the average reward using DPO-style methods. In Section 5, they show in Proposition 5.1 that the ranking under population-average rewards is not identifiable if we only have anonymous pairwise comparison data. We implicitly make a similar claim that motivates our paper. In particular, we claim that repeated comparisons within a user-task context (so comparisons are no longer anonymous), we can recover the ranking, and we ask how many such repetitions we need. Shirali et al. studies a complementary question, focusing on designing methods for policy alignment.
In Section 5, they propose a first-order correction to DPO methods, which can be estimated using paired comparisons from the same annotator. This provides an approximate alignment method rather than a guarantee of exact ranking recovery, where our paper is concerned with this ranking recovery. In section Section 6 they consider an information setting where every user type provides feedback for each response pair. In contrast, we only sample users and tasks independently, rather than requiring a comparison from every user type.