TL;DR
This paper introduces a new framework for ranking items (like Large Language Models) using feedback from multiple noisy sources, such as different human annotators or evaluation tasks. By intelligently identifying and prioritizing the most accurate sources for specific comparisons, the authors achieve optimal sample complexity under both Weak and Strong Stochastic Transitivity, even improving the state-of-the-art for the latter by a logarithmic factor.
What Problem Does This Paper Address?
Ranking is a fundamental task in machine learning, powering everything from recommender systems to LLM leaderboards. However, real-world ranking often relies on "oracles"—human annotators or automated benchmarks—that are inherently noisy.
The challenge is twofold:
- Heterogeneity: Not all oracles are created equal. One person might be an expert at judging coding tasks, while another is better at creative writing.
- Transitivity Assumptions: Most ranking algorithms assume Strong Stochastic Transitivity (SST), which posits that if item A is much better than B, and B is much better than C, then A is vastly easier to distinguish from C than from B. In reality, many scenarios only satisfy Weak Stochastic Transitivity (WST), where we only know that if $A \succ B$, then the probability of A beating B is $> 0.5$, without a strict relationship between the "gaps" of different pairs.
The authors aim to find the true ranking using the minimum number of queries possible by leveraging the best available oracles for every pair.
Methods
The authors propose a bi-level algorithmic design called Rank-with-Multiple-Oracles (RMO).
- High-Level Strategy: The algorithm manages the overall ranking process. For WST, it uses a "Probe-Max" approach to iteratively find the best remaining item. For SST, it uses an "Iterative-Insertion" approach.
- Low-Level Comparison: This is the core innovation. The
CompareandTry-Comparesubroutines handle the multiple oracles. Instead of querying oracles at random, the algorithm adaptively eliminates "noisy" oracles (those with high variance or low accuracy for a specific pair) and focuses its budget on the "experts." - Consistency Assumption: The methods rely on the assumption that while oracles have different noise levels, they all agree on the underlying "ground truth" direction of the ranking.
Experimental Setup
The paper evaluates the algorithms using simulated environments (synthetic data) to rigorously test theoretical bounds.
- Setup: They generated comparison matrices for $N$ items (ranging from 2 to 64) and $M$ oracles (2, 4, or 6).
- Oracle Quality: To simulate real-world expertise, they designated one oracle as "highly accurate" (win probabilities between 0.85 and 0.95) and the remaining $M-1$ oracles as "noisy" (win probabilities between 0.55 and 0.65).
- Goal: The simulation tests if the algorithm can successfully "find the expert" among the noisy crowd to recover the ranking efficiently.
Key Insights and Ideas
- The "Expert" Advantage: You don't need to know who the expert is beforehand. By observing the consistency of responses, the algorithm can statistically prune away low-accuracy oracles, effectively reducing a multi-oracle problem to a single-oracle problem with the best available gap.
- Solving the WST Open Problem: Ranking under WST is significantly harder than SST because you can't rely on the "distance" between items to simplify comparisons. This paper provides a tight lower bound for WST ranking, answering a previously open theoretical question.
- Bi-level Modularity: By separating the "which pair to compare" logic from the "how to compare this pair" logic, the authors created a flexible framework that can be optimized for different transitivity conditions.
Key Results
- WST Optimality: The RMO-WST algorithm achieves a sample complexity of $\tilde{O}(N \sum H_{i, i-1})$, which matches the newly proven lower bound.
- SST Improvement: For the SST condition, RMO-SST achieves a complexity of $\tilde{O}(\sum H_i \log N)$. This is a $\log N$ factor improvement over the previous best-known result (Saad et al., 2023).
- Empirical Gains: In simulations, RMO-WST consistently outperformed the baseline (Probe-Max). Notably, as the number of noisy oracles ($M$) increased, the performance gap widened, demonstrating that the algorithm becomes relatively more efficient as the environment becomes noisier.
Limitations and Future Work
- The Monotonicity Assumption: The authors assume all oracles agree on the same underlying ranking. In subjective fields (like "helpfulness" vs. "honesty" in LLMs), different oracles might actually have different ground truths, which this model does not yet account for.
- Instance-Dependent Lower Bounds: While the authors improved the upper bound for SST, it remains an open question whether a matching instance-dependent lower bound exists for the multi-oracle SST case.
- Unified Algorithms: A promising future direction is developing a "best-of-both-worlds" algorithm that automatically adapts to either WST or SST conditions without the user needing to specify the transitivity type in advance.
Summary updated