Evaluating Recommender Systems via Negative Sampling

This direction is split into other directions: sampled metric inconsistency. Its last version stays readable and citable here.

Version 1 of 114 papers26 conceptsfrozen 2026-10-04

In recommendation research, evaluating a model's performance on the "full" catalog of millions of items is computationally expensive. To save time, researchers often use a shortcut: they take the item a user actually interacted with (the positive) and mix it with a small random sample of items the user didn't interact with (the negatives). They then rank only this small subset and calculate metrics like NDCG or Hit-Ratio.

While this approach is efficient, it introduces a fundamental question: does a model that looks good on a sample of 100 items actually perform well on a catalog of 100,000?

The Convergence to AUC

The most significant critique of sampling-based evaluation is that it fundamentally changes what the metrics measure. In a full-catalog evaluation, position-aware metrics like NDCG or Precision@K are "top-heavy"—they reward a model much more for moving an item from rank 10 to rank 1 than from rank 100 to rank 91.

However, Walid Krichene and Steffen Rendle demonstrate in On Sampled Metrics for Item Recommendation that as the number of sampled negatives decreases, these metrics lose their sensitivity to top-tier rankings. Mathematically, the sampled metrics begin to behave like the Area Under the ROC Curve (AUC).

This happens because, in a small sample, the probability of a "good" item appearing in the top $K$ depends less on its exact position at the very top of the global list and more on its general ability to outrank a random item. This "AUC-ification" means that improvements at the bottom of the list are weighted equally with improvements at the top, which does not reflect real-world utility where users rarely scroll past the first few results.

The Consistency Debate

If sampling changes the nature of the metrics, can we still trust it to tell us which algorithm is better? This is the core of the "consistency" debate.

On one side, researchers like Theis E. Jendal, Matteo Lissandrini, and Peter Dolog argue in Simple and Powerful Architecture for Inductive Recommendation Using Knowledge Graph Convolutions that subsampling creates a "misleading perception of model performance." They found that models optimized for sampled metrics often fail to outperform simple popularity-based baselines when tested against the full item set. Similarly, Filip Cornell and colleagues show in Are We Really Measuring Progress? that sampling strategies can actually flip leaderboards, making inferior models appear superior.

On the other side, Ruoming Jin and Dong Li provide a more optimistic view in On Sampling Top-K Recommendation Evaluation. They prove that while a sampled metric (like Hit-Ratio@10) won't match the global Hit-Ratio@10, it is a "statistically consistent" proxy. If Model A beats Model B on a sampled evaluation, it is highly likely to beat it on the full catalog as well, provided the sampling is understood as a predictable scaling of the original problem.

From Metrics to Rank Distributions

To bridge the gap between sampled efficiency and global accuracy, Ruoming Jin and Jing Gao suggest a shift in perspective. Instead of trying to calculate a specific metric (like NDCG) directly from the sample, we should use the sample to estimate the empirical rank distribution of the items.

In On Estimating Recommendation Evaluation Metrics under Sampling, the authors model the sampling process as a mixture of binomial distributions. By observing where the positive item falls within a small sample, they use Maximum Likelihood Estimation (MLE) or Maximum Entropy (MaxEnt) to infer where that item likely sits in the full catalog of millions.

This approach treats the sample not as a "mini-test" but as a noisy signal of the true global rank. By reconstructing the underlying distribution first, researchers can then derive any metric (NDCG, Precision, Recall) with much higher accuracy and lower bias than by calculating them directly on the raw sample. This allows for the computational savings of sampling without the "AUC-ification" that distorts model comparisons.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_evaluating_recommender_systems_via_negat_fd1263ea,
  title = {Evaluating Recommender Systems via Negative Sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/evaluating-recommender-systems-via-negative-sampling/rdr_fd1263eaf6044aa29cd4d98796a92097},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_evaluating_recommender_systems_via_negat_fd1263ea_v1,
  title = {Evaluating Recommender Systems via Negative Sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/evaluating-recommender-systems-via-negative-sampling/rdr_fd1263eaf6044aa29cd4d98796a92097/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}