Part I · Statement and measurement · chapter 3 of 19

Metrics: what measures candidate generation and ranking

The two stages of the funnel have different jobs, so they have different metrics: the first is measured by recall, the second by order. After that the fine points begin, and they are what people get caught on: recall cannot be compared at a fixed K, precision does not see swaps, AUC knows nothing about calibration, and averaging over queries hides the degradation of newcomers. Every example here is computed and reproducible.

What to take away

Recall@K is compared at an equal budget, not an equal K. Otherwise you are comparing engineering decisions about output size rather than models.
Precision@k is blind to order. Three arrangements of the same slate give identical 0.300, while NDCG gives 1.0000, 0.5508 and 0.4250.
The same swap of neighbours costs differently. At the top ΔNDCG = 0.3691, at position nine it is 0.0120 — a difference of 31 times. Ranking losses grow out of this.
AUC is invariant to any monotone transformation of the score and therefore says nothing about calibration. Where the score is multiplied by money, you need LogLoss and ECE.

1. Two stages — two metrics

The job of candidate generation is not to lose. The job of ranking is to arrange. Everything else follows from that.

	Candidate generation	Ranking
the question	is the right item among those selected	is it in the right order
metric	Recall@K, HitRate@K	NDCG, MRR, MAP
K	hundreds to thousands	units to tens
cost of a mistake	unrecoverable: what is not there will not be shown	recoverable by re-ranking

Measuring a candidate generator by precision is not merely useless but harmful: precision pushes you to select fewer and safer items, that is, straight into the popular, collapsing coverage.

2. Metrics of candidate generation

Recall@K and HitRate@K

$$ \mathrm{Recall@}K = \frac{\#\{\text{relevant in the top }K\}}{\#\{\text{all relevant}\}}, \qquad \mathrm{HitRate@}K = \frac{\#\{\text{queries with at least one relevant in the top }K\}}{\#\ \text{queries}} $$

Both answer one question — «did the right item reach the second stage» — at different granularity: under the sum HitRate has a 0/1 instead of the recall itself. HitRate is convenient when the nature of the product means there is exactly one positive.

Problem 1: relative to what do we compute the denominator

«All relevant» — relevant according to whom? Two options, and both have a price.

Relative to the dataset. The denominator is the positives of the held-out set. Cheap, reproducible, but those positives were collected by the previous policy: whatever the system never showed is not counted as relevant by construction. Recall comes out inflated.
Jointly with the ranking stage. We measure how much of what the ranker would consider good actually reached it. More honest with respect to production, but more expensive, and it depends on the current version of the ranker — the metric stops being stable over time.

The engineering compromise usually chosen: measure against the dataset day to day, and jointly with ranking before a rollout.

Problem 2: K is already an engineering decision

By fixing $K$ we decide in advance how many candidates the first stage returns. And the $\mathrm{Recall}(K)$ curves of different sources are shaped differently: one gathers recall quickly over the first few tens and plateaus, another grows slowly but higher.

And the main point: candidate generators cost different amounts. A static top from memory costs almost nothing, a trip to an ANN index costs milliseconds, a neural source noticeably more.

So what is compared is not $\mathrm{Recall}(K)$ but recall relative to the latency budget: you build a Pareto front of «recall against time» and pick the point that fits your budget. A source with slightly lower recall but three times cheaper often wins — the time saved buys you another source.

What to look for here

Set the budget to 3 ms: the popular top wins — not because it is better, but because at that budget the others manage to return too few candidates.
Pull the budget towards 20 ms: the winner changes twice. Hence the rule — Recall@K cannot be compared at a fixed K.
Look at the shape of the curves: some gather recall quickly and hit a plateau, others grow longer but higher. That is what tells you how many items to take from each source.

What to say in an interview: «The recall of a candidate generator is compared at an equal latency budget, not an equal K — otherwise you are comparing engineering decisions rather than models».

The widget with the Pareto front is on the trainer page.

Coverage: the metric people forget

Recall answers the question «did we find the right item». It says nothing about how much of the catalogue the system is capable of showing at all. That is what coverage is for: the share of the catalogue that made it into somebody's output over a period.

Why it has to be read next to recall

A source that always returns the popular top shows decent recall at a negligible cost — and zero coverage. Formally it is not bad: the popular really is relevant more often.

But that is exactly how the loop from the previous chapter closes: in the simulation coverage stopped at 0.6% of the catalogue, and recall metrics did not show it at all. Coverage is the cheapest early diagnosis of degeneration, and almost nobody looks at it.

3. Metrics of ranking

Next comes the same output computed by different metrics. A slate of ten positions with only three relevant items, and only their arrangement changes.

One output, three arrangements

Arrangement	Slate	P@10	R@10	RR	AP	NDCG
hits at the top	`1110000000`	0.300	1.000	1.000	1.000	1.0000
hits in the middle	`0001110000`	0.300	1.000	0.250	0.383	0.5508
hits at the bottom	`0000000111`	0.300	1.000	0.125	0.216	0.4250

The numbers are reproduced by the script _tools/metrics_demo.py in this repository.

Precision and recall are identical in all three rows. They do not see order at all — and order is precisely the product. Hence the need for the whole rest of the list.

MRR — when there is exactly one positive

$$ \mathrm{RR} = \frac{1}{\mathrm{rank}}, \qquad \mathrm{MRR@}K = \frac{1}{|Q|}\sum_{q} \mathrm{RR}_q $$

where $\mathrm{rank}$ is the position of the first relevant item; if there is none in the top $K$, usually $\mathrm{RR} = 0$.

It is used where the nature of the product says the right answer is one: «next track», navigational search, autocomplete. In that scenario MRR also dampens positional effects rather well, because the whole mass of the metric sits on the first find.

MAP — and why NDCG displaced it

$$ \mathrm{AP} = \frac{1}{|R|}\sum_{k=1}^{K} \mathrm{Precision@}k \cdot rel_k, \qquad \mathrm{MAP} = \frac{1}{|Q|}\sum_{q}\mathrm{AP}_q $$

Position is taken into account indirectly here: in a normal system $\mathrm{Precision@}k$ decreases as $k$ grows, so a positive at the top contributes more.

Two caveats people ask about

The normalisation is ambiguous. Here the denominator $|R|$ is all relevant items; $\min(|R|, K)$ is also used, and then the metric can reach one even when $|R| > K$. This is worth clarifying rather than assuming.
The metric is binary by nature. AP cannot express graded relevance: «excellent», «will do» and «bad» are either 1 or 0 to it. NDCG can, and that is the main reason it won in industry.

NDCG — the industry standard

$$ \mathrm{DCG@}K = \sum_{k=1}^{K} \frac{g(rel_k)}{\log_2(k+1)}, \qquad \mathrm{NDCG@}K = \frac{\mathrm{DCG@}K}{\mathrm{IDCG@}K} $$

Three parts, and each does its own work.

Gain: what measures the value of a hit

The metric does not merely permit its own definition of $g(rel)$ — it demands one. For binary relevance $g(rel) = rel$. For graded relevance the exponential variant $g(rel) = 2^{rel} - 1$ is popular, and it separates «excellent» from «will do» more sharply.

How much more sharply is a computation. Two arrangements with labels 3, 1, 1 and zeros:

Gain	`[3,0,0,1,1]`	`[1,1,0,0,3]`	gap
linear	0.9241	0.6758	0.2484
exponential	0.9615	0.5336	0.4278

The exponential gain punishes the most valuable item sliding down almost twice as hard. And for e-commerce you can put the price of a positive into the gain — then NDCG starts measuring money rather than clicks.

The discount: why a logarithm

The factor $1/\log_2(k+1)$ by position: 1st — 1.00, 2nd — 0.63, 3rd — 0.50, 5th — 0.39, 10th — 0.29.

The logarithm was chosen as a compromise: it decays enough for the top of the output to dominate, but not so sharply that everything beyond the first two places is zeroed out. This is a modelling assumption about attention, not a measured quantity — and if you have your own curve of examination by position, it is more honest to substitute it.

The number ranking losses grow out of

Take a slate with one relevant item and swap two adjacent positions — the same swap at different depths:

Swapping	NDCG was	became	ΔNDCG
positions 1 and 2	1.0000	0.6309	0.3691
positions 2 and 3	0.6309	0.5000	0.1309
positions 3 and 4	0.5000	0.4307	0.0693
positions 9 and 10	0.3010	0.2891	0.0120

The same mistake — one inversion — costs 31 times more at the top than at position nine. Remember this one: it is exactly why pairwise losses that treat all inversions alike turn out not to be what is needed, and why LambdaRank appears.

Normalising by IDCG: what it is for

IDCG is the DCG of the ideal order for this same query. Dividing by it makes the metric comparable across queries with different numbers of positives, which neither Precision@K nor DCG can do.

An important detail in implementation: the ideal order is limited both by the number of positives and by the length of the output, that is, $\min(|R|, K)$. Without that NDCG stops being normalised to one — the classic bug in home-grown implementations.

What to look for here

Drag the relevant items downwards: precision does not change at all, while AP and NDCG fall. This is the same thing as the table above, but by hand.
Switch on graded labels and set the gain to exponential — the gap between a good and a bad arrangement grows.
Reduce $K$: the metrics stop seeing what is below the cutoff and start behaving differently. $K$ is part of the definition of the metric, not an implementation detail.

What to say in an interview: «Precision@k does not see order, MRR suits the case of a single positive, MAP is binary by nature, NDCG handles graded relevance and an explicit discount by position — which is why it became the standard».

4. AUC and what it does not see

$$ \mathrm{AUC} \;=\; P\bigl(f(u, i^{+}) > f(u, i^{-})\bigr) \;=\; \frac{1}{|P||N|}\sum_{i^{+} \in P}\ \sum_{i^{-} \in N} \mathbb{1}\bigl[f(u,i^{+}) > f(u,i^{-})\bigr] $$

The share of correctly ordered «positive–negative» pairs. Convenient in that it depends neither on the calibration of the scores, nor on a threshold, nor (almost) on class imbalance.

What is inconvenient about it

All pairs count equally. Swapping the first and second position costs exactly as much as swapping the two-hundredth and two-hundred-and-first — and the user only sees the first. For ranking an output that is precisely the blindness NDCG exists because of.

Hence the practical point: AUC is good as a metric of the model (can it tell a positive from a negative at all) and bad as a metric of the product.

AUC knows nothing about calibration

AUC is invariant to any monotone transformation of the score: square all the predictions, add a constant, push them through a sigmoid — the order does not change, and AUC does not move in the fourth decimal.

So a model with a beautiful AUC may systematically double its probabilities, and AUC will not show it. For ranking that is harmless. It is fatal where the score enters arithmetic:

an ad auction where the bid is multiplied by the predicted CTR;
splitting a budget between surfaces;
any rule of the form «show it if the probability is above a threshold».

For that there are LogLoss, Brier and ECE plus a calibration curve. Calibration is repaired after training (Platt scaling, isotonic regression) and does not interfere with ranking: AUC does not change.

Both widgets — AUC against threshold and imbalance and calibration — are on the trainer page. The second shows the main point well: the sliders change ECE and LogLoss severalfold while AUC stands still.

5. What to average over

Every one of these metrics is an average over something, and what exactly is usually left unsaid. It should not be: it changes the number and, more importantly, changes which regressions you are able to notice.

	Micro: over queries	Macro: over users
how it is computed	the average over all slates at once	first the average inside a user, then over users
the question it answers	how the average query is doing	how the average user is doing
who determines the number	the active: they have tens of times more queries	everyone equally, including someone who made one query

Why this is not pedantry

Activity is distributed just as heavily as popularity. Newcomers may be half the audience by headcount and a couple of percent by queries.

The consequence: a release that kills onboarding looks neutral in micro. Drop the metric for newcomers to zero and micro sags by hundredths, macro by tenths.

The reverse holds too: macro gives a full voice to someone who made one query and left, and is therefore noisier. So both numbers are read, and the divergence between them is itself a diagnosis.

What to look for here

Look at the shares: newcomers are half the audience by headcount and a few percent by queries. Micro is almost entirely determined by the active.
Drop the quality for newcomers: micro barely moves, macro sags noticeably.
Now do the opposite — drop it for the active: both fall, and that is the case where the problem is noticed even without cutting by cohort.

What to say in an interview: «Averaging over queries measures the average query, over users the average user. With a heavy tail of activity these are different numbers, and the degradation of newcomers is visible only in the second».

Interview questions

Why is candidate generation measured by recall while ranking is not?

Because the jobs differ. The first stage must not lose: what it did not select, the second will never show, and the mistake is unrecoverable. The second must arrange: its mistake is recoverable by re-ranking.

Measuring a candidate generator by precision is harmful: precision pushes you to select fewer and safer items, that is, into the popular, collapsing coverage. And end-to-end quality is bounded above by the recall of the first stage anyway.

Why can't Recall@K be compared at a fixed K?

Because K is already an engineering decision about output size, and sources cost different amounts: a static top from memory is nearly free, an ANN index costs milliseconds, a neural source noticeably more.

What has to be compared is recall relative to the latency budget: build a Pareto front of «recall against time» and take the point that fits your budget. A source with lower recall but three times cheaper often wins — the time saved adds another source.

Separately, the denominator is worth clarifying: do we count relative to the positives of the dataset (cheap, but inflated — those positives were collected by the previous policy) or jointly with ranking (more honest, but unstable over time).

What makes NDCG better than MAP and Precision@k?

Precision@k does not see order at all: three arrangements of the same slate with hits at the top, in the middle and at the bottom give an identical 0.300, whereas NDCG gives 1.0000, 0.5508 and 0.4250.

MAP does take order into account, but it is binary by nature: it cannot express graded relevance. NDCG handles a graded gain (including the exponential $2^{rel}-1$, or the price of a positive directly), an explicit discount by position, and normalisation by the ideal order, which makes queries with different numbers of positives comparable.

A caveat: the logarithmic discount is a modelling assumption about attention, not a measured quantity.

Why is one inversion not equal to another inversion?

Because of the discount. Swapping adjacent positions 1 and 2 changes NDCG by 0.3691; the same swap at positions 9 and 10 changes it by 0.0120. A difference of 31 times.

It follows that a pairwise loss treating all inversions alike (RankNet) optimises something other than what we measure. The correction is to multiply the gradient of a pair by how much swapping it would move the metric; that is how LambdaRank works.

What does AUC not show, and when is that critical?

First, AUC counts all pairs equally: a swap at the first position costs as much as one at the two-hundredth. For an output where the first ten are visible, that is precisely the blindness NDCG is needed for.

Second, AUC is invariant to any monotone transformation of the score and therefore says nothing about calibration. A model can systematically double its probabilities while having an excellent AUC.

It is critical where the score enters arithmetic: an ad auction with bid × CTR, budget allocation, threshold rules. There you look at LogLoss, Brier, ECE and the calibration curve. Calibration is repaired after training and does not spoil AUC.

Micro or macro: what should a metric be averaged over?

Over queries (micro) — this measures the average query, and the number is almost entirely determined by active users, who have tens of times more queries. Over users (macro) — this measures the average user, all voices equal.

The practical consequence: a release that kills onboarding looks neutral in micro — newcomers may be half the audience by headcount and a few percent by queries. Macro will sag noticeably.

The answer «I look at both and cut by cohort separately» is the right one: the divergence between micro and macro is itself a diagnosis.

One-screen cheat sheet

Candidate generation

Recall@K, HitRate@K. Compare at an equal budget, not an equal K. Read coverage alongside.

Precision is blind

Three arrangements of one slate — an identical 0.300. It does not see order.

NDCG

Gain (linear, $2^{rel}-1$ or a price) × discount $1/\log_2(k+1)$, divided by the ideal. Discount: 1.00, 0.63, 0.50, 0.29.

Inversions are unequal

At the top ΔNDCG 0.3691, at position nine 0.0120 — 31 times. Hence LambdaRank.

AUC

The probability that a positive is above a negative. Invariant to monotone transformations → silent about calibration.

Averaging

Micro — the average query, macro — the average user. The degradation of newcomers is visible only in the second.

Primary sources

K. Järvelin, J. Kekäläinen. Cumulated Gain-based Evaluation of IR Techniques, TOIS 2002 — the work in which DCG and its normalised version appeared.
C. Burges. From RankNet to LambdaRank to LambdaMART, MSR 2010 — where multiplying the gradient by ΔNDCG comes from.
A. Niculescu-Mizil, R. Caruana. Predicting Good Probabilities With Supervised Learning, ICML 2005 — Platt scaling and isotonic regression.
J. Davis, M. Goadrich. The Relationship Between Precision-Recall and ROC Curves, ICML 2006 — why PR rather than ROC is used on rare events.
The numbers in this chapter: _tools/metrics_demo.py in this repository.