Ndcg At K

---
name: ndcg-at-k
description: Compute normalized Discounted Cumulative Gain at cutoff k (nDCG@k) — the standard ranking metric for retrieval / recommendation / search evaluation when relevance is graded. Use when the user has a list of (query, ranked_doc_ids, relevance_judgements) and wants to score the ranking quality, or mentions "nDCG / NDCG / DCG / ranking metric / IR metric / BEIR-style eval". Returns a number in [0, 1]; higher = better ranking.
metadata:
  source_paper: Järvelin & Kekäläinen 2002, "Cumulated gain-based evaluation of IR techniques" (TOIS)
  task_type: ranking-metric
  metrics: [nDCG@k]
  use_cases: [BEIR, MS MARCO, TREC, recsys leaderboards]
---

# 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)

```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):
```python
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 `k`s 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

```bibtex
@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}
}
```