PaperlayerView exact revision on arXiv

Source-linked AI summary

Generative Multi-hop Retrieval

Hyunji Lee, Sohee Yang, Hanseok Oh, Minjoon Seo

arXiv:2204.13596v3cs.IR

TL;DR

Bi-encoder retrieval can lose information as multi-hop queries grow and is vulnerable to error propagation. GMR retrieves by generating full target text sequences, and the paper reports comparable or higher performance than bi-encoders across five datasets. The authors conclude that generative retrieval merits further exploration for multi-hop tasks.

  • Problem

    In multi-hop retrieval, appending previously retrieved items lengthens the query, increasing the information bottleneck of its fixed-size bi-encoder embedding.

    Source: §1 · p. 1

  • Method

    GMR is an encoder-decoder model that generates full target text sequences with constrained decoding, with LM and multi-hop memorization methods intended to help memorize the corpus.

    Source: §1 · pp. 1–2, §3 · p. 4

  • Results

    GMR achieves higher or comparable multi-hop retrieval performance than bi-encoder models across five datasets, with higher fixed-setting top-5 recall and dynamic-setting F1 reported across four datasets.

    Source: §5.1 · p. 6, §6 · p. 9

  • Takeaways & Limitations

    The authors conclude that generative retrieval is highly competitive with bi-encoders for multi-hop retrieval and deserves further exploration.

    Source: §6 · p. 9

    GMR is not as good as MDR on HotpotQA, and early stopping improves inference speed but degrades performance.

    Source: Limitations · p. 9

Abstract

from arXiv · show

A common practice for text retrieval is to use an encoder to map the documents and the query to a common vector space and perform a nearest neighbor search (NNS); multi-hop retrieval also often adopts the same paradigm, usually with a modification of iteratively reformulating the query vector so that it can retrieve different documents at each hop. However, such a bi-encoder approach has limitations in multi-hop settings; (1) the reformulated query gets longer as the number of hops increases, which further tightens the embedding bottleneck of the query vector, and (2) it is prone to error propagation. In this paper, we focus on alleviating these limitations in multi-hop settings by formulating the problem in a fully generative way. We propose an encoder-decoder model that performs multi-hop retrieval by simply generating the entire text sequences of the retrieval targets, which means the query and the documents interact in the language model's parametric space rather than L2 or inner product space as in the bi-encoder approach. Our approach, Generative Multi-hop Retrieval(GMR), consistently achieves comparable or higher performance than bi-encoder models in five datasets while demonstrating superior GPU memory and storage footprint.

1 Introduction

Multi-hop retrieval must combine multiple documents when one document cannot answer a query, but bi-encoder query embeddings face an information bottleneck as retrieved text lengthens. GMR instead generates target text sequences, and the paper reports comparable or higher performance than bi-encoders across five datasets.

1 Introduction

  • Bi-encoder retrieval becomes vulnerable to information loss as previously retrieved items lengthen the query that must fit in a fixed-size embedding.The introduction also identifies error propagation as a multi-hop limitation of bi-encoders.Source: §1 · pp. 1–2
  • GMR is an encoder-decoder model that retrieves target sequences by generating their full text with constrained decoding.Unlike prior generative retrieval that produces entity or document identifiers, GMR produces the target paragraph text.Source: §1 · pp. 1–2
  • The paper proposes LM and multi-hop memorization to help GMR memorize the target corpus.The introduction reports that multi-hop memorization improves GMR performance.Source: §1 · p. 2
  • GMR performs higher or comparably to bi-encoder models on five datasets and is especially strong in real-world-like multi-hop settings and datasets with low unseen rates.The paper also reports that multi-hop memorization improves GMR performance.Source: §1 · p. 2
  • The authors suggest generative retrieval as a potential practical alternative to bi-encoders for multi-hop as well as no-hop retrieval.This suggestion is framed in light of reported performance and storage efficiency.Source: §1 · p. 2

2 Related Work

Prior multi-hop retrieval work has used metadata or extended bi-encoder architectures, while generative retrieval work has largely focused on no-hop tasks. This paper explores generating full retrieval text as an alternative for multi-hop retrieval.

Multi-hop Retrieval

Generative Retrieval

  • Earlier generative retrieval work addresses entity or no-hop retrieval, including DSI's structured identifiers and SEAL's generated n-grams [Cao et al., 2021; Tay et al., 2022; Bevilacqua et al., 2022].SEAL uses an FM index, and the passage reports that it outperformed DPR and GAR on NQ and KILT [Karpukhin et al., 2020; Mao et al., 2021].Source: §2 · p. 3
  • The paper compares full retrieval-sequence generation with a reimplementation of DSI extended to multi-hop retrieval.The comparison is framed as a test of explicitly generating the entire retrieval sequence.Source: §2 · p. 3

3 Generative Multi-hop Retrieval

GMR retrieves a set of corpus sequences over multiple hops by generating target text conditioned on the query and previously retrieved sequences. Corpus memorization methods are proposed to improve sequence generation and retrieval.

3 Generative Multi-hop Retrieval

  • The paper targets settings where inference-time hop count and correct retrieval order are unknown, and the oracle number of hops varies widely.Multi-hop retrieval appends previously retrieved sequences to the query to model relationships among targets.Source: §3 · p. 3
  • SEAL and GENRE are noted as generative retrieval methods evaluated on multi-hop QA datasets in a no-hop retrieval setting.Source: §3 · p. 3
  • In a bi-encoder, each hop retrieves a sequence by encoding the query plus prior retrieved sequences into a fixed-size query vector.The authors identify the growing augmented query as a burden on the encoder and a source of bottleneck and error-propagation concerns.Source: §3 · p. 3
  • GMR instead generates the target sequence at each hop with an encoder-decoder model, conditioning on the query and previously retrieved sequences.The approach interacts through the model's parametric space rather than only L2 or inner-product space.Source: §3 · p. 3
  • Constrained decoding uses a corpus prefix tree to mask invalid continuations and keep generated sequences within the target corpus.The model generates tokens left to right while conditioning on the query, prior retrieved sequences, and current-hop tokens.Source: §3 · p. 4
  • LM memorization trains on corpus text with a language-model objective before retrieval training, exposing the model to sequence endings in advance.The LM task predicts later tokens from an initial text prefix.Source: §3 · p. 4
  • Multi-hop memorization addresses LM memorization's unconditional objective by training on pseudo-multi-hop queries and target sequences.The method generates pseudo-queries from sampled target sequences and trains the memorization and retrieval data together.Source: §3 · p. 4

4 Experimental Setup

The experiments define fixed and dynamic retrieval settings, use five varied datasets, compare with bi-encoder baselines, and evaluate with metrics tailored to each setting and task.

4.1 Fixed and Dynamic Multi-hop Retrieval

  • Fixed retrieval continues through the maximum hop count, whereas dynamic retrieval lets the model stop early by generating DONE.The dynamic setting is presented as more applicable when the required number of items is not known in advance.Source: §4.1 · p. 5

4.2 Datasets

  • The experiments use HotpotQA, EntailmentBank, StrategyQA, Explagraphs-Open, and RuleTaker-Open, with the latter two reformulated as retrieval tasks.EntailmentBank Task3 retrieves evidence leaf nodes; Explagraphs-Open uses subject-relation-object paths, and RuleTaker-Open uses graph sentence nodes.Source: §4.2 · p. 5

4.3 Bi-Encoder Retrieval Models

  • HotpotQA uses MDR as its bi-encoder baseline, while the other datasets use ST5, a T5-based encoder-decoder baseline.The models are trained and inferred in fixed and dynamic settings.Source: §4.3 · p. 5

4.4 Evaluation Metric

  • Fixed-setting evaluation uses HotpotQA's MDR metric or recall, while dynamic evaluation uses F1@k; RT-Open additionally measures graph-construction success.Dynamic F1 is measured with a maximum of k retrieved sequences.Source: §4.4 · p. 5

5 Experimental Results

GMR generally outperforms bi-encoder baselines in fixed and dynamic multi-hop retrieval, while analysis finds bi-encoder performance degrades with more hops and is more vulnerable to error propagation.

5.1 Results

  • Across four datasets, GMR has higher fixed-setting recall and dynamic-setting F1 than bi-encoders; dynamic evaluation also outperforms fixed evaluation for both model types.Source: Table 1 · p. 6, §5.1 · p. 6
  • On HotpotQA, GMR is comparable to MDR- but scores below MDR; on RT-Open, GMR and GMRM exceed BE success rate by 300% and 385%, respectively.Source: §5.1 · p. 6, Table 2 · p. 6
  • At equal parameter count, GMR reduces storage by 69.7% and GPU memory by 79.5% versus ST5; optimized early stopping cuts HotpotQA inference time 40%, while unoptimized decoding is 24.6 times slower.Source: §5.1 · p. 6
  • GMR outperforms both DSI* models on fixed-setting R@5 across all three datasets, supporting full-sequence generation over document-id retrieval.Source: Table 3 · p. 7, §5.1 · p. 7

5.2 Analysis

  • With gold prior-hop targets supplied, ST5's Hop-R@5oracle deteriorates more than GMR's as hops increase; on HotpotQA, BE's worst error case is a missed second hop.Source: Figure 2 · p. 7, §5.2 · p. 7
  • Average error-propagation rates are 28.2% and 72.5% for BE versus 20.7% and 45% for GMR on minor and major tasks, respectively.Source: §5.2 · p. 8, Table 4 · p. 8
  • GMR's relative F1@20 improvement is 305.4% on low-unseen-rate datasets versus 145.6% on high-unseen-rate datasets; multi-hop memorization reduces unseen rates by 40.4% on StrategyQA and 60% on EG-Open.Source: §5.2 · p. 8
  • LM memorization helps consistently on StrategyQA and RT-Open but not other datasets; multi-hop memorization adds pseudo-multi-hop data and beats GMR and GMRL, though it is difficult to apply as-is on low-unseen-rate datasets.Source: §5.2 · p. 8

6 Conclusion

The paper identifies bottleneck and error-propagation limitations in bi-encoder multi-hop retrieval and presents GMR, which generates target sequences. GMR achieves higher or comparable performance across five datasets, with corpus memorization methods intended to further improve it.

6 Conclusion

  • Bi-encoder bottleneck problems become more severe as hop count increases, and bi-encoders are more susceptible to error propagation.Source: §6 · p. 8
  • GMR achieves higher or comparable performance on multi-hop retrieval tasks across five datasets.The authors describe the approach as highly competitive with bi-encoder methods.Source: §6 · p. 9
  • GMR is an encoder-decoder model that retrieves by generating entire target sequences with constrained decoding.The paper also introduces LM memorization and multi-hop memorization to further improve GMR’s performance.Source: §6 · pp. 8–9

Limitations

GMR does not match the well-designed MDR bi-encoder on HotpotQA. The authors suggest task characteristics and early stopping’s speed-performance trade-off as relevant limitations.

Limitations

  • GMR is not as good as the well-designed bi-encoder MDR on HotpotQA.Source: Limitations · p. 9
  • The authors suspect GMR may be more advantageous with larger, dynamic hop counts, whereas HotpotQA has exactly two hops.Source: Limitations · p. 9
  • Early stopping improves GMR inference speed but degrades performance because it cannot calculate the total beam score over all target-sequence tokens.The authors state that more research is needed to achieve both speed and performance.Source: Limitations · p. 9

A Generative Multi-hop Retrieval

The section describes corpus memorization and inference procedures for GMR. Multi-hop memorization adds generated pseudo-multi-hop data, with filtering and dataset-specific choices shaping its application.

LM Memorization

  • LM memorization generates the object from a subject and relation for path retrieval, or the remainder of a sentence from its first 70% for paragraph retrieval.Source: A Generative Multi-hop Retrieval · p. 10

Multi-Hop Memorization

  • Multi-hop memorization trains on generated pseudo-queries and pseudo-target sequences alongside the original query-target training data.Pseudo-target sequences are constructed to share important words or phrases, such as entities or subjects, so their elements are interconnected.Source: A Generative Multi-hop Retrieval · pp. 10–11
  • For StrategyQA, the method extracts entities and removes sentences with no entities or more than four; for EG-Open, it treats path subjects and objects as important words.The authors report that removing sentences with many entities is critical to StrategyQA performance because such sentences may be irrelevant despite sharing an entity.Source: A Generative Multi-hop Retrieval · p. 11
  • Pseudo-target lists and queries are filtered, including removal of queries that stop before the end token and keeping pseudo-target list sizes within the original range.The sampling process also removes pseudo-target sets containing all elements of an original target sequence.Source: A Generative Multi-hop Retrieval · p. 11
  • Adding pseudo-multi-hop data reduces the unseen rate by 40.4% on StrategyQA and 60% on EG-Open, while increasing performance on both.The authors say this method is difficult to apply to datasets with low unseen rates and leave effective pseudo-data generation for them to future work.Source: A Generative Multi-hop Retrieval · p. 11

Inference

  • Dynamic conditional retrieval repeats retrieval while tracking the iteration step and, if the retriever returns null, fills the retrieved-sequence set with null elements to length k.The procedure initializes the retrieved-sequence set as empty and the iteration step at 1.Source: A Generative Multi-hop Retrieval · p. 11

B Experimental Setup

The experiments distinguish fixed-hop retrieval, which uses an oracle hop count, from dynamic retrieval, which predicts when to stop. The setup fixes the maximum retrieval steps at five and trains dynamic retrieval to stop by retrieving a null element.

B.1 Fixed and Dynamic Multi-hop Retrieval

  • The fixed setting assumes an oracle hop count and retrieves up to k; this paper sets k=5 because it is near the datasets’ average.For an oracle set with three items, training examples successively condition on previously retrieved items.Source: §B.1 · pp. 11–12
  • Table 5 presents pseudo-multi-hop data examples, with the top two examples from StrategyQA and the bottom two from EG-Open.Source: Table 5 · p. 12
  • Dynamic retrieval predicts the stopping point, addressing unknown query-specific hop counts and avoiding unnecessary retrievals that can introduce hard negatives.Training appends a null target after the oracle sequences; inference stops when the retriever returns it.Source: §B.1 · pp. 12–13

B.2.1 Datasets Details

The experimental setup evaluates retrieval across varied reasoning datasets and describes the construction of RuleTaker-Open, the bi-encoder baseline, and GMR training. Dynamic training yields higher retrieval-sequence F1 than fixed training in the reported settings.

B.2.1 Datasets Details

  • The datasets cover multi-hop question answering, reasoning-tree leaf retrieval, implicit-strategy evidence retrieval, open-domain reasoning graphs, and open-domain rule-based graph construction.HotpotQA uses two Wikipedia pages; EntailBank Task3 retrieves leaf nodes, while the described datasets also include StrategyQA, EG-Open, and RT-Open.Source: §B.2.1 · pp. 13–14

B.2.2 Datasets Examples

B.3 Details of RuleTaker-Open (RT-Open)

  • RT-Open uses facts and rules from RuleTaker D5, with 1,621 unique queries split into 1,300/121/200; graphs with fewer than two or more than ten nodes are excluded.The setup adds DONE for dynamic stopping.Source: §B.3 · p. 14
  • RT-Open evaluates graph validity using node-count, start-node, end-node, and missing-edge checks, with missing edges checked in prediction order.The paper introduces this rule-based evaluation because queries can have multiple possible answer graphs.Source: §B.3 · pp. 14–15

B.4 Bi-Encoder Retrieval Models

  • The bi-encoder baseline uses ST5 with the same parameter count as GMR, T5 encoder inputs, and the first decoder output as the sentence embedding.Similarity is computed by inner product.Source: §B.4 · pp. 15–16

B.5 Details

  • Both models start from the 770-million-parameter T5-large checkpoint and use the same hyperparameters for fair comparison.LM memorization exposes GMR to the retrieval corpus before retrieval; multi-hop memorization trains a generator on concatenated retrieval sequences to produce pseudo-multi-hop queries.Source: §B.5 · p. 16
  • Increasing LM-memorization epochs does not always improve performance; the authors attribute this to catastrophic forgetting and use the epoch-3 checkpoint for retrieval.GMRM uses both the original and generated training data during retrieval.Source: §B.5 · p. 16

C.1.1 Fixed vs. Dynamic Multi-Hop Settings

  • Dynamic-trained models achieve higher retrieval-sequence F1 than fixed-trained models for both approaches at maximum retrieval steps k=5, 10, and 20.Table 9 reports test-set F1@k.Source: §C.1.1 · p. 16

C.1.2 RT-Open Results

GMR’s storage reduction varies with retrieval-unit length and corpus characteristics, while dynamic training improves retrieval-sequence F1 over fixed training. The RT-Open examples show how missing and leftover nodes mark graph-construction failures.

C.1.2 RT-Open Results

  • Red nodes mark missing graph nodes and blue nodes mark leftover nodes; either indicates failure to construct the reasoning graph.The examples include success and missing-edge failure cases.Source: §C.1.2 · pp. 16–17, Figure 3 · p. 17
  • On the test set, models trained in the dynamic multi-hop retrieval setting consistently achieve higher retrieval-sequence F1 scores than models trained in the fixed setting, measured as F1@k with maximum retrieval step k.Source: Table 9 · p. 17

C.1.3 Storage Footprint

  • 73.49% average reduction in total memory usage is reported for GMR compared with the bi-encoder model.Table 10 compares MDR, GMR, and GMR with early stopping; the reduction is greater for shorter, similar-prefix items and smaller for paragraph-level HotpotQA.Source: Table 10 · p. 17, §C.1.3 · p. 17

C.1.4 DSI

The DSI comparison reproduces DSI on NQ-10k and reports differing outcomes by identifier method. The authors also note that DSI’s recall degrades as corpus size increases, suggesting a possible scaling difficulty relative to GMR.

C.1.4 DSI

  • DSI* reaches nearly twice DSI’s performance on Hits@1 and Hits@10 with Atomic Docid, but about 80% of DSI’s performance on both metrics with Naive String Docid.DSI* is the authors’ reproduction on NQ-10k; the reported comparison is subject to possible differences between reproduced and original datasets.Source: §C.1.4 · p. 17, Table 11 · p. 18
  • DSI has low recall on StrategyQA, whose corpus is four times larger than those of EG-Open and EntailBank; the DSI paper also reports degradation from NQ-10k to NQ-320k.Source: §C.1.4 · pp. 17–18
  • The authors infer that expanding DSI to larger corpora may be difficult, unlike GMR.Source: §C.1.4 · p. 18

C.2.1 Manual Analysis on HotpotQA

Manual comparison of GMR and MDR on HotpotQA identifies distinct error patterns, including frequent MDR second-hop misses and GMR errors when the first-hop item is implicit. Across three datasets, bi-encoder hop-R@5 degrades as embedding size shrinks and, after a threshold, as hop count increases.

C.2.1 Manual Analysis on HotpotQA

  • In 30 sampled cases where one model succeeded and the other failed, MDR often missed the second hop, while GMR struggled when the first-hop item was implicit.GMR tended to retrieve correctly when the first-hop item was explicit; the authors suggest direct input-output cross-encoding may avoid information loss and note its higher score on comparison questions than MDR.Source: §C.2.1 · pp. 18–19
  • The manual analysis groups retrieval errors into implicit first-hop items, attention to irrelevant query details, incorrect title detail, and failure to retrieve the second hop.The title example contrasts “Do you Love Me (Not That I Can Dance)” with “Do you Love Me (2NE1 song).”Source: §C.2.1 · p. 19
  • For bridge questions, MDR was more often wrong in the second and fourth error cases (1.3 and 2.2 times), while GMR was more often wrong in the first and third cases (6 and 2.8 times).Parenthetical values are error-rate ratios compared with the other model.Source: §C.2.1 · p. 19

C.2.2 BottleNeck Problem in Bi-Encoder Models

  • Across EntailBank, EG-Open, and StrategyQA, bi-encoder hop-R@5 declines as embedding size shrinks and, after a threshold, as hop count grows.Figure 7 plots hop-R@5 against hop count for different embedding dimensions.Source: §C.2.2 · p. 19, Figure 7 · p. 19

Related papers

Loading 2204.13596v3…