Measuring Search Quality: nDCG, MRR and Click Metrics

Three metrics dominate ranking evaluation and they disagree with each other constantly, because each encodes a different belief about what a user does with a list. Work all three on the same five documents and the disagreements stop being mysterious.

One ranking, three metrics

A search engine returns five documents for a query. A human has graded each on the standard four-point scale — 3 perfect, 2 good, 1 marginal, 0 irrelevant — and the grades, in the order the engine returned them, are:

rank    1    2    3    4    5
grade   3    0    2    3    1

Something has gone wrong at rank 2 and something is under-placed at rank 4. Every metric below is an opinion about how much that costs.

nDCG, worked

Discounted cumulative gain says two things: a more relevant document is worth more, and a document further down the list is worth less. The exponential-gain form, which is the one Kaggle, LightGBM and most learning-to-rank libraries use, is:

DCG@k = SUM for i = 1..k of  (2^g_i - 1) / log2(i + 1)

  g_i   graded relevance of the document at rank i
  i     the rank, counting from 1

The numerator is the gain and the denominator is the discount. log2(i+1) is chosen so rank 1 divides by log2 2 = 1, which is to say it is not discounted at all, and everything after it is worth progressively less but never zero. Compute each term:

i=1  g=3  (2^3 - 1) / log2(2) = 7 / 1.0000 = 7.0000
i=2  g=0  (2^0 - 1) / log2(3) = 0 / 1.5850 = 0.0000
i=3  g=2  (2^2 - 1) / log2(4) = 3 / 2.0000 = 1.5000
i=4  g=3  (2^3 - 1) / log2(5) = 7 / 2.3219 = 3.0147
i=5  g=1  (2^1 - 1) / log2(6) = 1 / 2.5850 = 0.3868
                                  DCG@5   = 11.9016

That number means nothing on its own — it depends on how many good documents happened to exist. So normalise by the best ordering possible, which sorts the same grades descending: 3, 3, 2, 1, 0.

i=1  g=3   7 / 1.0000 = 7.0000
i=2  g=3   7 / 1.5850 = 4.4165
i=3  g=2   3 / 2.0000 = 1.5000
i=4  g=1   1 / 2.3219 = 0.4307
i=5  g=0   0 / 2.5850 = 0.0000
             IDCG@5   = 13.3472

nDCG@5 = 11.9016 / 13.3472 = 0.892

Now the two things worth noticing. First, the exponential gain makes grade 3 worth seven and grade 2 worth three — more than twice as much for one step on the scale. There is a linear-gain variant, g_i / log2(i+1), still used in parts of the literature, and it gives materially different numbers for the same ranking. Two papers reporting “nDCG@10” are not necessarily reporting the same quantity, and you cannot compare them without checking which gain function each used. The measure is due to Järvelin and Kekäläinen (2002); the variants came later.

Second, the discount is gentle. Moving the grade-3 document from rank 4 to rank 2 would add 7/1.585 - 7/2.322 = 4.417 - 3.015 = 1.402 to a DCG of about 12 — roughly a tenth. If your product is a mobile screen showing three results, a logarithmic discount understates the damage, and truncating to nDCG@3 is a more honest choice than arguing about the discount function.

MRR versus MAP

Mean reciprocal rank cares about exactly one thing: where the first relevant document landed.

MRR = (1/|Q|) * SUM over queries of  1 / rank_of_first_relevant

five queries, first relevant at ranks  1, 2, 4, 1, none
  RR =  1.00, 0.50, 0.25, 1.00, 0.00
  MRR = 2.75 / 5 = 0.55

On the five-document ranking above, the first relevant document is at rank 1, so RR = 1.0 — a perfect score for a ranking that put an irrelevant document second and a perfect document fourth. MRR is blind to all of that by construction, and that is the right behaviour when there is one correct answer and the user stops at it: a navigational query, a question-answering system, a “jump to the right document” product.

Mean average precision cares about all of them. Average precision walks the list, computes precision at each rank where a relevant document appears, and averages those:

treat grades >= 1 as relevant: ranks 1, 3, 4, 5 are relevant, 4 in total

  rank 1: 1 relevant seen of 1 shown -> P = 1/1 = 1.000
  rank 3: 2 relevant seen of 3 shown -> P = 2/3 = 0.667
  rank 4: 3 relevant seen of 4 shown -> P = 3/4 = 0.750
  rank 5: 4 relevant seen of 5 shown -> P = 4/5 = 0.800

AP = (1.000 + 0.667 + 0.750 + 0.800) / 4 = 0.804

MAP is the mean of AP over the query set. It is recall-aware — the denominator is the number of relevant documents, so failing to return one at all is penalised — and it is binary, so it throws away the difference between a perfect result and a marginal one. Use it when the user is expected to work through the list: legal discovery, academic search, anything where completeness is the product.

Why click-through rate lies

Offline metrics need judgements, which cost money, so every team eventually reaches for clicks instead. Clicks are free, plentiful and systematically biased, and the bias has a shape you can write down. The examination hypothesis, which underpins the cascade click model of Craswell and colleagues (2008), says a click requires two independent things:

P(click on document at rank i) = P(examined at rank i) * P(relevant)
                               =        e_i           *      r

e_i is the propensity: the probability the user looked at position i at all. It falls steeply with rank and it has nothing to do with the document. So two documents of identical quality have different click rates purely because of where they sat, and comparing their raw CTRs compares their positions.

Assume — and this is an assumption you must estimate for your own interface, not a fact — that e_1 = 1.00 and e_5 = 0.35. Then:

document A at rank 1: 100 clicks / 1000 impressions -> CTR 0.100
document B at rank 5:  35 clicks / 1000 impressions -> CTR 0.035

A looks nearly 3x better. Divide by propensity:

  A: 0.100 / 1.00 = 0.100
  B: 0.035 / 0.35 = 0.100

They are indistinguishable.

Dividing by the propensity is inverse propensity scoring, and it is the basis of unbiased learning-to-rank as set out by Joachims and colleagues (2017). The catch is estimating e_i. The clean way is a result-randomisation experiment: for a small fraction of traffic, swap two positions at random and compare click rates for the same document in both — any difference is propensity, because the document did not change. That experiment costs you a slice of degraded traffic, which is why it is worth doing once carefully rather than never.

There is a second bias underneath the first. Clicks only exist for documents that were shown, so click logs describe the ranker that produced them and cannot tell you about a document it never surfaced. Any model trained on them inherits that blind spot, which is one of the reasons online experiments are not optional however good your offline numbers look.

Choosing one

Report one primary metric and watch the rest. A dashboard with six ranking metrics is a dashboard where every change improves something, and that is indistinguishable from no dashboard at all.