Ranking many items from pairwise judgments is expensive. The items might be LLMs judged by a model or by people, cartoon captions, or images. Each judgment costs a human vote or an API call, and in practice judgments are requested in batches: a crowdsourcing wave, or a parallel sweep of an LLM judge. The number of batches is then the main source of wall-clock latency. Theory says you can find the best $k$ items with the optimal worst-case number of comparisons in only about $\log^* n$ batches, where $\log^* n$ is the number of times you must take a logarithm before $n$ drops below 1, so it is at most 5 for any realistic $n$. That result is from Learning with Limited Rounds of Adaptivity. The same paper leaves open whether an algorithm can adapt to the actual gaps between items, rather than only the worst-case gap at the $k$-th position, without needing about $\log n$ batches.
This note proposes a batch-selection rule borrowed from a corner of coding theory. When constructing polar codes, one does not need to test every synthetic channel. A known partial order among channels implies that only the "frontier" between reliable and unreliable channels has to be evaluated. That frontier is found with a chain decomposition computed by bipartite matching (Construction of Polar Codes With Sublinear Complexity). We apply the same idea to ranking. After each batch, the statistically certified "A beats B" relations form a partial order. Each next batch spends comparisons only on the uncertain frontier around the $k$-th position, and it arranges those comparisons along chains so that each outcome certifies as many further relations by transitivity as possible. The expected payoff is fewer total comparisons at a fixed, small number of batches, with anytime-valid error control.
Core Claim
We claim that batch selection guided by a chain decomposition of the certified partial order reaches a correct top-$k$ set with fewer comparisons, at a matched small number of rounds, than both worst-case elimination and uncertainty-priority sampling. The gain should grow as the gaps between items become more uneven, which is the regime real leaderboards live in.
A few terms first. A round is one batch of comparisons issued in parallel before any results are seen. A chain is a set of items that are totally ordered among themselves by certified relations. An antichain is a set of items with no certified relations among them. Dilworth's theorem says the size $w$ of the largest antichain equals the minimum number of chains needed to cover the set. We call $w$ the width of the uncertain region. It is computable in polynomial time by maximum bipartite matching, which is exactly the tool used for polar code construction.
The mechanism is as follows. Let $F_t$ be the set of items after round $t$ that are neither certified in the top-$k$ nor certified out of it, and let $w_t$ be the width of the certified order restricted to $F_t$. Round $t+1$ decomposes $F_t$ into $w_t$ chains. It then issues, in one batch, comparisons that place each chain's median items against the other chains' medians, in the manner of a parallel merge. Each comparison is repeated as often as the current estimated gap for that pair requires to reach the round's confidence level. Certification uses e-processes: running test statistics whose expectation stays at most 1 when the null hypothesis is true, so one may stop at any time without inflating error. We use them as SERPANT does (Anytime-Valid Inference for Online Ranking of Large Language Models).
The analysis target is a comparison bound of roughly this form:
$$Q \;\lesssim\; \sum_{t=1}^{R} \; \sum_{i \in F_{t-1}} \frac{\log(w_{t-1}/\delta)}{\Delta_i^2},$$
where $Q$ is the total number of comparisons, $R$ the number of rounds, $\Delta_i$ the gap between item $i$'s win probability and the $k$-th boundary, and $\delta$ the target error. The $\log w$ factor, in place of $\log n$, comes from merge-style insertion needing only logarithmically many comparisons in the number of chains. The hope is that $R$ tracks the number of distinct gap scales in the instance rather than $\log n$. This is a hypothesis to prove or refute. We do not claim it resolves the open problem.
What Carries Over, and What Does Not
The coding-theory source supplies method, not application. Construction of Polar Codes With Sublinear Complexity shows that a universal partial order among synthetic channels lets one evaluate only $O(N/\log^{3/2} N)$ of them, saving at least 80% of channel computations at $N \approx 10^3$. We reuse its logic of antichain frontiers found by matching. We change one essential thing: in their setting the order is deterministic and known offline, whereas ours is stochastic, learned online, and grows between rounds.
Earlier constructions such as Performance and Construction of Polar Codes on Symmetric Binary-Input Memoryless Channels evaluate every channel. They are the analogue of the "compare everything near the boundary" baselines below.
Two ranking works motivate the proposal and set the bar. Learning with Limited Rounds of Adaptivity gives AGGRESSIVE-ELIMINATION, which discards a growing fraction of candidates each round. It is worst-case optimal in $\Theta(\log^* n)$ rounds, with a matching lower bound. Because it is tuned to the single gap $\Delta_k$, it cannot exploit the fact that most items are far from the boundary. SERPANT (Anytime-Valid Inference for Online Ranking of Large Language Models) supplies our statistical layer, e-processes plus transitivity pruning. It uses transitivity passively, crediting implied relations after the fact, and it queries one pair at a time with no round budget. We choose queries in order to create transitive implications, and we operate under a fixed round budget.
Just Sort It! shows that sorting algorithms are good active learners because they naturally compare nearby items, and that comparison errors in Quicksort cause only local displacements. That result supports our choice of merge-style chain queries.
Two works constrain the design. Learning Correlated Reward Models and Nonparametric LLM Evaluation from Preference Data document preferences that break single-parameter models such as Bradley–Terry, the model in which each item has one latent score. We therefore certify relations nonparametrically from pairwise e-values and never fit Bradley–Terry for decisions. Transitivity itself can still fail, and we treat that as a measured risk rather than assume it away.
We deliberately drop the tempting three-way combination of polar-coding the broadcast of queries to distributed judges. A query is a pair index of about $2\log_2 n$ bits and an answer is one bit, while one judge call costs a human vote or an LLM inference. Bits are not the bottleneck in any benchmark we have. Direction 1 therefore enters as the source of the frontier-and-matching technique. Direction 2 enters as the round-versus-volume tradeoff we measure. In that tradeoff, "communication" means comparisons per round, in the spirit of Kozachinskiy's staged protocols (On Slepian-Wolf Theorem with Interaction). There a receiver signals after each small batch whether ambiguity remains, and the protocol stops early.
Research Program
The first component is the algorithm, Frontier Chain Batching. It maintains e-processes per queried pair and a certified relation graph closed under transitivity. After each round it computes the frontier and a minimum chain cover by bipartite matching, as in Mondelli et al. It then emits a merge-structured batch whose per-pair repetition counts are set from empirical gap estimates. The algorithm takes a round budget $R$ and splits the confidence budget across rounds. Selection cost is polynomial in $|F_t|$, which is small in practice. We will report selection wall time, because Just Sort It! found that computational cost decides which active learners can run at all at $n \approx 6{,}000$.
The second component is analysis. We will prove correctness at level $\delta$ under optional stopping, which should follow directly from the e-process construction. We will then attempt the comparison bound above for strongly stochastically transitive instances. We will also characterize when $w_t$ collapses quickly, for example when items cluster into well-separated tiers. We will state the results as upper bounds relative to the gap profile, and we will check them against the $\Omega(\log^* n)$ lower bound of Agarwal et al., which our method cannot beat in the worst case.
The third component is a robustness mode for intransitive preferences. A small random fraction of relations implied by transitivity is directly re-queried. If audits contradict an implied relation more often than the error budget allows, the algorithm falls back to direct certification for the affected chain.
Baselines
The naive reference is uniform random matchmaking in batches. Each round draws pairs uniformly at random, and the same e-process certification is applied to all outcomes, so the only difference is query choice. It sets the floor, and it is what Chatbot Arena compared against. There, Elo-similar matchmaking needed 4,400 votes versus 6,800 for random to reach score precision 0.2, a 54% reduction as reported. We expect to beat random by a wide margin. That comparison is a sanity check, not evidence for the proposal.
The strongest round-limited competitor is AGGRESSIVE-ELIMINATION from Learning with Limited Rounds of Adaptivity. It is the only method in the file with a proven optimal tradeoff between rounds and comparisons for top-$k$. No reported empirical result was found on Lacuna for AGGRESSIVE-ELIMINATION on any of our benchmarks, so we will implement it from the paper. We give it the same round budget $R$, the same error target $\delta$, and a tuning grid over its elimination schedule of the same size as ours.
The strongest practical sequential competitor is SERPANT, with tournament sampling and transitivity pruning. Its reported result is that it recovered 91% of the true partial order within 2,000 comparisons on Databricks-Dolly-15k with a GPT-4o-mini judge over 10 LLMs, with FWER below 0.1 (Anytime-Valid Inference for Online Ranking of Large Language Models). We run it two ways. Unconstrained, it is a lower bound on comparisons achievable with unlimited rounds. Batched, it takes the top-$B$ pairs by its priority score per round, with $B$ tuned. Batched Multisort from Just Sort It!, with each Quicksort pivot level forming one round, is also included, since sorting is naturally a parallel procedure.
Two ablations isolate the key ingredient. The first, the "frontier-only" ablation, keeps our frontier $F_t$ and our repetition counts but draws pairs within the frontier at random, or by SERPANT's priority score. The second replaces the minimum chain cover with an arbitrary chain cover.
Beating the field means the following. At matched $R \in \{3, 5, 8\}$ and matched empirical error at most $\delta = 0.1$, Frontier Chain Batching must reach certified top-$k$ with at least 25% fewer comparisons than the better of AGGRESSIVE-ELIMINATION and batched SERPANT, on at least two of the three real-preference simulators. It must also beat the frontier-only ablation by a margin outside seed variance.
Why not just…?
Why not just batch SERPANT's priority score and let transitivity pruning do the rest? This is the most serious threat. Restricting queries to near-boundary pairs may capture most of the gain, with chain structure adding little. The frontier-only ablation tests exactly this. If random or priority-chosen pairs within the same frontier match chain-structured pairs, the Dilworth machinery is decoration. In that case the contribution shrinks to "frontier restriction under a round budget," and we would report it as such.
Why not just use AGGRESSIVE-ELIMINATION, which is already provably optimal in rounds? It is optimal in the worst case, and our method cannot beat it there. On instances with uneven gaps, its schedule still pays for the hardest gap on every item it keeps. Its authors state that instance-adaptive algorithms currently need $\Omega(\log n)$ rounds. The experiment that settles whether that gap matters in practice is to plot comparisons against the spread of gaps, using synthetic instances that interpolate from uniform gaps to tiered gaps. If there is no advantage anywhere on that sweep, the proposal fails.
Why not just run parallel Quicksort or Multisort? Sorting spends comparisons ordering the whole list, including items far from the top-$k$ boundary. It also needs about $\log n$ pivot levels, and therefore rounds, for a full order. It is a strong heuristic on displacement error: Just Sort It! reports a 14–23% displacement reduction over random on GIFGIF. It provides no certified top-$k$ guarantee, however. We will compare on both displacement and certified top-$k$ so that sorting is judged on its home metric too.
Why not just polar-code the query broadcast, as the obvious three-way combination suggests? Because query and answer payloads are a few bits per judge call, coding them saves nothing measurable relative to the cost of the judgments themselves. We found no benchmark in which link capacity binds.
Proposed Experiments
We use four evaluation settings. The first is simulators built from real preference data: the Sushi dataset (100 items, 5,000 respondents, with naturally occurring intransitivity), GIFGIF (6,120 items, over 100,000 comparisons, simulated through a fitted nonparametric win-probability smoother) from Just Sort It!, and the public Chatbot Arena votes (over 50 models) (Chatbot Arena). The second is large-$n$ top-$k$ caption selection on yguooo/newyorker_caption_ranking. There, thousands of captions per contest with "unfunny/somewhat/funny" ratings give a realistic heavy-tailed gap profile (Humor in AI). The third is a live run on SERPANT's Dolly-15k setup, with GPT-4o-mini judging 10 open LLMs, where we directly compare comparisons-to-91%-partial-order against the reported 2,000. The fourth is synthetic tiered and uniform-gap instances for the gap-spread sweep.
Metrics are total comparisons to certified top-$k$ at fixed $R$; the full Pareto curve of rounds against comparisons; empirical FWER over at least 200 seeds per setting; selection compute time; and the frontier width trajectory $w_t$. The last is the quantity our analysis claims drives cost.
Three checks decide the question. The first is the frontier-only ablation described above. The second is whether our advantage over AGGRESSIVE-ELIMINATION grows with gap spread, as the bound predicts. The third, on Sushi, is whether audit-triggered fallbacks keep empirical error below $\delta$ when transitivity is violated. If the second check shows advantage only on tiered synthetic data and not on the Chatbot Arena or NYCC gap profiles, the method is a curiosity rather than a tool.
References
- Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons.
- Construction of polar codes with sublinear complexity
- Anytime-Valid Inference for Online Ranking of Large Language Models
- Performance and construction of polar codes on symmetric binary-input memoryless channels
- Just Sort It! A Simple and Effective Approach to Active Preference Learning
- Learning Correlated Reward Models: Statistical Barriers and Opportunities
- Nonparametric LLM Evaluation from Preference Data
- On Slepian-Wolf Theorem with Interaction
- Chatbot Arena: An Open Platform for Evaluating LLMs by Human Preference
- Humor in AI: Massive Scale Crowd-Sourced Preferences and Benchmarks for Cartoon Captioning