Evaluating recommendation algorithms by ranking a small sample of items instead of the full catalog is a common but dangerous practice in recommender systems research. This paper demonstrates that "sampled metrics" are mathematically inconsistent—meaning they can rank a poor algorithm above a superior one even in expectation—and proposes statistical corrections to mitigate these errors.
The Problem: The Sampling Shortcut
In large-scale recommender systems, calculating the exact rank of a relevant item across millions of candidates is computationally expensive. To save time, researchers often take the relevant item and mix it with a small random sample of irrelevant items (e.g., 99 distractors). Metrics like NDCG, Recall@K, or Average Precision are then calculated on this subset. The underlying assumption is that performance on the sample is a reliable proxy for performance on the full catalog. This research proves that this assumption is often false; sampled metrics do not just add noise, they fundamentally alter the metric's properties.
Theoretical Framework
The authors establish that the rank of an item in a sample follows a Binomial distribution. Specifically, if an item has a true rank $r$ in a catalog of $n$ items, its rank $\tilde{r}$ in a sample of $m$ items is distributed as $\tilde{r} \sim B(m, \frac{r-1}{n-1}) + 1$.
A key finding is the "AUC Collapse." As the sample size $m$ decreases, every ranking metric begins to behave like the Area Under the ROC Curve (AUC). Unlike top-heavy metrics like NDCG, AUC is "position-unaware," treating an improvement at rank 100 the same as an improvement at rank 1.
Systematic Inconsistency and Flipped Rankings
The error introduced by sampling is not merely random noise that averages out over many trials. It is a systematic bias. In empirical "toy" examples, the authors show that a recommender that is ten times better than its competitors on exact metrics can appear to be the worst performing when evaluated using sampled Average Precision with 99 items.
Proposed Corrections
To address these biases, the paper proposes two main approaches:
- Unbiased Rank Estimator: An "upscaling" method to estimate the true rank from the sampled rank: $\hat{r} = 1 + \frac{(n-1)(\tilde{r}-1)}{m}$.
- Bias-Variance Trade-off: A regularized least-squares approach that minimizes the difference between the sampled estimate and the true value while controlling for variance.
Key Results and Recommendations
- AUC Consistency: The authors prove that AUC is the only common metric naturally consistent under sampling. If using Recall or NDCG on a sample, the researcher is no longer measuring those specific properties.
- Correction Efficacy: The proposed unbiased rank estimator significantly improves the likelihood of identifying the correct top algorithm, though it introduces higher variance, requiring more random seeds for stable results.
Conclusion
The ultimate recommendation is to avoid sampling whenever possible. Modern hardware and efficient indexing libraries (like FAISS) have largely removed the computational necessity for this shortcut. If sampling is unavoidable, researchers must apply statistical corrections and acknowledge that the fundamental characteristics of their chosen metrics have changed.
Summary updated