nDCG and graded relevance

Recall asks one question per document — is it relevant — and a labeller answering it needs no scale. Normalised discounted cumulative gain asks two: how relevant, and how high did it appear. That first question is a measurement only if each grade names a property a second person can check, which is why a chapter about a formula has to start with a rubric. A grade scale defined as "3 for the best answer" is not a scale; it is an invitation for two careful people to produce numbers that differ by more than any improvement you will later try to detect.

The name unpacks into the operations it performs. Gain is what a document contributes, set by its grade; discounted means that contribution is shrunk according to the position it was returned at, so a hit at rank 9 counts for a fraction of one at rank 1; cumulative means the discounted gains are summed down to a cutoff $k$; normalised means the sum is divided by the same sum over the ideal ordering of that query's judged documents, which puts the result in $[0, 1]$.

Deciding what a 3 means before anyone grades anything#

A rubric that works ties every level to a question about what the user can do with the document, and never uses a comparative word like best or most relevant.

Under that rubric a policy document is a 1 by construction, because reading it alone leaves you unable to rotate a key. A labeller who considers the policy authoritative is not wrong about authority; the rubric makes authority irrelevant to the number, which is the only way two people produce the same one.

Whether a rubric works is an empirical question, and it is cheap to answer. Give both labellers the same 30 queries, which at a pool depth of 20 with overlap comes to roughly 900 document-query pairs, and compute a linearly weighted Cohen's kappa over the grades — a measure of how far two labellers agree once the agreement they would reach by guessing has been discounted, running from 0 at chance to 1 at identical judgments. The weighting matters because a 3-versus-2 disagreement is a smaller failure than a 3-versus-0, and an unweighted kappa treats them identically. The nine hundred is thirty queries at a pool of about thirty documents each, which is the pool depth a four-system comparison produces once the systems' overlap is taken out — so the agreement check costs a seventh of the judging a full set costs, and it is done first, on the understanding that a set judged before the rubric is checked may have to be judged again.

The computation once the grades exist#

The conventional gain is exponential, $2^{g} - 1$, which spreads the grades apart: a 3 is worth 7, a 2 is worth 3, a 1 is worth 1, and a 0 contributes nothing. The conventional discount is $1 / \log_2(i + 1)$ for a document at rank $i$, so rank 1 divides by $\log_2 2 = 1$, rank 2 divides by the base-two logarithm of three — a shade under one and six tenths — and so on.

The shape of that column is the whole behaviour of the metric. It falls steeply across the first three positions and then flattens. Moving a document from rank 3 to rank 1 doubles what it is worth, since the table puts rank 3 at exactly half of rank 1. Moving the same document from rank 10 to rank 5 lifts it from 29 to 39 percent of a rank-1 slot, which is about a third more. Measured in units of rank-1 credit the first move gains half a unit and the second gains a tenth, so the top of the list is where almost all the available movement is. A logarithmic discount was chosen over something sharper because it decays slowly enough that documents deep in the list still register, and it is smooth, which matters if you ever want to optimise against it directly. It is a modelling assumption about attention rather than a measurement of it, and the fact that it does not match any particular interface's real click-through curve is a known limitation of the metric rather than a bug in your implementation.

DCG@k is the sum of gain times discount over the first $k$ returned documents. IDCG@k is the same sum computed over the ideal ordering of that query's judged documents — every relevant document sorted by grade descending, truncated at $k$. Dividing one by the other gives nDCG@k.

Take one query worked all the way through. Its judged set is api-keys/rotation at 3, sdk/auth#refreshing-keys and one platform-specific guide at 2, and two contextual documents at 1. A run returned them at ranks 2, 7, 4, 1 and 10 respectively, with irrelevant documents filling the other positions.

from math import log2

def dcg(gains):
    return sum(g / log2(i + 2) for i, g in enumerate(gains))

def ndcg_at_k(ranked_grades, all_grades, k=10):
    gain = lambda g: (2 ** g) - 1
    run = [gain(g) for g in ranked_grades[:k]]
    ideal = [gain(g) for g in sorted(all_grades, reverse=True)[:k]]
    idcg = dcg(ideal)
    return dcg(run) / idcg if idcg else 0.0

ranked = [1, 3, 0, 2, 0, 0, 2, 0, 0, 1]   # grades in returned order
judged = [3, 2, 2, 1, 1]                   # every judged-relevant doc for the query

Working the numerator by hand once makes the parts visible. Rank 1 holds a grade 1, worth $2^1 - 1 = 1$ in gain, discounted by 1.000, contributing 1.000. Rank 2 holds the grade 3, worth 7, discounted by 0.631, contributing $7 \times 0.631 = 4.417$ — 55% of the entire sum from one document. Rank 4 holds a grade 2, worth 3, discounted by 0.431, contributing 1.292. Rank 7 holds the other grade 2, worth 3, discounted by 0.333, contributing 1.0. Rank 10 holds the second grade 1, worth 1, discounted by 0.289. The six positions holding grade 0 contribute nothing, because $2^0 - 1 = 0$. Adding the five non-zero terms gives DCG@10 = 7.998.

The denominator is the same arithmetic over the best ordering those judgments permit: the 3 first, then both 2s, then both 1s. That is $7 \times 1.000 = 7$, plus $3 \times 0.631 = 1.893$, plus $3 \times 0.500 = 1.5$, plus $1 \times 0.431 = 0.431$, plus $1 \times 0.387 = 0.387$, giving IDCG@10 = 11.210. The ratio $7.998 / 11.210 = 0.713$ is the nDCG@10 for this query.

nDCG@10 = 7.998 / 11.210 = 0.713

The size of the moves available is worth calibrating against that. A run reaching DCG 9.045 on the same judged set would score $9.045 / 11.210 = 0.807$, nine points higher, and the difference between those two runs is entirely reordering inside the top few positions — no new document was found, and the set of documents in the top ten is identical.

Because the judged set did not change between those two runs, the denominator did not either, which makes the exchange rate readable. Roughly one unit of DCG bought nine points of nDCG on this query, and one unit of DCG is what a single grade-2 document is worth at the top of the list. The same conversion sizes the downside: the grade-3 document at rank 2 is carrying 4.417, and letting it slide to rank 10 would cut that to a little over two, costing more than twenty points of nDCG from one document moving. A metric where one document's position can move the query score by a fifth of the scale is a metric that needs its judgments to be right about that document.

Recall@10 on the same query is the count of judged-relevant documents appearing anywhere in the top ten divided by the count that exist: five out of five, so 1.0. It reads the same ranking as a set and throws the order away.

Now regrade one document and leave everything else alone, because this is where the two metrics separate. Suppose a second labeller reads the contextual policy document at rank 1 as the authoritative answer and grades it 3, and demotes the procedure at rank 2 to a 2. No document has changed position, no document has moved in or out of the top ten, and every document graded above zero by the first labeller is still graded above zero. Recall@10 is five out of five, exactly as before. The nDCG numerator, though, now leads with a 7 at rank 1 instead of a 1 there and a 7 at rank 2, so it rises to a shade under eleven and a half; the ideal ordering now holds a 3 and three 2s, so the denominator rises to a shade over twelve. The ratio is 0.951 against the 0.713 above — a swing of nearly a quarter of the scale, produced by one document's grade, with the ranking untouched.

That is the sentence to carry out of this chapter. Recall is invariant to everything the two labellers disagreed about, so a team checking their agreement by comparing recall figures would find perfect agreement and conclude the rubric was sound. A check whose result is identical whether the thing it is testing is present or absent cannot be used to test for it. The instrument that detects a grading disagreement is the one that reads grades, which means the rubric has to be validated against a metric that is sensitive to it, and kappa on the grades themselves is the direct version of that.

Where implementations quietly disagree#

Two evaluation libraries fed identical rankings and identical judgments will return different nDCG numbers, and the differences are large enough to matter. The choices are all defensible and none of them is standard enough to assume.

The direction of each of those effects can be reasoned out rather than looked up, which is worth doing because it tells you which way a library's silence is biasing you. Linear gains make a 3 worth three and a 2 worth two, where exponential gains make them seven and three; the top grade's dominance shrinks, so a run that found the best document but ranked it imperfectly is treated more kindly, and the whole scale compresses toward the middle. Computing the ideal ordering from only the documents the run returned removes every missed document from the denominator, so a run that returned one relevant document and nothing else divides its gain by its own gain and scores a perfect one. Dropping unjudged documents rather than grading them zero shortens the list, which promotes everything beneath them into cheaper positions and can only raise the score. Sorting tied documents by grade lets the run be credited with an ordering it did not produce. Three of the four choices move the number upward, and none of them moves it upward for a reason that has anything to do with retrieval — which is why the row that matters most is the one whose optimistic variant can reach 1.0.

The second row is the one that causes arguments six months later, and it is the subject of the next chapter. For the formulas themselves stated cleanly, Evaluation Metrics for Search and Recommendation Systems on the Weaviate blog is a compact reference worth keeping open while you write your first implementation. Whatever you choose, the choice belongs in the same file as the numbers, because a comparison between a run scored with exponential gains and one scored with linear gains is not a comparison.

Dividing by IDCG removes one source of incomparability across queries: a query with six relevant documents no longer scores higher than a query with one simply because there was more gain available. It does not make nDCG comparable across query sets, across corpora, or across projects. A team reporting nDCG@10 of 0.83 and a team reporting 0.71 may be describing the same retrieval quality over golden sets of different difficulty and different judgment depth, and there is no transformation that reconciles them. It is also not a probability, not a percentage of queries answered, and not something a product manager can interpret without a reference point. Nobody outside the team knows whether 0.71 is good, and the honest answer is that it is only good or bad relative to the run it replaced.

The sharpest limitation is structural. nDCG@10 is computed over ten positions, and a relevant document at rank 11 contributes exactly as much as a relevant document that does not exist anywhere in the corpus: nothing. A metric built to reward ordering has no way to distinguish a run that ordered badly from a run that never had the document to order.

The truncation cuts the denominator as well as the numerator, and that second cut is the one that surprises people. The ideal ordering is also taken only to $k$, so a query with fifteen relevant documents and a cutoff of ten has an ideal built from its ten best. A run that returns those ten in the right order scores exactly 1.0 while missing five relevant documents, and the metric is correct to do so — no ranking of ten slots could have done better. What that means in practice is that a perfect nDCG@10 is a statement about the ordering of ten positions and never a statement about coverage of the corpus, and on a query set where the relevant sets are larger than the cutoff, it is a ceiling several systems will reach for reasons that do not distinguish them.

Everything after the rubric is arithmetic — a gain per grade, a discount per position, a sum, and a division by the best sum the judgments allow — and it is arithmetic you can do by hand for one query in about a minute, which is worth doing once so that the metric stops being a fact to memorise. What is not arithmetic is the input, where a one-document disagreement between two reasonable labellers moved this metric by 0.238.

So the order of work is the reverse of how the metric is usually introduced: write the rubric, measure agreement on thirty queries, and only then report numbers. The distinction the last section names — between a run that ordered badly and a run that never had the document — is what the next chapter is for, and it is the reason nDCG is never reported alone.