Graded Gains and the NDCG Discount

A qrels file with four levels says more than a binary one, but only if the measure reading it treats three-plus documents as better than one-plus documents and prices that difference in a way the collection can defend. Cumulative gain does this by summing a function of each document’s label, discounted by position. Normalised discounted cumulative gain divides that sum by the most that could have been obtained from the same judgments, so the result is a ratio in the unit interval.

The measure is often described as if it were one formula. It is at least three decisions stacked: what number a label is worth, how fast position erodes that number, and what the top of the scale represents. Each is separable, each has alternatives, and the choices made in one are visible in the other two.

Turning a label into a gain

The judgment set supplies ordinal labels: typically not relevant, marginally relevant, relevant, and highly relevant, encoded as integers. A gain function maps label $\ell$ to a number $g(\ell)$ before any discounting happens.

The two mappings in common use are exponential and linear. The exponential mapping is $g(\ell) = 2^{\ell} - 1$, so labels 0 through 3 become 0, 1, 3, and 7. The linear mapping is $g(\ell) = \ell$, so the same labels become 0, 1, 2, and 3.

The difference is not cosmetic. Under the exponential mapping, moving a document from level 2 to level 3 multiplies its contribution by roughly 2.3; under the linear mapping it multiplies it by 1.5. The exponential mapping therefore makes the measure markedly more sensitive to the placement of the top-graded documents, which matches a common intuition that a document that answers the need directly is worth far more than one that discusses the topic at length. That intuition is also the reason a collection that reserves its top label for documents that answer the question, rather than for degree of topical relevance, produces a measure that behaves better: the multiplicative jump then corresponds to a real qualitative difference rather than to an arbitrary rung on a scale.

What the exponential mapping cannot do is make the labels interval-scaled. Doubling a gain is not a claim that a document is twice as useful; it is a chosen weighting. Any comparison between collections that use different gain mappings is therefore a comparison between different measures, even when both are labelled NDCG at the same cutoff.

The discount and why it is logarithmic

The discount at rank $i$ is $1/\log_2(i+1)$ in the standard formulation. Rank 1 contributes at full gain, rank 2 at about 0.63, rank 5 at about 0.39, rank 10 at about 0.29, rank 100 at about 0.15. The curve flattens: the marginal cost of moving down the list is high near the top and low in the tail.

$$DCG@k = \sum_{i=1}^{k} \frac{g(\ell_i)}{\log_2(i+1)}$$

Three arguments support that shape. First, it is bounded below by zero for all ranks, so a deep list cannot produce a negative discount. Second, it compresses slower than a linear or reciprocal discount, which means the deep tail still counts for something: this is what distinguishes DCG from average precision, where a document at rank 100 contributes almost nothing. Third, it is a smooth concave function, so the measure is not dominated by a handful of positions.

The bounded-loss variant replaces the discount with $1/\log_2(i+2)$, shifting the whole curve by one rank. The change is small but the effect on normalisation is not: with the shifted version, a list of length $k$ can be compared across cutoffs more naturally, because the last position is not the point at which the discount stops changing. Different tooling uses one or the other and does not always say which, so two implementations can disagree on identical inputs while both being internally consistent.

A reciprocal discount, $1/i$, is the alternative that makes the measure match a user who reads a fixed number of results. It decays much faster than the logarithm and gives the measure the character of average precision, with most of the signal concentrated in positions 1 through 10.

Normalisation and what the ideal list means

The ideal DCG at cutoff $k$ sorts every judged document by descending gain and takes the first $k$. Dividing by it gives a number between 0 and 1 with a natural interpretation: the fraction of the obtainable gain that the system captured.

$$\mathrm{NDCG}@k = \frac{DCG@k}{IDCG@k}$$

Normalisation does not make the measure comparable across topics in the way recall is comparable across topics, though it is often described that way. A topic with many top-graded documents can afford to place several of them deep and still reach a high NDCG; a topic with one top-graded document loses a fixed fraction of its possible score for every position it delays. The ratio measures the fraction of the achievable gain at this cutoff, and that fraction behaves differently from topic to topic because the ideal list differs, even though the arithmetic is identical.

Normalisation also introduces a degeneracy at cutoff. When the judged-relevant documents number fewer than $k$, the ideal list is exhausted below $k$, so the ideal DCG at a larger cutoff is computed over a shorter list. Extending $k$ then changes both sums by different amounts, and NDCG at 100 can be lower than NDCG at 10 for the same run on the same topic. The measure is meaningful at a fixed cutoff and not monotone across cutoffs, so a report has to state the cutoff and keep it constant.

Truncation, padding, and the unjudged middle

For documents that are returned but not in the judgment set, the usual reading assigns gain zero. That treats an unjudged document as nonrelevant, which is sometimes wrong and always biased in one direction: it penalises systems whose results were not in the pool. The effect compounds with cutoff, since deeper cutoffs reach more documents that no assessor saw, and it compounds with novelty, since a system that retrieves documents no other system retrieves contributes little to the pool of documents that get judged at all.

Two mitigations are common, and both are explicit about their assumptions. The first is condensing: drop unjudged documents from the ranked list and recompute as if they had never been returned. This assumes that the unjudged gap is uninformative and treats the run as if only judged documents existed. The second is to require the collection to have judged every document that any system returned above the cutoff; this is a guarantee rather than a fix, and it requires the pool to be deep enough, which is the subject of Pooling Depth and the Unjudged Tail.

Condensing has a subtle cost: it confuses two runs that differ only in how much unjudged material they returned, and rewards a run that returned fewer documents overall. The bias is usually small at shallow cutoffs against a well-built collection and large against a shallow pool. When the pool depth is known to be low relative to the cutoff, the honest report includes the per-run fraction of unjudged documents in the top $k$, because the NDCG number alone does not reveal whether the measure had full information to work with.

Choosing a configuration and stating it

The measure family has enough free parameters that a bare number is not a specification. A complete statement includes the gain function, the discount function and base, the cutoff, the treatment of unjudged documents, and whether the ideal list was built from the same judgments used to score the run.

That last point is worth separating out. Building the ideal list from the full judgment set is correct for a collection; building it from the judgments intersected with the run’s returns is not, because it makes the denominator depend on which documents the system happened to find and can produce a score of 1.0 for a system that returned only one document, provided that document was highly graded.

With the configuration fixed, NDCG separates systems that binary measures cannot. A run that returns the best answer at rank 4 and a less complete answer at rank 1 scores below one that reverses them, and the size of the gap is proportional to the top labels’ weight in the collection. That sensitivity is the point of the measure, and it is also why the labels must be defined before the collection is built: a label scheme invented after the fact makes the gain function arbitrary.