Judging 980 more documents moved a dense retriever above BM25

A score for one ranked list of results

A retrieval system answers a query by returning a ranked list of documents, its best guess first. To grade that list you have to know which documents actually answer the query, so someone reads query-document pairs and marks each one with a relevance judgment: a label saying how well that document answers that query. The collected labels are the test collection's answer key. nDCG@10 scores the ranked list against that key, and it is the single number MTEB reports to rank retrieval systems. MTEB takes both its datasets and that metric from BEIR.¹²

A judgment can be as plain as relevant or not, or it can run over several levels of relevance. That grading is what separates nDCG from an older sibling, mean average precision, which assumes a document is either relevant or not and averages precision down the list. nDCG reads the graded label and then adds a penalty for how far down the list a good document sits. The whole measure follows from those two ideas, a grade and a position penalty, and both are simple arithmetic.

Working nDCG by hand

Start with the wrong version, because it is the one most people carry. Suppose you just count the relevant documents in the top ten. Two systems each return four relevant documents, so they tie. But one put its four at ranks 1 through 4 and the other buried them at 7 through 10, and anyone reading the results would tell the two apart at a glance. A count cannot see order. nDCG is built to see it.

The defining paper grades each result from 0, no value, to 3, high value.³ The grade a result earns is its gain: a document graded 3 is worth 3. That is the linear convention, the one the official TREC scorer uses and therefore the one behind every MTEB and BEIR number.² Then comes the position penalty, the discount: divide each gain by the logarithm of one past its rank, log2(rank + 1). At rank 1 that divisor is log2(2) = 1, so the top result keeps its full gain. At rank 3 it is log2(4) = 2, so a document there is worth half its gain. The further down a good result sits, the less it counts.

Add the discounted gains down to a cutoff and you have the discounted cumulative gain, DCG. Take a six-result list graded 3, 2, 3, 0, 1, 2. Its DCG works out to 6.861. On its own that number says nothing, because it depends on how many high grades were there to be found. So you divide by the best score the list could have reached: the DCG of the same judged documents sorted from best to worst, called the ideal DCG, or IDCG. Here the ideal order is 3, 3, 2, 2, 1, 0, and its IDCG is 7.141. The normalized score is 6.861 divided by 7.141, which is 0.961. That is nDCG: 1 is a perfect ranking, and any value below 1 is the share of the ideal the system reached.³

The cutoff is the k in nDCG@k. Stop the sum at rank 10 and you have nDCG@10, the leaderboard number, which reports how well a system ordered its first ten results and says nothing about the eleventh.²

One ranking can score 0.961 or 0.949

That 0.961 came out of two choices that could have gone another way, and a different choice gives a different number for the very same ranking. The first is the gain. The linear convention sets the gain equal to the grade. The other common convention sets it to 2^grade − 1, so the jump from a 2 to a 3 counts for far more than the jump from a 0 to a 1.⁴ That exponential form is the one major web-search companies and Kaggle competitions use, and the two agree only when relevance is binary.⁵ Run the same six-result list through it and the score is 0.949 rather than 0.961.

The second choice is the discount itself. The 2002 original divided by the logarithm of the rank in a chosen base and applied no discount until that base rank; the modern standard divides by log2(rank + 1) at every rank.³ Both go by the name "the log discount." None of this makes any number wrong. It makes a bare nDCG@10 comparable only to another one computed the same way, on the same judgments. A leaderboard score and an in-house web-search score can both be called nDCG@10 and still not belong on the same axis.

The number only counts the documents someone judged

Every score so far assumed the answer key was complete. It never is. A test collection is judged by pooling: assessors label the documents that some set of systems returned, and anything left unjudged is treated as not relevant. When a newer system surfaces a relevant document that no earlier system found, that document sits in the results unjudged and is counted as a miss. These gaps are called holes, and a system with more of them is graded against a key that is missing its own best answers.²

BEIR ran the cleanest demonstration of what that does, on its TREC-COVID dataset. Left alone, the dense retriever ANCE scored 0.654, just below the old lexical baseline BM25. Its top-ten results carried far more holes than BM25's, 14.4 percent against 6.4 percent, because it kept retrieving recent papers the original pool had never judged. BEIR had assessors judge 980 of those missing pairs and recomputed the scores. No retrieval system changed. ANCE rose to 0.735, now 6.7 points above BM25, while the lexical docT5query, which had almost no holes, barely moved, from 0.713 to 0.714. ColBERT gained 5.8 points the same way. The ranking flipped, and the only thing that changed was the labels.²

The dependence gets sharper when the key is thin. Some collections judge fewer than two relevant documents per query,² and training sets drawn from click logs often carry exactly one.⁶ Work out what nDCG@10 becomes with a single relevant document. The ideal is that one document at rank 1, so IDCG is 1. The score is then just 1 divided by log2(1 + the rank of the hit): 1.000 at rank 1, 0.631 at rank 2, 0.500 at rank 3, 0.289 at rank 10, and 0 below that. The graded scale and the discount now have nothing to work with. The metric has quietly become a measure of one thing, how high the single answer landed, wearing the same name as before.

When an offline number can move like that, a whole field can spend years chasing it. Reviewing eighteen neural recommendation models published at top venues, Ferrari Dacrema and colleagues could reproduce only seven, and six of those seven were beaten by simple, well-tuned baselines that had been around for years, measured on nDCG among other scores.⁷ The reported progress had been in the metric, not in the systems.

What nDCG still gets right

None of this makes nDCG a poor measure. Of the common ranking measures, it is the one that best matches what people actually prefer. Sanderson and colleagues showed crowd workers pairs of rankings and asked which they liked better. nDCG agreed with the crowd on 63 percent of the comparisons it could judge, 160 of 252, significantly more often than reciprocal rank at 53 percent or precision-at-ten at 50 percent.⁸ It earns its place as the default.

The same study marks the edge of that defense. nDCG's advantage leaned on the easy cases, the ones where a system returned nothing relevant at all; where both rankings returned something, agreement was weaker, and even at its best nDCG matched people only about two times in three.⁸ It is an offline stand-in for a satisfied user, and a good one, not the user.

A second result defends the number and warns about it at once. Wang and colleagues proved that the standard log-discount nDCG can still tell substantially different rankers apart on almost any dataset, even though its raw value drifts toward 1 as a collection grows, so the absolute number means little on its own.⁹ Their proof turns on the discount: choose one that decays too slowly, past a critical rate, and nDCG loses even that ability to separate rankers. The discount is not decoration. It is the part of the formula the guarantee depends on.