Open-Domain Question Answering

The retriever and reader design for answering factual questions from a large collection, from the TREC-8 question answering track of 1999 through DrQA to the dense retrievers of 2020, and the two measures that score its answers. Exact match and token F1 are defined as SQuAD's official script computes them and proved to satisfy F1 = 2c/(|prediction| + |gold|) and EM ≤ F1; all 37,927 judged answer strings of TREC-8 are scored three ways (assessors, NIST's answer patterns, EM and F1 against the question writers' 203 answers); and a bound is proved that no extractive reader's exact match can exceed the share of questions whose answer is contained in what it reads, then read against the published tables of DrQA, BERTserini, DPR and the distilled reader of Izacard and Grave. Five worked problems cover scoring by hand, several gold answers, softmax across paragraphs, the bound on published numbers, and a generative reader that escapes it.

Question 21 of the TREC-8 question answering track, in 1999, was "Who was the first American in space?" One of the systems that took part answered "Jerry Brown". It had found a newspaper article in which a sentence ran "As for Wilson himself, he became a senator by defeating Jerry Brown, who has been called the first American in space", and it returned the name from that sentence (Voorhees and Tice, 1999, §2.3.1). The assessors marked the answer incorrect. The system had retrieved a document about the right words and read it wrongly. A different system might have read well and retrieved badly. So what does it take to answer a factual question from a large collection, and how should an answer be scored?

Open-domain question answering is the task of answering a question, usually a short factual one, from a large collection of text with no indication of where in the collection the answer lies. "Open" means that the answering system is not handed the passage that contains the answer, as it is in reading comprehension. Systems for it have been built, since the first evaluations, from two parts: a retriever that selects a small number of documents or passages from the collection, and a reader that extracts or writes an answer from what was selected. The later articles of this unit replace the reader with a language model; this one sets out the design, its measures and its ceilings, which the replacement does not remove.

Here is the route. First we look at the TREC-8 track, which defined the task, and at what its assessors found about answers. Then we follow the design to DrQA, which read Wikipedia with a neural reader, and to the datasets on which open-domain systems have been scored since. Next come the two measures, exact match and F1, with their exact definitions and a few properties proved; we then apply them, together with NIST's answer patterns, to every answer string judged at TREC-8. Finally we prove that an extractive reader can be no more accurate than its retriever's answer containment, and read that bound against the published tables. The article assumes the evaluation measures of ranked retrieval evaluation and the retriever of Dense Passage Retrieval. The numbers are computed by tools/experiments/rag/open-domain-question-answering.py, which downloads the public TREC-8 files from NIST and checks each against a recorded hash.

The first large evaluation: TREC-8

The question answering track ran for the first time at TREC-8 in 1999. Its report states the goal: "to retrieve small snippets of text that contain the actual answer to a question rather than the document lists traditionally returned by text retrieval systems" (Voorhees, 1999, introduction). The task was deliberately narrow.

  • The collection was the newspaper and government text on TREC disks 4 and 5 without the Congressional Record, the collection of the TREC-8 ad hoc task.
  • There were 200 questions, each "fact-based" with a short answer, and each guaranteed to have at least one document in the collection that answered it. Figure 1 of the report lists ten of them, among them "How many calories are there in a Big Mac?" and "Who was the 16th President of the United States?".
  • A system returned, for each question, a ranked list of five pairs of a document identifier and an answer string. The string was limited to 50 bytes in one kind of run and 250 bytes in the other, and it could be cut from the document or generated from it.
  • Human assessors read each string and decided whether it contained an answer to the question in the context of its document.

The score of a question was the reciprocal of the rank of the first correct string, or 0 if none of the five was correct, and a run's score was the mean over questions: the mean reciprocal rank (MRR), which ranked retrieval evaluation defines and works through. With five strings a question can score only six values, 0, 0.2, 0.25, 0.33, 0.5 and 1, which the report lists as a drawback, together with two others: a system received no credit for a second correct answer, and no credit for knowing that it did not know (§1).

Twenty organizations submitted 45 runs. The scores were computed over 198 questions, because two were found during judging to have no clear answer in the collection. The best 50-byte run, Cymfony's textract9908, had an MRR of 0.660 and found no correct string for 54 questions; the best 250-byte run, SMUNLP2 from Southern Methodist University, had 0.646 and missed 44 (Table 1 of the report). The report's summary is that "the most accurate systems found a correct response for more than 2/3 of the questions".

How the systems worked

The report describes the strategy most participants followed (§3). A system first classified the question by the type of answer it asked for: a question beginning "who" asks for a person or organization, one beginning "when" for a time. It then retrieved a small part of the collection with ordinary document retrieval, using the question as the query. A shallow parse of the retrieved text found entities of the required type, and if one occurred close enough to the question's words, it was returned; otherwise the system fell back on the best-matching passage.

This is the retriever and reader design in an early form, and the report found where it was strong and where it was weak. Passage retrieval alone did well when 250 bytes were allowed and badly at 50: AT&T's passage-based method "was very competitive for the 250-byte limit, but was not nearly as successful when restricted to just 50 bytes" (§2). Finding the answer's neighborhood was a retrieval problem; pinning down the answer itself was not. The report gives the Jerry Brown answer as its example of the second failure: "pattern matching on expected answer types was not fool-proof even when 'good' matches were found" (§3).

What the assessors found

The companion paper by Voorhees and Tice (1999) describes how the strings were judged, and it is a careful account of how hard it is to say whether an answer is right. Each question was judged by three assessors independently. Where they disagreed, an adjudicator decided whether the difference was a matter of opinion, in which case the majority stood, or a misapplication of the guidelines, in which case it did not. The pool of strings for one question held 191.6 pairs on average (§2.3). On average 6% of the strings were disagreed on, and the overlap of the sets of strings the three assessors judged correct, the size of their intersection divided by the size of their union, averaged 0.641 over the 193 questions with at least one correct string (§2.4).

The disagreements were mostly not mistakes. Two assessors accepted "April 22" as the date of a death and the third required the year; some accepted only "Lamar, Missouri" as a birthplace and others accepted "Missouri" (§2.3.2). The authors called this "the myth of the obvious answer" and concluded that "it is pointless to try to create a set of rules that specify exactly what is acceptable or unacceptable in all cases". Context mattered too. For "What is the capital of Kosovo?" the assessors accepted the 50-byte string

0 miles northwest of Pristina, five demonstrators

and rejected a 250-byte string that also contained "Pristina", because it named two towns and it was "unclear from the response whether the capital is Vucitrn or Pristina" (Voorhees, 1999, §2).

Example (a judged answer is a judged string). The unit that TREC-8 judged was the string returned, with its document, not the answer the system meant. That has a cost the track's evaluation paper states plainly: different runs "almost never return exactly the same answer strings", so the judgments cannot score a new system's strings, and the track "did not create a comparable QA test collection" (Voorhees and Tice, 1999, §3). The answer patterns that NIST distributes with the data, described below, score strings that no assessor saw.

That leaves the design and a scoring problem. The design took a new form in 2017, when the reader became a neural network trained on a large dataset of questions.

Machine reading at scale: DrQA

Reading comprehension, as the SQuAD dataset defined it, gives a model a paragraph and a question and asks for the span of the paragraph that answers it (Rajpurkar et al., 2016). Chen, Fisch, Weston and Bordes (2017) put such a model behind a retriever and pointed the pair at the whole of English Wikipedia, 5,075,182 articles in their dump of 21 December 2016 (§4.1). They called the setting machine reading at scale and the system DrQA. "In order to answer any question, one must first retrieve the few relevant articles among more than 5 million items, and then scan them carefully to identify the answer" (§1).

The retriever

DrQA's Document Retriever is not learned. Articles and questions are compared as TF-IDF weighted bag-of-words vectors, as in the course's TF-IDF and vector space model, with bigram counts added to capture local word order; the bigrams are mapped to $2^{24}$ bins by hashing to keep the index small (§3.1). It returns five articles per question. Table 3 of the paper measures it by the share of questions for which an answer string appears in one of the five articles returned:

Dataset Wikipedia search TF-IDF, unigrams TF-IDF with hashed bigrams
SQuAD 62.7 76.1 77.8
CuratedTREC 81.0 85.2 86.0
WebQuestions 73.7 75.5 74.4
WikiMovies 61.7 54.4 70.3

The authors add that BM25 and an embedding-based retriever "performed worse" in their trials (§5.1).

The reader

The Document Reader reads one paragraph at a time. Each token of the paragraph is represented by a GloVe word vector, three binary features saying whether it matches a question word exactly (in its original, lowercase or lemma form), part-of-speech and named-entity tags, its term frequency, and an attention-weighted average of the question's word vectors. A three-layer bidirectional LSTM turns these into context vectors $\vec{h}_1, \dots, \vec{h}_L$ for a paragraph of $L$ tokens, and a second LSTM with a learned weighting turns the question into one vector $\vec{q}$ (§3.2). Two bilinear classifiers then score each token as the start and as the end of the answer:

$$P_{\text{start}}(i) \propto \exp\!\big(\vec{h}_i^{\mathsf T} W_s\, \vec{q}\big), \qquad P_{\text{end}}(i') \propto \exp\!\big(\vec{h}_{i'}^{\mathsf T} W_e\, \vec{q}\big),$$

and the answer is the span from $i$ to $i'$ with $i \le i' \le i + 15$ that maximizes $P_{\text{start}}(i)\,P_{\text{end}}(i')$.

One detail matters for reading many paragraphs. The proportionality signs hide a normalization over the tokens of one paragraph. A span's normalized score says how much better it is than the other spans of its own paragraph, so normalized scores of different paragraphs cannot be compared, and a paragraph with one weak candidate can outscore a paragraph with several strong ones. DrQA therefore uses "the unnormalized exponential and take[s] argmax over all considered paragraph spans" (§3.2). Worked problem 3 shows the reversal on numbers.

How far reading at scale fell short

On the standard SQuAD task, where the right paragraph is given, the reader alone reached 69.5 exact match and 78.8 F1 on the development set (Table 4). With all of Wikipedia to search, the same kind of model (a streamlined version without the part-of-speech, entity and term-frequency features and without lemma matching, §5.3) answered 27.1% of the SQuAD development questions exactly when trained on SQuAD alone, and 29.8% when trained also on the other datasets with distant supervision (Table 6). The paper locates the loss in two steps. Given the correct article but not the paragraph, the reader reached 49.4. The retriever placed an answer-bearing article in its top five for 77.8% of the questions (Table 3). On our reading of these numbers, 20.1 of the 42.4 points between 69.5 and 27.1 were lost in finding the paragraph inside a known article, and 22.3 in going from a known article to five retrieved ones; since the full and the streamlined readers differ slightly, the split is approximate. The authors attribute much of the first loss to "highly topical sentences" that are not the answer, and part of the whole loss to SQuAD itself: its questions were written by people looking at a paragraph, so out of context "their language can be ambiguous" (§5.3).

DrQA's distant supervision is a rule that later systems varied; DPR's choice of positive passages, described in Dense Passage Retrieval, is one variant. For a dataset that supplies only questions and answer strings, the training paragraphs are found by rule: retrieve five articles, keep paragraphs that contain an answer string exactly, drop paragraphs shorter than 25 or longer than 1,500 characters and paragraphs missing the question's named entities, and keep up to five paragraphs whose 20-token window around the answer overlaps the question most (§4.4). A paragraph that contains the answer string need not support it, which is the false-positive problem that Izacard and Grave (2021b) illustrate with "Ada Lovelace died in 1852 in London" as a supposed positive for "where was Ada Lovelace born?".

The datasets

Open-domain systems since DrQA have been scored on a small set of datasets, most of them built for some other purpose and converted. The conversion is the same each time: keep each question and its answer strings, discard any passage that came with them, and score a system on the strings alone.

  • SQuAD (Rajpurkar et al., 2016): 107,785 questions written by crowdworkers about paragraphs of 536 Wikipedia articles. Its open form uses the development questions without their paragraphs.
  • CuratedTREC: questions from the TREC question answering tracks of 1999 to 2002, curated by Baudiš and Šedivý; DrQA used the large version of 2,180 questions (Chen et al., 2017, §4.3). Its answers are given as regular expressions (Lewis et al., 2020, Appendix D), as TREC's patterns were.
  • WebQuestions: questions gathered through the Google Suggest API and answered from the Freebase knowledge base, converted to plain text by Chen et al. (2017, §4.3).
  • TriviaQA (Joshi et al., 2017): 95,000 question-answer pairs "authored by trivia enthusiasts" with evidence documents gathered separately; open-domain work uses the unfiltered version without the evidence.
  • Natural Questions (Kwiatkowski et al., 2019): queries of eight words or more issued to Google by multiple users, each paired with a Wikipedia page from the top five search results and annotated with a long answer (usually a paragraph) and a short answer if the page has one. The release has 307,373 training examples, 7,830 development examples with five annotations each and 7,842 test examples held back. Its open version, NQ-Open, keeps questions with short answers of at most five tokens and discards the page (Lee, Chang and Toutanova, 2019, §7.1).

Two properties of these sets shape every result reported on them. The first is who wrote the questions. Lee, Chang and Toutanova (2019) separate datasets where "the question askers do not already know the answer" (Natural Questions, WebQuestions, CuratedTREC) from those where they do (SQuAD, TriviaQA), and found that the difference decided whether BM25 or a learned retriever won. A question written by someone looking at the answer tends to share its words. The second is overlap between training and test data. Lewis, Stenetorp and Riedel (2021) found that 63.6% of the test answers of NQ-Open also appear among its training answers, and that 32.5% of a sample of 1,000 test questions had a paraphrase in the training set (Table 1). Their abstract reports that models score far lower on test questions that cannot be memorized from the training set. The share of test answers seen in training was 71.7% for TriviaQA and 58% for WebQuestions.

The datasets give each question one or more gold answer strings. What remains is to decide when a predicted string matches one of them.

Exact match and F1

Rajpurkar et al. (2016, §6.1) defined the two measures that the field has used since. Both "ignore punctuations and articles". Exact match "measures the percentage of predictions that match any one of the ground truth answers exactly". The F1 score treats the prediction and each gold answer "as bags of tokens", computes their F1, takes the maximum over the gold answers and averages over questions. The prose leaves details open, and the official evaluation script fixes them. Since the open-domain papers of this unit score with that script's normalization ("lowercasing and removing articles, punctuation and duplicated whitespace", in the words of Izacard and Grave, 2021a, §4), we define the measures as the script computes them.

Normalization. A string is normalized in four steps, in this order:

  1. convert it to lowercase;
  2. delete every ASCII punctuation character (Python's string.punctuation);
  3. replace each whole word a, an or the by a space;
  4. collapse runs of whitespace to single spaces and trim the ends.

The tokens of a string are the space-separated words of its normalized form. For the string "The astronaut, Alan B. Shepard Jr." the steps give "the astronaut, alan b. shepard jr.", then "the astronaut alan b shepard jr", then the same with "the" blanked, and finally astronaut alan b shepard jr, five tokens.

Definitions. Write $\hat a$ for the predicted answer, $A$ for the set of gold answers, $\nu(s)$ for the normalized form of a string $s$ and $\tau(s)$ for its multiset of tokens, with $|\tau(s)|$ the number of tokens. For one gold answer $a$:

$$\mathrm{EM}(\hat a, a) = \begin{cases} 1 & \nu(\hat a) = \nu(a) \\ 0 & \text{otherwise,} \end{cases}$$

and, with $c = |\tau(\hat a) \cap \tau(a)|$ the size of the multiset intersection (a token that occurs twice in both counts twice), precision $c / |\tau(\hat a)|$ and recall $c / |\tau(a)|$,

$$\mathrm{F}_1(\hat a, a) = \frac{2 \cdot \text{precision} \cdot \text{recall}}{\text{precision} + \text{recall}} \quad (c > 0), \qquad \mathrm{F}_1(\hat a, a) = 0 \quad (c = 0).$$

If either token list is empty, the script sets F1 to 1 when both are empty and 0 otherwise. Over several gold answers each measure takes the maximum, $\mathrm{EM}(\hat a, A) = \max_{a \in A} \mathrm{EM}(\hat a, a)$ and likewise for F1, and a system's score is the mean over questions, usually reported in percent.

Three properties follow directly, and they explain most of what the two measures do.

Proposition 1 (F1 is a ratio of counts). For $c > 0$, $\mathrm{F}_1(\hat a, a) = \dfrac{2c}{|\tau(\hat a)| + |\tau(a)|}$.

Proof. Write $u = |\tau(\hat a)|$ and $v = |\tau(a)|$. Then precision is $c/u$ and recall is $c/v$, so $$\frac{2 \cdot \frac{c}{u} \cdot \frac{c}{v}}{\frac{c}{u} + \frac{c}{v}} = \frac{2c^2 / (uv)}{c(u + v)/(uv)} = \frac{2c}{u + v}. \qquad \blacksquare$$

The right side is the Dice coefficient of the two token bags. It needs no division by zero to be handled separately when $c > 0$, and the script asserts the identity for every string it scores.

Proposition 2 (exact match never exceeds F1). For every prediction and gold set, $\mathrm{EM}(\hat a, A) \le \mathrm{F}_1(\hat a, A)$; so the same holds for the means.

Proof. If $\mathrm{EM}(\hat a, A) = 0$ there is nothing to prove, since F1 is never negative. If it is 1, some $a \in A$ has $\nu(\hat a) = \nu(a)$, so $\tau(\hat a) = \tau(a)$. If the token lists are empty, F1 is 1 by the empty rule; otherwise $c = u = v$, and Proposition 1 gives $2c/(2c) = 1$. Hence $\mathrm{F}_1(\hat a, a) = 1$ and the maximum over $A$ is 1. Averaging over questions preserves the inequality term by term. $\blacksquare$

Proposition 3 (what each measure ignores). Exact match and F1 against every gold set are unchanged by any of these edits to a string: changing the case of an ASCII letter (more generally, any change that lowercasing undoes); inserting or deleting an ASCII punctuation character; inserting or deleting a whitespace-delimited word a, an or the; lengthening or shortening a run of whitespace that is already there. F1 is unchanged, in addition, by reordering the tokens.

Proof. Each normalization step erases one kind of edit: lowercasing erases case, step 2 deletes every punctuation character wherever it stood, step 3 removes the whole-word articles and step 4 reduces every whitespace run to one space. So a string and its edited form have equal normalized forms, hence equal token multisets, and both measures depend on a string only through these. F1 depends on the strings only through the multisets $\tau(\hat a)$ and $\tau(a)$, which do not record order. $\blacksquare$

The edits must be exactly these. Replacing a punctuation mark by a space is not one of them: "U.S.A." normalizes to usa, but "U S A" normalizes to u s, because its last letter now stands alone as the article a, and the two score an F1 of 0 against each other.

Back to question 21. NIST's file of the question writers' original answers gives "Alan Shepard". The script scores a few predictions against it:

Prediction Normalized tokens EM F1 Matches NIST's pattern
Alan Shepard alan shepard 1 1 yes
alan shepard. alan shepard 1 1 yes
Shepard shepard 0 0.667 yes
Alan B. Shepard Jr. alan b shepard jr 0 0.667 yes
the astronaut Alan Shepard astronaut alan shepard 0 0.800 yes
Shepard, Alan shepard alan 0 1 yes
Jerry Brown jerry brown 0 0 no

The F1 of "Alan B. Shepard Jr." is $2 \cdot 2/(4 + 2) = 0.667$ by Proposition 1: two tokens shared, four predicted, two gold. The fuller name is penalized as much as the bare surname. "Shepard, Alan" scores a full F1 and no exact match, which is Proposition 3 at work.

Example (F1 credits a wrong answer and docks a right one). "F1 is a softer exact match, so a higher F1 means a better answer." Not reliably. The 50-byte Kosovo string that TREC-8's assessors accepted has seven tokens after normalization, 0 miles northwest of pristina five demonstrators, one of which is the gold answer "Pristina": its F1 is $2 \cdot 1/(7 + 1) = 0.25$. A wrong answer that shares a common word with the gold, "Alan Turing" against "Alan Shepard" for instance, would score 0.5. F1 measures token overlap, which tracks correctness only as far as the gold strings anticipate the forms an answer can take.

TREC's answer patterns

NIST took a third route for TREC-8 (National Institute of Standards and Technology, 1999). With the judgments it distributes a file of answer patterns, regular expressions, for each question, and a script, pp_eval.pl, that counts a string as correct if "some pattern for the current question has a string match with the response". The match is case-insensitive and must begin and end at a non-word character or at an end of the string. The pattern for question 21 is the single word Shepard; for question 162, the Kosovo question, there are two, Prish?tina and Prishtine, which accept spellings that exact match against "Pristina" would reject. A pattern accepts any string that contains it, so the 50-byte Kosovo string passes, and so does the rejected 250-byte string, which also contains "Pristina".

Three ways of scoring, measured on TREC-8

The adjudicated judgments, the patterns and the question writers' answers are all public, so the three ways of scoring can be compared on the same strings. The judgments cover 37,927 answer strings for the 198 scored questions, of which the assessors judged 5,768 correct and 32,159 incorrect. The script scores each string with NIST's patterns and computes EM and F1 against the question writer's answers. The writers gave 203 answers to the 198 scored questions, since five questions have two, and the gold set of a question is all of its writer's answers, as in the definition of $\mathrm{EM}(\hat a, A)$.

Pattern matches Pattern does not match
Judged correct (5,768) 5,735 33
Judged incorrect (32,159) 582 31,577

The patterns agree with the adjudicated judgment on 98.4% of the strings and accept 99.4% of the correct ones. Agreement alone overstates this, since 84.8% of the strings were judged incorrect and a rule that rejects everything would agree that often; corrected for chance agreement, Cohen's kappa for the table is 0.939. Of the strings the patterns accept, 9.2% were judged incorrect. These may be strings that contain an accepted form without answering, like the 250-byte Kosovo string, or whose document did not support the answer; the data do not record the assessors' reasons. The data page does not say how the patterns were made (the file is named adjudicated_for_perl), and this agreement is measured on the strings that were judged. It does not say how well the patterns would stand in for assessors on the strings of a new system, which may fail in ways the 1999 systems did not.

Exact match against the writers' answers is the wrong tool for these strings. Only 121 of the 5,768 correct strings, 2.1%, equal one of their question's writer's answers after normalization. Submitted strings were limited to 50 or 250 bytes, and a string of that size has room for many words besides the answer: of the 37,927 strings as stored in NIST's judgment file (counted in Latin-1 bytes, which need not match the submitted strings byte for byte), 20,629 are longer than 50 bytes. F1 separates the two groups weakly: the mean F1 is 0.170 for correct strings and 0.009 for incorrect ones, and 81.4% of the correct strings and 6.5% of the incorrect ones share at least one token with a writer's answer.

The comparison also turns up the myth of the obvious answer in the data. Four strings equal a question writer's answer exactly and were judged incorrect. The assessors judged each string in the context of its document (Voorhees and Tice, 1999, §2.2), which can make an exact answer string wrong, for example when the document is about a different entity; the data do not record their reasons for these four. One of them is question 116, "Which team won the Super Bowl in 1968?", where the writer's answer was "Green Bay Packers" and the adjudicated pattern names a different team. And of the writers' 203 answers, the patterns reject 16; for 14 questions they reject every answer the writer gave, and for two more (questions 32 and 96) they accept the writer's other answer, so 184 questions have an accepted writer's answer. The 16 include different spellings ("Hoagy Carmichael" against the pattern's Hoagie\s+Carmichael, "Joseph Hazlewood" against Hazelwood), different precision (the writer's "35" against a pattern for "mid-30s") and different facts. In 69 of the 198 questions the patterns list more than one acceptable form.

So a gold answer string is a sample from the set of acceptable answers, and exact match, F1 and patterns are three ways of estimating membership in that set from a sample. That limit is the subject of Evaluating Retrieval-Augmented Systems when the answers are long and written by a model. For short factual answers, the open-domain papers cited in this unit report exact match, some with F1 beside it.

How answer accuracy depends on retrieval

A reader can answer only from what the retriever gives it. The DrQA numbers suggest how strong that limit is: 77.8% of questions had an answer in the top five articles and 27.1% were answered. The limit can be made exact for one kind of reader.

Answer containment. For a question with gold answers $A$ and retrieved passages $p_1, \dots, p_k$, say the answer is contained if for some $a \in A$ and some $j$, the token sequence of $\nu(a)$ occurs as a contiguous run in the token sequence of $\nu(p_j)$. The containment rate at $k$ is the share of questions whose answer is contained in their top $k$ passages. It is the top-$k$ accuracy of Dense Passage Retrieval with one difference that matters below: here it is computed with the same normalization as exact match.

An extractive reader returns a span of one of the passages it was given. We require the span to consist of whole whitespace-separated words of the passage. A reader that predicts spans over word pieces can cut a word in two, and the counterexample after the theorem shows why the bound needs whole words.

Here is the plan. If normalization treated each word of a passage separately, a span of whole words would normalize to a contiguous run of the passage's normalized tokens, and an exactly matching gold answer would then be contained. So we first prove that normalization acts word by word, then draw the bound.

Lemma (normalization acts word by word). Let a string $t$ have the whitespace-separated words $w_1, \dots, w_n$. Then the token sequence of $\nu(t)$ is the concatenation of the token sequences of $\nu(w_1), \dots, \nu(w_n)$.

Proof. Follow the four steps. Lowercasing and deleting punctuation act on one character at a time and neither creates nor removes whitespace, so after them $t$ is still the words, each transformed separately, joined by the same whitespace. (Python's lowercasing of a capital Greek sigma looks at neighboring letters to choose the final form, but whitespace ends that context, so the choice is the same for the word alone; and a word made only of punctuation becomes empty, which leaves two whitespace runs side by side for step 4 to merge.) The third step replaces a match of \b(a|an|the)\b. A match consists of letters only, so it lies inside one word; and the word boundaries \b at its ends are decided by the neighboring characters, which inside a word are the same whether the word stands alone or in $t$, and at the word's edges are whitespace or the end of the string, both non-word characters, so a boundary in either case. Hence each word is transformed exactly as it would be alone, with any article replaced by a space inside it. The fourth step splits the result at whitespace, and splitting a whitespace-joined sequence of strings gives the concatenation of the splits of each. $\blacksquare$

Theorem (the extractive bound). For an extractive reader whose answers are spans of whole words of its $k$ input passages, the exact match on any set of questions is at most the containment rate at $k$: $$\mathrm{EM} \le \text{containment at } k.$$

Proof. Take a question that the reader answers exactly: its answer $\hat a$ is the words $w_i, \dots, w_j$ of some passage $p$, and $\nu(\hat a) = \nu(a)$ for some gold $a$. By the lemma applied to $\hat a$, the tokens of $\nu(\hat a)$ are the concatenation of the tokens of $\nu(w_i), \dots, \nu(w_j)$; by the lemma applied to $p$, that concatenation is a contiguous run of the tokens of $\nu(p)$. Since $\nu(a) = \nu(\hat a)$, the tokens of $a$ are that run, so the question's answer is contained. Every exactly answered question is therefore a contained question, and dividing the counts by the number of questions gives the inequality. $\blacksquare$

The word-boundary condition is needed. In the passage "a rock-n-roll band", the characters "rock" form a span that exactly matches the gold answer "rock", yet the passage normalizes to the tokens rocknroll band, which do not contain it. The script checks the lemma on 20,000 random strings mixing letters, digits, punctuation, articles, non-ASCII letters and several kinds of whitespace (seed 20261118), and finds this counterexample when the span may cut a word.

Two consequences are worth stating. Since $\mathrm{EM} = \text{containment} \times (\text{EM among contained questions})$, the ratio of exact match to containment is the reader's accuracy on the questions it could have answered, which separates the two parts of the system. And the bound does not hold for a reader that writes its answer. Lewis et al. (2020, §4.1) report that their generative model answered 11.8% of the Natural Questions test questions correctly whose answer was in none of the retrieved passages, "where an extractive model would score 0%". The RAG Models explain where such answers come from.

Reading the bound on published tables

Published papers compute containment with their own matching rules, which are close to the normalization above but not identical (the evaluation code of the DPR repository, for example, tokenizes with a regular expression, keeps punctuation as tokens and lowercases without dropping articles; Facebook Research, 2026), so the bound holds for their numbers only approximately. With that caution the ratios are informative.

DrQA. 27.1 against 77.8 gives a ratio of 0.348: when an answer-bearing article was among the five, the reader found the answer about a third of the time.

BERTserini. Yang et al. (2019) put a BERT reader behind BM25 over the same Wikipedia dump and varied the unit of retrieval. Their Table 1 gives exact match, F1 and containment (their $R$, "the fraction of questions for which the correct answer appears in any retrieved segment") on the SQuAD development questions:

Retrieval EM F1 $R$ EM / $R$
Articles, $k = 5$ 19.1 25.9 63.1 0.303
Paragraphs, $k = 29$ 36.6 44.0 75.0 0.488
Sentences, $k = 78$ 34.0 41.0 67.5 0.504
Paragraphs, $k = 100$ 38.6 46.1 85.8 0.450

The first three rows read about the same amount of text, since an article has 5.8 paragraphs and a paragraph 2.7 sentences on average. Paragraphs win on containment. Sentences give the reader slightly better odds once the answer is present but contain it less often, and the product favors paragraphs; whole articles contain it less often than 29 paragraphs and bury it among distractors, so the reader's ratio falls to 0.303. Going from 29 to 100 paragraphs raised containment by 10.8 points and exact match by only 2.0, and the ratio fell. The paper's Figure 2 shows the shape: exact match "doesn't appear to increase much after around $k = 10$" while containment keeps rising to 100, so "the BERT reader is unable to take advantage of these additional answer passages".

DPR. Dense Passage Retrieval gives the retriever's top-20 and top-100 accuracy (Karpukhin et al., 2020, Table 2) and the end-to-end exact match (Table 4) on Natural Questions. The reader read $k = 50$ passages there, the value the authors found best, so its containment lies between the top-20 and top-100 accuracies, and the reader's ratio lies between exact match divided by each:

Retriever Top-20 Top-100 EM EM / top-100 EM / top-20
BM25 59.1 73.7 32.6 0.442 0.552
DPR 78.4 85.4 41.5 0.486 0.529

DPR's interval lies inside BM25's: a reader of the same design, given the dense retriever's passages, was about as good at finding an answer that was there, which is consistent with the gain in exact match coming from the answer being there more often. The paper's own conclusion is that "a higher retrieval precision indeed translates to a higher end-to-end QA accuracy" (§1).

The reader as a judge of passages. Izacard and Grave (2021b) report a sharper version of the BERTserini observation with a generative reader. Reading DPR's top 100 passages, their reader reached 48.2 exact match on Natural Questions; reading DPR's top 10, 42.9; reading the 10 of the 100 that the reader's own attention weighted most, 46.8 (§3.2). Cutting from 100 to 10 passages cost 5.3 points when the retriever chose the ten and 1.4 when the reader did. Both selections read ten passages from the same hundred, so the difference is in which ten: the reader's own choice kept most of what the retriever's lost. Fusion-in-Decoder takes up that reader and its use of many passages.

A retrieval ceiling for TREC-8

The TREC-8 data also include, for each question, a ranked list of the top 200 documents (the data page calls it the "top docs ranked list" and does not name the system that made it). The judgments say which documents supported a correct answer string, so the script can compute, for each question, the rank of the first such document in that list. The share of questions with one in the top $k$ is a lower bound on the list's top-$k$ document containment, since a document that no participant drew an answer from was never judged.

Top $k$ documents Questions with a supporting document Share of 198
1 96 48.5%
5 142 71.7%
10 155 78.3%
20 163 82.3%
50 174 87.9%
100 181 91.4%
200 187 94.4%

Some judged document supports a correct answer for 193 of the 198 questions. For question 21 the first document of the list is one; for question 193, "Who was the 16th President of the United States?", none of the 200 is a judged supporting document. The curve has the shape of every containment curve in this article: steep over the first ten documents, then slow. The participating systems did their own retrieval and did not read this list, so the curve does not measure their readers; it shows only that a list of this kind held a supporting document in its top 5 for at least 71.7% of the questions.

What is proved, what is cited, what the script shows

Proved here. The identity $\mathrm{F}_1 = 2c/(|\tau(\hat a)| + |\tau(a)|)$; that exact match never exceeds F1, per question and in the mean; what each measure is invariant to; that SQuAD's normalization acts word by word; and the extractive bound, exact match at most containment, with the counterexample showing why spans must be whole words.

Cited. Every result of TREC-8 (Voorhees, 1999; Voorhees and Tice, 1999), DrQA (Chen et al., 2017), BERTserini (Yang et al., 2019), DPR (Karpukhin et al., 2020), the distilled reader of Izacard and Grave (2021b), the overlap study (Lewis, Stenetorp and Riedel, 2021) and the 11.8% of Lewis et al. (2020), each with its table or section. The dataset descriptions are their papers', and those of CuratedTREC and WebQuestions are as DrQA describes them.

Computed by the script on NIST's public files. The scores of the example strings; the agreement of patterns, exact match and F1 with the adjudicated judgments on all 37,927 judged strings; the 16 of the writers' 203 answers that the patterns reject (14 questions with none accepted); the lower bound on the containment of the distributed ranked lists; the check of the lemma on 20,000 random strings; and the arithmetic on the published tables. These are measurements of one collection, one set of patterns and one run, and are reported as such.

Worked problems

The unit has no course assignments; these problems are posed on the TREC-8 data and on published tables, and the script recomputes each number.

Problem 1 (scoring by hand). For question 162 the gold answer is "Pristina". Score the strings "Pristina.", "the capital, Pristina", "Prishtina" and the accepted 50-byte string by exact match, F1 and NIST's patterns.

"Pristina." normalizes to pristina: EM 1, F1 1, and the pattern Prish?tina matches. "the capital, Pristina" normalizes to capital pristina: EM 0, and with $c = 1$, F1 $= 2/(2 + 1) = 0.667$; the pattern matches. "Prishtina" normalizes to prishtina, which shares no token with pristina: EM 0, F1 0, but the pattern matches, since h? makes the h optional. The 50-byte string has seven tokens, one shared: EM 0, F1 $2/(7 + 1) = 0.25$, pattern matches. Two strings that a reader would accept get an F1 of 0.25 and 0, and only the pattern accepts all four. The pattern, in turn, also accepts the 250-byte string the assessors rejected.

Problem 2 (several gold answers). For question 73, "Where is the Taj Mahal?", take the gold set {"Agra", "Agra, India"} and the prediction "in Agra". Compute EM and F1.

The prediction normalizes to in agra. Against "Agra" ($\tau = \{\text{agra}\}$): $c = 1$, F1 $= 2/(2 + 1) = 0.667$. Against "Agra, India" ($\tau = \{\text{agra}, \text{india}\}$): $c = 1$, F1 $= 2/(2 + 2) = 0.5$. The score is the maximum, 0.667, and EM is 0 against both. Adding a gold string can never lower a score, since the maximum is taken over a larger set; the prediction "India" scores 0 against "Agra" and $2/(1 + 2) = 0.667$ against "Agra, India". How many acceptable forms are listed therefore changes every system's score. TriviaQA lists 13.7 answer strings per question on average against 1.2 for Natural Questions (Lewis, Stenetorp and Riedel, 2021, §3), one reason why exact match on the two datasets is not on the same scale.

Problem 3 (why DrQA leaves its span scores unnormalized). A reader scores the candidate spans of two paragraphs on a log scale. Paragraph 1 has three candidates with scores 2, −3 and −3; paragraph 2 has three with 5, 5 and 4. Which span wins if the scores are normalized by a softmax within each paragraph, and which if they are compared unnormalized?

Within paragraph 1 the softmax gives the first span $e^2/(e^2 + 2e^{-3}) = 0.987$. Within paragraph 2 the two best spans tie at $e^5/(2e^5 + e^4) = 0.422$. Normalized, paragraph 1's span wins, 0.987 to 0.422. Unnormalized, the comparison is $e^2$ against $e^5$, and paragraph 2's spans win by a factor of $e^3$. The normalized score rewards paragraph 1 for having no competing candidates, which says nothing about whether its span answers the question; paragraph 2's high scores are spread over several strong candidates. That is the reason DrQA compares "the unnormalized exponential" across paragraphs.

Problem 4 (the bound on published numbers). BERTserini reading 100 paragraphs has $R = 85.8$ and EM 38.6. What is the highest exact match a better reader could reach with the same retrieval, and what is the present reader's accuracy on the questions it could answer? What would it take to reach 50 EM?

By the extractive bound, with the caution about matching rules, no extractive reader can exceed 85.8 on these passages. The present reader's ratio is $38.6/85.8 = 0.450$. Reaching 50 needs a ratio of $50/85.8 = 0.583$ at the same retrieval, or containment of $50/0.450 = 111$ with the same reader, which is impossible; so with this reader the gain must come from reading better, not from retrieving more. The 29-paragraph row has a higher ratio, 0.488, which suggests why: more passages brought more distractors along with more answers.

Problem 5 (a generative reader escapes the bound). Give a case in which a reader that writes its answer scores exact match on a question whose answer is not contained in its passages, and say why the theorem's proof does not apply.

Suppose the gold answer is "Alan Shepard" and the reader's passages mention only "Shepard's flight" and "the first American astronaut". A generative reader can write "Alan Shepard" from a name completed by its own weights: EM 1 with the answer not contained. The proof used one fact about the reader, that its answer is a span of whole words of a passage, to place the answer inside a passage. A generated answer need not be a span, so nothing places it there. The 11.8% of Natural Questions answered without the answer in any retrieved passage (Lewis et al., 2020) is this case at scale. Whether such an answer can be trusted is another matter, which Attribution and Citation takes up.

What we have learned

Open-domain question answering was defined at TREC-8 as answering short factual questions from a large collection, and the retriever and reader design that its systems used has lasted. The assessors of that first track found that even simple questions have no single obvious answer, a finding the public judgments still show: NIST's patterns reject 16 of the question writers' own 203 answers, and exact match against the writers' answers accepts 2.1% of the strings the assessors judged correct. Exact match and F1, as SQuAD's script defines them, are crude estimates of whether an answer belongs to the set of acceptable answers; we proved that F1 is a Dice coefficient of token bags and never falls below exact match. For extractive readers the retriever sets a hard ceiling, which we proved: exact match cannot exceed the rate at which the answer is contained in what the reader reads. Published tables, from DrQA to DPR, show the ceiling and a reader working well below it.

The ceiling holds because the reader copies spans. The next article, The RAG Models, replaces the reader with a generator that writes its answer while conditioning on retrieved passages, and trains the retriever from answers alone by treating the passage as a hidden variable.

References

  • Chen, D., Fisch, A., Weston, J., and Bordes, A. (2017). Reading Wikipedia to answer open-domain questions. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, 1870–1879. https://doi.org/10.18653/v1/P17-1171. arXiv:1704.00051. record · 3 pages
  • Facebook Research (2026). DPR: Dense Passage Retriever [software repository, read in November 2026], evaluation code dpr/data/qa_validation.py. https://github.com/facebookresearch/DPR record
  • Izacard, G., and Grave, E. (2021a). Leveraging passage retrieval with generative models for open domain question answering. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics, 874–880. https://doi.org/10.18653/v1/2021.eacl-main.74. arXiv:2007.01282. record · 2 pages
  • Izacard, G., and Grave, E. (2021b). Distilling knowledge from reader to retriever for question answering. In International Conference on Learning Representations (ICLR 2021). https://openreview.net/forum?id=NTEz-6wysdb. arXiv:2012.04584. record · 2 pages
  • Joshi, M., Choi, E., Weld, D. S., and Zettlemoyer, L. (2017). TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, 1601–1611. https://doi.org/10.18653/v1/P17-1147. arXiv:1705.03551. record
  • 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. https://doi.org/10.18653/v1/2020.emnlp-main.550. arXiv:2004.04906. record · 15 pages
  • Kwiatkowski, T., Palomaki, J., Redfield, O., Collins, M., Parikh, A., Alberti, C., Epstein, D., Polosukhin, I., Devlin, J., Lee, K., Toutanova, K., Jones, L., Kelcey, M., Chang, M.-W., Dai, A. M., Uszkoreit, J., Le, Q., and Petrov, S. (2019). Natural Questions: A benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7, 453–466. https://doi.org/10.1162/tacl_a_00276. record · 2 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. https://doi.org/10.18653/v1/P19-1612. arXiv:1906.00300. record · 4 pages
  • Lewis, P., Perez, E., Piktus, A., Petroni, F., Karpukhin, V., Goyal, N., Küttler, H., Lewis, M., Yih, W., Rocktäschel, T., Riedel, S., and Kiela, D. (2020). Retrieval-augmented generation for knowledge-intensive NLP tasks. In Advances in Neural Information Processing Systems 33, 9459–9474. arXiv:2005.11401. record · 6 pages
  • Lewis, P., Stenetorp, P., and Riedel, S. (2021). Question and answer test-train overlap in open-domain question answering datasets. In Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics, 1000–1008. https://doi.org/10.18653/v1/2021.eacl-main.86. arXiv:2008.02637. record
  • National Institute of Standards and Technology (1999). TREC-8 QA data: test questions, original answers, answer patterns and pp_eval.pl, judgment set, and top documents ranked list. https://trec.nist.gov/data/qa/t8_qadata.html record
  • Rajpurkar, P., Zhang, J., Lopyrev, K., and Liang, P. (2016). SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of EMNLP 2016, 2383–2392. https://doi.org/10.18653/v1/D16-1264. arXiv:1606.05250. Official evaluation script, version 2.0, from the SQuAD website (https://rajpurkar.github.io/SQuAD-explorer/). record
  • Voorhees, E. M. (1999). The TREC-8 question answering track report. In Proceedings of the Eighth Text REtrieval Conference (TREC-8), NIST Special Publication 500-246, 77–82. record · 5 pages
  • Voorhees, E. M., and Tice, D. M. (1999). The TREC-8 question answering track evaluation. In Proceedings of the Eighth Text REtrieval Conference (TREC-8), NIST Special Publication 500-246, 83–105. record
  • Yang, W., Xie, Y., Lin, A., Li, X., Tan, L., Xiong, K., Li, M., and Lin, J. (2019). End-to-end open-domain question answering with BERTserini. In Proceedings of NAACL-HLT 2019: Demonstrations, 72–77. https://doi.org/10.18653/v1/N19-4013. arXiv:1902.01718. record