Close and Sort: Exact Maximum-Likelihood Aggregation of Cyclic Rank-Two Preferences

Kehan Liu, Zhaoyun Chen, Xianquan YanarXiv 2026 · arXiv

Finding a single, consensus ranking from a set of pairwise comparisons—like "A is better than B"—is a fundamental problem in recommendation systems, voting, and now, Large Language Model (LLM) evaluation. Mathematically, this is known as the weighted Kemeny problem, and it is notoriously NP-hard.

A new paper from researchers at the National University of Singapore, "Close and Sort," reveals a surprising "trapdoor" to this complexity. By assuming the underlying preference structure has a specific algebraic property (rank-two), they transform a difficult combinatorial optimization problem into a simple geometric one: sorting vectors by their angle.

TL;DR

The authors introduce CloseSort, an $O(n \log n)$ algorithm that exactly solves the maximum-likelihood rank aggregation problem for rank-two preference matrices. By mapping pairwise log-odds to the area of a closed polygon, they provide a solution that is thousands of times faster than exact dynamic programming and significantly more accurate than common heuristics for cyclic LLM evaluations.

What Problem Does This Paper Address?

When we aggregate preferences, we usually want the "Maximum Likelihood" (ML) list—the one most likely to have generated the observed pairwise data. However, finding this list is computationally expensive.

Most practical systems use heuristics like Borda count (ranking by average win rate) or Copeland’s rule (ranking by number of pairwise wins). While fast, these methods often fail to capture the nuances of "weighted" preferences (how much better A is than B) and struggle with cycles (A > B, B > C, but C > A). Cycles are surprisingly common in human and LLM judgments, yet traditional transitive models like Bradley-Terry cannot represent them.

The authors identify that while the general problem is hard, many real-world preference datasets are "low-rank." Specifically, they focus on rank-two skew-symmetric matrices, which are expressive enough to include cycles but structured enough to potentially allow for exact, efficient solutions.

Methods

The core innovation of the paper is a mapping from linear algebra to plane geometry.

  1. The Rank-Two Assumption: The authors assume the log-odds matrix $W$ (where $W_{ij} = \log(p_{ij}/p_{ji})$) has rank two. This means every item $i$ can be represented by a 2D vector $h_i$, such that the preference strength between $i$ and $j$ is the determinant of their vectors: $W_{ij} = \det(h_i, h_j)$.
  2. The Polygon Area Identity: They prove that the maximum-likelihood objective is equivalent to maximizing the signed area of a polygon whose edges are the vectors $h_i$.
  3. The CloseSort Algorithm:
  4. Calculate a "closing vector" $h_0 = -\sum h_i$ to ensure the polygon closes.
  5. Polar Sort: Sort all vectors (the $n$ items plus the closing vector) by their angular position in the 2D plane.
  6. The Cut: The optimal linear ranking is simply the sequence of items found by starting the angular cycle immediately after the closing vector $h_0$.
Figure 1: The augmented edge vectors sum to zero. (a) An arbitrary order traces a self-intersecting polygon with small signed area. (b) Angular sorting produces a weakly con- vex, maximum-area polygon; removing the closing edge ℎ0 (dashed) yields the item ranking. The objective equals twice the signed area.

Datasets

The authors validated their approach using:

  • Synthetic Simulations: 5,120 profiles generated using a determinant-logit model to test recovery under noise.
  • Arena-Hard v0.1: A benchmark for LLM evaluation. They used 3,600 profiles involving 63 different LLM systems and 10 judges. This dataset is particularly interesting because it contains many "empirical-cyclic" profiles where judges' preferences form directed triangles.

Key Insights and Ideas

  • Geometry as a Solver: The realization that the Kemeny objective for rank-two matrices is exactly twice the signed area of a polygon is the "aha" moment. This turns an NP-hard search over $n!$ permutations into a simple $O(n \log n)$ sort.
  • Cycles are Native: Unlike the Bradley-Terry model (which is rank-one and strictly transitive), the rank-two model naturally accommodates and optimizes for cyclic preferences.
  • Stability Certificates: The geometry allows the authors to define a value $\delta$ (the smallest determinant between consecutive edges). If the noise in the data is less than $\delta$, the CloseSort ranking is guaranteed to be the unique global optimum.
  • Denoising via Projection: Even if the real data isn't perfectly rank-two, projecting it onto the nearest rank-two matrix acts as a powerful regularizer, filtering out sampling noise better than "plug-in" ML estimators.

Key Results

  • Massive Speedup: For a ranking of 18 items, CloseSort is 8,407 times faster than exact dynamic programming (Held-Karp).
  • Superior Accuracy: On cyclic LLM-judge profiles, CloseSort reduced normalized regret by 44% relative to the Borda count.
  • Energy Capture: In the Arena-Hard dataset, the leading rank-two component captured 89.2% of the log-odds energy, suggesting that the rank-two assumption is a very good fit for real-world LLM evaluation data.
  • Robustness: As shown in Figure 2, the algorithm remains optimal even under significant random residuals, only failing when targeted perturbations exceed the theoretical stability threshold $\delta$.
Figure 2: Fraction of trials in which the rank-two CloseSort order remains globally optimal under random or targeted residuals. The targeted construction attains the theorem’s threshold.

Limitations and Future Work

  • Complete Graphs Only: The current geometric reduction requires a complete set of pairwise comparisons. If many pairs haven't been compared (sparse data), the polygon area identity no longer holds directly.
  • Rank-Two Constraint: While rank-two captures cycles, it is still a simplification. The authors note that characterizing the trade-off between variance reduction and approximation error in higher-rank settings remains an open question.
  • Future Directions: Extending this geometric approach to sparse observation graphs is a primary goal for future research.

Summary updated

Abstract

Pairwise probabilities arise in rank aggregation, recommendation, and human or LLM evaluation, yet converting them into a maximum-likelihood list is a weighted Kemeny problem and is NP-hard in general. Known exact algorithms for rank-two tournaments use only comparison signs and do not optimize this likelihood. We show that the weighted problem is exactly solvable when the skew-symmetric log-odds matrix $W_{ij}=\log(p_{ij}/p_{ji})$ has rank two, including when the induced preferences contain cycles. Writing $W_{ij}=\det(h_i,h_j)$ and adding the closing vector $h_0=-\sum_i h_i$ turns the objective into twice the signed area of a closed polygon. This geometry yields CloseSort, which polar-sorts the $n+1$ edge vectors, cuts after $h_0$, and returns a global maximum-likelihood order in $O(n\log n)$ time from the factors. The same geometry identifies the runner-up and gives a stability certificate beyond exact rank two. When the smallest determinant $δ$ of two consecutive edges in the closed angular cycle is positive, it is exactly the best-to-runner-up log-likelihood gap. For $W=W_0+E$, the CloseSort order of $W_0$ has regret at most $\sum_{i<j}|E_{ij}|$ on $W$ and remains optimal whenever this sum is below $δ$, a worst-case tight threshold. In 5,120 determinant-logit simulations, increasing the observations per pair from 4 to 64 raises the fraction on which rank-two projection outperforms the empirical plug-in optimum from 68.6% to 85.7%. On 3,600 Arena-Hard LLM-judge profiles drawn from 63 systems and ten judges, the leading rank-two component captures 89.2% of the log-odds energy. On profiles containing a directed majority triangle, CloseSort reduces normalized regret by 44% relative to Borda and improves the mean normalized objective over each of eight baselines. With factors supplied, it is 8,407 times faster than exact dynamic programming on 18-item rankings.
BibTeX
@misc{liu2026close,
  author = {Kehan Liu and Zhaoyun Chen and Xianquan Yan},
  title = {{Close and Sort: Exact Maximum-Likelihood Aggregation of Cyclic Rank-Two Preferences}},
  year = {2026},
  eprint = {2611.10538},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.10538},
}
Figure