Source-linked AI summary
Autoregressive Search Engines: Generating Substrings as Document Identifiers
Michele Bevilacqua, Giuseppe Ottaviano, Patrick Lewis, Wen-tau Yih, Sebastian Riedel, Fabio Petroni
TL;DR
Knowledge-intensive language tasks need both answers and supporting evidence, yet autoregressive models are difficult to use reliably for retrieval. SEAL addresses this by generating corpus ngrams with an autoregressive model and mapping them through an FM-Index. It improves passage-level retrieval on KILT by more than 10 average points, while using substantially less memory than competing approaches.
Problem
Knowledge-intensive language tasks require systems to generate correct answers and retrieve supporting evidence from a corpus, while direct autoregressive evidence generation can hallucinate.
Method
SEAL combines an autoregressive language model with an FM-Index, using all ngrams occurring in documents as identifiers and constraining generation to valid corpus substrings.
Results
SEAL improves average passage-level R-precision on KILT by more than 10 points over DPR and establishes new downstream state-of-the-art results on 4 of 7 datasets.
Takeaways & Limitations
SEAL competes with or outperforms established retrieval systems while using a substantially smaller memory footprint.
Takeaways & Limitations
The experiments use a model of approximately 400M parameters, and the potential of larger autoregressive models remains unexplored.
Abstract
from arXiv · showhide
Knowledge-intensive language tasks require NLP systems to both provide the correct answer and retrieve supporting evidence for it in a given corpus. Autoregressive language models are emerging as the de-facto standard for generating answers, with newer and more powerful systems emerging at an astonishing pace. In this paper we argue that all this (and future) progress can be directly applied to the retrieval problem with minimal intervention to the models' architecture. Previous work has explored ways to partition the search space into hierarchical structures and retrieve documents by autoregressively generating their unique identifier. In this work we propose an alternative that doesn't force any structure in the search space: using all ngrams in a passage as its possible identifiers. This setup allows us to use an autoregressive model to generate and score distinctive ngrams, that are then mapped to full passages through an efficient data structure. Empirically, we show this not only outperforms prior autoregressive approaches but also leads to an average improvement of at least 10 points over more established retrieval solutions for passage-level retrieval on the KILT benchmark, establishing new state-of-the-art downstream performance on some datasets, while using a considerably lighter memory footprint than competing systems. Code and pre-trained models at https://github.com/facebookresearch/SEAL.
1 Introduction
Knowledge-intensive tasks require systems to retrieve supporting passages as well as generate answers, but transferring autoregressive language-model capabilities to reliable retrieval is difficult. SEAL uses corpus ngrams as unstructured identifiers and combines autoregressive generation with an FM-Index, achieving strong retrieval performance with substantially lower memory use.
- Knowledge-intensive tasks such as open-domain question answering and fact checking require surfacing knowledge from large corpora.
- Autoregressive models are difficult to transfer to retrieval because direct evidence generation can hallucinate, while query expansion does not fully exploit autoregressive modeling.
- SEAL uses all ngrams occurring in documents as identifiers instead of imposing hierarchical search-space structure.
- SEAL combines BART with an FM-Index to constrain generations to valid corpus ngrams and retrieve documents containing them.The system can generate spans from any corpus position without explicitly encoding every substring.
- SEAL matches or outperforms recent retrieval systems on Natural Questions with a memory footprint approximately 2 to 7 times smaller.
- More than 10 points of average passage-level retrieval improvement on KILT supports new downstream state-of-the-art results on multiple datasets.
2 Related Work
Related approaches use document identifiers, term weighting, expansion, likelihood modeling, or external search systems for retrieval. SEAL instead uses corpus string matches and a white-box index to determine both generated ngrams and retrieval.
- Document identifiers such as Wikipedia titles or hierarchical cluster paths make autoregressive retrieval targets easier to generate and constrain.
- Titles identify articles rather than passages, limiting their suitability for passage-level retrieval.
- String-matching retrieval commonly uses inverted indexes and term-weighting schemes under a bag-of-words assumption.
- Document and query expansion augment stored documents or queries with generated terms, answers, sentences, or titles.
- Query likelihood models score passages using P(q|p), whereas SEAL models ngram likelihood given the query as P(n|q).
- Unlike systems that generate queries for black-box web search, SEAL uses a white-box index that determines generated ngrams and the search process.
3 Background
Retrieval returns an ordered document list for a query, with ngrams representing contiguous token spans and corpus frequency counting their occurrences. SEAL uses the FM-Index because it supports compressed substring lookup, constrained continuation, and document matching without corpus-sized query costs.
- Retrieval returns an ordered list of corpus documents given a text query.
- An ngram is a span of tokens in a text, and a unigram is an ngram of size one.
- F(n, R) denotes an ngram’s total number of occurrences in the retrieval corpus.
- The FM-Index is a compressed suffix array that supports substring identification, document matching, and constrained generation without separately storing the original text.
- FM-Index space requirements are linear in corpus size, and counting an ngram takes O(|n|log|V|), independently of corpus size.
- The Burrows-Wheeler Transform sorts string rotations into a matrix whose last column is the transformed string.
- The FM-Index stores the first column as runs and the BWT last column in a Wavelet Tree, then locates strings by iteratively narrowing row ranges backwards.
4 Method
SEAL retrieves documents by generating corpus-attested ngrams and ranking the documents where they occur. Its method combines constrained autoregressive decoding, FM-index statistics, and intersective aggregation across multiple ngrams.
- Autoregressive Retrieval: The FM-index efficiently maps generated ngrams to matching documents, which are ranked using the ngrams’ scores.The pipeline generates ngrams, finds their corpus occurrences, and returns the documents containing them.
- Autoregressive Retrieval: SEAL generates query-conditioned ngrams with constrained beam search, masking continuations absent from the FM-index.The FM-index ensures every generated ngram occurs at least once in the retrieval corpus.
- Factoring in FM-index frequencies: LM+FM scoring combines autoregressive probabilities with normalized ngram frequencies to promote model-likely, corpus-distinctive ngrams.This formulation also addresses the monotonic probability decrease associated with longer ngrams.
- An Intersective Scoring for Multiple Ngrams: Intersective scoring aggregates weighted contributions from multiple non-overlapping generated ngrams within each document.The method addresses ties between documents sharing the same highest-scoring ngram and captures separated salient information.
- An Intersective Scoring for Multiple Ngrams: A coverage weight reduces the contribution of ngrams whose tokens overlap with higher-scoring ngrams, limiting overscoring of repetitive documents.The coverage weight depends on how many ngram tokens are absent from the higher-scoring ngrams’ coverage set.
5 Experimental Setting
The evaluation covers retrieval and downstream answer generation across Natural Questions and KILT, using passage-level and page-level settings with task-specific metrics. SEAL is compared with established and autoregressive baselines under a BART-based training and indexing setup.
- Evaluation Protocol: The experiments evaluate English knowledge-intensive tasks through both retrieval quality against ground truth and downstream answer generation by a trained reader.Retrieved documents are passed to a reader that generates task-specific answers.
- Datasets: Natural Questions includes a full Wikipedia corpus of around 21M 100-token passages and a restricted NQ320k corpus of ground-truth documents.NQ uses accuracy@k, while NQ320k uses hits@k.
- Datasets: KILT combines question answering, fact checking, dialogue, slot filling, and entity linking over a unified Wikipedia corpus, evaluated with passage-level R-precision.The corpus is rechunked into around 36M passages of 100 tokens, excluding entity linking and ELI5 because training ground-truth passages are unavailable.
- SEAL Configuration: BART large is fine-tuned to generate 10-token ngrams sampled from ground-truth documents, with query-overlapping ngrams favored and document titles added.Training also includes unsupervised examples to expose the model to more possible evidence pieces.
- SEAL Configuration: The FM-index encodes title–passage token sequences and provides a compact retrieval index; Table 1 reports language-model and index sizes for Natural Questions.SEAL’s index is reported as more than seven times lighter than DPR’s document embeddings and about 1.5 times smaller than uncompressed plain text.
- Baselines and Reporting: SEAL is compared with BM25, DPR, GAR, DSI-BART, GENRE, and other published or publicly released systems, with downstream results generally using a FiD reader.Inference uses constrained decoding for 10 timesteps with beam size 15, while Tables 2–4 report NQ320k, NQ, and KILT results.
6 Results
SEAL performs strongly across Natural Questions and KILT, with intersective scoring improving retrieval and downstream results. Its qualitative behavior shows both query-preserving and diverse ngram generation, while constrained decoding offers modest benefits and inference remains slower than some baselines.
- NQ320k: SEAL outperforms BM25 and DSI-BART in NQ320k hits@10 across all formulations, with LM+FM scoring exceeding GENRE.NQ320k evaluates page-level retrieval, the setting targeted by GENRE.
- Natural Questions: 3.5 points better than GAR on average, SEAL achieves the highest performance for unseen question-answer pairs in Natural Questions.The no-overlap split contains question-answer pairs never seen during training.
- KILT: More than 10 points higher than DPR in average passage-level R-precision, SEAL also establishes state-of-the-art downstream results on 4 of 7 KILT datasets.FiD using passages retrieved by intersective SEAL achieves the downstream results.
- Speed and constrained decoding: 16 minutes with beam size 5 and 35 minutes with beam size 15, intersective retrieval is slower than GAR and comparable to DPR in the reported setup.These runtimes are measured on one GPU for the Natural Questions test set.
- Ablation studies: Larger beams generally improve performance, but gains diminish or slightly reverse from beam size 10 to 15; removing constrained decoding slightly lowers results.The ablation is conducted on Natural Questions using accuracy@k.
- Qualitative Analysis: SEAL generates query-preserving and lexically diverse ngrams, helping address vocabulary mismatch in the earthquake-prediction example.Examples include “earthquakes can be predicted,” “used to predict earthquakes,” and related terms such as seism- and forecast.
7 Discussion
SEAL may extend beyond information retrieval because its constrained generation can enforce substrings from trusted sources. The paper also identifies larger models, very large corpora, and dynamic indexing as future scaling directions.
- Discussion: SEAL could enforce generated substrings from a whitelist of trusted sources, suggesting applications outside information retrieval.This possibility is presented as an example application rather than an evaluated result.
- Discussion: The experiments use a roughly 400M-parameter BART model, while larger models are expected to potentially improve performance without changing index size or lookup cost.The paper states that larger models could considerably improve performance and gives lookup cost O(|n|log|V|).
- Discussion: Scaling to very large corpora and updating the FM-index dynamically remain future-work challenges, despite SEAL’s light memory footprint.The paper suggests more efficient large-corpus indexing and dynamic FM-index variants without re-indexing.
8 Conclusion
SEAL combines an autoregressive language model with a compressed full-text substring index for retrieval. It improves passage-level KILT performance and achieves state-of-the-art downstream results on 4 of 7 datasets, while larger autoregressive models remain a direction for future exploration.
- SEAL combines an autoregressive language model with a compressed full-text substring index to retrieve corpus documents through existing ngrams.
- More than 10 points in average passage-level R-precision on KILT and state-of-the-art downstream performance on 4 of 7 datasets summarize the reported gains.
- The authors identify exploring existing or future larger autoregressive models as a potential direction beyond the current results.
A Additional KILT results
On KILT's test set, SEAL performs comparably to or better than other page-level retrieval systems on most datasets. Its KILT-scores reach state-of-the-art on 4 of 7 datasets.
- SEAL's page-level retrieval results on the KILT test set are comparable to or better than other systems on most datasets.
- SEAL's page-level results are within two points of GENRE's average performance, although GENRE directly targets the page-level setting.
- State-of-the-art KILT-scores are achieved on 4 out of 7 datasets.
B Impact of unsupervised examples
SEAL is trained with supervised and unsupervised examples, and ablations on Natural Questions assess their contributions. Adding unsupervised examples improves purely supervised training by one point in A@100, while unsupervised-only training remains slightly below BM25.
- SEAL uses both supervised and unsupervised examples, with ablations evaluating the importance of each training source.
- One point in A@100 is gained by adding unsupervised examples to purely supervised training.
- Training only on unsupervised examples produces performance slightly below BM25's.