Evaluating Graded Relevance

All metrics so far treat relevance as binary: a document is relevant or it is not. Average precision, for instance, gives System A’s rank-1 result (“Computer Organization and Design”) the same credit as System B’s rank-1 result (“Database Systems: The Complete Book”), because both are relevant. For the CS-foundations need, we assign three relevance grades: core foundations (grade 3), important specializations (grade 2), and useful peripheral reading (grade 1). “Database Systems” is a grade-3 core text; “Computer Organization and Design” is grade-1 peripheral reading. A metric that sees only “relevant” cannot tell these apart.

Of the 15 relevant books in the collection, 3 are graded as core foundations, 4 as important specializations, and 8 as useful peripheral reading. The complete grade distribution:

Consider the first five results from each system, now labelled with grades:

Binary AP cannot distinguish these two top-5 lists beyond counting “2 relevant at top for A, 4 for B”. Graded evaluation does more: it rewards B for placing its two highest-value books (both grade 3) in the most visible positions, while A placed a peripheral text (grade 1) at rank 1 and pushed its grade-3 titles to ranks 6, 12, and 18.

A second limitation of AP is subtler. AP rewards a system for placing any relevant document higher, but it does not penalize a system that places relevant documents in a sub-optimal order among themselves. If two relevant documents appear at ranks 3 and 5, AP does not care which of the two is more important. A graded metric can: it assigns more credit when a highly relevant document sits above a marginally relevant one.

Cumulative Gain¶

The simplest graded metric just sums the relevance grades of the documents returned up to rank $k$:

$CG_k$ measures how much total value the user has gathered after reading $k$ results. It is easy to compute but ignores order entirely: swapping a grade-3 book from rank 10 to rank 1 does not change $CG_{10}$.

Discounted Cumulative Gain¶

To make position matter, we discount contributions from lower ranks. The idea is that a user reading from the top gets diminishing benefit from each additional position: finding a grade-3 book at rank 1 is more valuable than finding the same book at rank 10, because by rank 10 the user may have already stopped reading, or the earlier results have already partially satisfied the need.

The logarithmic discount encodes a model of user patience: the benefit of each additional rank position decreases, but never reaches zero. A document at rank 10 still contributes, just less than the same document at rank 1.

Discounting with Binary Relevance¶

DCG works even when all relevance grades are binary (0 or 1). In that case, it reduces to summing the discount factors at positions where a relevant document appears. This isolates the effect of rank position from the effect of graded relevance, which helps clarify what each component contributes.

Normalized DCG¶

DCG values depend on the number of relevant documents that exist and on the magnitude of the grades, so raw DCG scores cannot be compared across different queries. A query with five grade-3 documents in the collection can produce a much higher DCG than one with two grade-1 documents, regardless of system quality.

Normalization divides the actual DCG by the best possible DCG for that query: the score achieved by an ideal ranking that places documents in descending order of their grades.

$nDCG$ always falls between 0 and 1. A value of 1 means the system produced the best possible ranking for that query at cutoff $k$. A value of 0 means no relevant document appeared in the first $k$ positions.

What nDCG Reveals That AP Does Not¶

The contrast between AP and nDCG on our running example is instructive:

AP favours System A because AP rewards finding many relevant documents (A finds 12 vs. B’s 6), and the denominator $|\text{Rel}| = 15$ heavily penalizes B’s 9 misses. The nDCG metrics tell a different story because they evaluate only the top 10 positions: within that window, B places more relevant, higher-grade material near the top.

Switching from binary to graded nDCG widens B’s lead further. Under binary evaluation, A’s rank-1 book and B’s rank-1 book both score 1.0 (both are “relevant”). Under graded evaluation, B’s grade-3 book at rank 1 scores 3.0 while A’s grade-1 book scores only 1.0. Graded relevance captures what a user experiences: not all useful results are equally useful.

Because the logarithmic discount shrinks toward zero, each additional position contributes less to the sum. Beyond a certain depth, nDCG effectively stops changing: a document at rank 50 contributes only $1/\log_2(51) \approx 0.18$ times its grade, while rank 1 contributes the full grade. For this reason, very large values of $k$ add little discriminative power between systems and are rarely used in practice. Standard cutoffs align with how far users actually read: $k = 10$ for a web search results page (the BEIR and MS MARCO benchmarks report nDCG@10), $k = 20$ for TREC Web Track, and $k = 3$ for voice assistants or mobile interfaces.

Practical Notes¶

nDCG is the standard metric in web search evaluation (where users rarely look past the first page) and in leaderboard-style benchmarks like MS MARCO and BEIR. The cutoff $k$ is chosen to match the application. The grading scale affects what nDCG rewards. Our linear scale (0, 1, 2, 3) treats the jump from grade 0 to grade 1 as equivalent to the jump from grade 2 to grade 3. An exponential gain variant replaces $rel_i$ with $2^{rel_i} - 1$, which amplifies the difference between high and low grades: a grade-3 document contributes $2^3 - 1 = 7$ while a grade-1 document contributes only $2^1 - 1 = 1$.

The exponential variant is the default in many evaluation toolkits and benchmark leaderboards. When comparing published nDCG scores, always check whether linear or exponential gain was used; the two are not comparable.