Close and Sort: Exact Maximum-Likelihood Aggregation of Cyclic Rank-Two Preferences
Organizations: Department of Physics, National University of Singapore, Singapore · Department of Computer Science, National University of Singapore, Singapore
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 has rank two, including when the induced preferences contain cycles. Writing and adding the closing vector turns the objective into twice the signed area of a closed polygon. This geometry yields CloseSort, which polar-sorts the edge vectors, cuts after , and returns a global maximum-likelihood order in 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 , the CloseSort order of has regret at most on 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.
Figures & tables
| Method | Cycles | Exact MLE | Complexity |
|---|---|---|---|
| BT sort | |||
| Rank-two MFAST | |||
| CloseSort | |||
| General Kemeny (unrestricted) | NP-hard |
| 4 | 6 | 8 | 10 | 16 | 32 | |
|---|---|---|---|---|---|---|
| Suboptimal (%) | 14.7 | 22.9 | 28.6 | 35.5 | 46.0 | 63.6 |
| Mean population regret | ||||||
|---|---|---|---|---|---|---|
| (%) | CloseSort | Plug-in | Borda | Copeland | Win vs. plug-in (%) | |
| 4 | 47.6 | 11.509 | 13.993 | 20.812 | 21.003 | 68.6 |
| 16 | 68.1 | 3.021 | 5.847 | 17.506 | 18.467 | 84.7 |
| 64 | 87.7 | .748 | 1.891 | 15.121 | 16.476 | 85.7 |
| Baseline | All | Empirical | |
|---|---|---|---|
| Cyclic | Acyclic | ||
| Full-data baselines; evaluated on | |||
| Bradley–Terry | |||
| Borda | |||
| Copeland | |||
| Rank Centrality | |||
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
| Cohort | Ranks | Systems | Cyclic (%) |
|---|---|---|---|
| 1 | 1–7 | claude-3-5-sonnet-20240620; gpt-4o-2024-05-13; gpt-4-1106-preview; gpt-4-turbo-2024-04-09; mistral-large-2407; yi-large-preview; gpt-4-0125-preview | 29.50 |
| 2 | 8–14 | claude-3-opus-20240229; gpt-4o-mini-2024-07-18; athene-70b-0725; llama-3.1-405b-instruct-fp8; yi-large; glm-4-0116; claude-3-sonnet-20240229 | 32.50 |
| 3 | 15–21 | glm-4-0520; gemini-1.5-pro-api-0409-preview; nemotron-4-340b-instruct; gemma-2-27b-it; llama-3.1-405b-instruct-fp8-no-sys-prompt; gemini-1.5-pro-api-0514; llama-3.1-70b-instruct | 34.50 |
| 4 | 22–28 | gpt-4-0314; mixtral-8x22b-instruct-v0.1; deepseek-coder-v2; mistral-next; llama-3-70b-instruct; mistral-large-2402; qwen2-72b-instruct | 36.75 |
| 5 | 29–35 | gpt-4-0613; glm-4-air; qwen1.5-72b-chat; claude-3-haiku-20240307; claude-2.0; mistral-medium; claude-2.1 | 36.00 |
| 6 | 36–42 | command-r-plus; gpt-3.5-turbo-0125; gpt-3.5-turbo-1106; gemini-1.5-flash-api-0514; dbrx-instruct-preview; gpt-3.5-turbo-0613; phi-3-medium-4k-instruct | 40.25 |
Rank Aggregation
Rank aggregation combines ranked lists or pairwise preferences into a consensus ordering for tasks such as search, recommendation, and model evaluation.
See all 36 papers