Title: LEARNING TO RETRIEVE REASONING PATHS OVER WIKIPEDIA GRAPH FOR QUESTION ANSWERING

Abstract: 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 graphbased 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. 1

1. INTRODUCTION:

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.

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.

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.

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.

2. RELATED WORK:

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.

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.

Multi-step (iterative) retrievers Similar to our recurrent retriever, multi-step retrievers explore multiple evidence documents iteratively. Multi-step reasoner (Das et al., 2019) 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) also propose a query reformulation mechanism with a focus on multi-hop open-domain QA. Most recently, Qi et al. (2019) introduce GoldEn Retriever, which reads and generates search queries for two steps to search documents for HotpotQA full wiki. These methods do not use the graph 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.

3. OPEN-DOMAIN QUESTION ANSWERING OVER WIKIPEDIA GRAPH:

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:

arg max E,a S(q, E, a) s.t. S(q, E, a) = S retr (q, E) + S read (q, E, a).

(1)

3.1. LEARNING TO RETRIEVE REASONING PATHS:

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 .

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.

3.1.1. THE GRAPH-BASED RECURRENT RETRIEVER:

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 (Devlin et al., 2019) 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:

EQUATION

EQUATION

EQUATION

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.

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.

In terms of the computational cost, the number of the paragraphs processed by Equation ( 2 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.

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:

EQUATION

where Ct is a set of the negative examples described above, and includes [EOE] for t < |g|. We exclude p r from C1 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.

3.2. READING AND ANSWERING GIVEN REASONING PATHS:

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; Devlin et al., 2019) , and (2) reasoning path re-ranking, that re-ranks the retrieved reasoning paths by computing the probability that the path includes the answer.

For the reading comprehension task, we use BERT (Devlin et al., 2019) , 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) .

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:

EQUATION

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 :

EQUATION

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 Devlin et al. (2019) .

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.

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

Multi-task loss function:

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:

EQUATION

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). We mask the span losses for negative examples, in order to avoid unexpected effects to the span predictions.

4. EXPERIMENTS:



4.1. EXPERIMENTAL SETUP:

We evaluate our method in three open-domain Wikipedia-sourced datasets: HotpotQA, SQuAD Open and Natural Questions Open. We target all the English Wikipedia paragraphs for SQuAD Open and Natural Questions Open, and the first paragraph (introductory paragraph) of each article for HotpotQA following previous studies. More details can be found in Appendix B.

HotpotQA HotpotQA (Yang et al., 2018) is a human-annotated large-scale multi-hop QA dataset.

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.

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.

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.

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; Das et al., 2019) , 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.

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.

Implementation details:

We use the pre-trained BERT models (Devlin et al., 2019) 

4.2. OVERALL RESULTS:

Table 1 compares our method with previous published methods on the HotpotQA development set.

Our method significantly outperforms all the previous results across the evaluation metrics under both the full wiki and distractor settings. Notably, our method achieves 14.5 F1 and 14.0 EM gains compared to state-of-the-art Semantic Retrieval (Nie et al., 2019) and 10.9 F1 gains over the concurrent Transformer-XH model (Zhao et al., 2020) on full wiki. We can see that our method, even with the BERT base configuration for our reader, significantly outperforms all the previous QA scores. 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.

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.

4.3. PERFORMANCE OF REASONING PATH RETRIEVAL:

We compare our retriever with competitive retrieval methods for HotpotQA full wiki, with F = 20.

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. (Hu et al., 2019) 50.2 41.9 MUPPET (Feldman & El-Yaniv, 2019 ) 46.2 39.3 BERTserini (Yang et al., 2019) 46.1 38.6 DENSPI-hybrid (Seo et al., 2019) 44.4 36.2 MINIMAL (Min et al., 2018) 42.5 34.7 Multi-step Reasoner (Das et al., 2019) 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 .

Retrieval results:



4.4. ANALYSIS:

We conduct detailed analysis of our framework on the HotpotQA full wiki development set.

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; 3 

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.

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

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.

The effectiveness of arbitrary-step retrieval The existing iterative retrieval methods fix the number of reasoning steps (Qi et al., 2019; Das 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.

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 EFL Cup, currently known as the FA Cup EFL Cup Carabao Cup for sponsorship reasons...

FA Cup:

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. (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.

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.

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.

5. CONCLUSION:

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. 

APPENDIX A DETAILS ABOUT MODELING:

A.1 A NORMALIZED RNN

We decompose Equation ( 4) as follows:

EQUATION

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] 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; Das 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.

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:

EQUATION

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:

EQUATION

EQUATION

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.

Published as a conference paper at ICLR 2020

A.3 WHY IS THE INTERPLAY IMPORTANT?:

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.

A.4 HANDLING YES-NO QUESTIONS IN OUR READER COMPONENT:

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.

A.5 SUPPORTING FACT PREDICTION IN HOTPOTQA:

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.

B DETAILS ABOUT EXPERIMENTS B.1 DATASET DETAILS OF HOTPOTQA, SQUAD OPEN AND NATURAL QUESTIONS OPEN:

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.

SQuAD Open and Natural Questions Open For SQuAD Open, we use the original training set (containing 78,713 questions) as our training data, and the original development set (containing 10,570 questions) as our test data. For Natural Questions Open, we follow the dataset splits provided by Min et al. (2019a) , and the training, development and test datasets contain 79,168, 8,757 and 3,610, respectively. For both the SQuAD Open and Natural Questions Open, we train our reader on the original examples with the augmented additional negative examples and the distantly supervised examples described in Section 3.2.

B.2 DERIVING GROUND-TRUTH REASONING PATHS:

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]].

B.3 DETAILS ABOUT NEGATIVE EXAMPLES FOR OUR READER MODEL IN SQUAD OPEN AND NATURAL QUESTIONS OPEN:

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

B.4 TRAINING SETTINGS:

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.

B.5 THE WIKIPEDIA DUMPS FOR EACH DATASET:

For HotpotQA full wiki, we use the pre-processed English Wikipedia dump from October, 2017, provided by the HotpotQA authors. 6 For Natural Questions Open, we use the English Wikipedia dump from December 20, 2018, following Lee et al. (2019) and Min et al. (2019a) . For SQuAD Open, we use the Wikipedia dump provided by Chen et al. (2017) .

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.

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.

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.

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.

B.7 DETAILS ABOUT ENTITY LINKING EXPERIMENT:

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.

C.2 PER-CATEGORY QUESTION ANSWERING AND RETRIEVAL PERFORMANCE ON HOTPOTQA FULL WIKI

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.

We evaluate the question answering and paragraph retrieval performance for each of the two question types. We compare the PR, P EM and QA EM for each of the two categories with two state-of-theart models, Cognitive Graph (Ding et al., 2019) and Semantic Retrieval (Nie et al., 2019) . Here, we set our initial TF-IDF number F to 500. 

C.3 ON THE ROBUSTNESS TO THE INCREASE OF THE PARAGRAPHS:

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.

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.

C.4 RESULTS OF QUESTION-INDEPENDENT PARAGRAPH ENCODING FOR OUR RETRIEVER:

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. 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.

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.

C.5 MORE QUALITATIVE ANALYSIS ON THE REASONING PATH ON HOTPOTQA FULL WIKI

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.

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.

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.

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.

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. 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.

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-Annotated reasoning path: The Bears and I, Oceans (film) Predicted reasoning path: The Bears and I 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.

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").

C.6 QUALITATIVE ANALYSIS ON THE REASONING PATH ON HOTPOTQA DISTRACTOR 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

:

Appendix A.2 discusses the motivation, and Appendix C.4 shows results with an alternative approach.

We use train/dev/test splits provided byMin et al. (2019a), which can be downloaded from https: //drive.google.com/file/d/1qsN5Oyi_OtT2LyaFZFH26vT8Sqjb89-s/view.

https://github.com/huggingface/pytorch-transformers.

https://pytorch.org/.

https://hotpotqa.github.io/wiki-readme.html.

https://en.wikipedia.org/wiki/Kenya on October 25, 2019

https://github.com/marcocor/tagme-python

Figures and Tables:

Paragraph 1: [Walter Davis (footballer)] Walter Otto Davis was a Welsh professional footballer who played at centre forward for Millwall for ten years in the 1910s. When was the football club founded in which Walter Otto Davis played at centre forward? Paragraph 2: [Millwall F.C.] Millwall Football Club is a professional football club in South East London, … Founded as Millwall Rovers in 1885.

Figure 1: An example of open-domain multi-hop question from HotpotQA. Paragraph 2 is unlikely to be retrieved using TF-IDF retrievers due to little lexical overlap to the given question.

Figure 2: Overview of our framework.

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 followChen 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 Figure5in 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.

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 ofGodbole 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. Cognitive Graph(Ding et al., 2019) that uses the provided prediction results of the Cognitive Graph model on the HotpotQA development dataset. Semantic Retrieval(Nie et al., 2019) that uses the provided prediction results of the state-of-the-art Semantic Retrieval model on the HotpotQA development dataset.

Selected by Re-rankWalter Otto Davis was a Welsh professional footballer who played at centre forward for Millwall for ten years in the 1910s.Tranmere Rovers Football Club is an English professional association football club founded in 1884, and based in Welsh Birkenhead, Wirral.When was the football club founded in which Walter Otto Davis played at centre forward?Millwall Football Club is a professional football club in South East London, … Founded as Millwall Rovers in 1885.

Figure 3: Reasoning examples by our model (two paragraphs connected by a dotted line) and Re-rank (the bottom two paragraphs). Highlighted text denotes a bridge entity, and blue-underlined text represents hyperlinks.

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.

Figure 5: Robustness to the increase of F . We compare the F1 scores of our model, our model without a beam search and Re-rank with different number of F .

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

Table content: <table><tr><td>3.1.2 TRAINING OF THE GRAPH-BASED RECURRENT RETRIEVER</td></tr><tr><td>Data augmentation We train our retriever in a supervised fashion using evidence paragraphs an-</td></tr><tr><td>notated for each question. For multi-hop QA, we have multiple paragraphs for each question, and</td></tr><tr><td>single paragraph for single-hop QA. We first derive a ground-truth reasoning path g = [p 1 , . . . , p |g| ]</td></tr><tr><td>using the available annotated data in each dataset. p |g| is set to [EOE] for the termination condition.</td></tr><tr><td>To relax and stabilize the training process, we augment the training data with additional reasoning</td></tr><tr><td>paths -not necessarily the shortest paths -that can derive the answer. In particular, we add a new</td></tr><tr><td>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</td></tr><tr><td>and is linked to the first paragraph p 1 in the ground-truth path g. Adding these new training paths</td></tr><tr><td>helps at the test time when the first paragraph in the reasoning path does not necessarily appear</td></tr><tr><td>among the paragraphs that initialize the Wikipedia search using the heuristic TF-IDF retrieval.</td></tr></table>

HotpotQA development set results: QA and SP (supporting fact prediction) results on HotpotQA's full wiki and distractor settings. "-" denotes no results are available.

Table content: <table><tr><td>full wiki</td><td/><td>distractor</td><td/></tr><tr><td>QA</td><td>SP</td><td>QA</td><td>SP</td></tr></table>

Table 5 shows that our recurrent retriever yields 8.8 P EM and 9.1 AR, leading to the improvement of 10.3 QA EM over Semantic Retrieval. The significant improvement from HotpotQA full wiki test set results: official leaderboard results (on November 6, 2019) on the hidden test set of the HotpotQA full wiki setting. Work marked with ♣ appeared after September 25.

Table content: <table><tr><td>Models</td><td>QA</td><td/><td>SP</td><td/><td>Models</td><td>F1</td><td>EM</td></tr><tr><td>(*: anonymous)</td><td>F1</td><td>EM</td><td>F1</td><td>EM</td><td>multi-passage (Wang et al., 2019b)</td><td colspan="2">60.9 53.0</td></tr><tr><td>Semantic Retrieval</td><td colspan="4">57.3 45.3 70.8 38.7</td><td>ORQA (Lee et al., 2019)</td><td>-</td><td>20.2</td></tr><tr><td>GoldEn Retriever</td><td colspan="4">48.6 37.9 64.2 30.7</td><td>BM25+BERT (Lee et al., 2019)</td><td>-</td><td>33.2</td></tr><tr><td>Cognitive Graph</td><td colspan="4">48.9 37.1 57.7 22.8</td><td>Weaver (Raison et al., 2018)</td><td>-</td><td>42.3</td></tr><tr><td>Entity-centric IR</td><td colspan="4">46.3 35.4 43.2 0.06</td><td>RE 3</td><td/></tr><tr><td>MUPPET</td><td colspan="4">40.3 30.6 47.3 16.7</td><td/><td/></tr><tr><td>DecompRC</td><td colspan="2">40.7 30.0</td><td>-</td><td>-</td><td/><td/></tr><tr><td>QFE</td><td colspan="4">38.1 28.7 44.4 14.2</td><td/><td/></tr><tr><td>Baseline</td><td colspan="3">32.9 24.0 37.7</td><td>3.9</td><td/><td/></tr><tr><td>HGN* ♣</td><td colspan="4">69.2 56.7 76.4 50.0</td><td/><td/></tr><tr><td>MIR+EPS+BERT* ♣</td><td colspan="4">64.8 52.9 72.0 42.8</td><td/><td/></tr><tr><td>Transformer-XH*</td><td colspan="4">60.8 49.0 70.0 41.7</td><td/><td/></tr><tr><td>Ours</td><td colspan="4">73.0 60.0 76.4 49.1</td><td/><td/></tr></table>

SQuAD Open results: we report F1 and EM scores on the test set of SQuAD Open, following previous work.

Table content: <table><tr><td>39.2 31.9</td></tr></table>

Natural Questions Open results: we report EM scores on the test and development sets of Natural Questions Open, following previous work.

Table content: <table><tr><td>Models</td><td>AR</td><td>PR</td><td colspan="2">P EM EM</td></tr><tr><td>Ours (F = 20)</td><td colspan="2">87.0 93.3</td><td>72.7</td><td>56.8</td></tr><tr><td>TF-IDF</td><td colspan="2">39.7 66.9</td><td>10.0</td><td>18.2</td></tr><tr><td>Re-rank</td><td colspan="2">55.1 85.9</td><td>29.6</td><td>35.7</td></tr><tr><td>Re-rank 2hop</td><td colspan="2">56.0 70.1</td><td>26.1</td><td>38.8</td></tr><tr><td>Entity-centric IR</td><td colspan="2">63.4 87.3</td><td>34.9</td><td>42.0</td></tr><tr><td>Cognitive Graph</td><td colspan="2">76.0 87.6</td><td>57.8</td><td>37.6</td></tr><tr><td colspan="3">Semantic Retrieval 77.9 93.2</td><td>63.9</td><td>46.5</td></tr></table>

Retrieval evaluation: Comparing our retrieval method with other methods across Answer Recall, Paragraph Recall, Paragraph EM, and QA EM metrics.

Table content: <table/>

Ablation study: evaluating different variants of our model on HotpotQA full wiki.

Table content: <table><tr><td>Settings (F = 100)</td><td>F1</td><td>EM</td><td>Settings (F = 100)</td><td>F1</td><td>EM</td></tr><tr><td>full</td><td colspan="2">72.4 59.5</td><td>with hyperlinks</td><td colspan="2">72.4 59.5</td></tr><tr><td>retriever, no recurrent module</td><td colspan="2">52.5 42.1</td><td colspan="3">with entity linking system 70.1 57.3</td></tr><tr><td>retriever, no beam search</td><td colspan="2">68.7 56.2</td><td/><td/><td/></tr><tr><td>retriever, no link-based negatives</td><td colspan="2">64.1 52.6</td><td/><td/><td/></tr><tr><td colspan="3">reader, no reasoning path re-ranking 70.1 57.4</td><td/><td/><td/></tr><tr><td>reader, no negative examples</td><td colspan="2">53.7 43.3</td><td/><td/><td/></tr></table>

Performance with different link structures: comparing our results on the Hotpot QA full wiki development set when we use an off-the-shelf entity linking system instead of the Wikipedia hyperlinks.

Table content: <table><tr><td colspan="2">Settings (F = 100)</td><td>F1</td><td>EM</td></tr><tr><td colspan="2">Adaptive retrieval</td><td colspan="2">72.4 59.5</td></tr><tr><td/><td colspan="3">L = 1 45.8 35.5</td></tr><tr><td>L-step retrieval</td><td colspan="3">L = 2 71.4 58.5 L = 3 70.1 57.7</td></tr><tr><td/><td colspan="3">L = 4 66.3 53.9</td></tr></table>

Performance with different reasoning path length: comparing the performance with different path length on HotpotQA full wiki. L-step retrieval sets the number of the reasoning steps to a fixed number.

Table content: <table><tr><td>(F = 100)</td><td colspan="2">Retriever Reader</td><td>EM</td></tr><tr><td>Avg. # of L</td><td>1.96</td><td>2.21</td><td>with L</td></tr><tr><td>1</td><td>539</td><td>403</td><td>31.2</td></tr><tr><td>2</td><td>6,639</td><td>5,655</td><td>60.0</td></tr><tr><td>3</td><td>227</td><td>1,347</td><td>63.0</td></tr></table>

Statistics of the reasoning paths: the average length and the distribution of length of the reasoning paths selected by our retriever and reader for HotpotQA full wiki. Avg. EM represents QA EM performance.

Table content: <table/>

Future work involves end-to-end training of our graph-based recurrent retriever and reader for improving upon our current two-stage training.Wei Yang, Yuqing Xie, Aileen Lin, Xingyu Li, Luchen Tan, Kun Xiong, Ming Li, and Jimmy Lin.End-to-end open-domain question answering with BERTserini. In NAACL (Demonstrations), 2019.

Table content: <table><tr><td>Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William Cohen, Ruslan Salakhutdinov,</td></tr><tr><td>and Christopher D. Manning. HotpotQA: A dataset for diverse, explainable multi-hop question</td></tr><tr><td>answering. In EMNLP, 2018.</td></tr><tr><td>Chen Zhao, Chenyan Xiong, Corby Rosset, Xia Song, Paul Bennett, and Saurabh Tiwary.</td></tr><tr><td>Transformer-XH: Multi-hop question answering with extra hop attention. In ICLR, 2020.</td></tr></table>

Table10shows that our retriever yields 16.5 P EM Retrieval evaluation: Comparing our retrieval method with other methods across Answer Recall, Paragraph Recall, Paragraph EM, and QA EM metrics.

Table content: <table><tr><td/><td colspan="3">Total (7,405)</td><td colspan="3">Bridge (5,918)</td><td colspan="2">Comp (1,487)</td></tr><tr><td>Models</td><td>PR</td><td colspan="2">P EM EM</td><td>PR</td><td colspan="2">P EM EM</td><td>PR</td><td>P EM EM</td></tr><tr><td>Ours</td><td>94.3</td><td>75.7</td><td colspan="2">60.5 93.9</td><td>73.7</td><td colspan="2">57.8 98.7</td><td>83.5</td><td>70.5</td></tr><tr><td>Cognitive Graph (Ding et al., 2019)</td><td>87.6</td><td>57.8</td><td colspan="2">37.5 84.8</td><td>51.8</td><td colspan="2">36.1 98.6</td><td>81.6</td><td>53.7</td></tr><tr><td colspan="2">Semantic Retrieval (Nie et al., 2019) 93.2</td><td>63.9</td><td colspan="2">46.5 91.6</td><td>57.2</td><td colspan="2">42.7 99.7</td><td>90.6</td><td>61.7</td></tr></table>

Effects of the question-dependent paragraph encoding: Comparing our retriever model

Table content: <table><tr><td>1.2) for quick experiments.</td></tr></table>

Peer review (iclr2020):
This paper proposes a method to find a sequence of reasoning paragraphs in Wikipedia to answer queries requiring multi-hop reasoning. They make the key observation that answering multi-hop queries might require retrieving evidence that have very less lexical overlap with the question. Given a query, the proposed method starts from a set of initial paragraphs retrieved by a tf-idf retriever and uses the outgoing Wikipedia anchor link to hop to the next evidence. They propose a simple recurrent neural network that takes in the current paragraph (and the hidden state) and decide which paragraph to hop to in the next step. Because of the available supervision for the paragraphs (in HotpotQA), they can train a supervised path selector. They also add a special EoE token that denotes the end of the reasoning path, thereby having the ability to produce reasoning paths of different lengths. After training the retriever a beam of reasoning paths is sent to the reader module. The reader module re-ranks the reasoning paths again and then use a standard BERTQA model and the top re-ranked chain of paragraphs to find the evidence. Overall, the paper presents a well-designed system for handling multi-hop queries and the explicit recurrent state is a nice contribution and addition to the IR model proposed in Godbole et al., 2019. The paper is clearly written for the most part. ===Update (11/12/2019)=== The authors have addressed all my comments and have improved the results since. I am recommending acceptance. Nice work. Strengths: — The proposed method has demonstrated strong results on 2 datasets in challenging open-domain settings. The ablation results are helpful. — The paper is clearly written and was straightforward to follow Weaknesses: 1. The paper mentions that it studies the interplay between the retriever and reader. It is unclear how it is doing so, since the retriever and the reader are not explicitly interacting with each other. Cant the retriever and the reader be trained separately? 2. It is unclear / not motivated, why there is an extra step of re-ranking required in the reading stage? In other words, what kinds of extra inductive bias is this additional step of re-ranking providing since the same kind of supervision was used while training the retriever model. I do note that the ablation study is helpful and it is clear that it is effective, but it would be nice to see a discussion regarding why this second step of re-ranking helps. 3. Since the reader model (BERT reader) takes the top scoring chain of paragraphs concatenated together, that would imply that it is currently limited by the number of positional embeddings in the BERT model (512 tokens). I think this limitation should be explicitly mentioned and possible remedies discussed. 4. The current approach is heavily dependent on Wikipedia graph and will not work if the hyperlink graph is not provided. It would have been nice to have an entity linker component that could also create the graph structure. I believe concurrent work such as Godbole et al., 2019 has addressed this and the paper should mention this while contrasting with their work. 5. From figure 2, I got an impression that since the reader scored the span in *Top 2 reasoning path” higher, that was selected. But after section 3.2, I was left confused because it looks like the reader model consumes the top scoring chain after the second stage of re-ranking. This is not clear from the figure and should be fixed. 6. Discussion on scalability: Although the retriever is clearly very effective for such questions, the running time would be prohibitive (for open domain QA) as at test time, query dependent context representations is constructed for each of the paragraph in the reasoning chain. I would like to see a discussion / some running time comparison where query independent paragraph representations are constructed and the network just encodes the query independently at test time. Minor: Typo liked -> linked (Sec 4.3, line 5)