NDCG: Graded Relevance and Discount Geometry

From sets to grades

Set metrics scored a ranking against a set of relevant documents: a document is in $R_q$ or it is not. That binary judgment throws away something real. Asked for a company’s interest-rate exposure, a retriever might surface the exact hedging paragraph from a 10-K, a sentence that merely mentions rates in passing, and an off-topic disclosure. The first is perfectly on point, the second marginally so, the third irrelevant — yet precision and recall see only “relevant, relevant, not.” Graded relevance keeps the distinction: each document carries a grade $g \in \{0, 1, 2, 3\}$, from irrelevant to perfect.

To keep every number a measurement rather than an illustration, we reuse the prerequisite’s apparatus wholesale — the same shared corpus of $N = 120$ documents and $Q = 40$ queries, the same three real legs (BM25, a pooled dense dual encoder, and late interaction), and the same exact-MaxSim oracle as the neutral ground truth. The one new ingredient is the grade itself.

That last equality is deliberate: the graded judgments nest the binary ones, so this topic measures the same retrievers against the same documents the set-metric topic did — only now with a degree attached. Across the forty queries the grades come out in balanced thirds (134 at grade 3, 133 at grade 2, 133 at grade 1), so no single grade dominates the signal.

A · graded relevanceB · discount geometryC · convention flipD · NDCG as estimator

lexical (BM25)dense (MIPS)late interaction

linear gain gexponential gain 2ᵍ−1

DCG@10

11.986

IDCG@10 (ideal)

15.153

NDCG@10 = DCG/IDCG

0.7910

Each bar is a rank's contribution gain(grade)·discount(rank); their sum is DCG, the dashed outline is the ideal ordering (sum IDCG), and the shaded fraction is NDCG = 0.791. Switch to exponential gain: grade-3 jumps from 3 to 7, so a leg that plants the perfect document near the top is rewarded far more than one that spreads marginal hits.

120 synthetic finance documents, 40 queries; relevance is graded by global tertiles of the exact-MaxSim oracle score over the top-10 (so grade ≥ 1 is the binary relevant set). Numbers mirror ndcg_discount_geometry.py; the lab recomputes DCG/IDCG/NDCG, the discount curves, the mean, and the CI in closed form.

The lab above is the topic in miniature; we return to each of its four panels in turn. The arc: attach a gain to each grade and a discount to each rank, sum them into DCG, normalize by the best attainable ordering — then read the geometry of the discount, watch the conventions flip a verdict, and admit that the resulting number is still a noisy estimate.

Gain and discount: the two design choices

A hit is worth something for being relevant and something for being near the top. NDCG multiplies the two: a document of grade $g$ at rank $i$ contributes $\mathrm{gain}(g)\cdot\mathrm{discount}(i)$. Both factors are design choices, and naming them honestly is half the topic.

Neither gain nor discount is forced by any axiom — they are conventions, and the last section shows each one reversing a verdict. The logarithmic discount is the most heuristic of the lot: it is chosen for its slow, heavy-tailed decay, not derived from a model of how anyone reads a result list. The geometric discount, by contrast, comes with a story, which we take up in the discount-geometry panel.

DCG, IDCG, NDCG

With a gain and a discount fixed, the rest is bookkeeping. Let $\pi$ be the ranking, so $\pi(i)$ is the document at rank $i$, with grade $g_{\pi(i)}$.

Normalization is what makes NDCG comparable across queries: a query with six perfect documents and a query with one have very different DCG ceilings, and dividing by each query’s own IDCG puts both on $[0,1]$. Panel A shows the worked query (which has an ideal grade profile $[3,2,2,2,2,2,1,1,1,1]$): the bars are each leg’s gains in the order it ranked them, the dashed outline is the ideal, and the shaded fraction is NDCG. That a maximum over orderings is achieved by sorting is the claim the next section proves — it is not a definition we may assert by fiat.

The ideal ranking is optimal: the rearrangement inequality

Why is the normalizer the sorted ranking? Read DCG as an inner product. Fix the multiset of gains a query’s documents carry and stack them in ranked order as a vector $\mathbf{g}_\pi$; stack the discounts as $\mathbf{d} = (\mathrm{disc}(1), \mathrm{disc}(2), \dots)$, a strictly decreasing sequence. Then $\mathrm{DCG} = \langle \mathbf{g}_\pi, \mathbf{d}\rangle$, and the question “which ranking maximizes DCG” becomes “which pairing of gains with a fixed decreasing weight vector maximizes the inner product.”

This is the rigorous spine of the metric: the normalizer is not a convention but a theorem, and it is the elementary rearrangement inequality — pair large with large. The notebook checks it directly, confirming that across the corpus no random permutation of a query’s gains beats the descending order and the ascending order is strictly worst whenever the grades are not all equal.

The construction also pins the implementation. Under linear gain and the logarithmic discount, $\mathrm{NDCG@}k$ here is identical — to better than $10^{-12}$ on every leg, query, and cutoff — to the ndcg_at_k the BM25 notebook computed long before this topic existed. The dependent’s metric reduces exactly to the prerequisite’s, which is the byte-for-byte twin that anchors the code.

Discount geometry

The discount is a fixed measure on rank positions, and its shape — the topic’s namesake — decides what the metric cares about. Two readings make the geometry concrete: how much total weight sits in the head, and how steeply the value of a position falls.

Over the full $N = 120$ positions, the three discounts concentrate their weight very differently in the top ten: the geometric discount ($p = 0.85$) puts $M_{10} = 0.80$ of its mass there, the reciprocal discount $0.55$, and the logarithmic discount only $0.19$. The log discount has a heavy tail — it keeps caring about documents deep in the list — where the geometric discount is light-tailed, spending almost everything at the top. The marginal value tells the same story locally: every discount loses the most between ranks $1$ and $2$ and flattens with depth, so a demotion off the top is the most expensive move and a demotion deep down barely registers. That single factor, $\mathrm{disc}(i) - \mathrm{disc}(i+1)$, is one half of the swap sensitivity $\Delta = \Delta_{\text{gain}}\cdot\Delta_{\text{disc}}$ that pairwise learning-to-rank methods such as LambdaRank weight their gradients by — the gain side of which we will meet in a later topic.

The geometric discount earns its shape from a model the logarithmic one cannot claim.

This is the honest contrast the rigor flag insists on: rank-biased precision’s discount is a user model, with a tunable patience $p$ and a closed expectation; the logarithmic discount is picked for its heavy tail and its convenient algebra, with no such interpretation. Panel B lets you slide $p$ and watch the geometric curve sweep from steep (impatient reader, weight pinned to rank 1) to nearly flat (patient reader), against the fixed logarithmic and reciprocal curves.

NDCG as an estimator

Here the prerequisite’s central lesson carries over without a change of substance. A leg’s mean NDCG is not a property of the retriever; it is the sample mean of forty per-query NDCG values, and a different forty queries would give a different number. Under exponential gain and the log discount the three legs again form a quality ladder — lexical $0.72$, dense $0.77$, late interaction $0.88$ — but those are estimates, and estimates have standard errors.

We reuse the prerequisite’s machinery verbatim — the per-query scores are fed to the same metric_summary, and the $1/\sqrt{n}$ rate is the same concentration inequality, verified empirically by resampling. Panel D is the payoff, and it tells two stories. The clearest pair — lexical versus late interaction, a $0.16$ gap — separates by $n = 15$ queries: you can confidently report a winner. The closest pair — lexical versus dense, a mere $0.05$ gap — has intervals that overlap across all forty queries and would need roughly $185$ to separate. Below that, the honest report is “indistinguishable on this query set,” not a leaderboard delta.

Convention sensitivity and consistency

Because the gain and the discount are choices, the verdict can move with them — and we build and run the flip before stating it. On this corpus the three legs are a quality ladder under every convention, so there is no aggregate reversal; but the convention reverses the per-query verdict on five leg-pair-and-query instances, and two minimal constructed examples flip it starkly.

The mechanism is exactly the geometry above. Exponential gain steepens the grade axis, so planting the one perfect document at the top outweighs several marginal ones; a steep discount steepens the rank axis, so a single hit at rank 1 outweighs three hits just below. Choose the convention to match the task — a known-item search wants steep everything, a recall-oriented sweep wants the heavy tail — and report which you chose.