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

The gist How many repeated pairwise comparisons are needed for ranking under heterogeneity?

This paper investigates how many repeated pairwise comparisons within each user-task context are necessary and sufficient to recover model rankings when preferences vary across users and tasks, which is a crucial problem in human feedback settings.

Problem Setup

The central question addressed is: How many repeated comparisons per user-task context are necessary and sufficient to recover the ranking of models by population-average utility? (Page 2). The study formalizes this using a contextual Bradley–Terry model where each user has a latent bounded utility function ui(t, m) (Page 2). The goal is to estimate the average utility across users and tasks, without assuming any relationship between individual utility functions across different users or tasks or models for the same user (Page 2). The ground-truth ranking is determined by the expected utility u(m) = Ei∼D [ui(m)] (Page 2).

Ranking Recovery and Repetition Budget Complexity

The paper defines the minimum repetition budget dA(ε, δ) as the smallest positive integer d for which there exists a finite positive integer n and a model-pair sampling distribution C such that P RankErr(A(S)) = 0 ≥ 1 − δ (Page 3). The optimal repetition budget is defined as d⋆(ε, δ):= inf A dA(ε, δ) (Page 3). The authors analyze four algorithms:

1. MLE-Based Algorithms: These start with maximum likelihood estimation to estimate context-level utility functions ui(t, m) (Page 3). A naive approach requires a repetition budget of Ω(1/∆2) because of estimation bias (Page 4). Two improved MLE-based variants and a randomized Russian Roulette-style algorithm reduce this budget to O(log(1/∆)) repeated comparisons per context (Page 4).

2. Russian Roulette-Based Algorithm: This introduces a randomization technique that uses only O(1) comparisons in expectation, while still achieving a repetition budget logarithmic in 1/∆ (Page 4).

3. Information-Theoretic Lower Bound on the Repetition Budget: This provides a lower bound showing that any ranking algorithm must require a repetition budget with logarithmic dependence on 1/∆, proving that the logarithmic dependence is optimal (Page 3).

MLE-Based Algorithms Analysis

The constrained MLE estimator with naive empirical aggregation, AMLE-AVG, requires a repetition budget of dAMLE-AVG (ε, δ) ≥ Ω(1/ε2) because of estimation bias (Page 6). Two improved MLE-based algorithms are introduced that obtain an improved repetition budget of O(log(1/ε)) (Page 6). Specifically, AMLE-CAL and AMLE-UNCONST satisfy dAMLE-CAL (ε, δ) ≤ O log 1/ε and dAMLE-UNCONST (ε, δ) ≤ O log 1/ε (Page 7). The analysis shows that the constrained MLE can be calibrated to control bias, leading to bounds like dAMLE-CAL (ε, δ) ≤ O log 1/ε and dAMLE-UNCONST (ε, δ) ≤ O log 1/ε (Page 7).

Randomized and Truncated Algorithms

The Truncated Russian Roulette (TRR) Estimator achieves a repetition budget of dATRR (ε, δ) ≤ O log 1/ε, and in expectation uses only a constant number of repeated comparisons per context, E[Kj] = O(1) (Page 8). The proof for ATRR shows that the bias decays exponentially with d when d = O log 1/ε) (Page 9). The Untruncated Russian Roulette (URR) Algorithm, which allows an unbounded number of comparisons, also achieves a repetition budget of dATRR(ε, δ) ≤ O log 1/ε but does not admit a deterministic upper bound on the number of comparisons (Page 10).

Lower Bound and Optimal Budget

The information-theoretic lower bound shows that the optimal repetition budget is d⋆(ε, δ) = Θ log 1/ε (Page 3). This is derived by constructing two population distributions µ+ and µ− that are indistinguishable given only d repeated comparisons but for which the average utility difference has opposite signs (Page 3). The proof involves controlling the error Ed:= inf P:deg(P)≤d sup p∈[σ(−β),1−σ(−β)] h(p) − P(p) (Page 37). This leads to the conclusion that d⋆(ε, δ) = Ω log 1/ε (Page 43).

Experimental Results

Synthetic and semi-synthetic experiments compare the four algorithms across varying levels of preference heterogeneity h and context distributions. The results indicate that AMLE-AVG can significantly degrade under harder problem instances, while the other three algorithms are robust to changes in heterogeneity levels or the underlying task distribution (Page 11). For instance, Table 3 shows that for fixed d = 32, the synthetic MLE-AVG has a minimum score gap of-0.0324717 under the synthetic regime (h=1) and Arena regime (λ=0.005), whereas AMLE-CAL and AMLE-UNCONST maintain a gap close to 1.0, illustrating their robustness (Page 52). The results also show that ATRR's expected number of comparisons E[Kj] = O(1) regardless of the minimum average utility gap ∆ (Page 47).

Conclusion

The paper concludes that for any fixed ε and δ, there exists a model-pair sampling distribution C such that the repetition budget d⋆(ε, δ) = Ω log 1/ε (Page 43). This result establishes the logarithmic dependence on the inverse of the utility gap as necessary and sufficient for ranking recovery under heterogeneity. The total number of pairwise comparisons required is O(M ε2 log 1/ε log M δ) (Page 47).

--- Page 1 ---

How Many Repeated Pairwise Comparisons Are Needed for Ranking under Heterogeneity? Shashaank Aiyer and Han Shao University of Maryland 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 omega(1/∆2) repeated comparisons per context to ensure ranking recovery. We then present two MLEbased variants and a randomized Russian Roulette-style algorithm that recover the ranking using O(log(1/∆)) repeated comparisons per context, and we prove that this logarithmic dependence is optimal. Despite this worst-case requirement, our Russian Roulette algorithm uses only O(1) 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.1 Introduction In recent years, human feedback in the form of pairwise comparisons has become a key instrument for evaluating and aligning large language models. Rather than asking for quantitative scores, platforms like LM Arena [Chiang et al., 2024] present users with two model responses associated with a given prompt and ask which is better. LM Arena uses such comparisons to construct global model leaderboards, while RLHF uses them to learn reward models that guide finetuning [Ouyang et al., 2022, Christiano et al., 2017]. Two features of pairwise human feedback introduce complications to these tasks: the heterogeneity of users and the price of obtaining pairwise comparison data. First, preferences across users and tasks can genuinely differ, making it somewhat impractical to assume a shared global ranking. For example, one user could prefer concise responses for some tasks and detailed explanations for others while another user’s preferences are completely flipped. The standard procedure of fitting a single Bradley-Terry (BT) model inherently ignores these discrepancies and treats variation in user preferences as noise surrounding an agreed-upon ranking of models. Gölz et al. [2025] show quantitatively that the BT-based alignment can fail to optimize for population-level average utility under heterogeneous user preferences. Pukdee et al. [2026] also study this problem, characterizing precise conditions under which heterogeneous preference data admits a BT representation (Page 1).

--- Page 2 ---

Figure 1: Ranking from repeated pairwise comparisons. For each of n independently sampled user-task contexts, we sample one model pair and collect d independent comparisons of that pair. The ranking algorithm consists of an estimator that estimates context-level utilities and an aggregator that combines these estimates to recover the ranking induced by population-average utility. The second limiting feature of pairwise comparison data involves the high cost of obtaining feedback, particularly as AI models scale to increasingly specialized applications and tasks. We believe that this evaluation cost problem appears at an even more granular level than simply obtaining feedback from additional users. In particular, even in instances where a platform is able to collect a large number of pairwise comparisons, it may be difficult to obtain repeated comparisons from any one user. For example, Chiang et al. [2024] obtained 240,000 votes in their January 2024 dataset, and these votes were dispersed across 90,000 users, fewer than three votes per user on average.

1. Bold header: Robust Ranking Recovery Under Heterogeneity

The improved system can recover rankings even when user preferences vary across tasks by using a repetition budget of only

O(log(1/∆)) repeated comparisons per context, rather than the naive

omega(1/∆ 2) required by MLE-based methods. This is achieved by utilizing the randomized Russian Roulette-style algorithm, which recover[s] the ranking using O(log(1/∆)) repeated comparisons per context and in expectation, it only uses a constant number of repeated comparisons per context.

2. Bold header: Low-Cost Ranking Evaluation

The system can perform ranking evaluation with significantly reduced data requirements by employing the Truncated Russian Roulette (TRR) estimator, which allows for an expected constant number of repetitions per context. This enables the system to achieve a total number of pairwise comparisons at most

O(Mε squared log Mδ), which is crucial for scaling in specialized applications where obtaining feedback is costly.

3. Bold header: Bias-Corrected Ranking via Calibration

The system can utilize the AMLE-CAL algorithm to mitigate estimation bias by employing a calibration function, which minimizes the largest absolute table entry subject to a bias constraint of at most

ε/8 for every model difference D in [−1, 1]. This ensures that the aggregated ranking preserves every strict average-utility ordering, even when using a fixed repetition budget.

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 (Golz 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 Ω(1/Δ 2) 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 O((1/Δ)) repeated comparisons per context, and we prove that this logarithmic dependence is optimal. Despite this worst-case requirement, our Russian Roulette algorithm uses only O(1) 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.