acceptodds
Under review as a conference paper at ICLR 2027

Fast Maximum-Likelihood Rankings from Pairwise Preferences

Abstract

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.

Primary area:
optimization
Keywords:
Combinatorial Optimization, Integer Programming, Preference Aggregation, Linear Ordering Problem, LLM-as-a-Judge

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_sdvMOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

This paper considers the problem of finding a maximum likelihood ranking given observed probabilities of preferring a candidate a to b for pairs of candidates. This problem is closely related to the task of Kemeny rank aggregation and the (weighted) feedback arc set problem; and the solution can be applied to solve such problems. The authors propose an exact formulation using the idea of chordless cycles to reduce the number of constraints compared to classical formulations (which have one constraint for every cycle), or formulations designed for complete inputs. The authors implement their formulation with standard solvers and study its performance on several previous works that study optimizing given pairwise comparisons.

Critical strengths

In applications where the goal is to find a maximum likelihood ranking, or aggregate ranking, and so on, it is ideal to find one that indeed is optimal for use in downstream tasks, or to make decisions. This minimizes future errors that can result, and gives a much more defensible ranking when making decisions. This paper offers a method to improve the scalability of exact solving, and allows more instances of such problems in practice to be solved exactly, instead of depending on approximations or heuristics.

Critical weaknesses

It is not clear if the results obtained generalize to have further impact beyond the observed results on the sparse datasets. In the Kemeny rank aggregation task, full rankings and top-lists as input give a complete graph of pairwise comparisons, and partial rankings as input are likely to have a comparison on most, if not all pairs. The paper suggests PFAS performs better than LO in such complete instances slightly – it would be interesting to know why, given the formulations are equivalent in theory. Therefore, it seems the results are more limited to ML applications where there are indeed sparse comparisons between candidates.

Theoretical contributions on improving the exact formulation are modest and mostly from the chordless cycles formulation; section 5 is relatively standard in optimization, there are no deeper analysis in whether effective heuristics or instance reduction steps can be applied on top to improve performance.

Unlike previous referenced work like approximation algorithms, SCO, Lehmer codes approach, which seem to be designed to be able to scale to problems with very large number of candidates (e.g. 10k-1million, or even larger), the exact solution is unlikely to do so, even though it is indeed much faster than previous formulations on sparse instances.

Therefore, while this has application to practitioners with some previous work applying this maximum likelihood ranking to actively rank candidates in practice, it seems overall too limited in impact and novelty.

Questions for authors
  1. Is there any understanding for the observed improvement over LO in almost-complete, or complete instances?

  2. If given say a good feasible solution like an approximation algorithm output as a starting, does it affect how much of a speedup PFAS gives over the original FAS/LO models, given these are branch-and-bound based?

3 comments

We thank the reviewer for the detailed and constructive feedback.

W1/Q1: Why is XRank faster than LO on complete instances? (Clarification of contributions)

Thank you for raising this, our new PFAS formulation is indeed equivalent to LO on complete instances. To explain the speedup, we must separate our two contributions: the new PFAS formulation (Section 3 & 4) and our improved algorithm to solve it (Section 5 & Appendix C).

  1. New Formulation. Figure 9 isolates the effect of the formulation by running the identical XRank algorithm with each one. While LO is 158× slower than PFAS on sparse instances, it performs the same on fully complete instances (within 5%), confirming the equivalence. The slight speedup reported in Table 6 for p∈[0.9,1]p\in[0.9,1] comes from the non-complete instances in this range. On the other end, FAS is fastest on sparse instances, but still 1.6× slower than PFAS. This favorable mix between FAS and LO is the most important theoretical contribution of this work. The classical FAS and LO formulations have been the standard in literature since 1985, and for the first time we propose a new formulation that combines their most favorable properties, dominating both in all regimes.

  2. Speedup from the improved algorithm to solve the formulation. Even though the PFAS and LO formulations are equivalent on fully dense instances, another contribution of XRank is a sophisticated separation and cut management algorithm, solving the same LO formulation up to 5.1x faster than the original algorithm of Grötschel et al.

The gains are therefore not limited to sparse instances. XRank is 5.1× faster than the original LO method on fully complete LOLIB/FASLIB instances, and 4.9× faster on nearly complete PrefLib voting profiles (Table 4).

W2/Q2: Analysis of heuristics and instance reductions to improve performance.

This is a very good idea, and we added the following analysis to the paper. XRank indeed uses heuristics like local search (Martí & Reinelt 2011) and LP rounding to find good solutions. We ablate their effect, and simulate what happens when each formulation is given a very good start solution (here, the optimal one):

SettingPFASFASLO
All heuristics off1.10×1.15×1.36×
XRank default (Local search and LP rounding)1.00×1.00×1.00×
Optimal ranking as start solution0.96×0.95×0.92×

Relative runtime (shifted geometric mean, 1s shift); 224 LOLIB/FASLIB instances.

Surprisingly, even an optimal start saves only 4-8%, because runtime is dominated by proving optimality. The speedup of PFAS over FAS and LO therefore barely changes with a good start solution.

Decomposition into strongly connected components speeds up sparse instances by 1.28× (they often split into many subproblems) but dense ones by only 1.08× (usually one component).

W3: Scaling to problems with very large number of candidates.

We fully agree that beyond 10k candidates an exact solver is not the right tool, and heuristics remain necessary. Luckily, most of the ML applications we target have at most a few hundred items. With a short time limit, however, XRank can also be used as an LP-guided heuristic on large instances. We ran it with a 2s time limit on all public instances from the suggested SCO and Lehmer papers:

InstancesXRank: proved optimal in 2sXRank: optimality gapSCO/Lehmer: optimality gap
SCO paper, 2–500 items98.5%<0.001%1.83% (SCO)
SCO paper, 501–2,000 items19.0%0.10%9.09% (SCO)
SCO paper, 2,001–5,904 items0%0.26%11.5% (SCO)
Lehmer paper, 10–100 items100%0%3.37% (Lehmer)

Gap relative to the best known solution. One Diplomacy instance from the SCO paper is omitted, since it is not public.

Although this is not the originally intended use case of XRank, it outperforms both heuristics in every size group: even on the largest instances, with up to 5,904 items, XRank stays within 0.3% of the optimum after 2s, while the heuristics are 2–12% away. In addition, XRank returns a lower bound, so the user knows how far the ranking can be from optimal.

Impact and novelty. PFAS is the first formulation to outperform both 40-year-old standards, FAS and LO, in every regime. Combined with our algorithmic improvements, XRank makes optimal rankings cheap enough to compute routinely in most ML applications. This matters in practice: we show that the heuristics in published ML pipelines regularly select winners that no optimal ranking places first. To facilitate optimal rankings in practice, we packaged XRank as a Python library (pip install xrank), with prebuilt wheels for Linux, macOS and Windows. It will be released on PyPI upon publication, since releasing it now could violate the double-blind rule.

We thank the reviewer again and would appreciate a reconsideration of the score in light of these results.

Thanks for the detailed comments, and the additional experiments studying the comparison between the implementations. I have read through them, and also the other reviews.

Overall, the other favorable reviews suggest this is indeed more relevant in practice for ML pipelines than I previously thought.

I have re-evaluated my score.

However, maybe one suggestion I would like to make (related as well to a comment from reviewer hMNN) that some presentation could be improved. While in practice the method is fast, it does not guarantee problem instances are tractable in practice, and therefore should be considered alongside previously proposed approximation/heuristic methods for when datasets scale significantly. Perhaps this should be mentioned as in some sense to me, the current exposition seems slightly to suggest that those methods are superseded by this work.

Thank you very much for your thorough review and for carefully considering our response and the other reviews! We fully agree with your suggestion. While on practical instances XRank is usually fast, there can be settings where exact optimization is intractable and heuristics will have to be used, so XRank complements rather than supersedes these methods. We now state this explicitly in the paper.

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

This submission studies finding a ranking of nn elements given pairwise observation of preference probabilities among the elements.

The core idea is to formulate an optimization problem which contains as few constraints as possible. The constraints role is to avoid that the rankings in the solution set contains cycles. The idea to write just few constraints is to notice that for guaranteeing that a ranking xx is feasible it is enough to only impose that ℓC(x)\ell_C(x) is larger or equal to 11 for all cycles CC which do not admit any chords. This excludes a large number of cycles and therefore makes the optimization problem to be solved much less complex.

Theorem 1 shows that despite the reduction on the constraints number the solution is still exact. moreover, Theorem 2 shows that the number of constraints can be reduced further in general without loosing optimality of the solution.

As a strong proof of evidence of the practicality of the approach, the authors show that in 99.93% of the considered instances their algorithm find the optimal ranking according to eq. 4 within 5 minutes runtime.

Critical strengths

The method is elegant and well explained.

The results seems impressive.

Critical weaknesses

Limitation 1: I found the abstract misleading. To explain why, I start by quoting the passage I found the most misleading: Finding the exact maximum-likelihood ranking is NP-hard, so pipelines typically settle for heuristics, compromising quality. We introduce XRank, a fast exact solver

Reading that a problem is NP hard but you can solve it exactly in a fast way sounds misleading because fast seems to suggest polynomial time for every input. I think the authors should really be more explicit by what the mean by fast and explain that the worst case running time remains intractable so that there is contradiction with NP hardness.

Notice that I am not saying there is an error, this is just a presentation issue in term "fast". Albeit, it is an important one to address.

Limitation 2: If I understand correctly you need to observe the probability that ii is better than jj denoted as pijp_{ij}. However, what if only samples from Bernoulli(pij)\mathrm{Bernoulli}(p_{ij}) are observed? I think this is important to address.

Questions for authors

Q1 Can you explain on which particular instances XRank is inefficient in the input size? It would be interesting to know for which graph structures the method is not efficient.

Q2 Why in Figure 4.1 do the numbers of PFAS constraints increase with pp? In contrast, why does the number of constraints in FAS decrease?

2 comments

We thank the reviewer for the careful review and positive assessment. Following the suggestions, we added new insights to the paper, strengthening the story.

L1: "Fast" vs. NP-hardness in the abstract.

We agree that this is confusing. NP-hardness means that likely no method can be efficient on every input, and XRank is no exception (its worst-case running time is exponential). By "fast" we meant that XRank, in contrast to prior methods, solves most practically relevant instances in reasonable time. Indeed, due to the NP-hard nature of the problem, there can even be small instances that are intractible to solve. Following your suggestion, we added the qualifier 'on most practical instances from the ML literature' to the abstract, and include the following analysis in the paper:

Q1: On what kind of instances is XRank inefficient?

This is an excellent question, and it prompted a new experiment in the paper. A common observation in combinatorial optimization is that random instances are harder than real-world instances; in our paper, too, the random LOLIB classes are the slowest family (Table 4). To investigate, we took 400 real-world ML instances, and created a random "twin" instance for each: the same #items and density, but every preference probability drawn uniformly at random.

ItemsReal-world: median timeReal-world: intransitivityRandom twin: median timeRandom twin: intransitivity
20–990.03 s0.6%184s30%
100–2990.05 s0.4%>300 s38%
300–1,0003.7 s2.0%>300 s40%

XRank on one core, 5-minute time limit. Intransitivity: the share of comparisons that even the best possible ranking must contradict (0% = fully consistent, 50% = maximally inconsistent).

Indeed the random twins are much harder than the real-world instances. This could be due to two reasons: random instances (1) lack the structure of real data, or (2) are far less transitive, i.e., contain many more conflicting cycles. To separate the two, we repeated the experiment on random instances whose transitivity matches their real-world counterparts. Interestingly, these are about as easy as the real-world instances. Hence, intransitivity seems to be a main driver of difficulty. Real ranking data is usually nearly transitive (because voters tend to at least somewhat agree), so this is the reason XRank is fast on most practical instances. We added this analysis to Section 6.

L2: What if only samples from Bernoulli(pij)\mathrm{Bernoulli}(p_{ij}) are observed?

Thank you very much for raising this, it is indeed common in practice that judges only output a binary preference. XRank works seamlessly in this setting, and we added two new interpretations to Section 2.1:

  1. Maximum likelihood under noisy sorting. Assume a true order, and that every outcome agrees with it independently with probability 1−q>1/21-q > 1/2 (Braverman & Mossel, 2008; Condorcet's model in Young, 1988). For a candidate ranking π\pi, let D(π)D(\pi) be the number of the mm observed outcomes it contradicts. By independence, the likelihood is

    P(outcomes∣π)=(1−q)m−D(π) qD(π)=(1−q)m(q1−q)D(π),P(\text{outcomes} \mid \pi) = (1-q)^{m-D(\pi)}\, q^{D(\pi)} = (1-q)^m \left(\frac{q}{1-q}\right)^{D(\pi)},

    which decreases in D(π)D(\pi). Thus, the maximum-likelihood ranking is the one contradicting the fewest outcomes, which is exactly what XRank computes.

  2. Empirical risk minimization. For a fixed ranking π\pi, the fraction of observed outcomes that π\pi contradicts is an unbiased estimate of the probability that π\pi contradicts a new comparison from the same process. XRank minimizes this empirical risk exactly.

Q2: Why in Figure 4.1 do the numbers of FAS constraints increase with pp, while the PFAS counts decrease?

  • FAS has a constraint for every directed cycle. More comparisons can only create more cycles.
  • PFAS has a constraint only for chordless cycles, since a cycle with a chord is implied by two shorter ones (Eq. 5). Denser graphs have more cycles (factor pkp^k), but each long cycle is also much more likely to have a chord (factor (1−p)k(k−3)/2(1-p)^{k(k-3)/2}). For long cycles, the second effect dominates, so the number of chordless cycles decreases with density. On a complete graph (p=1p = 1), only the O(n3)O(n^3) 3-cycles remain.

This question also made us realize that Figure 4.1 is somewhat hard to read, and we will replace it with a clearer version.

To facilitate optimal rankings in practice, we packaged XRank as a Python library with a NumPy interface (pip install xrank), with prebuilt wheels for Linux, macOS and Windows. It will be released on PyPI upon publication, since releasing it now could violate the double-blind rule.

We thank the reviewer again for the helpful suggestions, which made the paper both clearer and more useful to practitioners, and would really appreciate the reviewer's reconsideration of the score.

Dear authors,

Thank you for your response and for the revision along the directions I've suggested.

I keep my positive score.

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

ML pipelines frequently use rankings computed from the aggregation of votes from multiple users. Because this aggregation is NP-hard, practitioners use heuristics that can deviate from the true answer. The authors therefore introduce XRank, which uses integer programming and enforces a transitive total order. XRank solves the exact maximum-likelihood ranking. They find that XRank finds a provably optimal ranking in 99.93% of tested instances. They benchmark XRank across 9 other existing publications and find that it improves in performance relative to other exact methods, while maintaining comparable runtime performance to heuristics while exceeding them in accuracy.

Critical strengths
  • The key narrative point of the paper is that XRank provides near-heuristic runtime without the accuracy costs, and the math and experimental results all show this very clearly. I am convinced of this key point. The evaluations and baselines all seem reasonable and fair to me.
Critical weaknesses

No major weaknesses.

  • (Minor) Fig 6 and Fig 4a were somewhat hard to read
Questions for authors
  • In your experiments, does exact optimization usually identify a clear winner, or can equally optimal rankings still lead to different model selections?
3 comments

We are grateful for the reviewer's positive assessment and suggestions for improving the presentation. We fully agree that Figure 4a and 6 are hard to read, and will replace them with clearer versions.

Q1: Does exact optimization identify a clear winner? Mostly yes. For all 48,165 ML instances, we tested whether more than one model can be first in an optimal ranking. On 79.8% of the instances, the optimal winner is unique. In most of the remaining cases, the tied models are not connected by any chain of comparisons, so no aggregation method could separate them. Indeed, on instances where every pair has been compared, almost all (95.7%) have a unique winner.

This shows that the heuristic errors are even more consequential. Since in the majority of cases, there is indeed a clear optimal winner, it is even more problematic to crown the wrong model. We added this detail to the paper, strengthening the story.

We thank the reviewer again for the helpful suggestions, and are happy to discuss further during the discussion period.

Reviewer_NgNuOpenReview ↗

Response to authors

I thank the authors for their response. I am satisfied with the uniqueness analysis.

I also agree with reviewer sdvM that "While in practice the method is fast, it does not guarantee problem instances are tractable in practice, and therefore should be considered alongside previously proposed approximation/heuristic methods for when datasets scale significantly.". This is a key note.

I will maintain my positive score.

Thank you very much for your thorough review and carefully considering our response! We fully agree with the suggestion. While on practical instances XRank is usually fast, there can be settings where exact optimization is intractable and heuristics will have to be used, so XRank complements rather than supersedes these methods. We now state this explicitly in the paper.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.