Hybrid Inverted Index Is a Robust Accelerator for Dense Retrieval
Authors: Peitian Zhang
Zheng Liu
Shitao Xiao
Zhicheng Dou
Jing Yao
Venue: EMNLP 2023 Main (2023)
Keywords: Dense Retrieval
ANN Index
Inverted Index
TL;DR: The hybrid inverted index, which jointly incorporates embedding clusters and salient terms to organize the searching space, is a strong and robust accelerator for dense retrieval.

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.

Hybrid Inverted Index Is a Robust Accelerator for Dense Retrieval
Peitian Zhang', Zheng Liu Shitao Xiao², Zhicheng Dou', Jing Yao
'Gaoling School of Artificial Intelligence, Renmin University of China :Beijing Academy of Artificial Intelligence *Microsoft Research Asia (namespace.pt, zhengliul 026 )26)
@omngliu@226@@gmaall
Abstract
their latent embeddings in the semantic space using bi-encoders, and retrieve relevant documents based on embedding similarity. In practice, they rely on Approximate Nearest Neighbor (ANN) indexes to avoid expensive traversal of all document embed- dings for each input query, a.k.a. the brute force search (Johnson et al., 2019).
Inverted file structure a common technique for accelerating dense retrieval. It clusters documents based on their embeddings; dur- ing searching, it probes nearby clusters w.r.t. input query and only evaluates documents within them by subsequent codecs, thus avoid- ing the expensive cost of exhaustive traversal. However, the clustering 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, tends to be strong feature for identifying relevant documents. In this work, we present the Hybrid Inverted In- dex (HIP), where the embedding clusters and salient terms work collaboratively accelerate dense retrieval. To make best of both effective- ness and efficiency, we devise a cluster selector and term selector, to construct compact in- verted lists and efficiently searching through them. Moreover, leverage simple unsuper- vised algorithms as well as end-to-end knowl- edge distillation to learn these two modules, with the latter further boosting the effectiveness. Based on comprehensive experiments on pop- ular retrieval benchmarks, we verify that clus- ters and terms indeed complement each other, enabling HI2 to achieve lossless retrieval qual- ity with competitive efficiency across various index settings. Our code and checkpoint are publicly available at https: i thub. com/ namespace-Pt/Aaee tree/I2..
There are numerous ANN options, e.g. the hash- ing based ones (Datar et al., 2004; Wang et al., 2018), the tree based ones (Bentley, 1975; Wang et al., 2014), the graph based ones (Wang et al.. 2012; Malkov and Yashunin, 2018), and the vec- tor quantization (VQ) based ones (Jégou et al., 201 la,b). Among all these alternatives, the VQ based indexes, exemplified by IVF-PQ, are partic- ularly praised for their high running efficiency in terms of both query latency and space consump- tion, wherein the inverted file structure (IVF) is indispensable component (Jégou et al., 201
IVF partitions all document embeddings into disjoint clusters by KMeans. During searching, it finds nearby clusters to an input query and eval- uates documents within these clusters by subse- quent codecs (e.g. PQ). By increasing the num- ber of clusters to scan, one may expect higher re- trieval quality since the relevant document is more likely to be included, yet with higher query latency since there more documents evaluate (Jégou et al., 201 la). On top of the basic idea, recent stud- ies improve the accuracy of IVF by grouping the cluster embeddings and skipping the least promis- ing groups (Baranchuk et al., 2018), creating du- plicated records for boundary embeddings (Chen et al., 2021). and end-to-end learning the cluster assignments by knowledge distillation (Xiao et al., 2022a). Despite their improvements, IVF still ex- hibits limited retrieval quality, especially when high efficiency is needed. This is because the clus- tering 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
1 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 (Zou et al., 2021), recommender sys- tems (Zhao et al., 2022), and question answer- ing systems (Karpukhin et al., 2020). Specifically, dense retrievers encode queries and documents into
"Corresponding Author.

---

MF-Flay
is indexed in inverted lists of two types of entries: embedding clusters and salient terms. When search- ing, the input query is dispatched to both types of inverted lists. Documents within them are merged and evaluated by subsequent codecs.
Quary Laberey (me)
125
For effectiveness, HI² needs to include relevant documents in the dispatched inverted lists; For effi- ciency, HI requires these inverted lists to be small enough avoid significant overhead during post- hoc evaluation. Both of them call for construct- ing compact inverted lists and efficiently searching through them. To this end, we devise a cluster se- lector and a term selector, which accurately and efficiently pick out only few clusters and terms for indexing and searching, respectively.
20
0.700
0.8
0.536
8888 0.069 0 808
0.327
0.95
Recslig 100
Figure 1: Recall-latency trade-off example for existing IVF methods MSMARCO Passage. Better indexes should locate at the lower right corner.
sacrifices much more efficiency for minor effective- ness improvements. To better illustrate the above points, we take concrete example.
As for the implementation of the cluster and term selector, we show simple unsupervised algo- rithms, i.e. KMeans and BM25, work surprisingly well, whereby HI? already substantially outper- forms previous IVF methods with competitive ef- ficiency. Moreover, we propose to leverage neural networks for realization and end-to-end learning by knowledge distillation objective. This approach further boosts the retrieval quality, enabling H12 to remarkably and consistently surpass other ANN indexes on popular retrieval benchmarks, i.e. MS- MARCO (Nguyen et al., 2016) and Natual Ques- tions (Kwiatkowski et al., 2019).
Example In Figure 1, we showcase the recall- latency trade-off derived from changing the number of clusters to visit the basic IVF and the dis- tilled IVF (the best IVF method so far (Xiao et al., 2022a)). We use the "Flat" codec that reranks the candidate documents in brute force. As such, any retrieval loss against brute force search (denoted "Flat") ) is due to the failure of IVF.
Two critical facts can be observed. First, de- spite improvements from end-to-end distillation, both IVF methods suffer from much poorer re- trieval quality at low query latency. With 20ms latency, IVF-Flat and DistillIVF-Flat achieve re- call of 0.758 and 0.862, both of which lag far be- hind 0.927 from brute force search. Second, prob- ing more clusters marginally improves recall but significantly increases latency. To promote recall from 0.899 0.909, DistillVF-FFlat doubles the query latency (from 90ms to around 200ms). Con- sequently, there is plenty of room to optimize IVF to achieve lossless retrieval quality with high effi- ciency.
Our contributions are summarized as follows:
We propose the Hybrid Inverted Index, which combines embedding clusters and salient terms for accelerating dense retrieval.
We devise tailored techniques, i.e. the cluster selector, the term selector, and the joint opti- mization, to guarantee the effectiveness and efficiency of H12
In contrast to cluster proximity, extensive re- search has demonstrated that lexical matching, c.g.
We evaluate HI2 with extensive experiments and verify its robust advantage across imple- mentation variations, indexing/scarching con- figurations, and embedding models.
overlaps of salient terms between queries and docu- ments, tend to be strong features for identifying rel- evant documents (Robertson and Zaragoza, 2009; Lin and Ma, 2021; Formal et al., ..21). Moreover, complementary effect has been observed from com- bining lexical and semantic matching in hybrid re- trieval systems (Kuzi et al., 2020; Gao et al., 2020; Shen et al., 2022; Zhang al., 2023).
Related Works
Dense Retrieval. In the last four years, the rapid development of pre-trained language mod- els, e.g. BERT (Devlin al.. 2019), has signif- icantly pushed forward the progress of dense re- trieval, making increasingly popular for high- quality first-stage retrieval (Zhao et al., 2022: Zhu et al., 2023). Dense retrievers encode queries and
In this work, we explore the potential of unifying embedding clusters and salient terms in a Hybrid Inverted Index (HI2) for the accelcration of dense retrieval. Specifically, each document reference

---

documents into dense vectors (i.e. embeddings) in the same latent space, where the semantic rele- vance measured by embedding similarity. Recent studies further enhance their retrieval quality by retrieval-oriented pre-training (Wang et al., 2022; Xiao et al., 2022b; Gao and Callan, 2022), delicate negative sampling (Xiong et al., 2021; Qu et al., 2021; Zhan et al., 2021b), and knowledge distil- lation from more powerful rankers (Zhang al., 2022; Lu et al., 2022; Qu al., 2021).
timal as shown in Example In this work, our proposed Hybrid Inverted Index support efficient identification of relevant documents through both semantic and lexical matching. Note that our work is orthogonal to those about efficient inverted index access (Broder et al., 2003; Mallia et al., 2022) and hence can be combined for further acceleration.
Hybrid Retrieval. Recently, there have been emergent recipes for the union of semantic (dense) and lexical (sparse) features. Some of them are di- rect ensembles of dense and sparse retrievers (Ma et al., 2021; Kuzi et al., 2020); Others use enhanced optimization objectives, e.g. adversarial hard nega- tives and distillation, to jointly learn from seman- tic/lexical features (Gao et al., 2020; Shen et al., 2022; Zhang et al., 2023). However, they all rely separate sparse and dense indexes work, and interpolate scores from the two indexes. Differ- from them, HI² combines semantic and lexical features at index level, and estimates scores uni- versally by specific codecs. Meanwhile, HI" may benefit from enhanced optimization methods in these methods, which we leave for future work.
ANNs Indexes. In practice, relevant docu- ments usually need be retrieved from mas- sive collection. Consequently, dense retrieval must rely on Approximate Nearest Neighbor (ANN) in- dexes to avoid the expensive brute force search. The ANNs indexes can be realized via different strategies: 1) the hashing based ones (Datar et al., 2004; Weiss et al., 2008; Wang et al., 2018); 2) the tree based ones (Bentley, 1975; Wang al., 2014; Muja and Lowe, 2014); 3) the graph based ones (Dong et al., 2011; Wang et al., 2012; Malkov and Yashunin, 2018); 4) the vector quantization (VQ) based ones (Ge et al., 2014; Jégou et al., 201 la,b; Baranchuk et al., 2018). Among these options, the VQ based indexes are particularly pre- ferred for massive-scale retrieval owing to their high efficiency in terms of both query latency and space consumption (Johnson et al., 2019).
3 Preliminaries
3.1 Dense Retrieval
Given collection of documents D [ dense retrieval aims retrieve the top R relevant documents from D in response to an input query Q. Specifically, each document D E and query Q is encoded into its embedding ep, eq E R. by document encoder and a query encoder, respec- tively. Next, the relevance is measured by the inner product between them, whereby the top R. ranked documents are returned.
VQ Index Optimization. Despite the com- petitive efficiency, VQ-based indexes are prone to limited retrieval quality when low latency is desired, In recent years, continuous efforts have been dedi- cated to alleviating this problem, which can be cat- egorized into two threads. One thread is to design advanced heuristics for clustering and evaluation. For example, (Jégou et al., 201 1b) and (Baranchuk et al., 2018) add another refinement stage over the quantized embeddings and skip less promising clus- according tailored heuristics. (Chen al., 2021) create duplicated reference for boundary em- beddings to improve recall with high efficiency. The other research thread optimizes the VQ in- dex towards retrieval quality with cross-entropy loss instead of minimizing the reconstruction loss. For example, (Zhan et al., 2021a) and (Xiao et al., 2021) jointly Iearns the query encoder and the prod- uet quantizer by contrastive learning. (Xiao al., 2022a) further improves the accuracy by leverag- ing knowledge distillation for joint optimization. However, all these methods stick to conventional IVF to organize the search space, which is subop-
result = top-R (leq, ep) DED). (I)
where (..-) denotes inner product.
In reality, it is impractical to evaluate every doc- ument (computing (eq. eD)) for each input query (i.e. the brute force search), which results in ex- ceedingly high latency and resource consumption. Instead, ANN indexes are used to avoid exhaus- tively scanning all documents and accelerate the relevance measurement by approximation.
3.2 Inverted File Structure and Product Quantization
Among all alternative ANN indexes, the Vector Quantization (VQ) based ones are particularly pop- ular for massive-scale retrieval. They consist of

---

two basic modules: the inverted file structure (IVF) and the product quantization (PQ).
lists of cluster and Kf terms. When searching. the imput query Q dispatched the inverted lists of K clusters and K3 terms. Documents within them are merged and evaluated by PQ. Formally,
To avoid exhaustive search, IVF partitions all documents into disjoint clusters C - {C:]== by KMeans, where each cluster is associated with an embedding eC, E E. For the query Q. documents within the closest KC clusters are evaluated by the subsequent codec (PQ by default):
result top- (PQ(Q, D) D E A(Q))
A(Q) = -00))
(5)
result = top- (PQ(Q,D) D A(Q)):
To determine which clusters/terms to use for index- ing the document and dispatching the query, HI² employs two modules: a cluster selector and term selector. They can be implemented with simple unsupervised algorithms (resulting in Hu and neural networks (resulting in H. This flexible implementation scheme injects high practicability into HI2. In the following, we elaborate on the two modules ($4.1 and (4.2) and the supervised opti- mization for their neural network implementation (54.3).
D
A(Q) = ((eq,ec))) CEC). (2)
C.
To accelerate relevance estimation, PQ compresses the document embedding into discrete integer codes according It splits ep into m fragments ymL then quan- tizes each fragment to the closest codeword in w:
codebook
Rmxkxh/m
< = j fg = argginn e 2.
(3)
4.1 Cluster Selector
Therefore, only the global codebook and the codeword assignment 0, need to be stored, which is much smaller than the full-precision embedding. Finally, the relevance is evaluated by:
This module selects cluster for indexing the doc- ument and KC clusters for dispatching the query to. Specifically, it associates each cluster C with an embedding ec, R Then scores each cluster with the inner product between the document em- bedding ep or the query embedding eq: ec,). The document indexed to the cluster with the highest score. When searching. the query is dis- patched to the top KC clusters:
PQ(Q,
EQ eb).
(4)
where e/2 is the query embedding fragment. Since the inner product between eq and any codeword Uj.= be cached once computed, the relevance estimation approximated by PQ is much faster.
A (Q) = - Utop-K (leq, ec:) |c, C.E.). C}. Ci
(6)
By increasing the number of clusters to scan (KC), higher retrieval quality can be achieved be- cause the relevant document is more likely to be included in A(Q). Yet, the latency is increased at the same time as more documents need to be evalu- ated. Conventional IVF falls short in including the relevant document given small KC, meanwhile, it needs to sacrifice lot of efficiency for minor retrieval quality improvement. In this work, propose an alternative alleviate these problems.
For HI2 HI the cluster embeddings {ec, V are produced by KMeans over all document embed- dings. For H1 they are initialized with KMMaan and optimized on-the-fly by the objective in $4.3.
4.2 Term Selector
This module selects KT terms for indexing the document and K3 terms for dispatching the query. There are concerns for designing the term lector: 1) the selected terms must be representative w.r.t. the input, hence the lexical matching between the query and the document can be effectively cap- tured; 2) the term selection for the query must be efficient enough to avoid excess online overhead. Therefore, for the document D, the term selector first tokenizes it (d.) where d, E V, then it
4 Hybrid Inverted Index
The framework of the Hybrid Inverted Index (HI is shown in Figure 2. HI2 organizes the search space with two types of inverted lists: embedding clusters (C- (L) and salient terms (T {T, v E }} where V is the term vocabulary). Each document reference is stored in the inverted
We use HI" to denote both HI and HI2, henceforth.

---

Cluster Selector
Inverted Lists
Term Selector
C
D31
...
Cluster
C₁
D2
D8
D156
Cluster [1.7]
1
D156
C
D43
D96
Q3
oran weather october 2017. expect 25"
...
weather in oran
T chicken
D4
D6
D96
Toran
D156
(oran, weather]
[oran, weather)
...
Tweather
D31
D156
Menge
Evaluate (PQ)
D1
D31
D156
D156
D31
D1
Figure 2: The framework of the Hybrid Inverted Index (HI²), Each document reference indexed inverted lists of two types of entries: embedding clusters and salient terms. When searching, the input query is dispatched to both types inverted lists. Documents within them are merged and evaluated by the subsequent codee (PQ).
estimates the score of each unique term E V in D with BM25 (HI or BERT (H12 Formally,
powerful teacher θ to produce accurate estima- tions of their relevance. Finally, enforce the cluster selector and the term selector produce similar estimations by KL divergence:
(o+1)xIDF((XXPP(.... IF(r,D)ax((1-11 84 w
3dg = v Hinsup
max (ax(((BERT(Djd)) d:=0
3dg
HI2
Distill (Q) -KL(O(Q,D) || CS(Q, D)) +KL( D) TS(Q, D)). (9)
Ad. = U.
(7)
a, 3 are hyper parameters, avgdl is the average doc- ument length, f()) is two-layer MI. of RM -> IR' with ReLU activation, and BERT denotes encod- ing by BERT model (Devlin et al., 2019). As such, the top KT scored terms are used for indexing the document. Besides, the average score cach term across all documents (S,) is stored.
Following (Xiao et al., 2022a), we simply choose off-the-shelf embeddings as teachers. Denote soft- max operator sm, the teacher estimations are:
(Q D) sm((eq.
D}.
(10)
The cluster selector estimates relevance by query-cluster embedding similarity:
The query Q is tokenized to { likewise, while it is not processed with any complex compu- tations save online cost. For short queries, all its constituting terms are selected; for long queries, the terms with top KР average score are selected:
CS(Q, D) smm (eq. eC.Di) DE D), (11)
where ((D) is the cluster index of the document.
The term selector estimates relevance by term- score vector similarity:
A² = U( a E QQ U(T l E Q')
Q < K3,
otherwise.
TS(Q, sm SD) De D}, (12)
Q' = K2 (5g. | E Q)
where SQ and sD are the score vector over the vocabulary derived from Eq 7. Note that here both queries and documents are processed the same way. Additionally, since the document cluster assign- ment ((D) is fixed, add commitment loss to the final loss keep the document embedding close to its associated cluster, which is common practice for learning quantization (van den Oord
4.3 Joint Optimization
HIS involves learning cluster embeddings in the cluster selector, the MLP, and BERT in the term selector. We propose a knowledge distillation ob- jective for jointly training these parameters towards retrieval quality. Concretely, we sample a subset documents for the query (D D), then employ

---

et al., 2017):
et al., 2022b). 3) Dense retrievers with ANN in- dexes (denoted as ANNs), including IVF-PQ (Jé- gou et al., 201 2011a), IVF-OPQ (Ge et al., 2014), IVF-JPQ (Zhan et al., 2021a), Distill-VQ (Xiao et al., 2022a), and HNSW (Malkov and Yashunin, 2018) (we set the edges to 32 and efSearch to 500), We use RetroMAE and AR2 as the embedding model on MSMARCO and NQ, respectively, due to their superior performance with brute force search. More details are in the Appendix.
C Commit (Q) = Σ log exp((eD,
exp(ee,, )
DED
L= Σ Distill (Q) + C Commilt (Q).
(13)
5 Experiments
In this section, we first introduce our experimental settings, then carry out extensive experiments to investigate the following research questions (RQ):
Implementation Details. For all methods involv- ing clustering, we set the number of clusters L to 10000 and the number of probing clusters when searching to 100 (except H1²). For all methods involving PQ, we set the number of fragments m to 96, the number of sub-clusters & to 256. For HI², we use the BERT's vocabulary (Devlin et al., 2019) as the term vocabulary V, resulting in 30522 unique terms in total. K2 is always set to 32 for both HI² unsup and HI? sup
RQ1: How are the effectiveness and efficiency of HP compared with other baselines methods?
RQ2: Do clusters and terms complement each other for identifying relevant documents?
RQ3: How is the robustness of HI2 across different embedding models?
5.1 Experimental Settings
For HI2 iasps we use KMeans over all docu- ment embeddings to produce cluster embeddings {ec. | BM25 to produce term scores 8y with = 0.82, 3 - 0.68, and OPQ (Ge et al., 2014) as the evaluation codec, all of which are unsu- pervised algorithms. KC is set to 25, KT is to 15. For H1 we initialize cluster em- beddings with KMeans and optimize them after- ward. Note the cluster assignment ((D) is fixed once initialized. We use bert-base-uncased for the term selector. The passage is tokenized to 128 tokens before encoding. We employ the distilled OPQ (Xiao et al., 2022a) as the evaluation codec. KC is set to 30, KT is set to 3. More details are in the appendix. For reproducibility, lease our source code and model checkpoints https://anonymous.. 4open. scieence/r/ee////.......
Datasets. We use two popular benchmark datasets. 1) MS MARCO (Nguyen et al., 2016). We use the passage track, including 502,939 train- ing queries and 6,980 evaluation queries (dev set); the corpus size is 8,841,823. 2) Natural Ques- tions (Kwiatkowski et al., 2019). We follow the split of DPR (Karpukhin et al., 2020), resulting in 79,168 training queries and 3,610 testing queries. The corpus size is 21, 21,015,324.
Metrics. For evaluating retrieval quality, we leverage MRR@K (M@K, K) and Recall @K K (R@ K). For evaluating retrieval efficiency,
compute the average query latency (QL) and the overall index size (IS). Our evaluations are based on the same batch size, thread number, and toolkit (Faiss (John- son et al., 2019) for ANNs and Pyserini (Lin et al., 2021) for sparse models). Note that the latency of 2I2 is on par with that of IVF-OPQ given the same number of candidates to evaluate, because the term selector dispatches the query with simple heuristics that introduces very little overhead.
5.2 Main Analysis (RQ1)
We report the overall evaluation results in Table 1. On the one hand, our hybrid inverted index demonstrate effeeraaiveeefffettiveeees over baseline ANN indexes. Specifically, Hi which solely relies on unsupervised algorithms, improves the Re- call @ 100 of IVF-OPQ (the basic unsupervised VQ index) by 14%, and improves that of Distill-VQ (the strongest supervised VQ index in literature) by 8%. It even triumphs the powerful HNSW in- dex by 3 absolute points in Recall 100, which is a more valuable metric for first-stage retrieval than MRR. Moreover, the neural network imple-
Baselines. We compare with three types of retrieval models: 1) Sparse retrievers, in- cluding BM25 (Robertson and Zaragoza, 2009), DocT5 (Cheriton, 2019), DeepCT (Dai and Callan, 2019), UniCOIL (Lin and Ma, 2021), and Distil- SPLADE (Formal et al., 2021); 2) Dense retrievers with brute force search (denoted as Flat), includ- ing DPR (Karpukhin et al., 2020), ANCE (Xiong et al., 2021), CoCondenser (Gao and Callan, 2022), AR2 (Zhang et al., 2022), and RetroMAE (Xiao
effectiveness

---

MS MARCO
Natual Questions
Type
Method
M0
R8100
R@1000
(ms)
IS (G)
R@5
R@100
QL (ms)
18 (G)
BM25
0.187
0,670
0.490
0.639
2.3
DocI5
0.277
0.947
17
1.0
Sparse
DeepCT
0:243
12
Retrievers
UniCOI.
0.330
0.823
0.932
124
1.0
0.638
0.774
0.861
480
3.4
DisUSSPLADE
0.366
0.896
0.978
455
2.4
DPR
D.317
0.857
0.959
1751
26
0.784
0.853
4785
60
Dense
ANCE
0.346
0.873
0.964
1751
26
0.819
0.875
4785
60
Retrievers
CoCondeneer
0.382
0.984
1751
26
0.758
0.843
0.890
4785
60
(Flat)
AR2
0.984
1751
26
0.861
4785
60
RetroMAF
0.416
0.927
0.988
1751
26
0.844
0.894
4785
60
IVF-PQ
0.292*
0.763*
0.849
13
0.9
0.545
0.695
0.799*
28
2.1
Danse
IVE-PRQ
0,546*
0.796
0,853*
13
0.9
0.687
0.775
0.836*
28
2.1
Retrievers
IVF.JPQ
0.348*
0.799*
0.854
13
0.9
0.689
0.776*
0.836
28
2.1
(ANNs)
Distil-VV
0.358*
0.843*
0.705*
0.799*
0.860+
HNSW
0,400
0,887
0.944
28
0.778
0.857
0.898
13
66
I1
0.380
0,900
0.966
3.0
0.767
0.853
0.896
15
7.1
HI
D.401
0.916
0.976
3.0
0.779
0.861
0,906
15
7.1
Table 1: Overall evaluation results. Statistically significant results within ANNs group compared with HI? (paired t-test with p < 0.05) are decorated with * Best results are bold. Second best results are underlined. QL means the average query latency. IS means the index size.
mentation and the end-to-end knowledge distilla- tion further unleash its potential, as HI? further amplify the margins over ANN baselines. Remark- ably. HI2 achieves on par retrieval quality with its brute-horce-search teacher (RetroMAE on MS- MARCO and AR2 on NQ), and surpasses a lot of well-established sparse and dense retrievers.
From the figure, HIS Hu performs on par with the powerful HNSW across various index settings, as their recall are almost identical given the same latency. Both of them significantly outperform VQ baselines. Besides, H1S brings substantial improvement over HI? HI and HNSW, achieving higher recall with lower latency. Meanwhile, it efficiently approaches the brute-force-scard effec- tiveness. In contrast, VQ baselines need to largely increase the latency to marginally improve the re- call, yet lagging far behind brute force search.
On the other hand, the efficiency of our hybrid in- verted index is also satisfactory. Its query latency is the second lowest both datasets, accelerating the brute force search (Flat) by hundreds of times and only slightly falling behind that of HNSW. Notably, the latency is even lower than VQ-based indexes, because 2 nceds to evaluate fewer candidate doc- uments. Besides, 2 possesses a moderate index size, which is bigger than VQ baselines since more document references need to be stored, while much smaller than Flat or HNSW since it docs not need store full-precision embeddings.
Based on the above analysis, we answer RQI: HP achieves lossless retrieval quality against brute force search, with low query latency and small in- dex size, significantly and consistently outperform- ing baseline ANN indexes and retaining the advan- tages across indexing/searching configurations.
5.3 Ablation Analysis (RQ2)
As such, have showcased the outstanding ef- fectiveness and efficiency of HI2 under one specific setting. Next, we are interested in the effectiveness- efficiency trade-off of HI² and ANN baselines (we exclude IVF-PQ and IVF-JPQ, the former is too weak and the latter is similar to IVF-OPQ). Specif- ically, for VQ indexes, we change the number of clusters to visit; for HNSW, we change the num- ber of neighbors to visit; for HI?, we change the number of terms to index (KF) and the number of clusters dispatch (K Since the index size is static, we measure recall 1 100 as effectiveness and average query latency as efficiency. The resulted trade-off curves are reported in Figure 3.
To answer RQ2, we study the individual contribu- tion from embedding clusters and salient terms. Specifically,
disable the inverted lists corre- sponding terms and clusters, respectively, de- noted as w.o. Term and w.o. Clus. Other configura- tions are kept the same. We plot their recall-latency trade-off curves in Figure
Two critical facts can be observed. First, salient terms tend to be better features for organizing the search space than embedding clusters, as the w.o. Clus variants significantly and consistently outper- form w.o. Term ones. Thus, our claim that embed- ding clusters alone falls short in effective identifica- tion of relevant documents is well justified. Second,

---

(A] MS MARCO Passage
[A] MARCO Passage
140
100
HC Clus
HCae W.O. Tarm
Query Larency (ms)
Query Latency
80
H1
HC
HR,, W.O. Term
Hig W.O. Clus
Piat
40
Fatt
20
0.750
(B) Natual Questions
0.750
0,775
0.800
0.525
0.850
0.875
0.900
0.925
[B) Natual Questions
:50
IVT-0D
WF OPG
120
HC R.o.
DisilliQQ
HC
Term
Query Latercy (mes)
100
Quory Labency
200
HR, W.D.
HR,
Term
60
H
200
40
0.70
0.80
0.04
0.05
0.88
0.50
Recilly 100
0.87 Receligi100
Figure 3: intettivensss-effcienss trade-off of different methods on MS MARCO (A) and Natual Questions (B).
Figure 4: EFfectivennss-efffiinnyy trade-off of HI2 vari- ants on MS MARCO (A) and Natual Questions (B).
MS MARCO
NQ
the strong HNSW index, which uses full- -recisren embeddings for evaluation. As for efficiency, we observe HI2 resides in sweet spot with the second lowest query latency and relatively small index size, which is substantially smaller than Flat and HNSW but slightly bigger than VQ baselines.
Emah
ANN Index
100
QL
18
R@100
QL.
IS
Flat
0.927
1751
26
0.894
4785
60
HNSW
RetroMAE
IVP-OPQ
0.796
13
0.9
0.843
Disail-VO
0.843
10
0.870
2.1
H
quap
0.900
3.0
0.880
15
2.1
HC,
0.916
3.0
0.885
15
7.1
Flat
0.919
1751
26
0.908
4785
60
LINSW
Additionally, the performance of ANN base- lines unstable given different embedding models: higher retrieval quality with brute-force scarching does not result in higher retrieval quality with ANN acceleration. For example, the recall of AR2 Flat is inferior that of RetroMAR Flat MS MARCO. However, this trend reverses when ANN baselines are applied, i.e. AR2 IVF-OPQ is better than Retro- MAE IVF-OPQ. By comparison, the performance of HI stable: higher meute-force-seale effee- tiveness corresponds to higher effectiveness of HI2 regardless of the embedding model.
AR2
Distill
IVE-PF
0.858
0.846
11
10
0.9
0.860
0.836
28
2.1
2.1
HI
0,899
3.0
0.896
15
7.1
111
0.909
3.0
0.906
15
2.1
Table 2: Evaluation of HI2 and strong ANN baselines with different embedding models (Emb.).
salient terms and embedding clusters indeed com- plement each other, Ho and HI2 sup beats their "homogeneous" variants in terms of both effective- ness and efficiency. Therefore, we answer RQ2: Embedding clusters and salient terms complement each other for more effective and efficient identifi- cation of relevant documents.
In summary, we answer RQ3: HI² enjoys high robustness and stability across different embedding models, consistently surpassing strong ANN base- lines with competitive efficiency and aligning well with the brute force search.
5.4 Robustness Analysis (RQ3)
Figure 3, we have shown the robust advantage of HI² across different index configurations. For practical usage, it is important to evaluate the ro- bustness of 2I2 given different embedding models.
Conclusion
In this work, we propose the hybrid inverted in- dex, which reformulates conventional IVF by uni- fying both embedding clusters and salient terms to accelerate dense retrieval. We devise tailored techniques for cluster selection, term selection, and joint optimization. With comprehensive experi- ments, we verify the effectiveness and efficiency
In Table 2, report the performance of HI2 and selected strong baselines with RetroMAB and AR2 the embedding model. We can notice that sup always achieves the best recall among all ANN indexes, which is very close to that of brute force search. Besides, HT2 unsup performs on par with
H

---

of H12, which consistently outperforms strong ANN baselines across implementation variations, indexing/searching configurations, and embedding models. Moreover, we demonstrate that embed- ding 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.
David R. Cheriton. 2019. From doc2query to docttttt- query.
Zhuyun Dai and Jamie Callan. 2019. Context-aware sentence/passage term importance estimation for first stage retrieval. CoRR, abs/1910.
Mayur Datar, Nicole Immorlica, Piotr Indyk, and Va- hab S. Mirrokni. 2004, Locality-sensitive hashing scheme based on p-stable distributions. In Proceed- ings of the 20th ACM Symposium on Computational Geometry, Brooklyn, New York, USA, June 8-11, 1, 2004, pages 253 262. ACM.
Acknowledgement
This work was supported by the National Natural Science Foundation of China No. 62272467 and Public Computing Cloud, Renmin University of China. The work was partially done at the Engi- neering Research Center of Next-Generation Intel- ligent Search and Recommendation, MOE.
Jacob Devlin, Ming-Wai Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: pre-training of deep bidirectional transformers for language under- standing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, NAACL-HLT 2019, Minneapolis, MN. USA, June 2-7, 2019, Volume (Long and Short Papers). pages 4171-4188 Association for Computational Linguistics.
Limitations
Despite the satisfactory performance of the hybrid inverted index, it has more hyper parameters than conventional IVF hence may require more effort to tune them for ideal performance. Moreover, the searching of clusters and terms is currently inde- pendent; whilst we believe it is promising to design a more flexible mechanism to control the search- ing behaviors. For example, only the term-side inverted lists will be searched for some queries.
Wei Dong, Moses Charikar, and Kai Li. 201 I. Efffiientt k-nearest neighbor graph construction for generic similarity measures. Proceedings of the 20th In- ternational Conference on World Wide Web, WWW 2011, Hyderabad, India, March 28 April 1, 2011. pages 577-586. ACM.
elasticsearch. 2015. elastissaarchlllastisseaccc
Thibault Formal. Carlos Lassance, Benjamin Pi- wowarski, and Stéphane Clinchant. 2021. SPLADE v2: Sparse lexical and expansion model for informa- tion retrieval. CoRR, 0bs/2209910086
References
Luyu Gao and Jamie Callan. 2022. Unsupervised cor- pus aware language model pre- ve-training for dense pas- sage retrieval. In Proceedings of the 60th Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), ACI. 2022, Dublin, Ireland, May 22-27, 2022, pages 2843-2853. Associ- ation for Computational Linguistics.
Dmitry Baranchuk, Artem Babenko, and Yury Malkov. 2018. Revisiting the inverted indices for billion-scale approximate nearest neighbors. In Computer Vision ECCV 2018- 15th European Conference, Munich, Germany, September 8-14, 2018, Proceedings, Part XII, volume 11216 of Lecture Notes in Computer Science, pages 209-224. Springer.
Luyu Gao, Zhuyun Dai. Zhen Fan, and Jamie Callan, 2020. Complementing lexical retrieval with semantic residual embedding. CoRR, 0bs/2004.1396)
Jon Louis Bentley. 1975. Multidimensional binary search trees used for associative searching. Commun. ACM, 1899):509-517.
Tiezheng Ge, Kaiming He, Qifa Ke, and Jian Sun. 2014. Optimized product quantization. JEEE Trans. Pattern Anal. Mach. Intell., 36(4):744-755
Andrei 7. Broder, David Carmel, Michael Herscovici, Aya Soffer, and Jason Y. Zien. 2003. Efficient query evaluation using a two-level retrieval process. In Proceedings of the 2003 ACM CIKM International Conference on Information and Knowledge Manage- ment, New Orleans. Louisiana, USA, November 2-8. 2003, pages 426-434. ACM.
Hervé Jégou, Matthijs Douze, and Cordelia Schmid. 201 la. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 33( 33(1):117-1 17-128.
Hervé Jégou, Romain Tavenard, Matthijs Douze, and Laurent Amsaleg. 201 Searching one billion vectors: Re-rank with source coding. In Proceedings of the IEFE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2011, May 22-27. 2011, Prague Congress Center, Prague, Czech Republic, pages 861-864. IEEE
Qi Chen, Bing Zhao, Haidong Wang. Mingqin Li, Chuanjie Liu, Zengzhong Li. Mao Yang, and Jing- dong Wang. 2021. Spann: Highly-efficient billion- scale approximate nearest neighbor search. In 35th Conference on Neural Information Processing Sys- lems (NeurIPS 2021).

---

Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2019. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 7(3):335-547.
Marius Muja and David G. Lowe. 2014. Scalable near- est neighbor algorithms for high dimensional data. IEFF Trans. Pattern Anal. Mach. Intell,, 36( (1((1)))20 ):2227 2240.
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick S. H. Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. 2020. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Nat- ural Language Processing, EMNLP 2020, Online, November 16-20, 2020. pages 3769-6781. Associa- tion for Computational Linguisties.
Linh Thai Nguyen. 2009. Static index pruning for infor- mation retrieval systems: A aasting-based approach. In Proceedings of the 7th Workshop on Large-Scale Distributed Systems for Information Retrieval, co- located with ACM SIGIR 2009, LSDS-IRG SIGIR 2009, Boston, USA, July 23, 2009, volume 480 of CEUR Workshop Proceedings. CEUR-WS.org.
Saar Kuzi, Mingyang Zhang, Cheng Li, Michael Ben- dersky, and Mare Najork. 2020. Leveraging semantic and lexical matching to improve the recall of docu- ment retrieval systems: A hybrid approach. CoRR, abs/2010.01195.
Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. 2016. MS MARCO: A human generated machine reading comprehension dataset. In Proceedings of the Workshop on Cognitive Computation: Integrat- ing neural and symbolic approaches 2016 co-located with the 30th Annual Conference on Neural Infor- mation Processing Systems (NIPS 2016), Barcelona, Spain, December 9, 2016, volume 1773 of CEUR Workshop Proceedings. CEUR-WS.org.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Red- field, Michael Collins, Ankur P. Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Ken- ton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming-Wi Wei Chang, Andrew M. Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. 2019. Natu- ral questions: a benchmark for question answering research. Trans. Assoc. Comput. Linguistics, 7:452- 466.
Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. 2021. Rocketqa: An optimized train- ing approach to dense passage retrieval for open- domain question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Hu- man Language Technologies, NAACL-HLT 2021, On- line, June 6-1 1, 2021, pages 5835-5847. Association for Computational Linguistics.
Jimmy Lin and Xueguang Ma. 2021. A few brief notes on deepimpact, coil, and a conceptual frame- work for information retrieval techniques. CoRR, his/2106.14807
Jimmy Lin, Xueguang Ma, Sheng-Chied Lin, Jheng- Hong Yang, Ronak Pradeep, and Rodrigo Nogueira. 2021. Pyserini: A Python toolkit for reproducible information retrieval research with sparse and dense representations. In Proceedings of the 44th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR 2021), pages 2356-2362.
Stephen E. Robertson and Hugo Zaragoza. 2009, The probabilistic relevance framework: BM25 and be- yond. Found. Trends Inf. Retr. 344):333-38,
Tao Shen, Xiubo Geng, Chongyang Tao, Can Xu, Kai Zhang, and Daxin Jiang. 2022. Unifier: A unified retriever for large-scale retrieval. CoRR, abs/2205.111991
Yuxiang Lu, Yiding Liu, Jiaxiang Liu, Yunsheng Shi, Zhengjie Huang, Shikun Feng, Yu Sun, Hao Tian, Hua Wu, Shuaiqiang Wang, Dawei Yin, and Haifeng Wang. 2022. Ernie-search: Bridging cross-encoder with dual- dual-encoder via self on-the-fly fly distillation for dense passage retrieval. CoRR, abs/2205.09153.
Aäron den Oord, Oriol Vinyals, and Koray Kavukeuoglu. 2017. Neural discrete representation learning. In Advances in Neural Information Pro- cessing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 6306-6315.
Xueguang Ma, Kai Sun, Ronak Pradeep, and Jimmy Lin. 2021. A replication study of dense passage retriever. CoRR, abs/2104.05744
Jing Wang, Jingdong Wang, Gang Zeng, Zhuowen Tu, Rui Gan, and Shipeng Li. 2012. Scalable k-nn graph construction for visual descriptors. In 2012 IEEE Conference on Computer Vision and Pattern Recog- nition, Providence, RI, USA, June 16-21, 2012, pages 1106-1113. IEEE Computer Society.
Yu A Malkov and Dmitry A Yashunin. 2018. Efficient and robust approximate nearest neighbor search us- ing hierarchical navigable small world graphs. IEFE transactions on pattern analysis and machine intelli- gence, 42(4):824-836.
Jingdong Wang, Naiyan Wang. You Jia, Jian Li, Gang Zeng, Hongbin Zha, and Xian-Sheng Hua. 2014. Trinary-projection trees for approximate nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 36(2):3884033
Antonio Mallia, Joel Mackenzie, Torsten Suel, and Nicola Tonellotto. 2022. Faster learned sparse re- trieval with guided traversal. CoRR, abs/2204.1 1114..

---

Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, and Heng Tao Shen. 2018. A survey on learning to hash. IEEE Trans. Pattern Anal. Mach. Intell., 4094).76--79.
Retrieval, Virtual Event, Canada, July 11-15, 2021. pages 1512-112..00 ACM
Hang Zhang. Yeyun Gong, Yelong Shen, Jiancheng Lv, Nan Duan, and Weizhu Chen. 2022. Adversarial retriever-ranker for dense text retrieval. In The Tenth International Conference on Learning Representa- tions, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net.
Liang Wang, Nan Yang, Xiaolong Huang. Binxing Jiao, Linjun Yang, Daxin Jiang. Rangan Majumder, and Furu Wei, 2022. Simlm: Pre-training with represen- tation bottleneck for dense passage retrieval. CoRR, 00//2007.0258..
Kai Zhang, Chongyang Tao, Tao Shen, Can Xu, Xiubo Geng, Binxing Jiao, and Daxin Jiang. 2023. LED:; lexicon-enlightened dense retriever for large-scale retrieval. In Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX, USA, 30 April 2023- May 2023, pages 3203-3213. ACM.
Yair Weiss, Antonio Torralba, and Rob Fergus. 2008. Spectral hashing. In Advances Neural Information Processing Systems, volume 21. Curran Associates, Inc.
Shitao Xiao, Zheng Liu, Weihao Han, Jianjin Zhang. Defu Lian, Yeyun Gong, Qi Chen, Fan Yang. Hao Sun. Yingxia Shao, and Xing Xie. 2022a. Distill- vq: Learning retrieval oriented vector quantization by distilling knowledge from dense embeddings. In SIGIR 22: The 45th International ACM SIGIR Con- ference on Research and Development in Information Retrieval, Madrid, Spain, July 11 15, 2022, pages 1513-1523. ACM.
Wayne Xin Zhao, Jing Liu, Ruiyang Ren, and Ji-Rong Wen. 2022. Dense text retrieval based on pretrained language models: A survey. CoRR, 0ts/2211.14877
Yutao Zhu, Huaying Yuan, Shuting Wang. Jiongnan Liu, Wenhan Liu, Chenlong Deng, Zhicheng Dou, and Ji-Rong Wen. 2023, Large language models for information retrieval: A survey.
Shitao Xiao, Zheng Liu, Yingxia Shao, and Zhao Cao. 2022b. Retromae: Pre-training retrieval-oriented lan- guage models via masked auto-encoder. In Proceed- ings of the 2022 Conference on Empirical Methods in Natural Language Processing, EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 1, 2022, pages 538-548. Association for Computational Lin- guistics.
Justin Zobel, Alistair Moffat, and Kotagiri Ramamo- hanarao. 1998. Inverted files versus signature files for text indexing. ACM Trans. Database Syst., 23(4):453 490.
Lixin Zou, Shengqiang Zhang. Hengyi Cai, Dehong Ma, Suqi Cheng, Shuaiqiang Wang, Daiting Shi. Zhicong Cheng, and Dawei Yin. 2021. Pre-trained language model based ranking in baidu search. In KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singa- pore, August 14-18, 2021, pages 4014-4022, ACM.
Shitao Xiao, Zheng Liu, Yingxia Shao, Defu Lian, and Xing Xie. 2021. Matching- orreenee- embedding quan- tization for ad-hoc retrieval. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 1021, Virtual Event / Punta Cana, Dominican Republic, 7-11 November, 2021, pages 81 19-8129. Association for Computa- tional Linguistics.
Appendix
A Baseline Details
Sparse Retrievers. uments and queries with sparse vectors over the vocabulary, then estimate relevance with overlap- ping entries. The retrieval operation is acceler- ated with the efficient inverted index (Zobel et al., 1998). BM25 (Robertson and Zaragoza, 2009), the most basic sparse retriever. DocT5 (Cheri- ton, 2019), extending BM25 by appending pseudo- queries to documents. DeepCT (Dai and Callan, 2019), learning contextualized term weights us- ing BERT to replace the TD-IDF in BM25. Uni- COIL (Lin and Ma, 2021), learning contextualized term weights using BERT with contrastive learn- ing. DistiISPLADE (Formal et al., 2021), learning sparse term-weight vectors over vocabulary with knowledge distillation.
These methods represent doc-
Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang. Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. 2021. Approximate nearest neigh- bor negative contrastive learning for dense text re- trieval. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net.
Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Jiafeng Guo, Min Zhang. and Shaoping Ma. 2021a. Jointly optimiz- ing query encoder and product quantization to im- prove retrieval performance. In CIKM '21: The 30th ACM International Conference on Information and Knowledge Management, Virtual Event, Queensland, Australia, November 1 5, 2021, pages 2487-2496. ACM.
Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Jiafeng Guo, Min Zhang, and Shaoping Ma. lb. Optimizing dense retrieval model training with hard negatives. In SI- GIR 21: The 44th International ACM SIGIR Confer- ence on Research and Development in Information
Dense Retrievers with Brute Force Search (Flar). These methods encode documents and

---

queries into dense embeddings, then estimate rel- evance with embedding similarity. For each in- put query, all document embeddings are evaluated. DPR (Karpukhin et al., 2020), the most basic dense retriever. ANCE (Xiong et al., 2021); enhancing DPR with hard negatives mined from the previous model snapshot. CoCondenser (Gao and Callan, 2022), retrieval-oriented pretraining the encoder model to compress more information in the em- bedding. AR2 (Zhang al., 2022), adversarially train the encoder and ranker with knowledge dis- tillation. RetroMAE (Xiao et al., 2022b), retrieval- oriented pretraining the encoder model with a shal- low decoder and the representation bottleneck.
MS MARCO
NQ
Index
Codee
R@100
18
R
default
Flat
0,909
18
28
0.900
31
65
HC
defauit
0.916
3.0
0.906
15
7.1
Flat
17
28
Table 3: Evaluation of HI² with different codecs.
We use bert-base-uncased for the term selector. The passage is tokenized to 128 tokens before encoding. We employ the distilled OPQ (Xiao et al., 2022a) as the evaluation codec. KC is set to 30, Kf is set to 3. For training HI? sup we use the annotated ground truth document D 7 hard negatives sampled from B225 top 200 results, and in-batch negatives to form D.
Dense Retrievers with Approximate Nearest Neighbor Indexes (ANNs). These methods leverage ANN indexes to accelerate dense retrieval. IVF- PQ (Jégou et al., 201 la), the basic VQ index. IVF- OPQ (Ge et al., 2014), unsupervisedly learning a transformation orthogonal matrix for PQ to achieve higher accuracy. IVF-JPQ (Zhan et al., 2021a), op- timizing the PQ codebook with contrastive learning towards retrieval quality. Distill-VQ (Xiao al.. 2022a), optimizing the IVF centroids and PQ code- book with knowledge distillation from any off- the- shelf embeddings. HNSW (Malkov and Yashunin, 2018). a powerful graph-based ANN index that is widely used in modern search engines (elastic- search, 2015).
In practice, we find the terms selected by HI² results in much "denser" inverted lists than Himssup In other words, some terms may be frequently se- lected from multiple passages, translating to their super big inverted lists. This is especially the case for Natual Questions. Therefore, on NQ, we prune the super big inverted lists to a moderate size in- spired by static index pruning technique (Nguyen, 2009). Concretely, after indexing all documents, we count the size of each term-side inverted list, then take the one at the 7-th percentile (7 defaults to 0.996) as the threshold, whereby inverted lists bigger than the threshold are identified as "super big". Next, ascendingly order document refer- ences based on their individual score to the specific term of each super big inverted list. We prune the references from the head until the size of the in- verted list equals the threshold.
sup
B Implementation Details
For all methods involving clustering, we set the number of clusters L to 10000 and the number of probing clusters when searching 100 (except HI²).. For all methods involving PQ. we set the number of fragments m to 96, the number of sub- clusters & to 256, which results in 32 times smaller size than the full-precision one. For HI², we use the BERT'S vocabulary (Devlin et al., 2019) as the term vocabulary V. resulting in 30522 unique terms in total. K3 is always set to 32 for both HI2 Hussup
C Codec Analysis
Apart from the default PQ, HI2 can be combined with other codecs. In Table 3, we compare PQ with the most powerful yet most expensive Flat codec. It can be observed that HI& and HI both benefit from the more powerful codec. This indicates that 2 can return high-quality candidates universally applicable for different codecs. It also reveals that the current PQ codec still lossy. However, there is no free lunch: the powerful Flat codec comes with higher latency and higher index size, which is unfavorable for the index efficiency. In summary, again verify the practicality of HI", one may flexibly balance between higher effectiveness and higher efficiency.
and H sup-
For H1S Huunsup we use KMeans over all docu- ment embeddings to produce cluster embeddings {Ec, |-, BM25 to produce term scores 8, with a 0. 0.68, and OPQ (Ge et al., 2014) the evaluation codec, all of which are unsuper- vised algorithms. KC is set to 25, KT is set to 15. For H1S we initialize cluster embeddings with KMeans and optimize them afterwards. Note the cluster assignment (DD) is fixed once initialized.


Reviews:
[{"review_id": "7szchI4gAO", "reviewer": "Reviewer_4cBb", "summary": "", "questions": "A. I recommend measuring with brute force and the lexical+semantic score proposed, or some variation, to know how much precision/recall is missing due to the index approximation.\n\nB. Please mention what kind of input receives each ANN and what kind of similarity/metric is used in each case.\n \nC. Discuss the implications of using different representations for different ANN.\n\nD. HNSW and IVFPQ are sensitive to their hyper-parameters. Did you optimize their hyper-parameters?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, we appreciate your recognization of the idea and the emperical performance of HI$^2$. We provide the following clarifications in response to your questions. Hopefully, these clarifications may address all your concerns and help to improve your rating of our paper.\n\n> Methodology weaknesses: It is not clear if they are seeing the same information as the hybrid index. If they are seeing the same, it is fair and it is a matter of speed the comparison, if they are seeing differences it is a matter of the score but speed is not necessarily comparable, at least as how the manuscript presents results as compared with IVFPQ and HNSW.\n\nAll baselines see **the same information** as our method in the sense that all of them use the same text features for the queries and documents. However, they are differentiated in terms of how the representation is formulated on top of the text features. IVFPQ is based on the quantized semantic representation; HNSW is based on the semantic representation itself; our method (HI$^2$) is based on lexical representation and quantized semantic representation. IVFPQ (including all IVF-* and Distill-VQ), the sparse retrievers, and HI$^2$ are comparable in terms of speed, considering that all these methods are based on the inverted index. As for HNSW, the memory efficiency is comparable by measuring the index size. The running speed may not be directly comparable given that HI$^2$ and HNSW are based on different index structures. Their comparison is more of a reflection of the real-world performances when the two methods are applied (HNSW is based on the commonly used FAISS toolkit, whose implementation has been optimized and may serve as a proper indicator of its real-world performance).\n\n> A. I recommend measuring with brute force and the lexical+semantic score proposed, or some variation, to know how much precision/recall is missing due to the index approximation.\n\nThe brute-force search, which enumerates every document embedding for each input query, is denoted as **Flat** in our paper. It serves as the upper bound for all ANNs (including HI$^2$) given the same embedding model because ANNs only selectively evaluate a small number of documents for each query. Besides, the hybrid retrieval (i.e. lexical+semantic score) is orthogonal to our method, because we unifies the lexical and semantic features at index level for accelerating dense retrieval, rather than interpolating their scores for higher effectiveness.\n\nWe have reported the performance comparison with brute-force search in Table 1 in our paper, which is extracted and pasted below. It can be observed that HI$^2$ maintains a very little loss of precision (reflected by MRR) and recall compared with the upper bound. Particularly, HI$^2$ exhibits $-1.5\\%$ absolute point loss in MRR and $-1.1\\%$ absolute point loss in Recall with our default setting. However, it is indeed a tiny loss considering that there is more than x200 acceleration in terms of query latency.\n\n|Method|MRR@10|Recall@100|Query Latency (ms)|Index Size (GB)|\n|:-:|:-:|:-:|:-:|:-:|\n|Brute-Force Search (RetroMAE Flat)|0.416|0.927|1751|26|\n|HI$^2$|0.401|0.916|8|3.0|\n\n\n> B. Please mention what kind of input receives each ANN and what kind of similarity/metric is used in each case.\n\nAll ANNs are based on **the same embedding models** (RetroMAE for MSMARCO and AR2 for NQ, which were the strongest methods on the corresponding datasets when our experiment was conducted).  The similarity is  measured by inner product, which follows exactly the original settings of RetroMAE and AR2.\n\n> C. Discuss the implications of using different representations for different ANN.\n\nIn fact, all ANNs use **the same embedding model to produce semantic representations** (RetroMAE on MSMARCO and AR2 on NQ due to their highest brute-force search performance on the corresponding datasets when our experiment was conducted).\n\nFor HNSW/IVF-PQ/IVF-OPQ, the ANN index is directly constructed based on the representations produced by the same embedding model. Therefore, there is no difference between their representations.\n\nFor IVF-JPQ and Distill-VQ, the construction of their index calls for the adjustment of representations (i.e. the so-called joint optimization of index and embedding model). Thus, their representations are different from others. However, such a difference is introduced by the algorithms themselves, rather than our specification.\n\n> D. HNSW and IVFPQ are sensitive to their hyper-parameters. Did you optimize their hyper-parameters?\n\nWe have comprehensively evaluated the performance of IVFPQ and HNSW (and other ANN baselines) with different hyper parameters (`nprobe` and `efSearch` respectively) and report the effectiveness-efficiency trade-off in **Figure 3**, where HI$^2$ consistently outperforms ANN baselines under different configurations. Part of the experiment results are cited here for analysis (please refer to the original figure for the complete result).\n\n|Method|nprobe|efSearch|$K^C$ (#Clusters to Search)|$K_1^T$ (#Terms to Index)|Recall@100|Query Latency (ms)|Index Size (GB)|\n|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n|IVFPQ|50|--|--|--|0.722|8|**0.9**|\n|IVFPQ|100|--|--|--|0.763|13|**0.9**|\n|IVFPQ|500|--|--|--|0.829|51|**0.9**|\n|HNSW|--|100|--|--|0.784|**2**|28|\n|HNSW|--|500|--|--|0.887|6|28|\n|HNSW|--|1000|--|--|0.905|18|28|\n|HI$^2$|--|--|10|1|0.881|**2**|3.0|\n|HI$^2$|--|--|30|3|0.916|8|3.0|\n|HI$^2$|--|--|60|6|**0.921**|14|3.0|\n\nTwo critical facts can be observed:\n\n- HI$^2$ consistently and substantially outperform IVFPQ and HNSW with competitive or faster running speed. For example, given 2ms latency, HI$^2$ surpasses HSNW by $+9.7\\%$ absolute point in Recall@100; given roughly 14ms latency, HI$^2$ surpasses IVFPQ by $+15.8\\%$ absolute point in Recall@100.\n- The effectiveness of IVFPQ and HNSW benefit from larger `nprobe` and `efSearch`, respectively, yet with the cost of running speed. In HI$^2$, we can also adjust the hyper paremeters to achieve higher effectiveness with the cost of speed. It achieves the highest Recall@100 by doubling the number of clusters to search and the number of terms to index. Note that we do not need to re-build the inverted index even when we increase the number of terms to index due to our filtering-based implementation with Numpy ([anonymously open-sourced](https://anonymous.4open.science/r/HI2/src/utils/index.py)).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The hybrid inverted index that it is fast and precise.\n- It provides a way to combine lexical and semantic scores smoothly\n- It introduces a way to distill the data to become smaller, and faster, while maintaining precise", "reasons_to_reject": "Methodology weaknesses: It is not clear if they are seeing the same information as the hybrid index. If they are seeing the same, it is fair and it is a matter of speed the comparison, if they are seeing differences it is a matter of the score but speed is not necessarily comparable, at least as how the manuscript presents results as compared with IVFPQ and HNSW.\n", "questions_to_authors": "A. I recommend measuring with brute force and the lexical+semantic score proposed, or some variation, to know how much precision/recall is missing due to the index approximation.\n\nB. Please mention what kind of input receives each ANN and what kind of similarity/metric is used in each case.\n \nC. Discuss the implications of using different representations for different ANN.\n\nD. HNSW and IVFPQ are sensitive to their hyper-parameters. Did you optimize their hyper-parameters?", "paper_topic_and_main_contributions": "The manuscript describes a hybrid lexical and semantic inverted index for dense retrieval. The lexical component provides speed and precision due to terms; the semantic component allows to connect concepts beyond words. The semantic component works by clustering documents and creating meta-words that can be used to accumulate entries in the posting lists of the index. The approach includes a score function and a strategy to optimize lexical and semantic \"words\" selection.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "Table 1, Fig 3, Fig 4, Line 145. Natual -> Natural\n"}, "extra_text": {}}, {"review_id": "yH8CEQtwVL", "reviewer": "Reviewer_wBPq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, thank you for your recognization of the idea, the writing, and the emperical performance of our work. We sincerely appreciate your input and value the opportunity to address your questions. We hope the following clarifications may address all your concerns and help to improve the current rating of our paper.\n\n> In the experiments, only the query latency is given. The setup latency should also be given.\n\nWe evaluate the setup latency by measuring the time cost for constructing the index on MSMARCO. The results are reported in the following table:\n\n|Method|Setup Latency (minutes)|\n|:-:|:-:|\n|IVF-PQ, IVF-OPQ, IVF-JPQ, Distill-VQ|30|\n|HNSW|45|\n|HI$^2$|41|\n\nThe setup of HI$^2$ takes a little more time than the conventional IVF-PQ/IVF-OPQ, because HI$^2$ needs to set up the inverted index for both lexical and semantic representations; however, the setup is faster than HNSW. It should be noted that the setup of index only needs to be conducted once in the offline stage. Therefore, the above difference won't be a bottleneck of HI$^2$'s application in practice.  \n\n> The usage of “lossless retrieval quality” is easy to be confusing.\n\nWe are sorry for the confusion caused for you. In our experiment, we treat the brute-force search of all documents (Flat) as the upper bound of retrieval quality. According to Table 1, HI$^2$ achieves Recall@100 of $0.916$ on MSMARCO and Recall@20 of $0.861$ on NQ, which is very close to the upper bound performance. We will think about a better term to describe this property.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. The idea to combine embedding clusters and salient terms is interesting.\n2. The paper is well organized. The description of the method design and implementation is clear and easy to follow.\n3. The experimental results prove the effectiveness and efficiency of the proposed method on two popular benchmark datasets.", "reasons_to_reject": "1. In the experiments, only the query latency is given. The setup latency should also be given.\n2. The usage of “lossless retrieval quality” is easy to be confusing.", "questions_to_authors": "", "paper_topic_and_main_contributions": " This paper deals with the retrieval quality of dense retrieval and proposes a Hybrid Inverted Index that uses the embedding clusters and salient terms collaboratively to accelerate dense retrieval. It achieves lossless retrieval quality with competitive efficiency across a variety of index settings. The source code is provided.", "excitement": 3, "reproducibility": 5, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "There are some typos such as “IVF-Flat and DistillIVF-Flat achieves recall” ([pdf](zotero://open-pdf/library/items/WJ33MJVQ?page=2)) , “2) Natural Questions (Kwiatkowski et al., 2019).”"}, "extra_text": {}}, {"review_id": "BYtwUIEEVU", "reviewer": "Reviewer_8PkW", "summary": "", "questions": "What is the space overhead or memory consumption of propose techniques?", "limitations": "", "rating": 3, "confidence": 2, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer, we highly appreciate your recognization of the topic importance, the writing, and the technical depth of our work. We sincerely appreciate your input and value the opportunity to address your questions. We hope the following clarifications may address all your concerns and help to improve the current rating of our paper.\n\n> There is no result about space overhead. What is the space overhead or memory consumption of propose techniques?\n\nWe report the memory consumption on MSMARCO when running ANN baselines and HI$^2$ (using their default settings and the Faiss toolkit) in the following table:\n\n|Method|Memory Consumption (GB)|\n|:-:|:-:|\n|IVF-PQ, IVF-OPQ, IVF-JPQ, Distill-VQ|2.6|\n|HNSW|30.5|\n|HI$^2$|4.1|\n\nIt can be observed that the conventional IVF-PQ index family are the lightest. HI$^2$ consumes more memory because it needs to store the term-side inverted lists. However, since there are only a few terms selected from each document, the overhead is not so much. By comparison, HNSW consumes much more memory than IVF-PQ and HI$^2$, because it needs to store a big graph in the memory. \n\n> Some latest related works from the field of high dimensional similarity search are ignored such as [1]. They have been proved to have better performance than graph based methods such as HNSW compared here.\n\nWe agree that some recent ANN indexes achieve better performance than HNSW, despite that HNSW is one of the most commonly used methods. However, we find that [a] is about LSH; according to the authority benchmarks on ANN (https://ann-benchmarks.com, https://github.com/erikbern/ann-benchmarks), HNSW is way more accurate than LSH under the same query throughput. Instead, we choose a well-known improvement of HNSW: NSG , for further experiment. \n\n|Method|Recall@100|Query Latency (ms)|Index Size (GB)|Memory Consumption (GB)|\n|:-:|:-:|:-:|:-:|:-:|\n|HNSW|0.887|6|28.0|30.5|\n|NSG|0.899|7|27.0|63.0|\n|HI$^2$|0.916|8|3.0|4.1|\n\nWe may observe that using NSG indeed improves the retrieval quality. However, compared with HI$^2$, it has much bigger memory consumption, and inferior recall performance.\n \nIt should be noted that although many recent ANN methods claimed improvements in different scenarios, HNSW and its close variations remain the dominant approaches and are widely referenced as competitive baselines in the area of information retrieval and semantic search [b,c,d]. They are also the most intensively used methods in libraries like Milvus and FAISS. Thus, the notable advantage over HNSW is indeed a strong indicator of HI$^2$'s value. \n\n[a] Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph. Fu, Cong, et al., Proceedings of the VLDB Endowment 12.5. \n\n[b] Jointly Optimizing Query Encoder and Product Quantization to Improve Retrieval Performance, Zhan et. al., CIKM'21\n\n[c] Learning Discrete Representations via Constrained Clustering for Effective and Efficient Dense Retrieval, Zhan et. al., WSDM'22\n\n[d] Constructing Tree-based Index for Efficient and Effective Dense Retrieval, Li et. al., SIGIR'23\n\n> The comparison with some inverted list based sparse retrieval methods are missing. There are some works about compression over inverted lists and perfrom similarity search on them such as [2] [3]. They could also be extended as baseline methods. Since they are optimized, they should perform better than the selected sparse method here.\n\nThe listed references are about modification of inverted index [2] [3], such that the index can be more lightweight and efficient. Our method is not about modifying the inverted index, but unifying and optimizing the semantic and lexical features for the index, so that the retrieval quality can be improved. In other words, the listed references target on a parallel research direction with our work.\n\nThe listed references are important works in their own field. If they can be extended and applied to common indexes on semantic search, like Lucene and FAISS, there will probably be an opportunity to make combination with HI$^2$ for further improvement.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "* The research topic is important.\n\n* The paper is well written.\n\n* The proposed techniques are solid.", "reasons_to_reject": "* Some latest related works from the field of high dimensional similarity search are ignored such as [1]. They have been proved to have better performance than graph based methods such as HNSW compared here.\n\n* The comparison with some inverted list based sparse retrieval methods are missing. There are some works about compression over inverted lists and perfrom similarity search on them such as [2] [3]. They could also be extended as baseline methods. Since they are optimized, they should perform better than the selected sparse method here.\n\n* There is no result about space overhead.", "questions_to_authors": "What is the space overhead or memory consumption of propose techniques?", "paper_topic_and_main_contributions": "This paper studied the problem of dense retrieval. It aims at improving the document embedding for clustering as well as accelerate the retrieval process. To this end, the authors proposed a hybrid inverted index which combines the advantage of dense retrieval and lexical matching. The authors also proposed learning techniques for term and cluster selection with a joint optimization solution. Experiments are conducted on several popular datasets and the results look promising.\n", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "[1] MQH: Locality Sensitive Hashing on Multi-level Quantization Errors for Point-to-Hyperplane Distances. PVLDB 2022. https://www.vldb.org/pvldb/vol16/p864-lu.pdf\n\n[2] Highly Efficient String Similarity Search and Join over Compressed Indexes. ICDE 2022. https://ieeexplore.ieee.org/document/9835221\n\n[3] MILC: Inverted List Compression in Memory. VLDB 2017. http://www.vldb.org/pvldb/vol10/p853-wang.pdf"}}]

Author rebuttal:

Meta-review: The paper proposes a Hybrid Inverted Index that utilizes the embedding clusters and salient terms collaboratively to improve the quality and speed of dense retrieval.
All the reviewers have agreed that the paper has its merits in smoothly combining lexical and semantic features as an inverted index and bringing an instant speedup.
However, common concerns have also been raised by the reviewers that either the most recent baselines are missing or the speed reports are not very complete, making the results not that convincing. 
During the rebuttal period, these concerns seem to be largely addressed.
Decision: Accept-Main