skip to content

How is NDCG@k computed over a ranked result list, and why divide by the ideal DCG?

level: middleimportance: must knowfreq 72%

answer

  1. Grades, not just relevant or not
  2. Each position's gain is shrunk by its rank
  3. The shrink factor is logarithmic
  4. Divide by the best ordering possible
  5. Result always lands between 0 and 1

basics

~20 s

NDCG sums each result's graded relevance discounted by a logarithm of its position, then divides that discounted cumulative gain by the gain of the best possible ordering. The division normalises every query onto a 0-to-1 scale so scores can be averaged.

solid answer

~50 s

NDCG assumes **graded** judgments — say 0 to 3 rather than relevant/not — and rewards putting high grades high. Discounted cumulative gain at cutoff k is `DCG@k = Σ rel_i / log2(i+1)` over positions 1..k, so a grade-3 document at rank 1 contributes its full gain while the same document at rank 8 contributes about a third of it. An alternative formulation uses `(2^rel_i − 1)` in the numerator, which weights top grades far more aggressively; state which one you mean. Raw DCG is not comparable across queries because one query may have ten grade-3 documents and another only one. So you compute **IDCG@k**, the DCG of the judged documents sorted into their ideal order, and report `NDCG@k = DCG@k / IDCG@k`. That lands every query in [0, 1], where 1 means the ranking is as good as the judgments allow, and makes the mean across a query set meaningful.

code

python · 7 lines
python
from math import log2

gains = [3, 2, 3, 0, 1, 2]                                   # graded judgments, in returned order
dcg  = sum(g / log2(i + 2) for i, g in enumerate(gains))     # ~6.86
ideal = sorted(gains, reverse=True)                          # [3, 3, 2, 2, 1, 0]
idcg = sum(g / log2(i + 2) for i, g in enumerate(ideal))     # ~7.14
ndcg = dcg / idcg                                            # ~0.96

go deeper

for a junior

Know that NDCG scores a ranking on graded relevance from 0 to 1, and that higher positions count more. Being able to read the formula is enough at this stage.

for a middle

Be able to write DCG with the log2(i+1) discount, compute a small example by hand, and explain exactly what the ideal DCG denominator is for.

for a senior

Show that you know NDCG's ceiling is set by the judgment set, that unjudged means zero, and that a small mean delta over a few dozen queries is not a result.

for a principal

Own the choice of grading scale, cutoff, and gain formulation as a standard for the whole organisation, since inconsistent NDCG definitions make teams' numbers silently incomparable.

## Why graded relevance Precision and recall treat relevance as binary. Real relevance is not: for the query "running shoes", the flagship running shoe is perfect, a trail-running shoe is good, a sports sock is marginal, and a garden hose is wrong. Collapsing that to yes/no throws away the signal that distinguishes a great ranking from a merely acceptable one. Graded judgments — typically a small ordinal scale such as 0 = irrelevant, 1 = marginal, 2 = relevant, 3 = perfect — keep it, and NDCG is the standard metric that consumes them. ## Cumulative gain Start with **cumulative gain**: just add up the grades of the top k results. CG@5 for grades [3, 2, 3, 0, 1] is 9. This already uses the grades, but it is order-blind — reversing the list gives the same 9, which is wrong, because users read from the top. ## The positional discount **Discounted cumulative gain** fixes that by dividing each gain by a function of its rank: `DCG@k = Σ_{i=1..k} rel_i / log2(i + 1)` At rank 1 the divisor is log2(2) = 1, so the first result contributes its full grade. At rank 2 it is log2(3) ≈ 1.585, at rank 8 it is log2(9) ≈ 3.17. The logarithm is a deliberate choice: it decays fast enough to model that attention concentrates at the top, but slowly enough that position 10 still counts for something. It has no derivation from user behaviour — it is a convention that has proved robust, and metrics such as rank-biased precision replace it with an explicit user-persistence model. There are two DCG numerators in common use. The classic one uses `rel_i` directly. The other uses `(2^rel_i − 1)`, which turns grades 0,1,2,3 into gains 0,1,3,7 and therefore punishes burying a top-grade document much harder. Both are called DCG; libraries differ; always say which you are using when you quote a number, because they are not comparable. ## Why normalise DCG is unbounded above and query-dependent. A head query with fifteen perfect documents can reach a much larger DCG than a tail query with a single marginal one, no matter how good the ranker is. Averaging raw DCG across a query set therefore just weights the query set by how much relevant content each query happens to have. Normalisation removes that. Sort all judged documents for the query by grade, descending, and compute the DCG of that ideal list at the same cutoff — the **ideal DCG**, IDCG@k. Then: `NDCG@k = DCG@k / IDCG@k` Every query now scores in [0, 1]: 1.0 means the system ordered things exactly as well as the judgments say is possible, and the mean NDCG@k over a query set is a fair average. ## A worked example Grades in returned order: [3, 2, 3, 0, 1, 2]. DCG = 3/1 + 2/1.585 + 3/2 + 0/2.322 + 1/2.585 + 2/2.807 = 3 + 1.262 + 1.5 + 0 + 0.387 + 0.712 ≈ 6.86. Ideal order: [3, 3, 2, 2, 1, 0]. IDCG = 3 + 3/1.585 + 2/2 + 2/2.322 + 1/2.585 + 0 ≈ 7.14. NDCG@6 ≈ 6.86 / 7.14 ≈ 0.96. The ranking is close to ideal — it merely swapped a grade-2 and a grade-3. ## Practical traps **Unjudged documents.** If a returned document has no judgment, most implementations score it as grade 0. A ranker that surfaces genuinely good but unjudged documents is therefore punished. This is the same pooling bias that afflicts recall, and it is the reason NDCG comparisons are only valid against a judgment set that covers all the systems being compared. **The IDCG denominator only knows judged documents.** If your judgment set for a query holds two relevant documents and the corpus holds fifty, NDCG can read 1.0 while the ranking is mediocre. NDCG measures ordering quality given the judgments, not coverage of the corpus — pair it with a recall metric when coverage matters. **Cutoff choice.** NDCG@10 and NDCG@3 can disagree about which of two rankers is better; the shallower cutoff is dominated by the very top, the deeper one forgives a top-of-page mistake. Report the cutoff that matches the interface. **Averaging.** Report mean NDCG with a confidence interval or a paired significance test across queries. Per-query NDCG is noisy, and a headline mean that moves by 0.002 on 50 queries is noise, not a win. **Judgment quality.** NDCG inherits every flaw of the grades feeding it. Inter-annotator agreement on a 4-point scale is imperfect, so agree on guidelines, measure agreement, and adjudicate disagreements before trusting small deltas. ## What an interviewer wants The formula including the log2(i+1) discount, why the normalisation exists, the fact that graded relevance is the whole point, and at least one of the traps — usually unjudged-as-zero or the ceiling effect from a thin judgment set.

  • What happens to NDCG when a system returns a highly relevant document that has no judgment?
    Nearly every implementation treats an unjudged document as grade 0, so it contributes nothing to DCG while occupying a high position and pushing judged documents down. The system is penalised for surfacing something good. This is pooling bias, and it is why judgment sets must be extended with the new system's top results before comparing it against systems that helped build the pool.
  • Why might NDCG@3 and NDCG@10 rank two systems in opposite orders?
    The logarithmic discount means the top three positions carry most of the weight at k=3, so a single mistake at rank 1 dominates. At k=10 that mistake is diluted and a system that fills ranks 4-10 well can overtake. Neither is wrong — they answer different questions, so pick the cutoff that matches what users actually see.
  • When is NDCG the wrong metric to headline?
    When missing documents matters more than ordering them — e-discovery, patent search, or a first-stage retriever — because NDCG is normalised against the judged set and can read high while coverage is poor. Also when judgments are binary and shallow, where MRR or precision@k say the same thing more simply and with less machinery.

saying these in an interview costs you the question

  • Thinking NDCG works on binary relevance only
  • Forgetting the normalisation and comparing raw DCG across queries
  • Believing NDCG of 1.0 means the ranking is objectively perfect
  • Treating unjudged documents as neutral rather than zero
  • Quoting an NDCG number without saying the cutoff or gain formula

context

resolving links…