Dense Passage Retrieval

The dense passage retriever of Karpukhin and colleagues in full, with its two encoders, training data, negatives and reported results, followed by an experiment of our own. A pretrained bi-encoder with exhaustive search is run against BM25 on Cranfield and against BM25F on this site's 11,264 passages, with paired tests. On Cranfield the dense retriever matches BM25 at ten results and finds more at one hundred; on the site the judged queries cannot settle the comparison, because only the lexical ranker's own top 20 results were ever judged, and the known-item queries favor BM25F. Fusing the two lists beats either on Cranfield; on the site the judgments in hand cannot show whether it helps. Five worked problems cover index size, nDCG by hand, top-k accuracy against recall, best-passage scoring and the paired t-test.

One of this site's 60 judged test queries (T09 in the evaluation set) asks, in everyday words, whether a model can tell when it lacks an answer. The site's search engine, a BM25F ranker over terms, puts a page of interpretability notes first, which the judges graded not relevant, and puts a reading note on calibration, graded fully relevant, 14th. The trouble is in the words: the query is phrased the way a person would ask it, and the best page talks about calibration and about predicting whether an answer will be correct. A second query (T26) goes the other way. It asks for notes on an AI system operating a retail enterprise, and BM25F puts the two notes on such an experiment first and second, since their titles and text use the query's own words. Can a retriever that compares meanings and not terms fix the first query without breaking the second? On this evidence, partly: a dense retriever puts the calibration note first for the first query, and for the second it ranks those two notes 9th and 84th.

Dense retrieval is first-stage retrieval by nearest vectors. A bi-encoder turns every passage of the collection into a vector ahead of time, turns the query into a vector when it arrives, and returns the passages whose vectors score highest against the query's. The dense passage retriever, DPR, of Karpukhin et al. (2020) is the system that established the approach: it showed that a bi-encoder trained on question-passage pairs alone could beat BM25 at finding answer-bearing passages in Wikipedia.

Here is the route. First we set out the task DPR was built for and how its success is measured. Then we describe the system in full, its encoders, its passages, its training data and its negatives, and report its results from the paper's tables. Then we run a dense retriever ourselves, on Cranfield against BM25 and on this site's passages against BM25F, and test the differences with the paired tests of the course's article on significance. The article assumes Sentence and Passage Encoders for the bi-encoder and Contrastive Training for Retrieval for the loss. The numbers are computed by tools/experiments/dense/dense-passage-retrieval.py.

The task: finding passages that contain an answer

DPR was built for open-domain question answering: answering a factual question, such as the paper's example "Who first voiced Meg on Family Guy?", from a large collection with no indication of where the answer lies. The systems of the time worked in two stages (Karpukhin et al., 2020, §1). A retriever selected a small set of passages, and a reader, a model that reads the question and a passage together, extracted the answer span from them. The reader can only find an answer that the retriever has delivered, so the retriever sets a ceiling on the whole system.

That purpose fixes the measure. The paper evaluates a retriever by top-$k$ retrieval accuracy: the fraction of questions for which at least one of the $k$ passages returned contains a span that answers the question (their §2). It is a success-at-$k$ measure, not recall: one answer-bearing passage is enough, and how many others exist does not matter. Worked problem 3 sets it beside recall on a Cranfield query.

The retriever in such systems was usually TF-IDF or BM25. The paper's introduction states the reason a dense retriever might do better with its own example. The question "Who is the bad guy in lord of the rings?" is answered by a passage that says "Sala Baker is best known for portraying the villain Sauron in the Lord of the Rings trilogy." A term-matching system has little to connect "bad guy" with "villain". This is the vocabulary mismatch that query expansion attacks from the query's side and that the vector space model's limits trace to the independence of terms.

An earlier system, ORQA (Lee, Chang and Toutanova, 2019), had already shown a dense retriever beating BM25 on open-domain question answering, after an additional pretraining stage designed for the purpose, the inverse cloze task, in which a sentence serves as a pseudo-question and its surrounding passage as the evidence to find. Its own abstract states the result with a condition: on datasets whose questioners already knew the answer BM25 was sufficient, and where the questioner was genuinely seeking an answer its learned retrieval outperformed BM25 by up to 19 points of exact-match accuracy. The question Karpukhin et al. put was whether that stage was needed: "can we train a better dense embedding model using only pairs of questions and passages (or answers), without additional pretraining?" Their answer was yes.

The system

Two encoders and a dot product

DPR has a passage encoder $E_P$ and a separate question encoder $E_Q$. Each is a BERT network (the base, uncased model), and each takes the vector at the [CLS] token as its output, so the embeddings have $m = 768$ dimensions (their $d$; their §3.1). The score of a passage $p$ for a question $q$ is the dot product of the two embeddings,

$$s(q, p) = E_Q(q) \cdot E_P(p) ,$$

their equation (1). The vectors are not normalized.

The paper gives the reason for so plain a score: it has to be decomposable, a function of two separately computed representations, "so that the representations of the collection of passages can be precomputed". A model in which question and passage attend to each other is more expressive, and DPR uses one, as its reader, but only on the few passages the retriever returns. With a dot product, retrieval is maximum inner product search over stored vectors.

Two encoders differ from the single shared encoder of the previous articles in one respect: a question and a passage are different kinds of text, and separate weights let each side specialize. The score is then no longer symmetric in its two arguments, which is harmless, since a question is never retrieved by a passage.

Passages

The collection is the English Wikipedia dump of 20 December 2018. Each article's text is cut into disjoint blocks of 100 words, which gives 21,015,324 passages, and each passage is prefixed with the title of its article and a [SEP] token (their §4.1). The paper reports having tried natural paragraphs and overlapping blocks and found neither better.

The passage vectors are computed once and indexed with FAISS, a library for similarity search over dense vectors (Johnson, Douze and Jégou, 2021). The size of what has to be stored follows from the counts. At four bytes per number, the vectors alone take

$$21{,}015{,}324 \times 768 \times 4 = 64{,}559{,}075{,}328 \text{ bytes},$$

about 64.6 gigabytes, before any index structure is added. That figure is our arithmetic from the paper's counts, not a number the paper states. It is the reason the next unit, Vector Search, exists.

Training data: which passage is the positive?

Training needs, for each question, a passage known to be relevant: a positive. The paper trains on five question-answering datasets, and they supply positives in two different ways (their §4.2).

  • Natural Questions and SQuAD come with the passage each answer was found in. Since DPR's passages are cut differently, each original passage is matched to the corresponding 100-word passage, and questions for which the match fails are dropped.
  • TriviaQA, WebQuestions and CuratedTREC come with questions and answers only. For these the positive is chosen by rule: the highest-ranked BM25 passage that contains the answer string. A question is dropped if none of BM25's top 100 passages contains the answer.

The filtering is substantial. Their Table 1 gives the questions in each training set before and after: Natural Questions goes from 79,168 to 58,880, so 74.4% are kept. The second rule also means that for three of the five datasets the positives were selected by BM25. A positive found that way shares terms with its question by construction.

The loss and the negatives

Each training instance is a question $q_i$, its positive passage $p_i^+$ and $n$ negative passages $p_{i,1}^-, \dots, p_{i,n}^-$. The loss is the negative log-likelihood of the positive (their equation 2):

$$\mathcal{L} = -\ln \frac{e^{s(q_i, p_i^+)}}{e^{s(q_i, p_i^+)} + \sum_{j=1}^{n} e^{s(q_i, p_{i,j}^-)}} .$$

This is the contrastive loss that Contrastive Training for Retrieval derives, with dot-product scores and no temperature. That article works its gradient by hand; here we need only what the paper did with it.

The paper's emphasis is on where the negatives come from: "how to select negative examples is often overlooked but could be decisive for learning a high-quality encoder". It considers three kinds (their §3.2).

  • Random: any passage of the collection.
  • BM25: a passage that BM25 ranks highly for the question but that does not contain the answer. It matches the question's terms and is wrong.
  • Gold: the positive passage of another question in the training set.

Gold negatives cost nothing extra when they come from the same batch. With $B$ questions and their $B$ positives in a batch, the $B \times B$ matrix of scores has the positives on its diagonal, and every other entry of a row is a negative for that row's question: $B - 1$ negatives each, with no further passage encoded. These are in-batch negatives, a device the paper credits to earlier work including Henderson et al. (2017).

The configuration the paper settles on uses both. Each question has its in-batch gold negatives and, in addition, one BM25 negative, and each question's BM25 negative also serves as a negative for every other question of the batch. With the batch size of 128 used for the main results, a batch holds 128 questions and 256 passages, so $128 \times 256 = 32{,}768$ scores, and each question has $127 + 128 = 255$ negatives.

The remaining settings, from their §5: up to 40 epochs on the large datasets and 100 on the two small ones, the Adam optimizer at a learning rate of $10^{-5}$ with linear scheduling and warm-up, and a dropout rate of 0.1.

The results the paper reports

All numbers in this section are the paper's, read from its tables; nothing here was rerun.

Retrieval accuracy

Their Table 2 gives top-20 and top-100 accuracy on the test sets of the five datasets. "Single" means the retriever was trained on that dataset alone. "Multi" means one retriever trained on the combined training data of all the datasets except SQuAD. BM25 is Lucene's, with parameters tuned on the development sets ($b = 0.4$, $k_1 = 0.9$). "BM25 + DPR" re-ranks the union of the two systems' top 2,000 passages by $\mathrm{BM25}(q, p) + \lambda \cdot s(q, p)$ with $\lambda = 1.1$.

Top-20 accuracy, in percent:

Training Retriever NQ TriviaQA WQ TREC SQuAD
None BM25 59.1 66.9 55.0 70.9 68.8
Single DPR 78.4 79.4 73.2 79.8 63.2
Single BM25 + DPR 76.6 79.8 71.0 85.2 71.5
Multi DPR 79.4 78.8 75.0 89.1 51.6
Multi BM25 + DPR 78.0 79.9 74.7 88.5 66.2

Top-100 accuracy, in percent:

Training Retriever NQ TriviaQA WQ TREC SQuAD
None BM25 73.7 76.7 71.1 84.1 80.0
Single DPR 85.4 85.0 81.4 89.1 77.2
Single BM25 + DPR 83.8 84.5 80.5 92.7 81.3
Multi DPR 86.0 84.7 82.9 93.9 67.6
Multi BM25 + DPR 83.9 84.4 82.3 94.1 78.6

Subtracting the BM25 row from the single-dataset DPR row gives, at top 20, gains of 19.3 points on Natural Questions, 12.5 on TriviaQA, 18.2 on WebQuestions and 8.9 on CuratedTREC, and a loss of 5.6 on SQuAD. The abstract's "9%-19% absolute" matches the range of these four gains, 8.9 to 19.3; the paper does not say how it computed the range. At top 100 the gains are smaller: 11.7, 8.3, 10.3 and 5.0, with a loss of 2.8 on SQuAD. The paper's own summary is that the gap "is especially large when $k$ is small".

SQuAD is the exception, and the paper offers two reasons as conjecture (their §5.1). SQuAD's questions were written by annotators looking at the passage, so they share many of its words, "which gives BM25 a clear advantage". And its passages come from only some 500 Wikipedia articles, so its training examples are a biased sample of the collection.

The combination with BM25 is not uniformly better than DPR alone. At top 20 with single-dataset training it is lower on two datasets, by 1.8 and 2.2 points, and higher on three, by 0.4, 5.4 and 8.3. The paper says only that results "can be improved further in some cases" by combining.

What mattered in training

Their Table 3 varies the negatives, on the development set of Natural Questions. "IB" marks in-batch training.

Negatives Number per question IB Top-5 Top-20 Top-100
Random 7 no 47.0 64.3 77.8
BM25 7 no 50.0 63.3 74.8
Gold 7 no 42.6 63.1 78.3
Gold 7 yes 51.1 69.1 80.8
Gold 31 yes 52.1 70.8 82.1
Gold 127 yes 55.8 73.0 83.1
Gold + 1 BM25 31 + 32 yes 65.0 77.3 84.4
Gold + 2 BM25 31 + 64 yes 64.5 76.4 84.0
Gold + 1 BM25 127 + 128 yes 65.8 78.0 84.9

The paper draws three conclusions from the table. Without in-batch training, the kind of negative made little difference at $k \ge 20$. With in-batch training, accuracy rose with the batch size: from 7 negatives to 127, top-5 accuracy went from 51.1 to 55.8, a gain of 4.7 points. And adding one BM25 negative per question improved the result substantially, while a second did not help further: at a batch of 32 the first took top-5 accuracy from 52.1 to 65.0, a gain of 12.9 points. Setting the two gains side by side is our reading of the table: one hard negative did more than a fourfold larger batch. Why hard negatives teach more than random ones is the subject of Hard Negatives and Distillation.

Four more findings from the same section (their §5.2 and appendices):

  • Sample efficiency. A retriever trained on only 1,000 Natural Questions examples already outperformed BM25 on the development set (their Figure 1), and accuracy rose steadily up to the full 59,000.
  • Score and loss. Euclidean distance in place of the dot product performed comparably, and both were better than cosine; a triplet loss in place of the negative log-likelihood changed little. Their Table 6 gives top-20 accuracies between 76.1 and 78.1 for the four combinations of dot product or distance with either loss.
  • Positives by rule. Training on BM25-selected positives in place of the gold passages cost about one point of top-$k$ accuracy (their Table 5).
  • Transfer. A retriever trained on Natural Questions alone and applied unchanged to WebQuestions and CuratedTREC reached top-20 accuracies of 69.9 and 86.3, against 75.0 and 89.1 for the best trained retrievers and 55.0 and 70.9 for BM25. The transfer tested is between question-answering sets over the same Wikipedia passages. What happens on a different kind of collection is another matter, taken up in Limits of Single-Vector Retrieval.

Cost and end-to-end accuracy

The paper reports the costs on its own hardware (their §5.4). With a FAISS index held in memory, DPR answered 995.0 questions per second, returning 100 passages each, against 23.7 questions per second per processor thread for BM25 in Lucene. The paper does not put the two on equal terms: the first figure is for the whole server and the second for one thread, so their ratio is not a like-for-like speedup. Building is the other way around: computing the 21 million passage vectors took about 8.8 hours on eight graphics processors, and building the FAISS index took a further 8.5 hours, where Lucene's inverted index took about 30 minutes.

The retriever's gain carried through to answers. With the same kind of reader, exact-match accuracy on Natural Questions was 41.5 with DPR's passages and 32.6 with BM25's, against 33.3 for ORQA (their Table 4). On SQuAD, where DPR retrieved worse than BM25, the answers were worse too, 29.8 against 38.1.

The paper also shows where the dense retriever fails, with one example of each kind (their Table 7). For "What is the body of water between England and Ireland?", BM25's top passage is about British cycling, full of the words England and Ireland, while DPR returns a passage about the Irish Sea. For "Who plays Thoros of Myr in Game of Thrones?", BM25 finds the passage that names the actor and DPR returns a passage about an unrelated actor. The paper's comment is that DPR "might lack sufficient capacity to represent salient phrases which appear rarely".

An experiment: a dense retriever against BM25 and BM25F

Training DPR is far outside what a laptop processor can do: the paper used eight graphics processors with 32 gigabytes each. What can be run here is the retrieval design itself, with a small encoder that someone else has trained.

The encoder is the unit's pinned model, sentence-transformers/all-MiniLM-L6-v2 at revision 1110a243fdf4706b3f48f1d95db1a4f5529b4d41. It differs from DPR in ways that should be kept in view.

  • It is one shared six-block network with mean pooling, not two 12-block networks read at [CLS].
  • Its embeddings have 384 dimensions and unit length, so its score is a cosine.
  • It was trained on about 1.17 billion text pairs from many sources (its model card), with in-batch negatives, not on question-passage pairs from one collection. Neither Cranfield nor this site is among the datasets the card lists.
  • It reads at most 256 word pieces.
  • Search is exhaustive: every stored vector is scored against the query. Nothing is approximated.

So this is not a reproduction of DPR. It tests a narrower claim: that a single vector per passage from a pretrained bi-encoder, with no training on the collection, retrieves as well as the lexical ranker the collection already has.

Cranfield

The Cranfield collection has 1,400 abstracts and 225 queries with graded judgments (the course's test-collection article describes it). The lexical baseline is the BM25 of Comparing Ranking Models, with $k_1 = 1.2$ and $b = 0.75$, stemming and stop-word removal. The dense retriever embeds each abstract (title and text) and each query and ranks all 1,400 abstracts by cosine. The third row fuses the two lists by reciprocal rank fusion with $k = 60$, defined in Rank Fusion.

Ranker nDCG@10 Recall@10 Recall@20 Recall@100 Recall@1000
BM25 0.368 0.397 0.503 0.737 0.952
Dense 0.382 0.416 0.530 0.772 0.989
Fused (RRF) 0.419 0.455 0.576 0.789 0.989

nDCG@10 uses the collection's four grades with gain $5 - \text{grade}$, as the course does on Cranfield. Recall counts any graded abstract as relevant.

The same runs under the paper's measure, the share of queries with at least one relevant abstract in the top $k$:

Ranker Top-1 Top-5 Top-20 Top-100
BM25 0.324 0.769 0.911 0.969
Dense 0.351 0.791 0.916 0.978
Fused (RRF) 0.378 0.822 0.947 0.973

Is the dense retriever better than BM25? By nDCG@10 the difference is $+0.014$, and the paired tests say it could be chance. Over the 225 queries the differences have standard deviation 0.202, so the standard error is 0.0135 and $t = 1.01$ on 224 degrees of freedom, $p = 0.31$. The 95% interval is $[-0.013, 0.040]$. The dense retriever wins on 107 queries, loses on 98 and ties on 20; the sign test gives $p = 0.58$ and the Wilcoxon signed-rank test $p = 0.29$. The randomization test gives $p = 0.31$ (the median of 30 seeds of 20,000 sign assignments each), and the bootstrap interval is $[-0.013, 0.040]$. All five agree: at ten results, the two rankers cannot be told apart on this collection.

Deeper in the list the dense retriever finds more. Recall@100 rises by 0.035, with $t = 2.69$, $p = 0.008$, an interval of $[0.009, 0.061]$, and a randomization $p$ of 0.007; it is higher on 70 queries and lower on 41. The dense list reaches at 77 results the recall that BM25 has at 100.

Mean recall on Cranfield's 225 queries at every cutoff from 1 to 1,000 for BM25, the dense retriever and their fusion, with the cutoff on a logarithmic scale. Notice that the dense curve is barely above BM25's at the left, where the top-ten measures are computed, and that the gap opens with depth: beyond a few hundred results BM25 has nothing left to return for many queries, and its curve flattens at 0.952.
Mean recall on Cranfield's 225 queries at every cutoff from 1 to 1,000 for BM25, the dense retriever and their fusion, with the cutoff on a logarithmic scale. Notice that the dense curve is barely above BM25's at the left, where the top-ten measures are computed, and that the gap opens with depth: beyond a few hundred results BM25 has nothing left to return for many queries, and its curve flattens at 0.952.

Part of that is structural. BM25 can return only abstracts that share at least one term with the query, and for 102 of the 225 queries fewer than 1,000 abstracts do. Of the 1,612 relevant query-abstract pairs, 61 share no stemmed term at all, and BM25 cannot retrieve those at any depth. The dense retriever scores every abstract, and it places 14 of those 61 in its top 100. Counting all relevant pairs, 72 are outside BM25's top 1,000 and 21 are outside the dense retriever's.

The two lists are complementary. Fusion scores 0.419 in nDCG@10, which is 0.051 above BM25 ($t = 5.59$; better on 131 queries, worse on 58) and 0.037 above the dense retriever ($t = 4.17$). The course's Rank Fusion article fused three lexical rankers on this same collection and found that no fusion beat BM25 alone. It found the three lists overlapping heavily in what they retrieved, which is the condition the literature gives for fusion not helping. A dense list rests on different evidence, and here fusing it with BM25 gains more than replacing BM25 with it. The paper's own combined rows show the same thing less consistently, and combining lexical with dense retrieval is a subject of the unit on neural ranking and hybrid retrieval.

Example (query 185, where BM25 wins). The unit's running query, experimental studies on panel flutter, has nine relevant abstracts. BM25's first five results are abstracts 856, 857, 766, 390 and 858, of which four are relevant, and six of its top ten are. The dense retriever's first five are these:

Rank Abstract Cosine Title Judged relevant?
1 658 0.773 review of panel flutter and effects of aerodynamic noise, part I: panel flutter no
2 864 0.760 status of flutter of flat and curved panels no
3 856 0.751 some experimental studies of panel flutter at mach 1.3 yes
4 1008 0.747 free-flight measurements of the static and dynamic yes
5 878 0.671 experimental model techniques and equipment for flutter investigations no

Three of its top ten are relevant, and its nDCG@10 is 0.290 against BM25's 0.807. Its first two results are a review and a status report on panel flutter: on the subject, and not what the query's word "experimental" asks for. A likely reason, which the experiment does not isolate, is that a vector for the whole query gives that one qualifying word only a share of the direction, where BM25 gives it a full term weight. By rank 20 both systems have found all nine relevant abstracts. This is the pattern the paper described with "Thoros of Myr": a dense retriever is good at the subject and less good at a specific term that must be present.

Truncation. The encoder reads 256 word pieces. The median abstract has 192, but 413 abstracts, 29.5%, are longer and are cut. Raising the limit to 512, which leaves 23 abstracts cut, does not help: nDCG@10 goes from 0.382 to 0.376 ($p = 0.15$) and recall@100 from 0.772 to 0.777. The model was trained on texts cut at 128 word pieces (its model card). A likely reason for the lack of gain is that reading further is not something it was trained to use; the experiment does not test that.

This site

The second collection is this site as it stood at one commit: 679 pages, cut by the site's own chunker into 11,264 passages, 16.6 per page on average. A passage is a run of whole paragraphs inside one section of a page, with a median of 216 words. Each is embedded with its page's title and its section's heading in front, as DPR prefixes the article title. Mathematics and code are dropped, and links are replaced by their text. The median passage is 293 word pieces, and 6,721 of them, 59.7%, are longer than the encoder's 256 and are cut.

The judgments are for pages, not passages, so the dense retriever needs a page score. It uses the page's best passage:

$$s(q, \text{page}) = \max_{p \,\in\, \text{page}} \; \vec{q} \cdot \vec{p} .$$

The baseline is the site's live ranker, BM25F over whole pages with weighted fields for title, summary, headings and body, described in How This Search Works. The test set is the site's 60 topical queries with graded judgments from 0 to 3, 1,199 judged query-page pairs in all. nDCG@10 uses gain $2^g - 1$ and counts an unjudged page as grade 0. R@20 is the share of pages whose grade, averaged over the judges, is 2 or more that are found in the top 20. J@10 is the share of the top ten that has a judgment at all. The differences quoted below the tables of this section are computed from the unrounded means, so they can differ in the last place from the difference of two rounded entries (0.817 and 0.788 are 0.8165 and 0.7883, whose difference is 0.028).

Ranker nDCG@10 J@10 R@20 nDCG@10 on judged pages only
BM25F 0.753 0.978 0.995 0.760
Dense 0.626 0.610 0.802 0.788
Fused (RRF) 0.786 0.890 0.937 0.817

Read the first column alone and the dense retriever loses badly: $-0.127$, with $t = -5.39$ and a 95% interval of $[-0.174, -0.080]$, worse on 47 queries of 60. The second column says why that reading cannot be trusted.

Example (a comparison the judgments cannot make). It is natural to read the table as "BM25F is better on this site". The judgments do not support that. They were made by pooling, and the pool was as narrow as a pool can be: for each query, the top 20 results of the site's own BM25F ranker, and nothing else, were collected and judged (tools/search/eval/pool.tsv lists them, every one with a rank in that single ranker). Every page outside those 20 is counted as not relevant. The course's article on pooling explains the method and its known weakness, which is that a system that did not contribute to the pool is judged on documents chosen by its rival. So 97.8% of BM25F's top-ten results have a judgment, and its R@20 of 0.995 is close to 1 by construction: the pages known to be relevant are, by the way the judgments were made, pages that were in BM25F's top 20. (It is not exactly 1, and 13 of BM25F's 600 top-ten results are unjudged, presumably because the site's pages changed between the pooling and this snapshot; the script does not trace the cause.) Of the dense retriever's top-ten results only 61.0% are judged. The other 234 of its 600 results were never looked at, and each is scored as a miss.

Three further readings follow. None of them settles the question.

  • Judged pages only. Remove the unjudged pages from each list and compute nDCG@10 on what remains. The dense retriever then scores 0.788 against BM25F's 0.760, a difference of $+0.028$ with $t = 1.19$, $p = 0.24$ (randomization $p = 0.24$), interval $[-0.019, 0.075]$; it is ahead on 33 queries and behind on 27. Because the judged pages are BM25F's own top 20, this measures each ranker as a re-ranker of BM25F's candidates. It says nothing about pages BM25F does not find, which is where a dense retriever would differ.
  • Two extreme gradings, which are not bounds. With every unjudged page in the dense top ten graded 0, the dense retriever's mean nDCG@10 is the 0.626 of the table. With every one of them graded 3, and the ideal ranking recomputed to include them, it is 0.835. It is tempting to say the true value lies between the two, and it need not. nDCG divides by the score of the ideal ranking, which depends on the grades too, so raising an unknown grade raises the denominator as well as the numerator: for 4 of the 60 queries the all-3 grading gives a lower nDCG@10 than the all-0 grading. Unjudged relevant pages outside the dense top ten would raise the ideal and lower the score further. Evaluating Embedding Models works a small case of the same effect.
  • Recall of the known relevant pages. The dense retriever finds 0.802 of the pages graded 2 or more in its top 20. These are pages from BM25F's top 20, so this says the dense retriever reaches four fifths of what the lexical ranker found and the judges accepted.

The site has a second test set that pooling does not touch: 200 known-item queries, each written for one target page, scored by where that page ranks.

Ranker MRR Target first Target in top 10 Target in top 100
BM25F 0.942 0.905 1.000 1.000
Dense 0.795 0.705 0.950 1.000
Fused (RRF) 0.916 0.865 1.000 1.000

Here BM25F is clearly ahead: the mean difference in reciprocal rank is $-0.147$ ($t = -6.43$ on 199 degrees of freedom), with the dense retriever ahead on 7 queries, behind on 53 and tied on 140. This set has a bias of its own, stated in its documentation: the queries were written by a model from each page's title, summary and headings, with 89% of a query's terms occurring in the target's summary on average, so they reuse the pages' words, and BM25F gives a page's title and summary extra weight. It is a fair test of finding a page one remembers and an easy one for a lexical ranker. Limits of Single-Vector Retrieval takes the failures apart query by query.

What fusion shows on the site. Less than it shows on Cranfield. On judged pages the fused list's nDCG@10 is 0.817, above BM25F by 0.056 ($t = 3.24$, $p = 0.002$; ahead on 41 queries, behind on 18) and above the dense list by 0.028 ($t = 2.66$, $p = 0.010$). But the judged pages are BM25F's own top 20, so this shows that the dense scores help to re-order BM25F's candidates, and nothing about what fusion retrieves beyond them. With unjudged pages counted as misses the fused list scores 0.786 against BM25F's 0.753, a difference of 0.033 that falls short of the usual threshold ($t = 1.92$, $p = 0.06$). On the known-item queries, the one set free of pooling, fusion is not ahead: its MRR is 0.916 against BM25F's 0.942, a mean difference in reciprocal rank of $-0.027$ ($t = -1.76$, $p = 0.080$), with fusion ahead on 12 queries and behind on 19.

What would settle it. None of this shows that dense retrieval or fusion would make the site's search better, or worse. An experiment that could show it has not been done. It would pool the top 20 of all three rankers for each topical query, which on this snapshot adds 728 query-page pairs that have no judgment; judge those pairs with the existing guide, with the source ranker and the ranks hidden; compare the three rankers on the held-out queries, on which nothing was tuned; and add queries written without the pages in view, since both existing sets were written from the pages' own words and that is the condition under which a lexical ranker is hardest to beat.

The opening queries. For T09, the dense retriever's best passage is a section of the calibration note about training a model to predict, from the question alone, whether its answer will be correct, with a cosine of 0.641. The passage is on the query's subject and shares almost none of its wording. For T26, the dense retriever's first result is a passage of the note Building effective agents: about agents, and not about retail. This may be the pattern of "experimental" in query 185 again: the one word that distinguishes the query did not decide the ranking.

Truncation and cost. Reading 512 word pieces in place of 256, so that 702 passages are cut and not 6,721, changes nothing measurable: nDCG@10 on judged pages goes from 0.788 to 0.778 ($p = 0.13$), and known-item MRR from 0.795 to 0.788. The stored vectors take $11{,}264 \times 384 \times 4 = 17{,}301{,}504$ bytes, 17.3 megabytes. Scoring one query against all of them and taking the top 100 took one to two milliseconds on the laptop that ran the script, while other jobs were running (a timing the script prints and does not assert). At this size exhaustive search is fast enough, and no approximate index is needed.

What is proved here, what is cited, and what the experiment shows

Derived on the page. Arithmetic only: the size of DPR's stored vectors, the counts of scores and negatives in its batch, the differences between rows of its tables, and the worked problems.

Cited. Everything about DPR is from Karpukhin et al. (2020): the design, the data preparation, the settings, and every accuracy, timing and example, each with the section or table it was read from. Those results are for five question-answering datasets over one Wikipedia dump, with BERT-base encoders trained on those datasets, and the reasons given for SQuAD are the authors' conjectures. The description of the pinned model's training is from its model card.

Shown by the experiment. On Cranfield, with one pretrained encoder whose listed training data do not include the collection: no detectable difference from BM25 in nDCG@10, higher recall at 100 and beyond, and a fusion that beats both. On this site: a topical test set that cannot rank the two systems because only one of them supplied the pages that were judged, no detectable difference on the judged pages, a clear advantage for BM25F on known-item queries written from the pages' own words, and a fusion that re-orders BM25F's judged candidates better than BM25F does and is not ahead of it, with a lower point estimate, on the known-item queries. No benefit from reading 512 word pieces. These are observations on two small collections with one model. They do not show that dense retrieval is better or worse than lexical retrieval in general, and a different encoder could change every one of them, which is the subject of Evaluating Embedding Models.

Worked problems

These problems are posed on the unit's two collections and on the figures of the DPR paper; the unit has no course assignments. The script recomputes each number under "Worked problems" or in the section the problem refers to.

Problem 1 (index sizes). How many bytes do DPR's passage vectors occupy, and this site's, at four bytes per number? What is the ratio?

Solution. DPR: $21{,}015{,}324$ passages of $768$ numbers, $21{,}015{,}324 \times 768 \times 4 = 64{,}559{,}075{,}328$ bytes, which is 64.6 gigabytes at $10^9$ bytes each (60.1 at $2^{30}$). This site: $11{,}264 \times 384 \times 4 = 17{,}301{,}504$ bytes, 17.3 megabytes. The ratio is 3,731. Half the dimensions and about 1,866 times fewer passages account for it: $2 \times 1{,}865.7 = 3{,}731$.

Problem 2 (nDCG@10 for query 185 by hand). The grades of the two systems' top ten for query 185 give these gains ($5 - \text{grade}$ for a judged relevant abstract, 0 otherwise). Dense: $0, 0, 2, 2, 0, 3, 0, 0, 0, 0$. BM25: $2, 3, 3, 0, 3, 2, 0, 0, 3, 0$. The query's nine relevant abstracts have gains $3, 3, 3, 3, 2, 2, 1, 1, 1$. Compute nDCG@10 for both.

Solution. DCG@10 is $\sum_{r=1}^{10} g_r / \log_2(r + 1)$. For the dense list only ranks 3, 4 and 6 contribute:

$$\frac{2}{\log_2 4} + \frac{2}{\log_2 5} + \frac{3}{\log_2 7} = 1.000 + 0.861 + 1.069 = 2.930 .$$

For BM25, ranks 1, 2, 3, 5, 6 and 9 contribute, and the sum is 8.169. The ideal list puts the nine gains in decreasing order at ranks 1 to 9, which gives 10.121. So nDCG@10 is $2.930 / 10.121 = 0.290$ for the dense list and $8.169 / 10.121 = 0.807$ for BM25. The dense list's two relevant abstracts at ranks 3 and 4 are both of gain 2. The four abstracts of gain 3, which BM25 puts at ranks 2, 3, 5 and 9, are at ranks 6, 11, 19 and 17 in the dense list.

Problem 3 (top-$k$ accuracy and recall are different measures). In the dense list for query 185 the nine relevant abstracts are at ranks 3, 4, 6, 11, 12, 15, 16, 17 and 19. In BM25's list they are at ranks 1, 2, 3, 5, 6, 9, 12, 14 and 15. For each list give the top-1 and top-5 accuracy of this query, in the paper's sense, and recall at 10 and at 20.

Solution. Top-$k$ accuracy for one query is 1 if any relevant abstract is in the first $k$ and 0 otherwise. Dense: the first relevant abstract is at rank 3, so top-1 is 0 and top-5 is 1. BM25: the first is at rank 1, so both are 1. Recall@10 is the share of the nine found in the first ten: three for the dense list (ranks 3, 4, 6), $3/9 = 0.333$; six for BM25, $6/9 = 0.667$. Recall@20 is $9/9 = 1$ for both. At $k = 5$ the paper's measure calls the two lists equal on this query, though BM25 has four relevant abstracts there and the dense list two. Top-$k$ accuracy suits a reader that needs one good passage; recall suits a later stage that will re-rank everything it is given.

Problem 4 (page scores from passage scores). For a test query about picking a model without fitting noise (T33), the eight highest-scoring passages are, with their cosines: model-selection#1 0.529, model-selection#17 0.501, introduction-to-ensemble-models#1 0.480, model-selection#14 0.424, model-selection#3 0.422, introduction-to-ensemble-models#12 0.416, stacking#10 0.413, model-selection#2 0.402. The number after the page's name is the passage's position in the page. Give the first three pages of the ranking.

Solution. Each page takes its best passage's score. model-selection has five passages in the list, and its score is the largest, 0.529. introduction-to-ensemble-models has two, and its score is 0.480. stacking has one, 0.413. Any page not in the list has a best passage below 0.402, so the ranking begins model-selection, introduction-to-ensemble-models, stacking. The first is graded 3 for this query and the third 2; the second was never judged. BM25F ranks model-selection 12th. Taking the maximum means a page's other passages neither help nor hurt it: five strong passages count the same as one.

Problem 5 (the paired t-test on Cranfield). The 225 per-query differences in nDCG@10, dense minus BM25, have mean 0.0136 and standard deviation 0.2021. Compute the standard error, the $t$ statistic and a 95% confidence interval, and say what they show.

Solution. The standard error is $s_d / \sqrt{n} = 0.2021 / \sqrt{225} = 0.2021 / 15 = 0.0135$. The statistic is $t = 0.0136 / 0.0135 = 1.01$ on 224 degrees of freedom. With that many degrees of freedom the critical value for 95% is close to the normal 1.96 (the script uses the exact $t$ value), so the interval is about $0.0136 \pm 1.97 \times 0.0135$, that is $[-0.013, 0.040]$. It contains zero, and $p = 0.31$. The data are consistent with no difference, and also with a difference of up to four hundredths in favor of the dense retriever. The large standard deviation, fifteen times the mean, is the per-query variation that the course's article names as the reason a test is needed at all: on single queries the two rankers differ by as much as 0.68 one way and 0.59 the other.

What we have learned

DPR is a bi-encoder with two BERT networks, a dot product, and a contrastive loss over in-batch negatives plus one BM25 negative per question. Trained on question-passage pairs, it beat BM25 by 9 to 19 points of top-20 accuracy on four of five question-answering datasets and lost on the fifth, SQuAD, where questions echo their passages. Its ablations located the gain in the training recipe: more in-batch negatives helped, and one hard negative helped more. Our own run of a small pretrained bi-encoder shows the same shape on a small scale. On Cranfield the dense retriever was about even with BM25 at the top of the lists, better at depth, weaker where one exact word decides relevance, and most useful fused with the lexical list. On this site the topical comparison ran into the limits of the test collection, whose judged pages all came from BM25F. On the known-item queries, which have no pool, BM25F was clearly ahead, though those queries were written from the pages' own words. Whether a dense retriever or a fusion would serve the site's readers better is not answered by any of these numbers.

The paper's most effective single change was a better negative. Why random negatives stop teaching, how harder ones are mined, and what goes wrong when a mined negative is in fact relevant are the subject of Hard Negatives and Distillation.

References

  • Henderson, M., Al-Rfou, R., Strope, B., Sung, Y.-H., Lukács, L., Guo, R., Kumar, S., Miklos, B., and Kurzweil, R. (2017). Efficient natural language response suggestion for Smart Reply. arXiv:1705.00652. record · 2 pages
  • Johnson, J., Douze, M., and Jégou, H. (2021). Billion-scale similarity search with GPUs. IEEE Transactions on Big Data, 7(3), 535–547. record · 3 pages
  • Karpukhin, V., Oğuz, B., Min, S., Lewis, P., Wu, L., Edunov, S., Chen, D., and Yih, W. (2020). Dense passage retrieval for open-domain question answering. In Proceedings of EMNLP 2020, 6769–6781. arXiv:2004.04906. record · 10 pages
  • Lee, K., Chang, M.-W., and Toutanova, K. (2019). Latent retrieval for weakly supervised open domain question answering. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, 6086–6096. record
  • sentence-transformers (n.d.). sentence-transformers/all-MiniLM-L6-v2. Model card and train_script.py at revision 1110a243fdf4706b3f48f1d95db1a4f5529b4d41. https://huggingface.co/sentence-transformers/all-MiniLM-L6-v2 (accessed 17 November 2026). record · 5 pages