Ranking Items from Discrete Ratings: The Cost of Unknown User Thresholds

Oscar Villemaud, Suryanarayana Sankagiri, Matthias Grossglauser

TL;DR

Ranking items using coarse binary ratings (like thumbs up/down) requires a quadratic number of users ($\Omega(n^2)$), making it fundamentally harder than ranking via pairwise comparisons ($O(n \log n)$). This paper quantifies this "cost of discretization" due to unknown user thresholds and introduces an active learning algorithm, Threshold Binary Search, that matches this lower bound up to logarithmic factors.

What Problem Does This Paper Address?

Recommender systems, search engines, and peer-review platforms frequently ask users for discrete feedback (e.g., clicks, likes, or 1-5 star ratings) but aim to output a highly precise, fine-grained ranking of items.

While prior machine learning literature often treats discrete ratings as noisy versions of continuous utilities, this paper models discretization as a thresholding process. Every user is assumed to agree on the true ordering of items, but each possesses a different latent "internal bar" (threshold). A user rates an item positively only if the item's quality exceeds their personal threshold.

Because these thresholds are hidden and vary across a heterogeneous population, the platform faces a major challenge: it doesn't know which user has the right threshold to help distinguish between two closely ranked items. The authors set out to determine the fundamental query and sample complexity of recovering a fine-grained ranking under this realistic constraint.

Figure 1: The item scores and user thresholds are sampled iid, respectively with densities fX and fY .

Methods

The authors formalize the problem by modeling $n$ items with latent scores $X_i \in [0,1]$ drawn i.i.d. from a density $f_X$, and sequential users with latent thresholds $Y_u \in [0,1]$ drawn i.i.d. from a density $f_Y$. A rating is a noiseless binary indicator: $q(u,i) = 1$ if $X_i > Y_u$, and $0$ otherwise.

To evaluate ranking precision without requiring an impossible perfect ordering, they use the Maximum Spearman Footrule (MSF) distance. The MSF measures the worst-case rank displacement between the true ranking and any total ranking that is compatible with the learned "bins" of items.

The authors derive fundamental lower bounds for two regimes (linear and super-linear scaling of users to items). To demonstrate the tightness of these bounds, they propose an active learning algorithm called Threshold Binary Search (TBS). For each arriving user, TBS:

  1. SEARCH: Performs a binary search over existing item bins using single-item queries to locate where the user's threshold lies.
  2. ISOLATE: Pinpoints the exact bin containing the threshold.
  3. SPLIT: Prompts the user to rate all items within that specific bin, effectively splitting it into two more precise bins.

Datasets

The paper relies entirely on synthetic data to validate its theoretical claims. The authors run Monte-Carlo simulations (1000 trials per setting) in Python. Item scores and user thresholds are generated using various Beta distributions ($\text{Beta}(a_X, b_X)$ and $\text{Beta}(a_Y, b_Y)$) to simulate both matching and mismatched population characteristics.

Key Insights and Ideas

  • The Infinite Catch: Surprisingly, the expected number of users needed to achieve a perfect ranking is actually infinity. Because item scores are continuous random variables, the smallest gap between any two consecutive items follows a heavy-tailed distribution, making it incredibly rare for an unknown user threshold to land exactly in the tiniest gaps.
  • The Discretization Penalty: Moving from pairwise comparisons to binary ratings blows up the sample complexity from $O(n \log n)$ to $\Omega(n^2)$. This extra factor of $n$ is the exact mathematical cost of having to discover the users' latent thresholds.
  • The Mismatch Penalty: The complexity of ranking is heavily dictated by a quadratic divergence factor: $\mathbb{E}[(f_X(Y)/f_Y(Y))^2]$. If the distribution of item scores does not align well with the distribution of user thresholds (e.g., if items are clustered in a quality range where users lack discriminative thresholds), the ranking task becomes significantly harder.

Key Results

  • Linear User Regime: If the number of users $m$ scales linearly with the number of items $n$ ($m \sim rn$), the expected ranking error (MSF) per item remains bounded by a constant, scaling as $O(n)$.
  • Quadratic User Regime: To achieve a near-perfect ranking (where MSF approaches a constant), the platform requires a quadratic number of users: $m = \Omega(n^2)$. In this regime, the expected MSF scales as $O(n^2/m)$.
  • Algorithmic Tightness: The proposed TBS algorithm achieves an expected query complexity of $O(n \log m + m \log n)$. When $m \ge n$, the dominating term is $m \log n$, meaning it matches the fundamental lower bound up to a simple logarithmic factor.

Limitations and Future Work

  • Noiseless Ratings: The model assumes that user feedback is completely deterministic ($X_i > Y_u$). In practice, human ratings are noisy and inconsistent.
  • Universal Preference Agreement: The framework assumes all users agree on the objective quality ordering of items and only differ in their leniency (thresholds). It does not account for standard collaborative filtering challenges where users have fundamentally different tastes.
  • Binary Restriction: While the authors outline how their lower bounds generalize to $k$-level rating scales (reducing the user requirement by a factor of $k-1$), the active learning TBS algorithm is currently optimized only for binary feedback. Extending robust active search to multi-level, noisy ratings remains an open challenge.

Summary updated

Abstract

Ranking items is a central task in many information retrieval and recommender systems. User input for the ranking task often comes in the form of ratings on a coarse discrete scale. We ask whether it is possible to recover a fine-grained item ranking from such coarse-grained ratings. We model items as having scores and users as having thresholds; a user rates an item positively if the item's score exceeds the user's threshold. Although all users agree on the total item order, estimating that order is challenging when both the scores and the thresholds are latent. Under our model, any ranking method naturally partitions the $n$ items into bins; the bins are ordered, but the items inside each bin are still unordered. Users arrive sequentially, and every new user can be queried to refine the current ranking. We prove that achieving a near-perfect ranking, measured by Spearman distance, requires $Θ(n^2)$ users (and therefore $Ω(n^2)$ queries). This is significantly worse than the $O(n\log n)$ queries needed to rank from comparisons; the gap reflects the additional queries needed to identify the users who have the appropriate thresholds. Our bound also quantifies the impact of a mismatch between score and threshold distributions via a quadratic divergence factor. To show the tightness of our results, we provide a ranking algorithm whose query complexity matches our bound up to a logarithmic factor. Our work reveals a tension in online ranking: diversity in thresholds is necessary to merge coarse ratings from many users into a fine-grained ranking, but this diversity has a cost if the thresholds are a priori unknown.
BibTeX
@inproceedings{villemaud2026ranking,
  author = {Oscar Villemaud and Suryanarayana Sankagiri and Matthias Grossglauser},
  title = {{Ranking Items from Discrete Ratings: The Cost of Unknown User Thresholds}},
  booktitle = {ALT},
  year = {2026},
  url = {https://openreview.net/forum?id=MZhIzJxg7L},
}
Figure