Hybrid Inverted Index Is a Robust Accelerator for Dense Retrieval (2023)

Abstract: Inverted file structure is a common technique for accelerating dense retrieval. It clusters documents based on their embeddings; during searching, it probes nearby clusters w.r.t. an input query and only evaluates documents within them by subsequent codecs, thus avoiding the expensive cost from exhaustive traversal. However, the clustering is always lossy, which results in the miss of relevant documents in the probed clusters and hence degrades retrieval quality. In contrast, lexical matching, such as overlaps of salient terms, tend to be strong features for identifying relevant documents. In this work, we present the Hybrid Inverted Index (HI ^2 ), where the embedding clusters and salient terms work collaboratively to accelerate dense retrieval. To make best of both effectiveness and efficiency, we devise a cluster selector and a term selector, to construct compact inverted lists and efficiently searching through them. Moreover, we leverage simple unsupervised algorithms as well as end-to-end knowledge distillation to learn these two modules, with the latter further boosting the effectiveness. Based on comprehensive experiments on popular retrieval benchmarks, we verify that clusters and terms indeed complement each other, enabling HI ^2 to achieve lossless retrieval quality with competitive efficiency across a variety of index settings.

## introduction recently, dense retrieval has become the de-facto paradigm for high-quality first-stage text retrieval, serving as a fundamental component in various information access applications such as search engines @xcite , recommender systems @xcite , and question answering systems @xcite . specifically, dense retrievers encode queries and documents into † corresponding author. there are numerous ann options, e.g. the hashing based ones @xcite , the tree based ones @xcite , the graph based ones @xcite , and the vector quantization (vq) based ones @xcite . among all these alternatives, the vq based indexes, exemplified by ivf-pq, are particularly praised for their high running efficiency in terms of both query latency and space consumption, wherein the inverted file structure (ivf) is an indispensable component @xcite . ivf partitions all document embeddings into disjoint clusters by kmeans. during searching, it finds nearby clusters to an input query and evaluates documents within these clusters by subsequent codecs (e.g. pq). by increasing the number of clusters to scan, one may expect higher retrieval quality since the relevant document is more likely to be included, yet with higher query latency since there are more documents to evaluate @xcite . on top of the basic idea, recent studies improve the accuracy of ivf by grouping the cluster embeddings and skipping the least promising groups @xcite , creating duplicated records for boundary embeddings @xcite , and end-to-end learning the cluster assignments by knowledge distillation @xcite . despite their improvements, ivf still exhibits limited retrieval quality, especially when high efficiency is needed. this is because the clustering is too lossy to include relevant documents in a few close clusters to the query. what's worse, it is not cost-effective to probe more clusters, which sacrifices much more efficiency for minor effectiveness improvements. to better illustrate the above points, we take a concrete example. example 1 in figure 1 , we showcase the recalllatency trade-off derived from changing the number of clusters to visit in the basic ivf and the distilled ivf (the best ivf method so far @xcite ). we use the "flat" codec that reranks the candidate documents in brute force. as such, any retrieval loss against brute force search (denoted as "flat") is due to the failure of ivf. two critical facts can be observed. first, despite improvements from end-to-end distillation, both ivf methods suffer from much poorer retrieval quality at low query latency. with 20ms latency, ivf-flat and distillivf-flat achieve recall of 0.758 and 0.862, both of which lag far behind 0.927 from brute force search. second, probing more clusters marginally improves recall but significantly increases latency. to promote recall from 0.899 to 0.909, distillivf-flat doubles the query latency (from 90ms to around 200ms). consequently, there is plenty of room to optimize ivf to achieve lossless retrieval quality with high efficiency. in contrast to cluster proximity, extensive research has demonstrated that lexical matching, e.g. overlaps of salient terms between queries and documents, tend to be strong features for identifying relevant documents @xcite @xcite . moreover, complementary effect has been observed from combining lexical and semantic matching in hybrid retrieval systems @xcite @xcite . in this work, we explore the potential of unifying embedding clusters and salient terms in a hybrid inverted index (hi 2 ) for the acceleration of dense retrieval. specifically, each document reference is indexed in inverted lists of two types of entries: embedding clusters and salient terms. when searching, the input query is dispatched to both types of inverted lists. documents within them are merged and evaluated by subsequent codecs. for effectiveness, hi 2 needs to include relevant documents in the dispatched inverted lists; for efficiency, hi 2 requires these inverted lists to be small enough to avoid significant overhead during posthoc evaluation. both of them call for constructing compact inverted lists and efficiently searching through them. to this end, we devise a cluster selector and a term selector, which accurately and efficiently pick out only a few clusters and terms for indexing and searching, respectively. as for the implementation of the cluster and term selector, we show simple unsupervised algorithms, i.e. kmeans and bm25, work surprisingly well, whereby hi 2 already substantially outperforms previous ivf methods with competitive efficiency. moreover, we propose to leverage neural networks for realization and end-to-end learning by a knowledge distillation objective. this approach further boosts the retrieval quality, enabling hi 2 to remarkably and consistently surpass other ann indexes on popular retrieval benchmarks, i.e. ms-marco @xcite and natual questions @xcite . our contributions are summarized as follows: ## hybrid inverted index the framework of the hybrid inverted index (hi foot_1 ) is shown in figure 2 . hi 2 organizes the search space with two types of inverted lists: embedding clusters (@xmath0. each document reference is stored in the inverted lists of 1 cluster and k t 1 terms. when searching, the input query q is dispatched to the inverted lists of k c clusters and k t 2 terms. documents within them are merged and evaluated by pq. formally, to determine which clusters/terms to use for indexing the document and dispatching the query, hi 2 employs two modules: a cluster selector and a term selector. they can be implemented with simple unsupervised algorithms (resulting in hi 2 unsup ) and neural networks (resulting in hi 2 sup ). 1 this flexible implementation scheme injects high practicability into hi 2 . in the following, we elaborate on the two modules ( §4.1 and §4.2) and the supervised optimization for their neural network implementation ( §4.3). ## conclusion in this work, we propose the hybrid inverted index, which reformulates conventional ivf by unifying both embedding clusters and salient terms to accelerate dense retrieval. we devise tailored techniques for cluster selection, term selection, and joint optimization. with comprehensive experiments, we verify the effectiveness and efficiency of hi 2 , which consistently outperforms strong ann baselines across implementation variations, indexing/searching configurations, and embedding models. moreover, we demonstrate that embedding clusters and salient terms are complementary to each other for identifying relevant documents, which may inspire further research towards the combination of semantic and lexical features. queries into dense embeddings, then estimate relevance with embedding similarity. for each input query, all document embeddings are evaluated. dpr @xcite , the most basic dense retriever. ance @xcite , enhancing dpr with hard negatives mined from the previous model snapshot. cocondenser @xcite , retrieval-oriented pretraining the encoder model to compress more information in the embedding. ar2 @xcite , adversarially train the encoder and a ranker with knowledge distillation. retromae @xcite , retrievaloriented pretraining the encoder model with a shallow decoder and the representation bottleneck.