Fast Maximum-Likelihood Rankings from Pairwise Preferences

Computing rankings from pairwise (probabilistic) comparisons is ubiquitous in machine-learning pipelines, for example when aggregating LLM-as-a-judge preferences or combining the rankings of multiple voters. Finding the exact maximum-likelihood ranking is NP-hard, so pipelines typically settle for heuristics, compromising quality. We introduce XRank, a fast exact solver that substantially outperforms existing exact methods and makes optimal rankings cheap enough to compute routinely. We revisit 9 publications spanning LLM evaluation, benchmark leaderboards and rank aggregation, covering 48,165 ranking instances. Simple aggregation rules such as Borda counts, win ratios and greedy cycle removal, used in five of these publications, incur 4.8 - 13.8% higher objective cost on average, and on 23 - 96% of instances select a winner that no optimal ranking places first. On a released SuperGLUE leaderboard snapshot, for instance, Borda aggregation crowns a model that provably cannot come first in any optimal ranking. XRank instead finds provably optimal rankings for 99.93% of these instances, typically within milliseconds on a single core, showing that in many settings there is no need for heuristics anymore. We release the XRank software package to facilitate optimal preference aggregation in practice.