acceptodds
Under review as a conference paper at ICLR 2027

How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity?

Abstract

We study ranking models by population-average utility from pairwise comparisons when preferences vary across users and tasks. Prior work shows that a single comparison per user can be insufficient to identify the alternative with the highest average utility, even with arbitrarily many users (Gölz et al., 2025). We investigate how many repeated comparisons within each user-task context are necessary and sufficient for ranking recovery. Under a heterogeneous Bradley–Terry model with fixed inverse temperature, we start with a naive MLE-based algorithm that requires repeated comparisons per context to ensure ranking recovery. We then present two MLE-based variants and a randomized Russian Roulette-style algorithm that recover the ranking using repeated comparisons per context, and we prove that this logarithmic dependence is optimal. Despite this worst-case requirement, our Russian Roulette algorithm uses only comparisons per context in expectation. Synthetic experiments and semi-synthetic experiments based on Arena data compare the four algorithms in settings with varying levels of preference heterogeneity and under varying context distributions.

Primary area:
learning theory
Keywords:
LLM evaluation, preference learning, pairwise comparisons, heterogeneous preferences, Bradley–Terry model, ranking, sample complexity, human feedback

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_iLnwOpenReview ↗
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 Ω(1/Δ2)\Omega(1/\Delta^2) repetitions, where Δ\Delta is the minimum average-utility gap. The authors propose two improved MLE-based methods and a Russian Roulette algorithm achieving the optimal O(log⁡(1/Δ))O(\log(1/\Delta)) repetition budget, with the latter using O(1)O(1) 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 c=(i,t)c=(i,t)?

  • In line 200, why is aggregation relative to a fixed reference model m0m_0 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 u(i,t,m0)=0u(i,t,m_0)=0 is potentially misleading. Does it mean that defining v(i,t,m):=u(i,t,m)−u(i,t,m0)v(i,t,m):=u(i,t,m)-u(i,t,m_0) gives v(i,t,m0)=0v(i,t,m_0)=0?
    • Lines 225, 232: The same equation appears twice.
3 comments

We sincerely thank the reviewer for their time and feedback.

The literature review could be more thorough. Beyond recent alignment papers, connections to classical work on ranking recovery and preference aggregation would be helpful.

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.

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 c=(i,t)c = (i,t)?

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)(i^j,t^j) with the index jj, 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.

In line 200, why is aggregation relative to a fixed reference model m0m_0 considered the natural choice? Wouldn't averaging the estimated utility differences across all other models also recover the population-average utility ranking?

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|\mathcal M|-1 independent utility differences suffice. Choosing m0m_0 provides this representation. Estimating all (∣M∣2)\binom{|\mathcal M|}{2} pairwise differences instead introduces redundant quantities, since every pairwise difference can be expressed using the differences relative to m0m_0. Thus, using a fixed reference is a convenient modeling choice rather than a requirement for ranking recovery.

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?

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/ϵ))\Omega(\log (1/\epsilon)).

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?

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.

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 hh and λ\lambda. To see why, notice that once β\beta and ϵ\epsilon are fixed, and since we consider the same minimum utility gap Δ\Delta within each experiment, the caliration function ϕ\phi 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 dd 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 v(i,t,m)=u(i,t,m)−u(i,t,m0)v(i,t,m) = u(i,t,m)-u(i,t,m_0) to refer to the relative utility difference of mm with respect to m0m_0. So v(i,t,m0)=0v(i,t,m_0)=0 but it need not be the case that u(i,t,m0)=0u(i,t,m_0)=0. 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.

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

This paper studies how many repeated pairwise comparisons are needed to rank models by population-average utility when user preferences are heterogeneous. Under a contextual Bradley–Terry model, the authors show that a naive MLE-based method can require Ω(1/Δ²) repeated comparisons per context. They then propose two improved MLE-based methods and a Russian Roulette estimator, reducing this requirement to O(log(1/Δ)), and prove that this bound is optimal. The Russian Roulette estimator further requires only O(1) comparisons per context in expectation. The methods are evaluated on synthetic and semi-synthetic Arena-based datasets.

Critical strengths

1. The paper addresses a relevant problem in preference-based model evaluation.

Preference heterogeneity is a genuine issue in human evaluation, especially for large language models, where different users and tasks may induce substantially different preferences. Understanding how such heterogeneity affects the recovery of population-average utility rankings is a meaningful research direction.

2. The paper provides theoretically improved algorithms with logarithmic repetition complexity.

The proposed algorithms reduce the required per-context repetition budget from the quadratic dependence exhibited by the naive MLE-based approach to O(log(1/Δ)). The matching lower bound is also theoretically interesting, while the constant expected number of comparisons achieved by the TRR estimator suggests a potentially useful direction for reducing evaluation costs.

Critical weaknesses

1. Unrealistic assumptions about repeated human comparisons.

The theoretical analysis assumes that repeated comparisons within the same user-task context are independent and identically distributed. However, asking users to repeatedly compare identical responses may introduce memory effects, fatigue, and changes in judgment. Such dependencies could substantially affect the proposed estimators. The paper does not investigate these effects or evaluate the robustness of its methods when this assumption is violated, raising concerns about their applicability to real-world human evaluation.

2. Insufficient analysis of practical annotation efficiency.

The paper primarily emphasizes reducing the number of repeated comparisons per context, but this does not necessarily imply a reduction in the total annotation cost. The number of sampled contexts and the variance of the estimators also affect the number of comparisons required for accurate ranking recovery. Therefore, the claimed practical efficiency advantages, particularly those of the TRR estimator, are not sufficiently demonstrated.

3.Strong dependence on a fixed and known Bradley–Terry temperature parameter.

The proposed methods assume a fixed and known inverse temperature β shared across all users and tasks. However, different users may exhibit substantially different levels of preference consistency, making this assumption restrictive in heterogeneous human evaluation. More importantly, when β varies across users and is unknown, the observed comparison probabilities cannot uniquely determine the underlying utility differences, potentially making the target population-average utility ranking unidentifiable. The paper does not address this fundamental limitation or establish whether its theoretical guarantees can be extended to heterogeneous temperature settings. This substantially limits the generality of the proposed methods.

Questions for authors

1.Regarding empirical evaluation and benchmark selection: Why are the experiments limited to synthetic and semi-synthetic settings rather than actual repeated human preference judgments? Can the authors provide empirical evidence from real human evaluation settings to demonstrate that the proposed methods remain effective beyond the constructed Bradley–Terry environments?

2.Regarding baseline selection: Why does the experimental evaluation focus primarily on the proposed MLE variants and TRR estimator? How do these methods compare with established preference aggregation and ranking methods?

3.Regarding the conditional-independence assumption: How sensitive are the theoretical guarantees and empirical performance to violations of the assumption that repeated comparisons within a fixed user-task context are independent and identically distributed? For example, what happens when repeated judgments exhibit positive correlation, evaluator fatigue, memory effects, or preference drift? Can the authors provide robustness analyses demonstrating whether the logarithmic repetition advantage persists under such conditions?

4.Regarding the practicality of the sampling strategy: The proposed framework requires repeated comparisons of the same model pair within a fixed user-task context. How do the authors envision implementing this procedure in realistic LLM evaluation systems, where repeatedly presenting identical comparisons to the same user may be costly, unnatural, and potentially detrimental to annotation quality?

5.Sensitivity to reference model selection. All four algorithms rely on a fixed reference model (m_0), but the experiments do not sufficiently investigate how its selection affects performance. How sensitive are the ranking accuracy and sample efficiency of the proposed methods to the choice of (m_0)? Could the authors report results using different reference models, particularly the strongest and weakest models?

6 comments

We sincerely thank the reviewer for their time and feedback.

  1. Unrealistic assumptions about repeated human comparisons.

We totally agree with the reviewer that asking users to repeatedly compare identical responses may introduce memory effects, fatigue, and changes in judgment.

First, we want to clarify that we do not ask users to repeatedly compare identical responses. Our definition of a "task" is not a single prompt for which a model gives a response, but rather a large collection of prompts that fall within some category. Examples of tasks in our setting could be writing, coding, math, etc... Consider each task tt is associated with a distribution over prompts Qt\mathcal{Q}_t. Each repeated comparison is not asking a users to compare the same responses again and again but rather sampling a fresh prompt from Qt\mathcal{Q}_t each time and then asking the user to compare a fresh pair of responses given that prompt. Whenever we do not sample the same prompt (which is true when the task subsumes a large number of prompts), the pairwise comparisons are independent.

Second, we agree that obtaining many repeated comparisons for a single user is too demanding. This motivates the main question of this submission--how many repeated comparisons are sufficient and necessary to learn the true ranking. Our theoretical results show that repeated comparisons are inevitable and we propose a randomized algorithm TRR achieving a constant budget in expectation. In our experiments, the average number of repetitions used by TRR is at most 2.24, which is smaller than the average number of comparisons users provided in the LMArena dataset.

We apologize for the confusion, and we will clarify the problem setup in the final version of the paper.

  1. Insufficient analysis of practical annotation efficiency.

We agree that overall annotation efficiency is important. We decompose total annotation efficiency into two parts: the number of users and the number of comparisons per user, the latter of which we call the repetition budget in this submission. To collect more data, we could either find more users or collect more comparisons from the current users. In a lot of scenarios, obtaining these repeated comparisons is harder. In Arena data, the average number of comparisons per user is 3. Hence, in this paper, our main focus is optimizing this repetition budget.

That being said, we still do consider the complexity of sampled contexts (user-task pairs) ---- and thus the total sample complexity ---- of MLE-CAL, MLE-UNCONST, and TRR in Corollaries 3.3 and 3.5, respectively. Specifically, the number of sampled contexts we require for MLE-UNCONST and TRR has inverse-quadratic dependence on ϵ\epsilon and close to linear dependence on ∣M∣|\mathcal{M}| and for MLE-CAL, this dependence on ϵ\epsilon is slightly better than inverse quadratic (i.e 1/ϵ2+κβ1/\epsilon^{2+\kappa_{\beta}} for some positive constant κβ\kappa_{\beta}).

Further, we do design our algorithms to reduce the sampled context complexity where possible, precisely because we eventually do care about overall annotation efficiency.

As an example of this, in our definition of MLE-CAL, we specifically choose the calibration function with smallest magnitude that obeys the bias constraint (see Section C.2 line 796). That is, as long as we choose a calibration function that satisfies the constraint, our repetition budget result holds. The reason we choose the function with smallest magnitude is entirely because this reduces variance and thereby the total number of sampled contexts as opposed to choosing an arbitrary calibration that satisfies the bias constraint (see proof of Proposition C.4).

3.Strong dependence on a fixed and known Bradley–Terry temperature parameter.

We agree with the reviewer that having a fixed, known β\beta is a modeling assumption.

First, we'd like to address that a modeling assumption on β\beta is necessary. In the setting where β\beta varies arbitrarily across contexts (i.e each context jj is associated with some βj\beta_j) and is unknown, then repeated comparisons within context jj can only identify βj(uij(tj,m1j)−uij(tj,m2j))\beta_j(u_{i^j}(t^j,m_1^j)-u_{i^j}(t^j,m_2^j)). Even with inifinite repetition budget, it is impossible to recover the average utility and thus the ground truth ranking.

Second, an assumption on uniform β\beta allows us to derive clean repetition budget and understand how it depends on the utility gaps. Though we assume that β\beta is known, most algorithms in this work do not need the knowledge of β\beta, except for TRR to achieve constant expected repetition budget. It is an interesting open question for future exploration to achieve the same expected guarantee without knowing β\beta.

Finally, we'd like to address that uniform known β\beta is a fairly common assumption in the theoretical research of ranking from pairwise comparisons (see Haghtalab et al. for example).

Why are the experiments limited to synthetic and semi-synthetic settings rather than actual repeated human preference judgments? Can the authors provide empirical evidence from real human evaluation settings to demonstrate that the proposed methods remain effective beyond the constructed Bradley–Terry environments?

Our semi-synthetic experiments are based off of real human comparisons from the Arena dataset. However, the issue is that we cannot run experiemnts directly over the real dataset because the ground truth ranking (which is defined for the population of users and tasks) in the Arena data is unknown. Thus, we cannot observe whether a ranking is wrong or not.

Since the ground truth ranking of population-average utilities is unknown, our experiments have to be semi-synthetic by fitting some data modeling such as the Bradley-Terry model to the real world data. This semi-synthetic experiment setting is common for ranking algorithms when the ground-truth is unknown (see Song et al. and Haghtalab et al. for example).

Why does the experimental evaluation focus primarily on the proposed MLE variants and TRR estimator? How do these methods compare with established preference aggregation and ranking methods?

Standard preference aggregation methods such as Bradley-Terry do not consider the heterogeneous setting. This Arena blog post motivates considering heterogeneity and explains why they introduce different prompt categories in their datasets.

In the introduction (lines 79-81), we highlight that if the latent utility difference between two models is LL, standard Bradley-Terry estimates E[σ(βL)]\mathbb{E}[\sigma(\beta L)], whereas the target ranking is governed by E[L]\mathbb{E}[L]. When users are heterogeneous, these two quantities can induce different rankings. Consider the following toy example:

Let there be two models AA and BB and only one task. Let β=4\beta = 4. Suppose 10% of users strongly prefer model AA: the latent utility difference for these users is L=10L = 10. The remaining 90% of users slightly prefer BB: the utility difference for these users is L=−1L = -1. In this case, E[L]=0.1\mathbb{E}[L] = 0.1, so model AA should be ranked higher under average utility. However, what standard Bradley-Terry estimates is the average win probability, which in this case is E[σ(βL)]=0.34\mathbb{E}[\sigma(\beta L)] = 0.34. Thus, under average win probability, BB is ranked higher.

Additionally, we implemented and evaluated the standard Bradley-Terry method in our semi-synthetic experiment, and on the hard context distribution, it obtained the correct ranking in only ~14% of runs, given a budget of 100 million comparisons in each run.

The proposed framework requires repeated comparisons of the same model pair within a fixed user-task context. How do the authors envision implementing this procedure in realistic LLM evaluation systems, where repeatedly presenting identical comparisons to the same user may be costly, unnatural, and potentially detrimental to annotation quality?

Our lower bound shows that it is necessary to require repeated comparisons. we agree that it can be hard to implement. In practice, one thing we can do is, grouping similar users and treating each group as one single "user".

All four algorithms rely on a fixed reference model (m_0), but the experiments do not sufficiently investigate how its selection affects performance. How sensitive are the ranking accuracy and sample efficiency of the proposed methods to the choice of (m_0)? Could the authors report results using different reference models, particularly the strongest and weakest models?

We'd like to highlight that our theoretical guarantees are invariant to the choice of the reference model, since we are subtracting the same reference utility and estimating the remaining models' utilities relative to this reference. For our semi-synthetic experiments, changing the reference model will change the LP that we use to construct the hard context distribution. Note that for MLE-CAL, the calibration function is independent of the distribution over contexts once β\beta and Δ\Delta are fixed, so its performance is invariant to the choice of reference model. It is worth comparing the performance of the other three algorithms.

In terms of the experiments, we already choose the reference model to be the weakest model (model 5) in the semi-synthetic experiments. We reran the semi-synthetic experiment for each additional choice of reference model, reoptimizing the weights of the hard context distribution each time. For MLE-UNCONST and TRR, the performance was robust and invariant to the choice of the reference model. For MLE-AVG, reference models 1 (the strongest model) and 2 produced the same results as model 5, where the performance of the algorithm was good close to the empirical context distribution but sharply deteriorated closer to the hard context distribution. If we chose the reference models to be 3 or 4, we actually found that MLE-AVG performed well (required a repetition budget of 1) for all values of λ\lambda, the parameter we used to interpolate between the empirical and hard distributions.

In other words, the choice of reference model does substantially affect the performance of MLE-AVG in our experiments. That being said, in practice, it is not clear which reference model one should choose since we do not have a ground truth ranking. Although MLE-AVG can mirror the performance of the other algorithms in some cases, those algorithms are robust to the choice of context distribution and reference model, as we have shown both theoretically and empirically.

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

Machine learning models are often ranked using ordinal preference data. These data are collected across a wide variety of users with heterogeneous preferences. When these preferences conflict, a single comparison per user may be insufficient to recover the ranking by average utility, even with many users. The authors study situations where the same user compares the same two models on the same task more than once, and propose two corrected MLE-based algorithms as well as a randomized method. All three need only a few extra repetitions as two models get closer to a tie, while the randomized method uses a constant number of comparisons. They test these methods on synthetic and semi-synthetic data and find that they recover the true ranking with fewer repetitions, on harder instances, than directly averaging uncorrected MLE estimates.

Critical strengths
  • The paper addresses a real issue with heterogeneous preferences, where a single comparison per user may not recover the ranking. The authors prove that repeated comparisons can resolve this, and that the algorithm used makes a large difference to how many are needed. The experiments show this clearly, with the corrected methods needing far fewer repetitions on harder instances than the naive MLE approach.
Critical weaknesses
  • While I recognize that this paper is largely theoretical, I am not sure its assumptions about repeated comparisons hold in practice. The analysis assumes independent judgments within each user-task context, but repeated judgments from the same user may be correlated. I would like to see a discussion of how these comparisons could be collected and whether the bias correction remains useful when this assumption is violated.
  • In the Arena experiment, the authors change the mix of tasks to show where the uncorrected MLE performs poorly, but do not make clear how often this problem occurs in real evaluations. I would like to see more evidence that the correction matters under typical conditions.
Questions for authors

These are both clarifications, not suggestions for future work.

  • In practice, how would correlated judgments affect the bias correction?
  • How often does the uncorrected MLE give the wrong ranking in practice? Is there existing evidence in the Arena data?
7 comments

We sincerely thank the reviewer for their time and feedback.

While I recognize that this paper is largely theoretical, I am not sure its assumptions about repeated comparisons hold in practice. The analysis assumes independent judgments within each user-task context, but repeated judgments from the same user may be correlated. I would like to see a discussion of how these comparisons could be collected and whether the bias correction remains useful when this assumption is violated.

We appreciate the reviewer raising this important concern. We want to emphasize that in our setting, tasks represent a large set of prompts belonging to some category rather than a single prompt. Some examples of tasks could be coding, math, writing, etc... When we talk about repeated comparisons, we are not asking users to evaluate the exact same pair of responses repeatedly, which can certainly introduce bias and correlation in their responses. Instead, we can imagine that each task is associated with some distribution over a large set of prompts and collecting each repeated comparison involves sampling a fresh prompt from this distribution, a pair of responses, and asking the user to evaluate these responses. Whenever we do not sample the same prompt (which is true when the task subsumes a large number of prompts), the pairwise comparisons are independent. Hence, we argue that the independence assumption is fairly practical, especially when we are not asking any user for too many comparisons on a particular task.

In the real-world applications where we might not be able to obtain such repeated comparisons from a single user, we could group similar users together to represent a single "user", so we would not necessarily ask a single person for dd comparisons back to back. We will make the definition of a task more clear in the main version of the paper.

We'd also like to emphasize our result about the Truncated Russian Roulette Algorithm showing that the algorithm only requires a constant repetition budget in expectation. In our experiments, the average number of repetitions it requires is at most 2.24, which is actually close to the average number of comparisons per user collected in the LMArena dataset.

In practice, how would correlated judgments affect the bias correction?

Allowing correlation in repeated comparisons reduces the information that we obtain from each comparison. In the extreme case where future comparisons are just copies of the first comparison (fully correlated), we do not gain anything from repeated comparisons and cannot learn the utility function. In this case, our lower bound implies that it is impossible to recover the true ranking in the worst case.

How often does the uncorrected MLE give the wrong ranking in practice? Is there existing evidence in the Arena data?

This is an interesting question! The issue is we don't know the ground truth ranking (which is defined for the population of users and tasks) in the Arena data and thus, we cannot observe whether a ranking is wrong or not.

In practice, Arena runs MLE in the homogeneous setting (assuming that the utilities are identical across users and tasks), which is refuted by their own blog post. This provides motivation for our modeling that models can be heterogeneous in their performance across tasks in addition to users.

Since the ground truth ranking of population-average utilities is unknown, our experiments have to be semi-synthetic. This semi-synthetic experiment setting is common for ranking algorithms when the ground-truth is unknown (see Song et al. and Haghtalab et al.).

Our semi-synthetic experiments use the Arena data to construct utilities. Under the empirical task distribution constructed from the dataset, MLE-AVG (the "uncorrected" MLE algorithm) always recovers the correct ranking in our experiments. However, when the tasks become more heterogenous or the gaps between two models become smaller, MLE-AVG will request many more repeated comparisons. We are not claiming MLE-AVG is bad in practice as we don't observe the true ranking. However, the goal is to understand the scenarios in which MLE-AVG performs poorly and provide algorithms that are more robust to such settings.

Reviewer_cGDsOpenReview ↗

Response to authors

I thank the authors for their response and clarifications, and I recognize the tension between the assumptions of a theoretical framework and practical choices. However, grouping individuals is a fairly drastic change and could significantly affect the guarantees.

While the authors note that MLE-AVG recovers the correct ranking under the empirical Arena task distribution, it is still unclear how often the correction matters under typical conditions. I recognize that the ground truth is not recoverable, but this remains a concern to me.

I would welcome further analysis, and while the responses answer my questions, I will maintain my current score for now.

We thank the reviewer for their response.

However, grouping individuals is a fairly drastic change and could significantly affect the guarantees. Our suggestion for grouping individuals was one possible way to collect the repeated comparisons. If a set of users have the same underlying utilities, then all of the guarantees of our proposed algorithms hold under comparisons collected from that group. We recognize that identifying such groups presents a new challenge.

However, we want to emphasize that even without grouping, if we just collected repeated comparisons from individual users, the worst-case requirements of our proposed algorithms are reasonable both theoretically and in practice. For example, our TRR algorithm required at most 2.24 comparisons on average across our experiments, which is consistent with what the real Arena dataset was able to collect (~2.5 comparisons per user).

The main contribution of this paper is to establish the information-theoretic necessity of repeated comparisons and to propose algorithms with better minimal repetition requirements than MLE-AVG. The grouping suggestion should be understood in that context.

While the authors note that MLE-AVG recovers the correct ranking under the empirical Arena task distribution, it is still unclear how often the correction matters under typical conditions.

We would appreciate it if the reviewer could clarify this statement. If we do not know the underlying ground-truth ranking in practice, then there is no way to directly determine if MLE-AVG produces the correct ranking.

This is part of our motivation for studying the problem theoretically. Our theoretical analysis explicitly characterizes when an algorithm can fail, and we provide new algorithms that have better worst case guarantees than MLE-AVG.

We are not claiming that MLE-AVG frequently fails in real situations. Instead our point is that:

  • MLE-AVG can fail or require substantially more repeated comparisons in certain settings, and we do not know if we are encountering these settings in practice
  • We identify and analyze those settings
  • We provide algorithms with better theoretical worst-case guarantees that are robust to these settings, and we demonstrate this robustness in our experiments as well.

This is a meaningful theoretical contribution even if we do not know how often these worst-case settings for MLE-AVG occur in practice.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.