Efficient Passage Retrieval with Hashing for Open-domain Question Answering (2021)

Abstract: Most state-of-the-art open-domain question answering systems use a neural retrieval model to encode passages into continuous vectors and extract them from a knowledge source. However, such retrieval models often require large memory to run because of the massive size of their passage index. In this paper, we introduce Binary Passage Retriever (BPR), a memory-efficient neural retrieval model that integrates a learning-to-hash technique into the state-of-the-art Dense Passage Retriever (DPR) to represent the passage index using compact binary codes rather than continuous vectors. BPR is trained with a multi-task objective over two tasks: efficient candidate generation based on binary codes and accurate reranking based on continuous vectors. Compared with DPR, BPR substantially reduces the memory cost from 65GB to 2GB without a loss of accuracy on two standard open-domain question answering benchmarks: Natural Questions and TriviaQA. Our code and trained models are available at https://github.com/studio-ousia/bpr .

## introduction open-domain question answering (qa) is the task of answering arbitrary factoid questions based on a knowledge source (e.g., wikipedia). recent stateof-the-art qa models are typically based on a twostage retriever-reader approach @xcite using a retriever that obtains a small number of relevant passages from a large knowledge source and a reader that processes these passages to produce an answer. most recent successful retrievers encode questions and passages into a common continuous embedding space using two independent encoders @xcite @xcite . relevant passages are retrieved using a nearest neighbor search on the index con- bert q bert p question title + passage hash layer hash layer task 2: reranking task 1: candidate generation continuous vector continuous vector binary code binary code hamming distance inner product taining the passage embeddings with a question embedding as a query. these retrievers often outperform classical methods (e.g., bm25), but they incur a large memory cost due to the massive size of their passage index, which must be stored entirely in memory at runtime. for example, the index of a common knowledge source (e.g., wikipedia) requires dozens of gigabytes. 1 a reduction in the index size is critical for real-world qa that requires large knowledge sources such as scientific databases (e.g., pubmed) and web-scale corpora (e.g., common crawl). in this paper, we introduce binary passage retriever (bpr), which learns to hash continuous vectors into compact binary codes using a multitask objective that simultaneously trains the encoders and hash functions in an end-to-end manner (see figure 1 ). in particular, bpr integrates our learning-to-hash technique into the state-ofthe-art dense passage retriever (dpr) @xcite to drastically reduce the size of the passage index by storing it as binary codes. bpr computes binary codes by applying the sign function to continuous vectors. as the sign function is not compatible with back-propagation, we approximate it using the scaled tanh function during training. to improve search-time efficiency while maintaining accuracy, bpr is trained to obtain both binary codes and continuous embeddings for questions with multi-task learning over two tasks: (1) candidate generation based on the hamming distance using the binary code of the question and (2) reranking based on the inner product using the continuous embedding of the question. the former task aims to detect a small number of candidate passages efficiently from the entire passages and the latter aims to rerank the candidate passages accurately. we conduct experiments using the natural questions (nq) @xcite and triv-iaqa (tqa) @xcite datasets. compared with dpr, our bpr achieves similar qa accuracy and competitive retrieval performance with a substantially reduced memory cost from 65gb to 2gb. furthermore, using an improved reader, we achieve results that are competitive with those of the current state of the art in open-domain qa. our code and trained models are available at https://github.com/studio-ousia/bpr . ## related work retrieval for open-domain qa many recent open-domain qa models depend on the retriever to select relevant passages from a knowledge source. early works involved the adoption of sparse representations @xcite for the retriever, whereas recent works @xcite @xcite have often adopted dense representations based on neural networks. our work is an extension of dpr @xcite , which has been used in recent state-of-theart qa models @xcite . concurrent with our work, @xcite attempted to reduce the memory cost of dpr using post-hoc product quantization with dimension reduction and filtering of passages. however, they observed a significant degradation in the qa accuracy compared with their full model. we adopt the learning-to-hash method with our multi-task objective and substantially compress the index without losing accuracy. learning to hash the objective of hashing is to reduce the memory and search-time cost of the nearest neighbor search by representing data points using compact binary codes. learning to hash @xcite is a method for learning hash functions in a data-dependent manner. recently, many deep-learning-to-hash methods have been proposed @xcite @xcite @xcite to jointly learn feature representations and hash functions in an end-to-end manner. we follow @xcite to implement our hash functions. similar to our work, @xcite used the learning-to-hash method to reduce the computational cost of the answer sentence selection task, the objective of which is to select an answer sentence from a limited number of candidates (up to 500 in their experiments). our work is different from the aforementioned work because we focus on efficient and scalable passage retrieval from a large knowledge source (21m wikipedia passages in our experiments) using an effective multi-task approach. in addition to hashingbased methods, improving approximate neighbor search has been actively studied @xcite @xcite . we use @xcite and @xcite as baselines in our experiments. ## model given a question and large-scale passage collection such as wikipedia, a retriever finds relevant passages that are subsequently processed by a reader. our retriever is built on dpr @xcite , which is a retriever based on bert @xcite . in this section, we first introduce dpr and then explain our model. ## conclusion we introduce bpr, which is an extension of dpr, based on a learning-to-hash technique and a novel two-stage approach. it reduces the computational cost of open-domain qa without a loss in accuracy. in the mini-batch if it does not correspond to the question. our model contains 220 million parameters, and is trained for up to 40 epochs using adam. regarding the hyperparameter search, we select the learning rate from the search range {1e-5, 2e-5, 3e-5, 5e-5} based on the top-100 recall on the validation set of the nq dataset. therefore, the number of hyperparameter search trials is 4. the detailed hyperparameters are listed in