1 Definition and Intuition

nDCG (normalized Discounted Cumulative Gain) is an evaluation measure for ranking tasks in information retrieval (IR) and recommender systems. It assigns credit to an ordered list of items based on how relevant each position is, while also reducing the contribution of items placed lower in the list.

1.1 Relevance and Graded Judgments

Unlike binary relevance (relevant vs. not relevant), graded relevance assigns multiple levels (e.g., 0–3) to reflect varying degrees of usefulness. These levels can come from human judgments, implicit feedback, or calibrated relevance models. nDCG leverages these graded labels so that an ordering that places highly relevant items earlier is rewarded more than one that mixes levels less effectively.

1.2 Discounting by Rank Position

nDCG uses a discounting scheme so that the same relevance level yields less gain when it appears at deeper ranks. This reflects a common user behavior pattern: users typically examine only the first part of a results list and often stop early. As a result, nDCG is designed to penalize ranking mistakes more heavily near the top.

1.3 Normalization Against an Ideal Ranking

nDCG compares the observed ranking’s discounted gain (DCG) to the discounted gain of an ideal ordering (IDCG). This normalization produces a score that is easier to interpret across different queries or datasets because it accounts for how much graded relevance is available in the judged set.

2 Core Formulae

nDCG is built from DCG and an idealized variant, IDCG, followed by normalization.

2.1 Discounted Cumulative Gain (DCG)

DCG aggregates position-wise gains from the ranked list. A standard form uses a cumulative sum over ranks with a discount factor dependent on the rank position.

2.1.1 Gain Functions for Graded Relevance

Let the relevance label at rank position \(i\) be \(rel_i\). A gain function maps this label to a nonnegative numeric contribution. Common choices include using the label directly (identity gain) or using a monotonic transform such as \(2^{rel_i}-1\), which amplifies higher relevance levels more strongly.

2.1.2 Rank-Based Discounting (e.g., log-based)

A typical discount divides the gain by a function of the rank index, most commonly a logarithm: \[ \text{DCG}=\sum_{i=1}^{n}\frac{\text{Gain}(rel_i)}{\log_b(i+1)} \] where \(b\) is the log base (often 2) and \(n\) is the number of considered ranks. Alternative discount shapes exist, but the essential property is decreasing weight with increasing rank.

2.2 Ideal DCG (IDCG)

IDCG is the DCG of the best possible ordering under the given graded labels. It is computed by sorting items by decreasing relevance (or by the highest achievable ordering according to the available judgments) and then applying the same DCG computation.

2.2.1 Constructing the Ideal Ranking

To construct the ideal ranking, the evaluation framework orders documents/items by their relevance labels. If relevance labels include ties, the ideal ordering is determined by any tie-breaking consistent with the grading; the resulting IDCG is typically computed once per query using the sorted label sequence.

2.3 Normalized DCG (nDCG)

nDCG is the ratio of DCG to IDCG: \[ \text{nDCG}=\frac{\text{DCG}}{\text{IDCG}} \] When IDCG is nonzero, this yields a normalized score that reflects how close the produced ranking is to the ideal one under the same gain and discount rules.

2.3.1 Interpreting the Bounded Score

With typical monotonic gains and positive discount factors, nDCG is bounded between 0 and 1: 1 corresponds to the ideal ranking, while lower values indicate poorer placement of relevant items. The upper bound can be sensitive to implementation details (e.g., whether gain is defined to be strictly nonnegative), but the common practical behavior is a normalized score suitable for comparison.

3 Variants and Implementation Choices

Several design choices influence what nDCG measures and how scores are computed in practice.

3.1 Truncation at K (nDCG@K)

Many systems report nDCG@K, where the metric sums only the top \(K\) positions.

3.1.1 Choosing K for Evaluation

The choice of \(K\) aligns with user behavior and system requirements. Small \(K\) focuses the evaluation on the first screen of results, while larger \(K\) measures performance deeper in the list. Different applications—search, ranking in feeds, or recommendation—often select different \(K\) to match interaction patterns.

3.2 Base of the Logarithm and Discount Schemes

The log base and the exact functional form of the discount can vary across toolkits and papers. A common default uses \(\log_2(i+1)\), but other bases or alternative decays (e.g., linear or other sublinear functions) can shift relative emphasis across ranks.

3.3 Alternative Gain Exponents

When using transforms like \(2^{rel_i}-1\), the metric emphasizes differences between high relevance levels more than between low ones. Using identity gain instead yields a more linear interpretation of label values. Selecting a gain mapping changes how strongly the evaluator distinguishes among grading levels.

3.4 Handling Missing or Incomplete Relevance Judgments

In many datasets, judgments are incomplete for long-tail items or deeper ranks. Evaluation protocols may treat missing labels as nonrelevant, exclude them, or use pooling-based judgment strategies. Each approach affects bias: assuming missing equals zero can penalize unknown items, while exclusion can inflate scores by ignoring uncertain regions.

4 Practical Usage in Information Retrieval

nDCG is widely used because it captures both ranking quality and graded relevance in a single measure.

4.1 Offline Evaluation of Rankers

Offline evaluation compares different ranking models using held-out labeled data. For each query, the ranked output is scored with nDCG (often averaged across queries), producing a metric for model selection and benchmarking without requiring live user experiments.

4.2 Comparing Models Across Queries

Because different queries can have different relevance distributions, nDCG’s normalization helps make aggregated comparisons meaningful.

4.2.1 Aggregation: Mean nDCG and Weighting

A common aggregation is the mean over queries: \[ \text{Mean nDCG}=\frac{1}{Q}\sum_{q=1}^{Q}\text{nDCG}(q) \] Some evaluations apply weighting to queries based on importance, frequency, or judgment reliability. The choice of aggregation can influence which models appear better, particularly when query difficulty varies.

4.3 Sensitivity to Ranking Errors Near the Top

Because discounting reduces the influence of lower ranks, swapping a relevant item into a higher position typically produces a larger score change than moving it deeper by the same number of steps. This makes nDCG well suited for optimizing user-visible quality rather than merely total relevant coverage.

5 Worked Examples

Worked examples illustrate how nDCG combines gains and discounts, then normalizes.

5.1 Simple Ideal vs. Non-Ideal Rankings

Consider a single query with five judged items. Suppose the true relevance labels, when sorted ideally, are: \[ [3,2,1,0,0] \] An evaluated ranking might instead be: \[ [2,3,0,1,0] \] The two sequences have the same multiset of relevance labels but differ in where high-grade items appear.

5.2 Step-by-Step DCG Computation

Assume a log-based discount with \(\log_2(i+1)\) and identity gain (gain = relevance label). For the evaluated ranking, compute position-wise terms:

  • Rank 1 (\(i=1\)): gain \(=2\), discount \(=\log_2(2)=1\) → contribution \(=2/1=2\)
  • Rank 2 (\(i=2\)): gain \(=3\), discount \(=\log_2(3)\approx 1.585\) → contribution \(\approx 3/1.585\approx 1.893\)
  • Rank 3 (\(i=3\)): gain \(=0\), contribution \(=0\)
  • Rank 4 (\(i=4\)): gain \(=1\), discount \(=\log_2(5)\approx 2.322\) → contribution \(\approx 1/2.322\approx 0.431\)
  • Rank 5 (\(i=5\)): gain \(=0\), contribution \(=0\)

Summing yields: \[ \text{DCG}\approx 2+1.893+0+0.431+0=4.324 \]

Now compute IDCG using the ideal ordering \([3,2,1,0,0]\):

  • Rank 1: \(3/\log_2(2)=3\)
  • Rank 2: \(2/\log_2(3)\approx 2/1.585\approx 1.262\)
  • Rank 3: \(1/\log_2(4)=1/2=0.5\)
  • Rank 4: \(0\)
  • Rank 5: \(0\)

So: \[ \text{IDCG}\approx 3+1.262+0.5=4.762 \]

5.3 Step-by-Step nDCG Normalization

Finally: \[ \text{nDCG}=\frac{\text{DCG}}{\text{IDCG}}\approx \frac{4.324}{4.762}\approx 0.908 \] This value indicates that the evaluated ranking is close to ideal but not perfect due to suboptimal placement of the highest-graded item.

6 Relationship to Other IR Metrics

nDCG is one metric among several. Its relationship to precision, recall, and rank-based metrics helps decide when it is appropriate.

6.1 nDCG vs. Precision@K and Recall@K

Precision@K counts how many of the top \(K\) results are relevant (often under binary relevance). Recall@K measures how much of the relevant set appears within the top \(K\). Both can ignore graded differences; a method that retrieves moderately relevant items may appear strong under binary precision, even if it fails to rank the highest-grade items near the top. nDCG uses ranking position and graded relevance together.

6.2 nDCG vs. MAP

Mean Average Precision (MAP) evaluates the area under the precision-recall curve per query using binary relevance and considers precision at each relevant hit. MAP is sensitive to the ordering of relevant documents but does not inherently model graded relevance. In tasks where relevance levels carry meaning, nDCG often provides a more faithful picture.

6.3 nDCG vs. MRR

Mean Reciprocal Rank (MRR) focuses on the rank position of the first relevant result, again usually under binary relevance. This makes MRR highly sensitive to whether at least one good item appears early, but it does not reward having multiple highly relevant items near the top. nDCG typically offers a smoother evaluation across many graded positions.

6.4 When to Prefer nDCG

nDCG is often preferred when:

  • relevance judgments are graded rather than binary,
  • ranking position matters substantially (e.g., top-of-list experiences),
  • different relevance levels should influence scoring differently,
  • comparisons across queries require normalization.

7 Limitations and Common Pitfalls

Despite its usefulness, nDCG can mislead if used without attention to its assumptions and data conditions.

7.1 Effects of Relevance Scale or Grading Noise

Because nDCG depends on label values, noisy or inconsistent grading can distort outcomes. If relevance scales differ across annotators or sources, models may be evaluated unfairly. Large label gaps also increase the impact of gain transforms that strongly amplify high grades.

7.2 Dependency on Ideal Ranking Construction

IDCG requires an “ideal” ordering derived from the judged labels. If the relevance set is incomplete, the constructed ideal can be inaccurate—normalization then reflects an ideal that is only ideal within the judged subset. This can change the perceived quality of different systems.

7.3 Misleading Scores Under Certain Label Distributions

When there is little variation in relevance labels (e.g., most labels are zero or identical), nDCG can become insensitive to meaningful ranking differences. Conversely, when only a single highly relevant item exists per query, nDCG may behave similarly to metrics focused on early retrieval, placing disproportionate weight on the position of that one item.

7.4 Interpreting Large Differences in Practice

A large nDCG gap does not automatically imply a large user-impact difference because:

  • grading levels may not map linearly to user satisfaction,
  • the discount and gain choices affect magnitude,
  • query difficulty and label coverage vary.

Therefore, differences should be interpreted alongside dataset properties, validation consistency, and ideally additional analysis.

8 Computational Considerations

Efficient computation matters when evaluating many queries and models.

8.1 Efficient DCG Computation

DCG for each query is computed by iterating through the ranked list and summing discounted gains. Efficiency can be improved by precomputing discount denominators for each rank position up to the maximum \(K\), and by using vectorized operations in numerical libraries. Since nDCG is often evaluated at multiple cutoffs, caching intermediate prefix sums can reduce repeated work.

8.2 Data Structures for Ranked Lists

Ranked results are typically represented as arrays of item identifiers with associated relevance labels fetched from a lookup table. For large candidate sets, implementations may avoid materializing full relevance vectors by scoring only top \(K\) items, or by using sparse representations when only judged items have nonzero relevance.

8.3 Batch Evaluation Workflows

In batch evaluation, systems process many queries in parallel. Common strategies include:

  • grouping by query length or maximum cutoff,
  • aligning relevance label lookups to memory layouts for speed,
  • computing DCG and IDCG using shared precomputed discounts.

These optimizations are crucial when offline evaluation is part of iterative model training and selection.

9 nDCG in Learning-to-Rank Contexts

In learning-to-rank pipelines, nDCG is frequently used as an evaluation metric and sometimes as an optimization target.

9.1 Using nDCG for Offline Model Selection

Training can produce candidate models that are evaluated offline with nDCG@K. The best-performing model on validation queries (according to mean nDCG) is selected for deployment or further training. This aligns model selection directly with the evaluation criterion used to judge user-facing ranking quality.

9.2 Connection to Ranker Objectives

Some learning-to-rank approaches aim to produce score orderings that improve nDCG. While many algorithms optimize surrogate losses (e.g., listwise, pairwise, or pointwise objectives), they are often designed to correlate with ranking metrics, including nDCG, under the given relevance labels and sampling strategy.

9.3 Approximation Strategies in Training (High-Level)

Directly optimizing nDCG can be challenging because it depends on discrete ranking positions. High-level strategies commonly involve approximating the effects of sorting with differentiable or smooth surrogates, or using weighting schemes inspired by the DCG formula to guide learning. These approaches seek to capture the top-of-list emphasis and graded relevance sensitivity that nDCG embodies, while remaining trainable with gradient-based methods.