acceptodds
Under review as a conference paper at ICLR 2027

Convergent Elo: Online Pairwise Evaluation as Estimation

11 views

Abstract

Pairwise comparisons are increasingly relied upon to benchmark machine learning systems. When aggregated into a score for a fixed population, these comparisons pose an estimation problem: the reported ratings should settle as evidence accumulates. Fixed-gain Elo acts instead as a tracking algorithm: under noisy stationary comparisons, its ratings continue to fluctuate. We introduce Convergent Elo (CElo), which preserves Elo's two-participant online updates whilst decaying each participant's gain with respect to its own comparison count. We prove almost-sure convergence of the full rating vector under stationary outcome means and any fixed i.i.d. matchmaking distribution with connected support, without requiring global recentring. Further, we identify the limiting relative ratings: under Bradley–Terry realisability, CElo recovers latent strengths up to translation; under misspecification, it converges to the matchmaking-weighted KL-optimal Bradley–Terry approximation. Our analysis establishes a general convergence result for heterogeneous-gain stochastic approximation, deriving stability from coercivity on the identifiable subspace without assuming bounded iterates or imposing projection. In simulations of a stationary population calibrated from Arena Text data, CElo continues to reduce population-target error after fixed-gain Elo plateaus. A controlled ablation shows a clear finite-horizon advantage for participant-local over global gains under heterogeneous participation. Across four chronologically ordered applied datasets, CElo achieves lower prequential BCE than fixed-gain Elo on three, including text and vision model arenas, with no clear difference on the fourth.

Primary area:
optimization
Keywords:
stochastic approximation, Elo rating systems, Bradley–Terry models, pairwise comparisons, machine learning evaluation, model misspecification, online learning, statistical estimation

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

This paper proposes Convergent Elo (CElo), an online pairwise evaluation method that replaces Elo's fixed learning rate with participant-specific diminishing learning rates based on individual comparison counts. The authors establish almost-sure convergence of both relative ratings and the full rating vector under stationary outcomes and fixed, potentially nonuniform matchmaking.

Critical strengths

A major strength of this paper is its theoretical analysis of the convergence properties of Elo with participant-specific diminishing learning rates. The authors establish almost-sure convergence of both relative ratings and the full rating vector under nonuniform matchmaking, without requiring Bradley–Terry realizability or global recentering.

Critical weaknesses
  1. The experiments on real LLM evaluation rely entirely on historical Arena Text (2025) and Arena Vision (2024) comparison records, which raises concerns about their relevance to more recent LLMs and evaluation settings. More importantly, CElo achieves only marginal improvements over standard Elo, with BCE reductions of just 0.000616 and 0.003378 on the two datasets, respectively. Furthermore, the paper does not provide a direct comparison with a properly tuned global diminishing-gain Elo baseline on real Arena data, despite emphasizing participant-local learning rates as a key design choice. These limitations make it difficult to assess the practical significance of the proposed method.

  2. The paper presents participant-local diminishing K-factors as a central contribution, but a closely related approach has already been explored in Elo-based Learner Modeling for the Adaptive Practice of Facts (Pelánek et al., 2017, User Modeling and User-Adapted Interaction), which is not cited or discussed. In particular, the prior work uses a participant-specific learning rate of the form Ki(n)=A/(1+Bni)K_i(n)=A/(1+Bn_i), which is mathematically equivalent to CElo's proposed schedule when (\alpha=1), up to reparameterization. This substantial overlap raises concerns about the algorithmic novelty of CElo.

Questions for authors

Could the authors clarify the algorithmic differences between CElo and Pelánek et al. (2017)? In particular, the participant-specific diminishing learning rate proposed in the prior work appears mathematically equivalent to CElo's update schedule when (\alpha=1). What are the key algorithmic contributions of CElo beyond this existing approach?

1 comment

Thank you for the review, especially for pointing us to Pelánek et al. (2017) and identifying the missing comparison with a tuned global-clock baseline on Arena. We have clarified the overlap with prior work and added the direct comparison.

What is new relative to Pelánek et al. (2017)? We agree that their gain U(n)=A/(1+Bn)U(n)=A/(1+Bn) is equivalent, up to reparameterisation, to the CElo gain at α=1\alpha=1. We now credit this overlap in Related Work (Section 1.3) and alongside the update rule (Section 2). We do not claim novelty for inverse-count decay or participant-local counters. Pelánek et al. use the schedule to estimate student ability and item difficulty in an online system for learning geography. They show empirically that the estimates settle and agree closely with joint maximum likelihood estimates.

Their work does not prove almost-sure convergence of the unprojected rating vector, including its common offset, or characterise the limiting relative ratings under Bradley–Terry misspecification. Theorem 1 and Proposition 1 establish these results under fixed i.i.d. matchmaking with connected support and stationary conditional outcome means, without assuming bounded iterates or requiring projection or recentring. Under misspecification, the limiting relative ratings minimise the matchmaking-weighted KL discrepancy. The revision also derives asymptotic confidence intervals for rating differences (Theorem 3) and a fixed-sample confidence set for the population target (Proposition 2, Appendix C.6). These results, rather than the inverse-count update itself, are the paper's primary contributions.

The algorithmic extension is to allow a tunable exponent 1/2<α≤11/2<\alpha\le1 rather than fix inverse-count decay. This specification has meaningful theoretical implications. For instance, this range gives the Robbins-Monro-type nonsummable but square-summable gains used in our convergence proof. Under Theorem 3's conditions, the centred error is OP(n−α/2)O_P(n^{-\alpha/2}), and only the α=1\alpha=1 case requires an additional spectral condition. For 1/2<α<11/2<\alpha<1 under Bernoulli outcomes and Bradley–Terry realisability, the pairwise interval uses only the two participants' current ratings and gains. The choice of exponent also matters empirically: among unaveraged CElo configurations in Fig. 1, α=0.90\alpha=0.90 has the lowest median error at the validation horizon, whereas α=1\alpha=1 has the lowest at 10810^8 comparisons.

Direct comparison with tuned global-clock Elo and practical gains. We now tune global-clock Elo independently on each practical chronological dataset, expanding the search domains where validation approached a boundary (Appendix E.6). The paired moving-block bootstrap compares per-comparison loss differences on the same held-out observations while resampling contiguous blocks. The 95% intervals favour CElo over both tuned global-clock Elo and fixed-gain Elo on Arena Text, Arena Vision, and BASIL across all tested block lengths, with no clear difference on TCEC (Tables 6–7 and Appendix E.6). Though CElo's absolute raw BCE gains over fixed-gain Elo are modest, they are comparable in magnitude to TrueSkill's on both Arena streams. The results show that the convergent update remains competitive for prediction on the evaluated streams; they do not establish definitive superiority of one method over another.

Choice of Arena releases. arena-human-preference-140k and VisionArena-Battle are the most recent comparable large-scale public Arena releases we identified that provide timestamped individual human votes. Newer public leaderboard snapshots report aggregates and cannot be used to replay the rating updates. Our question is how rating rules learn from the same sequence of preferences, not how the latest models rank. Model identities serve only to index the ratings, so the age of the models does not invalidate the comparison. What may affect the result is a change in the comparison process itself, such as more uneven participation or a different degree of Bradley–Terry misspecification. We therefore do not assume the observed gains carry over to newer streams.

Controlled estimation experiments. In revised Fig. 2, we independently tune the initial gain, clock offset, and decay exponent for both clocks with equal validation budgets. CElo reduces mean final target error by 6.3-39.9% across the four heterogeneous regimes, while the methods are nearly tied under homogeneous participation. In Fig. 1, we tune configurations independently on shared validation streams and add time-averaged Elo and time-averaged CElo. All five unaveraged CElo configurations finish with lower median target error than both fixed-gain and time-averaged Elo, and time-averaged CElo finishes with the lowest median error. These simulations measure estimation error against a known stationary target, complementing the held-out predictive comparisons.

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

The paper proposes Convergent Elo (CElo), an online pairwise estimator that replaces Elo's fixed learning rate with participant-local gains that decay with each participant's comparison count. For a fixed finite population, stationary conditional outcome means, and fixed i.i.d. matchmaking with connected support, it proves almost-sure convergence of both relation ratings and the unrecentered rating vector. Under Bradley-Terry realizability, the limiting relative ratings recover latent strengths; under misspecification, they minimize a matchmatching-weighted KL divergence. The analysis combines convergence on the identifiable subspace with a separate argument controlling the common rating offset. Stationary simulations demonstrate continued error reduction beyond fixed-gain Elo's plateau, while controlled experiments show benefits from local clocks under heterogeneous participation. Chronological evaluations report lower predictive cross-entropy than Elo on 3 of 4 datasets. Practical conclusions remain limited by the absence of finite-time guarantees, restrictive sampling assumptions, and modest predictive improvements relative to established alternatives.

Critical strengths

S1. Substantive convergence guarantee. The analysis establishes stability without assuming bounded iterates or requiring projection, and separately proves convergence of the common rating offset.

S2. Clear statistical interpretation. The paper explains what CElo estimates under both realizable and misspecified models, making the role of matchmaking explicit.

S3. Simple implementation. CElo updates only the two participants in each match and uses local comparison counters, without requiring global recentering.

S4. Well-structured empirical evaluation. Paired simulations isolate the effect of the clock mechanism, while chronological predictive evaluation uses validation-based tuning and reports uncertainty and stronger baselines.

Critical weaknesses

W1. Limited finite-sample guidance. Almost-sure convergence does not provide sample-complexity bound or clear guidance for choosing decay parameters. Simulations with up to 10810^8 comparisons also leave practical efficiency uncertain.

W2. Restricted theoretical scope. . The theory assumes fixed populations, stationary means, and fixed i.i.d. matchmaking. It does not cover adaptive matchmaking or changing model populations. The reset variants are also not covered by the convergence guarantee.

W3. Incomplete comparison for estimation efficiency. The local/global ablation shares calibration rather than tuning each method separately, and the stationary experiments omit time-averaged Elo as a baseline for estimation accuracy.

W4. Modest practical gains. Table 4 shows small BCE improvements over Elo (approximately 0.0006-0.0034) across three datasets, but CElo does not consistently outperform TrueSkill or Glicko. Better predictive performance also does not necessarily imply more accurate benchmark rankings or better uncertainty estimates.

Questions for authors
  1. Does the local-clock advantage persist when local and global schedules are tuned separately using equal validation budgets?

  2. Can finite-time convergence bounds show how convergence depends on minimum participation probability, graph connectivity, and the decay exponent?

2 comments

Thank you for the review. In response, we added two uncertainty results, reran the local/global comparison with independent tuning, and added time-averaged baselines to the stationary and chronological evaluations.

Q2 / W1: Rates, uncertainty, and parameter guidance. The revision quantifies asymptotic error and gives a separate finite-sample guarantee for the population target. It does not give a nonasymptotic error bound for the current CElo iterate which we leave for future work.

Theorem 3 gives a central limit theorem for the centred rating error scaled by nα/2n^{\alpha/2}. The limiting covariance solves a Lyapunov equation involving the effective gains Dii=ciπi−αD_{ii}=c_i\pi_i^{-\alpha}, the Hessian J=∇2Lq(zq∗)J=\nabla^2\mathcal{L}_q(z_q^{\ast}), and the innovation covariance. Participation rates and the decay exponent enter through the gains, while the comparison graph is made relevant through the Hessian. At α=1\alpha=1, the smallest eigenvalue of (ΠDΠ)J(\Pi D\Pi)J on the identifiable subspace must exceed 1/21/2. A consistent plug-in covariance estimate yields approximate confidence intervals for fixed rating differences. Under Bernoulli outcomes, Bradley–Terry realisability, and 1/2<α<11/2 < \alpha < 1, the interval uses only the two participants' current ratings and gains:

Rn,i−Rn,j±z1−δ/2(λn,i+λn,j)/2.R_{n,i}-R_{n,j}\\ \pm\\ z_{1-\delta/2}\sqrt{(\lambda_{n,i}+\lambda_{n,j})/2}.

Appendix C.6 inverts an Azuma–Hoeffding bound on the empirical score to obtain a confidence set for the population target. At a prespecified sample size, it gives simultaneous coverage for all pairwise target differences, even if the reported pairs are chosen after inspecting the ratings. It allows misspecification and does not require known matchmaking probabilities, though the intervals can be wide or unbounded.

For parameter choice, 1/2<α<11/2 < \alpha < 1 avoids the additional spectral condition at α=1\alpha=1 and permits the local interval under the conditions above. In the stationary simulation (Fig. 1), α=0.90\alpha=0.90 and α=1\alpha=1 give the lowest median errors among unaveraged CElo configurations at the validation horizon and the end of the run, respectively. On BASIL, validation selects α=0.50023\alpha=0.50023, which keeps the gains from decaying as quickly. These results illustrate the trade-off between settling and responsiveness rather than prescribing a single exponent.

Q1 / W3: Independent tuning and averaging. In revised Fig. 2 and Appendix E.4, we independently tune the initial gain, clock offset, and decay exponent for each method in each regime, with 99 validation trials per method and 32 held-out paired streams per regime. After 10710^7 comparisons, the two methods have nearly identical mean centred target error under homogeneous participation (0.02853 vs. 0.02854). CElo reduces mean final error by 6.3–39.9% across the four heterogeneous regimes, with paired 95% bootstrap intervals excluding zero in each.

In revised Fig. 1, both time-averaged baselines are independently tuned. All five unaveraged CElo configurations finish with lower median target error than time-averaged Elo, and time-averaged CElo has the lowest terminal median error (0.0165). By contrast, cumulative averaging worsens held-out predictive BCE for both Elo and CElo on all four chronological streams (Table 6). Averaging helped stationary estimation in Fig. 1 but did not improve prediction on the evaluated streams.

W2: Scope of the guarantees. The convergence theorem does not cover adaptive matchmaking, changing populations, or the reset variants. However, it allows arbitrarily nonuniform fixed matchmaking on connected support and does not require Bradley–Terry realisability or independent outcomes. CElo can be run without knowing the matchmaking distribution or verifying stationarity. The practical chronological experiments assess prediction where these assumptions need not hold.

W4: Practical gains and contribution. The raw BCE gains are indeed modest and do not definitively establish better benchmark rankings or more accurate uncertainty estimates. However, on both Arena streams, CElo's gains over fixed-gain Elo are comparable in magnitude to TrueSkill's. Paired moving-block bootstrap intervals favour CElo over independently tuned global-clock Elo on Arena Text, Arena Vision, and BASIL, with no clear difference on TCEC (Table 7). The revised framing emphasises our primary contribution: establishing what the unprojected local update converges to and quantifying uncertainty in population rating differences.

I thank the authors for the substantive revisions. The added tuned comparisons resolve my primary experimental concerns (Q1) and the uncertainty results strengthen the theoretical contribution (Q2, addressed partially). The remaining limitations (W2 / W4) are appropriately acknowledged. I thus keep my rating.

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

The paper proposes a convergent Elo method that replaces the Elo’s fixed learning rate with a diminishing gain based on each participant’s own comparison count. Under a fixed population, stationary conditional outcome means, and fixed i.i.d. matchmaking, the paper proves almost-sure convergence of the entire rating vector without projection or recentring. The limiting relative ratings recover Bradley–Terry strengths under realizability and otherwise minimize a matchmaking-weighted KL discrepancy. The paper validates its theory through stationary simulations calibrated from Arena data, controlled local-versus-global clock experiments, and chronological predictive evaluation on four datasets. Its method improves over fixed-gain Elo in observed binary cross-entropy on three of those.

Critical strengths

The main strength in the theory is that the convergence guarantee preserves the simplicity of the actual online algorithm. The method updates only the two participants involved in a comparison but the analysis establishes convergence without projection or recentring.

The main strength in the experiments is that they distinguish the benefit of diminishing gains from the benefit of local clocks. The controlled ablation shows similar performance under homogeneous participation but a growing advantage for local clocks as participation becomes more uneven.

Critical weaknesses

My main concern is that the global-clock baseline is not independently tuned: it inherits the paper's method's Arena-calibrated initial gain and offset. Tuning both methods independently with the same validation budget would clarify how much of the reported gap remains.

Questions for authors

Can you repeat the local-versus-global experiment with each method’s initial gain, clock offset, and decay exponent independently tuned using the same validation budget, and report whether your method's advantage persists under heterogeneous participation?

2 comments

Thank you for the review and for highlighting the weakness in our global clock experiment which we have now addressed as described below.

Independently tuned local-vs-global ablation. We reran the ablation as suggested: in each participation regime, we independently tuned the initial gain, clock offset, and decay exponent for each method, using the same search space and 99 validation trials per method. We then evaluated both schedules on 32 held-out paired streams (revised Fig. 2 and Appendix E.4, Tables 1–2).

Independent tuning narrows the gap seen in the original ablation, but the local-clock advantage persists. Under homogeneous participation (πmax⁡/πmin⁡=1.0\pi_{\max}/\pi_{\min}=1.0), the two methods achieve nearly identical mean centred target error after 10710^7 comparisons (0.02853 vs. 0.02854). Across all four heterogeneous regimes, however, CElo reduces mean final error by 6.3–39.9%, with paired 95% bootstrap intervals excluding zero in every regime. At the strongest imbalance (πmax⁡/πmin⁡=91.0\pi_{\max}/\pi_{\min}=91.0), CElo lowers final error from 0.0939 to 0.0564 (39.9% reduction, winning 32/32 paired streams) and reduces mean qq-weighted population excess log-loss by 90.5% (Fig. 6(b)).

Additional experimental and theoretical updates. We also strengthened the stationary estimation experiment (Fig. 1) by tuning each configuration independently on shared validation streams and adding time-averaged Elo and time-averaged CElo. All five unaveraged CElo configurations finish with lower median target error than both fixed-gain and time-averaged Elo, and time-averaged CElo achieves the lowest terminal median error. In the expanded practical chronological evaluation, paired 95% moving-block bootstrap intervals favour CElo over independently tuned global-clock Elo on Arena Text, Arena Vision, and BASIL, with no clear difference on TCEC (Table 7). Finally, building on the locality highlighted as a strength in the review, the new Theorem 3 derives asymptotic confidence intervals for rating differences that require only the two participants’ current ratings and gains under Bernoulli outcomes with Bradley–Terry realisability and 1/2<α<11/2 < \alpha < 1.

Thank you for the additional experiments. They address my baseline-tuning concern, although the advantage is substantially smaller than originally reported. I will keep my current score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.