06 · Evaluation and experiments
Retrieval and ranking metrics
8 min read
A search or recommendation system does two jobs, picking a shortlist out of a huge catalogue and putting that shortlist in order. Each job fails in its own way. Retrieval metrics measure whether the good items made the shortlist at all, and ranking metrics measure where they ended up. Telling the two apart decides which part of the system to fix.
An everyday example
A reader asks a librarian for books about ancient Rome. The librarian walks the stacks and fills a cart with thirty books that seem to fit, then arranges five of them face out on the display table by the door. A good Rome book left in the stacks never reaches the table whatever the librarian does next, and a good book at the bottom of the cart may as well be in the stacks.
The two jobs are retrieval, the walk through the stacks, and ranking, the arrangement on the table. Readers take what is at eye level, so what gets borrowed says as much about the table layout as about the books. The sections below measure the cart, then measure the table, then deal with that eye-level problem.
The librarian knows which books are good because she has read them, and that is where the analogy breaks. A search system has to be told which results were relevant by paid judges or by what people clicked, and both sources are incomplete in ways the metrics inherit.
Check whether relevant items reach the ranker
Recall at K is the share of the known relevant items that appear in the first K the system retrieved. If a query has ten judged relevant items and the shortlist of 300 contains seven of them, recall at 300 is 0.7, and the ranker that comes next can never show the three missing ones however good it is. This is the cart metric, and it is checked first because a low number here makes every ranking metric below it misleading.
Precision at K is the share of the first K results that are relevant, so a display of five results with three relevant items has precision at 5 of 0.6. Both numbers depend on who judged relevance and how much of the catalogue they looked at. An item nobody judged may still be relevant, and a system that finds it is punished for it, which is why evaluation sets are built by pooling the results of several systems before anyone judges them.
Use position-sensitive metrics for ordering
Mean reciprocal rank looks only at the first relevant result and gives a query one divided by its position. A relevant item at position one scores 1, at position three scores a third, and a query with no relevant result in the list scores zero. Over three queries with first hits at positions 1 and 3 and one miss, the mean is (1 + 1/3 + 0) / 3, about 0.44. It fits tasks where one good answer is enough, such as finding a specific song, and it ignores everything after the first hit.
Normalized discounted cumulative gain, or NDCG, rewards putting the most relevant items highest and then compares the result with the best possible order of the same items. Each item’s relevance grade is turned into a gain, and that gain is divided by a discount that grows with position. Using gain = 2^relevance − 1 and discount = log₂(position + 1), grades [3, 0, 2] give DCG@3 of 7 + 0 + 3/2 = 8.5. The ideal order [3, 2, 0] gives about 8.893, so NDCG@3 is about 0.956 under this convention, meaning the list earned about 96 percent of the credit the perfect order would have.
Some libraries take the gains directly, so reproducing this number means passing [7, 0, 3] rather than the grades. The result also depends on how many positions you score and on what a query with no relevant items counts as. Fix those conventions once and keep them, because two teams with different conventions will report different NDCG for the same list.
gain(relevance) = 2^relevance − 1
DCG@K = Σ gain(relevance at position i) / log₂(i + 1)
NDCG@K = DCG@K / ideal DCG@KDo not confuse logged clicks with unbiased relevance
The clicks in your logs were made on lists the previous ranker chose, and people click what is near the top whether or not it was best, which engineers call position bias. Judging a new ranker only by whether it would have put the old clicks higher rewards it for copying the old ranker and punishes it for surfacing anything the old one buried.
There are three ways out, each with a cost. Paid relevance judgments do not depend on position but are expensive and slow. Showing a small share of lists in random order gives unbiased clicks at the cost of some worse results for those people. Counterfactual estimators reweight the logged clicks by how likely each item was to be seen, which is cheap but rests on assumptions that have to be checked. A design usually mixes a small randomized share with judgments on the queries that matter most.
Comparisons also need the same evaluation pool for both models, with separate checks on common and rare queries and on new items. A stronger average can hide a ranker that has stopped showing anything added in the last week, which is the kind of failure error analysis is for.
Where people get confused
Tuning the ranker when the problem is retrieval is the confusion that wastes the most time. If recall at 300 is 0.4, six in ten relevant items never reach the ranker, and no ranking change can show them, so the cart has to be measured before the table is polished.
Two smaller confusions are about what the numbers mean. A click gets treated as relevance, when it says only that the item was near the top and looked good enough to try, and an unclicked item at position twelve says almost nothing about whether it was good. An NDCG gets quoted without its conventions, and unless the cutoff, the gain formula and the treatment of unjudged items are stated, the number cannot be compared with anyone else’s.
In the interview
State recall at the shortlist size for the retrieval stage and NDCG or precision at the display size for the ranking stage, name position bias in one sentence and say how you would collect unbiased labels, then stop. That is three or four minutes of the evaluation phase on any search or recommendation problem, and it is enough.
The online metric, such as clicks or watch time per person, belongs to the experiments phase, and saying so shows you know the difference between the two.
Interview questions
You improve the ranker, but recall of relevant items in the final results barely changes. Where do you look?
I would measure recall before ranking, at the shortlist size. If the shortlist of 300 holds only four of every ten relevant items, the ranker is reordering a list that is missing most of what matters, and no ranking change can bring the missing items back.
The fix is in retrieval, so I would look at the retrieval sources, how the query is represented, the filters and how fresh the index is. I would also confirm that both evaluations used the same candidate pool and the same judgments, because a change in either can hide what the ranker improved.
Would you use mean reciprocal rank or NDCG for a music search box?
For a search box where the person is looking for one specific song, I would use mean reciprocal rank, because the only thing that matters is how far down the one right answer sits. A first hit at position three scoring a third matches how it feels to scroll past two wrong songs.
For a browse or discovery page, where several results can be good to different degrees, I would switch to NDCG at the display size, since it credits every relevant item and credits the ones near the top more. The metric follows what the person is trying to do on that screen.
Your only labels are clicks from the current system. How do you evaluate a new ranker fairly?
I would start by saying that the clicks are biased toward whatever the current ranker put at the top, so scoring the new ranker on them rewards copying the old one. To get labels that do not depend on position, I would show about one percent of lists in a random order and use only those clicks, and I would pay for relevance judgments on the few hundred most common queries.
If randomizing is not allowed, I would reweight the logged clicks by how likely each position was to be seen, and say plainly that this rests on assumptions I would want to check against the judged queries.
What to practice next
Design these systems on the canvas and get your design graded.
These problems compute the cart metric and the table metrics from this topic on small lists, so you can see for yourself how moving one relevant item up two places changes NDCG and leaves recall alone.