Ndcg At K

ndcg-at-k — Normalized Discounted Cumulative Gain at k

The dominant ranking metric for graded-relevance retrieval. Defined by Järvelin & Kekäläinen 2002, used as the headline metric in BEIR (arXiv:2104.08663) and most TREC/IR leaderboards.

When to invoke this skill

• User has (query, ranked list of doc ids, relevance grades for the gold docs) and wants the ranking score
• User says "nDCG@10", "report nDCG", "BEIR-style evaluation", "how do I score this ranker?"
• User mentions discounted gain, ideal DCG, ranking metric, graded relevance

For binary relevance + un-graded ranking, prefer mrr or recall-at-k (separate skills); nDCG works fine but has unit-relevance edge cases.

Definition

For a single query q, with ranked items d_1, …, d_n and relevance grade rel_i for the i-th item:

DCG@k(q) = sum_{i=1..k} (2^{rel_i} - 1) / log2(i + 1)         # Burges variant — paper-standard since ~2005
IDCG@k(q) = DCG@k of the best possible ranking (sort by rel desc, take top-k)
nDCG@k(q) = DCG@k(q) / IDCG@k(q)        # 0 if IDCG@k(q) == 0
nDCG@k    = mean_q nDCG@k(q)            # averaged over queries

Two conventions you must NOT mix:

• "Burges" (used by everyone since LambdaRank): gain = 2^rel - 1. Default — use this.
• "Original Järvelin": gain = rel. Only use if reproducing a paper that explicitly says so.

Reference implementation (numpy / pure python)

import numpy as np

def dcg_at_k(rels: list[float], k: int) -> float:
    """Burges-style DCG@k. rels is the relevance grades in ranked order."""
    rels = np.asarray(rels[:k], dtype=float)
    if rels.size == 0: return 0.0
    gains = (2.0 ** rels) - 1.0
    discounts = np.log2(np.arange(2, rels.size + 2))
    return float((gains / discounts).sum())

def ndcg_at_k(rels: list[float], k: int) -> float:
    """rels = relevance grades of the docs in YOUR ranking order, top-down.
    Pad shorter rankings with 0; truncate longer ones at k inside dcg_at_k."""
    ideal = sorted(rels, reverse=True)
    idcg = dcg_at_k(ideal, k)
    return dcg_at_k(rels, k) / idcg if idcg > 0 else 0.0

# Mean across queries
def mean_ndcg(rankings: dict[str, list[float]], k: int) -> float:
    return float(np.mean([ndcg_at_k(r, k) for r in rankings.values()]))

For TREC-style runs use pytrec_eval (the canonical implementation, used by BEIR):

import pytrec_eval
ev = pytrec_eval.RelevanceEvaluator(qrels, {f"ndcg_cut_{k}"})
results = ev.evaluate(run)   # run = {qid: {docid: score}}; qrels = {qid: {docid: rel}}

Input contract

• qrels: {qid: {docid: int_relevance_grade}} — gold judgements; missing docs treated as rel=0.
• run: {qid: {docid: float_score}} — your ranker's scores; the metric ranks by score desc.
• k: cutoff (typically 5, 10, 20, 100). BEIR / TREC default: 10.

Output format

Always report:

• nDCG@k to 4 decimals
• the convention (Burges vs Järvelin) — default Burges, but say so
• which queries are excluded (e.g. queries with no relevant doc in qrels are sometimes dropped, sometimes scored as 0; pytrec_eval drops them)

Edge cases (where most bugs live)

• No relevant doc for a query: IDCG = 0 ⇒ nDCG is undefined. Convention: treat as 0 OR drop the query. Pick one and document.
• Tied scores in your ranking: tie-breaking changes nDCG. Use stable sort by (score desc, docid asc) for reproducibility.
• Ranking shorter than k: just pad with rel=0 implicitly (no penalty beyond not getting the gain).
• Negative relevance grades (some TREC tracks): clamp to 0 unless paper says otherwise.
• Same docid appearing twice in your run: dedup before scoring; double-counting inflates DCG.

Don'ts

• Don't roll your own DCG without 2^rel - 1 and expect to compare against BEIR / MS MARCO numbers.
• Don't average per-query nDCG with different ks and call it "nDCG".
• Don't compute nDCG@k over the gold rels (top-k by gold) — that's IDCG, always 1.0.
• Don't include the query itself in the ranked list (some search APIs do this by default).

Citation

@article{jarvelin2002cumulated,
  title={Cumulated gain-based evaluation of {IR} techniques},
  author={J{\"a}rvelin, Kalervo and Kek{\"a}l{\"a}inen, Jaana},
  journal={ACM TOIS}, volume={20}, number={4}, year={2002}, publisher={ACM}
}