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

• With heterogeneous preferences, one user's data need not reveal another's utility, and a single comparison per user can leave population-average utility unrecoverable.The nonlinear Bradley-Terry link means many single comparisons reveal the sign of E[σ(βL)] − 1/2, which can differ from the sign of E[L].Source: §1 · p. 2
• O(log(1/∆)) repetitions per context suffice for improved MLE and Russian Roulette methods, and a lower bound makes this dependence optimal.Source: §1 · p. 3
• The naive MLE approach can require Ω(1/∆^2) repetitions per context because estimation bias impairs ranking aggregation.Source: §1 · p. 3
• Russian Roulette randomizes the number of comparisons actually used, retaining a logarithmic budget while averaging O(1) comparisons per context.Source: §1 · p. 3
• Synthetic and Arena-based semi-synthetic experiments compare four algorithms across varying preference heterogeneity and context distributions.Source: §1 · p. 3

• Ground-truth rankings follow expected utility: each user's utility for a model averages over that user's task distribution, then expectations are taken over users.Source: §2 · p. 3
• The observations are task-level pairwise comparisons for sampled contexts and model pairs, with outcomes following Bradley-Terry at inverse temperature β > 0.Source: §2 · pp. 3–4
• The objective is to characterize the smallest repetition budget that permits ranking recovery using finitely many sampled contexts.Source: §2 · p. 4
• The (ε, δ)-repetition budget is the smallest positive d for which some finite context count n and pair-sampling distribution work across instances with minimum utility gap ∆ ≥ ε.The context count may depend on the algorithm, ε, δ, β, and the number of models, but not on the particular instance.Source: §2 · p. 4

3.1 MLE-Based Algorithms

• With a finite repetition budget, AMLE−AVG’s constrained MLE can have bias of order 1/√d; its empirical average can concentrate around a biased expectation, yielding a repetition-budget lower bound quadratic in 1/ε.For a context with true utility difference 1, estimates above 1 are truncated to 1; with d Bernoulli comparisons, this results in downward bias of order 1/√d.Source: §3.1 · pp. 5–6

3 Ranking Algorithms and Analyses

• The improved MLE-based algorithms and truncated Russian Roulette achieve O(log(1/ε)) repetition budgets, and a lower bound makes this dependence optimal.The Russian Roulette method additionally uses O(1) repeated comparisons per context in expectation.Source: §3 · p. 5, §3.2 · p. 7, §3.3 · p. 10

3.1 MLE-Based Algorithms

• AMLE−CAL and AMLE−UNCONST control estimation bias through calibration or a finite transformation whose bias decays exponentially with d.For AMLE−UNCONST, the transformation truncates a series whose tail decays exponentially with d.Source: §3.1 · pp. 6–7

3.2 Truncated Russian Roulette (TRR) Estimator

• ATRR truncates a randomized estimator of context-level utility differences, yielding logarithmic repetition budgets and constant expected comparisons per context.Truncating at d makes the statistic biased, but the bias decays exponentially with d.Source: §3.2 · pp. 7–9

3.3 Lower Bound on Repeated Comparisons

• The lower bound constructs two populations indistinguishable from d comparisons but with opposite signs for their average utility differences.Matching the first d moments makes the comparison data indistinguishable; the logit utility difference need not have matching expectations.Source: §3.3 · p. 10

4 Experiments

• Synthetic experiments fix five models’ average-utility ranking, varying heterogeneity at ∆ = 0.015 and separately varying ∆ from 0.06 to 0.002 at h = 1.The heterogeneity parameter ranges from homogeneous utilities at h = 0 to high heterogeneity at h = 1.Source: §4 · p. 11
• Semi-synthetic experiments fit Bradley–Terry scores across 30 prompt clusters, then vary task-distribution difficulty while preserving each model’s population-average utility.The population uses the arena-human-preference-140k dataset [Chiang et al., 2024], with five selected LLMs and ∆ = 0.005.Source: §4 · p. 11

Results.

• AMLE−AVG’s repetition budget degrades on harder instances and depends more sharply on 1/∆; ATRR’s expected comparisons range from 1 to 2.24.Figure 4 uses synthetic populations with fixed h = 1; its solid and dotted lines distinguish ATRR’s expected and maximum comparisons.Source: Results · pp. 11–12, Figure 4 · p. 12

C.1 Formal Definition of AMLE−AVG

• The MLE variants aggregate estimated utility differences across contexts; AMLE−CAL calibrates estimates first, while AMLE−UNCONST applies a harmonic transformation before averaging.AMLE−AVG directly averages estimates relative to a reference model.Source: §C.2 · p. 17, §C.1 · p. 17, §C.3 · p. 18

C.4 Proof of Proposition 3.1

• With utility differences 1 and −1/2 across user types, the true average can favor a model while the averaged constrained-MLE estimate has negative expectation.Increasing the number of contexts cannot resolve the wrong-sign expectation.Source: §C.4 · pp. 19–20
• For any finite number of contexts, direct constrained-MLE averaging can rank models incorrectly even when their average-utility gap is positive.The proof constructs populations with a fixed positive gap for which the estimator’s expected value has the wrong sign.Source: §C.4 · pp. 20–21
• For fixed d, the expected constrained MLE is a degree-d polynomial in the Bradley–Terry win probability, unlike the true utility difference’s log-odds form.This mismatch supports a two-population testing argument for a fixed positive utility gap.Source: §C.4 · p. 21

C.5 Proof of Theorem 3.2

• AMLE−CAL’s proof constructs a degree-d polynomial approximating the log-odds utility function while respecting constrained-MLE truncation.The construction sets the polynomial’s value at 1/2 to zero, matching the log-odds function there.Source: §C.5 · pp. 21–22
• For AMLE−UNCONST, the proof uses a truncated series representation of contextual utility differences to control estimator bias.The proof then controls variance and estimator magnitude before establishing ranking preservation.Source: §C.5 · pp. 29, 31
• AMLE−CAL and AMLE−UNCONST have repetition-budget upper bounds, and their estimates preserve the strict average-utility ordering.The proof bounds the calibrated estimator’s error relative to the minimum nonzero utility gap and separately establishes ranking preservation for AMLE−UNCONST.Source: §C.5 · pp. 28, 31

D.1 Formal Definition of ATRR

• ATRR randomly selects a comparison cutoff K_j within each context and forms its statistic from wins in the first K_j comparisons.The cutoff is drawn independently for each context.Source: §D.1 · p. 32

D.2 Proof of Theorem 3.4

• Theorem 3.4 gives an upper bound on ATRR’s repetition budget for fixed ε and δ.The supplied theorem statement does not expose the bound’s explicit form.Source: §D.2 · p. 32
• The proof controls the estimator’s bias and variance before applying concentration bounds to recover the ranking.The estimator’s conditional expectation is a series representation of the contextual utility difference, truncated at d.Source: §D.2 · pp. 33–35
• ATRR’s estimator preserves the ranking under average utility, and the proof calculates an O(1) expected comparison count per context.The expectation is obtained by summing the cutoff’s tail probabilities.Source: §D.2 · p. 35

E Lower Bound

• The construction uses two distributions over Bradley–Terry win probabilities that share their first d moments but induce opposite signs of expected utility difference.The utility difference is the log-odds function of the win probability, and the lower-bound gap is tied to its best degree-d polynomial approximation.Source: E Lower Bound · pp. 37, 40, 41
• Matching the first d moments makes the distributions of d repeated comparisons identical, although the populations have opposite expected utility differences.The lower bound uses two model alternatives and one task; for sufficiently large populations, the indistinguishable datasets prevent a ranking guarantee when the induced gap exceeds the approximation error.Source: E Lower Bound · pp. 40–42
• Because d comparisons yield outcome likelihoods that are polynomials of degree at most d, matching those moments makes their outcome laws agree.This moment-matching argument applies to each comparison vector and hence to sampled datasets conditional on all sampled users being distinct.Source: E Lower Bound · pp. 40–41
• For sufficiently large populations, the two constructed instances have opposite average-utility rankings while their sampled datasets remain arbitrarily hard to distinguish.The proof selects the population size so repeated sampling of the same user is unlikely, then uses the opposing utility gaps to contradict any uniform error guarantee below one half.Source: E Lower Bound · p. 42

F Untruncated Russian Roulette (URR) Algorithm

• Unlike the truncated variant, URR allows an unbounded number of comparisons in a context, so it cannot guarantee a deterministic repetition limit.The benefit is that the estimator can be defined without knowing the minimum average-utility gap Δ.Source: F Untruncated Russian Roulette (URR)… · pp. 44, 47
• The untruncated estimator recovers the average-utility ranking with probability at least 1 − δ uniformly over instances with gap Δ ≥ ε, while using O(1) comparisons per context in expectation.Its random comparison count has a geometric distribution with constant expectation.Source: F Untruncated Russian Roulette (URR)… · pp. 44, 47
• Randomizing the comparison count yields an unbiased estimator of the average utility difference between a model and the reference model.The estimator is unbiased conditional on a context and therefore also after averaging over contexts.Source: F Untruncated Russian Roulette (URR)… · p. 45
• URR aggregates model-specific estimates with a median-of-means estimator to control deviations despite the statistic being unbounded.The proof uses Chebyshev’s inequality to obtain the desired logarithmic dependence on |M|/δ.Source: F Untruncated Russian Roulette (URR)… · pp. 44, 46, 47

G Experiments

• The experiments describe their methodology and additional results beyond those in the main paper.The experimental section begins with an observation model that treats users and tasks as contexts.Source: G Experiments · p. 48, §G.1 · p. 48

G.1 Observation Model

• Each sample draws a context by its weight, selects a non-reference model uniformly, and compares it with the fixed reference model.Within a context and model pair, outcomes are independent Bernoulli draws; repeated comparisons retain that context and pair.Source: §G.1 · p. 48
• The experiments set β = 1, and none of the algorithms observes the latent utilities.The three MLE-based algorithms use d comparisons deterministically per sample, whereas truncated Russian Roulette randomizes the count and reports both its maximum and expected count.Source: §G.1 · p. 48

G.2 Synthetic Experiment Construction

• The synthetic setup uses five models with model 4 as the reference, and the target ranking is 1 ≻ 2 ≻ 3 ≻ 4 ≻ 5.The minimum gap Δ is between models 3 and 4.Source: §G.2 · p. 48
• Increasing h shifts probability toward two opposing preference profiles and increases variance without changing the mean utility vector.At h = 0 the population is homogeneous; h controls the variance linearly.Source: §G.2 · pp. 48–49
• One synthetic experiment fixes Δ = 0.015 and sweeps h from 0 to 1 in increments of 0.1.Source: §G.2 · p. 49
• A second experiment fixes h = 1 and sweeps Δ from 0.06 down to 0.002 across ten tested gaps.Source: §G.2 · p. 49

G.3 Semi-Synthetic Experiment Construction

• Arena prompts are embedded and clustered into context types, where Bradley–Terry fits to decisive votes estimate relative performance for 52 models before five sufficiently observed models are selected.The five selected models include four named alternatives and mistral-medium-2505 as the reference.Source: §G.3 · p. 49
• AMLE−AVG’s one-comparison score difference between models 4 and 5 guides the hard context reweighting, with model 5 serving as reference at β = 1.The resulting context-level utilities are designed to lie in [0, 1].Source: §G.3 · p. 49
• The utility construction centers fitted cluster scores while preserving the fixed average-utility ranking, and an LP reweights contexts by at most a factor of five before interpolation with the empirical distribution.The experiment varies λ from 0 to 1 while holding the minimum average-utility gap at 0.005.Source: §G.3 · pp. 49–50

G.4 Algorithm Implementations

• AMLE−CAL maps each possible constrained-MLE estimate to a calibrated value chosen by linear programming to keep expected bias within ε/8 across utility differences.The experiments set ε = ∆/2, giving a target bias of at most ∆/16.Source: §G.4 · p. 50
• Calibration tables are checked across the full utility-difference interval and reused when d, β, and ε match; aggregation averages the table-adjusted context estimates.A depth is rejected if no table passes the checks.Source: §G.4 · p. 50

G.5 Estimating the Repetition Budget in the Experiments

• Repetition budgets are estimated by enumerating finite-context score distributions and selecting the first tested depth with positive ranking margin above 10^-12.Reported depths are the first successful values in the tested grid, not necessarily the optimal repetition budgets.Source: §G.5 · p. 51

G.6 Results

• AMLE−AVG uses as many as 512 repeated comparisons in the synthetic regime and 96 in the Arena regime, while the other three algorithms remain relatively stable as heterogeneity or context distribution varies.The reported values are first successful depths on some finite n, not necessarily depths minimizing total comparisons.Source: §G.6 · p. 51, Table 1 · p. 51
• The synthetic gap sweep holds h = 1 fixed while varying ∆, with Table 2 reporting first successful depths and both maximum and expected comparisons for TRR.The reported depth may not minimize total comparisons.Source: Table 2 · p. 52, §G.6 · p. 52
• At fixed d = 32, AMLE−AVG has a negative population score gap in both populations, so its full-ranking recovery probability tends to zero as contexts grow.AMLE−UNCONST and AMLE−TRR have identical population expected scores by design at a common repetition budget, but their finite-context recovery frequencies can differ.Source: §G.6 · pp. 52–53, Table 3 · p. 52