Ranking, Retrieval, and Top-K Metrics

A search engine may retrieve every relevant document somewhere in a million-item list and still fail the user. Ranking evaluation gives position and attention explicit weight.

Position is worth something measurable, and an eye tracker can separate looking from clicking. In 2005 Google result pages went in front of Cornell undergraduates, in a study by Joachims and Granka. Phase I had 34 participants, 29 of whom produced usable eye-movement data. Phase II had 22, of whom 16 did. Attention was spread almost evenly over the top two abstracts. The clicks were not. “It is very interesting that users click substantially more often on the first than on the second link, while they view the corresponding abstract with almost equal frequency.”

Then the study intervened. The ten results were silently reversed before display. The mean rank of a clicked document moved from 2.66 to 4.03. Clicks per query fell from 0.80 to 0.64. The documents were the same documents. Only the order had changed, and both the depth users reached and the amount they clicked at all moved with it.

The metric should match the experience: one correct answer, several useful documents, graded relevance, or exhaustive retrieval.

A ranking pipeline often contains several bottlenecks, and the stages are not a teaching abstraction. YouTube runs them in production, and Google published how in 2016. “The candidate generation network takes events from the user's YouTube activity history as input and retrieves a small subset (hundreds) of videos from a large corpus.” Only those few hundred are ever scored by the ranking network. A survey written outside Google restates the cardinalities: “This system divides the recommendation task into two stages: candidate generation and candidate ranking. The candidate generation network retrieves a subset (hundreds) from all video corpus. The ranking network generates a top-n list (dozens) based on the nearest neighbors scores from the candidates.” Millions, then hundreds, then dozens. Each stage throws away what the next one can no longer recover. That is why each needs a score of its own.

The objective changes with the stage too. That final ranking network sorts by expected watch time, not by click-through rate. Ranking by click-through rate often promotes videos the user does not complete. A stage is defined by what it is trying to maximise, not only by where it sits in the diagram.

How much the earlier stages are actually worth is measurable. The TREC 2019 Deep Learning Track accepted two kinds of run. “Fullrank” runs do their own retrieval, end to end. “Rerank” runs only reorder a fixed candidate set. Across 75 runs from 15 groups, the best fullrank run beat the best rerank run by 0.9% NDCG@10 on documents and 3.6% on passages. A pipeline diagram shows where the bottlenecks could be. Only stage-level measurement shows where they are.

For “renew Italian passport,” suppose the top five gains are 3, 0, 2, 1, and 0. A four-point scale like this is not a teaching invention. Järvelin and Kekäläinen demonstrated cumulated gain on 20 TREC-7 topics judged on exactly such a scale, and the TREC 2019 Deep Learning Track judged its passages on a 4-level scale for the same reason.

No ranking metric is universally sufficient, and the one most often reported carries the most design decisions inside it. Cumulated gain, discounted cumulated gain and the normalised, ideal-relative measure came together in 2002, in an article by Järvelin and Kekäläinen. The first two “were originally presented in Järvelin and Kekäläinen [2000]”. Normalising against the ideal ordering is what the 2002 article added. All three were demonstrated on 20 TREC-7 topics judged on a four-point graded scale.

The discount is where the user model lives, and the authors say so rather than leaving it implicit: “A discounting function is needed that progressively reduces the document score as its rank increases but not too steeply (e.g., as division by rank) to allow for user persistence in examining further documents.” Each document's gain is divided by the log of its rank. The base b is chosen by whoever computes the metric. With base 2, a document at position 1024 still keeps one tenth of its face value.

So “depends on gain and discount” is not a caveat attached to NDCG. It is a statement that anyone reading your number needs to know which gain scale and which base produced it. Two teams reporting NDCG@10 on the same ranked list can honestly report different figures.

Mean metrics can be dominated by common, navigational, or easy queries. Report distributions, head versus tail, locale, intent, query length, and zero-result cases. Repeated queries from the same users create dependence. Uncertainty estimates and online experiments should use an analysis unit aligned with randomization or user experience.

A flat mean can hide two opposite effects at once. Cutrell and Guan showed that in 2007. Eighteen analysable participants of the 22 recruited searched with short, medium and long result snippets. Snippet length had no main effect on any measure. Pooled, the manipulation looked inert. Split by intent, the same data produced a significant Task Type x Snippet Length interaction on all five measures: “For navigational tasks, the time on task remained the same for short- and medium-length snippets but increased by 10 seconds for long snippets. In contrast, informational tasks showed an improvement in task time of 24 seconds with long snippets.” Informational tasks averaged 78.1 s against 36.9 s for navigational ones. Two slices moved in opposite directions. The average between them reported nothing at all.

A second reason to distrust the aggregate arrived in 2017. Maxwell and colleagues ran 53 participants through four summary-length conditions on the TREC AQUAINT collection. Longer summaries raised clickthrough on relevant and non-relevant items alike. Accuracy stayed similar across all four conditions. More clicking, no better answers — an engagement metric moving while the outcome metric does not.

Domain shift hides inside an average the way an intent slice does. BEIR, published in 2021, is built from “18 publicly available datasets from diverse text retrieval tasks and domains” and evaluates “10 state-of-the-art retrieval systems” across them. It found that “BM25 is a robust baseline”. Re-ranking and late-interaction models scored best on average, “at high computational costs”. An in-domain leaderboard would have reported none of that.

Keep stage metrics and user outcomes connected. The TREC 2019 Deep Learning Track is a worked example of the first four steps. Its passage task ran over a corpus of 8.8 million MS MARCO passages, with 503 thousand training queries and a reusable test set of 43 NIST-judged queries. It drew 75 runs from 15 groups.

Step 1 was settled before anything was scored: judgments on a 4-level graded scale. Step 3 then followed from step 1 rather than from convention — “Our main metric in both tasks is Normalized Discounted Cumulative Gain (NDCG)—specifically, NDCG@10, since it makes use of our 4-level judgments and focuses on the first results that users will see.” The cutoff was chosen from what users see. The gain scale was chosen from what the assessors had produced.

Step 2 was reported separately and with a different measure. The track used Normalized Cumulative Gain, without the position discount, to ask how much relevant material candidate generation had brought back at all. That separation is what let the organisers report how little the extra recall bought. The best fullrank run beat the best rerank run by only 0.9% NDCG@10 on documents and 3.6% on passages. A single end-to-end number could not have said that.

Step 5 is the one no offline track can do for you. At YouTube, offline metrics guide development while final effectiveness is decided by live A/B tests, because “live A/B results are not always correlated with offline experiments.”