  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.
