A Theoretical Analysis of NDCG Type Ranking Measures

By Yining Wang, Liwei Wang, Yuanzhi Li, Di He, Tie-Yan Liu. 2013

539 citations recorded by the source corpus.

A central problem in ranking is to design a ranking measure for evaluation of ranking functions. In this paper we study, from a theoretical perspective, the widely used Normalized Discounted Cumulative Gain (NDCG)-type ranking measures. Although there are extensive empirical studies of NDCG, little is known about its theoretical properties. We first show that, whatever the ranking function is, the standard NDCG which adopts a logarithmic discount, converges to 1 as the number of items to rank goes to infinity. On the first sight, this result is very surprising. It seems to imply that NDCG cannot differentiate good and bad ranking functions, contradicting to the empirical success of NDCG in many applications. In order to have a deeper understanding of ranking measures in general, we propose a notion referred to as consistent distinguishability. This notion captures the intuition that a ranking measure should have such a property: For every pair of substantially different ranking functions, the ranking measure can decide which one is better in a consistent manner on almost all datasets. We show that NDCG with logarithmic discount has consistent distinguishability although it converges to the same limit for all ranking functions. We next characterize the set of all feasible discount functions for NDCG according to the concept of consistent distinguishability. Specifically we show that whether NDCG has consistent distinguishability depends on how fast the discount decays, and 1/r is a critical point. We then turn to the cut-off version of NDCG, i.e., NDCG@k. We analyze the distinguishability of NDCG@k for various choices of k and the discount functions. Experimental results on real Web search datasets agree well with the theory.

Subfields: Information Systems, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Systems

1. Xing Xie
2. Fuzheng Zhang
3. Manik Varma
4. Yashoteja Prabhu
5. Xiaobo Shen
6. Dacheng Tao
7. Chang Xu
8. Zhengran Zeng

In Signal Processing

1. Yu Zheng
2. Yining Wang
3. Dacheng Tao
4. Nicholas Jing Yuan
5. Xing Xie
6. Chang Xu
7. Manik Varma
8. Guandong Xu

Citations in the corpus

• DRN: A Deep Reinforcement Learning Framework for News Recommendation (2018, methodology): “We apply the standard Normalized Discounted Cumulative Gain proved in [46] as Equation 11, where r is the rank of items in the recommendation list, n is the length of the recommendation list, f is the ranking function or algorithm, y r is the 1 or 0 indicating whether a click happens and D(r ) is th”
• Boosting Search Engines with Interactive Agents (2021, neutral): “NDCG is a popular metric in IR as it accounts for rank position, it is comparable across queries, and it is effective at discriminating ranking functions (Wang et al., 2013).”
• Iterative Context-Aware Graph Inference for Visual Dialog (2020, unknown): “A new metric NDCG (Normalized Discounted Cumulative Gain) [33] is proposed to evaluate quantitative semantics, which penalizes low ranking correct answers.”
• Image-Question-Answer Synergistic Network for Visual Dialog (2019, background): “0 by four people to allow application for the more robust evaluation metric NDCG [27] rather than traditional retrieval metrics, such as mean rank, R@1,5,10, and MRR.”
• TranS^3: A Transformer-based Framework for Unifying Code Summarization and Code Search (2020, methodology): “Œe performance of code search is evaluated in terms of four widely-used metrics: MRR (Mean Reciprocal Rank) [52], nDCG (normalized Discounted Cumulative Gain) [53] and Success Rate@k [54], where MRR measures the average reciprocal ranks of results given a set of queries and the reciprocal rank of a ”
• The Emerging Trends of Multi-Label Learning (2020, background): “Thus, FastXML [10] presents to learn the hierarchy by optimizing the ranking loss function, normalized Discounted Cumulative Gain (nDCG) [72].”
• Direct Learning to Rank and Rerank (2018, background): “Ties are usually addressed by fixing them, or assigning the tied observations a (possibly fractional) rank that is the average (e.g., tied observations would get ranks 7.5 rather than 7 and 8) (see Tamhane and Dunlop, 2000; Wackerly et al, 2002).”
• FastXML: a fast, accurate and stable tree-classifier for extreme multi-label learning (2014, methodology): “In particular, it optimizes the normalized Discounted Cumulative Gain (nDCG) [33].”
• SkMTEB: Slovak Massive Text Embedding Benchmark and Model Adaptation (2026, unknown): “The standard metrics include nDCG@k (primarily nDCG@10) (Wang et al., 2013), MRR@k, MAP@k, precision@k, and recall@k.”
• Why Large Language Models can Secretly Outperform Embedding Similarity in Information Retrieval (2026, unknown): “NDCG is defined as: , where I is the ideal ranking and h ( d i ) is the relevance of document d at position i in the ranking.”
• Benchmarking and Building Long-Context Retrieval Models with LoCo and M2-BERT (2024, methodology): “…We perform a more detailed analysis of the M2-BERT retriever’s ability to encode long contexts and capture relevant information, despite surrounding irrelevant context, by using a synthetic modeled off “needle-in-the-haystack” tasks that have been used in other studies of longer context tasks [29].”
• CodeXEmbed: A Generalist Embedding Model Family for Multiligual and Multi-task Code Retrieval (2024, unknown): “Building on prior work (Wang et al., 2013), Normalized Discounted Cumulative Gain (NDCG) is preferred for its abil-1 ity to account for both rank order and varying relevance, unlike precision, recall or MRR.”