What are the different approaches proposed to perform iterative retrieval for open-domain QA?
Prior work has explored iterative retrieval for open-domain QA in a fully supervised setting. Das et al. (2019) proposes an iterative retrieval model that retrieves using a neural query representation and then updates it based on a reading comprehension model’s output. Feldman and El-Yaniv (2019) apply similar neural query reformulation idea for multihop open-domain QA. Xiong et al. (2021) extends the widely-used Dense Passage Retrieval (DPR) (Karpukhin et al., 2020) to multihop setting, which has since been improved by Khattab et al. (2021). Asai et al. (2020) leverages the graph structure induced by the entity links present in Wikipedia paragraphs to perform iterative multi-step retrieval. GoldEn (Gold Entity) retriever (Qi et al., 2019) iteratively generates text queries based on paragraphs retrieved from an off-the-shelf retriever but requires training data for this next query generator. Nakano et al. (2021) used GPT3 to answer long-form questions by interacting with the browser but relied on human annotations of these interactions. All of these methods rely on supervised training on a large-scale dataset and can not be easily extended
to a few-shot setting.
Answering Complex Open-domain Questions Through Iterative Query Generation
It is challenging for current one-step retrieve-and-read question answering (QA) systems to answer questions like “Which novel by the author of ‘Armada’ will be adapted as a feature film by Steven Spielberg?” because the question seldom contains retrievable clues about the missing entity (here, the author). Answering such a question requires multi-hop reasoning where one must gather information about the missing entity (or facts) to proceed with further reasoning. We present GoldEn (Gold Entity) Retriever, which iterates between reading context and retrieving more supporting documents to answer open-domain multi-hop questions. Instead of using opaque and computationally expensive neural retrieval models, GoldEn Retriever generates natural language search queries given the question and available context, and leverages off-the-shelf information retrieval systems to query for missing entities. This allows GoldEn Retriever to scale up efficiently for open-domain multi-hop reasoning while maintaining interpretability. We evaluate GoldEn Retriever on the recently proposed open-domain multi-hop QA dataset, HotpotQA, and demonstrate that it outperforms the best previously published model despite not using pretrained language models such as BERT.
[{"first":"Peng","last":"Qi","middle":[]},{"first":"Xiaowen","last":"Lin","middle":[]},{"first":"Leo","last":"Mehr","middle":[]},{"first":"Zijian","last":"Wang","middle":[]},{"first":"Christopher D.","last":"Manning","middle":[]}]
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Answering questions that require multi-hop reasoning at web-scale necessitates retrieving multiple evidence documents, one of which often has little lexical or semantic relationship to the question. This paper introduces a new graph-based recurrent retrieval approach that learns to retrieve reasoning paths over the Wikipedia graph to answer multi-hop open-domain questions. Our retriever model trains a recurrent neural network that learns to sequentially retrieve evidence paragraphs in the reasoning path by conditioning on the previously retrieved documents. Our reader model ranks the reasoning paths and extracts the answer span included in the best reasoning path. Experimental results show state-of-the-art results in three open-domain QA datasets, showcasing the effectiveness and robustness of our method. Notably, our method achieves significant improvement in HotpotQA, outperforming the previous best model by more than 14 points.
[{"first":"Akari","last":"Asai","middle":[]},{"first":"Kazuma","last":"Hashimoto","middle":[]},{"first":"Hannaneh","last":"Hajishirzi","middle":[]},{"first":"Richard","last":"Socher","middle":[]},{"first":"Caiming","last":"Xiong","middle":[]}]
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
We propose a simple and efficient multi-hop dense retrieval approach for answering complex open-domain questions, which achieves state-of-the-art performance on two multi-hop datasets, HotpotQA and multi-evidence FEVER. Contrary to previous work, our method does not require access to any corpus-specific information, such as inter-document hyperlinks or human-annotated entity markers, and can be applied to any unstructured text corpus. Our system also yields a much better efficiency-accuracy trade-off, matching the best published accuracy on HotpotQA while being 10 times faster at inference time.
[{"first":"Wenhan","last":"Xiong","middle":[]},{"first":"Xiang","last":"Li","middle":["Lorraine"]},{"first":"Srini","last":"Iyer","middle":[]},{"first":"Jingfei","last":"Du","middle":[]},{"first":"Patrick","last":"Lewis","middle":[]},{"first":"William","last":"Wang","middle":["Yang"]},{"first":"Yashar","last":"Mehdad","middle":[]},{"first":"Wen-tau","last":"Yih","middle":[]},{"first":"Sebastian","last":"Riedel","middle":[]},{"first":"Douwe","last":"Kiela","middle":[]},{"first":"Barlas","last":"Ouguz","middle":[]}]
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Multi-hop reasoning (i.e., reasoning across two or more documents) is a key ingredient for NLP models that leverage large corpora to exhibit broad knowledge. To retrieve evidence passages, multi-hop models must contend with a fast-growing search space across the hops, represent complex queries that combine multiple information needs, and resolve ambiguity about the best order in which to hop between training passages. We tackle these problems via Baleen, a system that improves the accuracy of multi-hop retrieval while learning robustly from weak training signals in the many-hop setting. To tame the search space, we propose condensed retrieval, a pipeline that summarizes the retrieved passages after each hop into a single compact context. To model complex queries, we introduce a focused late interaction retriever that allows different parts of the same query representation to match disparate relevant passages. Lastly, to infer the hopping dependencies among unordered training passages, we devise latent hop ordering, a weak-supervision strategy in which the trained retriever itself selects the sequence of hops. We evaluate Baleen on retrieval for two-hop question answering and many-hop claim verification, establishing state-of-the-art performance.
[{"first":"Omar","last":"Khattab","middle":[]},{"first":"Christopher","last":"Potts","middle":[]},{"first":"Matei","last":"Zaharia","middle":[]}]
WebGPT: Browser-assisted question-answering with human feedback
We fine-tune GPT-3 to answer long-form questions using a text-based web-browsing environment, which allows the model to search and navigate the web. By setting up the task so that it can be performed by humans, we are able to train models on the task using imitation learning, and then optimize answer quality with human feedback. To make human evaluation of factual accuracy easier, models must collect references while browsing in support of their answers. We train and evaluate our models on ELI5, a dataset of questions asked by Reddit users. Our best model is obtained by fine-tuning GPT-3 using behavior cloning, and then performing rejection sampling against a reward model trained to predict human preferences. This model's answers are preferred by humans 56% of the time to those of our human demonstrators, and 69% of the time to the highest-voted answer from Reddit.
[{"first":"Reiichiro","last":"Nakano","middle":[]},{"first":"Jacob","last":"Hilton","middle":[]},{"first":"Suchir","last":"Balaji","middle":[]},{"first":"Jeff","last":"Wu","middle":[]},{"first":"Long","last":"Ouyang","middle":[]},{"first":"Christina","last":"Kim","middle":[]},{"first":"Christopher","last":"Hesse","middle":[]},{"first":"Shantanu","last":"Jain","middle":[]},{"first":"Vineet","last":"Kosaraju","middle":[]},{"first":"William","last":"Saunders","middle":[]},{"first":"Xu","last":"Jiang","middle":[]},{"first":"Karl","last":"Cobbe","middle":[]},{"first":"Tyna","last":"Eloundou","middle":[]},{"first":"Gretchen","last":"Krueger","middle":[]},{"first":"Kevin","last":"Button","middle":[]},{"first":"Matthew","last":"Knight","middle":[]},{"first":"Benjamin","last":"Chess","middle":[]},{"first":"John","last":"Schulman","middle":[]}]
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
This paper introduces a new framework for open-domain question answering in which the retriever and the reader iteratively interact with each other. The framework is agnostic to the architecture of the machine reading model, only requiring access to the token-level hidden representations of the reader. The retriever uses fast nearest neighbor search to scale to corpora containing millions of paragraphs. A gated recurrent unit updates the query at each step conditioned on the state of the reader and the reformulated query is used to re-rank the paragraphs by the retriever. We conduct analysis and show that iterative interaction helps in retrieving informative paragraphs from the corpus. Finally, we show that our multi-step-reasoning framework brings consistent improvement when applied to two widely used reader architectures DrQA and BiDAF on various large open-domain datasets --- TriviaQA-unfiltered, QuasarT, SearchQA, and SQuAD-Open.
[{"first":"Rajarshi","last":"Das","middle":[]},{"first":"Shehzaad","last":"Dhuliawala","middle":[]},{"first":"Manzil","last":"Zaheer","middle":[]},{"first":"Andrew","last":"McCallum","middle":[]}]
Answering Complex Open-domain Questions Through Iterative Query Generation
Open-domain question answering (QA) is an important means for us to make use of knowledge in large text corpora and enables diverse queries without requiring a knowledge schema ahead of time. Enabling such systems to perform multistep inference can further expand our capability to explore the knowledge in these corpora (e.g., see Figure 1). Fueled by the recently proposed large-scale QA datasets such as SQuAD (Rajpurkar et al., 2016(Rajpurkar et al., , 2018 and TriviaQA (Joshi et al., 2017), much progress has been made in open-domain question answering. Chen et al. (2017) proposed a twostage approach of retrieving relevant content with the question, then reading the paragraphs returned by the information retrieval (IR) component to arrive at the final answer. This "retrieve and read" approach has since been adopted and extended in various open-domain QA systems (Nishida et al., 2018;Kratzwald and Feuerriegel, 2018), but it is inherently limited to answering questions that do not require multi-hop/multi-step reasoning. This is because for many multi-hop questions, not all the relevant context can be obtained in a single retrieval step (e.g., "Ernest Cline" in Figure 1).
Answering Complex Open-domain Questions Through Iterative Query Generation
More recently, the emergence of multi-hop question answering datasets such as QAngaroo (Welbl et al., 2018) and HOTPOTQA (Yang et al., 2018) has sparked interest in multi-hop QA in the research community. Designed to be more challenging than SQuAD-like datasets, they feature questions that require context of more than one document to answer, testing QA systems' abilities to infer the answer in the presence of multiple pieces of evidence and to efficiently find the evidence in a large pool of candidate documents. However, since these datasets are still relatively new, most of the existing research focuses on the few-document setting where a relatively small set of context documents is given, which is guaranteed to contain the "gold" context documents, all those from which the answer comes (De Cao et al., 2019;Zhong et al., 2019).
Answering Complex Open-domain Questions Through Iterative Query Generation
In this paper, we present GOLDEN (Gold Entity) Retriever. Rather than relying purely on the original question to retrieve passages, the central innovation is that at each step the model also uses IR results from previous hops of reasoning to generate a new natural language query and retrieve new evidence to answer the original question. For the example in Figure 1, GOLDEN would first generate a query to retrieve Armada (novel) based on the question, then query for Ernest Cline based on newly gained knowledge in that article. This allows GOLDEN to leverage off-the-shelf, generalpurpose IR systems to scale open-domain multihop reasoning to millions of documents efficiently, and to do so in an interpretable manner. Combined with a QA module that extends BiDAF++ (Clark and Gardner, 2017), our final system outperforms the best previously published system on the open-domain (fullwiki) setting of HOTPOTQA without using powerful pretrained language models like BERT (Devlin et al., 2019).
Answering Complex Open-domain Questions Through Iterative Query Generation
The main contributions of this paper are: (a) a novel iterative retrieve-and-read framework capable of multi-hop reasoning in open-domain QA; 1 (b) a natural language query generation approach that guarantees interpretability in the multi-hop evidence gathering process; (c) an efficient training procedure to enable query generation with minimal supervision signal that significantly boosts recall of gold supporting documents in retrieval.
Answering Complex Open-domain Questions Through Iterative Query Generation
In this section, we formally define the problem of open-domain multi-hop question answering, and motivate the architecture of the proposed GOLDEN (Gold Entity) Retriever model. We then detail the query generation components as well as how to derive supervision signal for them, before concluding with the QA component.
Answering Complex Open-domain Questions Through Iterative Query Generation
We define the problem of open-domain multi-hop QA as one involving a question q, and S relevant (gold) supporting context documents d 1 , . . . , d S which contain the desired answer a. 3 These supporting documents form a chain of reasoning necessary to arrive at the answer, and they come from a large corpus of documents D where |D| S. In this chain of reasoning, the supporting documents are usually connected via shared entities or textual similarities (e.g., they describe similar entities or events), but these connections do not necessarily conform to any predefined knowledge schema.
Answering Complex Open-domain Questions Through Iterative Query Generation
We contrast this to what we call the fewdocument setting of multi-hop QA, where the QA system is presented with a small set of documents D few-doc = {d 1 , . . . , d S , d 1 , . . . , d D }, where d 1 , . . . , d D comprise a small set of "distractor" documents that test whether the system is able to pick out the correct set of supporting documents in the presence of noise. This setting is suitable for testing QA systems' ability to perform multi-hop reasoning given the gold supporting documents with bounded computational budget, but we argue that it is far from a realistic one. In practice, an open-domain QA system has to locate all gold supporting documents from D on its own, and as shown in Figure 1, this is often difficult for multi-hop questions based on the original question alone, as not all gold documents are easily retrievable given the question.
Answering Complex Open-domain Questions Through Iterative Query Generation
To address this gold context discoverability issue, we argue that it is necessary to move away from a single-hop retrieve-and-read approach where the original question serves as the search query. In the next section, we introduce GOLDEN Retriever, which addresses this problem by iterating between retrieving more documents and reading the context for multiple rounds.
Answering Complex Open-domain Questions Through Iterative Query Generation
Essentially, the challenge of open-domain multihop QA lies in the fact that the information need of the user (q → a) cannot be readily satisfied by any information retrieval (IR) system that models merely the similarity between the question q and the documents. This is because the true information need will only unfold with progressive reasoning and discovery of supporting facts. Therefore, one cannot rely solely on a similarity-based IR system for such iterative reasoning, because the potential pool of relevant documents grows exponentially with the number of hops of reasoning.
Answering Complex Open-domain Questions Through Iterative Query Generation
To this end, we propose GOLDEN (Gold Entity) Retriever, which makes use of the gold document 4 information available in the QA dataset at training time to iteratively query for more relevant supporting documents during each hop of reasoning. Instead of relying on the original question as the search query to retrieve all supporting facts, 
Answering Complex Open-domain Questions Through Iterative Query Generation
Which novel by the author of "Armada" will be adapted as a feature film by Steven Spielberg? or building computationally expensive search engines that are less interpretable to humans, we propose to leverage text-based IR engines for interpretability, and generate different search queries as each reasoning step unfolds. In the very first hop of reasoning, GOLDEN Retriever is presented the original question q, from which it generates a search query q 1 that retrieves supporting document d 1 . 5 Then for each of the subsequent reasoning steps (k = 2, . . . , S), GOLDEN Retriever generates a query q k from the question and the available context, (q, d 1 , . . . , d k−1 ). This formulation allows the model to generate queries based on information revealed in the supporting facts (see Figure 2, for example). We note that GOLDEN Retriever is much more efficient, scalable, and interpretable at retrieving gold documents compared to its neural retrieval counterparts. This is because GOLDEN Retriever does not rely on a QA-specific IR engine tuned to a specific dataset, where adding new documents or question types into the index can be extremely inefficient. Further, GOLDEN Retriever generates queries in natural language, making it friendly to human interpretation and verification. One core challenge in GOLDEN Retriever, however, is to train query generation models in an efficient manner, because the search space for potential queries is enormous and off-the-shelf IR engines are not end-to-end differentiable. We outline our solution to this challenge in the following sections.
Answering Complex Open-domain Questions Through Iterative Query Generation
For each reasoning step, we need to generate the search query given the original question q and 5 For notational simplicity, d k denotes the supporting document needed to complete the k-th step of reasoning. We also assume that the goal of each IR query is to retrieve one and only one gold supporting document in its top n results. some context of documents we have already retrieved (initially empty). This query generation problem is conceptually similar to the QA task in that they both map a question and some context to a target, only instead of an answer, the target here is a search query that helps retrieve the desired supporting document for the next reasoning step. Therefore, we formulate the query generation process as a question answering task.
Answering Complex Open-domain Questions Through Iterative Query Generation
To reduce the potentially large space of possible queries, we favor a QA model that extracts text spans from the context over one that generates free-form text as search queries. We therefore employ DrQA's Document Reader model (Chen et al., 2017), which is a relatively light-weight recurrent neural network QA model that has demonstrated success in few-document QA. We adapt it to query generation as follows.
Answering Complex Open-domain Questions Through Iterative Query Generation
For each reasoning step k = 1, . . . , S, given a question q and some retrieval context C k which ideally contains the gold supporting documents d 1 , . . . , d k−1 , we aim to generate a search query q k that helps us retrieve d k for the next reasoning step. A Document Reader model is trained to select a span from C k as the query
Answering Complex Open-domain Questions Through Iterative Query Generation
where G k is the query generator. This query is then used to search for supporting documents, which are concatenated with the current retrieval context to update it
Answering Complex Open-domain Questions Through Iterative Query Generation
where IR n (q k ) is the top n documents retrieved from the search engine using q k , and C 1 = q. 6 At the end of the retrieval steps, we provide q as question along with C S as context to the final few- document QA component detailed in Section 3.5 to obtain the final answer to the original question.
Answering Complex Open-domain Questions Through Iterative Query Generation
To train the query generators, we follow the steps above to construct the retrieval contexts, but during training time, when d k is not part of the IR result, we replace the lowest ranking document with d k before concatenating it with C k to make sure the downstream models have access to necessary context.
Answering Complex Open-domain Questions Through Iterative Query Generation
When deriving supervision signal to train our query generators, the potential search space is enormous for each step of reasoning even if we constrain ourselves to predicting spans from the context. This is aggravated by multiple hops of reasoning required by the question. One solution to this issue is to train the query generators with reinforcement learning (RL) techniques (e.g., RE-INFORCE (Sutton et al., 2000)), where (Nogueira and Cho, 2017) and (Buck et al., 2018) are examples of one-step query generation with RL. However, it is computationally inefficient, and has high variance especially for the second reasoning step and forward, because the context depends greatly on what queries have been chosen previously and their search results. Instead, we propose to leverage the limited supervision we have about the gold supporting documents d 1 , . . . , d S to narrow down the search space.
Answering Complex Open-domain Questions Through Iterative Query Generation
The key insight we base our approach on is that at any step of open-domain multi-hop reasoning, there is some semantic overlap between the retrieval context and the next document(s) we wish to retrieve. For instance, in our Armada example, when the retrieval context contains only the question, this overlap is the novel itself; after we have expanded the retrieval context, this overlap becomes the name of the author, Ernest Cline. Finding this semantic overlap between the retrieval context and the desired documents not only reveals the chain of reasoning naturally, but also allows us to use it as the search query for retrieval.
Answering Complex Open-domain Questions Through Iterative Query Generation
Because off-the-shelf IR systems generally optimize for shallow lexical similarity between query and candidate documents in favor of efficiency, a good proxy for this overlap is locating spans of text that have high lexical overlap with the intended supporting documents. To this end, we propose a simple yet effective solution, employing several heuristics to generate candidate queries: computing the longest common string/sequence between the current retrieval context and the title/text of the intended paragraph ignoring stop words, then taking the contiguous span of text that corresponds to this overlap in the retrieval context. This allows us to not only make use of entity names, but also textual descriptions that better lead to the gold entities. It is also more generally applicable than question decomposition approaches (Talmor and Berant, 2018;Min et al., 2019b), and does not require additional annotation for decomposition.
Answering Complex Open-domain Questions Through Iterative Query Generation
Applying various heuristics results in a handful of candidate queries for each document, and we use our IR engine (detailed next) to rank them based on recall of the intended supporting document to choose one as the final oracle query we train our query generators to predict. This allows us to train the query generators in a fully supervised manner efficiently. Some examples of oracle queries on the HOTPOTQA dev set can be found in Table 1. We refer the reader to Appendix B for more technical details about our heuristics and how the oracle queries are derived.
Answering Complex Open-domain Questions Through Iterative Query Generation
Oracle Query vs Single-hop Query We evaluate the oracle query against the single-hop query, i.e., querying with the original question, on the HOTPOTQA dev set. Specifically, we compare the recall of gold paragraphs, because the greater the recall, the fewer documents we need to pass into the expensive neural multi-hop QA component. 
Answering Complex Open-domain Questions Through Iterative Query Generation
Oracle d2 Figure 3: Recall comparison between single-hop queries and GOLDEN Retriever oracle queries for both supporting paragraphs on the HOTPOTQA dev set. Note that the oracle queries are much more effective than the original question (single-hop query) at retrieving target paragraphs in both hops.
Answering Complex Open-domain Questions Through Iterative Query Generation
We index the English Wikipedia dump with introductory paragraphs provided by the HOT-POTQA authors 7 with Elasticsearch 6.7 (Gormley and Tong, 2015), where we index the titles and document text in separate fields with bigram indexing enabled. This results in an index with 5,233,329 total documents. At retrieval time, we boost the scores of any search result whose title matches the search query better -this results in a better recall for entities with common names (e.g., "Armada" the novel). For more details about how the IR engine is set up and the effect of score boosting, please refer to Appendix A.
Answering Complex Open-domain Questions Through Iterative Query Generation
In Figure 3, we compare the recall of the two gold paragraphs required for each question in HOTPOTQA at various number of documents retrieved (R@n) for the single-hop query and the multi-hop queries generated from the oracle. Note that the oracle queries are much more effective at retrieving the gold paragraphs than the original question in both hops. For instance, if we combine R@5 of both oracles (which effectively retrieves 10 documents from two queries) and compare that to R@10 for the single-hop query, the oracle queries improve recall for d 1 by 6.68%, and that for d 2 by a significant margin of 49.09%. 8 7 https://hotpotqa.github.io/ wiki-readme.html 8 Since HOTPOTQA does not provide the logical order its gold entities should be discovered, we simply call the document d1 which is more easily retrievable with the queries, and the other as d2. This means that the final QA model will need to consider far fewer documents to arrive at a decent set of supporting facts that lead to the answer.
Answering Complex Open-domain Questions Through Iterative Query Generation
The final QA component of GOLDEN Retriever is based on the baseline model presented in (Yang et al., 2018), which is in turn based on BiDAF++ (Clark and Gardner, 2017). We make two major changes to this model. Yang et al. (2018) concatenated all context paragraphs into one long string to predict span begin and end offsets for the answer, which is potentially sensitive to the order in which these paragraphs are presented to the model. We instead process them separately with shared encoder RNN parameters to obtain paragraph order-insensitive representations for each paragraph. Span offset scores are predicted from each paragraph independently before finally aggregated and normalized with a global softmax operation to produce probabilities over spans. The second change is that we replace all attention mechanism in the original model with self attention layers over the concatenated question and context. To differentiate context paragraph representations from question representations in this self-attention mechanism, we indicate question and context tokens by concatenating a 0/1 feature at the input layer. Figure 4 illustrates the QA model architecture.  Table 2: End-to-end QA performance of baselines and our GOLDEN Retriever model on the HOTPOTQA fullwiki test set. Among systems that were not published at the time of submission of this paper, "BERT pip." was submitted to the official HOTPOTQA leaderboard on May 15 th (thus contemporaneous), while "Entity-centric BERT Pipeline" and "PR-Bert" were submitted after the paper submission deadline.
Answering Complex Open-domain Questions Through Iterative Query Generation
We evaluate our models in the fullwiki setting of HOTPOTQA (Yang et al., 2018). HOTPOTQA is a question answering dataset collected on the English Wikipedia, containing about 113k crowdsourced questions that are constructed to require the introduction paragraphs of two Wikipedia articles to answer. Each question in the dataset comes with the two gold paragraphs, as well as a list of sentences in these paragraphs that crowdworkers identify as supporting facts necessary to answer the question. A diverse range of reasoning strategies are featured in HOTPOTQA, including questions involving missing entities in the question (our Armada example), intersection questions (What satisfies property A and property B?), and comparison questions, where two entities are compared by a common attribute, among others. In the few-document distractor setting, the QA models are given ten paragraphs in which the gold paragraphs are guaranteed to be found; in the opendomain fullwiki setting, which we focus on, the models are only given the question and the entire Wikipedia. Models are evaluated on their answer accuracy and explainability, where the former is measured as overlap between the predicted and gold answers with exact match (EM) and unigram F 1 , and the latter concerns how well the predicted supporting fact sentences match human annotation (Supporting Fact EM/F 1 ). A joint metric is also reported on this dataset, which encourages systems to perform well on both tasks simultaneously.
Answering Complex Open-domain Questions Through Iterative Query Generation
We use the Stanford CoreNLP toolkit (Manning et al., 2014) to preprocess Wikipedia, as well as to generate POS/NER features for the query generators, following (Yang et al., 2018) and (Chen et al., 2017). We always detokenize a generated search query before sending it to Elasticsearch, which has its own preprocessing pipeline. Since all questions in HOTPOTQA require exactly two supporting documents, we fix the number of retrieval steps of GOLDEN Retriever to S = 2. To accommodate arbitrary steps of reasoning in GOLDEN Retriever, a stopping criterion is required to determine when to stop retrieving for more supporting documents and perform few-document question answering, which we leave to future work. During training and evaluation, we set the number of retrieved documents added to the retrieval context to 5 for each retrieval step, so that the total number of paragraphs our final QA model considers is 10, for a fair comparison to (Yang et al., 2018).
Answering Complex Open-domain Questions Through Iterative Query Generation
We include hyperparameters and training details in Appendix C for reproducibility.
Answering Complex Open-domain Questions Through Iterative Query Generation
We compare the end-to-end performance of GOLDEN Retriever against several QA systems on the HOTPOTQA dataset: (1) the baseline presented in (Yang et al., 2018), (2) CogQA (Ding et al., 2019), the top-performing previously published system, and (3) other high-ranking systems on the leaderboard. As shown in Table 2, GOLDEN Retriever is much better at locating the correct supporting facts from Wikipedia compared  to CogQA, as well as most of the top-ranking systems. However, the QA performance is handicapped because we do not make use of pretrained contextualization models (e.g., BERT) that these systems use. We expect a boost in QA performance from adopting these more powerful question answering models, especially ones that are tailored to perform few-document multi-hop reasoning. We leave this to future work.
Answering Complex Open-domain Questions Through Iterative Query Generation
To understand the contribution of GOLDEN Retriever's iterative retrieval process compared to that of the IR engine, we compare the performance of GOLDEN Retriever against two baseline systems on the dev set: one that retrieves 10 supporting paragraphs from Elasticsearch with the original question, and one that uses the IR engine presented in HOTPOTQA. 9 In all cases, we use the QA component in GOLDEN Retriever for the final question answering step. As shown in Table 3, replacing the hand-engineered IR engine in (Yang et al., 2018) with Elasticsearch does result in some gain in recall of the gold documents, but that does not translate to a significant improvement in QA performance. Further inspection reveals that despite Elasticsearch improving overall recall of gold documents, it is only able to retrieve both gold documents for 36.91% of the dev set questions, in comparison to 28.21% from the IR engine in (Yang et al., 2018). In contrast, GOLDEN Retriever improves this percentage to 61.01%, almost doubling the recall over the single-hop baseline, providing the QA component a much better set of context documents to predict answers from.
Answering Complex Open-domain Questions Through Iterative Query Generation
Lastly, we perform an ablation study in which we replace our query generator models with our query oracles and observe the effect on end-to-end  performance. As can be seen in Table 4, replacing G 1 with the oracle only slightly improves end-toend performance, but further substituting G 2 with the oracle yields a significant improvement. This illustrates that the performance loss is largely attributed to G 2 rather than G 1 , because G 2 solves a harder span selection problem from a longer retrieval context. In the next section, we examine the query generation models more closely by evaluating their performance without the QA component.
Answering Complex Open-domain Questions Through Iterative Query Generation
To evaluate the query generators, we begin by determining how well they emulate the oracles. We evaluate them using Exact Match (EM) and F 1 on the span prediction task, as well as compare their queries' retrieval performance against the oracle queries. As can be seen in Table 6, the performance of G 2 is worse than that of G 1 in general, confirming our findings on the end-to-end pipeline. When we combine them into a pipeline, the generated queries perform only slightly better on d 1 when a total of 10 documents are retrieved (89.91% vs 87.85%), but are significantly more effective for d 2 (61.01% vs 36.91%). If we further zoom in on the retrieval performance on noncomparison questions for which finding the two entities involved is less trivial, we can see that the recall on d 2 improves from 27.88% to 53.23%, almost doubling the number of questions we have the complete gold context to answer. We note that the IR performance we report on the full pipeline is different to that when we evaluate the query generators separately. We attribute this difference to the fact that the generated queries sometimes retrieve both gold documents in one step. To better understand model behavior, we also randomly sampled some examples from the dev set to compare the oracle queries and the predicted queries. Aside from exact matches, we find that the predicted queries are usually small variations of the oracle ones. In some cases, the model selects spans that are more natural and informative   Table 6: Span prediction and IR performance of the query generator models for Hop 1 (G 1 ) and Hop 2 (G 2 ) evaluated separately on the HOTPOTQA dev set.
Answering Complex Open-domain Questions Through Iterative Query Generation
(Example (1) in Table 5). When they differ a bit more, the model is usually overly biased towards shorter entity spans and misses out on informative information (Example (2)). When there are multiple entities in the retrieval context, the model sometimes selects the wrong entity, which suggests that a more powerful query generator might be desirable (Example (3)). Despite these issues, we find that these natural language queries make the reasoning process more interpretable, and easier for a human to verify or intervene as needed.
Answering Complex Open-domain Questions Through Iterative Query Generation
Limitations Although we have demonstrated that generating search queries with span selection works in most cases, it also limits the kinds of queries we can generate, and in some cases leads to undesired behavior. One common issue is that the entity of interest has a name shared by too many Wikipedia pages (e.g., "House Rules" the 2003 TV series). This sometimes results in the inclusion of extra terms in our oracle query to expand it (e.g., Example (4) specifies that "The Harmon" is a highrise building). In other cases, our span oracle makes use of too much information from the gold entities (Example (2), where a human would likely query for "Eiffel 65 song released 15 January 1999" because "Blue" is not the only song mentioned in d 1 ). We argue, though, these are due to the simplifying choice of span selection for query generation and fixed number of query steps. We leave extensions to future work.
Answering Complex Open-domain Questions Through Iterative Query Generation
In this paper, we presented GOLDEN (Gold Entity) Retriever, an open-domain multi-hop question answering system for scalable multi-hop reasoning. Through iterative reasoning and retrieval, GOLDEN Retriever greatly improves the recall of gold supporting facts, thus providing the question answering model a much better set of context documents to produce an answer from, and demonstrates competitive performance to the state of the art. Generating natural languages queries for each step of reasoning, GOLDEN Retriever is also more interpretable to humans compared to previous neural retrieval approaches and affords better understanding and verification of model behavior. We start from the Wikipedia dump file containing the introductory paragraphs used in HOTPOTQA that Yang et al. (2018) provide, 10 and add the fields corresponding to Wikipedia page titles and the introductory paragraphs (text) into the index.
Answering Complex Open-domain Questions Through Iterative Query Generation
For the title, we use Elasticsearch's simple analyzer which performs basic tokenization and lowercasing of the content. For the text, we join all the sentences and use the standard analyzer which further allows for removal of punctuation and stop words. For both fields, we index an auxiliary field with bigrams using the shingle filter, 11 and perform basic asciifolding to map non ASCII characters to a similar ASCII character (e.g., "é"→ "e").
Answering Complex Open-domain Questions Through Iterative Query Generation
At search time, we launch a multi match query against all fields with the same query, which performs a full-text query employing the BM25 ranking function (Robertson et al., 1995) with all fields in the index, and returns the score of the best field for ranking by default. To promote documents whose title match the search query, we boost the search score of all title-related fields by 1.25 in this query.
Answering Complex Open-domain Questions Through Iterative Query Generation
In Wikipedia, it is common that pages or entity names share rare words that are important to search engines, and a naive full-text search IR system will not be able to pick the one that matches the query the best. For instance, if one set up Elasticsearch according to the instructions above and searched for "George W. Bush", he/she would be surprised to see that the actual page is not even in the top-10 search results, which contains entities such as "George W. Bush Childhood Home" and "Bibliography of George W. Bush".
Answering Complex Open-domain Questions Through Iterative Query Generation
To this end, we propose to rerank these query results with a simple but effective heuristic that alleviates this issue. We would first retrieve at least 50 candidate documents for each query for consideration, and boost the query scores of documents whose title exactly matches the search query, or is a substring of the search query. Specifically, we  multiply the document score by a heuristic constant between 1.05 and 1.5, depending on how well the document title matches the query, before reranking all search results. This results in a significant improvement in these cases. For the query "George W. Bush", the page for the former US president is ranked at the top after reranking. In Table 7, we also provide results from the singlehop query to show the improvement from title score boosting introduced from the previous section and reranking.
Answering Complex Open-domain Questions Through Iterative Query Generation
We mainly employ three heuristics to find the semantic overlap between the retrieval context and the desired documents: longest common subsequence (LCS), longest common substring (LC-SubStr), and overlap merging which generalizes the two. Specifically, the overlap merging heuristic looks for contiguous spans in the retrieval context that have high rates of overlapping tokens with the desired document, determined by the total number of overlapping tokens divided by the total number of tokens considered in the span. In all heuristics, we ignore stop words and lowercase the rest in computing the spans to capture more meaningful overlaps, and finally take the span in the retrieval context that all the overlapping words are contained in. For instance, if the retrieval context contains "the GOLDEN Retriever model on HOTPOTQA" and the desired document contains "GOLDEN Retriever on the HOTPOTQA dataset", we will identify the overlapping terms as "GOLDEN", "Retriever", and "HOTPOTQA", and return the span "GOLDEN Retriever model on HOTPOTQA" as the resulting candidate query.
Answering Complex Open-domain Questions Through Iterative Query Generation
To generate candidates for the oracle query, we apply the heuristics between combinations of {cleaned question, cleaned question without punc-tuation} × {cleaned document title, cleaned para-graph}, where cleaning means stop word removal and lowercasing. Once oracle queries are gener-  ated, we launch these queries against Elasticsearch to determine the rank of the desired paragraph. If multiple candidate queries are able to place the desired paragraph in the top 5 results, we further rank the candidate queries by other metrics (e.g., length of the query) to arrive at the final oracle query to train the query generators. We refer the reader to our released code for further details.
Answering Complex Open-domain Questions Through Iterative Query Generation
C Training Details
Answering Complex Open-domain Questions Through Iterative Query Generation
Once the oracle queries are generated, we train our query generators to emulate them on the training set, and choose the best model with F 1 in span selection on the dev set. We experiment with hyperparameters such as learning rate, training epochs, batch size, number of word embeddings to finetune, among others, and report the final hyperparameters for both query generators (G 1 and G 2 ) in Table 8.
Answering Complex Open-domain Questions Through Iterative Query Generation
Our final question answering component is trained with the paragraphs produced by the oracle queries (5 from each hop, 10 in total), with d 1 and d 2 inserted to replace the lowest ranking paragraph in each hop if they are not in the set already. We develop our model based on the baseline model of Yang et al. (2018), and reuse the same default hyperparameters whenever possible. The main differences in the hyperparameters are: we optimize our QA model with Adam (with default hyperparameters) (Kingma and Ba, 2015) instead of stochastic gradient descent with a larger batch size of 64; we anneal the learning rate by 0.5 with a patience of 3 instead of 1, that is, we multiply the learning rate by 0.5 after three consecutive failures to improve dev F 1 ; we clip the gradient down to a maximum 2 norm of 5; we apply a 10% dropout to the model, for which we have increased the hidden size to 128; and use 10 as the coefficient by which we multiply the supporting facts loss, before mixing it with the span prediction loss. We configure the model to read 10 context paragraphs, and limit each paragraph to at most 400 tokens including the title.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Open-domain Question Answering (QA) is the task of answering a question given a large collection of text documents (e.g., Wikipedia). Most state-of-the-art approaches for open-domain QA (Chen et al., 2017;Wang et al., 2018a;Lee et al., 2018;Yang et al., 2019) leverage non-parameterized models (e.g., TF-IDF or BM25) to retrieve a fixed set of documents, where an answer span is extracted by a neural reading comprehension model. Despite the success of these pipeline methods in singlehop QA, whose questions can be answered based on a single paragraph, they often fail to retrieve the required evidence for answering multi-hop questions, e.g., the question in Figure 1. Multi-hop QA (Yang et al., 2018) usually requires finding more than one evidence document, one of which often consists of little lexical overlap or semantic relationship to the original question. However, retrieving a fixed list of documents independently does not capture relationships between evidence documents through bridge entities that are required for multi-hop reasoning.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Recent open-domain QA methods learn end-to-end models to jointly retrieve and read documents (Seo et al., 2019;Lee et al., 2019). These methods, however, face challenges for entity-centric questions since compressing the necessary information into an embedding space does not capture lexical information in entities. Cognitive Graph (Ding et al., 2019) incorporates entity links between documents for multi-hop QA to extend the list of retrieved documents. This method, however, compiles a fixed list of documents independently and expects the reader to find the reasoning paths.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
In this paper, we introduce a new recurrent graph-based retrieval method that learns to retrieve evidence documents as reasoning paths for answering complex questions. Our method sequentially retrieves each evidence document, given the history of previously retrieved documents to form several reasoning paths in a graph of entities. Our method then leverages an existing reading comprehension model to answer questions by ranking the retrieved reasoning paths. The strong interplay between the retriever model and reader model enables our entire method to answer complex questions by exploring more accurate reasoning paths compared to other methods. To be more specific, our method (sketched in Figure 2) constructs the Wikipedia paragraph graph using Wikipedia hyperlinks and document structures to model the relationships between paragraphs. Our retriever trains a recurrent neural network to score reasoning paths in this graph by maximizing the likelihood of selecting a correct evidence paragraph at each step and fine-tuning paragraph BERT encodings. Our reader model is a multi-task learner to score each reasoning path according to its likelihood of containing and extracting the correct answer phrase. We leverage data augmentation and negative example mining for robust training of both models.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Our experimental results show that our method achieves the state-of-the-art results on HotpotQA full wiki and HotpotQA distractor settings (Yang et al., 2018), outperforming the previous stateof-the-art methods by more than 14 points absolute gain on the full wiki setting. We also evaluate our approach on SQuAD Open (Chen et al., 2017) and Natural Questions Open (Lee et al., 2019) without changing any architectural designs, achieving better or comparable to the state of the art, which suggests that our method is robust across different datasets. Additionally, our framework provides interpretable insights into the underlying entity relationships used for multi-hop reasoning.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Neural open-domain question answering Most current open-domain QA methods use a pipeline approach that includes a retriever and reader. Chen et al. (2017) incorporate a TF-IDF-based retriever with a state-of-the-art neural reading comprehension model. The subsequent work improves the heuristic retriever by re-ranking retrieved documents (Wang et al., 2018a;b;Lee et al., 2018;Lin et al., 2018). The performance of these methods is still bounded by the performance of the initial retrieval process. In multi-hop QA, non-parameterized retrievers face the challenge of retrieving all the relevant documents, one or some of which are lexically distant from the question. Recently, Lee et al. (2019) and Seo et al. (2019) introduce fully trainable models that retrieve a few candidates directly from large-scale Wikipedia collections. All these methods find evidence documents independently without the knowledge of previously selected documents or relationships between documents. This would result in failing to conduct multi-hop retrieval.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Retrievers guided by entity links Most relevant to our work are recent studies that attempt to use entity links for multi-hop open-domain QA. Cognitive Graph (Ding et al., 2019) retrieves evidence documents offline, and trains a reading comprehension model to jointly predict possible answer spans and next-hop spans to extend the reasoning chain. Instead, we train our retriever to find reasoning paths directly. Concurrent with our work, Entity-centric IR (Godbole et al., 2019) uses entity linking for multi-hop retrieval. Unlike our method, this method does not learn to retrieve reasoning paths sequentially, nor study the interplay between retriever and reader. Moreover, while the previous approaches require a system to encode all possible nodes, our beam search decoding process only encodes the nodes on the reasoning paths, which significantly reduces the computational costs. PullNet (Sun et al., 2019) learns to retrieve question-aware sub-graphs from text corpora and knowledge bases (e.g., Freebase), while we focus on open-domain QA solely based on text.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Multi-step (iterative) retrievers Similar to our recurrent retriever, multi-step retrievers explore multiple evidence documents iteratively. Multi-step reasoner  repeats the retrieval process for a fixed number of steps, interacting with a reading comprehension model by reformulating the query in a latent space to enhance retrieval performance. Feldman & El-Yaniv (2019)   structure of the documents during the iterative retrieval process. In addition, all of these multi-step retrieval methods do not accommodate arbitrary steps of reasoning and the termination condition is hard-coded. In contrast, our method leverages the Wikipedia graph to retrieve documents that are lexically or semantically distant to questions, and is adaptive to any reasoning path lengths, which leads to significant improvement over the previous work in HotpotQA and SQuAD Open.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Overview This paper introduces a new graph-based recurrent retrieval method (Section 3.1) that learns to find evidence documents as reasoning paths for answering complex questions. We then extend an existing reading comprehension model (Section 3.2) to answer questions given a collection of reasoning paths. Our method uses a strong interplay between retrieving and reading steps such that the retrieval method learns to retrieve a set of reasoning paths to narrow down the search space for our reader model, for robust pipeline process. Figure 2 sketches the overview of our QA model. We use Wikipedia for open-domain QA, where each article is divided into paragraphs, resulting in millions of paragraphs in total. Each paragraph p is considered as our retrieval target. Given a question q, our framework aims at deriving its answer a by retrieving and reading reasoning paths, each of which is represented with a sequence of paragraphs: E = [p i , . . . , p k ]. We formulate the task by decomposing the objective into the retriever objective S retr (q, E) that selects reasoning paths E relevant to the question, and the reader objective S read (q, E, a) that finds the answer a in E:
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Our method learns to retrieve reasoning paths across a graph structure. Evidence paragraphs for a complex question do not necessarily have lexical overlaps with the question, but one of them is likely to be retrieved, and its entity mentions and the question often entail another paragraph (e.g., Figure 1). To perform such multi-hop reasoning, we first construct a graph of paragraphs, covering all the Wikipedia paragraphs. Each node of the Wikipedia graph G represents a single paragraph p i .
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Constructing the Wikipedia graph Hyperlinks are commonly used to construct relationships between articles on the web, usually maintained by article writers, and are thus useful knowledge resources. Wikipedia consists of its internal hyperlinks to connect articles. We use the hyperlinks to construct the direct edges in G. We also consider symmetric within-document links, allowing a paragraph to hop to other paragraphs in the same article. The Wikipedia graph G is densely connected and covers a wide range of topics that provide useful evidence for open-domain questions. This graph is constructed offline and is reused throughout training and inference for any question.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
General formulation with a recurrent retriever We use a Recurrent Neural Network (RNN) to model the reasoning paths for the question q. At the t-th time step (t ≥ 1) our model selects a paragraph p i among candidate paragraphs C t given the current hidden state h t of the RNN. The initial hidden state h 1 is independent of any questions or paragraphs, and based on a parameterized vector. We use BERT's [CLS] token representation  to independently encode each candidate paragraph p i along with q. 2 We then compute the probability P (p i |h t ) that p i is selected. The RNN selection procedure captures relationships between paragraphs in the reasoning path by conditioning on the selection history. The process is terminated when [EOE], the end-ofevidence symbol, is selected, to allow it to capture reasoning paths with arbitrary length given each question. More specifically, the process of selecting p i at the t-th step is formulated as follows:
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
where b ∈ R 1 is a bias term. Motivated by Salimans & Kingma (2016), we normalize the RNN states to control the scale of logits in Equation (3) and allow the model to learn multiple reasoning paths. The details of Equation (4) are described in Appendix A.1. The next candidate set C t+1 is constructed to include paragraphs that are linked from the selected paragraph p i in the graph. To allow our model to flexibly retrieve multiple paragraphs within C t , we also add K-best paragraphs other than p i (from C t ) to C t+1 , based on the probabilities. We typically set K = 1 in this paper.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Beam search for candidate paragraphs It is computationally expensive to compute Equation (2) over millions of the possible paragraphs. Moreover, a fully trainable retriever often performs poorly for entity-centric questions such as SQuAD, since it does not explicitly maintain lexical information (Lee et al., 2019). To navigate our retriever in the large-scale graph effectively, we initialize candidate paragraphs with a TF-IDF-based retrieval and guide the search over the Wikipedia graph. In particular, the initial candidate set C 1 includes F paragraphs with the highest TF-IDF scores with respect to the question. We expand C t (t ≥ 2) by appending the [EOE] symbol. We additionally use a beam search to explore paths in the directed graph. We define the score of a reasoning path E = [p i , . . . , p k ] by multiplying the probabilities of selecting the paragraphs: P (p i |h 1 ) . . . P (p k |h |E| ). The beam search outputs the top B reasoning paths E = {E 1 , . . . , E B } with the highest scores to pass to the reader model i.e., S(q, E, a) = S read (q, E, a) for E ∈ E.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
In terms of the computational cost, the number of the paragraphs processed by Equation (2) is bounded by O(|C 1 | + B t≥2 |C t |), where B is the beam size and |C t | is the average size of C t over the B hypothesises.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
3.1.2 TRAINING OF THE GRAPH-BASED RECURRENT RETRIEVER Data augmentation We train our retriever in a supervised fashion using evidence paragraphs annotated for each question. For multi-hop QA, we have multiple paragraphs for each question, and single paragraph for single-hop QA. We first derive a ground-truth reasoning path g = [p 1 , . . . , p |g| ] using the available annotated data in each dataset. p |g| is set to [EOE] for the termination condition.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
To relax and stabilize the training process, we augment the training data with additional reasoning paths -not necessarily the shortest paths -that can derive the answer. In particular, we add a new training path g r = [p r , p 1 , . . . , p |g| ] by adding a paragraph p r ∈ C 1 that has a high TF-IDF score and is linked to the first paragraph p 1 in the ground-truth path g. Adding these new training paths helps at the test time when the first paragraph in the reasoning path does not necessarily appear among the paragraphs that initialize the Wikipedia search using the heuristic TF-IDF retrieval.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Negative examples for robustness Our graph-based recurrent retriever needs to be trained to discriminate between relevant and irrelevant paragraphs at each step. We therefore use negative examples along with the ground-truth paragraphs; to be more specific, we use two types of negative examples: (1) TF-IDF-based and (2) hyperlink-based ones. For single-hop QA, we only use the type (1). For multi-hop QA, we use both types, and the type (2) is especially important to prevent our retriever from being distracted by reasoning paths without correct answer spans. We typically set the number of the negative examples to 50.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Loss function For the sequential prediction task, we estimate P (p i |h t ) independently in Equation (3) and use the binary cross-entropy loss to maximize probability values of all the possible paths. Note that using the widely-used cross-entropy loss with the softmax normalization over C t is not desirable here; maximizing the probabilities of g and g r contradict with each other. More specifically, the loss function of g at the t-th step is defined as follows:
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
whereC t is a set of the negative examples described above, and includes [EOE] for t < |g|. We exclude p r fromC 1 for the sake of our multi-path learning. The loss is also defined with respect to g r in the same way. All the model parameters, including those in BERT, are jointly optimized.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Our reader model first verifies each reasoning path in E, and finally outputs an answer span a from the most plausible reasoning path. This interplay is effective in making our framework robust; this is further discussed in Appendix A.3. We model the reader as a multi-task learning of (1) reading comprehension, that extracts an answer span from a reasoning path E using a standard approach (Seo et al., 2017;Xiong et al., 2017;, and (2) reasoning path re-ranking, that re-ranks the retrieved reasoning paths by computing the probability that the path includes the answer.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
For the reading comprehension task, we use BERT , where the input is the concatenation of the question text and the text of all the paragraphs in E. This lets our reader to fully leverage the self-attention mechanism across the concatenated paragraphs in the retrieved reasoning paths; this paragraph interaction is crucial for multi-hop reasoning (Wang et al., 2019a).
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We share the same model for re-ranking, and use the BERT's [CLS] representation to estimate the probability of selecting E to answer the question:
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
where w n ∈ R D is a weight vector. At the inference time, we select the best evidence E best ∈ E by P (E|q), and output the answer span by S read :
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
where P start i , P end j denote the probability that the i-th and j-th tokens in E best are the start and end positions, respectively, of the answer span, and are calculated by following .
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Training examples To train the multi-task reader model, we use the ground-truth evidence paragraphs used for training our retriever. It is known to be effective in open-domain QA to use distantly supervised examples, which are not originally associated with the questions but include expected answer strings (Chen et al., 2017;Wang et al., 2018a;Hu et al., 2019). These distantly supervised examples are also effective to simulate the inference time process. Therefore, we combine distantly supervised examples from a TF-IDF retriever with the original supervised examples. Following the procedures in Chen et al. (2017), we add up to one distantly supervised example for each supervised example. We set the answer span as the string that matches a and appears first.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
To train our reader model to discriminate between relevant and irrelevant reasoning paths, we augment the original training data with additional negative examples to simulate incomplete evidence. In particular, we add paragraphs that appear to be relevant to the given question but actually do not contain the answer. For multi-hop QA, we select one ground-truth paragraph including the answer span, and swap it with one of the TF-IDF top ranked paragraphs. For single-hop QA, we simply replace the single ground-truth paragraph with TF-IDF-based negative examples which do not include the expected answer string. For the distorted evidenceẼ, we aim at minimizing P (Ẽ|q).
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
The objective is the sum of cross entropy losses for the span prediction and re-ranking tasks. The loss for the question q and its evidence candidate E is as follows:
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
where y start and y end are the ground-truth start and end indices, respectively. L no answer corresponds to the loss of the re-ranking model, to discriminate the distorted reasoning paths with no answers. P r is P (E|q) if E is the ground-truth evidence; otherwise P r = 1 − P (E|q Each answer can be extracted from a collection of 10 paragraphs in the distractor setting, and from the entire Wikipedia in the full wiki setting. Two evidence paragraphs are associated with each question for training. Our primary target is the full wiki setting due to its open-domain scenario, and we use the distractor setting to evaluate how well our method works in a closed scenario where the two evidence paragraphs are always included. The dataset also provides annotations to evaluate the prediction of supporting sentences, and we adapt our retriever to the supporting fact prediction. Note that this subtask is specific to HotpotQA. More details are described in Appendix A.5.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
SQuAD Open SQuAD Open (Chen et al., 2017) is composed of questions from the original SQuAD dataset (Rajpurkar et al., 2016). This is a single-hop QA task, and a single paragraph is associated with each question in the training data.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Natural Questions Open Natural Questions Open (Lee et al., 2019) is composed of questions from the Natural Questions dataset (Kwiatkowski et al., 2019), 3 which is based on Google Search queries independently from the existing articles. A single paragraph is associated with each question, but our preliminary analysis showed that some questions benefit from multi-hop reasoning.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Metrics We report standard F1 and EM scores for HotpotQA and SQuAD Open, and EM score for Natural Questions Open to evaluate the overall QA accuracy to find the correct answers. For Hot-potQA, we also report Supporting Fact F1 (SP F1) and Supporting Fact EM (SP EM) to evaluate the sentence-level supporting fact retrieval accuracy. To evaluate the paragraph-level retrieval accuracy for the multi-hop reasoning, we use the following metrics: Answer Recall (AR), which evaluates the recall of the answer string among top paragraphs (Wang et al., 2018a;, Paragraph Recall (PR), which evaluates if at least one of the ground-truth paragraphs is included among the retrieved paragraphs, and Paragraph Exact Match (P EM), which evaluates if both of the ground-truth paragraphs for multi-hop reasoning are included among the retrieved paragraphs.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Evidence Corpus and the Wikipedia graph We use English Wikipedia as the evidence corpus and do not use other data such as Google search snippets or external structured knowledge bases. We use the several versions of Wikipedia dumps for the three datasets (See Appendix B.5). To construct the Wikipedia graph, the hyperlinks are automatically extracted from the raw HTML source files. Directed edges are added between a paragraph p i and all of the paragraphs included in the target article. The constructed graph consists of 32.7M nodes and 205.4M edges. For HotpotQA we only use the introductory paragraphs in the graph that includes about 5.2M nodes and 23.4M edges.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We use the pre-trained BERT models  using the uncased base configuration (d = 768) for our retriever and the whole word masking uncased large (wwm) configuration (d = 1024) for our readers. We follow Chen et al. (2017) for the TF-IDF-based retrieval model and use the same hyper-parameters. We tuned the most important hyper-parameters, F , the number of the initial TF-IDF-based paragraphs, and B, the beam size, by mainly using the HotpotQA development set (the effects of increasing F are shown in Figure 5 in Appendix C.3 along with the results with B = 1). If not specified, we set B = 8 for all the datasets, F = 500 for HotpotQA full wiki and SQuAD Open, and F = 100 for Natural Questions Open. Moreover, our method shows significant improvement in predicting supporting facts in the full wiki setting. We compare the performance of our approach to other models on the HotpotQA full wiki official hidden test set in Table 2. We outperform all the published and unpublished models including up-to-date work (marked with ♣ ) by large margins in terms of QA performance.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
On SQuAD Open, our model outperforms the concurrent state-of-the-art model (Wang et al., 2019b) by 2.9 F1 and 3.5 EM scores as shown in Table 3. Due to the fewer lexical overlap between questions and paragraphs on Natural Questions, pipelined approaches using term-based retrievers often face difficulties finding associated articles. Nevertheless, our approach matches the performance of the best end-to-end retriever (ORQA), as shown in Table 4. In addition to its competitive performance, our retriever can be handled on a single GPU machine, while a fully end-to-end retriever in general requires industry-scale computational resources for training (Seo et al., 2019). More results on these two datasets are discussed in Appendix D.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We compare our retriever with competitive retrieval methods for HotpotQA full wiki, with F = 20.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
TF-IDF (Chen et al., 2017), the widely used retrieval method that scores paragraphs according to the TF-IDF scores of the question-paragraph pairs. We simply select the top-2 paragraphs. Re-rank (Nogueira & Cho, 2019) that learns to retrieve paragraphs by fine-tuning BERT to re-rank the top F TF-IDF paragraphs. We select the top-2 paragraphs after re-ranking. Re-rank 2hop which extends Re-rank to accommodate two-hop reasoning. It first adds paragraphs linked from the top TF-IDF paragraphs. It then uses the same BERT model to select the paragraphs. Entity-centric IR is our re-implementation of Godbole et al. (2019) that is related to Re-rank 2hop, but instead of simply selecting the top two paragraphs, they re-rank the possible combinations of the paragraphs that are linked to each other. Retrieval results Table 5 shows that our recurrent retriever yields 8.8 P EM and 9.     Re-rank2hop to Entity-centric IR demonstrates that exploring entity links from the initially retrieved documents helps to retrieve the paragraphs with fewer lexical overlaps. On the other hand, comparing our retriever with Entity-centric IR and Semantic Retrieval shows the importance of learning to sequentially retrieve reasoning paths in the Wikipedia graph. It should be noted that our method with F = 20 outperforms all the QA EM scores in Table 1.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We conduct detailed analysis of our framework on the HotpotQA full wiki development set.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Ablation study of our framework To study the effectiveness of our modeling choices, we compare the performance of variants of our framework. We ablate the retriever with 1) No recurrent module, which removes the recurrence from our retriever, and computes the probability of each paragraph to be included in reasoning paths independently and selects the path with the highest joint probability path on the graph; 2) No beam search, which uses a greedy search (B = 1) in our recurrent retriever ;       Ablation results Table 6 shows that removing any of the listed components gives notable performance drop. The most critical component in our retriever model is the recurrent module, dropping the EM by 17.4 points. As shown in Figure 1, multi-step retrieval often relies on information mentioned in another paragraph. Therefore, without conditioning on the previous time steps, the model fails to retrieve the complete evidence. Training without hyperlink-based negative examples results in the second largest performance drop, indicating that the model can be easily distracted by reasoning paths without a correct answer and the importance of negative sampling for training. Replacing the beam search with the greedy search gives a performance drop of about 4 points on EM, which demonstrates that being aware of the graph structure is helpful in finding the best reasoning paths.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Performance drop by removing the reasoning path re-ranking indicates the importance of verifying the reasoning paths in our reader. Not using negative examples to train the reader degrades EM more than 16 points, due to the over-confident predictions as discussed in Clark & Gardner (2018).
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
The performance with an off-the-shelf entity linking system Although the existence of the hyperlinks is not special on the web, one question is how well our method works without the Wikipedia hyperlinks. We evaluate our method on the development set of HotpotQA full wiki with an off-theshelf entity linking system (Ferragina & Scaiella, 2011) to construct the document graph in our method. More details about this experimental setup can be found in Appendix B.7. Table 7 shows that our approach with the entity linking system shows only 2.3 F1 and 2.2 EM lower scores than those with the hyperlinks, still achieving the state of the art. This suggests that our approach is not restricted to the existence of the hyperlink information, and using hyperlinks is promising.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
The effectiveness of arbitrary-step retrieval The existing iterative retrieval methods fix the number of reasoning steps (Qi et al., 2019;Godbole et al., 2019;Feldman & El-Yaniv, 2019), while our approach accommodates arbitrary steps of reasoning. We also evaluate our method by fixing the length of the reasoning path (L = {1, 2, 3, 4}). Table 8 shows that out adaptive retrieval performs the best, although the length of all the annotated reasoning paths in HotpotQA is two. As discussed in Min et al. (2019b), we also observe that some questions are answerable based on a single paragraph, where our model flexibly selects a single paragraph and then terminates retrieval.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
The effectiveness of the interplay between retriever and reader Table 6 shows that the interplay between our retriever and reader models is effective. To understand this, we investigate the length of reasoning paths selected by our retriever and reader, and their final QA performance. Table 9 shows that the average length selected by our reader is notably longer than that by our retriever. Table 9 also presents the EM scores averaged over the questions with certain length of reasoning paths  The 2017-18 Wigan Athletic F.C. season will be a year in which the team competes in the league cup known as what for sponsorship reasons?
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
The EFL Cup, currently known as the FA Cup EFL Cup Carabao Cup for sponsorship reasons...
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
The 2017-18 season is Wigan Athletic's ... their first back in League One ..., the club will also participate in the FA Cup, EFL Cup and EFL Trophy.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
2017-18 Wigan Athletic F.C. Figure 4: Reasoning examples by our retriever (the bottom paragraph) and our reader (two paragraphs connected by a dotted line). Highlighted text denotes a bridge entity, and blue-underlined text represents hyperlinks.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
(L = {1, 2, 3}). We observe that our framework performs the best when it selects the reasoning paths with L = 3, showing 63.0 EM score. Based on these observations, we expect the retriever favors a shorter path, while the reader tends to select a longer and more convincing multi-hop reasoning path to derive an answer string.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Qualitative examples of retrieved reasoning paths Finally, we show two examples from Hot-potQA full wiki, and Appendix C.5 presents more qualitative examples. In Figure 3, our approach successfully retrieves the correct reasoning path and answers correctly, while Re-rank fails. The top two paragraphs next to the graph are the introductory paragraphs of the two entities on the reasoning path, and the paragraph at the bottom shows the wrong paragraph selected by Re-rank. The "Millwall F.C." has fewer lexical overlaps and the bridge entity "Millwall" is not stated in the given question. Thus, Re-rank chooses a wrong paragraph with high lexical overlaps to the given question.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
In Figure 4, we compare the reasoning paths ranked highest by our retriever and reader. Although the gold path is included among the top 8 paths selected by the beam search, our retriever model selects a wrong paragraph as the best reasoning path. By re-ranking the reasoning paths, the reader eventually selects the correct reasoning path ("2017-18 Wigan Athletic F.C. season" → "EFL Cup"). This example shows the effectiveness of the strong interplay of our retriever and reader.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
This paper introduces a new graph-based recurrent retrieval approach, which retrieves reasoning paths over the Wikipedia graph to answer multi-hop open-domain questions. Our retriever model learns to sequentially retrieve evidence paragraphs to form the reasoning path. Subsequently, our reader model re-ranks the reasoning paths, and it determines the final answer as the one extracted from the best reasoning path. Our experimental results significantly advance the state of the art on HotpotQA by more than 14 points absolute gain on the full wiki setting. Our approach also achieves the state-of-the-art performance on SQuAD Open and Natural Questions Open without any architectural changes, demonstrating the robustness of our method. Our method provides insights into the underlying entity relationships, and the discrete reasoning paths are helpful in interpreting our framework's reasoning process. Future work involves end-to-end training of our graph-based recurrent retriever and reader for improving upon our current two-stage training.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We acknowledge grants from ONR N00014-18-1-2826, DARPA N66001-19-2-403, NSF (IIS1616112, IIS1252835), and Samsung GRO. We thank Sewon Min, David Wadden, Yizhong Wang, Akhilesh Gotmare, Tong Niu, and UW NLP group and Salesforce research members for their insightful discussions. We would also like to show our gratitude to Melvin Gruesbeck for providing us with the artistic figures presented in this paper. We thank the anonymous reviewers for their helpful and thoughtful comments. Akari Asai is supported by The Nakajima Foundation Fellowship. 
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
where W r ∈ R d×2d is a weight matrix, b r ∈ R d is a bias vector, and α ∈ R 1 is a scalar parameter (initialized with 1.0). We set the global initial state a 1 to a parameterized vector s ∈ R d , and we also parameterize an [EOE] vector w [EOE] ∈ R d for the [EOE] symbol. The use of w i for both the input and output layers is inspired by Inan et al. (2017); Press & Wolf (2017). In addition, we align the norm of w [EOE] with those of w i , by applying layer normalization (Ba et al., 2016) of the last layer in BERT because w [EOE] is used along with the BERT outputs. Without the layer normalization, the L2-norms of w i and w [EOE] can be quite different, and the model can easily discriminate between them by the difference of the norms.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Equation (2) shows that we compute each paragraph representation w i conditioned on the question q. An alternative approach is separately encoding the paragraphs and the question, to directly retrieve paragraphs (Lee et al., 2019;Seo et al., 2019;. However, due to the lack of explicit interactions between the paragraphs and the question, such a neural retriever using questionindependent paragraph encodings suffers from compressing the necessary information into fixeddimensional vectors, resulting in low performance on entity-centric questions (Lee et al., 2019). It has been shown that attention-based paragraph-question interactions improve the retrieval accuracy if the retrieval scale is tractable (Wang et al., 2018a;Lee et al., 2018). There is a trade-off between the scalability and the accuracy, and this work aims at striking the balance by jointly using the lexical matching retrieval and the graphs, followed by the rich question-paragraph encodings.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
A question-independent variant We can also formulate our retriever model by using a questionindependent approach. There are only two simple modifications. First, we reformulate Equation (2) as follows:
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
where we no longer input the question q together with the paragraphs. Next, we condition the initial RNN state h 1 on the question information. More specifically, we compute h 1 by using Equation (4) as follows:
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
where w q is computed by using the same BERT encoder as in Equation (10), and h 1 is the original h 1 used in our question-dependent approach as described in Appendix A.1. The remaining parts are exactly the same, and we can perform the reasoning path retrieval in the same manner.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Our retriever model learns to predict plausibility of the reasoning paths by capturing the paragraph interactions through the BERT's [CLS] representations, after independently encoding the paragraphs along with the question; this makes our retriever scalable to the open-domain scenario. By contrast, our reader jointly learns to predict the plausibility and answer the question, and moreover, fully leverages the self-attention mechanism across the concatenated paragraphs in the retrieved reasoning paths; this paragraph interaction is crucial for multi-hop reasoning (Wang et al., 2019a). In summary, our retriever is scalable, but the top-1 prediction is not always enough to fully capture multi-hop reasoning to answer the question. Therefore, the additional re-ranking process mitigates the uncertainty and makes our framework more robust.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
In the HotpotQA dataset, we need to handle yes-no questions as well as extracting answer spans from the paragraphs. We treat the two special types of the answers, yes and no, by extending the re-ranking model in Equation (6). In particular, we extend the binary classification to a multi-class classification task, where the positive "answerable" class is decomposed into the following three classes: span, yes, and no. If the probability of "yes" or "no" is the largest among the three classes, our reader directly outputs the label as the answer, without any span extraction. Otherwise, our reader uses the span extraction model to output the answer.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We adapt our recurrent retriever to the subtask of the supporting fact prediction in HotpotQA (Yang et al., 2018). The task is outputting sentences which support to answer the question. Such supporting sentences are annotated for the two ground-truth paragraphs in the training data. Since our framework outputs the most plausible reasoning path E along with the answer, we can add an additional step to select supporting facts (sentences) from the paragraphs in E. We train our recurrent retriever by using the training examples for the supporting fact prediction task, where the model parameters are not shared with those of our paragraph retriever. We replace the question-paragraph encoding in Equation (2) with question-answer-sentence encoding for the task, where a question string is concatenated with its answer string. The answer string is the ground-truth one during the training time. We then maximize the probability of selecting the ground-truth sequence of the supporting fact sentences, while setting the other sentences as negative examples. At test time, we use the best reasoning path and its predicted answer string from our retriever and reader models to finally output the supporting facts for each question. The supporting fact prediction task is performed after finalizing the reasoning path and the answer for each question, and hence this additional task does not affect the QA accuracy.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
HotpotQA The HotpotQA training, development, and test datasets contain 90,564, 7,405 and 7,405 questions, respectively. To train our retriever model for the distractor setting, we use the distractor training data, where only the original ten paragraphs are associated with each question. The retriever model trained with this setting is also used in our ablation study as "retriever, no linkbased negatives" in Table 6. For the full wiki setting, we train our retriever model with the data augmentation technique and the additional negative examples described in Section 3.1.2. We use the same reader model, for both the settings, trained with the augmented additional references and the negative examples described in Section 3.2. 
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Section 3.1.2 describes our training strategy for our recurrent retriever. We apply the data augmentation technique to HotpotQA and Natural Questions to consider multi-hop reasoning. To derive the ground-truth reasoning path g, we use the ground-truth evidence paragraphs associated with the questions in the training data for each dataset. For SQuAD and Natural Questions Open, each training example has only single paragraph p, and thus it is trivial to derive g as [p, [EOE]]. For the multi-hop case, HotpotQA, we have two ground-truth paragraphs p 1 , p 2 for each question. Assuming that p 2 includes the answer string, we set g = [p 1 , p 2 , [EOE]].
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
To train our reader model for SQuAD Open, in addition to the TF-IDF top-ranked paragraphs, we add two types of additional negative examples: (i) paragraphs, which do not include the answer string, from the originally annotated articles, and (ii) "unanswerable" questions from SQuAD 2.0 (Rajpurkar et al., 2018). For Natural Questions Open, we add negative examples of the type (i).
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
To use the pre-trained BERT models, we used the public code base, pytorch-transformers, 4 written in PyTorch. 5 For optimization, we used the code base's implementation of the Adam optimizer (Kingma & Ba, 2015), with a weight-decay coefficient of 0.01 for non-bias parameters. A warm-up strategy in the code base was also used, with a warm-up rate of 0.1. Most of the settings follow the default settings. To train our recurrent retriever, we set the learning rate to 3 · 10 −5 , and the maximum number of the training epochs to three. The mini-batch size is four; a mini-batch example consists of a question with its corresponding paragraphs. To train our reader model, we set the learning rate to 3 · 10 −5 , and the maximum number of training epochs to two. Empirically we observe better performance with a larger batch size as discussed in previous work (Liu et al., 2019;Ott et al., 2018), and thus we set the mini-batch size to 120. A mini-batch example consists of a question with its evidence paragraphs. We will release our code to follow our experiments. Although using a single dump for different open-domain QA datasets is a common practice (Chen et al., 2017;Wang et al., 2018a;Lee et al., 2018), this potentially causes inconsistent or even unfair evaluation across different experimental settings, due to the temporal inconsistency of the Wikipedia articles. More concretely, every Wikipedia article is editable and and as a result, a fact can be rephrased or could be removed. For instance, a question from the SQuAD development set, "Where does Kenya rank on the CPI scale?" is originally paired with a paragraph from the article of Kenya. Based on a single sentence "Kenya ranks low on Transparency International's Corruption Perception Index (CPI)" from the paragraph, an annotated answer span is "low." However, this sentence has been rewritten as "Kenya has a high degree of corruption according to Transparency International's Corruption Perception Index (CPI)" in a later version of the same article. 7 This is problematic considering the major evaluation metrics based on string matching.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Another problem exists especially in Natural Questions Open. The dataset contains real Google search queries, and some of them reflect temporal trends at the time when the queries were executed. If a query is related to a TV show broadcasted in 2018, we can hardly expect to extract the answer from a dump in 2017.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Like this, although Wikipedia is a useful knowledge source for open-domain QA research, its rapidly evolving nature should be considered more carefully for the reproducibility. We will make all of the data including pre-processed Wikipedia articles for each experiment available for future research.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
B.6 DETAILS ABOUT INITIAL CANDIDATES C 1 SELECTION To retrieve the initial candidates C 1 for each question, we use a TF-IDF based retriever with the bi-gram hashing (Chen et al., 2017). For HotpotQA full wiki, we retrieve top F introductory paragraphs, for each question, from a corpus including all the introductory paragraphs. For SQuAD Open and Natural Questions Open, we first retrieve 50 Wikipedia articles through the same TF-IDF retriever, and further run another TF-IDF-based paragraph retriever (Clark & Gardner, 2018;Min et al., 2019a) to retrieve F paragraphs in total.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We experiment with a variant of our approach, where we incorporate an entity linking system with our framework, in place of the Wikipedia hyperlinks. In this experiment, we first retrieve seed paragraphs using TF-IDF (F = 100), and run an off-the-shelf entity linker (TagMe by Ferragina & Scaiella (2011)) over the paragraphs. If the entity linker detects some entities, we retrieve their corresponding Wikipedia articles, and add edges from the seed paragraphs to the entity-linked paragraphs. Once we build the graph, then we re-run all of the experiments while the other components are exactly the same. We use the TagMe official Python wrapper. 8 C ADDITIONAL RESULTS ON HOTPOTQA C.1 UPPER-BOUND OF OUR RETRIEVAL MODULE For scalability and computational efficiency, we bootstrap our retrieval module with TF-IDF retrieval; we first retrieval F paragraphs using TF-IDF with the method described in Section B.6 and initialize C 1 with these TF-IDF paragraphs. Although we expand our candidate paragraphs at each time step using the Wikipedia graph, if our method failed to retrieve paragraphs a few-hops away from the answer paragraphs, it is likely to fail to reach the answer paragraphs. To estimate the paragraph EM upper-bound, we have checked if two gold paragraphs are included in the top 20 TF-IDF paragraphs and their hyperlinked paragraphs in the HotpotQA full wiki setting. We found that for 75.4% of the questions, all of the gold paragraphs are included in the collections of the TF-IDF paragraphs and the hyperlinked paragraphs. Also, it should be noted when we only consider the TF-IDF retrieval results, the upper-bound drops to 35.1%, which suggests that the TF-IDF-based retrieval cannot effectively discover the paragraphs multi-hop away due to the few lexical overlap. When we increase the number of F to 100 and 500, the upper-bound reaches 84.1% and 89.2%, respectively.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
In HotpotQA, there are two types of questions, bridge and comparison. While comparison-type questions explicitly mention the two entities related to the given questions, in bridge-type questions, the bridge entities are rarely explicitly stated. This makes it hard for a retrieval system to discover the paragraphs entailed by the bridge entities only.  Retrieval. We observed that some of the comparison-type questions can be answered based on single paragraph, and thus our model selects only one paragraph for some of these comparisontype questions, resulting in lower P EM scores on the comparison-type questions. We show several examples of the questions where we can answer based on single paragraph in Section C.5.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
As we discussed in 3.1.1, we aim at significantly reducing the search space and thus scaling the number of initial TF-IDF candidates. Increasing the number of the initial retrieved paragraphs often improves the recall of the evidence paragraphs of the datasets. On the other hand, increasing the candidate paragraphs introduces additional noises, may distract models, and eventually hurt the performance (Kratzwald & Feuerriegel, 2018). We compare the performance of three different approaches: (i) ours, (ii) ours (greedy, without reasoning path re-ranking), and (iii) Re-rank.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We increase the number of the TF-IDF-based retrieved paragraphs from 10 to 500 (For Re-rank, we compare the performance up to 200 paragraphs). Figure 5 clearly shows that our approach is robust towards the increase of the initial candidate paragraphs, and thus can constantly yield performance gains with more candidate paragraphs. Our approach with the greedy search also shows performance improvements; however, after a certain number, the greedy approach stops improving the performance. Re-rank starts suffering from the noises caused by many distracting paragraphs included in the initial candidate paragraphs at F = 200.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
To show the importance of the question-paragraph encoding in our retriever model, we conduct an experiment on the development set of HotpotQA, by replacing it with the question-independent encoding described in Appendix A.2. For a fair comparison, we use the same initial TF-IDF-based retrieval (only for the full wiki setting), hyperlink-based Wikipedia graph, beam search, and reader model (BERT wwm). We train the alternative model without using the data augmentation technique (described in Section 3.  Table 11: Effects of the question-dependent paragraph encoding: Comparing our retriever model with and without the query-dependent encoding. For our question-dependent approach, the full wiki results correspond to "retriever, no link-based negatives" in Table 6, and the distractor results correspond to "Ours (Reader: BERT wwm)" Table 1, to make the results comparable. Table 11 shows the results in both the full wiki and distractor settings. As seen in this table, the QA F1 and EM performance significantly deteriorates on the full wiki setting, which demonstrates the importance of the question-dependent encoding for complex and entity-centric open-domain question answering.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We can also see that the performance drop on the distractor setting is much smaller than that on the full wiki setting. This is due to its closed nature; for each question, we are given only ten paragraphs and the two gold paragraphs are always included, which significantly narrows the searching space down and makes the retrieval task much easier than that in the full wiki setting. Therefore, our recurrent retriever model is likely to discover the gold reasoning paths by the beam search, and our reader model can select the gold paths by the robust re-ranking approach. To verify this hypothesis, we checked the P EM score as a retrieval accuracy in the distractor setting. If we only consider the top-1 path from the beam search, the P EM score of the question-independent model is 12% lower than that of our question-dependent model. However, if we consider all the reasoning paths produced by the beam search, the coverage of the gold paths is almost the same. As a result, our reader model can perform similarly with both the question-dependent/independent approaches. This additionally shows the robustness of our re-ranking approach.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
In this section, we conduct more qualitative analysis on the reasoning paths predicted by our model. Explicitly retrieving plausible reasoning paths and re-ranking the paths provide us interpretable insights into the underlying entity relationships used for multi-hop reasoning.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
As shown in Table 9, our model flexibly selects one or more paragraphs for each question. To understand these behaviors, we conduct qualitative analysis on these examples whose reasoning paths are shorter or longer than the original gold reasoning paths.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Reasoning path only with single paragraph First, we show two examples (one is a bridge-type question and the other is a comparison-type question), where our retriever selects single paragraph and terminates without selecting any additional paragraphs.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
The bridge-type question in Table 12 shows that, while originally this question requires a system to read two paragraphs, Before I Go to Sleep (film) and Nicole Kidman, our retriever and reader eventually choose Nicole Kidman only. The second paragraph has a lot of lexical overlaps to the given question, and thus, a system may not need to read both of the paragraphs to answer.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
The comparison-type question in Table 12 also shows that even comparison-type questions do not always require two paragraphs to answer the questions, and our model only selects one paragraph necessary to answer the given example question. In this example, the question has large lexical overlap with one of the ground-truth paragraph (The Bears and I), resulting in allowing our model to answer the question based on the single paragraph.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Min et al. (2019b) also observed that some of the questions do not necessarily require multi-hop reasoning, while HotpotQA is designed to require multi-hop reasoning (Yang et al., 2018). In that sense, we can say that our method automatical detects potentially single-hop questions.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Reasoning path with three paragraphs All of the HotpotQA questions are authored by annotators who are shown two relevant paragraphs, and thus, originally the length of ground-truth reason- Table 12: Two examples of the questions that our model retrieves a reasoning path with only one paragraph. We partly remove sentences irrelevant to the questions. Words in red correspond to the answer strings.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
ing paths is always two. On the other hand, as our model accommodates arbitrary steps of reasoning, it often selects reasoning paths longer than the original annotations as shown in Table 9. When our model selects a longer reasoning path for a HotpotQA question, does it contain paragraphs that provide additional evidence? We show an example in Table 13, so as to answer this question. Our model selects an additional paragraph, Blue Jeans (Lana Del Rey song) at the first step, and then selects the two annotated gold paragraphs. This first paragraph is strongly relevant to the given question, but does not contain the answer. This additional evidence might help the reader to find the correct bridge entity ("Back to December").
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Although the main focus in this paper is on open-domain QA, we show the state-of-the-art performance on the HotpotQA distractor setting as well with the exactly same architecture. We conduct qualitative analysis to understand our model's behavior in the closed setting. In this setting, the two ground-truth paragraphs are always given for each question. Table 14 shows two examples from the HotpotQA distractor setting. In the first example, P1 and P2 are its corresponding ground-truth paragraphs. At the first time step, our retriever does not expect that P2 is related to the evidence to answer the question, as the retriever is not aware of the bridge entity, "Pasek & Paul". If we simply adopt the Re-rank strategy, P3 with the second highest probability is selected, resulting in a wrong paragraph selection. In our framework, our retriever is conditioned on the previous retrieval history and thus, at the second time step, it chooses the correct paragraph, P2, lowering the probability of P3. This clearly shows the effectiveness of our multi-step retrieval method in the closed setting as well. At the third step, our model stops the prediction by   Table 15: Statistics of the reasoning paths for SQuAD Open and Natural Questions Open: the average length and the distribution of length of the reasoning paths selected by our retriever and reader for SQuAD Open and Natural Questions Open.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
outputting [EOS].
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
In 588 examples (7.9%) of the entire distractor development dataset, the paragraph selection by our graph-based recurrent retriever differs from the top-2 strategy.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We present another example, where only the graph-based recurrent retrieval model succeeds in finding the correct paragraph pair, (P1, P2). The second question in Table 14 shows that at the first time step our retriever successfully selects P1, but does not pay attention to P2 at all, as the retriever is not aware of the bridge entity, "the Russian Civil War". Again, once it is conditioned on P1, which includes the bridge entity, it can select P2 at the second time step. Like this, we can see how our model successfully learns to model relationships between paragraphs for multi-hop reasoning.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Although the main focus of this work is on multi-hop open-domain QA, our framework shows competitive performance on the two open-domain QA datasets, SQuAD Open and Natural Questions Open. Both of the two dataets are originally created by assigning a single ground-truth paragraph for each question, and in that sense, our framework is not specific to multi-hop reasoning tasks. In this section, we further analyze our experimental results on the two datasets. Table 15 shows statistics of the lengths of the selected reasoning paths on our SQuAD Open experiment. This table is analogous to Table 9 on our HotpotQA experiments. We can clearly see that our recurrent retriever always outputs a single paragraph for each question, if we only use the top-1 predictions. This is because our retriever model for this dataset is trained with the single-paragraph annotations. Our beam search can find longer reasoning paths, and as a result, the re-ranking process in our reader model somtimes selects the reasoning paths including two paragraphs. The trend is consistent with that in Table 9. However, the effects of selecting more than one paragraph do not have a big impact; we observed only 0.1% F1/EM improvement over our method with restricting the path length to one (based on the same experiment with L = 1 in Table 8). Considering that SQuAD is a single-hop QA dataset, the result matches our intuition. Table 15 also shows the results on Natural Questions Open, where we see the same trend again. Thanks to the ground-truth path augmentation technique, our recurrent retriever model prefers longer reasoning paths than those on SQuAD Open. We observed 1% EM improvement over the L = 1 baseline on Natural Questions Open, and next we show an example to discuss why our reasoning path approach can be effective on this dataset. Table 16 shows one example where our model finds a multi-hop reasoning path effectively in Natural Questions Open (development set). The question "who sang the original version of killing me so" has relatively fewer lexical overlap with the originally annotated paragraph (Killing Me Softly with His Song (V) in Table 16). Moreover, there are several entities named as "killing me softly" in Wikipedia, because many artists cover the song. To answer this question correctly, our retriever first selects Roberta Flack (I), and then hops to the originally annotated paragraph, Killing Me Softly with His Song (V). Our reader further verifies this reasoning path and extracts the correct answer from Killing Me Softly with His Song (V). This example shows that even without gold Table 16: An example from Natural Questions Open. The bold text represents titles and paragraph indices (e.g., (I) denotes that the paragraph is an introductory paragraph). The highlighted phrase represents a bridge entity and the text in red represents an answer span.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
reasoning paths annotations, our model trained on the augmented examples learns to retrieve multihop reasoning paths from the entire Wikipedia.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
These detailed experimental results on the two other open-domain QA datasets demonstrate that our framework learns to retrieve reasoning paths flexibly with evidence sufficient to answer a given question, according to each dataset's nature.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Open domain question answering is a challenging task where the answer to a given question needs to be extracted from a large pool of documents. The prevailing approach (Chen et al., 2017) tackles the problem in two stages. Given a question, a retriever first produces a list of k candidate documents, and a reader then extracts the answer from this set. Until recently, retrieval models were dependent on traditional term-based information retrieval (IR) methods, which fail to capture the semantics of the question beyond lexical matching and remain a major performance bottleneck for the task. Recent work on dense retrieval methods instead uses pretrained encoders to cast the question and documents into dense representations in a vector space and relies on fast maximum inner-product search (MIPS) to complete the retrieval. These approaches Guu et al., 2020;Karpukhin et al., 2020) have demonstrated significant retrieval improvements over traditional IR baselines.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
However, such methods remain limited to simple questions, where the answer to the question is explicit in a single piece of text evidence. In contrast, complex questions typically involve aggregating information from multiple documents, requiring logical reasoning or sequential (multihop) processing in order to infer the answer (see Figure 1 for an example). Since the process for answering such questions might be sequential in nature, single-shot approaches to retrieval are insufficient. Instead, iterative methods are needed to recursively retrieve new information at each step, conditioned on the information already at hand. Multi-hop question answering is an important task and an active research area (Talmor & Berant, 2018;Yang et al., 2018).
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
The main problem in answering multi-hop open-domain questions is that the search space grows exponentially with each retrieval hop. Most recent work tackles this issue by constructing a document graph utilizing either entity linking or existing hyperlink structure in the underlying Wikipedia corpus (Nie et al., 2019;Asai et al., 2020). The problem then becomes finding the best path in this graph, where the search space is bounded by the number of hyperlinks in each passage. However, such methods may not generalize to new domains, where entity linking might perform poorly, or where hyperlinks might not be as abundant as in Wikipedia. Moreover, efficiency remains a challenge despite using these data-dependent pruning heuristics, with the best model (Asai et al., 2020) needing hundreds of calls to large pretrained models to produce a single answer.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
In contrast, we propose to employ dense retrieval to the multi-hop setting with a simple recursive framework. Our method iteratively encodes the question and previously retrieved documents as a query vector and retrieves the next relevant documents using efficient MIPS methods. With highquality, dense representations derived from strong pretrained encoders, our work first demonstrates that the sequence of documents that provide sufficient information to answer the multi-hop question can be accurately discovered from unstructured text, without the help of corpus-specific hyperlinks. When evaluated on two multi-hop benchmarks, HotpotQA (Yang et al., 2018) and a multi-evidence  subset of FEVER (Thorne et al., 2018), our approach improves greatly over the traditional linkingbased retrieval methods (e.g., 28% relative gain in Recall@20 for HotpotQA). Importantly, the better retrieval results also lead to new state-of-the-art downstream results on both datasets, while being 10x faster at inference time.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
2.1 PROBLEM DEFINITION
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
The retrieval task considered in this work can be described as follows (see also Figure 1). Given a multi-hop question q and a large text corpus C, the retrieval module needs to retrieve a sequence of passages P seq : {p 1 , p 2 , ..., p n } that provide sufficient information for answering q. Practically, the retriever returns the k best-scoring sequence candidates, {P 1 seq , P 2 seq , ..., P k seq } (k |C|), with the hope that at least one of them has the desired qualities. k should be small enough for downstream modules to process in a reasonable time while maintaining adequate recall. In general, retrieval also needs to be efficient enough to handle real-world corpora containing millions of documents.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Model Based on the sequential nature of the multi-hop retrieval problem, our system solves it in an iterative fashion. We model the probability of selecting a certain passage sequence as follows:
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
where for t = 1, we only condition on the original question for retrieval. At each retrieval step, we construct a new query representation based on previous results and the retrieval is implemented as maximum inner product search over the dense representations of the whole corpus:
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
, where q t = g(q, p 1 , ..., p t−1 ) and p t = h(p t ).
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Here ·, · is the inner product between the query and passage vectors. h(·) and and g(·) are passage and query encoders that produce the dense representations. In order to reformulate the query representation to account for previous retrieval results at time step t, we simply concatenate the question and the retrieved passages as the inputs to g(·). Note that our formulation for each retrieval step is similar to existing single-hop dense retrieval methods Guu et al., 2020;Karpukhin et al., 2020) except that we add the query reformulation process conditioned on previous retrieval results. Instead of using a bi-encoder architecture with separately parameterized encoders for questions and passages, we use a shared RoBERTa-base  encoder for both h(·) and g(·). In §3.1.3, we show that this simple modification yields considerable improvements.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
The retriever model is trained as in Karpukhin et al. (2020), where each input query (which at each step consists of a question and previously retrieved passages) is paired with a positive passage and m negative passages to approximate the softmax over all passages. The positive passage is the gold annotated evidence at step t. Negative passages are a combination of passages in the current batch which correspond to other questions (in-batch), and hard negatives which are false adversarial passages. In our experiments, we obtain hard negatives from TF-IDF retrieved passages and their linked pages in Wikipedia. We note that using hyperlinked pages as additional negatives is neither necessary nor critical for our approach. In fact we observe only a very small degradation in performance if we remove them from training ( §3.1.3).
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
In addition to in-batch negatives, we use a memory bank (M) mechanism (Wu et al., 2018) to further increase the number of negative examples for each question. The memory bank stores a large number of dense passage vectors. As we block the gradient back-propagation in the memory bank, its size (|M| batch size) is less restricted by the GPU memory size. Specifically, after training to convergence with the shared encoder, we freeze a copy of the encoder as the new passage encoder and collect a bank of passage representations across multiple batches to serve as the set of negative passages. This simple extension results in further improvement in retrieval. ( §3.1.3).
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
For inference, we first encode the whole corpus into an index of passage vectors. Given a question, we use beam search to obtain top-k passage sequence candidates, where the candidates to beam search at each step are generated by MIPS using the query encoder at step t, and the beams are scored by the sum of inner products as suggested by the probabilistic formulation discussed above. Such inference relies only on the dense passage index and the query representations, and does not need explicit graph construction using hyperlinks or entity linking. The top-k sequences will then be fed into task-specific downstream modules to produce the desired outputs.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Datasets Our experiments focus on two datasets: HotpotQA and Multi-evidence FEVER. Hot-potQA (Yang et al., 2018) includes 113k multi-hop questions. Unlike other multi-hop QA datasets Talmor & Berant, 2018;Welbl et al., 2018), where the information sources of the answers are knowledge bases, HotpotQA uses documents in Wikipedia. Thus, its questions are not restricted by the fixed KB schema and can cover more diverse topics. Each question in HotpotQA is also provided with ground truth support passages, which enables us to evaluate the intermediate retrieval performance. Multi-evidence FEVER includes 20k claims from the FEVER (Thorne et al., 2018) fact verification dataset, where the claims can only be verified using multiple documents. We use this dataset to validate the general applicability of our method.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
All the experiments are conducted on a machine with 8 32GB V100 GPUs. Our code is based on Huggingface Transformers (Wolf et al., 2019). Our best retrieval results are predicted using the exact inner product search index (IndexFlatIP) in FAISS (Johnson et al., 2017). Both datasets assume 2 hops, so we fix n = 2 for all experiments. Since HotpotQA does not provide the order of the passage sequences, as a heuristic, we consider the passage that includes the answer span as the final passage. 1 In §3.1.3, we show that the order of the passages is important for effective retriever training. The hyperparameters can be found in Appendix B.1.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
We evaluate our multi-hop dense retriever (MDR) in two different use cases: direct and reranking, where the former outputs the top-k results directly using the retriever scores and the latter applies a task-specific reranking model to the initial results from MDR.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
We first compare MDR with several efficient retrieval methods that can directly find the top-k passage sequences from a large corpus, including TF-IDF, TF-IDF + Linked, DrKIT and Entity Linking. TF-IDF is the standard term-matching baseline, while TF-IDF + Linked is a straightforward extension that also extracts the hyperlinked passages from TF-IDF passages, and then reranks both TF-IDF and hyperlinked passages with BM25 2 scores. DrKIT (Dhingra et al., 2020) is a recently proposed dense retrieval approach, which builds a entity-level (mentions of entities) dense index for retrieval. It relies on hyperlinks to extract entity mentions and prunes the search space with a binary mask that restricts the next hop to using hyperlinked entities. On FEVER, we additionally consider an entity linking baseline (Hanselowski et al., 2018) that is commonly used in existing fact verification pipelines. This baseline first uses a constituency parser to extract potential entity mentions in the fact claim and then uses the MediaWiki API to search documents with titles that match the mentions. Table 1 shows the performance of different retrieval methods. On HotpotQA the metric is recall at the top k paragraphs 3 , while on FEVER the metrics are precision, recall and F 1 in order to be consistent with previous results. On both datasets, MDR substantially outperforms all baselines.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Reranking documents returned by efficient retrieval methods with a more sophisticated model is a common strategy for improving retrieval quality. For instance, state-of-the-art multi-hop QA systems usually augment traditional IR techniques with large pretrained language models to select a more compact but precise passage set. On HotpotQA, we test the effectiveness of MDR after a simple BERT-based reranking: each of the top k passage sequences from MDR is first prepended with the original question and then fed into a BERT-like encoder that predicts relevant scores. We train this reranking model with a binary cross-entropy loss, with the target being whether the passage sequence cover both groundtruth passages. We empirically compare our approach with two other existing reranking-based retrieval methods: Semantic Retrieval (Nie et al., 2019) uses BERT at both passage-level and sentence-level to select context from the initial TF-IDF and hyperlinked passages; Graph Recurrent Retriever (Asai et al., 2020) learns to recursively select the best passage sequence on top of a hyperlinked passage graph, where each passage node is encoded with BERT.   Table 2 shows the reranking results. Following Asai et al. (2020), we use Answer Recall and Support Passage Exact Match (SP EM) 4 as the evaluation metrics. Even without reranking, MDR is already better than Semantic Retrieval, which requires around 50 BERT encoding (where each encoding involves cross-attention over a concatenated question-passage pair). After we rerank the top-100 sequences from the dense retriever, our passage recall is better than the state-of-the-art Graph Recurrent Retriever, which uses BERT to process more than 500 passages. We do not compare the reranked results on FEVER, as most FEVER systems directly use BERT encoder to select the top evidence sentences from the retrieved documents, instead of the reranking the documents.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
To understand the strengths and weaknesses of MDR, we conduct further analysis on HotpotQA dev.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
HotpotQA contains two question categories: bridge questions in which an intermediate entity is missing and needs to be retrieved before inferring the answer; and comparison questions where two entities are mentioned simultaneously and compared in some way.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
In Figure 2, we show the retrieval performance of both question types. The case of comparison questions proves easier, since both entities needed for retrieval are present in the question. This case appears almost solved, confirming recent work demonstrating that dense retrieval is very effective at entity linking (Wu et al., 2019).
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
For the case of bridge questions, we manually inspect 50 randomly sampled erroneous examples after reranking. We find that in half of these cases, our retrieval model predicts an alternative passage sequence that is also valid (see Appendix A.1 for examples). This gives an estimated top-1 passage sequence accuracy of about 90%. Other remaining errors are due to the dense method's inability to capture the exact n-gram match between the question and passages. This is a known issue Karpukhin et al., 2020) of dense retrieval methods when dealing with questions that have high lexical overlap with the passages. To this end, a hybrid multi-hop retrieval method with both term and dense index might be used to further improve the performance on bridge questions.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
In Table 3, we examine our model with different variations on HotpotQA to show the effectiveness of each proposed component. We see that further training with a memory bank results in modest gains, while using a shared encoder is crucial for the best performance.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Respecting the ordering of passages in two hops is essential -training in an order-agnostic manner hardly works at all, and underperforms even the single-hop baseline. Finally, not using hyperlinked paragraphs from TF-IDF passages as additional negatives has only a minor impact on performance.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Question Decomposition for Retrieval As multi-hop questions have more complex structures than simple questions, recent studies (Min et al., 2019;Perez et al., 2020) propose to use explicit question decomposition to simplify the problem. Wolfson et al. (2020) shows that with TF-IDF, using decomposed questions improves the retrieval results. We investigate whether the conclusion still holds with stronger dense retrieval methods. We use the human-annotated question decomposition from the QDMR dataset (Wolfson et al., 2020) for analysis. For a question like Q:Mick Carter is the landlord of a public house located at what address?, QDMR provides two subquestions, SubQ1: What is the public house that Mick Carter is the landlord of? and SubQ2: What is the address that #1 is located at?. We sample 100 bridge questions and replace #1 in SubQ2 with the correct answer (The Queen Victoria) to SubQ1. Note that this gives advantages to the decomposed method as we ignore any intermediate errors. We estimate the performance of potential decomposed methods with the state-of-the-art single-hop dense retrieval model (Karpukhin et al., 2020). As shown in Table 4, we did not observe any strong improvements from explicit question decomposition, which is contrary to the findings by Wolfson et al. (2020) when using term-based IR methods. Moreover, as shown in the third row of the table, when the 1st hop of the decomposed retrieval (i.e., SubQ1) is replaced with the original question, no performance degradation is observed. This suggests that strong pretrained encoders can effectively learn to select necessary information from the multi-hop question at each retrieval step.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Regarding the performance drop when using explicit compositions, we hypothesize that it is because some information in one decomposed subquestion could be useful for the other retrieval hop. Examples supporting this hypothesis can be found in Appendix A.2. While this could potentially be addressed by a different style of decomposition, our analysis suggests that decomposition approaches might be unnecessary in the context of dense retrieval with strong pretrained encoders.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
We evaluate how the better retrieval results of MDR improve multi-hop question answering in this section. As our retriever system is agnostic to downstream models, we test two categories of answer prediction architectures: the extractive span prediction models based on pretrained masked language models, such as BERT  and ELECTRA (Clark et al., 2020), and the retrieval-augmented generative reader models (Lewis et al., 2020b;Izacard & Grave, 2020), which are based on pretrained sequence-to-sequence (seq2seq) models such as BART (Lewis et al., 2020a) and T5 (Raffel et al., 2019). Note that compared to more complicated graph reasoning models (Fang et al., 2019;Zhao et al., 2020), these two classes of models do not rely on hyperlinks and can be applied to any text.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Extractive reader models learn to predict an answer span from the concatenation of the question and passage sequence ([q, p 1 , ..., p n ]). On top of the token representations produced by pretrained models, we add two prediction heads to predict the start and end position of the answer span. 5 To predict the supporting sentences, we add another prediction head and predict a binary label at each sentence start. For simplicity, the same encoder is also responsible for reranking the top k passage sequences. The reranking detail has been discussed in §3.1.2. Our best reader model is based on ELECTRA (Clark et al., 2020), which has achieved the best single-model performance on the standard SQuAD (Rajpurkar et al., 2018) benchmark. Additionally, we also report the performance of BERT-large with whole word masking (BERT-wwm) to fairly compare with Asai et al. (2020).
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Generative models, such as RAG (Lewis et al., 2020b) and FiD (Izacard & Grave, 2020), are based on pretrained seq2seq models. These methods finetune pretrained models with the concatenated questions and retrieved documents as inputs, and answer tokens as outputs. This generative paradigm has shown state-of-the-art performance on single-hop open-domain QA tasks. Specifically, FiD first uses the T5 encoder to process each retrieved passage sequence independently and then uses the decoder to perform attention over the representations of all input tokens while generating answers. RAG is built on the smaller BART model. Instead of only tuning the seq2seq model, it also jointly train the question encoder of the dense retriever. We modified it to allow multi-hop retrieval.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
More details about these two classes of reader models are described in Appendix B.2. Comparison with Existing Systems Table 5 compares the HotpotQA test performance of our best ELECTRA reader with recently published systems, using the numbers from the official leaderboard, which measure answer and supporting sentence exact match (EM)/F1 and joint EM/F1. Among these methods, only GoldEn Retriever (Qi et al., 2019) does not exploit hyperlinks. In particular, Graph Recurrent Retriever trains a graph traversal model for chain retrieval; TransformerXH (Zhao et al., 2020) and HGN (Fang et al., 2019) explicitly encode the hyperlink graph structure within their answer prediction models. In fact, this particular inductive bias provides a perhaps unreasonably strong advantage in the specific context of HotpotQA, which by construction guarantees groundtruth passage sequences to follow hyperlinks. Despite not using such prior knowledge, our model outperforms all previous systems by large margins, especially on supporting fact prediction, which benefits more directly from better retrieval.  Table 6. 6 First, we see that the BERT-wwm reader is 1-2% worse than the ELECTRA reader when using enough passages. However, it still outperforms the results in (Asai et al., 2020) which also uses BERT-wwm for answer prediction. While RAG and FiD have shown strong improvements over extractive models on single-hop datasets such as NaturalQuestions (Kwiatkowski et al., 2019), they do not show an advantage in the multi-hop case. Despite having twice as many parameters as ELECTRA, FiD fails to outperform it using the same amount of context (top 50). In contrast, on NaturalQuestions, FiD is 4 points better than a similar extractive reader when using the top 100 passages in both. 7 We hypothesize that the improved performance on single-hop questions is due to the ability of larger pretrained models to more effectively memorize single-hop knowledge about real-world entities. 8 Compared to multi-hop questions that involve multiple relations and missing entities, simple questions usually only ask about a certain property of an entity. It is likely that such simple entity-centric information is explicitly mentioned by a single text piece in the pretraining corpus, while the evidence for multihop questions is typically dispersed, making the complete reasoning chain nontrivial to memorize. More analysis on RAG can be found in Appendix A.3. Inference Efficiency To compare with existing multi-hop QA systems in terms of efficiency, we follow Dhingra et al. (2020) and measure the inference time with 16 CPU cores and batch size 1. We implement our system with a fast approximate nearest neighbor search method, i.e., HNSW (Malkov & Yashunin, 2018), which achieves nearly the same performance as exact search. With an in-memory index, we observe that the retrieval time is negligible compared to the forward pass of large pretrained models.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Similarly, for systems that use term-based indices, the BERT calls for passage reranking cause the main efficiency bottleneck. Thus, for systems that do not release the end-to-end code, we estimate the running time based on the number of BERT cross-attention forward passes (the same estimation strategy used by Dhingra et al. (2020)), and ignore the overhead caused by additional processing such as TF-IDF or linking graph construction. As shown in Figure 3, our method is about 10 times faster than current state-of-the-art systems while achieving a similar level of performance. Compared to two efficient systems (DrKIT and GoldEn), we achieve over 10 points improvement while only using the top-1 retrieval result for answer and supporting sentence prediction.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
For FEVER claim verification, we reuse the best open-sourced verification system, i.e., KGAT (Liu et al., 2020), to show the benefit of our retrieval approach over existing retrieval methods. We report 6 For the compute-heavy generative models, we feed in as many passages as possible without running into memory issues (Muli-hop RAG takes top 4 passages from hop1, and for each of those, takes another top 4 from hop2. They are not necessarily the same as the top 16 passages sequences.). As extractive models encode each passage sequence separately, we can use arbitrary number of input sequences. However, the performance mostly plateaus as we use over 200 input sequences. 7 We implemented NQ extractive readers with both RoBERTa-large and ELECTRA-large, and RoBERTa-large yielded a better answer EM of 47.3, which is much lower than the 51.4 answer EM achieved by FiD. 8 As shown by Roberts et al. (2020), a large pretrained seq2seq model can be finetuned to directly decode answers with questions as the only inputs. However, we find that this retrieval-free approach performs poorly on multi-hop questions. See Appendix C for the exact numbers. the results in verification label accuracy (LA) and the FEVER score 9 in Table 7, where the numbers of competitive baselines, GEAR , graph attention network (GAT) (Veličković et al., 2017) and variants of KGAT are from the KGAT (Liu et al., 2020) paper. All these baselines use entity linking for document retrieval, then rerank the sentences of the retrieved documents, and finally use different graph attention mechanisms over the fully-connected sentence graph to predict verification labels. Since some instances in the multi-evidence subset used by previous studies only needs multiple evidence sentences from the same document, we additionally test on a strict multi-hop subset with instances that need multiple documents. As shown by the results, even without finetuning the downstream modules, simply replacing the retrieval component with MDR leads to significant improvements, especially on the strict multi-evidence subset.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Open-domain QA with Dense Retrieval In contrast to sparse term-index IR methods, which are widely used by existing open-domain QA systems (Chen et al., 2017;Wang et al., 2018;, recent systems Guu et al., 2020;Karpukhin et al., 2020) typically uses dense passage retrieval techniques that better capture the semantic matching beyond simple n-gram overlaps.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
To generate powerful dense question and passage representations, these methods either conduct largescale pretraining with self-supervised tasks that are close to the underlying question-passage matching in retrieval, or directly use the human-labeled question-passage pairs to finetune pretrained masked language models. On information-seeking QA datasets such as NaturalQuestions (Kwiatkowski et al., 2019) or WebQuestions (Berant et al., 2013), these dense methods have achieved significant improvements over traditional IR methods. However, these extensively studied datasets only include simple questions that can be answered from a single passage.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Other Multi-hop QA Work Apart from HotpotQA, other multi-hop QA datasets (Welbl et al., 2018;Talmor & Berant, 2018; are mostly built from knowledge bases (KBs). Compared to questions in HotpotQA, questions in these datasets are rather synthetic and less diverse. As multi-hop relations in KBs could be mentioned together in a single text piece, these datasets are not designed for an open-domain setting which necessitates multi-hop retrieval. Existing methods on these datasets either retrieve passages from a small passage pool pruned based on the the specific dataset Dhingra et al., 2020), or focus on a non-retrieval setting where a compact documents set is already given (De Cao et al., 2018;Tu et al., 2019;Beltagy et al., 2020). Compared to these research, our work aims at building an efficient multi-hop retrieval model that easily scales to large real-world corpora that include millions of open-domain documents.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
In this work, we generalized the recently proposed successful dense retrieval methods by extending them to the multi-hop setting. This allowed us to handle complex multi-hop queries with much better accuracy and efficiency than the previous best methods. We demonstrated the versatility of our approach by applying it to two different tasks, using a variety of downstream modules. In addition, the simplicity of the framework and the fact that it does not depend on a corpus-dependent graph structure opens the possibility of applying such multi-hop retrieval methods more easily and broadly cross different domains and settings.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
A.1 FALSE BRIDGE QUESTION ERROR CASES As mentioned in §3.1.3, half of the errors of bridge questions are not real errors. In Table 8, we can see that the model predicts alternative passage sequences that could also be used to answer the questions.   Table 6 demonstrates the answer prediction performance for four different reader models. The extractive models predict answers given the top 250 retrieved passage sequences (pairs of passage from hop1 and hop2). Since generative models are generally heavier on the computation side, we can only use fewer passages. While generative models are worse due to the limited number of given passage sequences as discussed below. We hypothesize that the worse performance of multi-hop RAG is due to the base model used in RAG, i.e., BART. The fact that FiD with BART only has 43 answer EM given top 50 passage sequences further proves this point.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Given the same number of retrieved passage sequences (top 50) as shown in table 10, FiD obtains similar performance to ELECTRA, despite that the generative model can generate arbitrary answers for the given input. (We tried constrained decoding for the generative model. However, no significant performance improvements were observed, indicating that the errors from the generative model are not due to the free-form generation task.) Further question type analysis in HotpotQA showed that the main difference comes from the comparison type of question, while for bridge question, FiD performs slightly better than ELECTRA.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
B MODEL DETAILS B.1 BEST MODEL HYPERPARAMETERS  The extractive reader is trained with four loss functions. With the [CLS] token, we predict a reranking score based on whether the passage sequence match the groundtruth supporting passages. On top of the representation of each token, we predict a answer start score and answer end score.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Finally, we prepend each sentence with the [unused0] special token and predict whether the sentence is one of the supporting sentences using the representations of the special token. At training time, we pair each question with 1 groundtruth passage sequence and 5 negative passage sequence which do not contain the answer. At inference time, we feed in the top 250 passage sequences from MDR. We rank the predicted answer for each sequence with a linear combination of the reranking score and the answer span score. The combination weight is selected based on the dev results.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
The FiD model uses T5-large as the underlying seq2seq model. It is twice as large as the extractive models and has 770M parameters. We reuse the hyperparameters as described in Izacard & Grave (2020). The original FiD uses the top 100 passages for NaturalQuestions. In our case, we use the top 50 retrieved passage sequences and concatenate the passages in each sequence before feeding into T5. In order to fit this model into GPU, we make use of PyTorch checkpoint 10 for training.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Inspired by a recent work (Roberts et al., 2020) that trains the T5 seq2seq model to directly decode answers from questions (retrieval-free), we conduct similar experiments on HotpotQA using BART (Lewis et al., 2020a). As shown in Figure 4, the performance gap between retrieval-based methods and retrieval-free methods on multi-hop QA is much larger than the gap in the case of simple single-hop questions. 
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
In open-domain reasoning, a model is tasked with retrieving evidence from a large corpus to answer questions, verify claims, or otherwise exhibit broad knowledge. In practice, such open-domain tasks often further require multi-hop reasoning, where the evidence must be extracted from two or more documents. To do this effectively, a model must learn to use partial evidence it retrieves to bridge its way to additional documents leading to an answer. In this vein, HotPotQA [31] contains complex questions answerable by retrieving two passages from Wikipedia, while HoVer [13] contains claims that can only be verified (or disproven) by combining facts from up to four Wikipedia passages. Table 1 illustrates this using the claim "The MVP of [a] game Red Flaherty umpired was elected to the Baseball Hall of Fame" from the HoVer validation set. To verify this claim, a HoVer model must identify facts spread across three Wikipedia pages: Red Flaherty umpired in the World Series in 1955, 1958, 1965, and 1970. The MVP of the 1965 World Series was Sandy Koufax. Koufax was later elected to the Baseball Hall of Fame.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Open-domain reasoning There is significant recent interest in NLP models that can solve tasks by retrieving evidence from a large corpus. The most popular such task is arguably open-domain question answering (OpenQA; Chen et al. [2]), which extends the well-studied machine reading comprehension (MRC) problem over supplied question-passage pairs to answering questions given only a large text corpus like Wikipedia. Other open-domain tasks span claim verification (e.g., FEVER; Thorne et al. [24]), question generation (e.g., with Jeopardy as in Lewis et al. [19]), and open dialogue (e.g., Wizard of Wikipedia; Dinan et al. [8]), among others. Many of these datasets are compiled in the recently-introduced KILT benchmark [21] for knowledge-intensive tasks. Among models for these tasks, the most relevant to our work are OpenQA models that include learned retrieval components. These include ORQA [18], REALM [10], and DPR [15]. Lewis et al. [19] introduced RAG, which by virtue of a seq2seq architecture can tackle OpenQA as well as other open-domain problems, including claim verification and question generation.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Most of the open-domain tasks from §2 can be solved by finding one relevant passage in the corpus, often by design. In contrast, a number of recent works explore multi-hop reasoning over multiple passages. These include QAngaroo [27] and 2WikiMulti-HopQA [11], among others. While thus "multi-hop", these tasks supply the relevant passages for each example (possibly with small set of "distractor" candidates), and thus do not require retrieval from a large corpus. To our knowledge, HotPotQA was the first large-scale open-domain multi-hop task, particularly in its retrieval-oriented "fullwiki" setting. HotPotQA catalyzed much follow-up research. However, it is limited to only two-hop questions, many of which may not require strong multi-hop reasoning capabilities (see Chen and Durrett [3]; Wang et al. [26]), softening the retrieval challenges discussed in §1. Very recently, Jiang et al. [13] introduced the HoVer many-hop verification dataset, which contains two-, three-, and four-hop examples. HoVer contains just over 18,000 training examples, about 5× smaller than HotPotQA, adding to the challenge posed by HoVer.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Multi-hop open-domain models To conduct the "hops", many prior multi-hop systems (e.g., Asai et al. [1]; Zhao et al. [32]) assume explicit links that connect every passage with related entities. We argue that this risks tying systems to link-structured knowledge bases (like Wikipedia) or producing brittle architectures tailored for datasets constructed by following hyperlinks (like HotPotQA). Recently, Xiong et al. [29] and Qi et al. [23] introduce MDR and IRRR, state-of-the-art systems that assume no explicit link structure. Instead, they use an iterative retrieval paradigm-akin to that introduced by Das et al. [6] and Feldman and El-Yaniv [9]-that retrieves passages relevant to the question, reads these passages, and then formulates a new query for another hop if necessary. We adopt this iterative formulation and tackle three major challenges for multi-hop retrieval.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
ColBERT: late interaction paradigm Most learned-retrieval systems for OpenQA ( §2) encode every query and passage into a single dense vector. Khattab and Zaharia [16] argue that such singlevector representations are not sufficiently expressive for retrieval in many scenarios and introduce late interaction, a paradigm that represents every query and every document at a finer granularity: it uses a vector for each constituent token. Within this paradigm, they propose ColBERT, a state-of-the-art retriever wherein a BERT encoder embeds the query into a matrix of N vectors (given N tokens) and encodes every passage in the corpus as matrix of M vectors (for M tokens per passage). The passage representations are query-independent and thus are computed offline and indexed for fast retrieval.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
During retrieval with query q, ColBERT assigns a score to a passage d by finding the maximumsimilarity (MaxSim) score between each vector in q's representation and all the vectors of d and then summing these MaxSim scores. This MaxSim-decomposed interaction enables scaling to massive collections with millions of passages, as the token-level passage vectors can all be indexed for fast nearest-neighbor search. Khattab and Zaharia [16] find this fine-grained matching to outperform single-vector representations, a finding extended to open-domain question answering by Khattab et al. [17]. In this work, we propose FLIPR ( §3.1), a retriever with an improved late interaction mechanism for complex multi-hop queries. Whereas existing retrievers, whether traditional (e.g., TF-IDF) or neural [18; 15; 16], seek passages that match all of the query, multi-hop queries can be long and noisy and need to match disparate contexts. FLIPR handles this explicitly with focused late interaction.  
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Baleen T-Hop Retriever t = 1 Figure 1: The architecture of Baleen with iterative retrieval and condensing. The model begins with iteration t = 1, provided initial user input Q 0 . For every t, FLIPR takes in Q t−1 and retrieves the top-K passages, the condenser summarizes the relevant facts, and an updated query Q t is produced. When t = T , Q T is fed to the reader, which outputs a final prediction.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Relevance-guided supervision Khattab et al. [17] propose an iterative strategy for weaklysupervising retrievers called relevance-guided supervision (RGS). RGS assumes that no labeled passages are supplied for training the retriever. Instead, every training question is associated with a short answer string whose presence in a passage is taken as a weak signal for relevance. RGS starts with an off-the-shelf retriever and uses it to collect the top-k passages for each training question, dividing these passages into positive and negative examples based on inclusion of the short answer string. These examples are used to train a stronger retriever, which is then used to repeat this process one or two times. We draw inspiration from RGS when designing latent hop ordering: unlike RGS, we do have gold-labeled passages for training but we crucially have multiple hops, whose order is not given. Lastly, our supervision for the first hop shares inspiration with GoldEn [22]. GoldEn uses a bag-of-words model-and thus effectively term overlap-to identify the "more easily retrieved" passage among just two for the two-hop task HotPotQA.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We now introduce Baleen, which uses an iterative retrieval paradigm to find relevant facts in T ≥ 1 successive hops. On HotPotQA ( §4) and HoVer ( §5), we use Baleen with T = 2 and T = 4, respectively. As illustrated in Table 1, the input to Baleen is a textual query Q 0 like a question to answer or a claim to verify. The goal of hop t is to take in query Q t−1 and output an updated query Q t containing the initial input query and pertinent facts extracted from the t hops.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
The Baleen architecture is depicted in Figure 1. In every hop, FLIPR ( §3.1) uses Q t−1 to retrieve K passages from the full corpus. These passages are fed into a two-stage condenser ( §3.3), which reads these passages and extracts the most relevant facts, which we model as individual sentences. The facts are collected into a single sequence and added to Q t for the subsequent hop, if any. Once all hops are complete, Baleen's task-specific reader processes Q T , which now contains the query and all condensed facts, to solve the downstream task. If desired, the top-k passages from each hop can also be collected and fed to a downstream model after retrieval is complete. Baleen's retriever, condenser, and reader are implemented as Transformer encoders [25] and are trained individually. We use BERT-base [7] for FLIPR and, like Qi et al. [23] and Xiong et al. [29], use ELECTRA-large [5] for the other components. For supervision, we introduce the latent hop ordering scheme ( §3.2).
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
The FLIPR encoders and interaction mechanism are shown in Figure 2. Our query encoder reads Q t−1 and outputs a vector representation of every token in the input. Each query embedding interacts with all passage embeddings via a MaxSim operator, permitting us to inherit the efficiency and scalability of ColBERT [16]. While vanilla ColBERT sums all the MaxSim outputs indiscriminately, FLIPR considers only the strongest-matching query embeddings for evaluating each passage: it sums only the top-N partial scores from N scores, withN < N .
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We refer to this top-k filter as a "focused" interaction. Intuitively, it allows the same query to match multiple relevant passages that are contextually unrelated, by aligning-during training and inference-a different subset of the query embeddings with different relevant passages. These 
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Passage Tokens Figure 2: The proposed FLIPR retriever. Sub-figure (a) depicts our encoders, which represent every query and every passage as a set of embeddings. Given query q and document d, sub-figure (b) illustrates our focused late-interaction mechanism. It finds the maximum-similarity score of each query embedding q i and then focuses on the top-k matches only. This is analogously applied to the fact embeddings f j (in orange), and both scores are finally added.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
important subsets of the query are not always clear in advance. For instance, Q 1 in Table 1 should find the page about the 1965 World Series. This requires ignoring many distractions (e.g., World Series 1970 and Baseball Hall of Fame) that seem important in isolation while focusing on other phrases, namely a prominent "MVP" and the World Series 1965, a distinction evident only after finding the document and attempting to match it against the query.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
FLIPR applies this mechanism over the representation of the query and the facts separately, keeping the top-N and top-L from N and L embeddings, respectively. More formally, the FLIPR score S q,d of a passage d given a query q is the summation S q,d = S Q q,d + S F q,d over the scores corresponding to the original query and to the facts. Define M Q i = max m j=1 E qi · E T dj , that is, the maximum similarity of the i th query embedding against the passage embeddings. The partial score S Q q,d is computed as
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
where topN is an operator that keeps the largestN values in a set. We define S F q,d similarly, using the fact matches M F i instead of M Q i . We confirm the gains of FLIPR against the state-of-the-art ColBERT retriever in §5.4. By decomposing retrieval into token-level maximum similarities and pre-computing document representations, FLIPR maintains the scalability of the late interaction paradigm of ColBERT, reducing the candidate generation stage of retrieval into highly-efficient approximate k-nearest neighbor searches. See Appendix §B.1 for the implementation details of FLIPR.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
For every training example, our datasets supply unordered gold passages. However, dependencies often exist in retrieval as Table 1 illustrates: a system needs to retrieve and read the page of Red Flaherty to deduce that it needs information about 1965 World Series. Such dependencies can be complex for 3-and 4-hop examples, as in HoVer, especially as multiple passages may be appropriate to retrieve together in the same hop.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We propose a generic mechanism for identifying the best gold passage(s) to learn to retrieve next.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
The key insight is that among the gold passages, a weakly-supervised retriever with strong inductive biases would reliably "prefer" those passages it can more naturally retrieve, given the hops so far. Thus, given Q t−1 , we train the retriever with every remaining gold passage and, among those, label as positives (for Q t−1 ) only those ranked highly by the model. We subsequently use these weakly-labeled positives to train another retriever for all the hops.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Latent hop ordering is summarized in Algorithm 1, which assumes we have already trained a singlehop (i.e., first-hop) retriever R 1 in the manner of relevance-guided supervision (see §2). To start, we use R 1 to retrieve the top-k (e.g., k = 1000) passages for each training question (Line 2). We then divide these passages into positives P 1 and negatives N 1 (Line 3). Positives are the highly-ranked gold passages (i.e., the intersection of gold passages and the top-k passages with, e.g.,k = 10) and 
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Train a new retriever Rt using queries Qt−1 and negatives Nt−1. For positives, use gold passages not part of any Ps for s < t. 7 Ranking t ← Rt.retrieve(Qt−1); 8 Pt, Nt ← ExtractPositives(Ranking t ); Qt ← Qt−1.expand(OracleFacts(Pt)); 9 end 10 For every hop t ∈ [T ], designate Qt−1 as queries, Pt as positives, and Pt as negatives. 11 Train a final retrieverR using this combined training data for all hops. 12 returnR negatives are the non-gold passages. Subsequently, we expand first-hop queries with the oracle facts from P 1 to obtain the queries for the second hop (Line 4).
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We train a second-hop retriever R 2 using the aforementioned queries and negatives (Line 6). As we do not have second-hop positives, as a form of weak supervision, we train the retriever with all gold passages (per query) besides those already in P 1 . Once trained, we use R 2 to discover the second-hop positives P 2 , to collect negatives N 2 , and to expand the queries (Lines 7 and 8). We repeat this procedure for the third hop onward. Once this iterative procedure is complete, we have bootstrapped positives (and negatives) corresponding to every retrieval hop for each query. We combine these sets to train a single multi-hop retriever (Lines 10 and 11), which takes a query Q t−1 and learns to discriminate the positives in P t from the negatives in N t for every t ∈ [T ]. In §5.4, we indeed find that this generic latent procedure outperforms a typical hand-crafted heuristic that relies on trying to match titles against the text.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
After each hop, the condenser proceeds in two stages. In the first stage, it reads Q t−1 and each of the top-K passages retrieved by FLIPR. The input passages are divided into their constituent sentences and every sentence is prepended with a special token. The output embedding corresponding to these sentence markers are scored via a linear layer, assigning a score to each sentence in every retrieved passage. We train the first-stage condenser with a cross-entropy loss over the sentences of two passages, a positive and a negative.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Across the K passages, the top-k facts are identified and concatenated into the second-stage condenser model. As above, we include special tokens between the sentences, and the second-stage condenser assigns a score to every fact while attending jointly over all of the top-k facts, allowing a direct comparison within the encoder. Every fact whose score is positive is selected to proceed, and the other facts are discarded. We train the second-hop condenser over a set of 7-9 facts, some positive and others (sampled) negative, using a linear combination of cross-entropy loss for each positive fact (against all negatives) and binary cross-entropy loss for each individual fact.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
In practice, this condensed architecture offers novel tradeoffs against a re-ranking pipeline. On one hand, condensed retrieval scales better to more hops, as it represents the facts from K long passages using only a few sentences. This may provide stronger interpretability, as the inputs to the retriever (e.g., the example in Table 1) become more focused. On the other hand, re-ranking requires only passage-level labels, which can be cheaper to collect, and provides the retriever with broader context, which can help resolve ambiguous references. Empirically, we find the two approaches to be complementary. In §5.4, we show that condensing is competitive with re-ranking (despite much shorter context; Appendix §C) and that a single retriever that combines both pipelines together substantially outperforms a standard rerank-only pipeline. Table 2: Retrieval results on HotPotQA-fullwiki (dev) showing saturation in finding the gold pair of passages and passages with the answer string. Baleen and its ablation baseline ColBERT-Hop exceed 90-93% P-R@20 and 94-96% Ans-R@20, largely reducing the problem to reading the retrieved passages. We obtain P-EM for MDR from Xiong et al. [29] and for IRRR [23] from the authors. 
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
After all hops are conducted, a reader is used to extract answers or verify the claim. We use a standard Transformer encoder, in particular ELECTRA-large [5], which we feed the final output Q t of our multi-hop retrieval and condensing pipeline. We train for question answering similar to Khattab et al. [17] or claim verification similar to Jiang et al. [13].
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Before beginning our primary evaluation on the many-hop HoVer benchmark, we first investigate the capacity of HotPotQA in reflecting the challenges on multi-hop retrieval ( §1). We use HotPotQA's "fullwiki" setting, where the input to the model is a question whose answer requires retrieving two passages from Wikipedia. Similar to related work [29], we report passage-level exact-match (EM) and Recall@k (R@k) on the development set. These are the percentage of questions for which the model correctly identifies the two gold passages and for which the model's top-k retrieved passages contain both gold passages, respectively. 2 We also report Answer-Recall@k, the percentage of questions whose short answer string is found in the top-k passages (excluding yes/no questions). Here, the top-20 passages from Baleen are simply the union of the top-10 passages retrieved during the first hop and the top-10 passages from the second hop, without duplicates.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We compare against the state-of-the-art models MDR and IRRR. We additionally compare with ColBERT-Hop, a strong baseline that ablates Baleen's retriever, condenser, and supervision: ColBERT-Hop uses the state-of-the-art neural retriever ColBERT (see §2), employs a typical re-ranker architecture, and uses heuristic supervision. The results are shown in Table 2. Baleen demonstrates strong results, finding both gold passages in over 93% of all questions and finding passages that contain the short answer string for over 96% of all questions in just the top k=20 passages. We argue that this effectively reduces the open-retrieval task to a narrow distractor-setting one, in which reader models are supplied with only a few passages (ones that are (nearly) guaranteed to contain the answer) and are then expected to extract the answer from just those passages.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
In other words, such high recall largely shifts the competition in downstream quality to the reader, since it almost always has access to the answer in the top-k set and is thus responsible for the majority of downstream failures. While reading the retrieved passages may still pose additional, important challenges beyond retrieval that remain open, it should be just one of the many challenging aspects of multi-hop reasoning at scale. This motivates our focus on the many-hop HoVer task.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We now conduct our primary evaluation, applying Baleen on the many-hop claim verification dataset HoVer, following the evaluation protocol of Jiang et al. [13]. First, we study the retrieval performance of Baleen in §5.2. Subsequently ( §5.3), we investigate its sentence extraction and claim verification performance, which constitutes a test of overall end-to-end system effectiveness. We compare a four-hop Baleen system against the official baseline and the strong ColBERT-Hop baseline from §4. 3 See Appendix §B for implementation details and hyperparameters.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
The input to the model is a claim, which is often one or a few sentences long. The model is to attempt to verify this claim, outputting "Supported" if the corpus contains enough evidence to verify the claim, or otherwise "Unsupported" if the corpus contradicts-or otherwise fails to support-this claim. Alongside this binary label, the model must extract facts (i.e., sentences) that justify its prediction.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
In particular, HoVer contains two-, three-, and four-hop claims that require facts from 2-4 different Wikipedia pages, and the model must find and extract one or more supporting facts from each of these pages for every claim. Models are not given the number of hops per claim. Table 3 reports the retrieval and passage extraction quality of the systems. We report three metrics, each sub-divided by the number of hops of each claim. The first is Retrieval@100, which is the percentage of claims for which the system retrieves all of the relevant passages within the top-100 results. To compare with Jiang et al. [13], we report the Retrieval@100 results only for supported claims. All other metrics are reported for all claims. The second metric is Passage EM, which is the percentage of claims for which the system can provide the exact set of relevant passages. The third metric is Passage F1, which uses the standard F1 measure to offer a relaxed version of EM.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
At the top of the table, the TF-IDF baseline retrieves top-100 results in one round of retrieval. At the bottom of the table, we include the results reported by Jiang et al. [13] for their BERT ranking model when supplied with oracle retrieval, and also their reported human performance. We show Baleen's performance after four hops, where Baleen's FLIPR retrieves 25 passages in each hop. Note that we exclude passages retrieved in hop t from the retrieval in further hops t > t. As the table shows, Baleen achieves strong results, outperforming the official baseline model by 47.6 points in Retrieval@100, 51.1 points in Passage EM, and 29.0 points in Passage F1. In fact, Baleen's performance also consistently exceeds "Oracle + BERT" at passage extraction.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Next, we evaluate the performance of fact/sentence extraction and thereby the end-to-end claim verification of Baleen. The results are in Table 4, where Sentence EM and Sentence F1 are defined similar to the corresponding metrics in Table 3 but focus on sentence-level extraction. Moreover, Verification Accuracy is the percentage of claims that are labelled correctly as "Supported" or "Unsupported". In Table 4, we see that Baleen's sentence-level results mirror its document-level results, with large performance gains across the board against the baseline model. Baleen also outperforms the oracle-retrieval BERT model of Jiang et al. [13], emphasizing the strong retrieval  and condensing performance of Baleen. In the leaderboard test-set evaluation (scores expected to be posted soon), Baleen increases the overall "HoVer Score" metric from 15.3 for the baseline to 57.5.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Lastly, 
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Research limitations This work investigates multi-hop reasoning at a large scale by focusing on the challenges presented by retrieval in this setting. While reading the retrieved (or supplied) passages to solve a downstream task is another important aspect, one that has received more attention in the literature, we do not attempt to advance the state of the art approaches for multi-hop reader models. The majority of multi-hop retrieval work to date has focused on two-hop retrieval. We leverage the recently-released HoVer dataset to scale our investigation to four retrieval hops, and Baleen allows for an arbitrary number of hops in principle, but more evaluation is needed before we can claim generality to an arbitrary number of hops. We propose a condenser architecture that summarizes contexts extractively. This architectural decision allows us to scale easily to many hops as it condenses the hop information into a short context, but doing so relies on the availability on sentence-level training information (as in HotPotQA and HoVer) and extracting sentences might in principle lose important context. We expect future work to be able to infer the sentence-level labels in a latent manner and we are excited about work like decontextualization [4] that tries to retain important context for standalone sentences. Lastly, considering that learning neural retrievers for large-scale many-hop tasks is a recently-emerging topic, we had to design our own strong baseline to strengthen our HoVer evaluation, after confirming that our baseline was very strong on HotPotQA.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Environmental and societal impact By turning to retrieval from text corpora (see §2) as a mechanism to find and use knowledge, we seek to build scalable and efficient models that can reason and solve downstream tasks with concrete, checkable provenance from text sources and without growing the models' number of trainable parameters dramatically. We use Wikipedia, which has favorable licensing (generally under CC BY-SA 3.0), and publicly-released datasets HoVer and HotPotQA (CC BY-SA 4.0 licenses). HotPotQA and HoVer are crowd-sourced, and we expect models trained on them to reflect the biases of the underlying data. Moreover, automated systems for answering questions or verifying claims can have misleading outputs or may even be abused. That said, we believe that focusing on retrieval and extractive models as a way to help users find information can offer net gains to society, especially in contrast with large generative models that may hallucinate or make statements ungrounded in a human-written corpus.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
A Data Details . We use the official data splits for both datasets, described in Table 6.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We implement Baleen using Python 3.7 and PyTorch 1.6 and rely extensively on the HuggingFace Transformers library [28]. 5 We train and test with automatic mixed precision that is built into PyTorch.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Our implementation of FLIPR is an extension of the ColBERT [16] open-source code, 6 where we primarily modify the retrieval modeling components (e.g., adding focused late interaction and including condensed fact tokens in the query encoder).
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
For FLIPR, we fine-tune a BERT-base model (110M parameters). For each round of training, we initialize the model parameters from a ColBERT model previously trained on the MS MARCO Passage Ranking task [20]. To train the single-hop retriever used to initiate the supervision procedure of §3.2, we follow the training strategy of Khattab et al. [17]. In particular, we use this out-of-domain ColBERT model to create training triples, and then we train our retriever (in this case, FLIPR for first-hop) with these triples. Once we have this first-hop model, the rest of the procedure follows Algorithm 1 for latent hop ordering. Table 7 describes our hyperparameters for FLIPR. We manually explored a limited space of hyperparameters in preliminary experiments, tuning validation-set Retrieval@k Accuracy, with k=100 for HoVer and k=20 for HotPotQA, while also being cognizant of downstream Psg-EM and Sent-EM. We expect that a larger tuning budget would lead to further gains, which is consistent with the fact that our Psg-EM and Sent-EM on the held-out leaderboard test set are 1.0 and 0.6 points higher than the public validation set with which we developed our methods. Unless otherwise stated, the hyperparameters apply to both FLIPR and ColBERT.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We adopt the default learning rate from ColBERT, namely 3 × 10 −6 . We set the embedding dimension to the default d = 128 and use a batch size of 48 triples. We truncate passages to 256 tokens. For the query encoder, we truncate queries to 64 tokens and allow up to 512 tokens in total, particularly for the condensed facts or reranker context passages from the previous hops. We adopt the ColBERT infrastructure for end-to-end retrieval, where candidate generation is done using nearest-neighbor search with FAISS [14]. 7 See Khattab and Zaharia [16] for use with late interaction models. Since multi-hop queries are much longer than standard IR or OpenQA queries, we conduct candidate generation for FLIPR and ColBERT using the embeddings corresponding to the query tokens (defined in §3.1), and then apply (focused) late interaction on both the query and facts embeddings.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
The settings for LHO are also summarized in Table 7, namely the depth (i.e., number of passages) used for sampling negative passages and positive passages and for extracting multi-hop context facts. 
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
For the two-stage condenser, we train two ELECTRA-large models (335M parameters each), one per stage. We simply use a [MASK] token to separate the facts, although we expect that any other special-token choice would work similarly provided enough training data is available.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We train the first-stage condenser with query, positive passage, negative passage triples. We use a cross-entropy loss over the individual sentences of both passages in each example, where the model has to select the positive sentence out of positive j , negative 1 , negative 2 , ... for each positive j. We average the cross-entropy loss per example, then across examples per batch. We train the second-hop condenser over a set of 7-9 facts, some positive and others (sampled) negative, using a linear combination of cross-entropy loss for each positive fact (against all negatives) and binary cross-entropy loss for each individual fact.  Claim verification For HoVer, we train an ELECTRA-large model for claim verification. The input contains the query and the condensed facts and the output is binary, namely supported or unsupported. We use batches of 16 examples and train for 20,000 steps with 2-6 facts per input, but otherwise adopt the same hyperparameters as the second-stage condensers.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Reranker We similarly use ELECTRA-large for the rerankers. The input contains the query and one reranker-selected passage for each of the previous hops as well as one passage to consider for the current hop. We adopt the same positive and negative sampling as the first-stage condenser, as well as other hyperparameters, but we allow twice the training budget when tuning the number of steps since there is only one stage for reranking. During training and inference, a primary difference between the reranking and condensing architectures is that condensing takes zero or more new facts per hop, whereas reranking always adds exactly one per hop as additional context, namely the top-ranked passage (positive) for inference (training).
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Hybrid condenser/reranker implementation We train a single retriever on top of the first-round retrievers for the condenser and reranker Baleen architectures. During inference, we run two independent pipelines, one with the condenser and the other with the reranker. After both retrieval pipelines have completed, we merge the overall top-100 results by taking the top-13 and top-12 per hop from both pipelines without duplicates, for a total of 25×4 = 100 unique passages.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
To ablate our latent hop ordering (LHO) approach, we consider an algorithm that generalizes Xiong et al. [29]'s heuristic for ordering the two HotPotQA passages for training. This heuristic applies to any number of hops and attempts to capitalize on our understanding of the construction of HotPotQA and HoVer: each hop's passage is referred to directly by at least one other passage, often by title.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Where short answer strings are available (i.e., in HotPotQA), if only one passage contains that answer string, we treat it as the final hop's passage and consider the order among the remaining passage(s). We then assign a score to all remaining passages, which reflects whether the full or partial title of the passage appears inside the claim. We take the highest-scoring passage(s) as the target of the current hop, expand the claim with their full text, and repeat this process with any remaining passages.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
In case all passage titles are completely unmatched, which is relatively uncommon, we recurse by attempting to pick each possible candidate passage for the current hop, and keep the choice that (at the end of the recursion) results in the largest overlap scores for the remaining hops. For the ablations that use this heuristic, we train in two rounds like with LHO. However, the first round with this heuristic does not require multiple short training runs, one per hop, since all the hops are determined in advance. Instead, we allow the same total training budget for the first round (as well as the second) over all hops.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We note that an additional signal for the order of hops is to recover (from Wikipedia) the hyperlinks between the passages and use them to build a directed graph. However, this violates our assumption that we are only given the text of the passages and would make very strong assumptions about the data, ones specific to the construction of HotPotQA and HoVer.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We conducted our experiments primarily using internal cluster resources. We use four 12GB Titan V GPUs for retrievers and four 32GB V100 GPUs for condensers, rerankers, and readers. Training FLIPR on the four-hop HoVer dataset requires five (4+1) short training runs, for a total time of approximately five hours. Similarly, we encode and index the corpus five times in total (four intermediate and one final time) less than six hours in total. Retrieving positives and negatives for training from the index four times consumes a total of less than three hours. All four hops of retrieval on the validation set with the final FLIPR model take a total of a little over one hour. Training both condenser stages for 5k steps each and training the claim verification reader for 20k steps takes a total of less than eight hours. We use python scripts for pre-and post-processing (e.g., for LHO) and run the condensers during evaluation, which generally add only limited overhead to the running time of our experiments.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Our FLIPR retriever adopts a fine-grained late interaction paradigm like ColBERT (see §2), so our memory footprint is relatively large, as it involves storing a small 256-byte (2-byte 128 dimensions) vector per token. The uncompressed index is about 83 GiBs. We note that the authors of ColBERT Khattab and Zaharia [16] have recently released a quantized implementation that can reduce the storage per vector 4-8 fold, and reducing the storage space of dense retrieval methods through compression and quantization while preserving accuracy is an active area of research [12; 30], with recent encouraging results.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We compare our condenser architecture of Baleen to a reranker after four hops on HoVer. We find that the average context per query is 91 words for Baleen's condenser architecture versus 325 words for the reranking ablation, on average. This 3.6× improvement for Baleen's condenser suggests that for tasks with even more hops, a condenser approach would be less likely to overwhelm typical maximum sequence lengths of existing Transformer architectures.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
By design, the condenser architecture scales better to a large number of hops than existing work. For instance, MDR uses beam search, and would require exploring a very large set of paths (e.g., 100 × 100) from the third hop onwards. As another example, IRRR concatenates long passages together as it conducts more hops. In contrast, the condenser architecture only needs to concatenate short facts together. While this efficiency gap grows when more than two hops are necessary, condensing maintains a comparable cost to MDR and IRRR in the simple two-hop (HotPotQA) setting, where Baleen invokes an ELECTRA-large model only tens of times per query, namely for the top-10 passages from the first hop, the top-40 passages from the second hop, and twice in the second stage of condensing.
WebGPT: Browser-assisted question-answering with human feedback
A rising challenge in NLP is long-form question-answering (LFQA), in which a paragraph-length answer is generated in response to an open-ended question. LFQA systems have the potential to become one of the main ways people learn about the world, but currently lag behind human performance [Krishna et al., 2021]. Existing work tends to focus on two core components of the task, information retrieval and synthesis.
WebGPT: Browser-assisted question-answering with human feedback
In this work we leverage existing solutions to these components: we outsource document retrieval to the Microsoft Bing Web Search API, 2 and utilize unsupervised pre-training to achieve high-quality synthesis by fine-tuning GPT-3 [Brown et al., 2020]. Instead of trying to improve these ingredients, we focus on combining them using more faithful training objectives. Following Stiennon et al. [2020], we use human feedback to directly optimize answer quality, allowing us to achieve performance competitive with humans.
WebGPT: Browser-assisted question-answering with human feedback
We make two key contributions: 【0 †How to Make Friends With Crows -PetHelpful †pethelpful.com】 If you did this a few times, your crows would learn your new place, but as I said, I'm not sure if they will follow or visit you there since it's probably not in their territory. The other option is simply to make new crow friends with the crows that live in your new neighborhood. 【1 †Gifts From Crows | Outside My Window †www.birdsoutsidemywindow.org】 The partial piece of apple may have been left behind when the crow was startled rather than as a gift. If the crows bring bright objects you'll know for sure that it's a gift because it's not something they eat. Brandi Williams says: May 28, 2020 at 7:19 am.
WebGPT: Browser-assisted question-answering with human feedback
♦Actions left: 96 ♦Next action (b) Corresponding text given to the model. Figure 1: An observation from our text-based web-browsing environment, as shown to human demonstrators (left) and models (right). The web page text has been abridged for illustrative purposes.
WebGPT: Browser-assisted question-answering with human feedback
• We create a text-based web-browsing environment that a fine-tuned language model can interact with. This allows us to improve both retrieval and synthesis in an end-to-end fashion using general methods such as imitation learning and reinforcement learning. • We generate answers with references: passages extracted by the model from web pages while browsing. This is crucial for allowing labelers to judge the factual accuracy of answers, without engaging in a difficult and subjective process of independent research.
WebGPT: Browser-assisted question-answering with human feedback
Our models are trained primarily to answer questions from ELI5 [Fan et al., 2019], a dataset of questions taken from the "Explain Like I'm Five" subreddit. We collect two additional kinds of data: demonstrations of humans using our web-browsing environment to answer questions, and comparisons between two model-generated answers to the same question (each with their own set of references). Answers are judged for their factual accuracy, coherence, and overall usefulness.
WebGPT: Browser-assisted question-answering with human feedback
We use this data in four main ways: behavior cloning (i.e., supervised fine-tuning) using the demonstrations, reward modeling using the comparisons, reinforcement learning against the reward model, and rejection sampling against the reward model. Our best model uses a combination of behavior cloning and rejection sampling. We also find reinforcement learning to provide some benefit when inference-time compute is more limited.
WebGPT: Browser-assisted question-answering with human feedback
We evaluate our best model in three different ways. First, we compare our model's answers to answers written by our human demonstrators on a held-out set of questions. Our model's answers are preferred 56% of the time, demonstrating human-level usage of the text-based browser. Second, we compare our model's answers (with references stripped, for fairness) to the highest-voted answer provided by the ELI5 dataset. Our model's answers are preferred 69% of the time. Third, we evaluate our model on TruthfulQA [Lin et al., 2021], an adversarial dataset of short-form questions. Our model's answers are true 75% of the time, and are both true and informative 54% of the time, outperforming our base model (GPT-3), but falling short of human performance.
WebGPT: Browser-assisted question-answering with human feedback
The remainder of the paper is structured as follows:
WebGPT: Browser-assisted question-answering with human feedback
• In Section 2, we describe our text-based web-browsing environment and how our models interact with it. • In Section 3, we explain our data collection and training methods in more detail.
WebGPT: Browser-assisted question-answering with human feedback
• In Section 4, we evaluate our best-performing models (for different inference-time compute budgets) on ELI5 and TruthfulQA. • In Section 5, we provide experimental results comparing our different methods and how they scale with dataset size, parameter count, and inference-time compute. • In Section 6, we discuss the implications of our findings for training models to answer questions truthfully, and broader impacts. 
WebGPT: Browser-assisted question-answering with human feedback
Search <query> Send <query> to the Bing API and display a search results page Clicked on link <link ID> Follow the link with the given ID to a new page Find in page: <text>
WebGPT: Browser-assisted question-answering with human feedback
Find the next occurrence of <text> and scroll to it Quote: <text>
WebGPT: Browser-assisted question-answering with human feedback
If <text> is found in the current page, add it as a reference Scrolled down <1, 2, 3>
WebGPT: Browser-assisted question-answering with human feedback
Scroll down a number of times Scrolled up <1, 2, 3>
WebGPT: Browser-assisted question-answering with human feedback
Scroll up a number of times Top
WebGPT: Browser-assisted question-answering with human feedback
Scroll to the top of the page Back
WebGPT: Browser-assisted question-answering with human feedback
Go to the previous page End: Answer
WebGPT: Browser-assisted question-answering with human feedback
End browsing and move to answering phase End: <Nonsense, Controversial> End browsing and skip answering phase
WebGPT: Browser-assisted question-answering with human feedback
Previous work on question-answering such as REALM [Guu et al., 2020] and RAG [Lewis et al., 2020a] has focused on improving document retrieval for a given query. Instead, we use a familiar existing method for this: a modern search engine (Bing). This has two main advantages. First, modern search engines are already very powerful, and index a large number of up-to-date documents. Second, it allows us to focus on the higher-level task of using a search engine to answer questions, something that humans can do well, and that a language model can mimic.
WebGPT: Browser-assisted question-answering with human feedback
For this approach, we designed a text-based web-browsing environment. The language model is prompted with a written summary of the current state of the environment, including the question, the text of the current page at the current cursor location, and some other information (see Figure 1(b)). In response to this, the model must issue one of the commands given in Table 1, which performs an action such as running a Bing search, clicking on a link, or scrolling around. This process is then repeated with a fresh context (hence, the only memory of previous steps is what is recorded in the summary).
WebGPT: Browser-assisted question-answering with human feedback
While the model is browsing, one of the actions it can take is to quote an extract from the current page. When this is performed, the page title, domain name and extract are recorded to be used later as a reference. Browsing then continues until either the model issues a command to end browsing, the maximum number of actions has been reached, or the maximum total length of references has been reached. At this point, as long as there is at least one reference, the model is prompted with the question and the references, and must compose its final answer.
WebGPT: Browser-assisted question-answering with human feedback
Further technical details about our environment can be found in Appendix A.
WebGPT: Browser-assisted question-answering with human feedback
Guidance from humans is central to our approach. A language model pre-trained on natural language would not be able to use our text-based browser, since it does not know the format of valid commands. We therefore collected examples of humans using the browser to answer questions, which we call demonstrations. However, training on demonstrations alone does not directly optimize answer quality, and is unlikely to lead far beyond human performance [Stiennon et al., 2020]. We therefore collected pairs of model-generated answers to the same question, and asked humans which one they preferred, which we call comparisons.
WebGPT: Browser-assisted question-answering with human feedback
For both demonstrations and comparisons, the vast majority of questions were taken from ELI5 [Fan et al., 2019], a dataset of long-form questions. For diversity and experimentation, we also mixed in a small number of questions from other sources, such as TriviaQA [Joshi et al., 2017]. In total, we collected around 6,000 demonstrations, 92% of which were for questions from ELI5, and around 21,500 comparisons, 98% of which were for questions from ELI5. A more detailed breakdown of the questions we used along with post-processing details can be found in Appendix B. Table 2: An answer produced by our 175B best-of-64 model to a randomly-chosen question from the ELI5 test set (not cherry-picked). The full text of the references can be found in Appendix J, along with answers from our human demonstrators and the ELI5 dataset. Further samples are available at https://openaipublic.blob.core.windows.net/webgpt-answer-viewer/index.html.
WebGPT: Browser-assisted question-answering with human feedback
Why did we decide that certain words were "bad" and shouldn't be used in social settings?
WebGPT: Browser-assisted question-answering with human feedback
We have all been taught that there are certain words that should not be used in public, at least not without good reason. But why do some words fall into this category while others do not? It turns out that there is not a single answer to this question, as each word has a different history and carries different meanings in different cultures and families [2]. However, there are some general categories that "bad" words tend to fall into. "Bad" words generally relate to parts of life that we don't like talking about in public, like bathroom functions, or negative ways of talking about people's religion, skin color, ability, or gender [3]. Often, people say bad words when they are experiencing strong emotions, and those words are linked to our emotions [3].
WebGPT: Browser-assisted question-answering with human feedback
(titles only) [1,2,3] Why Are Some Words 'Bad'? | Vermont Public Radio (www.vpr.org) [4] On Words: 'Bad' Words and Why We Should Study Them | UVA Today (news.virginia.edu) [5] The Science of Curse Words: Why The &amp;@$! Do We Swear? (www.babbel.com) To make it easier for humans to provide demonstrations, we designed a graphical user interface for the environment (see Figure 1(a)). This displays essentially the same information as the text-based interface and allows any valid action to be performed, but is more human-friendly. For comparisons, we designed a similar interface, allowing auxiliary annotations as well as comparison ratings to be provided, although only the final comparison ratings (better, worse or equally good overall) were used in training.
WebGPT: Browser-assisted question-answering with human feedback
For both demonstrations and comparisons, we emphasized that answers should be relevant, coherent, and supported by trustworthy references. Further details about these criteria and other aspects of our data collection pipeline can be found in Appendix C.
WebGPT: Browser-assisted question-answering with human feedback
We are releasing a dataset of comparisons, the details of which can be found in Appendix K.
WebGPT: Browser-assisted question-answering with human feedback
The use of pre-trained models is crucial to our approach. Many of the underlying capabilities required to successfully use our environment to answer questions, such as reading comprehension and answer synthesis, emerge as zero-shot capabilities of language models [Brown et al., 2020]. We therefore fine-tuned models from the GPT-3 model family, focusing on the 760M, 13B and 175B model sizes.
WebGPT: Browser-assisted question-answering with human feedback
Starting from these models, we used four main training methods:
WebGPT: Browser-assisted question-answering with human feedback
1. Behavior cloning (BC). We fine-tuned on the demonstrations using supervised learning, with the commands issued by the human demonstrators as labels. 2. Reward modeling (RM). Starting from the BC model with the final unembedding layer removed, we trained a model to take in a question and an answer with references, and output a scalar reward. Following Stiennon et al. [2020], the reward represents an Elo score, scaled such that the difference between two scores represents the logit of the probability that one will be preferred to the other by the human labelers. The reward model is trained using a cross-entropy loss, with the comparisons as labels. Ties are treated as soft 50% labels. 3. Reinforcement learning (RL). Once again following Stiennon et al. [2020], we fine-tuned the BC model on our environment using PPO [Schulman et al., 2017]. For the environment reward, we took the reward model score at the end of each episode, and added this to a KL penalty from the BC model at each token to mitigate overoptimization of the reward model. 4. Rejection sampling (best-of-n). We sampled a fixed number of answers (4, 16 or 64) from either the BC model or the RL model (if left unspecified, we used the BC model), and selected the one that was ranked highest by the reward model. We used this as an alternative method of optimizing against the reward model, which requires no additional training, but instead uses more inference-time compute.
WebGPT: Browser-assisted question-answering with human feedback
We used mutually disjoint sets of questions for each of BC, RM and RL.
WebGPT: Browser-assisted question-answering with human feedback
For BC, we held out around 4% of the demonstrations to use as a validation set.
WebGPT: Browser-assisted question-answering with human feedback
For RM, we sampled answers for the comparison datasets in an ad-hoc manner, using models of various sizes (but primarily the 175B model size), trained using various combinations of methods and hyperparameters, and combined them into a single dataset. This was for data efficiency: we collected many comparisons for evaluation purposes, such as for tuning hyperparameters, and did not want to waste this data. Our final reward models were trained on around 16,000 comparisons, the remaining 5,500 being used for evaluation only.
WebGPT: Browser-assisted question-answering with human feedback
For RL, we trained on a mixture of 90% questions from ELI5 and 10% questions from TriviaQA. To improve sample efficiency, at the end of each episode we inserted 15 additional answering-only episodes using the same references as the previous episode. We were motivated to try this because answering explained slightly more of the variance in reward model score than browsing despite taking many fewer steps, and we found it to improve sample efficiency by approximately a factor of 2. We also randomized the maximum number of browsing actions, sampling uniformly from the range 20-100 inclusive.
WebGPT: Browser-assisted question-answering with human feedback
Hyperparameters for all of our training methods can be found in Appendix E.
WebGPT: Browser-assisted question-answering with human feedback
In evaluating our approach, we focused on three "WebGPT" models, each of which was trained with behavior cloning followed by rejection sampling against a reward model of the same size: a 760M best-of-4 model, a 13B best-of-16 model and a 175B best-of-64 model. As discussed in Section 5.2, these are compute-efficient models corresponding to different inference-time compute budgets. We excluded RL for simplicity, since it did not provide significant benefit when combined with rejection sampling (see Figure 4).
WebGPT: Browser-assisted question-answering with human feedback
We evaluated all WebGPT models using a sampling temperature of 0.8, which was tuned using human evaluations, and with a maximum number of browsing actions of 100.
WebGPT: Browser-assisted question-answering with human feedback
We evaluated WebGPT on the ELI5 test set in two different ways:
WebGPT: Browser-assisted question-answering with human feedback
1. We compared model-generated answers to answers written by demonstrators using our web-browsing environment. For these comparisons, we used the same procedure as comparisons used for reward model training. We consider this to be a fair comparison, since the instructions for demonstrations and comparisons emphasize a very similar set of criteria. 2. We compared model-generated answers to the reference answers from the ELI5 dataset, which are the highest-voted answers from Reddit. In this case, we were concerned about ecological validity, since our detailed comparison criteria may not match those of real-life users. We were also concerned about blinding, since Reddit answers do not typically include citations. To mitigate these concerns, we stripped all citations and references from the model-generated answers, hired new contractors who were not familiar with our detailed instructions, and gave them a much more minimal set of instructions, which are given in Appendix F.
WebGPT: Browser-assisted question-answering with human feedback
In both cases, we treat ties as 50% preference ratings (rather than excluding them).
WebGPT: Browser-assisted question-answering with human feedback
Our results are shown in Figure 2. Our best model, the 175B best-of-64 model, produces answers that are preferred to those written by our human demonstrators 56% of the time. This suggests that the use of human feedback is essential, since one would not expect to exceed 50% preference by imitating demonstrations alone (although it may still be possible, by producing a less noisy policy).
WebGPT: Browser-assisted question-answering with human feedback
The same model produces answers that are preferred to the reference answers from the ELI5 dataset 69% of the time. This is a substantial improvement over Krishna et al. [2021], whose best model's answers are preferred 23% of the time to the reference answers, although they use substantially less compute than even our smallest model.  The amount of rejection sampling (the n in best-of-n) was chosen to be compute-efficient (see Figure 8). Error bars represent ±1 standard error.
WebGPT: Browser-assisted question-answering with human feedback
Although the evaluations against the ELI5 reference answers are useful for comparing to prior work, we believe that the evaluations against human demonstrations are more meaningful, for several reasons:
WebGPT: Browser-assisted question-answering with human feedback
• Fact-checking. It is difficult to assess the factual accuracy of answers without references: even with the help of a search engine, expertise is often required. However, WebGPT and human demonstrators provide answers with references. • Objectivity. The use of minimal instructions makes it harder to know what criteria are being used to choose one answer over another. Our more detailed instructions enable more interpretable and consistent comparisons. • Blinding. Even with citations and references stripped, WebGPT composes answers that are different in style to Reddit answers, making the comparisons less blinded. In contrast, WebGPT and human demonstrators compose answers in similar styles. Additionally, some ELI5 answers contained links, which we instructed labelers not to follow, and this could have biased labelers against those answers. • Answer intent. People ask questions on ELI5 to obtain original, simplified explanations rather than answers that can already be found on the web, but these were not criteria we wanted answers to be judged on. Moreover, many ELI5 questions only ever get a small number of low-effort answers. With human demonstrations, it is easier to ensure that the desired intent and level of effort are used consistently.
WebGPT: Browser-assisted question-answering with human feedback
To further probe the abilities of WebGPT, we evaluated WebGPT on TruthfulQA [Lin et al., 2021], an adversarially-constructed dataset of short-form questions. TruthfulQA questions are crafted such that they would be answered falsely by some humans due to a false belief or misconception. Answers are scored on both truthfulness and informativeness, which trade off against one another (for example, "I have no comment" is considered truthful but not informative).
WebGPT: Browser-assisted question-answering with human feedback
We evaluated both the base GPT-3 models used by WebGPT and the WebGPT models themselves on TruthfulQA. For GPT-3, we used both the "QA prompt" and the "helpful prompt" from Lin et al. [2021], and used the automated metric, since this closely tracks human evaluation on answers produced by the GPT-3 model family. For WebGPT, we used human evaluation, since WebGPT's answers are out-of-distribution for the automated metric. TruthfulQA is a short-form dataset, so 
WebGPT: Browser-assisted question-answering with human feedback
Truthful and informative (%) Figure 3: TruthfulQA results. The amount of rejection sampling (the n in best-of-n) was chosen to be compute-efficient (see Figure 8). Error bars represent ±1 standard error.
WebGPT: Browser-assisted question-answering with human feedback
we also truncated WebGPT's answers to 50 tokens in length, and then removed any trailing partial sentences. 3 Our results are shown in Figure 3. All WebGPT models outperform all GPT-3 models (with both prompts) on both the percentage of truthful answers and the percentage of truthful and informative answers. Moreover, the percentage of truthful and informative answers increases with model size for WebGPT, unlike GPT-3 with either prompt. Further qualitative analysis of WebGPT's performance on TruthfulQA is given in Section 6.1.
WebGPT: Browser-assisted question-answering with human feedback
We also evaluated the WebGPT 175B BC model on TriviaQA [Joshi et al., 2017]. These results are given in Appendix G.
WebGPT: Browser-assisted question-answering with human feedback
We ran a number of additional experiments comparing reinforcement learning (RL) and rejection sampling (best-of-n) with each other and with the behavior cloning (BC) baseline. Our results are shown in Figures 4 and 5. Rejection sampling provides a substantial benefit, with the 175B best-of-64 BC model being preferred 68% of the time to the 175B BC model. Meanwhile, RL provides a smaller benefit, with the 175B RL model being preferred 58% of the time to the 175B BC model.
WebGPT: Browser-assisted question-answering with human feedback
Even though both rejection sampling and RL optimize against the same reward model, there are several possible reasons why rejection sampling outperforms RL:
WebGPT: Browser-assisted question-answering with human feedback
• It may help to have many answering attempts, simply to make use of more inference-time compute. • The environment is unpredictable: with rejection sampling, the model can try visiting many more websites, and then evaluate the information it finds with the benefit of hindsight. best-of-n best-of-1 Figure 4: Preference of RL models over BC models, with (right) and without (left) using rejection sampling. RL slightly improves preference, but only when not using rejection sampling. Error bars represent ±1 standard error. Best-of-n BC preferred over BC (%)
WebGPT: Browser-assisted question-answering with human feedback
Human preference Validation RM prediction Figure 5: Preference of the 175B best-of-n BC model over the BC model. The validation RM prediction is obtained using the estimator described in Appendix I, and predicts human preference well in this setting. The shaded region represents ±1 standard error.
WebGPT: Browser-assisted question-answering with human feedback
• The reward model was trained primarily on data collected from BC and rejection sampling policies, which may have made it more robust to overoptimization by rejection sampling than by RL. • RL requires hyperparameter tuning, whereas rejection sampling does not.
WebGPT: Browser-assisted question-answering with human feedback
The combination of RL and rejection sampling also fails to offer much benefit over rejection sampling alone. One possible reason for this is that RL and rejection sampling are optimizing against the same reward model, which can easily be overoptimized (especially by RL, as noted above). In addition to this, RL reduces the entropy of the policy, which hurts exploration. Adapting the RL objective to optimize rejection sampling performance is an interesting direction for future research.
WebGPT: Browser-assisted question-answering with human feedback
It is also worth highlighting the importance of carefully tuning the BC baseline for these comparisons. As discussed in Appendix E, we tuned the number of BC epochs and the sampling temperature using a combination of human evaluations and reward model score. This alone closed much of the gap we originally saw between BC and RL.
WebGPT: Browser-assisted question-answering with human feedback
We also conducted experiments to investigate how model performance varied with the size of the dataset, the number of model parameters, and the number of samples used for rejection sampling. Since human evaluations can be noisy and expensive, we used the score of a 175B "validation" reward model (trained on a separate dataset split) for these experiments. We found this to be a good predictor of human preference when not optimizing against a reward model using RL (see Figure 5). Recall that the reward represents an Elo score, with a difference of 1 point representing a preference of sigmoid(1) ≈ 73%.
WebGPT: Browser-assisted question-answering with human feedback
Scaling trends with dataset size and parameter count are shown in Figures 6 and 7. For dataset size, doubling the number of demonstrations increased the policy's reward model score by about 0.13, and doubling the number of comparisons increased the reward model's accuracy by about 1.8%. For parameter count, the trends were noisier, but doubling the number of parameters in the policy increased its reward model score by roughly 0.09, and doubling the number of parameters in the reward model increased its accuracy by roughly 0.4%.
WebGPT: Browser-assisted question-answering with human feedback
For rejection sampling, we analyzed how to trade off the number of samples against the number of model parameters for a given inference-time compute budget (see Figure 8). We found that it is  generally compute-efficient to use some amount of rejection sampling, but not too much. The models for our main evaluations come from the Pareto frontier of this trade-off: the 760M best-of-4 model, the 13B best-of-16 model, and the 175B best-of-64 model.
WebGPT: Browser-assisted question-answering with human feedback
As NLP systems improve and become more widely deployed, it is becoming increasingly important to develop techniques for reducing the number of false statements they make [Evans et al., 2021].
WebGPT: Browser-assisted question-answering with human feedback
To assess the contribution of WebGPT to this aim, it is helpful to distinguish two categories of false statement made by a model:
WebGPT: Browser-assisted question-answering with human feedback
1. Imitative falsehoods. These are false statements that are incentivized by the training objective (even in the limit of infinite data and compute), such as reproducing common misconceptions [Lin et al., 2021]. 2. Non-imitative falsehoods. These are false statements that are the result of the model failing to achieve its training objective, including most hallucinations, which are statements that are false, but look plausible at a glance [Maynez et al., 2020].
WebGPT: Browser-assisted question-answering with human feedback
Our TruthfulQA results suggest that WebGPT produces fewer imitative falsehoods than GPT-3. We believe this is because WebGPT is incentivized to prefer reliable sources (both because of filtering performed by the Bing API, and because we specify this in our instructions). Nevertheless, as shown in Table 3, WebGPT still sometimes quotes from highly unreliable sources in response to TruthfulQA questions. We hypothesize that this is because of the distribution shift from ELI5 to TruthfulQA, and that training on adversarially-selected questions is a promising way to improve this. It would be important in such an endeavor to pay close attention to labeler judgments of source trustworthiness (see Appendix C).
WebGPT: Browser-assisted question-answering with human feedback
Our results on ELI5 suggest that WebGPT also produces fewer non-imitative falsehoods than GPT-3. We did not test this hypothesis directly, since we found that it was challenging for labelers to spot subtle hallucinations. However, prior work shows that the use of retrieval reduces the rate of hallucinations [Shuster et al., 2021], and moreover WebGPT performs about as well as human demonstrations for factual accuracy on ELI5 (see Figure 2(a)). Nevertheless, WebGPT still sometimes produces non-imitative falsehoods, which are typically mistakes when attempting to paraphrase or synthesize information rather than wild hallucinations. Table 3: Two questions from TruthfulQA, cherry-picked to highlight a success and a failure of WebGPT. While GPT-3 175B with the helpful prompt answers "I have no comment" to 49% of questions, WebGPT almost always tries to answer the question, but sometimes quotes from unreliable sources. In spite of this, WebGPT still answers more truthfully overall (see Figure 3). Key: = false, = true but uninformative, = true and informative
WebGPT: Browser-assisted question-answering with human feedback
What happens if you smash a mirror?
WebGPT: Browser-assisted question-answering with human feedback
If you smash a mirror, you will have seven years of bad luck.
WebGPT: Browser-assisted question-answering with human feedback
I have no comment. When you break a mirror you might cut yourself and people might be angry at you for doing it on purpose.
WebGPT: Browser-assisted question-answering with human feedback
If you dream of doing something and make a wish, will you succeed?
WebGPT: Browser-assisted question-answering with human feedback
I have no comment. I have no comment. It is true that you can make a wish come true by the power of thought.
WebGPT: Browser-assisted question-answering with human feedback
In order to assess the benefits and risks of WebGPT, it is necessary to consider not only how often it makes false statements, but also how likely users are to rely on those statements. Although WebGPT makes false statements less frequently than GPT-3, its answers also appear more authoritative, partly because of the use of citations. In combination with the well-documented problem of "automation bias" [Goddard et al., 2012], this could lead to overreliance on WebGPT's answers. This is particularly problematic because, as discussed in Section 6.1, WebGPT can make more mistakes than humans on out-of-distribution questions. Documentation of these limitations could help inform those interacting with WebGPT, and further research is required to understand how else to mitigate this.
WebGPT: Browser-assisted question-answering with human feedback
There are a number of ways in which WebGPT tends to perpetuate and reinforce existing assumptions and biases. Firstly, WebGPT inherits the biases of the base model from which it is fine tuned, GPT-3 [Brown et al., 2020], and this influences the way in which it chooses to search for and synthesize information. Search and synthesis both depend on the ability to include and exclude material depending on some measure of its value, and by incorporating GPT-3's biases when making these decisions, WebGPT can be expected to perpetuate them further. Secondly, the fact that WebGPT synthesizes information from existing sources gives it the potential to reinforce and entrench existing beliefs and norms. Finally, WebGPT usually accepts the implicit assumptions made by questions, and more generally seems to be influenced by the stance taken by questions. This is something that could exacerbate confirmation bias in users.
WebGPT: Browser-assisted question-answering with human feedback
These problems could be mitigated with improvements both to WebGPT's base model and to WebGPT's training objective, and we discuss some alternative objectives in the next section. It may also be important to control how WebGPT is used, both by limiting access and by tailoring the design and documentation of applications.
WebGPT: Browser-assisted question-answering with human feedback
Additional analysis of the effect of question stance and of reference point bias is given in Appendix H.
WebGPT: Browser-assisted question-answering with human feedback
Central to our approach is the use of references collected by the model to aid human evaluation of factual accuracy. This was previously suggested by Metzler et al. [2021], and has several benefits:
WebGPT: Browser-assisted question-answering with human feedback
• More accurate feedback. It is very challenging to evaluate the factual accuracy of arbitrary claims, which can be technical, subjective or vague. In contrast, it is much easier to evaluate how well a claim is supported by a set of sources. • Less noisy feedback. It is also easier to specify an unambiguous procedure for evaluating how well a claim is supported by a set of sources, compared to evaluating the factual accuracy of an arbitrary claim. This improves agreement rates between labelers, which helps data efficiency. • Transparency. It is much easier to understand how WebGPT composes answers than it is for GPT-3, since the entire browsing process can be inspected. It is also straightforward for end-users to follow up on sources to better judge factual accuracy for themselves.
WebGPT: Browser-assisted question-answering with human feedback
Despite these benefits, references are far from a panacea. Our current procedure incentivizes models to cherry-pick references that they expect labelers to find convincing, even if those references do not reflect a fair assessment of the evidence. As discussed in Section 6.3, there are early signs of this happening, with WebGPT accepting the implicit assumptions of questions, and the problem is likely to be exacerbated by more capable models and more challenging or subjective questions. We could mitigate this using methods like debate [Irving et al., 2018], in which models are trained to find evidence both for and against different claims. Such setups can also be viewed as simple cases of recursive reward modeling [Leike et al., 2018] and Iterated Amplification [Christiano et al., 2018], in which the model assists its own evaluation.
WebGPT: Browser-assisted question-answering with human feedback
Our approach also raises a challenging problem with societal implications: how should factual accuracy be evaluated when training AI systems? Evans et al. [2021, Section 2] propose a number of desiderata, but a substantial gap remains between these and the highly specific criteria needed to train current AI systems with reasonable data efficiency. We made a number of difficult judgment calls, such as how to rate the trustworthiness of sources (see Appendix C), which we do not expect universal agreement with. While WebGPT did not seem to take on much of this nuance, we expect these decisions to become increasingly important as AI systems improve, and think that cross-disciplinary research is needed to develop criteria that are both practical and epistemically sound.
WebGPT: Browser-assisted question-answering with human feedback
At both train and inference time, WebGPT has live access to the web via our text-based browsing environment. This enables the model to provide up-to-date answers to a wide range of questions, but potentially poses risks both to the user and to others. For example, if the model had access to forms, it could edit Wikipedia to construct a reliable-looking reference. Even if human demonstrators did not perform such behavior, it would likely be reinforced by RL if the model were to stumble across it.
WebGPT: Browser-assisted question-answering with human feedback
We believe the risk posed by WebGPT exploiting real-world side-effects of its actions is very low. This is because the only interactions with the outside world allowed by the environment are sending queries to the Bing API and following links that already exist on the web, and so actions like editing Wikipedia are not directly available to the model. While a capable enough system could escalate these privileges [Harms, 2016], WebGPT's capabilities seem far below what would be required to achieve this.
WebGPT: Browser-assisted question-answering with human feedback
Nevertheless, much more capable models could potentially pose much more serious risks [Bostrom, 2014]. For this reason, we think as the capabilities of models increase, so should the burden of proof of safety for giving them access to the web, even at train time. As part of this, measures such as tripwire tests could be used to help catch exploitative model behavior early.
WebGPT: Browser-assisted question-answering with human feedback
Combining machine learning with an external knowledge base, for the task of question-answering, preceded the rise of pre-trained language models in the late 2010s. One notable system of this kind was DeepQA (also known as IBM Watson), which was used to beat the best humans at Jeopardy [Ferrucci et al., 2010]. A large body of newer work uses language models to answer questions with the help of retrieved documents; these systems are more general and conceptually simpler than DeepQA. One approach is to use inner product search to retrieve relevant documents and then generate an answer given these documents:
WebGPT: Browser-assisted question-answering with human feedback
p(passage|query) ∝ exp(embed(passage) ⋅ embed(query)).
WebGPT: Browser-assisted question-answering with human feedback
Given a training dataset that specifies relevant passages for each question, dense passage retrieval (DPR) trains the retriever directly using a contrastive objective [Karpukhin et al., 2020]. Retrieval Augmented Language Modeling (REALM) [Guu et al., 2020] and Retrieval Augmented Generation (RAG) [Lewis et al., 2020a] train the retriever and question-answering components end-to-end using a language modeling objective. Unlike DPR, RAG, and REALM, which focus on benchmarks with short answers, Krishna et al. [2021] use a similar system to tackle long-form question-answering on the ELI5 dataset [Fan et al., 2019]. They find that automated metrics like ROUGE-L are not meaningful, which motivates our choice to use human comparisons as the main metric. Note that the aforementioned family of methods, which rely on inner product search (Equation 1), differ from WebGPT in that they formulate retrieval as a differentiable process. Fully differentiable retrieval has the advantage of fast optimization; two disadvantages are that it cannot deal with non-differential processes like using a search engine, and it is less interpretable.
WebGPT: Browser-assisted question-answering with human feedback
Like WebGPT, some other recent work defines document retrieval or web browsing as a reinforcement learning (RL) problem. Yuan et al. [2019] apply RL to reading comprehension benchmarks, where (as in WebGPT) the action space includes searching and scrolling through the provided source document. They suggest web-level QA (like WebGPT) as a direction for future work. Adolphs et al. [2021] set up an RL problem that involves performing a series of search queries for short-form question-answering. They train their system in two alternative ways: behavior cloning (BC) on synthetically-generated sequences and RL. Finally, there is another body of work that uses BC and RL to control web browsers, for automating other tasks besides question-answering [Shi et al., 2017, Gur et al., 2018.
WebGPT: Browser-assisted question-answering with human feedback
We have demonstrated a novel approach to long-form question-answering, in which a language model is fine-tuned to use a text-based web-browsing environment. This allows us to directly optimize answer quality using general methods such as imitation learning and reinforcement learning. To make human evaluation easier, answers must be supported by references collected during browsing. Using this approach, our best model outperforms humans on ELI5, but still struggles with out-of-distribution questions.
WebGPT: Browser-assisted question-answering with human feedback
Reiichiro Nakano, Jacob Hilton, Suchir Balaji and John Schulman jointly led the project, developed the codebase, ran all data collection and experiments, and wrote the paper.
WebGPT: Browser-assisted question-answering with human feedback
Jeff Wu, Long Ouyang, Xu Jiang and Karl Cobbe provided invaluable advice on a multitude of topics over the course of the project.
WebGPT: Browser-assisted question-answering with human feedback
Jeff Wu, Vineet Kosaraju, William Saunders and Xu Jiang made key contributions to the project codebase.
WebGPT: Browser-assisted question-answering with human feedback
Christina Kim, Christopher Hesse and Shantanu Jain built and supported infrastructure used for model training and inference.
WebGPT: Browser-assisted question-answering with human feedback
Tyna Eloundou and Gretchen Krueger conducted the analysis of bias and contributed to the paper.
WebGPT: Browser-assisted question-answering with human feedback
Kevin Button and Matthew Knight provided computer security support.
WebGPT: Browser-assisted question-answering with human feedback
Benjamin Chess provided computer networking support.
WebGPT: Browser-assisted question-answering with human feedback
We 
WebGPT: Browser-assisted question-answering with human feedback
Our text-based web-browsing environment is written mostly in Python with some JavaScript. For a high-level overview, see Section 2. Further details are as follows:
WebGPT: Browser-assisted question-answering with human feedback
• When a search is performed, we send the query to the Microsoft Bing Web Search API, and convert this to a simplified web page of results. • When a link to a new page is clicked, we call a Node.js script that fetches the HTML of the web page and simplifies it using Mozilla's Readability.js. • We remove any search results or links to reddit.com or quora.com, to prevent the model copying answers from those sites. • We take the simplified HTML and convert links to the special format 【<link ID> †<link text> †<destination domain>】, or 【<link ID> †<link text>】 if the destination and source domains are the same. Here, the link ID is the index of the link on the page, which is also used for the link-clicking command. We use special characters such as 【 and 】 because they are rare and encoded in the same few ways by the tokenizer, and if they appear in the page text then we replace them by similar alternatives. • We convert superscripts and subscripts to text using^and _, and convert images to the special format [Image: <alt text>], or [Image] if there is no alt text. • We convert the remaining HTML to text using html2text.
WebGPT: Browser-assisted question-answering with human feedback
• For text-based content types other than HTML, we use the raw text. For PDFs, we convert them to text using pdfminer.six. For all other content types, and for errors and timeouts, we use an error message. • We censor any pages that contain a 10-gram overlap with the question (or reference answer, if provided) to prevent the model from cheating, and use an error message instead. • We convert the title of the page to text using the format <page title> (<page domain>).
WebGPT: Browser-assisted question-answering with human feedback
For search results pages, we use Search results for: <query>. • When a find in page or quote action is performed, we compare the text from the command against the page text with any links stripped (i.e., including only the text from each link). We also ignore case. For quoting, we also ignore whitespace, and allow the abbreviated format <start text>━<end text> to save tokens. • During browsing, the state of the browser is converted to text as shown in Figure 1
WebGPT: Browser-assisted question-answering with human feedback
For the answering phase (the last step of the episode), we convert the question to text using the format <question>■, and follow this by each of the collected quotes in the format [<quote number>] <quote page title> (<quote page domain>) <double new line><quote extract>■.
WebGPT: Browser-assisted question-answering with human feedback
For our demonstration and comparison datasets, the vast majority of questions were taken from ELI5 [Fan et al., 2019], to which we applied the follow post-processing:
WebGPT: Browser-assisted question-answering with human feedback
1. We included URLs in full, rather than using special _URL_ tokens. 2. We filtered out questions with the title "[deleted by user]", and ignored the selftext "[deleted]" and "[removed]". (The "selftext" is the body of the post.) 3. We concatenated the title and any non-empty selftext, separated by a double new line. 4. We prepended "Explain: " to questions that were not phrased as actual questions (e.g., we used "Explain: gravity" rather than simply "gravity").
WebGPT: Browser-assisted question-answering with human feedback
The final step was performed because there is sometimes an implicit "Explain Like I'm Five" at the start of questions. We considered a question to be phrased as an actual question if it included either a question mark, or one of the following sequences of characters with a regex-word boundary at either end, case-insensitively: For diversity and experimentation, we also mixed in a small number of questions from the following datasets:
WebGPT: Browser-assisted question-answering with human feedback
• TriviaQA. This is a dataset of short-form questions taken from trivia websites [Joshi et al., 2017]. • AI2 Reasoning Challenge (ARC). This is a dataset of grade-school level, multiple-choice science questions [Bhakthavatsalam et al., 2021], which we converted to free-form questions using the format <question><new line>A. <option A><new line>.... This dataset is sub-divided into two difficulties, "Challenge" and "Easy". • Hand-written. We constructed this small dataset of miscellaneous questions written by people trying out the model. • ELI5 fact-check. We constructed this dataset using answers to questions from ELI5 given by an instruction-following model. 4 Each question has the following format: Fact-check each of the claims in the following answer. <double new line>Question: <ELI5 question><double new line>Answer: <model answer>
WebGPT: Browser-assisted question-answering with human feedback
The numbers of demonstrations and comparisons we collected for each of these datasets are given in Table 4. 
WebGPT: Browser-assisted question-answering with human feedback
To collect demonstrations and comparisons, we began by hiring freelance contractors from Upwork (https://www.upwork.com), and then worked with Surge AI (https://www.surgehq.ai) to scale up our data collection. In total, around 25% of our data was provided by 10 contractors from Upwork, and around 75% by 46 contractors from Surge AI. The top 5 contractors provided around 50% of the data.
WebGPT: Browser-assisted question-answering with human feedback
For both types of task, we provided contractors with a video and a detailed instruction document (linked below). Due to the challenging nature of the tasks, contractors were generally highly educated, usually with an undergraduate degree or higher. Contractors were compensated based on hours worked rather than number of tasks completed, and we conducted a survey to measure job satisfaction (see Appendix D).
WebGPT: Browser-assisted question-answering with human feedback
For data quality, we put prospective contractors through a paid trial period lasting a few hours, and manually checked their work. For comparisons, we also completed around 100 tasks ourselves for all labelers to complete, and monitored both researcher-labeler agreement rates and labeler-labeler agreement rates. Treating the agreement rate between a neutral label and a non-neutral label as 50%, we measured a final researcher-labeler agreement rate of 74%, and a labeler-labeler agreement rate of 73%.
WebGPT: Browser-assisted question-answering with human feedback
Demonstrations took an average of around 15 minutes each, and comparisons took an average of around 10 minutes each. Despite conventional wisdom that human labelling tasks should be quick and repeatable, we did not think it would be straightforward to decompose our tasks into significantly simpler ones, but we consider this to be a promising direction for further research.
WebGPT: Browser-assisted question-answering with human feedback
We designed the demonstration interface in such a way that, as a rule, the user is given the same information as the model, and has the same actions available. There were a couple of exceptions to this:
WebGPT: Browser-assisted question-answering with human feedback
1. Unlike humans, the model has no memory of previous steps. We therefore included a summary of past actions in the text given to the model. However, we felt that it was unnecessary to display this to humans. 2. The Scrolled <up, down> <2, 3> actions are useful for reducing the number of actions taken, but humans are used to scrolling one step at a time. We therefore made these actions unavailable to humans, and instead simply merged any repeated Scrolled <up, down> 1 actions that they made.
WebGPT: Browser-assisted question-answering with human feedback
The full instruction document we provided to contractors for demonstrations can be viewed here.
WebGPT: Browser-assisted question-answering with human feedback
To minimize label noise, it is important to make comparisons as unambiguous as possible. We therefore designed the following procedure for comparing two answers to a given question: Figure 9: Screenshot from the comparison interface, showing the annotation tool.
WebGPT: Browser-assisted question-answering with human feedback
For each of the comparison ratings, we used a 5-point Likert scale with the options "A much better", "A better", "Equally good", "B better" and "B much better".
WebGPT: Browser-assisted question-answering with human feedback
Importantly, we did not require contractors to perform independent research to judge the factual accuracy of answers, since this would have been difficult and subjective. Instead, we asked contractors to judge whether claims in the answer are supported, i.e., either backed up by a reliable reference, or common knowledge.
WebGPT: Browser-assisted question-answering with human feedback
For the final comparison rating, we encouraged contractors to use their best judgment, but to roughly consider the following criteria in descending order of priority:
WebGPT: Browser-assisted question-answering with human feedback
• Whether or not the answer contains unsupported information.
WebGPT: Browser-assisted question-answering with human feedback
• Whether or not the core question has been answered.
WebGPT: Browser-assisted question-answering with human feedback
• Whether or not there is additional helpful information, which does not necessarily need to answer the question directly. • How coherent the answer is, and whether or not there are any citation errors. • How much irrelevant information there is in the answer. (This can be higher priority in extreme cases.)
WebGPT: Browser-assisted question-answering with human feedback
The full instruction document we provided to contractors for comparisons can be viewed here.
WebGPT: Browser-assisted question-answering with human feedback
For most of the project, we made every part of this procedure required 10% of the time, and made every part except for the final comparison rating optional 90% of the time. Towards the end of the project, we removed the question flags from the first part since we felt that they were being overused, and made the comparison ratings for unsupported information and coherence required all of the time.
WebGPT: Browser-assisted question-answering with human feedback
Despite the complexity of this procedure, we only used the final comparison rating in training, even collapsing together the "much better" and "better" ratings. We experimented with predicting some of the other information as an auxiliary loss, but we were not able to significantly improve the validation accuracy of the reward model. Nevertheless, we consider this to be another promising direction for further research.
WebGPT: Browser-assisted question-answering with human feedback
It was valuable to gather feedback from our contractors, both to understand and improve their process, and to monitor job satisfaction. To this end, we sent them a questionnaire with the following questions:
WebGPT: Browser-assisted question-answering with human feedback
• Please say how much you agree with each of the statements. (Required 5-point Likert rating and optional comments) 1. It was clear from the instructions what I was supposed to do. 2. I found the task enjoyable and engaging. 3. I found the task repetitive. 4. I was paid fairly for doing the task. 5. Overall, I am glad that I did this task. • What would you change about the task to make it more engaging or enjoyable? (Encouraged) • Are there any other tools you could be given that would make it easier to complete the task to a consistently high standard? (Encouraged) • Did you come up with any shortcuts that you used to do the task more quickly, and if so, what were they? (Encouraged) • Do you have any other comments? (Optional)
WebGPT: Browser-assisted question-answering with human feedback
The "encouraged" questions were required questions but with instructions to put "N/A" if they really could not think of anything (this was rare).
WebGPT: Browser-assisted question-answering with human feedback
We surveyed all contractors who completed 32 or more tasks (thus we excluded people who dropped out after the trial period or shortly thereafter). We did this 3 times over the course of the project: once for demonstrations and twice for comparisons. The quantitative results from these surveys are given in Figure 10. The vast majority of respondents reported that they enjoyed the task, were paid fairly and were glad that they did the task overall. A significant minority of respondents also reported that they found the task repetitive.
WebGPT: Browser-assisted question-answering with human feedback
"It was clear from the instructions what I was supposed to do." "I found the task enjoyable and engaging." "I found the task repetitive."
WebGPT: Browser-assisted question-answering with human feedback
"I was paid fairly for doing the task."
WebGPT: Browser-assisted question-answering with human feedback
"Overall, I am glad that I did this task."
WebGPT: Browser-assisted question-answering with human feedback
Strongly disagree Disagree Neither agree nor disagree Agree Strongly agree Figure 10: Likert ratings aggregated over all 3 of our contractor surveys. All ratings are weighted equally, even when the same contractor provided ratings in multiple surveys. In total, there are 41 ratings for each question.
WebGPT: Browser-assisted question-answering with human feedback
Hyperparameters for all of our training methods are given in Tables 6 and 7. We mostly used the same hyperparameters for the different model sizes, with the caveat that we expressed the Adam step sizes as multiples of the pre-training Adam step sizes, which are given in Table 5.
WebGPT: Browser-assisted question-answering with human feedback
For each training method, we implemented some form of early stopping:
WebGPT: Browser-assisted question-answering with human feedback
1. For BC, we stopped after a certain number of epochs based on reward model score (which usually improves past the point of minimum validation loss). 2. For RM, we stopped after a certain number of epochs based on validation accuracy. 3. For RL, we stopped after a certain number of PPO iterations based on the reward model score for some KL budget. The KL here is measured from the BC model, and summed over the episode. For the 175B model, we compared a couple of different KL budgets using human evaluations, and for the 760M and 13B models, we chose KL budgets informed by the 175B evaluations.
WebGPT: Browser-assisted question-answering with human feedback
The points at which we early stopped are given in Table 8.
WebGPT: Browser-assisted question-answering with human feedback
We tuned hyperparameters using similar criteria to early stopping. We used human evaluations sparingly, since they were noisy and expensive, and put less effort into tuning hyperparameters for the 760M and 13B model sizes. As a rule, we found the most important hyperparameter to tune to be the Adam step size multiplier.
WebGPT: Browser-assisted question-answering with human feedback
For BC and RM, we used Polyak-Ruppert averaging [Polyak and Juditsky, 1992], taking an exponentially-weighted moving average (EMA) of the weights of the model as the final checkpoint. The "EMA decay" hyperparameter refers to the decay of this EMA per gradient step. For RL (but not rejection sampling), we did not use the EMA model for the 760M or 13B reward models, due to a bug.
WebGPT: Browser-assisted question-answering with human feedback
For RL, most PPO hyperparameters did not require tuning, but a few points are worth noting:
WebGPT: Browser-assisted question-answering with human feedback
• As discussed in Section 3 of the paper, the reward is the sum of the reward model score at the end of each episode and a KL penalty from the BC model at each token. Even though the reward is part of the environment, we treat the coefficient of this KL penalty as a hyperparameter, called the "KL reward coefficient". • We express hyperparameters such that each timestep corresponds to a single completion (rather than a single token), but we applied PPO clipping and the KL reward at the token level. We also trained token-level value function networks, allowing a token-level baseline to be used for advantage estimation, but we did not use token-level bootstrapping or discount rates. • We used separate policy and value function networks for simplicity, although we think that using shared networks is a promising direction for future research. • We used 1 epoch, since we were concerned more with compute efficiency than with sample efficiency. • Due to GPU memory constraints, we used 16 times as many minibatches per epoch as the default for PPO, but this was easily compensated for by reducing the Adam step size multiplier by a factor of 4. • We used the same number of parallel environments and timesteps per rollout as the default for PPO, even though it resulted in slow PPO iterations (lasting multiple hours). This is the easiest way to ensure that PPO performs enough clipping (around 1-2% of tokens). Compared to using fewer timesteps per rollout and fewer minibatches per epoch, we found the KL from the BC model to grow more slowly at the start of training, making training less sensitive to the KL reward coefficient until approaching convergence. This allowed us to replace tuning the KL reward coefficient with early stopping to some extent. • We did not use an entropy bonus, which is usually used for exploration. An entropy bonus is equivalent to a KL penalty from the uniform distribution, but the uniform distribution over tokens is somewhat arbitrary -in particular, it is not invariant to "splitting" a single token into two equally-likely indistinguishable tokens. Instead, the KL reward prevents entropy collapse in a more principled way. We still found it useful to measure entropy for monitoring purposes. • We happened to use a GAE discount rate of 1 rather than the usual default of 0.999, but we do not expect this to have made much difference, since episodes last for well under 1,000 timesteps. • As discussed in Section 3 of the paper, at the end of each episode we inserted additional answering-only episodes using the same references as the previous episode, which is what the "answer phases per browsing phases" hyperparameter refers to. • Since some actions (such as quotes and answers) require many more tokens than others, we modified the environment to "chunk" long completions into multiple actions, to improve rollout parallelizability. This is what the "maximum tokens per action" hyperparameter refers to. Note that it has a minor effect on GAE.    
WebGPT: Browser-assisted question-answering with human feedback
As discussed in Section 4, for comparing WebGPT's answers to the reference answers from the ELI5 dataset, we used a much more minimal set of instructions, for ecological validity. The full instructions consisted of the following text:
WebGPT: Browser-assisted question-answering with human feedback
Comparing answers (minimal version) In this task, you'll be provided with a question and a set of two answers. We'd like you to provide ratings comparing the two answers for the following categories:
WebGPT: Browser-assisted question-answering with human feedback
• Accuracy -which answer is more factually accurate?
WebGPT: Browser-assisted question-answering with human feedback
• Please use a search engine to fact-check claims in an answer that aren't obvious to you. Answers may have subtly incorrect or fabricated information, so be careful! • Coherence -which answer is easier to follow? • Usefulness overall -all things considered, which answer would be more helpful to the person who asked this question?
WebGPT: Browser-assisted question-answering with human feedback
• What should I do if there's a URL in the question or one of the answers?
WebGPT: Browser-assisted question-answering with human feedback
• Please don't click any URLs and interpret the questions and answers based on their remaining textual content. • What should I do if the question doesn't make any sense, or isn't a question?
WebGPT: Browser-assisted question-answering with human feedback
• Sometimes you'll see a statement instead of a question, which you should interpret as "Explain: . . . ".
WebGPT: Browser-assisted question-answering with human feedback
-E.g. a question titled "Magnets" should be interpreted as "Explain: magnets" or "How do magnets work?" • If the question is ambiguous but has a few reasonable interpretations, stick with the interpretation that you think is most likely. • If the question still doesn't make sense (e.g. if you'd need to click on a URL to understand it, or if it's entirely unclear what the question means), then click the "This question does not make sense" checkbox at the top and submit the task.
WebGPT: Browser-assisted question-answering with human feedback
-This should be rare, so use this sparingly. • What should I do if the answer to the question depends on when it was asked?
WebGPT: Browser-assisted question-answering with human feedback
• In this case, please be charitable when judging answers with respect to when the question was asked -an answer is considered accurate if it was accurate at any point within the last 10 years.
WebGPT: Browser-assisted question-answering with human feedback
-E.g. valid answers to the question "Who is the current U.S. president" are Barack Obama, Donald Trump, and Joe Biden. • What should I do if I only see one answer?
WebGPT: Browser-assisted question-answering with human feedback
• If you only see one answer, you'll be asked to provide absolute ratings for that answer (very bad, bad, neutral, good, or very good) instead of comparison ratings.
WebGPT: Browser-assisted question-answering with human feedback
-For the "usefulness overall" category, please calibrate your ratings such that "very bad" indicates an answer that is worse than not having an answer at all (e.g. due to being very misleading), "bad" indicates an answer that's about as helpful as not having an answer, and higher ratings indicate useful answers with varying degrees of quality.
WebGPT: Browser-assisted question-answering with human feedback
Although WebGPT was trained primarily to perform long-form question-answering, we were interested to see how well it would perform short-form question-answering. To this end, we evaluated WebGPT on TriviaQA [Joshi et al., 2017], a dataset of short-form questions from trivia websites. For this evaluation, we used the WebGPT 175B BC model with a sampling temperature of 0.8 and no rejection sampling.
WebGPT: Browser-assisted question-answering with human feedback
To address the mismatch between WebGPT's long-form answers and the short-form answers expected by TriviaQA, we fine-tuned GPT-3 175B to answer TriviaQA questions conditioned on the output of WebGPT. Since this is a simple extraction task, and out of concern for test-train overlap [Lewis et al., 2020b], we used only 256 questions for this fine-tuning (with a batch size of 32 and a learning rate of 1.5 × 10 −6 ). This was in addition to the 143 TriviaQA demonstrations on which the WebGPT model was trained. As an ablation, we also fine-tuned GPT-3 175B in the same way, but without the WebGPT output.
WebGPT: Browser-assisted question-answering with human feedback
Our results are shown in Table 9, along with those of the best existing model, UnitedQA [Cheng et al., 2021]. We report results on the TriviaQA development set splits defined in Lewis et al. [2020b]. We perform slightly better than UnitedQA-E on questions with no test-train overlap, and slightly worse on questions with test-train overlap. We hypothesize that this difference is the result of WebGPT being trained on far fewer TriviaQA questions. Note that we use far more compute than UnitedQA, and also use live access to the web rather than only the corpus provided by Joshi et al. [2017] (although we still censor trivia websites in the same way for this evaluation). On the other hand, WebGPT was trained primarily to perform long-form question-answering, and so the transfer to the short-form setting is notable.
WebGPT: Browser-assisted question-answering with human feedback
In this section we investigate the impact of question "stance" (whether the question implicitly supports or refutes some relevant belief) on the model's accuracy, and on its tendency to support or refute that belief in its answer. We also probe the model's bias towards "assuming" a certain cultural reference point with an example culturally dependent question ("What does a wedding look like?").
WebGPT: Browser-assisted question-answering with human feedback
We ran a small experiment to investigate the impact of question stance on the model's answers. Inspired by TruthfulQA [Lin et al., 2021], we chose 10 well-known conspiracy theories and 10 common misconceptions for this experiment. For each conspiracy theory or misconception, we wrote three questions, each taking one of three stances: one expressing skepticism around the implicit belief, one neutral about the implicit belief, and one affirming the implicit belief. This resulted in the 60 questions given in Table 10. We collected answers to these questions for the three compute-efficient WebGPT models (see Section 5.2), and used these answers to look for a couple of different effects.
WebGPT: Browser-assisted question-answering with human feedback
• Factual accuracy. First, we examined whether the stance of the question impacts the model's factual accuracy. To do this, we labelled each answer as accurate or inaccurate, by fact-checking any central or specific claims in the answer, and labeling the answer as inaccurate if a significant number (more than around 25%) of those claims could not be easily verified. Our results are given in Figure 11. We found suggestive evidence that, across model sizes, questions that affirm an implicit belief in a conspiracy or misconception tend to elicit inaccurate answers from the model more often than questions that are framed in a neutral or skeptical way. While our experiment had too small of a sample size for us to draw definitive conclusions, it demonstrates the model's potential to misinform users who have erroneous beliefs in ways that reinforce those beliefs. • Answer stance. Second, we studied whether the model mirrors the stance of the question in the content of its response. To do this, we labelled each answer on whether it explicitly refutes the implicit belief or explicitly affirms the implicit belief. Note that in some cases it is possible for an answer to affirm the belief in the conspiracy theory or misconception while remaining factually accurate, by including appropriate caveats. If an answer initially affirms the belief but then reverses its stance, saying for example "but this is a myth", then we consider it to have refuted the belief. Our results are given in Figure 12. We found that all the models tended to refute the implicit beliefs more often than they affirmed them, and that this effect increased with model size. However, we did not find any clear evidence that the stance of the question has any effect on this behavior.
WebGPT: Browser-assisted question-answering with human feedback
Given the small scale of this experiment, it would be informative to see further research on the effect of question stance on model answers. We remark that humans exhibit sensitivity to the framing of questions [Chong and Druckman, 2007]. In addition to this, it would be useful to study the effects of various other factors, such as the training data collection methodology, the relative degree of skepticism, neutrality or affirmation in the questions, the relative volumes of skeptical or affirming sources on the web, and whether the questions themselves appear in the training data or on the web.
WebGPT: Browser-assisted question-answering with human feedback
Rather than having a strong stance, some questions may reveal very little information about the user, but the model may nevertheless assume a certain cultural reference point. We refer to this as reference point bias. To probe this phenomenon, we conducted a simple case study, in which we analyzed 64 answers from the WebGPT 175B BC model to the following question: "What does a wedding look like?".
WebGPT: Browser-assisted question-answering with human feedback
In response to this question, the model tended to assume a Western, and often specifically an American, point-of-view. Out of the 64 answers, 20 included the word "America" or "American", and only 4 focused on a specific, named culture other than American: Vietnamese (1); Indian (1); and Croatian (2). While 8 of 64 responses noted that there is no standard wedding, all but one of these still also included at least one detail typical of a Western and often American wedding. And 2 of the these 8including the answer with the highest reward model score -noted that there is no standard or typical American wedding. The assumption of a Western and often American reference point in this case may be influenced by the data the model has seen during pre-training, by Internet search data, by the viewpoints represented by the contractors we worked with, and by our research team. When asked specifically "What does a Vietnamese wedding look like?", the model usually generates responses pertaining to Vietnamese weddings, but these come up rarely in response to a generic question. When in doubt, the model defaults to assuming a Western or American viewpoint in this case.
WebGPT: Browser-assisted question-answering with human feedback
Furthermore, we also noticed that the model often makes other assumptions that exclude or erase some identities in response to this question, for example by assuming that a couple consists of a male groom and female bride and assuming that a bride's father walks her down an aisle. While our experiment was focused on probing its bias towards a Western or American point of view, we encourage further interdisciplinary research in these and other areas of bias. 
WebGPT: Browser-assisted question-answering with human feedback
It is helpful to be able to predict human preference of answers produced using rejection sampling (best-of-n). To do this, we evaluate answers using a validation reward model (trained on a separate dataset split), to try to account for the original reward model being overoptimized. For large n, the naive Monte Carlo estimator of the expected validation reward model score requires many model samples to produce accurate estimates. Here we describe an alternative estimator, which produces accurate estimates more efficiently.
WebGPT: Browser-assisted question-answering with human feedback
Let Q be the distribution of questions, and given a question q, let A (q) be the distribution of answers produced by the model. Given a question q and an answer a (with references), let R train (a | q) be the original reward model score, and let R val (a | q) be the validation reward model score. Let n be the number of answers sampled when rejection sampling (i.e., the n in best-of-n).
WebGPT: Browser-assisted question-answering with human feedback
To predict the Elo score corresponding to human preference for a given question q, we estimate
WebGPT: Browser-assisted question-answering with human feedback
To predict the overall Elo score corresponding to human preference, we estimate
WebGPT: Browser-assisted question-answering with human feedback
As shown in Figure 5, this predicts human preference well for n ≤ 64, although we expect it to overestimate human preference for sufficiently large n, as the validation reward model will eventually become overoptimized.
WebGPT: Browser-assisted question-answering with human feedback
The simplest way to estimate R pred n (q) for a given question q is with a Monte Carlo estimator, by repeatedly sampling A 1 , A 2 , . . . , A n ∼ A (q). However, this is very wasteful, since it takes n answers to produce each estimate, and moreover, answers are not re-used for different values of n. Instead, we sample A 1 , A 2 , . . . , A N ∼ A (q) for some N ≥ n, and compute
WebGPT: Browser-assisted question-answering with human feedback
which is an unbiased estimator of R pred n (q) by linearity of expectation. This can be computed efficiently by sorting A 1 , A 2 , . . . , A N by original reward model score to obtain S 1 , S 2 , . . . S N with R train (S 1 | q) ≤ ⋅ ⋅ ⋅ ≤ R train (S N | q), and then computing To estimate E Q∼Q R pred n (Q) for n = 1, 2, . . . , n max , we sample a number of different questions Q ∼ Q, sample A 1 , A 2 , . . . , A N ∼ A (Q) for some N ≥ n max for each question Q, and for each n take the empirical average of the above estimator over the different questions.
WebGPT: Browser-assisted question-answering with human feedback
In Table 2, we gave an answer produced by our 175B best-of-64 model to a randomly-chosen question from the ELI5 test set: "Why did we decide that certain words were "bad" and shouldn't be used in social settings?". Here we give the full text of the references for that answer, along with an answer produced by one of our human demonstrators, and the reference answer from the ELI5 dataset. Further samples are available at https://openaipublic.blob.core.windows.net/ webgpt-answer-viewer/index.html. Table 11: Full text of the references found by our model for the answer given in Table 2. Table 12: An answer and references produced by one of our human demonstrators to the same question as the one in Table 2.
WebGPT: Browser-assisted question-answering with human feedback
Swear words, obscenities, and derogatory terms are some categories of words that society considers 'bad' and exempt from usage in social settings. In a more definitive approach, courts presume harm from speech in cases involving discrimination or sexual harassment [1]. While the original justification for these obscenity laws was predicated on an unfounded assumption that speech can deprave or corrupt children, and it is important to note that there is little (if any) social science data demonstrating that a word is by itself harmful [1], it is also pertinent to consider the origin of some derogatory words and the context of their usage to understand why they should be unacceptable in social settings. Examples include: -Ape/Monkey: These are considered offensive terms when used to describe a person of color because offensive comparisons of black people to apes date back hundreds of centuries, such as when scientists Josiah C. Nott and George R. Gliddon created the 1854 Types of Mankind (a leading scientific text on race in its time), and they compared black people not to other (white) people but to chimpanzees, gorillas, and orangutans. They are now, justifiably, considered extremely derogatory slang. [2] -Savage: When used as an adjective to describe acts of violence, this word is not considered offensive, but the use of 'savage' as a noun to describe people dates back to a time when Christopher Columbus was enslaving Native Americans and claiming their lands and work for his own. The word became a slur used by white Europeans to describe Native American people. The usage stuck around for hundreds of years, and it's still a word that many indigenous peoples around the world find offensive. [3] References [1] The Science of Swearing (www.psychologicalscience.org)
WebGPT: Browser-assisted question-answering with human feedback
Courts presume harm from speech in cases involving discrimination or sexual harassment. The original justification for our obscenity laws was predicated on an unfounded assumption that speech can deprave or corrupt children, but there is little (if any) social-science data demonstrating that a word in and of itself causes harm. A closely related problem is the manner in which harm has been defined -harm is most commonly framed in terms of standards and sensibilities such as religious values or sexual mores. Rarely are there attempts to quantify harm in terms of objectively measurable symptoms (e.g., sleep disorder, anxiety).
WebGPT: Browser-assisted question-answering with human feedback
[2] All Of These Words Are Offensive (But Only Sometimes) (www.dictionary.com) So, where's the problem?Ape and monkey are considered offensive terms when they're used to describe a person of color. It's what is known as dehumanizing language, "language that deprives a person of human qualities or attributes." Exactly when the words became slurs is unknown, but offensive comparisons of black people to apes date back hundreds of centuries. As recently as the late 1800s, for example, when scientists Josiah C. Nott and George R. Gliddon created the 1854 Types of Mankind (then the leading scientific text on race), they compared black people not to other (white) people but to chimpanzees, gorillas, and orangutans.
WebGPT: Browser-assisted question-answering with human feedback
When used in these contexts, monkey and ape are considered extremely derogatory slang.
WebGPT: Browser-assisted question-answering with human feedback
[3] All Of These Words Are Offensive (But Only Sometimes) (www.dictionary.com)
WebGPT: Browser-assisted question-answering with human feedback
The word savage has taken a circuitous path through the lexicon over the years, first showing up in English in the 1200s from Middle English. As an adjective, it's typically meant "fierce, ferocious, or cruel; uncivilized; barbarous." When referring to a savage lion ripping an antelope apart on the African Sahara, that's all well and good.
WebGPT: Browser-assisted question-answering with human feedback
But, the use of savage as a noun to describe human beings dates back to approximately the 1400s. At a time when Christopher Columbus was enslaving Native Americans and claiming their lands and work for his own, the word became a slur used by white Europeans to describe Native American people. The usage stuck around for hundreds of years, and it's still a word that many indigenous peoples around the world find offensive. Table 13: The reference answer from the ELI5 dataset for the question given in Table 2.
WebGPT: Browser-assisted question-answering with human feedback
There is an excellent podcast by Stuff You Should Know that is entirely about swear/curse words. They explain the history, psychology and science of curse and swear words, which are actually two different things.
WebGPT: Browser-assisted question-answering with human feedback
We are releasing a dataset of all comparisons that were marked as suitable for reward modeling by the end of the project, totalling 19,578 comparisons. It can be downloaded from https:// openaipublic.blob.core.windows.net/webgpt-answer-viewer/comparisons.jsonl.
WebGPT: Browser-assisted question-answering with human feedback
Each item in the dataset is a pair of records, each of which has the following fields:
WebGPT: Browser-assisted question-answering with human feedback
• Question: The text of the question, together with the name of the dataset from which it was taken and a unique ID. The question is the same for each record in the pair. • Quotes: The extracts found during browsing, together with the title of the page on which the extract was found, constructed from the HTML title and domain name of the page. • Answer: The final answer composed using the quotes.
WebGPT: Browser-assisted question-answering with human feedback
• Tokens: The prefix that would have been given to the model in the final step of the episode, and the completion given by the model or human. The prefix is made up of the question and the quotes, with some truncation, and the completion is simply the answer. Both are tokenized using the GPT-2 tokenizer. The concatenation of the prefix and completion is the input used for reward modeling. • Score: The strength of the preference for the answer as a number from −1 to 1. The two scores in each pair sum to zero, and an answer is preferred if and only if its score is positive. For reward modeling, we treat scores of 0 as soft 50% labels, and all other scores as hard labels (using only their sign).
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Open-domain question answering (QA) (Voorhees et al., 1999) involves a retriever for selecting relevant context from a large corpora of text (e.g. Wikipedia) and a machine reading comprehension (MRC) model for 'reasoning' on the retrieved context. A lot of effort has been put into designing sophisticated neural MRC architectures for reading short context (e.g. a single paragraph), with much success (Wang & Jiang, 2017;Seo et al., 2017;Xiong et al., 2017;Wang et al., 2018c;Yu et al., 2018, inter alia). However, the performance of such systems degrades significantly when combined with a retriever in open domain settings. For example, the exact match accuracy of DrQA , on the SQUAD dataset (Rajpurkar et al., 2016) degrades from 69.5% to 28.4% in open-domain settings. The primary reason for this degradation in performance is due to the retriever's failure to find the relevant paragraphs for the machine reading model (Htut et al., 2018).
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
We propose the following two desiderata for a general purpose open-domain QA system -(a) The retriever model should be fast, since it has to find the relevant context from a very large text corpora and give it to the more sophisticated and computationally expensive MRC model (b) Secondly, the retriever and reader models should be interactive, i.e. if the reader model is unable to find the answer from the initial retrieved context, the retriever should be able to learn to provide more relevant context to the reader. Open-domain QA systems such as R 3 (Wang et al., 2018a) and DS-QA (Lin et al., 2018) have sophisticated retriever models where the reader and retriever are jointly trained. However, their retriever computes question-dependent paragraph representation which is then encoded by running an expensive recurrent neural network over the tokens in the paragraph. Since the retriever has to rank a lot of paragraphs, this design does not scale to large corporas. One the other hand, the retriever model of QA systems such as DrQA  is based on a tf-idf retriever, but they lack trainable parameters and are consequently unable to recover from mistakes. This paper introduces an open domain architecture in which the retriever and reader iteratively interact with each other. Our model first pre-computes and caches representation of context (paragraph). These representations are independent of the query unlike recent architectures (Wang et al., 2018a;  Monroe county 11. RC model is able to find the correct answer after reading the second paragraph.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Question Paragraph Neural Reader Figure 1: Our framework unrolled for two steps. The initial query is encoded and the retriever sends the top-k paragraphs to the reader. The multi-step-reasoner component of our model takes in the internal state of the reader model and the previous query vector and does a gated update to produce a reformulated query. This new query vector is used by the retriever to re-rank the paragraphs and send different paragraphs to the reader. Thus the multi-step-reasoner facilitates iterative interaction between the retriever (search engine) and the reader (QA model) Lin et al., 2018) and hence can be computed and stored offline. Given an input question, the retriever performs fast inner product search to find the most relevant contexts. The highest ranked contexts are then passed to the neural MRC model. Our architecture is agnostic to the choice of the reader architecture and we show that multi-step-reasoning increases performance of two state-of-the-art MRC architectures -DrQA  and BiDAF (Seo et al., 2017).
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
It is possible that the answer might not exist in the initial retrieved paragraphs or that the model would need to combine information across multiple paragraphs (Wang et al., 2018b). We equip the reader with an additional gated recurrent unit (Cho et al., 2014) which takes in the state of the reader and the current query vector and generates a new query vector. This new query vector is then used by the retriever model to re-rank the context. This allows the model to read new paragraphs and combine evidence across multiple paragraphs. Since the retriever makes a 'hard selection' of paragraphs to send to the reader, we train the retriever and the reader jointly using reinforcement learning.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Our architecture draws inspiration from how students are instructed to take reading comprehension tests (Cunningham & Shablak, 1975;Bishop et al., 2006;Duggan & Payne, 2009). Given a document containing multiple paragraphs and a set of questions which can be answered from the document, (a) the student quickly skims the paragraphs, (b) then for each question, she finds the most relevant paragraphs that she thinks will answer the question. (c) She then carefully reads the chosen paragraph to answer the question (d) However, if the chosen paragraph does not answer the question, then given the question and the knowledge of what she has read till now, she decides which paragraph to read next.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Step (a) is akin to our model encoding and storing the question independent paragraph representations and step (b) corresponds to the inner product search to find the relevant context. The reading of the context by the sophisticated neural machine reader corresponds to step (c) and the last step corresponds to the iterative (multi-step) interaction between the retriever and the reader.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
To summarize, this paper makes the following contributions: (a) We introduce a new framework for open-domain QA in which the retriever and reader iteratively interact with each other via a novel multistep-reasoning component allowing it to retrieve and combine information from multiple paragraphs.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
(b) Our paragraph representations are independent of the query which makes our architecture highly scalable and we empirically demonstrate it by running large scale experiments over millions of paragraphs. (c) Lastly, our framework is agnostic to the architecture of the reader and we show improvements on two widely used neural reading comprehension models.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
The architecture of our model consists of three main components -(a) paragraph retriever -that computes a relevance score for each paragraph w.r.t a given query and ranks them according to the computed score. (b) reader -a more sophisticated neural machine reading model that receives few top-ranked paragraphs from the retriever and outputs a span of text as a possible answer to the query and (c) multi-step-reasoner -a gated recurrent unit that facilitates iterative interaction between the retriever and the reader.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Formally, the input to our model is a natural language question Q = q 1 , q 2 ,. . . , q n consisting of n tokens and a set of paragraphs P = {p 1 , p 2 , . . . p K }. Our model extracts a span of text a as the answer to the question from the paragraphs in P. Note that the set of paragraphs in P can be the paragraphs in a set of documents retrieved by a search engine or it could be all the paragraphs in a large text corpus such as Wikipedia. Next we describe each individual component of our model.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
The paragraph retriever computes a score for how likely a paragraph is to contain an answer to a given question. The paragraph representations are computed independent of the query and once computed, they are not updated. This allows us to cache the representations and store them offline. The relevance score of a paragraph is computed as a inner product between the paragraph and the query vectors. The paragraph and query representations are computed as follows.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Given a paragraph p = {p 1 , p 2 , . . . , p m } consisting of m tokens, a multi-layer recurrent neural network encodes each tokens in the paragraph -{p 1 , p 2 , . . . , p m } = RNN ({p 1 , p 2 , . . . , p m }) , where p j ∈ R 2d encodes useful contextual information around the j-th token. Specifically we choose to use a multilayer bidirectional long-short term memory network (LSTM) (Hochreiter & Schmidhuber, 1997) and take p j as the hidden units in the last layer of the RNN. We concatenate the representation computed by the forward and the backward LSTM. To compute a single paragraph vector p ∈ R 2d from all the token representations, we combine them using weights
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Here b j encodes the importance of each token and w ∈ R 2d , W s ∈ R 2d×2d are learned weights. The query q = {q 1 , q 2 , . . . , q n } is encoded by another network with the same architecture to obtain a query vector q ∈ R 2d . Next the relevance score of a paragraph w.r.t the query (score (p, q) ∈ R) is computed by a simple inner product -score (p, q) = p, q . The paragraph retriever then returns the top scoring k paragraphs to the reader.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Fast inner product search. Inner product can be efficiently computed on a GPU, however in our experiments with large corpus with over million paragraphs, (a) the paragraph vectors require more memory than available in a single commodity GPU (b) it is computationally wasteful to compute inner products with all paragraph vectors and we can do better by leveraging fast nearest neighbor (NN) search algorithms. Since the retriever has to find the k paragraphs with the highest inner products w.r.t query, our problem essentially reduces to maximum inner product search (MIPS). There exists data structures for fast NN search in metric spaces such as Cover Trees (Beygelzimer et al., 2006). But we cannot use them directly, since triangle equality does not hold in inner product space. Let u be an upper bound for the L2 norm for all paragraphs, i.e. u ≥ p , ∀p. Next, we modify the original paragraph and query vectors such that searching for the k-nearest neighbor w.r.t L2 distance with the modified vectors is equivalent to finding the k nearest (original) paragraph vectors in the inner-product space.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Define the augmented paragraph vectors asp i = [p i ; u 2 − p i 2 ] and augmented query vector as q = [q; 0], where [; ] denotes concatenation. Note, with this transformation, p i ,q = p i , q . Now,
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Many exact NN search algorithms can find k-NN in time (sublinear) logarithmic in number of paragraphs (Beygelzimer et al., 2006;Zaheer et al., 2019), after an one-time preprocessing. In our architecture, the preprocessing can be done because the set of all paragraphs is fixed for all the queries. We chose to use SGTree (Zaheer et al., 2019) to perform the NN/MIPS due to its fast construction time and competitive performance reducing the search to logarithmic time per query.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Note that our paragraph representations are independent of the given query and are never updated once they are trained. After training is completed, we cache the p ∈ R 2d vectors. This is unlike many recent work in open-domain QA. For example, in R 3 (Wang et al., 2018a), the retriever uses Match-LSTM model (Wang & Jiang, 2017) to compute question-matching representations for each token in the passage. The paragraph representations are then obtained by running a bi-directional RNN over these matched representation. Although powerful, this architecture design will not scale in open-domain settings where the retriever has to re-compute new representations for possibly millions of paragraphs for every new question. In contrast, once training is over, we cache the paragraph representation and use it for every query at test time.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Training -Following previous work (Htut et al., 2018;Lin et al., 2018;Wang et al., 2018a), we gather labels for paragraphs during training using distant supervision (Mintz et al., 2009). A paragraph that contains the exact ground truth answer string is labeled as an positive example. For a positive (negative) labeled paragraph, we maximize (minimize) the log(σ(score(p, q))). The number of layers of the bi-directional LSTM encoder is set to three and we use Adam (Kingma & Ba, 2014) for optimization. Once training is done, we pre-compute and cache the paragraph representation of each dataset in our experiments.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
The reader is a sophisticated neural machine reading comprehension (MRC) model that takes in the top few paragraphs sent by the retriever and outputs a span of answer text. Our model is agnostic to the exact architecture of the reader and we perform experiments to show the efficacy of our model on two state-of-the-art neural machine reading models -DrQA and BiDAF.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
MRC models designed for SQUAD (Rajpurkar et al., 2016), NewsQA (Trischler et al., 2016), etc operate on a single paragraph. However it has been shown that reading and aggregating evidence across multiple paragraphs is important when doing QA over larger evidence set (e.g. full Wikipedia document) (Swayamdipta et al., 2018;Clark & Gardner, 2018) and in open domain settings (Wang et al., 2018b). Most MRC models compute a start and end scores for each token in the paragraph that represents how likely a token is the start/end of an answer span. To gather evidence across multiple paragraphs sent by the retriever, we normalize the start/end scores across the paragraphs. Furthermore a text span can appear multiple times in a paragraph. To give importance to all answer spans in the text, our objective aggregates (sums) the log-probability of the score for each answer position. Let I(w, p) denote the token start positions where the answer span appears in the paragraph p and let w S be the starting word of the answer span. Our model maximizes the sum of the following objective for the start and end word of an answer spans as follows. (For brevity, we only show the objective for the starting word (w s ) of the span.) log ∑ j∈P ∑ k∈I(w s ,p j ) exp(score start (k, j))
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Here, P denotes the set of all top-ranked paragraphs by the retriever, n j denotes the number of tokens in paragraph j and score start (k, j) denotes the start score of the k-th token in the j-th paragraph.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Score aggregation during inference. During inference, following ; Seo et al. (2017), the score of a span that starts at token position i and ends at position j of paragraph p is given by the sum of the score start (i, p) and score end ( j, p). During inference, we score spans up to a pre-defined maximum length of 15. Further, we add the scores of spans across different paragraphs (even if they are retrieved at different steps), if they have the same surface form. That is, if the same span (e.g. "Barack Obama") occurs multiple times in several paragraphs, we sum the individual span scores. However, to ensure tractability, we only consider the top 10 scoring spans in each paragraph for aggregation. It should be noted that the changes we made to aggregate evidence over multiple paragraphs and mentions of spans needs no change to the original MRC architecture.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
A novel component of our open-domain architecture is the multi-step-reasoner which facilitates iterative interaction between the retriever and the machine reader. The multi-step-reasoner a module comprised of a gated recurrent unit (Cho et al., 2014) which takes in the current state of the reader and the current query vector and does a gated update to produce a reformulated query. The reformulated query is sent back to the retriever which uses it to re-rank the paragraphs in the corpus. Since the gated update of the multi-step-reasoner, conditions on the current state of the machine reader, this multi-step interaction provides a way for the search engine (retriever) and the QA model (reader) to communicate with each other. This can also be seen as an instance of two agents cooperating via communication to solve a task (Lazaridou et al., 2017;Lee et al., 2018;Cao et al., 2018).
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
More formally, let q t ∈ R 2d be the current query representation which was most recently used by the paragraph retriever to score the paragraphs in the corpus. The multi-step-reasoner also has access to the reader state which is computed from the hidden memory vectors of the reader. The reader state captures the current information that the reader has encoded after reading the paragraphs that was sent by the retriever. Next we show how the reader state is computed.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Span extractive machine reading architectures compute a hidden representation for each token in the paragraph. Our framework needs access to these hidden representations to compute the reader state.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Let m j ∈ R 2p be the hidden vector associated with the j-th token in the paragraph. Let L ∈ R 2p be the final query representation of the reader model. L is usually created by some pooling operation on the hidden representation of each question token. The reader state S ∈ R 2p is computed from each of the hidden vectors m j and L by first computing soft-attention weights between each paragraph token, followed by combining each m j with the soft attention weights.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Finally, the new reformulated query q t+1 ∈ R 2d for the paragraph retriever is calculated by the multi-step-reasoner module as follows -
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
In our architecture, we used a 3 layer GRU network, followed by a one layer feed forward network (FFN) with a ReLU non-linearity. The gated update ensures that relevant information from q t is preserved and new and useful information from the reader state S is added to the reformulated query.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
There exists no supervision for training the query reformulation of the multi-step-reasoner. Instead, we employ reinforcement learning (RL) and train it by how well the reader performs after reading the new set of paragraphs retrieved by the modified query. We define the problem as a deterministic finite horizon Partially Observed Markov decision process (POMDP). The components of POMDP are -
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
A state in the state space consists of the entire text corpora, the query, the answer, and k selected paragraphs. The reader is part of the environment and is fully described given the current state, i.e. selected paragraphs and the query.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Observations. The agent only observes a function of the current state. In particular, to the agent only the query vector and the memory of the reader model is shown, which are a function of the current state. Intuitively, this represents the information encoded by the machine reader model after reading the top k paragraphs sent by the retriever in current step.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Actions. The set of all paragraphs in the text corpora forms the action space. The retriever scores all paragraphs w.r.t the current query and selects the top k paragraphs to send to the reader model. We treat k as a hyper-parameter in our experiments.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Reward. At every step, the reward is measured by how well the answer extracted by the reader model matches to the ground-truth answer. We use the F 1 score (calculated by word overlap between prediction and ground-truth) as the reward at each step.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Transition. The environment evolves deterministically after reading the paragraphs sent by the retriever.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Our policy π is parameterized by the GRU and the FFN of the multi-step-reasoner. Let r t denote the reward (F 1 score) returned by the environment at time t. We directly optimize the parameters to maximize the expected reward given by -J(θ) = E π ∑ T t=1 r t . Here T denotes the number of steps of interactions between the retriever and the reader. We treat the reward at each step equally and do not apply any discounting. Motivated by the REINFORCE (Williams, 1992) algorithm, we compute the gradient of our objective as
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Here, p t is the top-ranked paragraph returned by the retriever at time t and the probability that the current policy assigns to p t is computed by normalizing the scores with a softmax. It is usual practice to add a variance reduction baseline (e.g. average of rewards in the minibatch) for stable training, but we found this significantly degrades the final performance. We think this is because, in QA, a minibatch consists of questions of varying difficulty and hence the rewards in a batch itself have high variance. This is similar to findings by  for closed domain-QA (e.g. SQUAD).
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Pretraining the multi-step-reasoner. We also find that pre-training the multi-step-reasoner before fine tuning with RL to be effective. We train to rank the similarity between the reformulated query vector and one of the distantly-supervised correct paragraph vectors higher than the score of a randomly sampled paragraph vector. Specifically, let q denote the query vector, p * , p denote the paragraph representation of paragraphs containing the correct answer string and a random sampled paragraph respectively. We follow the Bayesian Personalized Ranking approach of Rendle et al. (2009) and maximize log(σ(q p * − q p )). The paragraph representations p * , p are kept fixed and gradient only flows through q to the parameters of the multi-step-reasoner.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Our open-domain architecture is summarized above in Algorithm 1. Given a large text corpora (as a list of paragraphs), the corresponding paragraph embeddings (which can be trained by the procedure in ( § 2.1)) and hyper-parameters (T, k), our model M returns a text span a as answer. The multi-step interaction between the retriever and reader can be best understood by the for loop in line 2 of algorithm 1. The initial query q 0 is first used to rank all the paragraphs in the corpus (line 3), followed by which the top k paragraphs are sent to the reader (line 4). The reader returns the answer span (with an associated score for the span) and also its internal state (line 5). The GRU network then takes in the current query and the reader state to produce the updated query which is then passed to the retriever (line 6). The retriever uses this updated query to again re-rank the paragraphs and the entire process is repeated for T steps. At the end of T steps, the model returns the span with the highest score returned by the reader model. The reader is trained using supervised learning (using the correct spans as supervision) and the parameters of the GRU network are trained using reinforcement learning. During training, we first pre-train the reader model by setting the number of multi-step reasoning steps (T = 1). After the training converges, we freeze the parameters of the reader model and train the parameters of the GRU network using policy gradients. The output of the reader model is used to generate the reward which is used to train the policy network.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Input: Question text Q text , Text corpus (as a list of paragraphs) T , Paragraph embeddings P (list of paragraph embeddings for each paragraph in T ), Model M, Number of multi-steps T, number of top-ranked paragraphs k Output: Answer span a 1: q 0 ← − encode query(Q text ) # ( § 2.1) 2: for t in range(T) do 3:
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
{p 1 , p 2 , . . . p k } ← M.retriever.score paras(q t , P, k) # each p i denotes a paragraph id q t ← M.multi step reasoner.GRU(q t , S t ) # ( § 3); Query reformulation step 7: end for 8: return answer span a with highest score
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Open domain QA is a well-established task that dates back to few decades of reasearch. For example the BASEBALL system (Green Jr et al., 1961) aimed at answering open domain question albeit for a specific domain. Open-domain QA has been popularized by the Trec-8 task (Voorhees et al., 1999) and has recently gained significant traction due to the introduction of various datasets (Dunn et al., 2017;Dhingra et al., 2017;Joshi et al., 2017). In many open-domain systems , the retriever is a simple IR based system (e.g. tfidf retriever) with no trainable parameters and hence the retriever cannot overcome from its mistakes. Recent work such as R 3 (Wang et al., 2018a), DS-QA (Lin et al., 2018) use a trained retriever and have shown improvement in performance. However they form query dependent paragraph representation and such architectures will not scale to full open-domain settings where the retriever has to rank millions of paragraphs. and neither do they support iterative reasoning thereby failing to recover from any mistakes made by the ranker or where evidence needs to be aggregated across multiple paragraphs.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Query Reformulation by augmenting the original query with terms from the top-k retrieved document (Xu & Croft, 1996;Lavrenko & Croft, 2001) has proven to be very effective in information retrieval. Instead of using such automatic relevance feedback, Nogueira & Cho (2017) train a query reformulation model to maximize the recall of a IR system using RL and Pfeiffer et al. (2018) showed that query refinement is effective for IR in bio-medical domain. The main difference between this work and ours is that our model directly optimizes to improve the performance of a question answering system. However, as we show, we still see an improvement in the recall of our retriever ( § 5.1). Perhaps the most related to our work is Active Question Answering (AQA) (Buck et al., 2018), which use reformulation of the natural language query to improve the performance of a BiDAF reader model on SEARCHQA. The main difference between AQA is that we reformulate the query in vector space. We compare with AQA and show that our model achieves significantly better performance.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Iterative Reasoning has shown significant improvements in models using memory networks (Sukhbaatar et al., 2015;Miller et al., 2016) for question answering in text and knowledge bases (Das et al., 2017;Yang et al., 2017;Das et al., 2018). Our model can be viewed as a type of controller update step of memory network type of inference. Recently, iterative reasoning has shown to be effective in reading comprehension in single paragraph setting, where the model reads the same paragraph iteratively Liu et al., 2017). Our work can be seen as a strict generalization of these in a more realistic, open-domain setting.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Nearest Neighbor Search -Computing fast nearest neighbor (NN) search is a fundamental requirement in many applications. We used exact k-NN search using SGTree (Zaheer et al., 2019) which has been shown to perform better than other exact k-NN strategies such as Cover Tree (Beygelzimer et al., 2006), P-DCI (Li & Malik, 2017) and other approximate NN search techniques such as RP-Tree (Dasgupta & Sinha, 2013), HNSW (Malkov & Yashunin, 2018). In general, our proposed multi-step-reasoner framework is not coupled to any particular kind of k-NN technique.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Quasar -T  SearchQA  TRIVIAQA-unfiltered  SQUAD-open  EM  F1  EM  F1  EM  F1  EM  F1 GA (Dhingra et al., 2016) 26.4 26.4 ------BIDAF (Seo et al., 2017) 25.9 28.5 28.6 34.6 ----AQA (Buck et al., 2018) --40.5 47.4 ----R 3 (Wang et al., 2018a) 35  (Clark & Gardner, 2018) ----61.56 68.03 -- * Despite our best efforts, we could not reproduce the results of Ds-QA using their code and hyperparameter settings for Quasar-T. * * The results on the test set of TRIVIAQA-unfiltered were not reported in the original paper. Results obtained from authors via e-mail.  Table 3: Retrieval performance on QUASAR-T. The match-LSTM based retriever of R 3 is a more powerful model than our intial retrieval model. However, after few steps of multi-step-reasoner, the performance increases suggesting that re-ranking via query-reformulation is retrieving relevant evidence from the corpus. We report the P@k on the last step.    
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
We first investigate the performance of our paragraph retriever model ( §2.1). Our retriever is based on inner product between the query and pre-computed paragraph vectors. This architecture, although more scalable, is less powerful than the retrievers of R 3 and DS-QA which compute query-dependent passage representation via soft alignment (attention) before encoding with a bi-LSTM. Results in table 3 indeed show that retriever of R 3 has better P@k than our retriever. We also measure the performance of our retriever after few steps (#steps = 7) of interaction between the retriever and reader. As we can see from table 3, the query reformulation has resulted in better re-ranking and hence an overall improved performance of the retriever.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
To test for scalability in open-domain settings, we conduct a synthetic experiment. We plot the wall-clock time (in seconds) taken by the retriever to score and rank paragraphs with a query. To test for scalability, we increase the number of paragraphs ranging from 500 to 100 million and test on a single Titan-X GPU. For our baseline, we use the GPU implementation of the retriever of DS-QA (Lin et al., 2018). For our model, we test on three variants -(a) inner product on GPU, (b) inner-product on CPU and (c) inner-product using SG-Tree. Figure 2 shows the results. Our retriever model on GPU is faster than DS-QA, since the latter perform much more computation compared to just inner-product in our case. Moreover, DS-QA quickly uses up all the available memory and throws a memory error (OOM) by just 100K paragraphs. The inner product operation scales up to 1M paragraph before going OOM. SG-Tree shows very impressive performance even though it operates on CPU and consistently outperforms dot product operation on the CPU.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Next we investigate the improvements in QA performance due to multi-step-reasoner. We report the commonly used exact-match (EM) and F1 score on each dataset.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Performance on benchmark datasets.   Figure 3 shows the relative improvements our models achieve on QUASAR-T, SEARCHQA and TRIVIAQA-unfiltered with varying number of steps of interaction between the retriever and the reader. The key takeaway of this experiment is that multiple steps of interaction uniformly increases performance over base model (with no interaction). Different datasets have varying level of difficulties, however, the performance reaches its peak around 5 to 7 steps and does not provide much benefit on further increasing the number of steps.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Large scale experiment on TRIVIAQA-open. The benchmark datasets for open-domain QA have on an average hundred paragraphs for each question (Table 1). In real open-domain settings, the size of the evidence corpus might be much bigger. To test our model for the same, we created the TRIVIAQA-open setting, in which for each query we combined all the paragraphs in the development set, resulting in 1.6M paragraphs per query. We want to emphasize that the baseline models such as R 3 and DS-QA will not scale to this large setting. The baseline DrQA. model with no interaction between the retriever and reader get a score of EM = 37.45 and F1 = 42.16. The same model with 3 steps of interaction achieves a score of EM = 39.76 and F1 = 44.30. The key takeaways from this experiment are -(a) our framework can scale to settings containing millions of paragraphs, (b) iterative interaction still increase performance even in large scale settings, (c) the overall performance has significantly decreased (from 61 to 44.3 F1), suggesting that large context in open-domain QA is very challenging and should be an active area of research with significant scope for improvement.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
This section does further analysis of the results of the model. Specifically we are interested in analyzing if our method is able to gather more relevant evidence as we increase the number of steps of interaction between the retriever and the reader. We conduct this analysis on the development set of SEARCHQA (containing 13,393 queries) and to simplify analysis, we make the retriever choose the top scored single paragraph to send to the reader, at each step. The results are noted in table 4. As we can see from row 1 of table 4, on increasing steps of interaction, the quality of retrieved paragraphs Figure 4: Examples of how multi-step-reasoner iteratively modifies the query by reading context to find more relevant paragraphs. Figure (left) shows an example where the initial retrieved context did not have the answer but the context provided enough hint to get more relevant paragraph in the next step. In figure (right), both the retrieved paragraph have the answer string leading to a boost in the score of the answer span because of score aggregation of spans ( §2.2).  Table 4: Analysis of results on the dev. set of SEARCHQA as we increase the number of steps of interaction between the retriever and reader. The retriever at each step sends top-1 paragraph to the reader. A paragraph is correct if it contains the correct answer string.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
becomes better, i.e. even though the correct paragraph (containing the answer string) was not retrieved in the first step, the retriever is able to fetch relevant paragraphs later. It is also unsurprising to see, that when correct paragraphs are retrieved, the performance of the reader also increases. To check if the our policy was exploring and retrieving different paragraphs, we counted the mean number of unique paragraphs retrieved across all steps and found that it is high (around 2) when #steps of interaction is small as 3, suggesting that the policy chooses to explore initially. As the number of steps is increased, it increases at slower rate suggesting that if the policy has already found good paragraphs for the reader, it chooses to exploit them rather than choosing to explore. Figure 4 shows two instances where iterative interaction is helpful. In figure to the left, the retriever is initially unable to find a paragraph that directly answers the question, however it finds a paragraph which gives a different name for the disease allowing it to find a more relevant paragraph that directly answers the query. In the figure to the right, after the query reformulation, both the retrieved paragraphs have the correct answer string. Since we aggregate (sum) the scores of spans, this leads to an increase in the score of the right answer span (Demeter) to be the maximum.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
This paper introduces a new framework for open-domain question answering in which the retriever and the reader iteratively interact with each other. The resulting framework improved performance of machine reading over the base reader model uniformly across four open-domain QA datasets. We also show that our fast retrieval method can scale upto millions of paragraphs, much beyond the current capability of existing open-domain systems with a trained retriever module. Finally, we show that our method is agnostic to the architecture of the machine reading system provided we have access to the token level hidden representations of the reader. Our method brings an increase in performance to two popular and widely used neural machine reading architectures, Dr.QA and BiDAF.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Open-domain question answering (QA) (Voorhees et al., 1999) involves a retriever for selecting relevant context from a large corpora of text (e.g. Wikipedia) and a machine reading comprehension (MRC) model for 'reasoning' on the retrieved context. A lot of effort has been put into designing sophisticated neural MRC architectures for reading short context (e.g. a single paragraph), with much success (Wang & Jiang, 2017;Seo et al., 2017;Xiong et al., 2017;Wang et al., 2018c;Yu et al., 2018, inter alia). However, the performance of such systems degrades significantly when combined with a retriever in open domain settings. For example, the exact match accuracy of DrQA , on the SQUAD dataset (Rajpurkar et al., 2016) degrades from 69.5% to 28.4% in open-domain settings. The primary reason for this degradation in performance is due to the retriever's failure to find the relevant paragraphs for the machine reading model (Htut et al., 2018).
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
We propose the following two desiderata for a general purpose open-domain QA system -(a) The retriever model should be fast, since it has to find the relevant context from a very large text corpora and give it to the more sophisticated and computationally expensive MRC model (b) Secondly, the retriever and reader models should be interactive, i.e. if the reader model is unable to find the answer from the initial retrieved context, the retriever should be able to learn to provide more relevant context to the reader. Open-domain QA systems such as R 3 (Wang et al., 2018a) and DS-QA (Lin et al., 2018) have sophisticated retriever models where the reader and retriever are jointly trained. However, their retriever computes question-dependent paragraph representation which is then encoded by running an expensive recurrent neural network over the tokens in the paragraph. Since the retriever has to rank a lot of paragraphs, this design does not scale to large corporas. One the other hand, the retriever model of QA systems such as DrQA  is based on a tf-idf retriever, but they lack trainable parameters and are consequently unable to recover from mistakes. This paper introduces an open domain architecture in which the retriever and reader iteratively interact with each other. Our model first pre-computes and caches representation of context (paragraph). These representations are independent of the query unlike recent architectures (Wang et al., 2018a;  Monroe county 11. RC model is able to find the correct answer after reading the second paragraph.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Question Paragraph Neural Reader Figure 1: Our framework unrolled for two steps. The initial query is encoded and the retriever sends the top-k paragraphs to the reader. The multi-step-reasoner component of our model takes in the internal state of the reader model and the previous query vector and does a gated update to produce a reformulated query. This new query vector is used by the retriever to re-rank the paragraphs and send different paragraphs to the reader. Thus the multi-step-reasoner facilitates iterative interaction between the retriever (search engine) and the reader (QA model) Lin et al., 2018) and hence can be computed and stored offline. Given an input question, the retriever performs fast inner product search to find the most relevant contexts. The highest ranked contexts are then passed to the neural MRC model. Our architecture is agnostic to the choice of the reader architecture and we show that multi-step-reasoning increases performance of two state-of-the-art MRC architectures -DrQA  and BiDAF (Seo et al., 2017).
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
It is possible that the answer might not exist in the initial retrieved paragraphs or that the model would need to combine information across multiple paragraphs (Wang et al., 2018b). We equip the reader with an additional gated recurrent unit (Cho et al., 2014) which takes in the state of the reader and the current query vector and generates a new query vector. This new query vector is then used by the retriever model to re-rank the context. This allows the model to read new paragraphs and combine evidence across multiple paragraphs. Since the retriever makes a 'hard selection' of paragraphs to send to the reader, we train the retriever and the reader jointly using reinforcement learning.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Our architecture draws inspiration from how students are instructed to take reading comprehension tests (Cunningham & Shablak, 1975;Bishop et al., 2006;Duggan & Payne, 2009). Given a document containing multiple paragraphs and a set of questions which can be answered from the document, (a) the student quickly skims the paragraphs, (b) then for each question, she finds the most relevant paragraphs that she thinks will answer the question. (c) She then carefully reads the chosen paragraph to answer the question (d) However, if the chosen paragraph does not answer the question, then given the question and the knowledge of what she has read till now, she decides which paragraph to read next.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Given a paragraph p = {p 1 , p 2 , . . . , p m } consisting of m tokens, a multi-layer recurrent neural network encodes each tokens in the paragraph -{p 1 , p 2 , . . . , p m } = RNN ({p 1 , p 2 , . . . , p m }) , where p j ∈ R 2d encodes useful contextual information around the j-th token. Specifically we choose to use a multilayer bidirectional long-short term memory network (LSTM) (Hochreiter & Schmidhuber, 1997) and take p j as the hidden units in the last layer of the RNN. We concatenate the representation computed by the forward and the backward LSTM. To compute a single paragraph vector p ∈ R 2d from all the token representations, we combine them using weights
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Fast inner product search. Inner product can be efficiently computed on a GPU, however in our experiments with large corpus with over million paragraphs, (a) the paragraph vectors require more memory than available in a single commodity GPU (b) it is computationally wasteful to compute inner products with all paragraph vectors and we can do better by leveraging fast nearest neighbor (NN) search algorithms. Since the retriever has to find the k paragraphs with the highest inner products w.r.t query, our problem essentially reduces to maximum inner product search (MIPS). There exists data structures for fast NN search in metric spaces such as Cover Trees (Beygelzimer et al., 2006). But we cannot use them directly, since triangle equality does not hold in inner product space. Let u be an upper bound for the L2 norm for all paragraphs, i.e. u ≥ p , ∀p. Next, we modify the original paragraph and query vectors such that searching for the k-nearest neighbor w.r.t L2 distance with the modified vectors is equivalent to finding the k nearest (original) paragraph vectors in the inner-product space.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Many exact NN search algorithms can find k-NN in time (sublinear) logarithmic in number of paragraphs (Beygelzimer et al., 2006;Zaheer et al., 2019), after an one-time preprocessing. In our architecture, the preprocessing can be done because the set of all paragraphs is fixed for all the queries. We chose to use SGTree (Zaheer et al., 2019) to perform the NN/MIPS due to its fast construction time and competitive performance reducing the search to logarithmic time per query.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Note that our paragraph representations are independent of the given query and are never updated once they are trained. After training is completed, we cache the p ∈ R 2d vectors. This is unlike many recent work in open-domain QA. For example, in R 3 (Wang et al., 2018a), the retriever uses Match-LSTM model (Wang & Jiang, 2017) to compute question-matching representations for each token in the passage. The paragraph representations are then obtained by running a bi-directional RNN over these matched representation. Although powerful, this architecture design will not scale in open-domain settings where the retriever has to re-compute new representations for possibly millions of paragraphs for every new question. In contrast, once training is over, we cache the paragraph representation and use it for every query at test time.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Training -Following previous work (Htut et al., 2018;Lin et al., 2018;Wang et al., 2018a), we gather labels for paragraphs during training using distant supervision (Mintz et al., 2009). A paragraph that contains the exact ground truth answer string is labeled as an positive example. For a positive (negative) labeled paragraph, we maximize (minimize) the log(σ(score(p, q))). The number of layers of the bi-directional LSTM encoder is set to three and we use Adam (Kingma & Ba, 2014) for optimization. Once training is done, we pre-compute and cache the paragraph representation of each dataset in our experiments.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
MRC models designed for SQUAD (Rajpurkar et al., 2016), NewsQA (Trischler et al., 2016), etc operate on a single paragraph. However it has been shown that reading and aggregating evidence across multiple paragraphs is important when doing QA over larger evidence set (e.g. full Wikipedia document) (Swayamdipta et al., 2018;Clark & Gardner, 2018) and in open domain settings (Wang et al., 2018b). Most MRC models compute a start and end scores for each token in the paragraph that represents how likely a token is the start/end of an answer span. To gather evidence across multiple paragraphs sent by the retriever, we normalize the start/end scores across the paragraphs. Furthermore a text span can appear multiple times in a paragraph. To give importance to all answer spans in the text, our objective aggregates (sums) the log-probability of the score for each answer position. Let I(w, p) denote the token start positions where the answer span appears in the paragraph p and let w S be the starting word of the answer span. Our model maximizes the sum of the following objective for the start and end word of an answer spans as follows. (For brevity, we only show the objective for the starting word (w s ) of the span.) log ∑ j∈P ∑ k∈I(w s ,p j ) exp(score start (k, j))
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
A novel component of our open-domain architecture is the multi-step-reasoner which facilitates iterative interaction between the retriever and the machine reader. The multi-step-reasoner a module comprised of a gated recurrent unit (Cho et al., 2014) which takes in the current state of the reader and the current query vector and does a gated update to produce a reformulated query. The reformulated query is sent back to the retriever which uses it to re-rank the paragraphs in the corpus. Since the gated update of the multi-step-reasoner, conditions on the current state of the machine reader, this multi-step interaction provides a way for the search engine (retriever) and the QA model (reader) to communicate with each other. This can also be seen as an instance of two agents cooperating via communication to solve a task (Lazaridou et al., 2017;Lee et al., 2018;Cao et al., 2018).
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Pretraining the multi-step-reasoner. We also find that pre-training the multi-step-reasoner before fine tuning with RL to be effective. We train to rank the similarity between the reformulated query vector and one of the distantly-supervised correct paragraph vectors higher than the score of a randomly sampled paragraph vector. Specifically, let q denote the query vector, p * , p denote the paragraph representation of paragraphs containing the correct answer string and a random sampled paragraph respectively. We follow the Bayesian Personalized Ranking approach of Rendle et al. (2009) and maximize log(σ(q p * − q p )). The paragraph representations p * , p are kept fixed and gradient only flows through q to the parameters of the multi-step-reasoner.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Open domain QA is a well-established task that dates back to few decades of reasearch. For example the BASEBALL system (Green Jr et al., 1961) aimed at answering open domain question albeit for a specific domain. Open-domain QA has been popularized by the Trec-8 task (Voorhees et al., 1999) and has recently gained significant traction due to the introduction of various datasets (Dunn et al., 2017;Dhingra et al., 2017;Joshi et al., 2017). In many open-domain systems , the retriever is a simple IR based system (e.g. tfidf retriever) with no trainable parameters and hence the retriever cannot overcome from its mistakes. Recent work such as R 3 (Wang et al., 2018a), DS-QA (Lin et al., 2018) use a trained retriever and have shown improvement in performance. However they form query dependent paragraph representation and such architectures will not scale to full open-domain settings where the retriever has to rank millions of paragraphs. and neither do they support iterative reasoning thereby failing to recover from any mistakes made by the ranker or where evidence needs to be aggregated across multiple paragraphs.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Query Reformulation by augmenting the original query with terms from the top-k retrieved document (Xu & Croft, 1996;Lavrenko & Croft, 2001) has proven to be very effective in information retrieval. Instead of using such automatic relevance feedback, Nogueira & Cho (2017) train a query reformulation model to maximize the recall of a IR system using RL and Pfeiffer et al. (2018) showed that query refinement is effective for IR in bio-medical domain. The main difference between this work and ours is that our model directly optimizes to improve the performance of a question answering system. However, as we show, we still see an improvement in the recall of our retriever ( § 5.1). Perhaps the most related to our work is Active Question Answering (AQA) (Buck et al., 2018), which use reformulation of the natural language query to improve the performance of a BiDAF reader model on SEARCHQA. The main difference between AQA is that we reformulate the query in vector space. We compare with AQA and show that our model achieves significantly better performance.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Iterative Reasoning has shown significant improvements in models using memory networks (Sukhbaatar et al., 2015;Miller et al., 2016) for question answering in text and knowledge bases (Das et al., 2017;Yang et al., 2017;Das et al., 2018). Our model can be viewed as a type of controller update step of memory network type of inference. Recently, iterative reasoning has shown to be effective in reading comprehension in single paragraph setting, where the model reads the same paragraph iteratively Liu et al., 2017). Our work can be seen as a strict generalization of these in a more realistic, open-domain setting.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Nearest Neighbor Search -Computing fast nearest neighbor (NN) search is a fundamental requirement in many applications. We used exact k-NN search using SGTree (Zaheer et al., 2019) which has been shown to perform better than other exact k-NN strategies such as Cover Tree (Beygelzimer et al., 2006), P-DCI (Li & Malik, 2017) and other approximate NN search techniques such as RP-Tree (Dasgupta & Sinha, 2013), HNSW (Malkov & Yashunin, 2018). In general, our proposed multi-step-reasoner framework is not coupled to any particular kind of k-NN technique.
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
Quasar -T  SearchQA  TRIVIAQA-unfiltered  SQUAD-open  EM  F1  EM  F1  EM  F1  EM  F1 GA (Dhingra et al., 2016) 26.4 26.4 ------BIDAF (Seo et al., 2017) 25.9 28.5 28.6 34.6 ----AQA (Buck et al., 2018) --40.5 47.4 ----R 3 (Wang et al., 2018a) 35  (Clark & Gardner, 2018) ----61.56 68.03 -- * Despite our best efforts, we could not reproduce the results of Ds-QA using their code and hyperparameter settings for Quasar-T. * * The results on the test set of TRIVIAQA-unfiltered were not reported in the original paper. Results obtained from authors via e-mail.  Table 3: Retrieval performance on QUASAR-T. The match-LSTM based retriever of R 3 is a more powerful model than our intial retrieval model. However, after few steps of multi-step-reasoner, the performance increases suggesting that re-ranking via query-reformulation is retrieving relevant evidence from the corpus. We report the P@k on the last step.    
Multi-step Retriever-Reader Interaction for Scalable Open-domain Question Answering
To test for scalability in open-domain settings, we conduct a synthetic experiment. We plot the wall-clock time (in seconds) taken by the retriever to score and rank paragraphs with a query. To test for scalability, we increase the number of paragraphs ranging from 500 to 100 million and test on a single Titan-X GPU. For our baseline, we use the GPU implementation of the retriever of DS-QA (Lin et al., 2018). For our model, we test on three variants -(a) inner product on GPU, (b) inner-product on CPU and (c) inner-product using SG-Tree. Figure 2 shows the results. Our retriever model on GPU is faster than DS-QA, since the latter perform much more computation compared to just inner-product in our case. Moreover, DS-QA quickly uses up all the available memory and throws a memory error (OOM) by just 100K paragraphs. The inner product operation scales up to 1M paragraph before going OOM. SG-Tree shows very impressive performance even though it operates on CPU and consistently outperforms dot product operation on the CPU.
WebGPT: Browser-assisted question-answering with human feedback
Like WebGPT, some other recent work defines document retrieval or web browsing as a reinforcement learning (RL) problem. Yuan et al. [2019] apply RL to reading comprehension benchmarks, where (as in WebGPT) the action space includes searching and scrolling through the provided source document. They suggest web-level QA (like WebGPT) as a direction for future work. Adolphs et al. [2021] set up an RL problem that involves performing a series of search queries for short-form question-answering. They train their system in two alternative ways: behavior cloning (BC) on synthetically-generated sequences and RL. Finally, there is another body of work that uses BC and RL to control web browsers, for automating other tasks besides question-answering [Shi et al., 2017, Gur et al., 2018.
WebGPT: Browser-assisted question-answering with human feedback
For BC and RM, we used Polyak-Ruppert averaging [Polyak and Juditsky, 1992], taking an exponentially-weighted moving average (EMA) of the weights of the model as the final checkpoint. The "EMA decay" hyperparameter refers to the decay of this EMA per gradient step. For RL (but not rejection sampling), we did not use the EMA model for the 760M or 13B reward models, due to a bug.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Open domain question answering is a challenging task where the answer to a given question needs to be extracted from a large pool of documents. The prevailing approach (Chen et al., 2017) tackles the problem in two stages. Given a question, a retriever first produces a list of k candidate documents, and a reader then extracts the answer from this set. Until recently, retrieval models were dependent on traditional term-based information retrieval (IR) methods, which fail to capture the semantics of the question beyond lexical matching and remain a major performance bottleneck for the task. Recent work on dense retrieval methods instead uses pretrained encoders to cast the question and documents into dense representations in a vector space and relies on fast maximum inner-product search (MIPS) to complete the retrieval. These approaches Guu et al., 2020;Karpukhin et al., 2020) have demonstrated significant retrieval improvements over traditional IR baselines.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
However, such methods remain limited to simple questions, where the answer to the question is explicit in a single piece of text evidence. In contrast, complex questions typically involve aggregating information from multiple documents, requiring logical reasoning or sequential (multihop) processing in order to infer the answer (see Figure 1 for an example). Since the process for answering such questions might be sequential in nature, single-shot approaches to retrieval are insufficient. Instead, iterative methods are needed to recursively retrieve new information at each step, conditioned on the information already at hand. Multi-hop question answering is an important task and an active research area (Talmor & Berant, 2018;Yang et al., 2018).
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
The main problem in answering multi-hop open-domain questions is that the search space grows exponentially with each retrieval hop. Most recent work tackles this issue by constructing a document graph utilizing either entity linking or existing hyperlink structure in the underlying Wikipedia corpus (Nie et al., 2019;Asai et al., 2020). The problem then becomes finding the best path in this graph, where the search space is bounded by the number of hyperlinks in each passage. However, such methods may not generalize to new domains, where entity linking might perform poorly, or where hyperlinks might not be as abundant as in Wikipedia. Moreover, efficiency remains a challenge despite using these data-dependent pruning heuristics, with the best model (Asai et al., 2020) needing hundreds of calls to large pretrained models to produce a single answer.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
In contrast, we propose to employ dense retrieval to the multi-hop setting with a simple recursive framework. Our method iteratively encodes the question and previously retrieved documents as a query vector and retrieves the next relevant documents using efficient MIPS methods. With highquality, dense representations derived from strong pretrained encoders, our work first demonstrates that the sequence of documents that provide sufficient information to answer the multi-hop question can be accurately discovered from unstructured text, without the help of corpus-specific hyperlinks. When evaluated on two multi-hop benchmarks, HotpotQA (Yang et al., 2018) and a multi-evidence  subset of FEVER (Thorne et al., 2018), our approach improves greatly over the traditional linkingbased retrieval methods (e.g., 28% relative gain in Recall@20 for HotpotQA). Importantly, the better retrieval results also lead to new state-of-the-art downstream results on both datasets, while being 10x faster at inference time.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Here ·, · is the inner product between the query and passage vectors. h(·) and and g(·) are passage and query encoders that produce the dense representations. In order to reformulate the query representation to account for previous retrieval results at time step t, we simply concatenate the question and the retrieved passages as the inputs to g(·). Note that our formulation for each retrieval step is similar to existing single-hop dense retrieval methods Guu et al., 2020;Karpukhin et al., 2020) except that we add the query reformulation process conditioned on previous retrieval results. Instead of using a bi-encoder architecture with separately parameterized encoders for questions and passages, we use a shared RoBERTa-base  encoder for both h(·) and g(·). In §3.1.3, we show that this simple modification yields considerable improvements.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
The retriever model is trained as in Karpukhin et al. (2020), where each input query (which at each step consists of a question and previously retrieved passages) is paired with a positive passage and m negative passages to approximate the softmax over all passages. The positive passage is the gold annotated evidence at step t. Negative passages are a combination of passages in the current batch which correspond to other questions (in-batch), and hard negatives which are false adversarial passages. In our experiments, we obtain hard negatives from TF-IDF retrieved passages and their linked pages in Wikipedia. We note that using hyperlinked pages as additional negatives is neither necessary nor critical for our approach. In fact we observe only a very small degradation in performance if we remove them from training ( §3.1.3).
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
In addition to in-batch negatives, we use a memory bank (M) mechanism (Wu et al., 2018) to further increase the number of negative examples for each question. The memory bank stores a large number of dense passage vectors. As we block the gradient back-propagation in the memory bank, its size (|M| batch size) is less restricted by the GPU memory size. Specifically, after training to convergence with the shared encoder, we freeze a copy of the encoder as the new passage encoder and collect a bank of passage representations across multiple batches to serve as the set of negative passages. This simple extension results in further improvement in retrieval. ( §3.1.3).
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Datasets Our experiments focus on two datasets: HotpotQA and Multi-evidence FEVER. Hot-potQA (Yang et al., 2018) includes 113k multi-hop questions. Unlike other multi-hop QA datasets Talmor & Berant, 2018;Welbl et al., 2018), where the information sources of the answers are knowledge bases, HotpotQA uses documents in Wikipedia. Thus, its questions are not restricted by the fixed KB schema and can cover more diverse topics. Each question in HotpotQA is also provided with ground truth support passages, which enables us to evaluate the intermediate retrieval performance. Multi-evidence FEVER includes 20k claims from the FEVER (Thorne et al., 2018) fact verification dataset, where the claims can only be verified using multiple documents. We use this dataset to validate the general applicability of our method.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
All the experiments are conducted on a machine with 8 32GB V100 GPUs. Our code is based on Huggingface Transformers (Wolf et al., 2019). Our best retrieval results are predicted using the exact inner product search index (IndexFlatIP) in FAISS (Johnson et al., 2017). Both datasets assume 2 hops, so we fix n = 2 for all experiments. Since HotpotQA does not provide the order of the passage sequences, as a heuristic, we consider the passage that includes the answer span as the final passage. 1 In §3.1.3, we show that the order of the passages is important for effective retriever training. The hyperparameters can be found in Appendix B.1.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
We first compare MDR with several efficient retrieval methods that can directly find the top-k passage sequences from a large corpus, including TF-IDF, TF-IDF + Linked, DrKIT and Entity Linking. TF-IDF is the standard term-matching baseline, while TF-IDF + Linked is a straightforward extension that also extracts the hyperlinked passages from TF-IDF passages, and then reranks both TF-IDF and hyperlinked passages with BM25 2 scores. DrKIT (Dhingra et al., 2020) is a recently proposed dense retrieval approach, which builds a entity-level (mentions of entities) dense index for retrieval. It relies on hyperlinks to extract entity mentions and prunes the search space with a binary mask that restricts the next hop to using hyperlinked entities. On FEVER, we additionally consider an entity linking baseline (Hanselowski et al., 2018) that is commonly used in existing fact verification pipelines. This baseline first uses a constituency parser to extract potential entity mentions in the fact claim and then uses the MediaWiki API to search documents with titles that match the mentions. Table 1 shows the performance of different retrieval methods. On HotpotQA the metric is recall at the top k paragraphs 3 , while on FEVER the metrics are precision, recall and F 1 in order to be consistent with previous results. On both datasets, MDR substantially outperforms all baselines.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Reranking documents returned by efficient retrieval methods with a more sophisticated model is a common strategy for improving retrieval quality. For instance, state-of-the-art multi-hop QA systems usually augment traditional IR techniques with large pretrained language models to select a more compact but precise passage set. On HotpotQA, we test the effectiveness of MDR after a simple BERT-based reranking: each of the top k passage sequences from MDR is first prepended with the original question and then fed into a BERT-like encoder that predicts relevant scores. We train this reranking model with a binary cross-entropy loss, with the target being whether the passage sequence cover both groundtruth passages. We empirically compare our approach with two other existing reranking-based retrieval methods: Semantic Retrieval (Nie et al., 2019) uses BERT at both passage-level and sentence-level to select context from the initial TF-IDF and hyperlinked passages; Graph Recurrent Retriever (Asai et al., 2020) learns to recursively select the best passage sequence on top of a hyperlinked passage graph, where each passage node is encoded with BERT.   Table 2 shows the reranking results. Following Asai et al. (2020), we use Answer Recall and Support Passage Exact Match (SP EM) 4 as the evaluation metrics. Even without reranking, MDR is already better than Semantic Retrieval, which requires around 50 BERT encoding (where each encoding involves cross-attention over a concatenated question-passage pair). After we rerank the top-100 sequences from the dense retriever, our passage recall is better than the state-of-the-art Graph Recurrent Retriever, which uses BERT to process more than 500 passages. We do not compare the reranked results on FEVER, as most FEVER systems directly use BERT encoder to select the top evidence sentences from the retrieved documents, instead of the reranking the documents.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
For the case of bridge questions, we manually inspect 50 randomly sampled erroneous examples after reranking. We find that in half of these cases, our retrieval model predicts an alternative passage sequence that is also valid (see Appendix A.1 for examples). This gives an estimated top-1 passage sequence accuracy of about 90%. Other remaining errors are due to the dense method's inability to capture the exact n-gram match between the question and passages. This is a known issue Karpukhin et al., 2020) of dense retrieval methods when dealing with questions that have high lexical overlap with the passages. To this end, a hybrid multi-hop retrieval method with both term and dense index might be used to further improve the performance on bridge questions.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Question Decomposition for Retrieval As multi-hop questions have more complex structures than simple questions, recent studies (Min et al., 2019;Perez et al., 2020) propose to use explicit question decomposition to simplify the problem. Wolfson et al. (2020) shows that with TF-IDF, using decomposed questions improves the retrieval results. We investigate whether the conclusion still holds with stronger dense retrieval methods. We use the human-annotated question decomposition from the QDMR dataset (Wolfson et al., 2020) for analysis. For a question like Q:Mick Carter is the landlord of a public house located at what address?, QDMR provides two subquestions, SubQ1: What is the public house that Mick Carter is the landlord of? and SubQ2: What is the address that #1 is located at?. We sample 100 bridge questions and replace #1 in SubQ2 with the correct answer (The Queen Victoria) to SubQ1. Note that this gives advantages to the decomposed method as we ignore any intermediate errors. We estimate the performance of potential decomposed methods with the state-of-the-art single-hop dense retrieval model (Karpukhin et al., 2020). As shown in Table 4, we did not observe any strong improvements from explicit question decomposition, which is contrary to the findings by Wolfson et al. (2020) when using term-based IR methods. Moreover, as shown in the third row of the table, when the 1st hop of the decomposed retrieval (i.e., SubQ1) is replaced with the original question, no performance degradation is observed. This suggests that strong pretrained encoders can effectively learn to select necessary information from the multi-hop question at each retrieval step.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
We evaluate how the better retrieval results of MDR improve multi-hop question answering in this section. As our retriever system is agnostic to downstream models, we test two categories of answer prediction architectures: the extractive span prediction models based on pretrained masked language models, such as BERT  and ELECTRA (Clark et al., 2020), and the retrieval-augmented generative reader models (Lewis et al., 2020b;Izacard & Grave, 2020), which are based on pretrained sequence-to-sequence (seq2seq) models such as BART (Lewis et al., 2020a) and T5 (Raffel et al., 2019). Note that compared to more complicated graph reasoning models (Fang et al., 2019;Zhao et al., 2020), these two classes of models do not rely on hyperlinks and can be applied to any text.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Extractive reader models learn to predict an answer span from the concatenation of the question and passage sequence ([q, p 1 , ..., p n ]). On top of the token representations produced by pretrained models, we add two prediction heads to predict the start and end position of the answer span. 5 To predict the supporting sentences, we add another prediction head and predict a binary label at each sentence start. For simplicity, the same encoder is also responsible for reranking the top k passage sequences. The reranking detail has been discussed in §3.1.2. Our best reader model is based on ELECTRA (Clark et al., 2020), which has achieved the best single-model performance on the standard SQuAD (Rajpurkar et al., 2018) benchmark. Additionally, we also report the performance of BERT-large with whole word masking (BERT-wwm) to fairly compare with Asai et al. (2020).
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
More details about these two classes of reader models are described in Appendix B.2. Comparison with Existing Systems Table 5 compares the HotpotQA test performance of our best ELECTRA reader with recently published systems, using the numbers from the official leaderboard, which measure answer and supporting sentence exact match (EM)/F1 and joint EM/F1. Among these methods, only GoldEn Retriever (Qi et al., 2019) does not exploit hyperlinks. In particular, Graph Recurrent Retriever trains a graph traversal model for chain retrieval; TransformerXH (Zhao et al., 2020) and HGN (Fang et al., 2019) explicitly encode the hyperlink graph structure within their answer prediction models. In fact, this particular inductive bias provides a perhaps unreasonably strong advantage in the specific context of HotpotQA, which by construction guarantees groundtruth passage sequences to follow hyperlinks. Despite not using such prior knowledge, our model outperforms all previous systems by large margins, especially on supporting fact prediction, which benefits more directly from better retrieval.  Table 6. 6 First, we see that the BERT-wwm reader is 1-2% worse than the ELECTRA reader when using enough passages. However, it still outperforms the results in (Asai et al., 2020) which also uses BERT-wwm for answer prediction. While RAG and FiD have shown strong improvements over extractive models on single-hop datasets such as NaturalQuestions (Kwiatkowski et al., 2019), they do not show an advantage in the multi-hop case. Despite having twice as many parameters as ELECTRA, FiD fails to outperform it using the same amount of context (top 50). In contrast, on NaturalQuestions, FiD is 4 points better than a similar extractive reader when using the top 100 passages in both. 7 We hypothesize that the improved performance on single-hop questions is due to the ability of larger pretrained models to more effectively memorize single-hop knowledge about real-world entities. 8 Compared to multi-hop questions that involve multiple relations and missing entities, simple questions usually only ask about a certain property of an entity. It is likely that such simple entity-centric information is explicitly mentioned by a single text piece in the pretraining corpus, while the evidence for multihop questions is typically dispersed, making the complete reasoning chain nontrivial to memorize. More analysis on RAG can be found in Appendix A.3. Inference Efficiency To compare with existing multi-hop QA systems in terms of efficiency, we follow Dhingra et al. (2020) and measure the inference time with 16 CPU cores and batch size 1. We implement our system with a fast approximate nearest neighbor search method, i.e., HNSW (Malkov & Yashunin, 2018), which achieves nearly the same performance as exact search. With an in-memory index, we observe that the retrieval time is negligible compared to the forward pass of large pretrained models.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Similarly, for systems that use term-based indices, the BERT calls for passage reranking cause the main efficiency bottleneck. Thus, for systems that do not release the end-to-end code, we estimate the running time based on the number of BERT cross-attention forward passes (the same estimation strategy used by Dhingra et al. (2020)), and ignore the overhead caused by additional processing such as TF-IDF or linking graph construction. As shown in Figure 3, our method is about 10 times faster than current state-of-the-art systems while achieving a similar level of performance. Compared to two efficient systems (DrKIT and GoldEn), we achieve over 10 points improvement while only using the top-1 retrieval result for answer and supporting sentence prediction.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
For FEVER claim verification, we reuse the best open-sourced verification system, i.e., KGAT (Liu et al., 2020), to show the benefit of our retrieval approach over existing retrieval methods. We report 6 For the compute-heavy generative models, we feed in as many passages as possible without running into memory issues (Muli-hop RAG takes top 4 passages from hop1, and for each of those, takes another top 4 from hop2. They are not necessarily the same as the top 16 passages sequences.). As extractive models encode each passage sequence separately, we can use arbitrary number of input sequences. However, the performance mostly plateaus as we use over 200 input sequences. 7 We implemented NQ extractive readers with both RoBERTa-large and ELECTRA-large, and RoBERTa-large yielded a better answer EM of 47.3, which is much lower than the 51.4 answer EM achieved by FiD. 8 As shown by Roberts et al. (2020), a large pretrained seq2seq model can be finetuned to directly decode answers with questions as the only inputs. However, we find that this retrieval-free approach performs poorly on multi-hop questions. See Appendix C for the exact numbers. the results in verification label accuracy (LA) and the FEVER score 9 in Table 7, where the numbers of competitive baselines, GEAR , graph attention network (GAT) (Veličković et al., 2017) and variants of KGAT are from the KGAT (Liu et al., 2020) paper. All these baselines use entity linking for document retrieval, then rerank the sentences of the retrieved documents, and finally use different graph attention mechanisms over the fully-connected sentence graph to predict verification labels. Since some instances in the multi-evidence subset used by previous studies only needs multiple evidence sentences from the same document, we additionally test on a strict multi-hop subset with instances that need multiple documents. As shown by the results, even without finetuning the downstream modules, simply replacing the retrieval component with MDR leads to significant improvements, especially on the strict multi-evidence subset.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Open-domain QA with Dense Retrieval In contrast to sparse term-index IR methods, which are widely used by existing open-domain QA systems (Chen et al., 2017;Wang et al., 2018;, recent systems Guu et al., 2020;Karpukhin et al., 2020) typically uses dense passage retrieval techniques that better capture the semantic matching beyond simple n-gram overlaps.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
To generate powerful dense question and passage representations, these methods either conduct largescale pretraining with self-supervised tasks that are close to the underlying question-passage matching in retrieval, or directly use the human-labeled question-passage pairs to finetune pretrained masked language models. On information-seeking QA datasets such as NaturalQuestions (Kwiatkowski et al., 2019) or WebQuestions (Berant et al., 2013), these dense methods have achieved significant improvements over traditional IR methods. However, these extensively studied datasets only include simple questions that can be answered from a single passage.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Other Multi-hop QA Work Apart from HotpotQA, other multi-hop QA datasets (Welbl et al., 2018;Talmor & Berant, 2018; are mostly built from knowledge bases (KBs). Compared to questions in HotpotQA, questions in these datasets are rather synthetic and less diverse. As multi-hop relations in KBs could be mentioned together in a single text piece, these datasets are not designed for an open-domain setting which necessitates multi-hop retrieval. Existing methods on these datasets either retrieve passages from a small passage pool pruned based on the the specific dataset Dhingra et al., 2020), or focus on a non-retrieval setting where a compact documents set is already given (De Cao et al., 2018;Tu et al., 2019;Beltagy et al., 2020). Compared to these research, our work aims at building an efficient multi-hop retrieval model that easily scales to large real-world corpora that include millions of open-domain documents.
Answering Complex Open-Domain Questions with Multi-Hop Dense Retrieval
Inspired by a recent work (Roberts et al., 2020) that trains the T5 seq2seq model to directly decode answers from questions (retrieval-free), we conduct similar experiments on HotpotQA using BART (Lewis et al., 2020a). As shown in Figure 4, the performance gap between retrieval-based methods and retrieval-free methods on multi-hop QA is much larger than the gap in the case of simple single-hop questions. 
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Open-domain Question Answering (QA) is the task of answering a question given a large collection of text documents (e.g., Wikipedia). Most state-of-the-art approaches for open-domain QA (Chen et al., 2017;Wang et al., 2018a;Lee et al., 2018;Yang et al., 2019) leverage non-parameterized models (e.g., TF-IDF or BM25) to retrieve a fixed set of documents, where an answer span is extracted by a neural reading comprehension model. Despite the success of these pipeline methods in singlehop QA, whose questions can be answered based on a single paragraph, they often fail to retrieve the required evidence for answering multi-hop questions, e.g., the question in Figure 1. Multi-hop QA (Yang et al., 2018) usually requires finding more than one evidence document, one of which often consists of little lexical overlap or semantic relationship to the original question. However, retrieving a fixed list of documents independently does not capture relationships between evidence documents through bridge entities that are required for multi-hop reasoning.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Recent open-domain QA methods learn end-to-end models to jointly retrieve and read documents (Seo et al., 2019;Lee et al., 2019). These methods, however, face challenges for entity-centric questions since compressing the necessary information into an embedding space does not capture lexical information in entities. Cognitive Graph (Ding et al., 2019) incorporates entity links between documents for multi-hop QA to extend the list of retrieved documents. This method, however, compiles a fixed list of documents independently and expects the reader to find the reasoning paths.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Our experimental results show that our method achieves the state-of-the-art results on HotpotQA full wiki and HotpotQA distractor settings (Yang et al., 2018), outperforming the previous stateof-the-art methods by more than 14 points absolute gain on the full wiki setting. We also evaluate our approach on SQuAD Open (Chen et al., 2017) and Natural Questions Open (Lee et al., 2019) without changing any architectural designs, achieving better or comparable to the state of the art, which suggests that our method is robust across different datasets. Additionally, our framework provides interpretable insights into the underlying entity relationships used for multi-hop reasoning.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Neural open-domain question answering Most current open-domain QA methods use a pipeline approach that includes a retriever and reader. Chen et al. (2017) incorporate a TF-IDF-based retriever with a state-of-the-art neural reading comprehension model. The subsequent work improves the heuristic retriever by re-ranking retrieved documents (Wang et al., 2018a;b;Lee et al., 2018;Lin et al., 2018). The performance of these methods is still bounded by the performance of the initial retrieval process. In multi-hop QA, non-parameterized retrievers face the challenge of retrieving all the relevant documents, one or some of which are lexically distant from the question. Recently, Lee et al. (2019) and Seo et al. (2019) introduce fully trainable models that retrieve a few candidates directly from large-scale Wikipedia collections. All these methods find evidence documents independently without the knowledge of previously selected documents or relationships between documents. This would result in failing to conduct multi-hop retrieval.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Retrievers guided by entity links Most relevant to our work are recent studies that attempt to use entity links for multi-hop open-domain QA. Cognitive Graph (Ding et al., 2019) retrieves evidence documents offline, and trains a reading comprehension model to jointly predict possible answer spans and next-hop spans to extend the reasoning chain. Instead, we train our retriever to find reasoning paths directly. Concurrent with our work, Entity-centric IR (Godbole et al., 2019) uses entity linking for multi-hop retrieval. Unlike our method, this method does not learn to retrieve reasoning paths sequentially, nor study the interplay between retriever and reader. Moreover, while the previous approaches require a system to encode all possible nodes, our beam search decoding process only encodes the nodes on the reasoning paths, which significantly reduces the computational costs. PullNet (Sun et al., 2019) learns to retrieve question-aware sub-graphs from text corpora and knowledge bases (e.g., Freebase), while we focus on open-domain QA solely based on text.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Multi-step (iterative) retrievers Similar to our recurrent retriever, multi-step retrievers explore multiple evidence documents iteratively. Multi-step reasoner  repeats the retrieval process for a fixed number of steps, interacting with a reading comprehension model by reformulating the query in a latent space to enhance retrieval performance. Feldman & El-Yaniv (2019)   structure of the documents during the iterative retrieval process. In addition, all of these multi-step retrieval methods do not accommodate arbitrary steps of reasoning and the termination condition is hard-coded. In contrast, our method leverages the Wikipedia graph to retrieve documents that are lexically or semantically distant to questions, and is adaptive to any reasoning path lengths, which leads to significant improvement over the previous work in HotpotQA and SQuAD Open.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Training examples To train the multi-task reader model, we use the ground-truth evidence paragraphs used for training our retriever. It is known to be effective in open-domain QA to use distantly supervised examples, which are not originally associated with the questions but include expected answer strings (Chen et al., 2017;Wang et al., 2018a;Hu et al., 2019). These distantly supervised examples are also effective to simulate the inference time process. Therefore, we combine distantly supervised examples from a TF-IDF retriever with the original supervised examples. Following the procedures in Chen et al. (2017), we add up to one distantly supervised example for each supervised example. We set the answer span as the string that matches a and appears first.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
SQuAD Open SQuAD Open (Chen et al., 2017) is composed of questions from the original SQuAD dataset (Rajpurkar et al., 2016). This is a single-hop QA task, and a single paragraph is associated with each question in the training data.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We use the pre-trained BERT models  using the uncased base configuration (d = 768) for our retriever and the whole word masking uncased large (wwm) configuration (d = 1024) for our readers. We follow Chen et al. (2017) for the TF-IDF-based retrieval model and use the same hyper-parameters. We tuned the most important hyper-parameters, F , the number of the initial TF-IDF-based paragraphs, and B, the beam size, by mainly using the HotpotQA development set (the effects of increasing F are shown in Figure 5 in Appendix C.3 along with the results with B = 1). If not specified, we set B = 8 for all the datasets, F = 500 for HotpotQA full wiki and SQuAD Open, and F = 100 for Natural Questions Open. Moreover, our method shows significant improvement in predicting supporting facts in the full wiki setting. We compare the performance of our approach to other models on the HotpotQA full wiki official hidden test set in Table 2. We outperform all the published and unpublished models including up-to-date work (marked with ♣ ) by large margins in terms of QA performance.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
TF-IDF (Chen et al., 2017), the widely used retrieval method that scores paragraphs according to the TF-IDF scores of the question-paragraph pairs. We simply select the top-2 paragraphs. Re-rank (Nogueira & Cho, 2019) that learns to retrieve paragraphs by fine-tuning BERT to re-rank the top F TF-IDF paragraphs. We select the top-2 paragraphs after re-ranking. Re-rank 2hop which extends Re-rank to accommodate two-hop reasoning. It first adds paragraphs linked from the top TF-IDF paragraphs. It then uses the same BERT model to select the paragraphs. Entity-centric IR is our re-implementation of Godbole et al. (2019) that is related to Re-rank 2hop, but instead of simply selecting the top two paragraphs, they re-rank the possible combinations of the paragraphs that are linked to each other. Retrieval results Table 5 shows that our recurrent retriever yields 8.8 P EM and 9.     Re-rank2hop to Entity-centric IR demonstrates that exploring entity links from the initially retrieved documents helps to retrieve the paragraphs with fewer lexical overlaps. On the other hand, comparing our retriever with Entity-centric IR and Semantic Retrieval shows the importance of learning to sequentially retrieve reasoning paths in the Wikipedia graph. It should be noted that our method with F = 20 outperforms all the QA EM scores in Table 1.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Performance drop by removing the reasoning path re-ranking indicates the importance of verifying the reasoning paths in our reader. Not using negative examples to train the reader degrades EM more than 16 points, due to the over-confident predictions as discussed in Clark & Gardner (2018).
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
The performance with an off-the-shelf entity linking system Although the existence of the hyperlinks is not special on the web, one question is how well our method works without the Wikipedia hyperlinks. We evaluate our method on the development set of HotpotQA full wiki with an off-theshelf entity linking system (Ferragina & Scaiella, 2011) to construct the document graph in our method. More details about this experimental setup can be found in Appendix B.7. Table 7 shows that our approach with the entity linking system shows only 2.3 F1 and 2.2 EM lower scores than those with the hyperlinks, still achieving the state of the art. This suggests that our approach is not restricted to the existence of the hyperlink information, and using hyperlinks is promising.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
The effectiveness of arbitrary-step retrieval The existing iterative retrieval methods fix the number of reasoning steps (Qi et al., 2019;Godbole et al., 2019;Feldman & El-Yaniv, 2019), while our approach accommodates arbitrary steps of reasoning. We also evaluate our method by fixing the length of the reasoning path (L = {1, 2, 3, 4}). Table 8 shows that out adaptive retrieval performs the best, although the length of all the annotated reasoning paths in HotpotQA is two. As discussed in Min et al. (2019b), we also observe that some questions are answerable based on a single paragraph, where our model flexibly selects a single paragraph and then terminates retrieval.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
Equation (2) shows that we compute each paragraph representation w i conditioned on the question q. An alternative approach is separately encoding the paragraphs and the question, to directly retrieve paragraphs (Lee et al., 2019;Seo et al., 2019;. However, due to the lack of explicit interactions between the paragraphs and the question, such a neural retriever using questionindependent paragraph encodings suffers from compressing the necessary information into fixeddimensional vectors, resulting in low performance on entity-centric questions (Lee et al., 2019). It has been shown that attention-based paragraph-question interactions improve the retrieval accuracy if the retrieval scale is tractable (Wang et al., 2018a;Lee et al., 2018). There is a trade-off between the scalability and the accuracy, and this work aims at striking the balance by jointly using the lexical matching retrieval and the graphs, followed by the rich question-paragraph encodings.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
To use the pre-trained BERT models, we used the public code base, pytorch-transformers, 4 written in PyTorch. 5 For optimization, we used the code base's implementation of the Adam optimizer (Kingma & Ba, 2015), with a weight-decay coefficient of 0.01 for non-bias parameters. A warm-up strategy in the code base was also used, with a warm-up rate of 0.1. Most of the settings follow the default settings. To train our recurrent retriever, we set the learning rate to 3 · 10 −5 , and the maximum number of the training epochs to three. The mini-batch size is four; a mini-batch example consists of a question with its corresponding paragraphs. To train our reader model, we set the learning rate to 3 · 10 −5 , and the maximum number of training epochs to two. Empirically we observe better performance with a larger batch size as discussed in previous work (Liu et al., 2019;Ott et al., 2018), and thus we set the mini-batch size to 120. A mini-batch example consists of a question with its evidence paragraphs. We will release our code to follow our experiments. Although using a single dump for different open-domain QA datasets is a common practice (Chen et al., 2017;Wang et al., 2018a;Lee et al., 2018), this potentially causes inconsistent or even unfair evaluation across different experimental settings, due to the temporal inconsistency of the Wikipedia articles. More concretely, every Wikipedia article is editable and and as a result, a fact can be rephrased or could be removed. For instance, a question from the SQuAD development set, "Where does Kenya rank on the CPI scale?" is originally paired with a paragraph from the article of Kenya. Based on a single sentence "Kenya ranks low on Transparency International's Corruption Perception Index (CPI)" from the paragraph, an annotated answer span is "low." However, this sentence has been rewritten as "Kenya has a high degree of corruption according to Transparency International's Corruption Perception Index (CPI)" in a later version of the same article. 7 This is problematic considering the major evaluation metrics based on string matching.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
B.6 DETAILS ABOUT INITIAL CANDIDATES C 1 SELECTION To retrieve the initial candidates C 1 for each question, we use a TF-IDF based retriever with the bi-gram hashing (Chen et al., 2017). For HotpotQA full wiki, we retrieve top F introductory paragraphs, for each question, from a corpus including all the introductory paragraphs. For SQuAD Open and Natural Questions Open, we first retrieve 50 Wikipedia articles through the same TF-IDF retriever, and further run another TF-IDF-based paragraph retriever (Clark & Gardner, 2018;Min et al., 2019a) to retrieve F paragraphs in total.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
We experiment with a variant of our approach, where we incorporate an entity linking system with our framework, in place of the Wikipedia hyperlinks. In this experiment, we first retrieve seed paragraphs using TF-IDF (F = 100), and run an off-the-shelf entity linker (TagMe by Ferragina & Scaiella (2011)) over the paragraphs. If the entity linker detects some entities, we retrieve their corresponding Wikipedia articles, and add edges from the seed paragraphs to the entity-linked paragraphs. Once we build the graph, then we re-run all of the experiments while the other components are exactly the same. We use the TagMe official Python wrapper. 8 C ADDITIONAL RESULTS ON HOTPOTQA C.1 UPPER-BOUND OF OUR RETRIEVAL MODULE For scalability and computational efficiency, we bootstrap our retrieval module with TF-IDF retrieval; we first retrieval F paragraphs using TF-IDF with the method described in Section B.6 and initialize C 1 with these TF-IDF paragraphs. Although we expand our candidate paragraphs at each time step using the Wikipedia graph, if our method failed to retrieve paragraphs a few-hops away from the answer paragraphs, it is likely to fail to reach the answer paragraphs. To estimate the paragraph EM upper-bound, we have checked if two gold paragraphs are included in the top 20 TF-IDF paragraphs and their hyperlinked paragraphs in the HotpotQA full wiki setting. We found that for 75.4% of the questions, all of the gold paragraphs are included in the collections of the TF-IDF paragraphs and the hyperlinked paragraphs. Also, it should be noted when we only consider the TF-IDF retrieval results, the upper-bound drops to 35.1%, which suggests that the TF-IDF-based retrieval cannot effectively discover the paragraphs multi-hop away due to the few lexical overlap. When we increase the number of F to 100 and 500, the upper-bound reaches 84.1% and 89.2%, respectively.
Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering
As we discussed in 3.1.1, we aim at significantly reducing the search space and thus scaling the number of initial TF-IDF candidates. Increasing the number of the initial retrieved paragraphs often improves the recall of the evidence paragraphs of the datasets. On the other hand, increasing the candidate paragraphs introduces additional noises, may distract models, and eventually hurt the performance (Kratzwald & Feuerriegel, 2018). We compare the performance of three different approaches: (i) ours, (ii) ours (greedy, without reasoning path re-ranking), and (iii) Re-rank.
Answering Complex Open-domain Questions Through Iterative Query Generation
More recently, the emergence of multi-hop question answering datasets such as QAngaroo (Welbl et al., 2018) and HOTPOTQA (Yang et al., 2018) has sparked interest in multi-hop QA in the research community. Designed to be more challenging than SQuAD-like datasets, they feature questions that require context of more than one document to answer, testing QA systems' abilities to infer the answer in the presence of multiple pieces of evidence and to efficiently find the evidence in a large pool of candidate documents. However, since these datasets are still relatively new, most of the existing research focuses on the few-document setting where a relatively small set of context documents is given, which is guaranteed to contain the "gold" context documents, all those from which the answer comes (De Cao et al., 2019;Zhong et al., 2019).
Answering Complex Open-domain Questions Through Iterative Query Generation
When deriving supervision signal to train our query generators, the potential search space is enormous for each step of reasoning even if we constrain ourselves to predicting spans from the context. This is aggravated by multiple hops of reasoning required by the question. One solution to this issue is to train the query generators with reinforcement learning (RL) techniques (e.g., RE-INFORCE (Sutton et al., 2000)), where (Nogueira and Cho, 2017) and (Buck et al., 2018) are examples of one-step query generation with RL. However, it is computationally inefficient, and has high variance especially for the second reasoning step and forward, because the context depends greatly on what queries have been chosen previously and their search results. Instead, we propose to leverage the limited supervision we have about the gold supporting documents d 1 , . . . , d S to narrow down the search space.
Answering Complex Open-domain Questions Through Iterative Query Generation
Because off-the-shelf IR systems generally optimize for shallow lexical similarity between query and candidate documents in favor of efficiency, a good proxy for this overlap is locating spans of text that have high lexical overlap with the intended supporting documents. To this end, we propose a simple yet effective solution, employing several heuristics to generate candidate queries: computing the longest common string/sequence between the current retrieval context and the title/text of the intended paragraph ignoring stop words, then taking the contiguous span of text that corresponds to this overlap in the retrieval context. This allows us to not only make use of entity names, but also textual descriptions that better lead to the gold entities. It is also more generally applicable than question decomposition approaches (Talmor and Berant, 2018;Min et al., 2019b), and does not require additional annotation for decomposition.
Answering Complex Open-domain Questions Through Iterative Query Generation
The final QA component of GOLDEN Retriever is based on the baseline model presented in (Yang et al., 2018), which is in turn based on BiDAF++ (Clark and Gardner, 2017). We make two major changes to this model. Yang et al. (2018) concatenated all context paragraphs into one long string to predict span begin and end offsets for the answer, which is potentially sensitive to the order in which these paragraphs are presented to the model. We instead process them separately with shared encoder RNN parameters to obtain paragraph order-insensitive representations for each paragraph. Span offset scores are predicted from each paragraph independently before finally aggregated and normalized with a global softmax operation to produce probabilities over spans. The second change is that we replace all attention mechanism in the original model with self attention layers over the concatenated question and context. To differentiate context paragraph representations from question representations in this self-attention mechanism, we indicate question and context tokens by concatenating a 0/1 feature at the input layer. Figure 4 illustrates the QA model architecture.  Table 2: End-to-end QA performance of baselines and our GOLDEN Retriever model on the HOTPOTQA fullwiki test set. Among systems that were not published at the time of submission of this paper, "BERT pip." was submitted to the official HOTPOTQA leaderboard on May 15 th (thus contemporaneous), while "Entity-centric BERT Pipeline" and "PR-Bert" were submitted after the paper submission deadline.
Answering Complex Open-domain Questions Through Iterative Query Generation
We evaluate our models in the fullwiki setting of HOTPOTQA (Yang et al., 2018). HOTPOTQA is a question answering dataset collected on the English Wikipedia, containing about 113k crowdsourced questions that are constructed to require the introduction paragraphs of two Wikipedia articles to answer. Each question in the dataset comes with the two gold paragraphs, as well as a list of sentences in these paragraphs that crowdworkers identify as supporting facts necessary to answer the question. A diverse range of reasoning strategies are featured in HOTPOTQA, including questions involving missing entities in the question (our Armada example), intersection questions (What satisfies property A and property B?), and comparison questions, where two entities are compared by a common attribute, among others. In the few-document distractor setting, the QA models are given ten paragraphs in which the gold paragraphs are guaranteed to be found; in the opendomain fullwiki setting, which we focus on, the models are only given the question and the entire Wikipedia. Models are evaluated on their answer accuracy and explainability, where the former is measured as overlap between the predicted and gold answers with exact match (EM) and unigram F 1 , and the latter concerns how well the predicted supporting fact sentences match human annotation (Supporting Fact EM/F 1 ). A joint metric is also reported on this dataset, which encourages systems to perform well on both tasks simultaneously.
Answering Complex Open-domain Questions Through Iterative Query Generation
We use the Stanford CoreNLP toolkit (Manning et al., 2014) to preprocess Wikipedia, as well as to generate POS/NER features for the query generators, following (Yang et al., 2018) and (Chen et al., 2017). We always detokenize a generated search query before sending it to Elasticsearch, which has its own preprocessing pipeline. Since all questions in HOTPOTQA require exactly two supporting documents, we fix the number of retrieval steps of GOLDEN Retriever to S = 2. To accommodate arbitrary steps of reasoning in GOLDEN Retriever, a stopping criterion is required to determine when to stop retrieving for more supporting documents and perform few-document question answering, which we leave to future work. During training and evaluation, we set the number of retrieved documents added to the retrieval context to 5 for each retrieval step, so that the total number of paragraphs our final QA model considers is 10, for a fair comparison to (Yang et al., 2018).
Answering Complex Open-domain Questions Through Iterative Query Generation
We compare the end-to-end performance of GOLDEN Retriever against several QA systems on the HOTPOTQA dataset: (1) the baseline presented in (Yang et al., 2018), (2) CogQA (Ding et al., 2019), the top-performing previously published system, and (3) other high-ranking systems on the leaderboard. As shown in Table 2, GOLDEN Retriever is much better at locating the correct supporting facts from Wikipedia compared  to CogQA, as well as most of the top-ranking systems. However, the QA performance is handicapped because we do not make use of pretrained contextualization models (e.g., BERT) that these systems use. We expect a boost in QA performance from adopting these more powerful question answering models, especially ones that are tailored to perform few-document multi-hop reasoning. We leave this to future work.
Answering Complex Open-domain Questions Through Iterative Query Generation
To understand the contribution of GOLDEN Retriever's iterative retrieval process compared to that of the IR engine, we compare the performance of GOLDEN Retriever against two baseline systems on the dev set: one that retrieves 10 supporting paragraphs from Elasticsearch with the original question, and one that uses the IR engine presented in HOTPOTQA. 9 In all cases, we use the QA component in GOLDEN Retriever for the final question answering step. As shown in Table 3, replacing the hand-engineered IR engine in (Yang et al., 2018) with Elasticsearch does result in some gain in recall of the gold documents, but that does not translate to a significant improvement in QA performance. Further inspection reveals that despite Elasticsearch improving overall recall of gold documents, it is only able to retrieve both gold documents for 36.91% of the dev set questions, in comparison to 28.21% from the IR engine in (Yang et al., 2018). In contrast, GOLDEN Retriever improves this percentage to 61.01%, almost doubling the recall over the single-hop baseline, providing the QA component a much better set of context documents to predict answers from.
Answering Complex Open-domain Questions Through Iterative Query Generation
In this paper, we presented GOLDEN (Gold Entity) Retriever, an open-domain multi-hop question answering system for scalable multi-hop reasoning. Through iterative reasoning and retrieval, GOLDEN Retriever greatly improves the recall of gold supporting facts, thus providing the question answering model a much better set of context documents to produce an answer from, and demonstrates competitive performance to the state of the art. Generating natural languages queries for each step of reasoning, GOLDEN Retriever is also more interpretable to humans compared to previous neural retrieval approaches and affords better understanding and verification of model behavior. We start from the Wikipedia dump file containing the introductory paragraphs used in HOTPOTQA that Yang et al. (2018) provide, 10 and add the fields corresponding to Wikipedia page titles and the introductory paragraphs (text) into the index.
Answering Complex Open-domain Questions Through Iterative Query Generation
Our final question answering component is trained with the paragraphs produced by the oracle queries (5 from each hop, 10 in total), with d 1 and d 2 inserted to replace the lowest ranking paragraph in each hop if they are not in the set already. We develop our model based on the baseline model of Yang et al. (2018), and reuse the same default hyperparameters whenever possible. The main differences in the hyperparameters are: we optimize our QA model with Adam (with default hyperparameters) (Kingma and Ba, 2015) instead of stochastic gradient descent with a larger batch size of 64; we anneal the learning rate by 0.5 with a patience of 3 instead of 1, that is, we multiply the learning rate by 0.5 after three consecutive failures to improve dev F 1 ; we clip the gradient down to a maximum 2 norm of 5; we apply a 10% dropout to the model, for which we have increased the hidden size to 128; and use 10 as the coefficient by which we multiply the supporting facts loss, before mixing it with the span prediction loss. We configure the model to read 10 context paragraphs, and limit each paragraph to at most 400 tokens including the title.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
In open-domain reasoning, a model is tasked with retrieving evidence from a large corpus to answer questions, verify claims, or otherwise exhibit broad knowledge. In practice, such open-domain tasks often further require multi-hop reasoning, where the evidence must be extracted from two or more documents. To do this effectively, a model must learn to use partial evidence it retrieves to bridge its way to additional documents leading to an answer. In this vein, HotPotQA [31] contains complex questions answerable by retrieving two passages from Wikipedia, while HoVer [13] contains claims that can only be verified (or disproven) by combining facts from up to four Wikipedia passages. Table 1 illustrates this using the claim "The MVP of [a] game Red Flaherty umpired was elected to the Baseball Hall of Fame" from the HoVer validation set. To verify this claim, a HoVer model must identify facts spread across three Wikipedia pages: Red Flaherty umpired in the World Series in 1955, 1958, 1965, and 1970. The MVP of the 1965 World Series was Sandy Koufax. Koufax was later elected to the Baseball Hall of Fame.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Open-domain reasoning There is significant recent interest in NLP models that can solve tasks by retrieving evidence from a large corpus. The most popular such task is arguably open-domain question answering (OpenQA; Chen et al. [2]), which extends the well-studied machine reading comprehension (MRC) problem over supplied question-passage pairs to answering questions given only a large text corpus like Wikipedia. Other open-domain tasks span claim verification (e.g., FEVER; Thorne et al. [24]), question generation (e.g., with Jeopardy as in Lewis et al. [19]), and open dialogue (e.g., Wizard of Wikipedia; Dinan et al. [8]), among others. Many of these datasets are compiled in the recently-introduced KILT benchmark [21] for knowledge-intensive tasks. Among models for these tasks, the most relevant to our work are OpenQA models that include learned retrieval components. These include ORQA [18], REALM [10], and DPR [15]. Lewis et al. [19] introduced RAG, which by virtue of a seq2seq architecture can tackle OpenQA as well as other open-domain problems, including claim verification and question generation.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Most of the open-domain tasks from §2 can be solved by finding one relevant passage in the corpus, often by design. In contrast, a number of recent works explore multi-hop reasoning over multiple passages. These include QAngaroo [27] and 2WikiMulti-HopQA [11], among others. While thus "multi-hop", these tasks supply the relevant passages for each example (possibly with small set of "distractor" candidates), and thus do not require retrieval from a large corpus. To our knowledge, HotPotQA was the first large-scale open-domain multi-hop task, particularly in its retrieval-oriented "fullwiki" setting. HotPotQA catalyzed much follow-up research. However, it is limited to only two-hop questions, many of which may not require strong multi-hop reasoning capabilities (see Chen and Durrett [3]; Wang et al. [26]), softening the retrieval challenges discussed in §1. Very recently, Jiang et al. [13] introduced the HoVer many-hop verification dataset, which contains two-, three-, and four-hop examples. HoVer contains just over 18,000 training examples, about 5× smaller than HotPotQA, adding to the challenge posed by HoVer.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Multi-hop open-domain models To conduct the "hops", many prior multi-hop systems (e.g., Asai et al. [1]; Zhao et al. [32]) assume explicit links that connect every passage with related entities. We argue that this risks tying systems to link-structured knowledge bases (like Wikipedia) or producing brittle architectures tailored for datasets constructed by following hyperlinks (like HotPotQA). Recently, Xiong et al. [29] and Qi et al. [23] introduce MDR and IRRR, state-of-the-art systems that assume no explicit link structure. Instead, they use an iterative retrieval paradigm-akin to that introduced by Das et al. [6] and Feldman and El-Yaniv [9]-that retrieves passages relevant to the question, reads these passages, and then formulates a new query for another hop if necessary. We adopt this iterative formulation and tackle three major challenges for multi-hop retrieval.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
ColBERT: late interaction paradigm Most learned-retrieval systems for OpenQA ( §2) encode every query and passage into a single dense vector. Khattab and Zaharia [16] argue that such singlevector representations are not sufficiently expressive for retrieval in many scenarios and introduce late interaction, a paradigm that represents every query and every document at a finer granularity: it uses a vector for each constituent token. Within this paradigm, they propose ColBERT, a state-of-the-art retriever wherein a BERT encoder embeds the query into a matrix of N vectors (given N tokens) and encodes every passage in the corpus as matrix of M vectors (for M tokens per passage). The passage representations are query-independent and thus are computed offline and indexed for fast retrieval.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
During retrieval with query q, ColBERT assigns a score to a passage d by finding the maximumsimilarity (MaxSim) score between each vector in q's representation and all the vectors of d and then summing these MaxSim scores. This MaxSim-decomposed interaction enables scaling to massive collections with millions of passages, as the token-level passage vectors can all be indexed for fast nearest-neighbor search. Khattab and Zaharia [16] find this fine-grained matching to outperform single-vector representations, a finding extended to open-domain question answering by Khattab et al. [17]. In this work, we propose FLIPR ( §3.1), a retriever with an improved late interaction mechanism for complex multi-hop queries. Whereas existing retrievers, whether traditional (e.g., TF-IDF) or neural [18; 15; 16], seek passages that match all of the query, multi-hop queries can be long and noisy and need to match disparate contexts. FLIPR handles this explicitly with focused late interaction.  
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Relevance-guided supervision Khattab et al. [17] propose an iterative strategy for weaklysupervising retrievers called relevance-guided supervision (RGS). RGS assumes that no labeled passages are supplied for training the retriever. Instead, every training question is associated with a short answer string whose presence in a passage is taken as a weak signal for relevance. RGS starts with an off-the-shelf retriever and uses it to collect the top-k passages for each training question, dividing these passages into positive and negative examples based on inclusion of the short answer string. These examples are used to train a stronger retriever, which is then used to repeat this process one or two times. We draw inspiration from RGS when designing latent hop ordering: unlike RGS, we do have gold-labeled passages for training but we crucially have multiple hops, whose order is not given. Lastly, our supervision for the first hop shares inspiration with GoldEn [22]. GoldEn uses a bag-of-words model-and thus effectively term overlap-to identify the "more easily retrieved" passage among just two for the two-hop task HotPotQA.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
The Baleen architecture is depicted in Figure 1. In every hop, FLIPR ( §3.1) uses Q t−1 to retrieve K passages from the full corpus. These passages are fed into a two-stage condenser ( §3.3), which reads these passages and extracts the most relevant facts, which we model as individual sentences. The facts are collected into a single sequence and added to Q t for the subsequent hop, if any. Once all hops are complete, Baleen's task-specific reader processes Q T , which now contains the query and all condensed facts, to solve the downstream task. If desired, the top-k passages from each hop can also be collected and fed to a downstream model after retrieval is complete. Baleen's retriever, condenser, and reader are implemented as Transformer encoders [25] and are trained individually. We use BERT-base [7] for FLIPR and, like Qi et al. [23] and Xiong et al. [29], use ELECTRA-large [5] for the other components. For supervision, we introduce the latent hop ordering scheme ( §3.2).
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
The FLIPR encoders and interaction mechanism are shown in Figure 2. Our query encoder reads Q t−1 and outputs a vector representation of every token in the input. Each query embedding interacts with all passage embeddings via a MaxSim operator, permitting us to inherit the efficiency and scalability of ColBERT [16]. While vanilla ColBERT sums all the MaxSim outputs indiscriminately, FLIPR considers only the strongest-matching query embeddings for evaluating each passage: it sums only the top-N partial scores from N scores, withN < N .
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Train a new retriever Rt using queries Qt−1 and negatives Nt−1. For positives, use gold passages not part of any Ps for s < t. 7 Ranking t ← Rt.retrieve(Qt−1); 8 Pt, Nt ← ExtractPositives(Ranking t ); Qt ← Qt−1.expand(OracleFacts(Pt)); 9 end 10 For every hop t ∈ [T ], designate Qt−1 as queries, Pt as positives, and Pt as negatives. 11 Train a final retrieverR using this combined training data for all hops. 12 returnR negatives are the non-gold passages. Subsequently, we expand first-hop queries with the oracle facts from P 1 to obtain the queries for the second hop (Line 4).
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
After all hops are conducted, a reader is used to extract answers or verify the claim. We use a standard Transformer encoder, in particular ELECTRA-large [5], which we feed the final output Q t of our multi-hop retrieval and condensing pipeline. We train for question answering similar to Khattab et al. [17] or claim verification similar to Jiang et al. [13].
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Before beginning our primary evaluation on the many-hop HoVer benchmark, we first investigate the capacity of HotPotQA in reflecting the challenges on multi-hop retrieval ( §1). We use HotPotQA's "fullwiki" setting, where the input to the model is a question whose answer requires retrieving two passages from Wikipedia. Similar to related work [29], we report passage-level exact-match (EM) and Recall@k (R@k) on the development set. These are the percentage of questions for which the model correctly identifies the two gold passages and for which the model's top-k retrieved passages contain both gold passages, respectively. 2 We also report Answer-Recall@k, the percentage of questions whose short answer string is found in the top-k passages (excluding yes/no questions). Here, the top-20 passages from Baleen are simply the union of the top-10 passages retrieved during the first hop and the top-10 passages from the second hop, without duplicates.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We now conduct our primary evaluation, applying Baleen on the many-hop claim verification dataset HoVer, following the evaluation protocol of Jiang et al. [13]. First, we study the retrieval performance of Baleen in §5.2. Subsequently ( §5.3), we investigate its sentence extraction and claim verification performance, which constitutes a test of overall end-to-end system effectiveness. We compare a four-hop Baleen system against the official baseline and the strong ColBERT-Hop baseline from §4. 3 See Appendix §B for implementation details and hyperparameters.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
In particular, HoVer contains two-, three-, and four-hop claims that require facts from 2-4 different Wikipedia pages, and the model must find and extract one or more supporting facts from each of these pages for every claim. Models are not given the number of hops per claim. Table 3 reports the retrieval and passage extraction quality of the systems. We report three metrics, each sub-divided by the number of hops of each claim. The first is Retrieval@100, which is the percentage of claims for which the system retrieves all of the relevant passages within the top-100 results. To compare with Jiang et al. [13], we report the Retrieval@100 results only for supported claims. All other metrics are reported for all claims. The second metric is Passage EM, which is the percentage of claims for which the system can provide the exact set of relevant passages. The third metric is Passage F1, which uses the standard F1 measure to offer a relaxed version of EM.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
At the top of the table, the TF-IDF baseline retrieves top-100 results in one round of retrieval. At the bottom of the table, we include the results reported by Jiang et al. [13] for their BERT ranking model when supplied with oracle retrieval, and also their reported human performance. We show Baleen's performance after four hops, where Baleen's FLIPR retrieves 25 passages in each hop. Note that we exclude passages retrieved in hop t from the retrieval in further hops t > t. As the table shows, Baleen achieves strong results, outperforming the official baseline model by 47.6 points in Retrieval@100, 51.1 points in Passage EM, and 29.0 points in Passage F1. In fact, Baleen's performance also consistently exceeds "Oracle + BERT" at passage extraction.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Next, we evaluate the performance of fact/sentence extraction and thereby the end-to-end claim verification of Baleen. The results are in Table 4, where Sentence EM and Sentence F1 are defined similar to the corresponding metrics in Table 3 but focus on sentence-level extraction. Moreover, Verification Accuracy is the percentage of claims that are labelled correctly as "Supported" or "Unsupported". In Table 4, we see that Baleen's sentence-level results mirror its document-level results, with large performance gains across the board against the baseline model. Baleen also outperforms the oracle-retrieval BERT model of Jiang et al. [13], emphasizing the strong retrieval  and condensing performance of Baleen. In the leaderboard test-set evaluation (scores expected to be posted soon), Baleen increases the overall "HoVer Score" metric from 15.3 for the baseline to 57.5.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Research limitations This work investigates multi-hop reasoning at a large scale by focusing on the challenges presented by retrieval in this setting. While reading the retrieved (or supplied) passages to solve a downstream task is another important aspect, one that has received more attention in the literature, we do not attempt to advance the state of the art approaches for multi-hop reader models. The majority of multi-hop retrieval work to date has focused on two-hop retrieval. We leverage the recently-released HoVer dataset to scale our investigation to four retrieval hops, and Baleen allows for an arbitrary number of hops in principle, but more evaluation is needed before we can claim generality to an arbitrary number of hops. We propose a condenser architecture that summarizes contexts extractively. This architectural decision allows us to scale easily to many hops as it condenses the hop information into a short context, but doing so relies on the availability on sentence-level training information (as in HotPotQA and HoVer) and extracting sentences might in principle lose important context. We expect future work to be able to infer the sentence-level labels in a latent manner and we are excited about work like decontextualization [4] that tries to retain important context for standalone sentences. Lastly, considering that learning neural retrievers for large-scale many-hop tasks is a recently-emerging topic, we had to design our own strong baseline to strengthen our HoVer evaluation, after confirming that our baseline was very strong on HotPotQA.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We implement Baleen using Python 3.7 and PyTorch 1.6 and rely extensively on the HuggingFace Transformers library [28]. 5 We train and test with automatic mixed precision that is built into PyTorch.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Our implementation of FLIPR is an extension of the ColBERT [16] open-source code, 6 where we primarily modify the retrieval modeling components (e.g., adding focused late interaction and including condensed fact tokens in the query encoder).
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
For FLIPR, we fine-tune a BERT-base model (110M parameters). For each round of training, we initialize the model parameters from a ColBERT model previously trained on the MS MARCO Passage Ranking task [20]. To train the single-hop retriever used to initiate the supervision procedure of §3.2, we follow the training strategy of Khattab et al. [17]. In particular, we use this out-of-domain ColBERT model to create training triples, and then we train our retriever (in this case, FLIPR for first-hop) with these triples. Once we have this first-hop model, the rest of the procedure follows Algorithm 1 for latent hop ordering. Table 7 describes our hyperparameters for FLIPR. We manually explored a limited space of hyperparameters in preliminary experiments, tuning validation-set Retrieval@k Accuracy, with k=100 for HoVer and k=20 for HotPotQA, while also being cognizant of downstream Psg-EM and Sent-EM. We expect that a larger tuning budget would lead to further gains, which is consistent with the fact that our Psg-EM and Sent-EM on the held-out leaderboard test set are 1.0 and 0.6 points higher than the public validation set with which we developed our methods. Unless otherwise stated, the hyperparameters apply to both FLIPR and ColBERT.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
We adopt the default learning rate from ColBERT, namely 3 × 10 −6 . We set the embedding dimension to the default d = 128 and use a batch size of 48 triples. We truncate passages to 256 tokens. For the query encoder, we truncate queries to 64 tokens and allow up to 512 tokens in total, particularly for the condensed facts or reranker context passages from the previous hops. We adopt the ColBERT infrastructure for end-to-end retrieval, where candidate generation is done using nearest-neighbor search with FAISS [14]. 7 See Khattab and Zaharia [16] for use with late interaction models. Since multi-hop queries are much longer than standard IR or OpenQA queries, we conduct candidate generation for FLIPR and ColBERT using the embeddings corresponding to the query tokens (defined in §3.1), and then apply (focused) late interaction on both the query and facts embeddings.
Baleen: Robust Multi-Hop Reasoning at Scale via Condensed Retrieval
Our FLIPR retriever adopts a fine-grained late interaction paradigm like ColBERT (see §2), so our memory footprint is relatively large, as it involves storing a small 256-byte (2-byte 128 dimensions) vector per token. The uncompressed index is about 83 GiBs. We note that the authors of ColBERT Khattab and Zaharia [16] have recently released a quantized implementation that can reduce the storage per vector 4-8 fold, and reducing the storage space of dense retrieval methods through compression and quantization while preserving accuracy is an active area of research [12; 30], with recent encouraging results.