Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity

Tao Jin, Yue Wu, Quanquan Gu, Farzad FarnoudICML 2025 · OpenReview

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:

  1. Heterogeneity: Not all oracles are created equal. One person might be an expert at judging coding tasks, while another is better at creative writing.
  2. 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 Compare and Try-Compare subroutines 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

Sample complexity comparison of different algorithms
  • 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.
Empirical sample complexity of RMO-WST vs Probe-Max across different numbers of oracles (M)

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

Abstract

We study the problem of efficiently aggregating the preferences of items from multiple information sources (oracles) and infer the ranking under both the weak stochastic transitivity (WST) and the strong stochastic transitivity (SST) conditions. When the underlying preference model satisfies the WST condition, we propose an algorithm named RMO-WST, which has a bi-level design: at the higher level, it actively allocates comparison budgets to all undetermined pairs until the full ranking is recovered; at the lower level, it attempts to compare the pair of items and selects the more accurate oracles simultaneously. We prove that the sample complexity of RMO-WST is $ \tilde O( N\sum_{i=2}^{N}H_{\sigma^{-1}(i),{\sigma^{-1}(i-1)}} )$, where $N$ is the number of items to rank, $H$ is a problem-dependent hardness factor, and $\sigma^{-1}(i)$ represents the $i$-th best item. We also provide a tight lower bound that matches the upper bound of approximate ranking under the WST condition, answering a previously open problem. In addition, when the SST condition is satisfied, we propose an algorithm named RMO-SST, which can achieve an $\tilde{O}(\sum_{i=1}^{N} H_i \log(N))$ sample complexity. This outperforms the best-known sample complexity by a factor of $\log(N)$. The theoretical advantages of our algorithms are verified by empirical experiments in a simulated environment.
BibTeX
@inproceedings{jin2025ranking,
  author = {Tao Jin and Yue Wu and Quanquan Gu and Farzad Farnoud},
  title = {{Ranking with Multiple Oracles: From Weak to Strong Stochastic Transitivity}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=d3PjjtGc07},
}
Figure