Ranking metrics: NDCG, MAP, MRR

Summary

Ranking metrics assign different credit to gain, coverage, precision at hits, and the first useful result. Choose the decision target, judged universe, cutoff, relevance definition, and query weights before comparing systems. A high score under one credit rule need not establish performance under another.

NDCG. The dominant ranking metric

Use nonnegative graded judgments and exponential gain for this lesson:

Discounted Cumulative Gain at $K$ :

DCG_{K} = i = 1 \sum K \frac{2 ^{rel_{i}} - 1}{lo g _{2} ( i + 1 )} .

For the hypothetical fully judged ranking [3,0,2,1] at cutoff four, DCG is $7 + 0 + 3/2 + 1/ lo g_{2} (5) = 8.93068$ . Sort the judged grades only for the ideal reference: [3,2,1,0] gives IDCG $9.39279$ .

NDCG normalizes by the ideal ranking’s DCG so scores live in [0, 1]:

NDCG_{K} = \frac{DCG _{K}}{IDCG _{K}} .

The ratio is approximately $0.95080$ . It lies in $[0, 1]$ under the stated nonnegative-gain and common-universe conventions when IDCG is positive. Normalization does not make different gain scales or judging populations interchangeable.

MAP. Average precision averaged over queries

For a query with binary relevance:

Precision at position $k$ : $P@k = \frac{relevant items in top k}{k}$ .

Average Precision:

AP = \frac{1}{R} k = 1 \sum K P@k \cdot 1 [item at k is relevant]

Define binary relevance as grade greater than zero; the fixture has total $R = 3$ . Use the full-universe R denominator even when truncating at K here. Then AP@4 is $(1 + 2/3 + 3/4) /3 = 29/36 \approx 0.80556$ . Alternative denominators, such as $min (R, K)$ , define different truncated metrics and must be labeled.

MAP is the declared query-weighted mean of AP; equal-query averaging and traffic-weighted averaging target different populations.

MRR. When there’s one right answer

Let r be the first relevant rank, even if multiple relevant items exist:

RR = {1/ r 0 if a correct answer is in top-K otherwise

MRR averages reciprocal rank over queries. The left fixture has first hit at rank one, so RR is one. The separate right-hand example has first hit at rank three, so RR is $1/3$ .

Learning objective

Average precision accumulates relevant hits; reciprocal rank stops at the first

Derivation

Many relevant items: graded or binary?

The same four results support two different judgments.

Rank	Grade	DCG credit	AP checkpoint
1	3 · relevant	(2³−1) / 1 = 7.00	1 / 1
2	0 · not relevant	0	Skip
3	2 · relevant	(2²−1) / 2 = 1.50	2 / 3
4	1 · relevant	(2¹−1) / 2.32 = 0.43	3 / 4

NDCG@4 = 8.93 / 9.39 = 0.95
AP = (1 + 2/3 + 3/4) / 3 = 0.81

First useful answer: stop at its rank

MRR ignores later ranks once the answer is found.

Rank	Answer?	MRR action
1	Wrong	Continue
2	Wrong	Continue
3	Correct	Stop

RR = 1 / first correct rank = 1 / 3 = 0.33

the left table accumulates unnormalized DCG terms and precision at binary-relevant hits. Divide by IDCG or R under the stated conventions. The separate right example stops at its first useful answer. Original calculations follow the cumulative-gain paper, IR textbook, and TREC-8 QA evaluation.

Check: Which metric keeps accumulating after the first relevant item? What extra averaging step produces MAP or MRR?

Read it this way: Relevant ranks 2 and 4 give reciprocal rank 1/2. Average precision is ((1/2)+(2/4))/2=1/2, but its two contributions come from both hits.
Which metric can change if a later relevant item moves?

Hit rate and recall@K

Recall@K is retrieved relevant count divided by R; hit@K is an indicator that any relevant result was retrieved. They coincide only under particular relevance settings, such as exactly one relevant item per query.

Change Retrieval Depth

New task: Permit only two candidates to reach the next stage.

Picture and change: Set K to two without changing total R or the judged universe.

Check: The fixture has hit@2 one, recall@2 $1/3$ , and full-R AP@2 $1/3$ . One successful hit does not mean complete candidate coverage.

Use when: Candidate-generation capacity binds and the downstream stage cannot recover omitted items.

Change the Reward Target

New task: One useful answer suffices regardless of later results.

Picture and change: Use reciprocal first-hit rank instead of AP.

Check: Adding a relevant result at rank four after a first hit at rank three leaves RR at $1/3$ .

Use when: The user stops at the first satisfactory answer; multiple valid answers remain possible.

For R zero or IDCG zero, the corresponding ratios are undefined; this lesson excludes those queries and reports their count. Benchmark zero-value conventions are alternatives, not silent substitutions. Declare unjudged-item handling, duplicates, score ties, and query weights before evaluation; unjudged does not automatically mean irrelevant.

Metric	Order matters?	Graded relevance?	Multi-relevant per query?
NDCG	Yes	Yes	Yes
MAP	Yes	No (binary)	Yes
MRR	Yes	No	Yes, but only first hit earns credit
Recall@K	No (just need in top-K)	No	Yes
Precision@K	No	No	Yes

When to use which

Graded utility: choose gains and discounts justified by the judgment/task model.
Multiple relevant items: AP rewards precision at successive hits; recall measures coverage.
First-answer utility: RR ignores later relevant items after the first.
Candidate generation: inspect coverage at its actual capacity and query slices.

Common pitfalls

Different gain scales: grades zero-to-three and zero-to-four need common semantics before comparing their exponential-gain scores.
Wrong universe: computing IDCG over only returned items can conceal missing relevant candidates.
Pooling queries: equal-query, traffic-weighted, and pooled-count measurements need not agree.
One number: report intended cutoffs, uncertainty, judging coverage, and important slices rather than treating one metric as universal utility.

Precision, recall, F1. Binary classification metrics.
Two-tower retrieval. What gets evaluated with these metrics in production.
Learning-to-rank losses. Surrogate objectives for ordered results.
Position bias and counterfactual ranking. Evaluation from biased interaction logs.