PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning to Retrieve Reasoning Paths over Wikipedia Graph for Question Answering

Akari Asai, Kazuma Hashimoto, Hannaneh Hajishirzi, Richard Socher, Caiming Xiong

arXiv:1911.10470v2cs.CL

TL;DR

Multi-hop open-domain QA requires retrieving multiple evidence documents, including documents with little lexical or semantic relationship to the question. The paper learns graph-based recurrent reasoning-path retrieval over Wikipedia and uses a reader to rank paths and extract answers, achieving state-of-the-art or comparable performance across three datasets, including more than 14 points of absolute gain on HotpotQA full wiki.

  • Problem

    Multi-hop QA often requires evidence documents with little lexical or semantic relationship to the question, which independent fixed-list retrieval does not connect through bridge entities.

  • Method

    A recurrent retriever sequentially selects evidence paragraphs over a Wikipedia graph, while a reader ranks reasoning paths and extracts the answer from the best path.

  • Results

    The method achieves state-of-the-art results on HotpotQA, SQuAD Open, and Natural Questions Open, including more than 14 points of absolute gain on HotpotQA full wiki.

  • Takeaways & Limitations

    Graph-based sequential retrieval provides robust reasoning-path retrieval across open-domain QA datasets without architectural changes across datasets.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper addresses multi-hop QA failures caused by retrieving evidence independently when one required paragraph has little lexical or semantic relationship to the question. It introduces recurrent graph-based retrieval and a reader that ranks reasoning paths, achieving strong results across open-domain QA datasets.

  • Motivation: Multi-hop QA requires multiple evidence documents, but independent fixed-list retrieval does not model relationships through bridge entities.One required document may have little lexical overlap or semantic relationship to the original question.
  • Approach: The proposed recurrent graph-based retriever sequentially selects evidence documents conditioned on previously retrieved documents to form reasoning paths.The reader then ranks these paths and extracts the answer from the best one.
  • Approach: The framework constructs a Wikipedia paragraph graph and trains recurrent retrieval and reading models with data augmentation and negative-example mining.The retriever models paths, while the reader scores whether each path contains and allows extraction of the correct answer phrase.
  • Results: More than 14 points of absolute gain over previous state-of-the-art methods is reported on HotpotQA full wiki.The method also achieves state-of-the-art results on HotpotQA distractor and better or comparable results on SQuAD Open and Natural Questions Open.

2 RELATED WORK

Prior open-domain QA systems rely on initial retrieval, entity links, or iterative query reformulation, but have limitations in modeling reasoning paths and flexible termination. The paper instead learns graph-based sequential retrieval over Wikipedia.

  • Neural open-domain question answering: Pipeline QA performance remains bounded by the initial retriever, especially when multi-hop evidence is difficult to retrieve.Non-parameterized retrievers struggle to retrieve all relevant documents for multi-hop questions.
  • Retrievers guided by entity links: Entity-link methods extend retrieval or leave reasoning-path discovery to the reader, whereas this work trains the retriever to find reasoning paths directly.The contrast concerns where path construction is performed in the system.
  • Multi-step (iterative) retrievers: Existing multi-step retrievers use iterative retrieval or query reformulation, but do not accommodate arbitrary reasoning steps or adaptive termination.The paper positions graph traversal as a way to support variable-length reasoning paths.
  • Multi-step (iterative) retrievers: The proposed method leverages the Wikipedia graph to retrieve documents lexically or semantically distant from questions and improves over previous work on HotpotQA and SQuAD Open.This claimed comparison is stated in the related-work discussion.

3 OPEN-DOMAIN QUESTION ANSWERING OVER WIKIPEDIA GRAPH

The framework represents Wikipedia paragraphs as a graph and combines recurrent path retrieval with multi-task reading and answer extraction. Training uses supervised paths, augmentation, and negative examples, while inference uses graph-guided beam search.

  • Overview: The system retrieves and reads sequences of Wikipedia paragraphs, combining retriever and reader scores over reasoning paths.Its objective is decomposed into retrieval and reading components.
  • Graph construction: Wikipedia paragraphs form graph nodes connected by hyperlinks and symmetric within-document links.These links provide traversal structure for retrieving related evidence paragraphs.
  • Graph-based recurrent retriever: An RNN sequentially selects candidate paragraphs using its hidden state, then expands later candidates through graph links and high-probability alternatives.The design supports multiple reasoning paths and flexible path lengths.
  • Beam search: TF-IDF initializes candidates, after which beam search explores paths in the directed Wikipedia graph while adding an end-of-evidence option.This reduces computation over millions of possible paragraphs.
  • Retriever training: Retriever training derives ground-truth paths with an explicit termination condition and uses TF-IDF- and hyperlink-based negative examples.Hyperlink-based negatives are used for multi-hop QA to discriminate relevant from irrelevant paragraphs.
  • Reading and answering: The reader jointly extracts answer spans and reranks retrieved reasoning paths according to the probability that a path contains the answer.BERT receives the question concatenated with all paragraphs in a path, enabling cross-paragraph self-attention.
  • Reader training: Reader training adds incomplete or misleading paths by replacing answer-containing paragraphs with highly ranked TF-IDF paragraphs.These examples train discrimination between relevant and irrelevant reasoning paths.

4 EXPERIMENTS

The experiments evaluate the method across three open-domain QA datasets and analyze retrieval, ablations, graph construction, and reasoning-path length. Results show strong performance, with especially large gains on HotpotQA and evidence that recurrent, link-aware retrieval and reader reranking are important.

  • Experimental Setup: The evaluation covers HotpotQA, SQuAD Open, and Natural Questions Open, using standard QA and retrieval metrics.HotpotQA additionally includes supporting-fact metrics, while paragraph retrieval is evaluated with Answer Recall, Paragraph Recall, and Paragraph EM.
  • Overall Results: 14.5 F1 and 14.0 EM gains over Semantic Retrieval are reported on HotpotQA full wiki, alongside improvements across full wiki and distractor settings.The method also improves supporting-fact prediction in the full wiki setting and outperforms published and unpublished methods on the hidden test set.
  • Overall Results: 2.9 F1 and 3.5 EM gains over the concurrent state-of-the-art model are reported on SQuAD Open, while Natural Questions Open matches the best end-to-end retriever.The retriever is reported to run on a single GPU, unlike fully end-to-end retrievers that generally require industry-scale training resources.
  • Reasoning Path Retrieval: 8.8 P EM and 9.1 AR are achieved by the recurrent retriever, contributing to a 10.3 QA EM improvement over Semantic Retrieval.Entity-link exploration helps retrieve paragraphs with fewer lexical overlaps, while sequential reasoning-path retrieval improves over competing retrieval methods.
  • Analysis: Removing the recurrent module drops EM by 17.4 points, omitting hyperlink-based negatives causes the second-largest drop, and greedy search loses about 4 EM points.These ablations support conditioning on previous retrieval steps, negative sampling, and beam search over the graph.
  • Analysis: Adaptive reasoning-path retrieval performs best over fixed lengths, while paths of length 3 yield the strongest reported performance at 63.0 EM.The reader selects notably longer paths than the retriever, suggesting that reader reranking favors longer and more convincing multi-hop paths.

5 CONCLUSION

The paper concludes that graph-based recurrent retrieval constructs reasoning paths, while a reader re-ranks them to select the answer. It reports robust performance across datasets and identifies end-to-end training as future work.

  • 5 CONCLUSION: The retriever sequentially selects evidence paragraphs to form reasoning paths, and the reader re-ranks those paths before extracting the final answer.The framework combines recurrent retrieval over a graph with reader-based path selection.
  • 5 CONCLUSION: The method achieves state-of-the-art performance on SQuAD Open and Natural Questions Open without architectural changes.The unchanged architecture supports the paper’s reported robustness across datasets.
  • 5 CONCLUSION: The framework provides insights into entity relationships, and its discrete reasoning paths support interpretation of the reasoning process.The paths expose intermediate evidence selections rather than only the final answer.
  • 5 CONCLUSION: Future work will pursue end-to-end training of the graph-based recurrent retriever and reader.The current framework uses two-stage training.
  • 5 CONCLUSION: The retriever models paragraph interactions through BERT representations, while the reader jointly scores path plausibility and answer extraction.The retriever and reader use different but complementary scoring roles.

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

The appendix describes dataset splits, training data, augmentation, negative examples, and optimization settings for HotpotQA, SQuAD Open, and Natural Questions Open.

  • B.1 DATASET DETAILS OF HOTPOTQA, SQUAD OPEN AND NATURAL QUESTIONS OPEN: HotpotQA provides separate training, development, and test sets, while its distractor and full-wiki settings use different retrieval-training data.The distractor setting associates each question with ten original paragraphs; the full-wiki setting uses augmented data.
  • B.1 DATASET DETAILS OF HOTPOTQA, SQUAD OPEN AND NATURAL QUESTIONS OPEN: SQuAD Open and Natural Questions Open use their specified dataset splits and train readers with augmented negative or distantly supervised examples.The additional examples are described as part of the reader-training setup.
  • B.1 DATASET DETAILS OF HOTPOTQA, SQUAD OPEN AND NATURAL QUESTIONS OPEN: Ground-truth reasoning paths are derived from annotated evidence paragraphs; single-paragraph examples use a path ending with [EOE].For single-hop examples, the path is represented as [p, [EOE]].
  • B.1 DATASET DETAILS OF HOTPOTQA, SQUAD OPEN AND NATURAL QUESTIONS OPEN: SQuAD reader training adds paragraphs without the answer string and unanswerable SQuAD 2.0 questions, while Natural Questions adds paragraphs without the answer string.These examples serve as additional negative training data.
  • B.1 DATASET DETAILS OF HOTPOTQA, SQUAD OPEN AND NATURAL QUESTIONS OPEN: Optimization uses Adam with weight decay and warm-up, while the recurrent retriever uses a learning rate of 3 · 10^-5.Most other settings follow the underlying code base’s defaults.

B.5 THE WIKIPEDIA DUMPS FOR EACH DATASET

The appendix documents dataset-specific Wikipedia dumps and retrieval settings, while noting temporal inconsistencies that can affect evaluation and reproducibility.

  • B.5 THE WIKIPEDIA DUMPS FOR EACH DATASET: The experiments use Wikipedia dumps from October 2017 for HotpotQA, December 20, 2018 for Natural Questions Open, and a dump provided for SQuAD Open.The dump dates and sources differ across datasets.
  • B.5 THE WIKIPEDIA DUMPS FOR EACH DATASET: Using one Wikipedia dump across settings can make evaluation inconsistent or unfair because articles change over time.Facts may be rephrased or removed, affecting string-matching metrics.
  • B.5 THE WIKIPEDIA DUMPS FOR EACH DATASET: Natural Questions Open queries can reflect historical trends, so later events may be absent from an earlier Wikipedia dump.The paper gives television shows broadcast in 2018 as an example that may not be answerable from a 2017 dump.
  • B.5 THE WIKIPEDIA DUMPS FOR EACH DATASET: The authors state that Wikipedia’s evolving nature should be considered for reproducibility and plan to release processed articles for each experiment.The planned release targets dataset-specific preprocessing.
  • B.5 THE WIKIPEDIA DUMPS FOR EACH DATASET: Initial candidates are retrieved with TF-IDF, after which the method expands candidates through Wikipedia hyperlinks or entity-linked paragraphs.The entity-linking variant uses TagMe to add edges from seed paragraphs.
  • B.5 THE WIKIPEDIA DUMPS FOR EACH DATASET: 75.4% of HotpotQA full-wiki questions include both gold paragraphs among the top 20 TF-IDF paragraphs and their hyperlinked paragraphs.The upper bound rises to 84.1% with F=100 and 89.2% with F=500, compared with 35.1% for TF-IDF alone.
  • B.5 THE WIKIPEDIA DUMPS FOR EACH DATASET: Bridge questions are harder because their bridge entities are rarely stated explicitly, whereas comparison questions mention both related entities.This distinction affects paragraph discovery for multi-hop retrieval.
  • B.5 THE WIKIPEDIA DUMPS FOR EACH DATASET: The retrieval evaluation compares Answer Recall, Paragraph Recall, Paragraph EM, and QA EM across question types and methods.Table 10 includes comparisons with Cognitive Graph and Semantic Retrieval.

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

Increasing the initial paragraph pool can improve evidence recall, but additional candidates also introduce noise that may distract the models and reduce performance.

  • C.3 ON THE ROBUSTNESS TO THE INCREASE OF THE PARAGRAPHS: Larger initial TF-IDF candidate sets often improve evidence-paragraph recall but can add noise and eventually hurt performance.The experiment compares approaches under different numbers of initial paragraphs.

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

Question-dependent paragraph encoding is important for retrieval in complex, entity-centric open-domain QA, especially when searching the full Wikipedia collection. Its absence substantially harms full-wiki performance, while the smaller distractor-setting drop reflects an easier, closed search space.

  • Question-independent paragraph encoding significantly deteriorates QA F1 and EM performance on HotpotQA full wiki.The comparison uses the same initial retrieval, Wikipedia graph, beam search, and reader model.
  • The results demonstrate the importance of question-dependent encoding for complex and entity-centric open-domain question answering.
  • The performance drop is much smaller on the HotpotQA distractor setting because each question has only ten paragraphs, including both gold paragraphs.This closed setting narrows the search space and makes retrieval easier than in full wiki.
  • In the distractor setting, the question-independent model’s top-1 retrieval P EM is 12% lower than the question-dependent model’s.Considering all beam-search paths produces almost the same gold-path coverage, allowing the reader to perform similarly.

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

On HotpotQA full wiki, the model retrieves and re-ranks flexible reasoning paths rather than assuming every question requires the annotated two-paragraph path. Its paths may be shorter when one paragraph suffices or longer when an extra bridge-evidence paragraph helps.

  • The model explicitly retrieves plausible reasoning paths and re-ranks them, providing interpretable evidence for the entity relationships used in multi-hop reasoning.
  • The retriever flexibly selects one or more paragraphs, including paths shorter or longer than the original gold reasoning paths.HotpotQA annotations use two relevant paragraphs, but the model accommodates arbitrary reasoning steps.
  • Reasoning path only with single paragraph: For a bridge-type question, the model selects only Nicole Kidman instead of both the Before I Go to Sleep and Nicole Kidman paragraphs.Lexical overlap with the question can make the second paragraph sufficient for answering.
  • Reasoning path only with single paragraph: For a comparison-type question, the model selects one paragraph because lexical overlap with The Bears and I permits answering from that paragraph alone.
  • Reasoning path with three paragraphs: A three-paragraph path adds Blue Jeans before the two annotated gold paragraphs, potentially supplying bridge evidence for the reader.The added paragraph is strongly relevant but does not contain the answer; it may help identify the bridge entity Back to December.

C.6 QUALITATIVE ANALYSIS ON THE REASONING PATH ON HOTPOTQA DISTRACTOR

In HotpotQA distractor, the graph-based recurrent retriever uses previously selected paragraphs to uncover bridge entities and recover paragraph pairs that a fixed re-ranking strategy can miss. The framework also handles cases where the retriever terminates early.

  • The distractor setting supplies both ground-truth paragraphs for each question, enabling analysis of how retrieval handles known candidate sets.
  • A fixed re-rank strategy can select a wrong paragraph when the retriever initially misses the bridge entity Pasek & Paul.The recurrent framework conditions later retrieval on the selected paragraph, addressing this failure pattern in the illustrated example.
  • The graph-based recurrent retriever differs from the top-2 paragraph-selection strategy in 588 examples, or 7.9% of the distractor development dataset.
  • Conditioning on a first paragraph can reveal a bridge entity and enable selection of the correct second paragraph.In one example, selecting P1 exposes the Russian Civil War bridge entity, after which the retriever selects P2.

D ADDITIONAL RESULTS ON SQUAD OPEN AND NATURAL QUESTIONS OPEN

Additional experiments show that the framework adapts reasoning-path length to dataset structure: it usually uses one paragraph on SQuAD Open but can exploit longer paths on Natural Questions Open. Qualitative evidence illustrates multi-hop retrieval even without gold path annotations.

  • SQuAD Open: On SQuAD Open, restricting paths to one paragraph changes F1/EM by only 0.1% compared with allowing longer paths.The retriever is trained with single-paragraph annotations, while the reader sometimes selects two-paragraph paths from beam search.
  • Natural Questions Open: On Natural Questions Open, the model obtains a 1% EM improvement over the L = 1 baseline.Ground-truth path augmentation leads the retriever to prefer longer reasoning paths than on SQuAD Open.
  • Natural Questions Open: For a Natural Questions example, the retriever hops from Roberta Flack to Killing Me Softly with His Song to answer a low-overlap question.The reader verifies the path and extracts the answer from the originally annotated paragraph.
  • Natural Questions Open: The augmented training examples teach the model to retrieve multi-hop reasoning paths from the entire Wikipedia without gold reasoning-path annotations.
  • Across SQuAD Open and Natural Questions Open, the framework retrieves reasoning paths flexibly with evidence sufficient for each dataset’s nature.
Loading 1911.10470v2…