# A Theoretical Analysis of NDCG Type Ranking Measures

arXiv: https://arxiv.org/abs/1304.6480 · HTML: https://mlsanity.com/paper/1304.6480/

## Key facts

- Cited by 119 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2013.

## Built on by (most cited first, 30 of 119)

- [LiPO: Listwise Preference Optimization through Learning-to-Rank](https://mlsanity.com/paper/2402.01878/) (2024)
- [Blended RAG: Improving RAG (Retriever-Augmented Generation) Accuracy with Semantic Search and Hybrid Query-Based Retrievers](https://mlsanity.com/paper/2404.07220/) (2024)
- [A Survey of Personalized Large Language Models: Progress and Future Directions](https://mlsanity.com/paper/2502.11528/) (2025)
- [Building and Evaluating Open-Domain Dialogue Corpora with Clarifying Questions](https://mlsanity.com/paper/2109.05794/) (2021)
- [CoIR: A Comprehensive Benchmark for Code Information Retrieval Models](https://mlsanity.com/paper/2407.02883/) (2024)
- [When Search Engine Services meet Large Language Models: Visions and Challenges](https://mlsanity.com/paper/2407.00128/) (2024)
- [ELIXR: Towards a general purpose X-ray artificial intelligence system through alignment of large language models and radiology vision encoders](https://mlsanity.com/paper/2308.01317/) (2023)
- [eCeLLM: Generalizing Large Language Models for E-commerce from Large-scale, High-quality Instruction Data](https://mlsanity.com/paper/2402.08831/) (2024)
- [Multi-Vector Models with Textual Guidance for Fine-Grained Scientific Document Similarity](https://mlsanity.com/paper/2111.08366/) (2021)
- [CodeXEmbed: A Generalist Embedding Model Family for Multiligual and Multi-task Code Retrieval](https://mlsanity.com/paper/2411.12644/) (2024)
- [Scalable Ranked Preference Optimization for Text-to-Image Generation](https://mlsanity.com/paper/2410.18013/) (2024)
- [Region-Adaptive Sampling for Diffusion Transformers](https://mlsanity.com/paper/2502.10389/) (2025)
- [Toward Generalizable Evaluation in the LLM Era: A Survey Beyond Benchmarks](https://mlsanity.com/paper/2504.18838/) (2025)
- [Unsupervised Model Selection for Time-series Anomaly Detection](https://mlsanity.com/paper/2210.01078/) (2022)
- [LLM-Enhanced User-Item Interactions: Leveraging Edge Information for Optimized Recommendations](https://mlsanity.com/paper/2402.09617/) (2024)
- [BookGPT: A General Framework for Book Recommendation Empowered by Large Language Model](https://mlsanity.com/paper/2305.15673/) (2023)
- [Benchmarking and Building Long-Context Retrieval Models with LoCo and M2-BERT](https://mlsanity.com/paper/2402.07440/) (2024)
- [CSFCube -- A Test Collection of Computer Science Research Articles for Faceted Query by Example](https://mlsanity.com/paper/2103.12906/) (2021)
- [Boosting Search Engines with Interactive Agents](https://mlsanity.com/paper/2109.00527/) (2021)
- [C-FedRAG: A Confidential Federated Retrieval-Augmented Generation System](https://mlsanity.com/paper/2412.13163/) (2024)
- [Rethinking Knowledge Graph Evaluation Under the Open-World Assumption](https://mlsanity.com/paper/2209.08858/) (2022)
- [Optimal Design for Human Preference Elicitation](https://mlsanity.com/paper/2404.13895/) (2024)
- [MemoryCD: Benchmarking Long-Context User Memory of LLM Agents for Lifelong Cross-Domain Personalization](https://mlsanity.com/paper/2603.25973/) (2026)
- [Tool-integrated Reinforcement Learning for Repo Deep Search](https://mlsanity.com/paper/2508.03012/) (2025)
- [A Survey on Fairness-aware Recommender Systems](https://mlsanity.com/paper/2306.00403/) (2023)
- [Unsupervised Contrast-Consistent Ranking with Language Models](https://mlsanity.com/paper/2309.06991/) (2023)
- [AdvisorQA: Towards Helpful and Harmless Advice-seeking Question Answering with Collective Intelligence](https://mlsanity.com/paper/2404.11826/) (2024)
- [Human-inspired Perspectives: A Survey on AI Long-term Memory](https://mlsanity.com/paper/2411.00489/) (2024)
- [One Billion Audio Sounds from GPU-enabled Modular Synthesis](https://mlsanity.com/paper/2104.12922/) (2021)
- [CoSQA+: Pioneering the Multi-Choice Code Search Benchmark with Test-Driven Agents](https://mlsanity.com/paper/2406.11589/) (2024)

## Abstract (arXiv)

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.