Generative Multi-hop Retrieval (2022)

Abstract: 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.

## introduction finding the relevant knowledge from a massive collection of information is often formulated as a text retrieval problem. a large portion of the text retrieval literature focuses on finding the single most relevant paragraph or document (i.e., no hop) to the given query @xcite . when we cannot answer a query with a single document, the task is often formulated as a multi-hop retrieval problem, where one needs to retrieve multiple documents that together provide 1 https://github.com/amy-hyunji/generative-multihopretrieval sufficient evidence to answer the query @xcite @xcite . for example, to answer the question "where did the form of music played by die rhöner säuwäntzt originate?" (figure 1 ), we first need to retrieve the form of music played by die rhöner säuwäntzt and then where the form originated from. no-hop and multi-hop retrieval tasks are often approached by encoding both the query and retrieval sequences to a common vector space and then finding the sequence whose embedding is closest to the query. this bi-encoder approach for retrieval is often considered as a de facto standard; heavy computations such as extracting the dense embeddings of the items in the corpus can be done offline, and one can search over a large number of items with low latency through the nearest neighbor search (nns) or maximum inner product search (mips) @xcite @xcite . while such a biencoder approach performs well on many retrieval tasks, it has also shown to suffer from information loss when encoding a long query or document into a fixed-size embedding @xcite . the problem becomes even more critical in multi-hop retrieval as previously retrieved items are appended to the query while iterating through multiple hops. the augmented query gets longer as the number of hops increases; therefore, the query embedding gradually becomes incapable of containing the entire information. in this paper, we argue that a fully generative approach to multi-hop retrieval may be the solution; it overcomes the bottleneck problem by interacting in the whole parametric space of the model trained on the target corpus during the retrieval process, rather than operating on l2 or inner product space as in bi-encoder approach (figure 1 ). we propose generative multi-hop retrieval (gmr), an encoder-decoder model that attempts to memorize the entire target corpus in a generative manin the first hop retrieval of gmr, to generate the second token, rhöner, it finds the potential next tokens @xcite ) by searching through the prefix tree with the previously generated tokens. we mask out tokens that are not in the potential next tokens and find the token with the maximum score from unmasked tokens, which in this example is säuwäntzt. finally, when it retrieves @xmath0, the generation ends, and the generated output is the retrieval sequence of the query. in the second hop retrieval, the concatenation of the query and the previously retrieved sequence is the input query for both approaches. given that generative retrieval shows high performance with high storage efficiency in multi-hop retrieval task compared to the traditional bi-encoder approach, we suggest that generative retrieval has the potential to be a practical alternative for not only the no-hop text retrieval tasks, as shown in @xcite ; @xcite , but also for multi-hop retrieval tasks as explored in this work. ## related work multi-hop retrieval multi-hop retrieval, which answers a query by integrating multiple documents, is often necessary to solve complex queries; it is an active area of research due to its importance. there has been a line of previous works in multihop retrieval with non-textual metadata such as knowledge bases, wikipedia hyperlinks, or entity linking which leverage such metadata to solve the tasks @xcite @xcite . however, they are not expandable to cases where such metadata does not exist. another line of research focuses on expanding the bi-encoder architecture which has shown high performance on no-hop retrieval to multi-hop retrieval @xcite . while such methods have shown good performance, previous studies @xcite show that bi-encoder approach suffers from information loss when condensing text into a fixedsize vector. since the input text gets longer as the number of hops increases in multi-hop retrieval, it is highly likely for the bi-encoder to fall into the bottleneck problem when the number of hops is large. therefore, to overcome such limitations, it is worth exploring the changes in the fundamental approach; our work suggests that a generative method can be an effective alternative to the bi-encoder approach for multi-hop retrieval tasks. generative retrieval cao et al. (2021) first propose a generative retrieval model, which achieves comparable or higher performances on entity retrieval tasks compared to bi-encoder models. moreover, concurrent works dsi @xcite and seal @xcite show generative retrieval methods in no-hop retrieval settings. dsi (differentiable search engine) generates structured identifiers of each corpus and shows higher performance than the bi-encoder approach in the nq dataset. seal (search engines with autoregressive lms) retrieves an item (paragraph or document) by finding an item containing generated ngram using fm index. it tests on nq and kilt benchmarks and shows that the generative retrieval model can even outperform well-designed bi-encoder models such as dpr @xcite and gar @xcite foot_0 . to see the effectiveness of explicitly generating the entire retrieval sequence, we compare gmr with our reimplementation of dsi foot_1 which we expand to a multi-hop retrieval setting for fair comparison. ## generative multi-hop retrieval multi-hop retrieval is a task of retrieving a set of sequences (e.g., sentences or paragraphs) from a target corpus d given a query x. it is often approached by iterating through multiple hops where the previously retrieved sequences are appended to the query and form an augmented query to model the relationship between the target sequences @xcite @xcite . in this paper, we focus on multi-hop retrieval tasks that resemble a real-world scenario: the oracle number of hops and the correct order of retrieval sequences are not given for each query at the inference time, and the number of oracle hops varies in a wide range. canonical text retrieval can be formulated as retrieving a sequence d ŷ = arg max @xmath1, where x is the query, d is a retrieval sequence in the target corpus d, and ŷ is the index of retrieved sequence in d. the retrieval is considered successful if d ŷ = d y where d y is the ground truth tar-get. on the other hand, multi-hop retrieval aims on finding a set of sequences retrieved through k hops, d ŷ = {d ŷ1 , • • • , d ŷk }, given the query. here, d ŷi is the sequence retrieved at the i-th hop, d ŷi = arg max @xmath2, d ŷ<i ), where x is the query and d ŷ<i is sequences retrieved at previous hops. as the canonical text retrieval of a bi-encoder approach is modeled as arg max @xmath3, which is the inner product between the query vector from an encoder g and the retrieval sequence vector from an encoder f, its extension to multihop is defined as as the number of hops increases, the augmented query (x, d ŷ<i ) gets longer, and it increases the burden of query encoder g to encode the long augmented query into a fixed-size vector. we investigate that such a burden on the query encoder worsens the bottleneck problem of the bi-encoder model and that such models are vulnerable to error propagation (section 5.2). to alleviate such limitations of the bi-encoder approach in a multi-hop setting, we formulate the problem in a fully generative way; the generative approach can interact in the whole parametric space of the model trained on the target corpus during the retrieval process rather than operating only on l2 or inner product space as in bi-encoder approach. we propose generative multi-hop retrieval (gmr), an encoder-decoder model that retrieves the most relevant sequence at each hop from the target corpus by generating the sequence using constrained decoding as in the right side of figure 1 . the generation goes over multiple hops to retrieve a set of sequences. in training time, the objective is to maximize: to generate the tokens d ( j) y i of the ground truth text to retrieve d y i at retrieval hops @xmath4, • • • , n, 4 when the query x and the ground truth target sequences of the previous hops d @xmath5. in inference time, gmr decides the sequence to retrieve by p(d|x, d ŷ<i ) ∝ ∏ |d| @xmath6, d ŷ<i , d (< j) ), i.e. the probability of generating the token d ( j) conditioned on the query since gmr generates a sequence in a unidirectional way (left to right) during the retrieval process, it cannot know the information at the end of a sequence in advance if the model has not been previously trained to generate the sequence. however, the training set for the target multi-hop retrieval task may not cover all the sequences in the corpus. this may negatively affect the performance, especially when the length of the sequence is long and the training set does not contain enough sequences in the target corpus. to alleviate the issue, we propose lm memorization and multi-hop memorization, two corpus memorization methods that aim to store the target corpus in the parameters. by training gmr with the methods, it is able to leverage the memorized information in the parameters on multi-hop retrieval tasks (appendix a). lm memorization lm (language modeling) memorization is an intermediate task applied before training on a multi-hop retrieval task. during lm memorization, gmr is trained on the texts in the corpus using the standard lm objective function: when a corpus d with texts d (@xmath7, the model learns to maximize the lm probability p(d) = ∏ |d| @xmath8. by training the retrieval task on top of the parameters trained on lm memorization, the model is able to be aware of the contents at the end of the sequence it generates beforehand since it has seen the sequence during the lm memorization. to make the input of lm memorization similar to that of multihop retrieval task, we make the first m (randomly chosen) tokens of the text to generate to serve as the encoder input when maximizing p(d) so that the model is trained to maximize p(d (≥m) <m) is the in5 the prefix tree is built by aggregating the tokenization result of texts in the corpus. tokens that create strings that are not a sub-string of any text in the corpus are masked out, and only the next top-k tokens from the unmasked and thus valid set of tokens are passed to the model as the potential next tokens list. put to the encoder. ## experimental results in section 5.1, we compare the results of gmr and bi-encoder models in fixed and dynamic settings with five different datasets. in section 5.2, we show the limitations of bi-encoder retrieval models, discuss the effect of unseen rate in gmr, and show gmr's efficiency on storage and inference time. ## conclusion in this paper, we show that the bi-encoder approach has limitations in multi-hop retrieval; the bottleneck problem becomes a more severe problem as the number of hops increases, and is more susceptible to error propagation. we present generative multi-hop retrieval (gmr), an encoder-decoder model that performs retrieval by generating the entire target sequences with the aid of constrained decoding. we show that gmr is more robust on multi-hop retrieval tasks where it achieves higher or comparable performance in five datasets. we also introduce two corpus memorization methods, lm memorization and multi-hop memorization, to further improve gmr's performance. our experimental results demonstrate that in multi-hop retrieval, a generative approach is highly competitive with bi-encoder methods and deserves further explorations in the community.