PaperlayerView exact revision on arXiv

Source-linked AI summary

Natural Logic-guided Autoregressive Multi-hop Document Retrieval for Fact Verification

Rami Aly, Andreas Vlachos

arXiv:2212.05276v1cs.CL

TL;DR

Fact verification often needs evidence from multiple documents, but dense multi-hop retrieval requires storing knowledge-base representations and retrieve-and-rerank methods can rely on heuristics and hyperlinks. AdMIRaL combines autoregressive document retrieval with natural-logic proofs that assess evidence sufficiency. It is competitive across several benchmarks while using substantially less memory than competing dense systems.

  • Problem

    Multi-hop fact verification needs evidence from multiple documents, while dense retrieval requires storing document representations and retrieve-and-rerank methods can rely on heuristics and hyperlinks.

    Source: §1 · p. 1

  • Method

    AdMIRaL autoregressively scores documents jointly with previously retrieved sentences and uses natural-logic proofs to assess evidence sufficiency and terminate retrieval.

    Source: §1 · pp. 2–3

  • Results

    Across FEVER, HoVer, and sentence-only FEVEROUS-S, AdMIRaL is competitive with state of the art while using 5 to 10 times less memory than competing dense retrieval systems.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Natural-logic proofs help people predict model decisions correctly more often than using the evidence alone.

    Source: §1 · p. 3

    The benchmarks use homogeneous Wikipedia sources and hyperlink-constructed datasets, and natural logic is limited for reasoning involving time ranges or numbers.

    Source: Limitations · p. 10

Abstract

from arXiv · show

A key component of fact verification is thevevidence retrieval, often from multiple documents. Recent approaches use dense representations and condition the retrieval of each document on the previously retrieved ones. The latter step is performed over all the documents in the collection, requiring storing their dense representations in an index, thus incurring a high memory footprint. An alternative paradigm is retrieve-and-rerank, where documents are retrieved using methods such as BM25, their sentences are reranked, and further documents are retrieved conditioned on these sentences, reducing the memory requirements. However, such approaches can be brittle as they rely on heuristics and assume hyperlinks between documents. We propose a novel retrieve-and-rerank method for multi-hop retrieval, that consists of a retriever that jointly scores documents in the knowledge source and sentences from previously retrieved documents using an autoregressive formulation and is guided by a proof system based on natural logic that dynamically terminates the retrieval process if the evidence is deemed sufficient. This method is competitive with current state-of-the-art methods on FEVER, HoVer and FEVEROUS-S, while using $5$ to $10$ times less memory than competing systems. Evaluation on an adversarial dataset indicates improved stability of our approach compared to commonly deployed threshold-based methods. Finally, the proof system helps humans predict model decisions correctly more often than using the evidence alone.

1 Introduction

Fact verification often requires evidence from multiple documents, while existing multi-hop retrieval methods face memory costs or rely on heuristics and document links. AdMIRaL combines autoregressive retrieval with natural-logic proofs that assess evidence sufficiency.

1 Introduction

  • Multi-hop fact verification requires combining partial evidence from multiple documents, and the claim itself may not lead to the document containing the needed follow-up information.The example requires connecting the award host to a separate document about that person.Source: §1 · pp. 1–2
  • Dense multi-hop retrievers store representations for the full knowledge base, whereas retrieve-and-rerank avoids a dense index but often relies on heuristics and document hyperlinks.Many textual knowledge bases do not have links between documents.Source: §1 · p. 2
  • AdMIRaL jointly scores knowledge-base documents and previously reranked sentences autoregressively, while a natural-logic proof assesses evidence sufficiency and can stop further retrieval.Generating document and sentence identifiers token by token avoids storing dense document representations in an index.Source: §1 · pp. 2–3
  • FEVER document recall and F1 improve by 1.4% and 4.6%, respectively; AdMIRaL is competitive on HoVer and sentence-only FEVEROUS-S while using 5 to 10 times less memory.The authors also report runtime complexity more favorable when scaling to large knowledge bases.Source: §1 · p. 3

2 Related Work

Prior multi-hop retrieval work spans retrieve-and-rerank systems using sparse or entity-based retrieval, dense iterative retrieval, and graph-based question-answering methods. These approaches differ in how they find follow-up evidence and manage retrieval across hops.

2 Related Work

  • Early retrieve-and-rerank systems used sparse or entity-linking retrieval, sentence reranking, and hyperlinks for follow-up documents, typically limiting retrieval to two iterations.Stammbach (2021) down-weighted hyperlinked documents by a fixed factor, while Malon (2021) generated missing evidence sentences and selected candidates by word overlap.Source: §2 · p. 3
  • GENRE achieved state-of-the-art fact-verification document retrieval by autoregressively generating documents without requiring a dense index (De Cao et al., 2021).Stronger document retrievers and more accurate rerankers also improved retrieve-and-rerank performance.Source: §2 · p. 3
  • MDR uses beam search to prune an exponentially growing search space, while Baleen condenses retrieved documents but still scores every knowledge-base document at each hop (Xiong et al., 2021; Khattab et al., 2021).The FEVEROUS shared task drew 12 systems, none of which used a dense retrieval index.Source: §2 · p. 3
  • Graph-based QA retrieval can use reader feedback to determine dynamically whether an answer is sufficient, but fact verification must also handle claims that cannot be verified from the knowledge base.Misleading information in claims makes sufficiency-based stopping more challenging for fact verification.Source: §2 · p. 3

3 AdMIRaL

AdMIRaL extends retrieve-and-rerank with autoregressive document retrieval conditioned on selected sentences and a natural-logic proof system that dynamically assesses evidence sufficiency. Its scoring uses the claim and selected sentences rather than precomputed document representations, while the proof process provides an interpretable basis for deciding whether to continue retrieval.

3 AdMIRaL

  • AdMIRaL iterates retrieve-and-rerank: it retrieves document sets, reranks their sentences, and uses the selected sentences to update document sequences until the hop limit.The number of hops is not known in advance in prior approaches, so they use a dataset upper bound; AdMIRaL instead determines its hop count dynamically.Source: §3 · p. 4

3.1 Autoregressive Document Retrieval

  • The autoregressive retriever scores candidate document sets using selected sentences as a compact approximation of retrieved documents’ claim-relevant information.It generates sentence identifiers and document titles token by token, conditioning on the claim and selected sentences; beam search navigates the vocabulary rather than comparing against every KB document.Source: §3.1 · p. 4
  • Because scoring uses the claim and selected sentences rather than precomputed document representations, AdMIRaL does not need to store dense document representations in an index.Generation is constrained with a prefix tree and dynamically constrained decoding to keep generated sentence and document identifiers valid.Source: §3.1 · pp. 4–5

3.2 Evidence Sufficiency with Natural Logic

  • A natural-logic proof mutates claim spans into evidence spans using equivalence, negation, alternation, or independence operators to assess evidence sufficiency.Cover and entailment operators are excluded because they do not conclusively indicate sufficiency; the method treats them as independence for this purpose.Source: §3.2 · p. 5
  • Evidence is predicted insufficient if any mutation in the generated proof receives the independence operator.Training proofs are generated for both sufficient and insufficient evidence, then their operators are adjusted to match the evidence’s sufficiency label.Source: Figure 3 · p. 5, §3.2 · p. 6

4 Experimental setup

The experiments evaluate multi-hop retrieval on FEVER, HoVer, and the sentence-evidence subset of FEVEROUS. They use different initial retrieval and sentence-reranking setups across datasets.

Datasets

  • FEVER evaluation covers both multi-hop claims and the full dataset, where 87% of claims require a single evidence sentence.The authors report the full dataset because whether a claim needs multi-hop retrieval is unknown in practice.Source: §4 · p. 6
  • HoVer includes two-hop, three-hop, and four-hop claims at 46%, 36%, and 18%, respectively.FEVER and HoVer use introductory Wikipedia sections, whereas FEVEROUS includes entire articles and semi-structured table evidence.Source: §4 · p. 6
  • The FEVEROUS-S evaluation restricts FEVEROUS to claims requiring sentence evidence only, about 41% of its claims.The paper focuses on text retrieval rather than table retrieval.Source: §4 · p. 6

Implementation Details

  • Initial candidates come from GENRE and BM25, then dataset-specific sentence rerankers select the top five sentences for the first hop.The setup reranks the top 10 documents for FEVER and FEVEROUS-S and the top 100 for HoVer; retrieval and proof-generation BART models are trained independently.Source: §4 · p. 6

5 Results

AdMIRaL achieves strong multi-hop retrieval results while using substantially less memory than dense-index systems. Its runtime advantage depends on knowledge-base size, and proof generation limits the runtime benefit of dynamic termination.

5.1 Multi-hop Document Retrieval

  • 34.8 percentage points on FEVER, 16.9 on FEVEROUS-S, and 9.1 on HoVer: AdMIRaL’s 2-hop recall gains over initial retrieval.It has the highest 2-hop recall on all three datasets and the highest overall recall on FEVER and FEVEROUS-S, but trails Baleen on HoVer; F1 improves over MDR by 4.6% on FEVER and over hyperlink retrieval by 14.2% on FEVEROUS-S.Source: Table 2 · p. 7, §5.1 · p. 7

5.2 Efficiency

  • 3.3GB on HoVer, 6.4GB on FEVER, and 20.7GB on FEVEROUS-S: AdMIRaL’s memory footprint, about 10 times less than MDR and 5 times less than Baleen.The footprint comprises the initial BM25 inverted index and a prefix tree of document titles; it is comparable to retrieve-and-rerank approaches.Source: §5.2 · p. 7
  • 2 minutes and 32 seconds versus 290 minutes and 12 seconds: AdMIRaL and Baleen’s respective HoVer index-building times.Retrieval complexity is O(ndyn + |D|) for AdMIRaL, versus O(n|D|) for dense retrievers; its per-hop retrieval depends on vocabulary size, with ndyn ≤ n.Source: §5.2 · p. 7
  • 2.87 seconds on HoVer versus 1.94 seconds for Baleen: AdMIRaL is slower on smaller KBs, while its runtime is nearly unchanged as KB size grows.On a KB twice HoVer’s size, AdMIRaL takes 2.88 seconds while Baleen takes 2.30 seconds; proof generation costs at least as much as autoregressive retrieval, making runtime gains from dynamic termination challenging.Source: §5.2 · pp. 7–8

6 Discussion

The discussion compares autoregressive retriever variants, tests robustness to adversarial claims and changes in the initial retriever, and evaluates Natural Logic sufficiency prediction. AdMIRaL's results favor joint document-sentence scoring and proof-based sufficiency checks, while revealing room to improve sufficiency prediction.

Autoregressive Generation

  • Hyperlink information improves AdMIRaL's recall substantially, yielding a 0.16-percentage-point FEVER multi-hop state-of-the-art improvement.Top-1 has comparable exact-match accuracy but considerably lower recall; Not-joint has competitive recall but lower exact-match accuracy, while Joint-docs performs worst overall.Source: §6 · p. 8, Table 3 · p. 8

Robustness

  • On DeSePtion, AdMIRaL substantially improves over the initial retriever and BM25, while Not-joint performs worse than AdMIRaL despite similar FEVER recall.The authors identify this contrast as evidence of brittleness in statically adding documents by fixed position or threshold.Source: §6 · p. 8, Table 4 · p. 8

Results with different initial retrievers

  • Across initial retrievers, AdMIRaL improves FEVER recall@5 by an average of 33 percentage points, with variance 0.0004.The tested initial retrievers include BM25, KGAT, and Jiang et al. (2021b); KGAT includes gold documents before sentence reranking and was excluded from the main experiments.Source: §6 · p. 8, Table 5 · p. 9

Sufficiency Proof with Natural Logic

  • AdMIRaL's sufficiency check outperforms alternative sufficiency-prediction methods and the fixed-iteration approach, but the oracle's higher precision yields substantially higher retrieval recall@5.The comparison includes always-complete or always-incomplete decisions, a BART classifier, ProofVER, and a lexical-resource NatLog proof.Source: §6 · p. 9, Table 6 · p. 9

7 Human Evaluation of Sufficiency Proofs

The human evaluation tests whether Natural Logic sufficiency proofs help people predict AdMIRaL's decisions. Participants predicted decisions more accurately and faster with proofs than with evidence sentences alone.

Interpretability

  • Proofs indicate where information is missing, letting users consider targeted claim edits or override an erroneous sufficiency decision.The authors describe this as a human-in-the-loop use of the proof-based sufficiency prediction.Source: §7 · p. 9

Human evaluation results

  • 70% of participants' predictions were correct using sufficiency proofs, versus 50% with evidence sentences alone.Annotators predicted system behavior 20% faster using proofs; average time was 51 seconds, falling to 24 seconds after the first five annotations.Source: §7 · p. 9

Evaluation design

  • The evaluation comprised 60 annotations from six subjects, with subjects not seeing both explanations for the same claim.Ten claims were each paired with a proof and a baseline explanation, and each was annotated by three subjects.Source: §7 · p. 9

8 Conclusion

The paper concludes that AdMIRaL combines autoregressive retrieve-and-rerank with Natural Logic proofs that dynamically stop retrieval when evidence is sufficient. It reports competitive retrieval performance with minimal memory footprint, and describes the proofs as interpretable for human involvement in retrieval.

Conclusion

  • AdMIRaL combines autoregressive retrieve-and-rerank with Natural Logic proofs to dynamically terminate retrieval when evidence is deemed sufficient.Source: §8 · p. 9
  • The model achieves competitive retrieval recall and F1 with minimal memory footprint compared with current state-of-the-art retrieval models.Source: §8 · p. 9
  • The authors identify end-to-end use of ProofVER and human-in-the-loop approaches as future research directions.They describe the generated proof as interpretable and as enabling human involvement in the retrieval process.Source: §8 · p. 10

Limitations

The benchmarks and retrieval setting constrain the findings to Wikipedia, sentence evidence, and datasets constructed using hyperlinks. Natural logic also has limited expressiveness for reasoning involving time ranges or numbers.

Limitations

  • The benchmarks use Wikipedia, which is more homogeneous than the news articles, encyclopedias, and scientific documents used by professional factcheckers.This limits how directly the benchmark setting reflects those heterogeneous sources.Source: Limitations · p. 10
  • The retrieval methods focus on unstructured sentence evidence, although recent datasets also include other modalities.Source: Limitations · p. 10
  • Because the datasets were constructed using Wikipedia hyperlinks, the approach appears particularly suited to these benchmarks; the authors know of no large-scale dataset that avoids this annotation choice.Source: Limitations · p. 10
  • Natural logic is interpretable but limited in expressiveness, and is not suited to more complex reasoning involving time ranges or numbers.Source: Limitations · p. 10

Ethics Statement

The authors anticipate using the retrieval system in fact-checking systems, but it does not judge real-world truth and considers Wikipedia as its evidence source. Because Wikipedia can contain errors and noise, they discourage using the system to make absolute statements about claims.

Ethics Statement

  • The authors anticipate that the retrieval system will be used in fact-checking systems.Source: Ethics Statement · p. 10
  • The system retrieves evidence from Wikipedia but does not judge whether a statement is true in the real world.Source: Ethics Statement · p. 10
  • Because Wikipedia has its own mistakes and noise, the authors discourage using the system to make absolute claims or develop truth-tellers.Source: Ethics Statement · p. 10

A Appendix

The appendix details the autoregressive retrieval model and training, implementation settings, additional retrieval results, and human-evaluation participants. It also describes the scope and reporting of the appendix results.

A.1 Autoregressive Document Retrieval

  • BART receives the claim followed by evidence sentences, each preceded by its document title; decoding emits sentence identifiers before the document identifier.The proof output uses braces for claim spans, square brackets for evidence spans, and the following token for the natural-logic operator.Source: §A.1 · pp. 12–13

A.3 Further Results

  • Table 7 reports document-retrieval F1 for 2-hop and overall results; its HoVer comparison uses recall@100 for supported dev claims and excludes Khattab et al.The caption says Khattab et al. results are excluded because F1 computation is unclear and the script is inaccessible.Source: Table 7 · p. 13, §A.3 · p. 13

A.1 Autoregressive Document Retrieval

  • A separate model is trained for each hop using maximum likelihood, with prior gold evidence sentences as input and the remaining gold sentence's document title as the target.Training also samples negative sentences and shuffles the input; when evidence order is unavailable, it generates all possible choices of the input gold sentences.Source: §A.1 · p. 13

A.2 Implementation Details

  • Both retrieval and proof-generation autoregressive models are based on BART and GENRE; experiments used beam sizes of 25 for autoregressive generation and 5 for sufficiency-proof generation.Experiments ran on a machine with a single Quadro RTX 8000 and 64GB RAM.Source: §A.2 · p. 13

A.4 Human Evaluation

  • Human-evaluation participants were computer science or linguistics students without prior natural language inference knowledge; Table 8 lists natural-logic operators and their paraphrases.Source: §A.4 · p. 13, Table 8 · p. 13

Related papers

Loading 2212.05276v1…