Model-enhanced Vector Index
Authors: Hailin Zhang
Yujing Wang
Qi Chen
Ruiheng Chang
Ting Zhang
Ziming Miao
Yingyan Hou
Yang Ding
Xupeng Miao
Haonan Wang
Bochen Pang
Yuefeng Zhan
Hao Sun
Weiwei Deng
Qi Zhang
Fan Yang
Xing Xie
Mao Yang
Bin CUI
Venue: NeurIPS 2023 poster (2023)
Keywords: document retrieval
model-based index
dense retrieval
residual quantization

Abstract: Embedding-based retrieval methods construct vector indices to search for document representations that are most similar to the query representations. They are widely used in document retrieval due to low latency and decent recall performance. Recent research indicates that deep retrieval solutions offer better model quality, but are hindered by unacceptable serving latency and the inability to support document updates. In this paper, we aim to enhance the vector index with end-to-end deep generative models, leveraging the differentiable advantages of deep retrieval models while maintaining desirable serving efficiency. We propose Model-enhanced Vector Index (MEVI), a differentiable model-enhanced index empowered by a twin-tower representation model. MEVI leverages a Residual Quantization (RQ) codebook to bridge the sequence-to-sequence deep retrieval and embedding-based models. To substantially reduce the inference time, instead of decoding the unique document ids in long sequential steps, we first generate some semantic virtual cluster ids of candidate documents in a small number of steps, and then leverage the well-adapted embedding vectors to further perform a fine-grained search for the relevant documents in the candidate virtual clusters. We empirically show that our model achieves better performance on the commonly used academic benchmarks MSMARCO Passage and Natural Questions, with comparable serving latency to dense retrieval solutions.

Model-enhanced Vector Index
Hailin Zhang!.2. Yujing Wang2. Qi Chen² Ruiheng Chang?
Ting Zhang²
Ziming M Yingyan 23. Yang Ding? Xupeng Miao
Haonan Wang
Bochen Pang" Yuefeng Zhan? Hao Sun? Weiwei Deng?
Qi Zhang?
Fan Yang² Xing Xie Mao Yang" Bin Cui
School of Computer Science & Key Lab of High Confidence
Software Technologies, Peking University "Microsoft
3 "Arrsspace Information Research Institute & Key Laboratory of Target
Cognition and Application Technology, Chinese Academy Sciences
"nnttitute of Information Engineering, Chinese Academy of Sciences
*Carnegie Mellon University National University of Singapore
National Engineering Laboratory for Big Data Analysis and Applications, Peking University
hl, bin. cui cui) edu.
2 [yujwang, cheqi, ruihengchang, tinzhan, zimiao, bopa] @microsoft.....mmmmmmomo com
[yuefzh, hasun, dedeng, qizhang, fanyang, xingx, maoyang) 0mi crosoft. com "houyy@aircas, ac. cn "dingyang@iie ac.cn *xupengücmu. edu hhaonan. "haonan.wanguu. nus.
Abstract
Emhedding- based retrieval methods construct vector indices to search for document representations that most similar the query representations. They widely used document retrieval due to low latency and decent recall performance. Recent research indicates that deep retrieval solutions offer better model quality, but are hindered by unacceptable serving latency and the inability to support document updates. In this paper, aim enhance the vector index with end- to-end deep generative models, leveraging the differentiable advantages of deep retrieval models while maintaining desirable serving efficiency. We propose Model- enhanced Vector Index (MEVI), a differentiable eenene-n index empowered by a twin-tower representation model. MEVI leverages a Residual Quantization deep retrieval and embedding-
(RQ) codebook to bridge the requence-to-seqeene based models. To substantially reduce the inference time, instead of decoding the unique document ids in long sequential steps, we first generate some semantic virtual cluster ids candidate documents leverage the well-adapted embedding vectors further perform a fine- -reigga search for relevant documents in the candidate virtual clusters. empirically show that our model achieves better performance the commonly used academic benchmarks MSMARCO Passage and Natural Questions, with comparable serving latency to dense retrieval solutions.
small number of steps, and then
Introduction
A web search engine basically consists of two key stages, document retrieval and ranking [52, 24, 47, 9]. The document retrieval stage retrieves candidate documents related the query, while the ranking stage re-ranks the documents using precise ranking scores. Accurate ranking models are usually deep neural networks that predict query and document relevance scores [17, 13). guarantee low latency
The work was done Microsoft. Corresponding authors.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

in online systems, such ranking models can only support hundreds or thousands of documents per query, requiring the retrieval stage to recall relevant documents precisely. Therefore, improving the quality of retrieval models is of great significance to improve the effectiveness of web search engines.
Existing methods of document retrieval can be roughly divided into three categories, namely term- based, embedding- baasdd and generation- based methods [14, 46]. sparse retrieval, build an inverted index upon words or phrases from the whole corpus for searching [4, 56]. However, they are not aware of document semantics information and may miss target documents with different wordings. Embedding--aat -baeed methods, also called dense retrieval, are proposed to leverage semantics information [52, 28]. They encode queries and documents to dense embedding vectors by a twin-tower architecture, then build a vector index and apply Approximate Nearest Neighbor (ANN) search to retrieve relevant documents for queries [12]. Such methods are widely used in real applications, since they have decent recall performance and low serving latency. Although these methods prevail in industry. they cannot fully leverage the power of deep neural networks because they are not end-to-end differentiable due to the necessity of ANN index. They suffer from the discrepancy between brute-force K-Nearest Neighbor (KNN) and ANN. The discrepancy leads to a non-trivial gap in recall performance of KNN and ANN [49].
methods, also called
Recently, generation-based methods [44, 46] are proposed to tackle the limitation of embedding- -basd retrieval solutions. Typically, a generation- based model adopts generating document identifiers directly based on the given queries. To achieve better results, the document identifiers need to reflect effective priors of the document semantics. For example, SEAL [2] leverages the n-grams itself as identifiers. In DSI [44] and NCI [46], documents are organized as a tree by hierarchical KMMaas clustering [15], and identifiers are the codes of paths from the root to the leaf nodes. Though such methods reach better recall performance than embedding- based retrieval models on small corpus (containing less than I million documents), they have difficulty in scaling to larger corpus (containing more than 10 million documents), and can not be served online in industrial systems due to high latency and immutable corpus. To train a deep retrieval model that indexes larger dataset, we need much more parameters to memorize all documents semantics, and the decoder needs to compute more times by beam search at inference. Another blocking issue is that the tree index is fixed during training and inference, posing a significant challenge for adding or removing documents. As a result, the model needs to be retrained every time the corpus changes. Overall, generation-base corpus. To the best of our knowledge, they have not been successfully used in real applications with large-scale corpus due to these non-trivial challenges.
sauuuence-tosequenee architecture,
retrieval methods are time-consuming and only applicable to static small
In this paper, we aim to address the aforementioned constraints of model-based methods while preserving their benefits. We propose Model-enhanced Vector Index (MEVI), which enjoys high recall performance as well as fast retrieval speed on large-scale corpus. Specifically, we construct a Residual Quantization (RQ) codebook to cluster the documents first. The RQ codebook preserves the hierarchical structure of the document clusters, which is inherently suitable for autoregressive generation. Thereafter, we build sequence-to-seeee to-sequence model to encode user queries and directly generate virtual cluster identifiers according to the RQ codebook; then we conduct efficient ANN method to search embedding vectors which are semantically relevant the virtual cluster. During training, ground-truth data and augmented query- query-document pairs are fed into the model. During inference, the top K document clusters are retrieved from the RQ codebook via beam search on the decoder, and an ANN search process is conducted based on the query embedding as well as the retrieved document embeddings corresponding to the clusters. Our MEVI design solves the limitations of both traditional embedding -baed methods and generation based methods. On the one hand, we can limit the RQ codebook to a moderate size to reduce the computation time of the autorogressive decoder and thus ensure low latency. On the other hand, MEVI enables insertion or removal of documents to RQ-based index structures, such that new documents can be recalled if their virtual clusters with related semantics can be generated by the selecting a suitable size for the RQ codebook, we can balance the recall performance and the inference latency. This allows us to leverage the high efficiency of ANN and the accurate recall of deep retrieval models simultaneously. The code of MEVI is available at:
model. By
Our contributions are highlighted as follows.
For the first time, we demonstrate that a novel-designed iemeration-enhancee model is able to handle a large corpus with millions of documents, reaching high recall performance and low serving
2

---

latency at the same time. The proposed MEVI provides unified solution for document retrieval, incorporating the advantages of both embedding- based methods and generation basedd methods.
In our experiments, MEVI significantly improves the recall performance compared to existing methods, achieving +3.62% % / +7.32% % / ++0.544% of MRR@ 10 / R@ 50/ / R @ 1000 on the MS- MARCO Passage dataset and +5.04 % +5.466% +5..66% % Rf R @@20 r@ 100 on the Natural Questions dataset with low latency capable of serving. Importantly We also validate MEVI's capability in addressing dynamic corpora effectively.
-eesuueeee model support training and serving on large-scale retrieval datasets. As verified by experiments and analysis, the RQ structure allows for dynamic updates of documents and enables better model performance with low serving lateney.
We propose novel RQ-based
2 Related work
Document retrieval aims to find relevant documents that match a user's query. The core idea of document retrieval is to build an index for vast number of documents to guarantee fast query response, Document retrieval methods can be divided into three categories.
Traditional sparse retrieval methods build on top of an inverted index using term matching metrics such as TF-IDF [41], query likelihood [23], and a hard-to-beat baseline BM25 [42] in industry-scale web search. Unfortunately, these methods do not take into account the semantics of documents, which can lead to the overlooking of target documents with different wordings.
Dense retrieval methods represent queries and documents using dense embedding vectors, and build ANN index speed up the search. These methods take advantage of recent advances in pre-trained language models to encode queries and documents into dense representations, such as BERT [8] and RoBERTa [27]. During training, dense retrieval generally follows the contrastive learning paradigm. During inference, ANN methods are applied to search relevant documents, such as tree [1. 25], locality sensitive hashing [6], neighbor graph index (e.g., HNSW [30], DiskANN [43], HMANN [40], the combination of graph index and inverted index (e.g., SPANN [3]), Sparse retrieval and dense retrieval can be combined [29] to achieve better search quality. However, the discrepancy between KNN and ANN presents challenge for these methods, particularly in scenarios where there is a significant distribution difference between documents and queries. Besides document retrieval, embeddings are also utilized in cross-modal retrieval [55, 18), graph [5, 19), recommendation [32, 33), etc.
Autoregressive retrieval is new paradigm retrieve relevant documents. It uses end-to-end autoregressive model that takes queries as input and directly generates document identifiers as output. Differentiable Search Index (DSI) [44] and Neural Corpus Indexer (NCI) [46] are the first attempts to propose differentiable indexes for semantics search that directly map queries to relevant document identifiers. DSI generates document identifiers with document tokens, and designs multi-task training for augmentation. NCI builds a tree index by hierarchical KMeans clustering, and represents each file decoder and uses augmented
by the path from root to leaf on the tree. It designs a data to further improve performance. SEAL [2] leverages autoregressive models in another way, generating n- n-grams and retrieving documents through a pre-built FM-index for n-grams. However, they are all limited by unacceptable serving latency and the inability to handle document updates.
3 Model-enhanced vector index
In this paper, we propose a novel Model-enhanced Vector Index (MEVI) to address the above limitations of both embedding- dense retrieval methods and generation autoregressive retrieval methods. The goal of MEVI is to achieve both fast retrieval speed, like dense retrieval methods, and high recall performance, like autoregressive retrieval methods, by leveraging the strengths of both approaches.
MEVI adopts an autoregressive sequence-to-ssquenee model as the enhancing model and well- adapted twin-tower representation model as the vector index. The twin-tower model encodes queries and documents into embedding vectors for common embedding- based retrieval. The autoregressive pequence-to-sqquene
model takes the same queries as input and outputs the most relevant document clusters. To organize documents into hierarchical clusters, MEVI employs Residual Quantization [31], which first clusters the document embeddings and then iteratively clusters the residual embeddings. During each clustering pass, the residual embeddings are computed by subtracting the cluster cen- troid embeddings from the embeddings used in the previous pass. RQ is essentially hierarchical
3

---

Document Embeddings
K-Means Clustering
Ground-Truth Documents
Query
Encoder
Codebook
Subtract Centroid Embeddings
Iterative X3
Residual Embeddings
7-355
K- K-Means Clustering
9668
5-3-4
Embodeings
Decoder
Training
Document
Documents
Representa tion Model
ANN Search
Candidates from ANN
Finel Candidates
Quary Embodding
Candidates
Query
Seq25eq Model
RQ Clusters
Chasters
8-3-2
Top-k Clusters
(b) Inference
Figure 1: Overview of Model-enhanced Vector Index (MEVI). (a) Training. Document embeddings and residual embeddings are iteratively clustered to form the RQ structure; then the RQ structure provides cluster codes as labels for the training of eeguenceeto-sequence model. (b) Inference. The query is fed into the representation model and the sequence-to-sequene model respectively to get candidates from ANN and clusters; then ensemble strategies are performed to get final candidates.
KMeans [15] algorithm, where similar documents assigned to the same close clusters. Docu- ment clustering not only works in traditional clustering- baaedd retrieval [45, 26). but also suitable for autoregressive sequence- cnvencc-to-sequenee to-sequence models mentioned in DSI [44] and NCI [46]. Once the results are obtained from the autoregressive model and the twin-tower model, MEVI ensembles the results to form the final document candidates. The whole workflow is shown in Figure 1.
3.1 Organizing documents with Residual Quantization
Twin-tower representation models [38, 11, 51] designed for dense retrieval, also known as embedding- retrieval. They separately encode queries and documents into embeddings, and perform similarity search (e.g. Euclidean, cosine, inner product) on the embeddings retrieve relevant documents for given queries. Our method utilizes information from autoregressive sequence- to sequence models to significantly and accurately narrow down the range of candidate sets. We use the state-of-the-ar the-art twin-tower models AR2 [54] and T5-ANCE [51] in our experiments. It is worth noting that the improvement
theoretically be applied to any twin-tower representation models.
To build an autoregressive seqeence-t-sequenee kind of data structures. In DSI [44] and NSI [46], documents are hierarchically clustered through the KMeans algorithm [15] to form tree, and the T5 model [39] is used to encode the query and decode into document identifier represented by a path the tree. The tree structure, however, cannot support large-scale corpus real applications due to its long sequential decoder steps.
task, documents need to organized into some
Vector quantization is useful method to compress document embedding representations. Instead of the commonly used Product Quantization which splits embeddings along dimension, we leverage Residual Quantiztaion (RQ) to preserve the hierarchical semantics of documents. The construction of RQ codebook process iterative clustering. Concretely, assume the initial document embedding is X E [Raxd the first K.Maans clustering is performed X to get the centroid embeddings B, b also known as codewords, and the one-hot clustering assignment C₁ E {0, 1]=xb, also known codes. Then the second clustering is performed the residual embeddings R₁ = X C₁

---

rather than the original document embeddings X. Codewords B2 and codes C2 are obtained in this step. Then the residual R₂ R C2B₂ fed into the third clustering, and the process continues till pre-defined number of steps is reached. After all the clustering process, the overall codebook is obtained as B- [ B2, .... Bm] E Rmmbxd and the overall codes for documents are C' = - C2 CHIT" {0, 1 the iterative clustering can be seen as solution to the minimization problem min || CB The explanation of symbols are detailed in Table 1.
Table I: Notations.
Notation
Explanation
The number of documents
d
Embedding dimension
log2 b
The bit number of compact codes
The number of centroid embeddings for each clustering
m
The number of clustering layers, i.c. the length of cluster-id
X E 1xxd
All document embedding
B, E Rixd
i = 1, m
Centroid embeddings of clusters
Rmbxd
Overall centroid embeddings
C, {0, 12xbb i
m
Code-style assignment of documents
C' {0, 1 jaxmb
Overall cluster assignment
ČE (0, 1, 2,....b. 13 1
Overall compact cluster assignment
k
The number of retrieved clusters
The number of retrieved documents (for R@K, MRR@K)
G, = 1,..., h
Top-k retrieved clusters
Rg E Ruxd i = 1, 11
Residual embeddings after clustering
$0: Sc
Scoring function for embedding similarity and cluster ranking Cluster ranking function
Te a, 3
Hyperparameters of the ensemble process
Both RQ codebooks and hierarchical trees are constructed using iterative clustering. The difference that RQ clusters the residuals and maintains fixed step length. Considering that the clustering process is essentially the classification of documents, RQ's clustering of residuals can be regarded as classifying documents in more and more refined manner. On the other hand, all codes in RQ are of length m, making the latency of the autoregressive process stable and acceptable.
After the RQ construction process, we obtain the codes of documents C, compact version C E (0, 1.2. b ]]"*m instead of one-hot vectors, with each code an index of the codebook in the corresponding step. In the decoding process of autoregressive sequence-to-sequee
models, the code Č is generated step by step during inference until step m, with the vocabulary of each step {0, 1, .... b }}. We consider documents to be from the same cluster only their codes are identical. Therefore,
regard the results from the sequence-to-seve to-suueence model clusters with top-k probability of containing relevant documents. With the mapping of document to code Č, the scquence-to-sequene model can be trained with large collection of < query, code > pairs derived from < query, document pairs.
3.2 Ensemble process
Given the top-k retrieved clusters (2,,,,,..., (x) from the autoregressive sequence-to-seequence model, incorporate such information into embedding- retrieval. The rest of this section explores some possible options to ensemble the top-k cluster information.
Search only in candidates from top-k clusters. A straight-forwan strategy is to only search relevant embeddings within top-k clusters. This strategy assumes that the sequence-to- suneence-to-sqqueee to--squeeeee model has already retrieved relevant documents by retrieving top-k related clusters, greatly reducing the number of candidates for embedding similarity search.
Ensemble the original embedding search results with the candidates from the top-k clusters. Considering that RQ structure may inaccurate, and the beam search process a lossy greedy algorithm, the retrieved top-k clusters may not contain all the relevant documents. A more robust
5

---

method is to combine candidates from common embedding saabedding-basedd based retrieval and top-k clusters. The original similarity score is not applicable for re-ranking these candidates, since the first candidate set already contains the best documents under this similarity metric. Therefore, we design new score for re-ranking, also leveraging the information of retrieved top-k clusters. Assume 80 denotes the original scoring function for embedding similarity, 8 denotes the cluster scoring function of documents, a denotes the coefficient of cluster scores, æ is random document, the new score is:
s (z) = so + a (c())
The cluster scoring function can be a function of the cluster ranking:
8x(2) 3 rc(x) +1
where Te denotes the cluster ranking function of documents, 8 is another hyperparameter. For documents that are not in the top-k clusters, we simply use zero or a value smaller than the minimum cluster score.
4 Experiments
In this section, we conduct various experiments to verify the effectiveness and the efficiency of MEVI. We first introduce the datasets and the evaluation metries be used (Section 4.1), and then describe the implementation details of MEVI and other baseline methods (Section 4.2). We demonstrate and analyze the effectiveness of MEVI examine the ability of MEVI to handle unseen documents (Section 4.5), and explore the effectiveness of RQ (Section 4.6). We also examine the efficiency of MEVI (Section 4.7), study the impact of hyperparameters (Section 4.8) and apply our method to practical applications (Appendix A).
large-scale datasets (Section 4.3, 4.4),
4.1 Datasets metrics
Datasets. We conduct experiments two widely used large-scale document retrieval benchmarks, i.e. MSMARCO [34] Passage Retrieval dataset and Natural Questions (NQ) [22] dataset. MSMARCO is question answering dataset formulated by Microsoft in 2016. It consists of real Bing questions and sunaangeneraatd answers. The version we use is the MSMARCO Passage Retrieval dataset, which contains 8.8 million passages and around 5 510,000 queries. NQ is large open-domain question answering dataset containing queries collected from Google search logs. DPR [21] selected around 62,000 factoid questions and processed all the Wikipedia articles (21 million) as the collection of passages. We use the DPR version for evaluation. For both datasets, we use their predetermined training and validation splits for evaluation.
Metrics. To reflect whether relevant documents are retrieved given a user query, we employ Recall K and MRR @ K. two widely accepted information retrieval evaluation metries. R@K (short for Recall K) measures the proportion of relevant items found among the retrieved top- candidates. A higher recall means that there (mean reciprocal rank) calculates the reciprocal of the rank at which the first relevant document is retrieved within top-K candidates. A higher MRR indicates that the relevant document is retrieved with higher rank.
relevant documents among the top-K candidates. MRR @RR@K K
4.2 Implementation details
RQ codebook. By default, we use an RQ codebook with 4 clustering layers and 5 bits per layer. In each layer, we use the default KMeans algorithm provided by scikit-learn [37], where the number of centroids is 2 32. The entire RQ has 32 = 1, 048, 576 clusters, and each cluster contains an average and 20 documents in two datasets. We tested other configurations of RQ in Section 4.6.
model. We leverage Neural Corpus Indexer (NCI) [46], the state-of-the-art sequence-to-se tow-uue--eeeeeeeeeeeeeeeeeeeeeee model for document retrieval. We replace its original decoder vocabularies with our RQ structure, and train NCI upon the processed < query, code > pairs. For data augmentation, we employ the "document as query" technique and use DocTSQuery [35] as suggested in NCI, generating 10 queries per document for MSMARCO Passage, and 1 query document for NQ. We use the same optimizer and learning rate as NCI; however, we use a larger batch size, 256 per GPU, and disable Rdrop reduce the overall training cost. For inference,
Sequence-to-sequeee
beam search with a beam

---

size of 10 to 1000. All experiments of NCI are conducted on an NVIDIA V100 GPU cluster with 32GB memory per GPU, and each job runs on GPUs.
Twin-tower representation model. We use T5-ANCE [36] to generate embeddings for RQ clus- tering. T5-ANCE is effective embedding- retrieval model which replaces the backhones of ANCE [51] with T5 [39]. We use T5-ANCE and AR2 [54] to generate embeddings for ensembling. AR2 is the ofate-of-the-art twin tower retrieval model. These two methods have different backbone models, indicating that our method can be applied to different twin-tower representation models. To obtain the search result from embedding based retrieval, we adopt HNSW [30], novel ANN search technique implemented in Faiss [20], with 256 neighbors per vertex. We have also tried more neighbors per vertex but got no gain compared 256.
Ensemble. All the ensemble strategies require searching among the top-k clusters retrieved by the loquence-to-sqqeemee model. Instead of performing ANN search in traditional umbedding-basee based retrieval, we employ brute-force search in top-k clusters. This is because the number candidates in the top-k clusters is relatively small, typically on the order of ten thousand, given beam size of 1000. The hyperparameters of the ensemble are determined through grid-search. We study the impact of hyperparameters in Section 4.8.
Baselines. We compare our method with sparse retrieval methods BM25 [42] and SPLADE [10), dense retrieval methods T5-ANCE and AR2 with ANN, and model-basee retrieval NCL The compar- isons with T5-ANCE/AR2 and NCI also reflect the gain of ensemble strategies. For NCI, we build a hierarchical tree with depth of 8. The other hyperparameters of the baseline methods remain the same as the original papers.
4.3 Results on MSMARCO Passage
Table 2 presents the retrieval results on MSMARCO Passage dataset. We compare different ensemble strategies of MEVI with baselines. We report the results of searches in the 10p110, top- 100, and t0p-1000 clusters, and the ensemble of these results with the embedding based retrieval methods. Among all the tested methods, the ensemble of embedding- based retrieval and generation-bast retrieval outperforms all baselines. Compared to the ANN baseline, MEVI improves 3.62% / 2.62% for MRR @ 10, 7.32% / 5.43% for Recall 50, 10.54% 8.00% for Recall @ 1000 on AR2 / T5-ANCE respectively. The more clusters be considered, the better the retrieval performance. Even without ensemble, vanilla MEVI performs better than dense retrieval methods when considering top-1000 1000 clusters. After ensemble, MEVI can achieve better results than ANN with only top- 10 clusters, which shows that the ensemble combines the advantages of ANN and top-k clusters, making them complement each other. Compared NCI, MEVI performs better especially on MRR @ 10, because MEVI utilizes generation-base retrieval with smaller decoder steps, allowing the model to learn better ranking.
Table 2: Experiment results on MSMARCO Passage (Dev).
Method
MRR@) @ 10
R 5@5
R @@ 1000
BM25
18.7
59.2
85.7
SPLADE
32.2
95.5
T5-ANCE (HNSW)
33.21
77.30
88.61
AR2 (HNSW)
35,54
78.80
87.11
NCI
26.18
74.68
92.44
MEVI Top-10 Clus
32.05
63.25
66.82
MEVI Top-100) Clus
35.16
79.14
88.22
MEVI Top-1000 1000 Clus
35.76
82.37
95.17
MEVI Top-10 10 Clus T5-ANCE (HNSW)
35.22
81.29
93.21
MEVI Top-100 Clus & T5-ANCE (HNSW)
35.60
82.27
95.62
MEVI 1000 Clus & T5-ANCE (HNSW)
35.83
82.73
96.61
MEVI Top-10 Clus & AR2 (HNSW)
37.00
82.64
93.46
MEVI 100 Clus & AR2 (HNSW)
38.42
84.52
96.23
MEVI 1000 Clus & AR2 (HNSW)
39.16
86.12
97.65

---

4.4 Results on Natural Questions
Table 3 presents the retrieval results on Natural Questions dataset. Compared the ANN baseline, MEVI improves 5.04% for Recall 55, 5.46% for Recall @ 20, 5.96% for Recall @ 100 on AR2 model. Vanilla MEVI also performs better than AR2 (HNSW) when searching among top- 1000 clusters. After ensemble, MEVT can outperform AR2 (HNSW) with only 10 clusters.
Table 3: Experiment results on Natural Questions (Test).
Method
R@5
R @ 20
R@ 100
BM25
59.1
73.7
AR2 (HNSW)
70.89
78.50
83.02
MEVI Top-10 10 Clus
59.61
66.45
71.63
MEVI Top-100 Clus
70.33
77.23
81.77
MEVI Top-1000 1000 Clus
75.57
82.83
87.31
MEVI T0p-10 Clus & AR2 (HNSW)
74.10
82.11
86.43
MEVI Top-100 Clus & AR2 (HNSW)
74.43
82.71
87.51
MEVI Top-1000 Clus & AR2 (HNSW)
75.93
83.96
88.98
4.5 Dynamic update of documents
In order to test whether MEVI can support the dynamic update documents, we randomly remove 10% of the documents in the MSMARCO Passage dataset during training, and add these 10% documents back during evaluation. We compare MEVI with the embedding- basndd retrieval method T5-ANCE. Since NCI only maintains fixed document tree that does not support dynamic update of documents, we do not include NCI in this experiment.
Table 4 shows the results. Performance drop compared to normal training are listed in the parentheses. All tested methods lose some model accuracy when 10% of the documents are discarded during training. MEVI still performs well compared to ANN, showing the ability to handle unseen documents. From experiments we also find that the recall drops less as more clusters are retrieved, because more clusters provide more possible semantics information about unseen documents.
Table 4: Train with random 90% documents, and evaluate with all documents.
Method
MRR@ @ 10
R@50
@ 1000
T5-ANCE (HNSW)
29.34 (3.87)
73.09 (4.21)
86.26 (2.35)
MEVI Top-10 Clus
28.20 (3.85)
55.43 (7.82)
58.81 (8.01)
MEVI Top-100 Clus
33.48 (1.68)
74.16 (4.98)
82.68 (5.54)
MEVI Top-1000 Clus
35.38 (0.38)
81.06 (1.31)
93.40 (1.77)
4.6 Residual quantization
In this section, we first analyze the advantages of RQ over ordinary KMeans clustering, and then study the impact of RQ codebook configuration.
We choose RQ instead normal hicrarchical KMeans in MEVI. Compared to hierarchical KMcans that focuses more fine-grat fine-grained clustering within large clusters in each layer, RQ adopts residual information to address the errors the previous layer, making the clustering results more precise and robust. We conduct an experiment MEVI. In the experiments, we set layer depth to and the number of centroids per layer to 32. In Table 5, RQ generally achieves better recall than normal KMeans with the same number of clusters.
MSMARCO Passage compare these two algorithms in
In Table 6, we use RQ(x x y) to represent an RQ codebook with x layers, y bits (29 centroids) per layer, and a total of 2 clusters. For simplicity, we train the models on MSMARCO Passage with only generated query per document for augmentation. We report MRR 10, Recall @ 100, the total recall of top-k clusters, and the average number of retrieved documents per query. The numbers of

---

Table 5: Comparison of KMeans and RQ in MEVI.
Method
MRR@ 10
R@50
@@ 1000
MEVI-KMeans Top-10 Clus
31.62
65.09
68.25
MEVI-KMeans Top-100 Clus
34.82
77.30
87.93
MEVI-KMeans Top-1000 Clus
35.65
81.01
94.17
MEVI-RQ Top-10 Clus
32.05
63.25
66.82
MEVI-RQ Top-100 Clus
35.16
79.14
88.22
MEVI-RQ Top-1000 Clus
35.76
82.37
95.17
layers and bits both determine the size of cluster-id space, while the number retrieved clusters determines the number of retrieved documents per query. To fairly compare these configurations, we would like to align the number of retrieved documents per query to the same order of magnitude. From RQ(33 x 4) to RQ(5 5), the number of clusters increases, and the number of documents in each cluster decreases, so we enlarge the number of clusters from 3 to 1000 to align the number of the documents per query. In general, model is to recall the correct document. With the same order of magnitude of retrieved documents, RQ(4 x 5) performs well with moderate number of retrieved clusters. Although RQ(5 5) performs better in this case, it needs to retrieve more clusters to maintain appropriate number of document candidates, which poses serious memory challenges. Larger configurations also mean more decoder steps, resulting in larger inference latency. Hence for MSMARCO Passage dataset, RQ 5) is more proper. We leave the support for larger RQ in future work.
larger the number of candidate documents, the more likely the
Table 6: Model performance with different RQ configurations.
Configuration
# Clusters
MRR@ 10
R @@1 100
R@ Cluustees
# Docs Query
RQ(3 4)
26.38
55,05
58.83
13318
RQ 4)
10
29.15
63.28
67.28
9750
(Q 5)
100
33.36
76.14
80.71
4972
(Q 4)
100
32.57
72.92
77.11
4764
RQ 5)
1000
34.12
79.69
85.62
3999
4.7 Efficiency
We test the online serving latency of MEVI on single A6000 card. Since the inference time is affected by the number of retrieved clusters, we list the latency different settings Table For MEVI and NCI, the latency mainly comes from the stepwise generation of the autoregressive Sequence-to-sequeee
model. Latency increases with the number of clusters, because larger beam size leads to larger autoregressive generation time, well as larger number of candidates to be searched. NCI has much longer decoder steps than MEVI, resulting in a significant increase in latency. Latency of ANN includes the query encoding time and the HNSW searching time; it is the fastest method, which is appealing to real applications. Compared to ANN, MEVI can achieve a good performance and latency trade-off when with less than 100ms latency. This is acceptable online, as by adopting some acceleration techniques (c.g., FP16, ONNX Runtime [7]), can further improve the average serving latency less than 40ms.
10, improving the MRR @ 10 metric by more than 2 absolute points
Table 7: Trade-off between serving latency and model performance.
Method
MRR @ 10
Latency (ms)
T5-ANCE (HNSW)
33.21
19.71
NCI
26.18
2899.17 17
MEVI Top-10& & T5-ANCE (HNSW)
35.22
96.87
MEVI Top-100 & T5-ANCE (HNSW)
35.60
222.55
MEVI 100- & T5-ANCE (HNSW)
35.83
1662.84

---

4.8 Hyperparameters
We try different K for Recall and MRR on MSMARCO Passage in Figure "HNSW" means T5-ANCE with HNSW index, "Ensemble" means the ensemble result of TS-ANCE (HNSW) and MEVI Top-1000 Cluster. MEVI ensemble results consistently outperform T5-ANCE (HNSW).
In the ensemble process, we search the values of hyperparameters a and 3 in a proper range and choose the configuration with the best model metrics. Since the ensemble process does not incur additional training and inference cost, the time for grid search can be ignored. Figure 3 shows the MRR @ 10 of MEVI Top- 1000 T5-ANCE (HNSW) on MSMARCO Passage with different a and 3. The optimal configuration fully leverages the information of both components. Our ensemble method is also robust hyperparameters, the ensemble result outperforms the baseline (MEVI
Hop-1000 Clus 35.76) when 0.3 < S 0.7 and 0.01 < 5 < 0.03.
Figure 2: Recall and MRR at different K.
0.35
Recall
MRR
0.30
HNSW MEVI 1000Clus
HNSW
0.25
MEVI 1000Clus
Ensemble
Ensemble
10
10a
10a
10a
10"
10a
10a
10a
@K
@K
(a) @
(b) MRR@E
Figure 3: Impact of hyperparameters.
MRR@10 10
0.358
MRR@10
0.3580
Baseline
0.357
Baseline
beta=0.03
0.3575
alpha=0.6
0.4
0.6
1.0
0.01
0.02
0.03
0.04
0.05
alpha
beta
(a) MRR @ 10 v.s. a.
(b) MRR@ 10 v.s. 8
5 Limitations & future works
Despite the significant contribution of MEVI, there are opportunities for further improvements to enhance the model performance. First, the twin-tower model and the sequence-to-sequeee model not jointly learned, which may not yield the optimal retrieval performance. Second, the capacity of model still insufficient to cope with large-scale corpus within acceptable inference latency. In future works, these issues may be addressed by the following techniques: (a) Joint-training of RQ codebooks and models can be explored [53, 48]. (b) Model compression and acceleration techniques can be applied, such as knowledge distillation [16], con-autoregressive generation [50].
the sgquence-to-squeene
Conclusion
In this work, we introduce a novel Model-enhanced Vector Index (MEVI), which combines the advan- tages of both the sequence-to-sequence autoregressive model and the twin-tower dense representation model. It can be effectively applied in real-world applications due to its ability to achieve both high recall performance and fast retrieval speed on large-scale corpus. MEVI constructs an RQ structure to hierarchically cluster aarge-scale documents, enabling the sequence-to-sequeee generate the relevant cluster identifiers given an input query; retrieved candidate documents the top-k clusters are further ensembled with embedding-based retrieval results for candidates re-ranking. We empirically show that MEVI achieves better model performance than baselines on the widely used large-scale retrieval datasets MSMARCO Passage and Natural Questions.
model to directly
10

---

Acknowledgments
This work supported by National Key R&D Program of China 20022D01163115) and National Natural Science Foundation of China (6183) (61832001 and U22B2037). We thank Chenyan Xiong for his participation in the early discussions of MEVI and his guidance on the use of the T5-ANCE model. We thank Hang Zhang and Yeyun Gong for their guidance on the use of the AR2 model.
References
[1] Jon Louis Bentley. Multidimensional binary search trees used for associative searching. Com- munications of the ACM, 18(9):509-517, 1975.
[2] Michele Bevilacqua, Giuseppe Ottaviano, Patrick S. H. Lewis, Scott Yih, Sebastian Riedel, and Fabio Petroni. Autoregressive search engines: Generating substrings as document identifiers. In Advances Neural Information Processing Systems 35 (NeurIPS), 2022.
[3] Qi Chen, Bing Zhao, Haidong Wang, Mingqin Li, Chuanjie Liu, Zengzhong Li, Mao Yang, and Jingdong Wang. SPANN: highly-efficient billion-scale approximate nearest neighborhood search. In Advances Neural Information Processing Systems 34 (NeurIPS), 2021.
[4] Zhuyun Dai and Jamie Callam. Context-aware sentence/passage term importance estimation for first stage retrieval. CoRR, abs/191 (100 10687, 2019.
[5] Fu-Rong Dang, Jintao Tang. Kunyuan Pang, Ting Wang, Sha-Sha Li, and Xiao Li. Constructing an educational knowledge graph with concepts linked to wikipedia. Journal of Computer Science and Technology,
2021.
[6] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S. Mirrokni. Locality-sensittyy hashing scheme based on p-stable distributions. In Proceedings of the 20th ACM Symposium on Computational Geometry, 2004.
[7] ONNX Runtime developers. Onnx runtime. https: /ttpp:///nnxuuutimee. ai/, 2021.
[8] Jacob Devlin, Ming-Was Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT, 2019.
[9] Qian Dong, Shuzi Niu, Tao Yuan, and Yucheng Li. Disentangled graph recurrent network for document ranking. Data Science and Engineering, 43, 2022.
[10] Thibault Formal, Benjamin Piwowarski, and Stéphane Clinchant. SPLADE: sparse lexical and expansion model for first stage ranking. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2021.
[11] Luyu Gao and Jamie Callan. Condenser: pre-training architecture for dense retrieval. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP. 2021.
[12] Luyu Gao and Jamie Callan. Unsupervised corpus aware language model pre-training for dense passage retrieval. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics, ACL, 2022.
[13] Jiafeng Guo, Yixing Fan, Qingyao Ai, and W. Bruce Croft. A deep relevance matching model for ad-hoc retrieval. In Proceedings of the 25th ACM International Conference on Information and Knowledge Management, CIKM, 2016.
[14] Tonglei Guo, Jiafeng Guo, Yixing Fan, Yanyan Lan, Jun Xu, and Xueqi Cheng. comparison between term- based and embedding- based methods for initial retrieval. In Information Retrieval 24th China Conference, CCIR, 2018
[15] John Hartigan and Manchek Wong. k-means clustering algorithm. Journal of the royal statistical society. series e (applied statistics), 28(1):100-108, 1979.

---

[16] Geoffrey E. Hinton, Oriol Vinyals, and Jeffrey Dean. Distilling the knowledge in neural network. CoRR, abs/1503.02531, 2015.
[17] Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck. Learning deep structured semantic models for web search using clickthrough data. In Proceedings of the 22nd ACM International Conference on Information and Knowledge Management, CIKM, 2013.
[18) Zhong Ji, Kexin Chen, Yuqing He, Yanwei Pang, and Xuelong Li. Heterogeneous memory enhanced graph reasoning network for cross-modal retrieval. Science China Information Sciences, 65(7):1-13, 2022.
[19] Taisong Jin, Huaqiang Dai, Liujuan Cao, Baochang Zhang, Feiyue Huang, Yue Gao, and Rongrong Ji. Deepwalk-aware graph convolutional networks. Science China Information Sciences, 65(5):1-15, 2022.
[20] Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 7(3):535-3) -4,5, 2021.
[21] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick S. H. Lewis, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP, 2020.
[22] Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur P. Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, Kristina Toutanova, Llion Jones, Matthew Kelcey, Ming- Ming-Wei Chang, Andrew M. Dai. Jakob Uszkoreit, Quoe Le, and Slav Petrov. Natural questions: a benchmark for question answering research. Transactions of the Association for Computational Linguistics, 7:452 466, 2019.
[23] John D. Lafferty and ChengXiang Zhai. Document language models, query models, and risk minimization for information retrieval. In Proceedings of the 24th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2001.
[24] Canjia Li, Andrew Yates, Sean MacAvaney, Ben He, and Yingfei Sun. PARADE: passage representation aggregation for document reranking. ACM Transactions on Information Systems, 42(2), 2023.
[25] Wuchao Li, Chao Feng, Defu Lian, Yuxin Xie. Haifeng Liu, Yong Ge, and Enhong Chen. Learning balanced tree indexes for large-scale vector retrieval. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2023.
[26] Xiaoyong Liu and W. Bruce Croft. Cluster-based retrieval using language models. In Pro- ceedings of the 27th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2004.
[27] Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy. Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized BERT pretraining approach. CoRR, abs/ 1ttp/197.111 1692, 2019.
[28] Wenhao Lu, Jian Jiao, and Ruofei Zhang. Twinbert: Distilling knowledge to twin-structured compressed BERT models for large-scale retrieval. In Proceedings of the 29th ACM Interna- tional Conference on Information and Knowledge Management, CIKM, 2020
[29] Yi Luan, Jacob Eisenstein, Kristina Toutanova, and Michael Collins. Sparse, dense, and attentional representations for text retrieval. Transactions of the Association for Computational Linguistics, 9:329-345, 2021.
[30] Yury A. Malkov and Dmitry A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4))824-836, 2020.
[31] Julieta Martinez, Holger H. Hoos, and James Little. Stacked quantizers for compositional vector compression. CoRR, 4bs/1411.2173, 2014.
12

---

[32] Xupeng Miao, Hailin Zhang, Yining Shi, Xiaonan Nie, Zhi Yang, Yangyu Tao, and Bin Cui. HET: scaling out huge embedding model training via cache-enabled distributed framework. Proceedings of the VLDB Endowment, 15(2):312-320, 2021.
[33] Xupeng Miao, Yining Shi, Hailin Zhang, Xin Zhang, Xiaonan Nie. Zhi Yang, and Bin Cui. HET-GMP: A braph-based system approach to scaling large embedding model training. In SIGMOD '22: International Conference on Management of Data, 2022.
[34] Tri Nguyen, Mir Rosenberg, Xia Song, Jianfeng Gao, Saurabh Tiwary, Rangan Majumder, and Li Deng. MS MARCO: human generated machine reading comprehension dataset. In Proceedings of the Workshop on Cognitive Computation: Integrating neural and symbolic approaches 2016 co-located with the 30th Annual Conference on Neural Information Processing Systems (NeurIPS), 2016.
[35] Rodrigo Nogueira, Jimmy Lin, and AI Epistemic. From doc2query docttttqquery Online preprint, 6, 2019.
[36]
OpenMatch. T5-ANCE. https://nuggiingface http:://anggngaac...oo///otttaaa
2022.
[37] Fabian Pedregosa, Gaäl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, Jake Vander- Plas, Alexandre Passos, David Cournapeau, Matthieu Brucher, Matthieu Perrot, and Edouard Duchesnay, Scikit-learn: Machine learning in python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[38] Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. Rocketqa: An optimized training 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: Human Language Technologies, NAACL-IILT, 2021.
[39] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of Machine Learning Research, 21:140:1-4 1-440:67, 2020.
[40] Jie Ren, Minjia Zhang, and Dong Li. HM-ANN: efficient billion-poin nearest neighbor search on heterogeneous memory. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[41] Stephen E. Robertson and Steve Walker. On relevance weights with little relevance information. In Proceedings of the 20th International ACM SIGIR Conference Research and Development in Information Retrieval, 1997.
[42] Stephen E. Robertson and Hugo Zaragoza. The probabilistic relevance framework: BM25 and beyond. Foundations and Trends@ in Information Retrieval, ((4):333-389, 2009.
[43] Suhas Jayaram Subramanya, Fnu Devvrit, Harsha Vardhan Simhadri, Ravishankar Krish- naswamy, and Rohan Kadekodi. Rand-nsg: Fast accurate billion-point nearest neighbor search on single node. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
[44] Yi Tay, Vinh Tran, Mostafa Dehghani, Jianmo Ni, Dara Bahri, Harsh Mehta, Zhen Qin, Kai Hui, Zhe Zhao, Jai Prakash Gupta, Tal Schuster, William W. Cohen, and Donald Metzler. Transformer memory as a differentiable search index. In Advances in Neural Information Processing Systems 35 (NeurIPS), 2022.
[45] Ellen M. Voorhees. The cluster hypothesis revisited. Proceedings of the 8th International ACM SIGIR Conference on Research and Development in Information Retrieval, 1985.
[46] Yujing Wang, Yingyan Hou, Haonan Wang, Ziming Miao, Shibin Wu, Qi Chen, Yuqing Xia, Chengmin Chi, Guoshuai Zhao, Zheng Liu, Xing Xie, Hao Sun, Weiwei Deng, Qi Zhang, and Mao Yang. A neural corpus indexer for document retrieval. In Advances Neural Information Processing Systems 35 (NeurIPS), 2022.
13

---

[47] Zhijing Wu, Yiqun Liu, Jiaxin Mao, Min Zhang, and Shaoping Ma. Leveraging document-level and query-level passage cumulative gain for document ranking. Journal of Computer Science and Technology, 37(4):814 (144):814-88888 2022.
[48] Shitao Xiao, Zheng Liu, Yingxia Shao, Defu Lian, and Xing Xie. Matching-oriented embedding quantization for ad-hoe retrieval. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. EMNLP. 2021.
[49] Shitao Xiao, Zheng Liu, Weihao Han, Jianjin Zhang, Defu Lian, Yeyun Gong, Qi Chen, Fan Yang. Hao Sun, Yingxia Shao, and Xing Xie. Distill-vq: Learning retrieval oriented vector quantization by distilling knowledge from dense embeddings. In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2022.
[50] Yisheng Xiao, Lijun Wu, Junliang Guo, Juntao Li, Min Zhang, Tao Qin, and Tie- Yan Liu. survey on non-autoregressive generation for neural machine translation and beyond. IEEE Trunsuctions on Puttern Analysis and Machine Intelligence, 45(10): 1407-11427, 2023.
[51] Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang. Jialin Liu, Paul N. Bennett, Junaid Ahmed, and Arnold Overwijk. Approximate nearest neighbor negative contrastive learning for dense text retrieval. In The 9th International Conference on Learning Representations, ICLR, 2021.
[52] Wei Yang, Haotian Zhang, and Jimmy Lin. Simple applications of BERT for ad hoc document retrieval. CoRR, Mas//193.1000 10972, 2019.
[53] Han Zhang, Hongwei Shen, Yiming Qiu, Yunjiang Jiang, Songlin Wang. Sulong Xu, Yun Xiao, Bo Long, and Wen- Yun Yang. Joint learning of deep retrieval model and product quantization based embedding index. In The 44th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2021.
[54] Hang Zhang, Yeyun Gong, Yelong Shen, Jiancheng Lv, Nan Duan, and Weizhu Chen. Adversar- ial retriever-ranker for dense text retrieval. In The 10th International Conference on Learning Representations, ICLR, 2022.
[55] Mingdong Zhu, Derong Shen, Lixin Xu, and Xianfang Wang. Scalable multi-grained cross- modal similarity query with interpretability. Data Science and Engineering, 6(3):280-293, 2021.
[56] Shengyao Zhuang, Hang Li, and Guido Zuccon. Deep query likelihood model for information retrieval. Advances Information Retrieval 443rd European Conference on IR Research, ECIR, 2021.
14

---

Appendices for Model-enhanced Vector Index
A
Application in industry
We apply MEVI in a commercial advertising system. When users submit their queries, the system will retrieve the advertisements from the corpus. A successful retrieval algorithm should ensure that the retrieved advertisements satisfy two essential conditions. First, they should have a relatively high CTR (click-throurg
rate) to maximize the number of clicks. Second, they should have strong relevance to the user's query, ensuring a good user experience that the displayed advertisements are closely related to the user intent.
Dataset and training details. In this scenario, large-scale internal dataset selected from the historical advertising logs for offline evaluation. We collect approximately 80 million query-ad pairs for training and 40 million for testing. There are approximately 20 million advertisements in the sampled dataset. To satisfy both the CTR and relevance goals, the retrieval model is followed by a relevance- velevance-turgetinn re-rank model to select top ads from the recall candidates. We adopt RQ codebook with clustering layers and 5 bits per layer for MEVI. The model is trained on 8 V100 GPU cards for weeks, with a batch size of 256. The evaluation beam size is 10. Other settings and hyperparameters keep the same as the MSMARCO Passage experiments.
Metrics. We adopt several metries to evaluate recall and relevance performance. Hitrate (Hit@K) measures how many clicked ads are included in top K results given query. MRR (MRR@H measures the ranking performance of the ads. Average Relevance score (Rel@K) measures the relevance score from top-K results, calculated by a commercial large language model finetuned by human labels, which has been proved to be effective and correlate closely to human labels.
Baseline. We adopt commercial embedding- bbsed retrieval (EBR) methods as the baseline, which has transformer layers on both query and document sides. The hidden dimension is 768 and the number of head is 12. The EBR model is trained on 8 V100 GPU cards for 6 epochs. After the training finished, we generate query and ads embeddings and adopt an efficient ANN algorithm used in production to search for relevant advertisements. We also use the same relevance model to rerank the recall candidates.
Table 1: Experiment results on commercial advertising dataset.
Method
Hit@50
Hit@500
MRR@50
MRR@500
Rel@50
@el
EBR
61.80
95.23
73.42
97.07
39.61
22.92
Top-10 10 Clusters
69.62
83.40
75.30
84.35
26.57
14.98
MEVI
71.92
96.25
80.55
97.75
39.78
23.23
The experimental results are shown in Table 1. The search results within top-10 clusters demonstrate strong recall performance for the top 50 results. However, the top 500 results show decline in performance compared to the EBR baseline, primarily due to the beam size being limited to during MEVI inference, which results a smaller search space. Increasing the beam size could potentially improve performance but would also place greater computation burden on the relevance model. Consequently, a beam size of was ultimately chosen for production scenario.
Results.
Despite these limitations, the ensemble results reveal substantial increase across all metrics, in- dicating that MEVI serves as an excellent candidate provider for recall and complementary to embedding based retrieval methods, which is meaningful for multiple-recal! scenarios. By incorpo- rating MEVI, the commercial advertising system can significantly enhance both recall and relevance performance.
Online A/B test. MEVI also demonstrates impressive results in online A/B test. It achieves a 0.71% RPM (Revenue per Mille searches) growth in the A/B test with a P-Value of 0.00021 (a P-Value less than 0.05 is considered statistically significant in production). Moreover, MEVI shows 0.60% reduction of bad relevance cases according to the human judgement, further demonstrating that MEVI not only boost advertising revenue, but also effectively improve user experiences with better query-ad relevances.


Reviews:
[{"review_id": "WfPp8MzOCN", "reviewer": "Reviewer_v1wc", "summary": "This research paper introduces a deep text retrieval model that possesses the capability to effectively manage a large corpus comprising millions of documents. The model achieves remarkable recall performance while maintaining relatively low latency. Moreover, in addition to surpassing the performance of existing methods in a document retrieval benchmark, the paper also showcases the successful integration of deep text retrieval models into a commercial advertising system, demonstrating their practical value in an industrial setting.", "questions": "1.\tIn dynamic update experiments, if more documents come in, their codebook may not be \"optimal\", so how can the codebook be adjusted to preserve similar effectiveness and robustness? Otherwise, the resulting method may not be good. In addition, their Top-10 results are worse than T5-ANCE. \n2.\tMore experiments are needed. They should also compare their method with one another datasets used in DSI or NCI. And the latency experiment should include other baseline models.\n3.\tIf RQ is applied to DSI and NSI, does their method achieve better performance or does the utilization of normal k-means in the proposed method potentially diminish its effectiveness to a significant extent?\n", "limitations": "The authors pointed out the limitations of their model including not jointly learning between twin-tower model and seq2seq model, and their method is still unacceptable inference latency in the large-scale corpus. They had provided potential solutions to address the above issues.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1.\tS1: They are supposed to be the first to demonstrate the successful implementation of deep text retrieval models in the practical application.\n2.\tS2: They investigate and test the effectiveness of Residual Quantization within the deep text retrieval model.\n3.\tS3: The experiment results on MSMARCO dataset display the effectiveness of the proposed method.\n", "weaknesses": "W1: They conduct experiments on a single dataset for their study. However, it is recommended that their model undergo experiments on commonly used datasets such as Natural Question, which is utilized in both DSI and NCI research. In addition, they point out that the existing methods are limited by unacceptable serving latency but they do not conduct such experiments to prove this. Since their method use Residual \nQuantization (RQ) as their clustering method, this method may be more time-consuming than other clustering methods during training.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper.\n\nFirst, we address the points you mentioned in the weaknesses part.\n\n1. We conduct experiments on another popular dataset, Natural Questions (NQ). We take AR2 (https://arxiv.org/abs/2110.03611) as the dense retriver and HNSW as the ANN algoritm. As shown in the table below, MEVI method still achieves better performance than baseline methods.\n\n| Method | R@5 | R@20 | R@100 |\n| -------- | :-----: | :-----: | :-----: |\n| BM25 | / | 59.1 | 73.7 |\n| AR2 + HNSW | 70.89 | 78.50 | 83.02 |\n||||\n| MEVI Top-10 Clus | 59.61 | 66.45 | 71.63 |\n| MEVI Top-100 Clus | 70.33 | 77.23 | 81.77 |\n| MEVI Top-1000 Clus | 75.57 | 82.83 | 87.31 |\n||||\n| MEVI Top-10 Clus & AR2(HNSW) | 74.10 | 82.11 | 86.43 |\n| MEVI Top-100 Clus & AR2(HNSW) | 74.43 | 82.71 | 87.51 |\n| MEVI Top-1000 Clus & AR2(HNSW) | **75.93** | **83.96** | **88.98** |\n\n2. We add the latency of NCI here for comparison. It is worth noting that the clustering process is performed in advance, while the training process and the serving process are performed on the constant RQ structure. The service latency here is mainly determined by the number of decoding steps in the autoregressive generation. Since MEVI allows each doc-id to represent a set of documents, while NCI only allows one doc-id to represent one document, MEVI has much fewer decoding steps than NCI's 10 decoding steps, resulting in a smaller latency.\n\n| Method | MRR@10 | Latency (ms) |\n| -------- | :-----: | :-----: |\n| T5-ANCE (HNSW) | 33.21 | 19.71 |\n| NCI | 26.18 | 2899.17 |\n| MEVI Top-10 & HNSW | 35.22 | 96.87 |\n| MEVI Top-100 & HNSW | 35.60 | 222.55 |\n| MEVI Top-1000 & HNSW | 35.83 | 1662.84 |\n\nThen we answer the questions below.\n\n1. In dynamic update experiments, if more documents come in, their codebook may not be \"optimal\", so how can the codebook be adjusted to preserve similar effectiveness and robustness? Otherwise, the resulting method may not be good. In addition, their Top-10 results are worse than T5-ANCE.\n- If more documents come in and the distribution of documents has changed drastically, all existing dense retrieval methods, as well as MEVI, have to re-train the model and re-construct the document index. In other words, dynamic updates only support a small number of new documents that do not change the distribution much. In future work we may extend RQ to an adaptive structure that captures the distribution of new documents during training. When MEVI only searches documents within top-10 clusters, the number of documents to be ranked is very small, leading to bad recall performance. After enlarged to top-100 or top-1000 clusters, MEVI performs better than the baseline in both basic experiment and dynamic update experiment.\n\n2. More experiments are needed. They should also compare their method with one another datasets used in DSI or NCI. And the latency experiment should include other baseline models.\n- This question has been addressed in the weakness part. The experiment results on NQ dataset (full document set version from DPR) are listed in the first table. MEVI performs better than baseline models. For latency comparison, the results are listed in the second table. Dense retrieval based on bi-encoders has the smallest latency. MEVI outperforms significantly better than NCI while holding affordable latency. \n\n\n3. If RQ is applied to DSI and NSI, does their method achieve better performance or does the utilization of normal k-means in the proposed method potentially diminish its effectiveness to a significant extent?\n- We would like to break this problem down into two parts, one is the difference between MEVI and NCI/DSI, and the other is the difference between RQ and normal k-means. For the first difference, each minimal cluster in MEVI contains a set of documents, while each minimal cluster in NCI and DSI contains only one document. This design makes MEVI smaller number of clustering layers, leading to lower serving latency. Also, if the doc-id is too long, the model cannot learn effectively in a certain time budget, so the results of MEVI on MSMARCO Passage is much better than NCI. For the second difference, we use RQ instead of normal K-Means in MEVI because RQ performs better. In RQ, each layer uses the residual vectors from the last clustering layer, and conducts k-means clustering among all the vectors. Comparing to hierarchical k-means that focuses on more fine-grained clustering within large clusters, RQ adopts residual information to address the errors of the last clustering layer, making the clustering results more robust. We conduct an experiment to compare RQ with normal hierarchical k-means. In the experiments, we test MEVI-RQ and MEVI-KMeans on MSMARCO Passage dataset, setting layer depth to 4 and the number of clusters per layer to 32. The results are listed in the following table, showing that RQ generally achieves better recall than hierarchical k-means under the same number of layers (corresponding to comparable latency).\n\n\n| Method | MRR@10 | Recall@50 | Recall@1000 |\n| -------- | :-----: | :-----: | :-----: |\n| MEVI-RQ Top-10 Clus | 32.05 | 63.25 | 66.82 |\n| MEVI-RQ Top-100 Clus | 35.16 | 79.14 | 88.22 |\n| MEVI-RQ Top-1000 Clus | **35.76** | **82.37** | **95.17** |\n||||\n| MEVI-KMeans Top-10 Clus | 31.62 | 65.09 | 68.25 |\n| MEVI-KMeans Top-100 Clus | 34.82 | 77.30 | 87.93 |\n| MEVI-KMeans Top-1000 Clus | 35.65 | 81.01 | 94.17 |"}, {"review_id": "aCrI5lCN30", "reviewer": "Reviewer_c7Dg", "summary": "This paper present a new method for ensembling generative retrieval and embedding-based dense retrieval. Prior generative retrieval work that solely relies on a generation model to generate the retrieval document, but it is difficult to scale to large corpus. In contrast, this paper uses the generation model to predict candidate document clusters, but still adopt a dense retriever to produce the final document rankings, where the document from different clusters are weighted according the generation model's output.  \n\nThe authors first evaluated this method on MS MARCO. The proposed method show improvements over a dense retriever T5-ANCE, and also good support to corpus update. The authors also tested this method in a production ad system where improvements were also observed over their production dense retrieval model (a 4-layer transformer dual-encoder).", "questions": "- How does the model compares or works with SOTA dense retrievers on MS MARCO?\n- What is model size of the generation model? How does it affect serving latency?\n- How's the performance with just the generation model?", "limitations": "No", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- This paper proposes a simple idea to ensemble generative retrieval model and embedding-based dense retrieval.  In the proposed method, the generative retrieval model is essentially predicting document clusters from a query which are then used for reweighting or pruning the dense retrieval results. This aproach is a lot more practical and scalable compared to existing generative retrieval approaches that need to generate the exact document identifier. \n- Experiments show promising results.\n- Paper is well written.", "weaknesses": "- The authors did not compare to any published neural retrieval baselines on MS MARCO, as T5-ANCE and NCI are both their own implementations. I'm wondering how does the method work with SOTA dense retrievers such as RocketQA v2 or coCondensor, whose results seem stronger than T5-ANCE on MS MARCO. \n- It would be nice to add another dataset, such as Natural Questions.\n- It is unclear to me what is the advantage of RQ compared to other hierarchical clustering approaches. It would be nice to add some discussion and ablation studies. \n- There are some confusions around T5-ANCE. First of all, T5-ANCE does not seem to exactly follow the ANCE recipe which uses dynamic indexing for hard negative mining. Second, it is unclear the model size and hyperparameters for this model. \n- I think is is an over-claim to say \"For the first time, we demonstrate that a novel-designed generation-based model is able to handle\n a large corpus with millions of documents, reaching high recall performance and low serving latency at the same time.\" From my understanding, this method mostly rely on dense retrieval and generation-based model is only providing cluster-level weights. To justify this claim, the author should report the performance without ensembling with dense retrieval.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback.\n\nFirst, we address the five points you mentioned in the weaknesses part.\n\n1. On the MSMARCO Passage dataset, we add another state-of-the-art dense retrieval model AR2 (https://arxiv.org/abs/2110.03611) in addition to T5-ANCE. AR2 performs better than RocketQA-v2 and coCondenser. From the experiment results in the table below, we can see that MEVI also achieves a better performance than AR2+HNSW.\n\n| Method | MRR@10 | Recall@50 | Recall@1000 |\n| -------- | :-----: | :-----: | :-----: |\n| BM25 | 18.7 | 59.2 | 85.7 |\n| T5-ANCE + HNSW | 33.21 | 77.30 | 88.61 |\n| AR2 + HNSW | 35.54 | 78.80 | 87.11 |\n| NCI | 26.18 | 74.68 | 92.44 |\n||||\n| MEVI Top-10 Clus | 32.05 | 63.25 | 66.82 |\n| MEVI Top-100 Clus | 35.16 | 79.14 | 88.22 |\n| MEVI Top-1000 Clus | 35.76 | 82.37 | 95.17 |\n||||\n| MEVI Top-10 Clus & T5-ANCE(HNSW) | 35.22 | 81.29 | 93.21 |\n| MEVI Top-100 Clus & T5-ANCE(HNSW) | 35.60 | 82.27 | 95.62 |\n| MEVI Top-1000 Clus & T5-ANCE(HNSW) | 35.82 | 82.77 | 97.12 |\n||||\n| MEVI Top-10 Clus & AR2(HNSW) | 37.00 | 82.64 | 93.46 |\n| MEVI Top-100 Clus & AR2(HNSW) | 38.42 | 84.52 | 96.23 |\n| MEVI Top-1000 Clus & AR2(HNSW) | **39.16** | **86.12** | **97.65** |\n\n2. We conduct experiments on Natural Questions (NQ) and the results are listed here. We take AR2 as the dense retriever and HNSW as the ANN algorithm. MEVI achieves better performance than baseline methods on NQ.\n\n| Method | R@5 | R@20 | R@100 |\n| -------- | :-----: | :-----: | :-----: |\n| BM25 | / | 59.1 | 73.7 |\n| AR2 + HNSW | 70.89 | 78.50 | 83.02 |\n||||\n| MEVI Top-10 Clus | 59.61 | 66.45 | 71.63 |\n| MEVI Top-100 Clus | 70.33 | 77.23 | 81.77 |\n| MEVI Top-1000 Clus | 75.57 | 82.83 | 87.31 |\n||||\n| MEVI Top-10 Clus & AR2(HNSW) | 74.10 | 82.11 | 86.43 |\n| MEVI Top-100 Clus & AR2(HNSW) | 74.43 | 82.71 | 87.51 |\n| MEVI Top-1000 Clus & AR2(HNSW) | **75.93** | **83.96** | **88.98** |\n\n3. We find RQ performs better than normal hierarchical K-Means. In RQ, each layer uses the residual vectors from the last clustering layer, and conducts k-means clustering among all the vectors. Comparing to hierarchical k-means that focuses on more fine-grained clustering within large clusters, RQ adopts residual information to address the errors of the last clustering layer, making the clustering results more robust. We conduct an experiment to compare RQ with normal hierarchical k-means. In the experiments, we test MEVI-RQ and MEVI-KMeans on MSMARCO Passage dataset, setting cluster depth to 4 and the number of clusters per layer to 32. The results are listed in the table below, showing that RQ generally achieves better recall than hierarchical k-means under the same number of layers.\n\n| Method | MRR@10 | Recall@50 | Recall@1000 |\n| -------- | :-----: | :-----: | :-----: |\n| MEVI-RQ Top-10 Clus | 32.05 | 63.25 | 66.82 |\n| MEVI-RQ Top-100 Clus | 35.16 | 79.14 | 88.22 |\n| MEVI-RQ Top-1000 Clus | **35.76** | **82.37** | **95.17** |\n||||\n| MEVI-KMeans Top-10 Clus | 31.62 | 65.09 | 68.25 |\n| MEVI-KMeans Top-100 Clus | 34.82 | 77.30 | 87.93 |\n| MEVI-KMeans Top-1000 Clus | 35.65 | 81.01 | 94.17 |\n\n4. T5-ANCE is another model released by the authors of ANCE. The hyperparameters and the whole training process is shown in this website https://openmatch.readthedocs.io/en/latest/models/t5-ance.html. T5-ANCE follows the two-round training, where the first round uses BM25 negative samples and the second round uses hard negative samples. It uses T5-base as the backbone model. More detailed hyperparameters can be found in the website above.\n\n5. Our expression here is a little bit confusing. We will revise it in the next version. We would like to demonstrate that MEVI is the first generation-ENHANCED model to handle a large corpus with millions of documents, with high recall performance and acceptable serving latency. The performance without ensembling has already been reported in Table 1 from the original version, named \"MEVI Top-K Clus\". The recall and MRR metrics are generally better than T5-ANCE+HNSW when K is 100 or 1000.\n\n\nThen here are the answers to your questions.\n\n1. How does the model compares or works with SOTA dense retrievers on MS MARCO?\n- Already presented in weaknesses part. We add an experiment with sota dense retriever AR2 in the first table.  \n\n2. What is model size of the generation model? How does it affect serving latency?\n- Currently we use T5-base as the backbone generation model. We add an experiment on the serving latency of different model sizes in the following table. When the model size becomes larger, the latency becomes unacceptable for online serving.\n\n| Method | Latency (ms) |\n| -------- | :-----: |\n| T5-base Top-10 | 96.87 |\n| T5-base Top-100 | 222.55 |\n| T5-base Top-1000 | 1662.84 |\n| T5-large Top-10 | 124.56 |\n| T5-large Top-100 | 253.23 |\n| T5-large Top-1000 | 1665.47 |\n\n3. How's the performance with just the generation model?\n- The performance is presented in the first table above, named \"MEVI Top-k Clus\". The generation model already achieves good recall performance without ensembling when K is 1000.\n\n"}, {"review_id": "skLu1SF0DA", "reviewer": "Reviewer_aDGQ", "summary": "This paper proposes to improve dense neural IR models by adding a RQ structure (hierarchical clustering based on residuals at each step) before the ANN search. The structure is used to construct a semantic identifier string for each document. The authors thus use a generative approach to retrieval combined with a dense model.\n\nThis approach has two advantages, firstly to have a faster retrieval (since the ANN search is restricted to a subset of the document), secondly to have a better retrieval (by exploiting a cluster-based score). Experiments conducted on MS Marco (passages) and a proprietary advertisement dataset show improvements over T5-ANCE.", "questions": "- what is the performance of ANCE without HNSW? This would have been a proper baseline.\n\n- in section 3.2, how are $\\alpha$ and $\\beta$ set?\n\n- What it the advantage of using RQ over hierarchical clustering?", "limitations": "The limitation section contradicts a bit the initial claims (“… the capacity of the sequence-to-sequence model is still insufficient to cope with large-scale corpus within acceptable inference latency …”), but correctly lists the different limitations of the paper.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well written and technical details ensuring reproduction are given.\n\nThe approach is promising as it both allows for more effective and efficient retrieval - which is always a challenge in IR. The proposed approach, based on RQ clusters, is original and combines the strength of generative and dense models in IR.  \n\nIt also shows that adding documents is not as problematic as for other generative approaches (but however the performance is worse than T5-ANCE in that case, for a higher latency).", "weaknesses": "- Comparison with state of the art models (A2R/Adversarial Retriever-Ranker for dense models, SPLADE for sparse ones) is missing - it would have been good to see how with better dense models the proposed approach evolves.\n\n- With respect to generative models, several approaches have better results than NCI nowadays (e.g. Ultron) or the more recent “Learning to tokenise” (SIGIR’23). At least Ultron should be reported (ArXiv 2022) for comparison purposes.\n\n- The authors have chosen to use a proprietary dataset (section 4.7) for the second evaluation. It would have been much wiser to use publicly available ones as nothing can be checked on this one (e.g. BEIR) - reporting proprietary results in the appendix would have been appropriate.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed review.\n\nFirst, we address the three points you mentioned in the weaknesses part.\n\n1. On the MSMARCO Passage dataset, we add the experiment results with another state-of-the-art dense retrieval model AR2 (https://arxiv.org/abs/2110.03611) in the following table. We also add SPLADE results for comparison. MEVI achieves better performance than AR2 (with HNSW as the ANN algorithm). Note that AR2 without HNSW performs brute force to rank all candidates, which gets better results but is not applicable in online applications. \n\n| Method | MRR@10 | Recall@50 | Recall@1000 |\n| -------- | :-----: | :-----: | :-----: |\n| BM25 | 18.7 | 59.2 | 85.7 |\n| SPLADE | 32.2 | / | 95.5 |\n| T5-ANCE | 35.73 | 82.96 | 97.21 |\n| T5-ANCE + HNSW | 33.21 | 77.30 | 88.61 |\n| AR2 | 39.50 | 86.98 | 98.44 |\n| AR2 + HNSW | 35.54 | 78.80 | 87.11 |\n| NCI | 26.18 | 74.68 | 92.44 |\n||||\n| MEVI Top-10 Clus | 32.05 | 63.25 | 66.82 |\n| MEVI Top-100 Clus | 35.16 | 79.14 | 88.22 |\n| MEVI Top-1000 Clus | 35.76 | 82.37 | 95.17 |\n||||\n| MEVI Top-10 Clus & T5-ANCE(HNSW) | 35.22 | 81.29 | 93.21 |\n| MEVI Top-100 Clus & T5-ANCE(HNSW) | 35.60 | 82.27 | 95.62 |\n| MEVI Top-1000 Clus & T5-ANCE(HNSW) | 35.82 | 82.77 | 97.12 |\n||||\n| MEVI Top-10 Clus & AR2(HNSW) | 37.00 | 82.64 | 93.46 |\n| MEVI Top-100 Clus & AR2(HNSW) | 38.42 | 84.52 | 96.23 |\n| MEVI Top-1000 Clus & AR2(HNSW) | 39.16 | 86.12 | 97.65 |\n\n2. Ultron conducts experiments on MSMARCO DOCUMENT and NQ-320K datasets, which has much fewer documents than MSMARCO PASSAGE and NQ datasets (we add experiments of this dataset in the second table) in our experiments. Due to the high decoding cost of generative models, Ultron is not friendly to larger datasets. Therefore, we do not compare to Ultron in our experiments. Moreover, the results presented in the Ultron paper are no better than NCI. For another paper you mentioned as \"learning to generate\", we can not find this paper in both Arxiv and SIGIR'23 venue. Could you provide a link to this paper for our reference?\n\n3. We conduct experiments on another public dataset Natural Questions (NQ) and the results are listed in the table below. MEVI still achieves better performance than baseline methods.\n\n| Method | R@5 | R@20 | R@100 |\n| -------- | :-----: | :-----: | :-----: |\n| BM25 | / | 59.1 | 73.7 |\n| AR2 | 77.78 | 85.98 | 90.03 |\n| AR2 + HNSW | 70.89 | 78.50 | 83.02 |\n||||\n| MEVI Top-10 Clus | 59.61 | 66.45 | 71.63 |\n| MEVI Top-100 Clus | 70.33 | 77.23 | 81.77 |\n| MEVI Top-1000 Clus | 75.57 | 82.83 | 87.31 |\n||||\n| MEVI Top-10 Clus & AR2(HNSW) | 74.10 | 82.11 | 86.43 |\n| MEVI Top-100 Clus & AR2(HNSW) | 74.43 | 82.71 | 87.51 |\n| MEVI Top-1000 Clus & AR2(HNSW) | 75.93 | 83.96 | 88.98 |\n\nThen we answer the questions below.\n\n1. What is the performance of ANCE without HNSW? This would have been a proper baseline.\n- We add the performance of ANCE without HNSW in the tables above. Though the ideal result of ANCE achieves good recall performance especially when k is large, it is not applicable in real industrial scenarios due to large serving latency (> 3500 ms), so we do not explicitly include it in our paper. MEVI can reach better or nearly the same model quality with less serving latency.\n\n\n\n2. In section 3.2, how are $\\alpha$ and $\\beta$ set?\n- We search $\\alpha$ and $\\beta$ within a proper range and set them according to the model metric. Since the ensemble process does not incur additional training and inference, the time for search can be ignored. Figure 1 in the attached PDF shows the MRR@10 for different values of $\\alpha$ and $\\beta$. With the right configuration, the ensemble results achieves optimal performance as it fully leverages both components. In general, for the same dataset, the best hyperparameters searched on the dev set are also optimal on the test set.\n\n3. What it the advantage of using RQ over hierarchical clustering?\n- In RQ, each layer uses the residual vectors from the last clustering layer, and conducts k-means clustering among all the vectors. Comparing to hierarchical k-means that focuses on more fine-grained clustering within large clusters, RQ adopts residual information to address the errors of the last clustering layer, making the clustering results more robust. We conduct an experiment to compare RQ with normal hierarchical k-means. In the experiments, we test MEVI-RQ and MEVI-KMeans on MSMARCO Passage dataset, setting layer depth to 4 and the number of clusters per layer to 32. The results are listed in the table below, showing that RQ generally achieves better recall than hierarchical k-means under the same number of layers.\n\n| Method | MRR@10 | Recall@50 | Recall@1000 |\n| -------- | :-----: | :-----: | :-----: |\n| RQ MEVI Top-10 Clus | 32.05 | 63.25 | 66.82 |\n| RQ MEVI Top-100 Clus | 35.16 | 79.14 | 88.22 |\n| RQ MEVI Top-1000 Clus | **35.76** | **82.37** | **95.17** |\n||||\n| K-Means MEVI Top-10 Clus | 31.62 | 65.09 | 68.25 |\n| K-Means MEVI Top-100 Clus | 34.82 | 77.30 | 87.93 |\n| K-Means MEVI Top-1000 Clus | 35.65 | 81.01 | 94.17 |"}, {"review_id": "m4TpceCkZR", "reviewer": "Reviewer_VZqD", "summary": "This work introduces residual quantisation codebook into k-mean clustering to generate semantic IDs. These semantic IDs are used to provide initial cluster-level ranking and prune the corpus into document subset with thousand documents. The interpolation between the dual-encoder similarity and a derived cluster score is used as final ranking. The experiments are on msmarco passage dataset.   ", "questions": "- What is the configuration of \\alpha and \\beta and how sensitive is the performance relative to their configs?\n", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- An novel idea is implemented and examined to exploit the semantic ids from generative retrievers to introduce clusters into dual-encoder\n- The writing is easy to follow and the method is insightful\n- Promising results are reported on large in-house dataset Ms Marco and on an online system", "weaknesses": "- The cluster-based retrieval has been long studied and this paper should be put into context better, e.g., [1, 2] . Besides, is this the first work to introduce clusters into dual-encoder retriever?\n- The effectiveness improvement in Table 1 comes from the fine-grained clustering information. Does such boost still exist when using state-of-the-art dual-encoder retrievers, like rocketqav2 and GTR, where the document similarity is with higher quality? Actually, in Table 1, it can be seen that use of HNSW could boos the recall considerably. Also, the results of the online system are also on top of weak dual-encoder models (four layers). Thus, it is beneficial to better understand when and where the clustering information could help. \n- For the dynamic update of documents, is this the first work that investigates this problem? What are the existing methods tackling this problem and how they design the experiments? The results from Table 2 look promising, but I am not sure how convincing it is to support that claims of dynamic updates.\n- As an ablation results, Table 3 is hard to read, and the configuration differences among rows are more than one out of three (subgroup, bits, top-k), and it is hard to answer by increasing subgroup or k it helps.\n- Some formatting issues: a space is required between the text and their follow-up citation, like line 150\n\n\n1. https://dl.acm.org/doi/pdf/10.1145/253495.253524\n2. https://arxiv.org/abs/2008.00150", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time you took to review our paper.\n\nFirst, we address the five points you mentioned in the weaknesses part.\n\n1. From the taxonomy perspective, our proposed MEVI is a generation-enhanced dense retrieval method, not a traditional cluster-based retrieval method. The clustering process here forms doc-ids (or say cluster-ids) to build outputs of a generative language model. We would like to claim this is the first work to introduce information from generative model into dual-encoder retriever. We will reference the cluster-retrieval based methods and clarify their difference in the next version of our paper.\n\n2. We have conducted experiments with another state-of-the-art dense retrieval model AR2 (https://arxiv.org/abs/2110.03611) in the table below. AR2 performs better than RocketQA-v2. The comparison of vanilla dense retriever and ensembling method in the table below shows the gain of introducing generative-based retrieval information.\n\n| Method | MRR@10 | Recall@50 | Recall@1000 |\n| -------- | :-----: | :-----: | :-----: |\n| BM25 | 18.7 | 59.2 | 85.7 |\n| T5-ANCE + HNSW | 33.21 | 77.30 | 88.61 |\n| AR2 + HNSW | 35.54 | 78.80 | 87.11 |\n| NCI | 26.18 | 74.68 | 92.44 |\n||||\n| MEVI Top-10 Clus | 32.05 | 63.25 | 66.82 |\n| MEVI Top-100 Clus | 35.16 | 79.14 | 88.22 |\n| MEVI Top-1000 Clus | 35.76 | 82.37 | 95.17 |\n||||\n| MEVI Top-10 Clus & T5-ANCE(HNSW) | 35.22 | 81.29 | 93.21 |\n| MEVI Top-100 Clus & T5-ANCE(HNSW) | 35.60 | 82.27 | 95.62 |\n| MEVI Top-1000 Clus & T5-ANCE(HNSW) | 35.82 | 82.77 | 97.12 |\n||||\n| MEVI Top-10 Clus & AR2(HNSW) | 37.00 | 82.64 | 93.46 |\n| MEVI Top-100 Clus & AR2(HNSW) | 38.42 | 84.52 | 96.23 |\n| MEVI Top-1000 Clus & AR2(HNSW) | **39.16** | **86.12** | **97.65** |\n\n3. Dynamic update is not a problem in dense retrieval, since the usage of embedding already enables unseen documents if the new-coming ones do not change the overall distribution drastically. However, in existing generation-based methods which convert documents to fixed doc-ids, re-training is required if new documents come in. Therefore, existing dense retrieval methods have better ability to handle new documents, while existing generation-based methods cannot support dynamic update. Since we aim to incorporate the information from generative models and take the advantage of dense retrieval methods simultaneously, we train the model with only 90% documents and regard the rest as new documents to validate the capability of MEVI to handle new documents. In experiments, MEVI has comparable results to dense retrieval methods, exhibiting similar ability to support dynamic updates.\n\n4. In Table 3 of the original paper, our aim is to examine the recall performance of different configurations with almost the same number of candidate documents per query. To align the magnitude of the number of documents per query, we have to adjust the number of clusters, which is calculated as (2 ^ #subgroup) ^ #bits. The numbers of subgroup and bits both determine the size of cluster-id space, while the k determines the number of documents per query. From RQ(3,4) to RQ(5,5), the number of clusters increases, and the number of documents in each cluster decreases; so we enlarge $k$ to align the magnitude of the number of documents per query. In general, the larger number of candidate documents, the more likely the model is to recall the correct document. Comparing RQ(3,4), RQ(4,4), and RQ(4,5), even the number of documents per query is reduced, the recall performance increases due to finer-grained learning to generate cluster-ids. In RQ(5,5) setting, the cost of generation becomes unacceptable as the number of clusters increases. In summary, RQ(4,5) achieves the best trade-off between model performance and cluster-id space size.\n\n5. Thanks for your valuable suggestions. We will modify the typos in the next version.\n\nThen we answer the questions below.\n\n1. What is the configuration of $\\alpha$ and $\\beta$ and how sensitive is the performance relative to their configs?\n- $\\alpha$ determines the overall contribution ratio of clustering information, while $\\beta$ determines how large the clustering score is with respect to the cluster rank. In practice, we directly search and choose the best configurations since the ensembling does not incur additional training or inference, and the search overhead can be ignored. Figure 1 in the attached PDF shows the MRR@10 for different values of $\\alpha$ and $\\beta$. With the right configuration, the ensemble results achieves optimal performance as it fully leverages the two components. The best hyperparameters searched on the dev set are also optimal on the test set.\n\n"}, {"review_id": "ytrk9xlClA", "reviewer": "Reviewer_KfyS", "summary": "In this study, the authors present a new approach called Model-enhanced Vector Index (MEVI) that combines ideas from both autoregressive sequence-to-sequence models for indexing and dense retrieval models (twin-tower architectures), and includes Residual Quantization. This approach offers significant advantages and proves to be highly effective in real-world applications. MEVI demonstrates nice performance gains in terms of achieving both high recall accuracy and faster retrieval speed, even when dealing with large-scale corpora.", "questions": "See weaknesses above.", "limitations": "Yes.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The method introduced combines two of the recent approaches for document retrieval - dense retrieval and the generative neural indexing. It showcases the power of these together and is extensively evaluated and experimented, both in an offline manner as usual, but also online in real-word scenarios (in commercial advertising). They also include a nice latency evaluation.\n* The paper is well-written and easy to follow in general.\n", "weaknesses": "Major comments:\n* MSMARCO is the only benchmark which was evaluated in this work. I’d love to see if the method generalizes well across more datasets. This is required in order to convince readers to favour this method.\n* While an online A/B testing experiment appreciated, there is no guarantee about the quality of such kind of testing, while controlled crowdsourcing does provide an infrastructure for filtering out bad annotations.\n* L152: I am not convinced that the tree structure is problematic because of decoding time. It can actually alleviate the decoding if using controlled decoding instead of plain beam search. Also, the hierarchical nature of the structure of embeddings proposed in this work is not that different (as stated in L167).\n* The authors report results using MRR@10 Recall@50 Recall@1000 but it woul’d be interesting to see both more fine-grained retrieval results (Recall@1) following previous works, as well as a figure which states how the method results progress as k is being increased.\nThe training process of the twin-tower model and the sequence-to-sequence model are distinct which may be very problematic. But I do acknowledge this was stated in the limitations section.\n\n\nMinor comments:\n* Please elaborate more both in the contributions part in the introduction section about and in the introduction itself more about the proposed MEVI method. After reading this, I didn’t have any clue about the method which should be stated much early in the text.\n* Related work section - please state how your method differs from other recent works.\n* L146: insert space after T5-ANCE. Similar comment for the paragraph starting in 149 and the rest of the paper.\n* L157-166: The mathematical notations lack clarity in terms of explicitly defining the dimensions of the vectors/matrices and what they represent.\n* Table 4: please include detailed caption so the table can be understood standalone. The same applies for the rest of the tables.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Trank you for your thoughful comments and suggestions.\n\n\nWe address the points you mentioned in the weaknesses part.\n\nMajor comments\n\n1. We add another dataset Natural Questions (NQ). We take AR2 (https://arxiv.org/abs/2110.03611) as the dense retriever and HNSW as the ANN algorithm. The results are listed in the table below. MEVI also achieves better performance than baseline methods on NQ dataset.\n\n| Method | R@5 | R@20 | R@100 |\n| -------- | :-----: | :-----: | :-----: |\n| BM25 | / | 59.1 | 73.7 |\n| AR2 + HNSW | 70.89 | 78.50 | 83.02 |\n||||\n| MEVI Top-10 Clus | 59.61 | 66.45 | 71.63 |\n| MEVI Top-100 Clus | 70.33 | 77.23 | 81.77 |\n| MEVI Top-1000 Clus | 75.57 | 82.83 | 87.31 |\n||||\n| MEVI Top-10 Clus & AR2(HNSW) | 74.10 | 82.11 | 86.43 |\n| MEVI Top-100 Clus & AR2(HNSW) | 74.43 | 82.71 | 87.51 |\n| MEVI Top-1000 Clus & AR2(HNSW) | **75.93** | **83.96** | **88.98** |\n\n2. The online A/B test results come from our company's real online service business, which has brought higher advertising revenue with higher model quality. We present this experimental result to show that MEVI is not only applicable to academic datasets, but also effective in real industrial applications.\n\n3. NCI's high latency does not come from the tree structure, but from its long decoding steps. We add a latency comparison between NCI and MEVI in the following table. We decouple the problem into two parts, one is the difference between MEVI and NCI/DSI, and the other is the difference between RQ and normal k-means. For the first part, each minimal cluster in MEVI contains a set of documents, while each minimal cluster in NCI and DSI contains only one document. This design makes MEVI smaller number of clustering layers, leading to smaller serving latency; also if the doc-id is too long, the model cannot learn well, so the results of MEVI is better than NCI. For the second part, we use RQ instead of normal K-Means in MEVI because RQ performs better. In RQ, each layer uses the residual vectors from the last clustering layer, and conducts k-means clustering among all the vectors. Comparing to hierarchical k-means that focuses on more fine-grained clustering within large clusters, RQ adopts residual information to address the errors of the last clustering layer, making the clustering results more robust. We conduct an experiment to compare RQ with normal hierarchical k-means. In the experiments, we test MEVI-RQ and MEVI-KMeans on MSMARCO Passage dataset, setting layer depth to 4 and the number of clusters per layer to 32. The results are listed below, showing that RQ generally achieves better recall than hierarchical k-means under the same number of layers.\n\n| Method | MRR@10 | Latency (ms) |\n| -------- | :-----: | :-----: |\n| T5-ANCE (HNSW) | 33.21 | 19.71 |\n| NCI | 26.18 | 2899.17 |\n| Top-10 & HNSW | 35.22 | 96.87 |\n| Top-100 & HNSW | 35.60 | 222.55 |\n| Top-1000 & HNSW | 35.83 | 1662.84 |\n\n| Method | MRR@10 | Recall@50 | Recall@1000 |\n| -------- | :-----: | :-----: | :-----: |\n| RQ MEVI Top-10 Clus | 32.05 | 63.25 | 66.82 |\n| RQ MEVI Top-100 Clus | 35.16 | 79.14 | 88.22 |\n| RQ MEVI Top-1000 Clus | **35.76** | **82.37** | **95.17** |\n||||\n| K-Means MEVI Top-10 Clus | 31.62 | 65.09 | 68.25 |\n| K-Means MEVI Top-100 Clus | 34.82 | 77.30 | 87.93 |\n| K-Means MEVI Top-1000 Clus | 35.65 | 81.01 | 94.17 |\n\n4. In the main experiments, we align with existing work (e.g. coCondenser https://arxiv.org/abs/2108.05540, RocketQA https://arxiv.org/abs/2010.08191, AR2 https://arxiv.org/abs/2110.03611) and report MRR@10, Recall@50, Recall@1000. Following your suggestion, we add Figure 2 into the attached PDF to show how the results vary with different $k$, where the ensemble method consistently outperforms T5-ANCE+HNSW. We currently separate the training of the two-tower model and the sequence-to-sequence model to eliminate the overall training cost. We plan to explore joint-training optimization in the future.\n\n\nMinor comments\n\n1. We incorporate the information from sequence-to-sequence model into dense retrievers, achieving better model quality on large datasets with acceptable serving latency. For the generative sequence-to-sequence model, we construct an RQ codebook to cluster the documents, limiting the decoding steps as well as improving the clustering quality. For the ensembling, we take the retrieved documents from the dense retriever and the generative model, then re-rank the documents with a proper score. In experiments, we exhibits better recall performance than baseline dense retriever and generative model. We have also applied MEVI in real industrial applications, bringing higher advertising revenue.\n\n2. Existing state-of-the-art methods can be classified into dense retrievers and generative models, where the former applies to large datasets and the latter performs better on small datasets. MEVI incorporates information from generative models into dense retrievers, achieving better model quality on large datasets.\n\n3. Thanks for your suggestions in items 3-5. We will modify the typos and improve the captions in the next version of this paper. We have also added a table for notations, which will be placed in the appendix later.\n\n\nNotations\n\n| Notation | Explanation |\n| ----- | ----- |\n| $n$ | The number of documents |\n| $d$ | Embedding dimension |\n| $b$ | The number of bits for clustering |\n| $m$ | The number of clustering layers, i.e. the length of cluster-id |\n| $X \\in \\mathbb{R}^{n\\times d}$ | All document embedding |\n| $B_i\\in\\mathbb{R}^{b\\times d}, i=1,...,m$ | Centroid embeddings of clusters |\n| $B\\in\\mathbb{R}^{mb\\times d}$ | Overall centroid embeddings |\n| $C_i\\in\\{0,1\\}^{n\\times b}, i=1,...,m$ | Code-style assignment of documents |\n| $C\\in\\{0,1\\}^{n\\times mb}$ | Overall cluster assignment |\n| $\\widetilde{C}\\in\\{0,1,2,...,2^b-1\\}^{n\\times m}$ | Compact cluster assignment (typos in the original paper will be modified) |\n| $R_i\\in \\mathbb{R}^{n\\times d},i=1,...,m-1$ | Residual embeddings after clustering |\n\n\n"}]

Author rebuttal:
Dear reviewers,

Thank you for taking time in reading our paper and providing valuable comments. We briefly address common questions here.

1. We add another dataset, Natural Questions (full document set version from DPR https://arxiv.org/abs/2004.04906), for comparison. We take AR2 (https://arxiv.org/abs/2110.03611) as the dense retriver and HNSW as the ANN algoritm. As shown in the table below, MEVI performs better than  baseline methods.

| Method | R@5 | R@20 | R@100 |
| -------- | :-----: | :-----: | :-----: |
| BM25 | / | 59.1 | 73.7 |
| AR2 + HNSW | 70.89 | 78.50 | 83.02 |
||||
| MEVI Top-10 Clus | 59.61 | 66.45 | 71.63 |
| MEVI Top-100 Clus | 70.33 | 77.23 | 81.77 |
| MEVI Top-1000 Clus | 75.57 | 82.83 | 87.31 |
||||
| MEVI Top-10 Clus & AR2(HNSW) | 74.10 | 82.11 | 86.43 |
| MEVI Top-100 Clus & AR2(HNSW) | 74.43 | 82.71 | 87.51 |
| MEVI Top-1000 Clus & AR2(HNSW) | **75.93** | **83.96** | **88.98** |


2. We would like to clarify the difference between MEVI and NCI/DSI, and the difference between RQ and k-means for identifier generation. For the first difference, each minimal cluster in MEVI contains a set of documents, while each minimal cluster in NCI and DSI contains only one document. This design makes MEVI smaller number of decoding steps, leading to smaller serving latency. Also, if the doc-id is too long, the model cannot be trained effectively, so the results of MEVI on MSMARCO Passage dataset is better than NCI and has lower serving latency. For the second difference, we choose RQ instead of K-Means in MEVI for its better performance. In RQ, each layer uses the residual vectors from the last clustering layer and conducts k-means clustering among all the vectors. Comparing to hierarchical k-means that focuses on more fine-grained clustering within large clusters in each layer, RQ adopts residual information to address the errors of the previous layer, making the clustering results more precise and robust. We conduct an experiment to compare RQ with normal hierarchical k-means. In the experiments, we test MEVI-RQ and MEVI-KMeans on MSMARCO Passage dataset, setting layer depth to 4 and the number of clusters per layer to 32. The results are listed in the following table, showing that RQ generally achieves better recall than hierarchical k-means under the same number of layers.

| Method | MRR@10 | Recall@50 | Recall@1000 |
| -------- | :-----: | :-----: | :-----: |
| MEVI-RQ Top-10 Clus | 32.05 | 63.25 | 66.82 |
| MEVI-RQ Top-100 Clus | 35.16 | 79.14 | 88.22 |
| MEVI-RQ Top-1000 Clus | **35.76** | **82.37** | **95.17** |
||||
| MEVI-KMeans Top-10 Clus | 31.62 | 65.09 | 68.25 |
| MEVI-KMeans Top-100 Clus | 34.82 | 77.30 | 87.93 |
| MEVI-KMeans Top-1000 Clus | 35.65 | 81.01 | 94.17 |

3. On the MSMARCO Passage dataset, we add an experiment on the state-of-the-art dense retriever AR2 (https://arxiv.org/abs/2110.03611) in addition to T5-ANCE. From the result table below, we can see that MEVI+AR2 achieves a better performance than the corresponding baselines.

| Method | MRR@10 | Recall@50 | Recall@1000 |
| -------- | :-----: | :-----: | :-----: |
| BM25 | 18.7 | 59.2 | 85.7 |
| T5-ANCE + HNSW | 33.21 | 77.30 | 88.61 |
| AR2 + HNSW | 35.54 | 78.80 | 87.11 |
| NCI | 26.18 | 74.68 | 92.44 |
||||
| MEVI Top-10 Clus | 32.05 | 63.25 | 66.82 |
| MEVI Top-100 Clus | 35.16 | 79.14 | 88.22 |
| MEVI Top-1000 Clus | 35.76 | 82.37 | 95.17 |
||||
| MEVI Top-10 Clus & T5-ANCE(HNSW) | 35.22 | 81.29 | 93.21 |
| MEVI Top-100 Clus & T5-ANCE(HNSW) | 35.60 | 82.27 | 95.62 |
| MEVI Top-1000 Clus & T5-ANCE(HNSW) | 35.82 | 82.77 | 97.12 |
||||
| MEVI Top-10 Clus & AR2(HNSW) | 37.00 | 82.64 | 93.46 |
| MEVI Top-100 Clus & AR2(HNSW) | 38.42 | 84.52 | 96.23 |
| MEVI Top-1000 Clus & AR2(HNSW) | **39.16** | **86.12** | **97.65** |

4. To determine the values of $\alpha$ and $\beta$, we search within a proper range and set them according to the model metrics. Since the ensemble process does not incur additional training and inference cost, the time for grid search can be ignored. We show the MRR@10 for different values of $\alpha$ and $\beta$ in the attached PDF. With the best configuration, the ensemble results achieves optimal performance as it fully leverages both components. On MSMARCO dataset, the best hyperparameters searched on the dev set are also optimal on the test set.

Meta-review: This is a well-written paper that proposes a highly novel way to combine generative retrieval and dense retrieval. The experimental results are strong and convincing.

The reviewers did raise a few concerns about this paper, but the most critical aspects of those were adequately addressed during the rebuttal.

Given that the strengths of this paper clearly outweigh its weaknesses, this paper is suitable for publication.

The authors are strongly encouraged to carefully consider all of the reviewer feedback, including the rebuttal-related discussion, and to take meaningful steps to incorporate it into the final version of their paper.
Decision: Accept (poster)