PaperlayerView exact revision on arXiv

Source-linked AI summary

Model-enhanced Vector Index

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

arXiv:2309.13335v2cs.IR

TL;DR

Embedding-based retrieval is efficient but has limits on differentiability, while generation-based methods face latency, scale, and update challenges. MEVI combines sequence-to-sequence generation with dense retrieval through an RQ codebook, and reports better benchmark performance with low serving latency.

  • Problem

    Embedding-based retrieval is efficient but ANN indexing limits end-to-end differentiability, while generative retrieval faces scale, latency, and document-update challenges.

    Source: §1 · p. 2

  • Method

    MEVI uses an RQ codebook and sequence-to-sequence model to generate candidate virtual clusters, then searches their document embeddings with ANN.

    Source: §1 · p. 2

  • Results

    Across MSMARCO Passage and Natural Questions, MEVI improves performance; on MSMARCO Passage it reports +3.62% MRR@10 over existing methods.

    Source: §1 · p. 3

  • Takeaways & Limitations

    MEVI achieves high recall and fast retrieval on large-scale corpora, supporting its applicability to real-world applications.

    Source: §6 · p. 10

    The twin-tower and sequence-to-sequence models are not jointly learned, and sequence-to-sequence capacity remains insufficient for large-scale corpora within acceptable inference latency.

    Source: §5 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

Embedding-based retrieval offers low latency but is not end-to-end differentiable, while generative retrieval struggles with scale, serving latency, and updates. MEVI generates candidate clusters from an RQ codebook before ANN search and reports stronger recall across two benchmarks with low serving latency.

  • Embedding-based retrieval uses twin-tower vectors and ANN search, but ANN’s discrepancy from brute-force KNN limits end-to-end differentiability and recall.Source: §1 · p. 2
  • Generation-based retrieval can outperform embedding methods on small corpora, but struggles with large-scale serving latency and document updates.Its fixed tree index means corpus changes require retraining.Source: §1 · p. 2
  • MEVI generates virtual cluster identifiers from an RQ codebook, then uses ANN over cluster embeddings to retrieve relevant documents.A moderate codebook size reduces decoder computation; its size balances recall and inference latency.Source: §1 · p. 2
  • MEVI supports document insertion and removal; new documents can be recalled when the model generates their semantically related virtual clusters.The paper also reports validating MEVI’s ability to handle dynamic corpora.Source: §1 · pp. 2–3
  • On MSMARCO Passage, MEVI gains +3.62% MRR@10, +7.32% R@50, and +10.54% R@1000; on Natural Questions, gains are +5.04% R@5, +5.46% R@20, and +5.96% R@100.Source: §1 · p. 3

2 Related work

The related work contrasts sparse, dense, and autoregressive retrieval. Sparse and dense methods have distinct limitations, while autoregressive methods face serving and update challenges.

  • Document retrieval aims to find relevant documents for queries using an index that supports fast responses.Source: §2 · p. 3
  • Sparse retrieval builds an inverted index from terms but can miss relevant documents expressed with different wording.Source: §2 · p. 3
  • Dense retrieval represents queries and documents as vectors and uses ANN search, but the KNN–ANN discrepancy challenges recall, especially with document-query distribution differences.Source: §2 · p. 3
  • Autoregressive retrieval generates document identifiers from queries, but existing methods are limited by serving latency and inability to handle document updates.Examples include DSI, NCI, and SEAL, with different identifier and index designs.Source: §2 · p. 3

3 Model-enhanced vector index

MEVI combines a twin-tower vector index with autoregressive retrieval over Residual Quantization clusters. It uses the generated clusters to refine embedding-based candidate retrieval through ensemble strategies.

3 Model-enhanced vector index

  • MEVI combines a twin-tower representation model for embedding retrieval with an autoregressive model that generates relevant document clusters, then ensembles their candidates.The RQ structure supplies cluster-code labels for training the sequence-to-sequence model.Source: §3 · pp. 3–4, Figure 1 · p. 4

3.1 Organizing documents with Residual Quantization

  • Residual Quantization iteratively clusters document embeddings and their residuals, producing fixed-length codes that the sequence-to-sequence model generates as candidate clusters.Documents sharing identical codes are treated as belonging to the same cluster.Source: §3.1 · pp. 4–5

3.2 Ensemble process

  • MEVI can restrict embedding search to top-k generated clusters or combine those candidates with original embedding results and rerank using cluster scores.Combining candidate sets is described as more robust because the RQ structure may be inaccurate and beam search is lossy.Source: §3.2 · pp. 5–6

4 Experiments

The experiments evaluate MEVI on MSMARCO Passage and Natural Questions using standard retrieval metrics and compare it with sparse, dense, and model-based baselines. They describe the RQ, sequence-to-sequence, twin-tower, and ensemble configurations used.

4 Experiments

  • Experiments assess retrieval effectiveness, unseen-document handling, RQ, efficiency, hyperparameters, and practical applications.The evaluation uses MSMARCO Passage and Natural Questions benchmarks.Source: §4 · p. 6

4.1 Datasets & metrics

  • MSMARCO Passage and Natural Questions are evaluated with Recall@K and MRR@K, measuring relevant-item retrieval and the rank of the first relevant item.The MSMARCO version contains 8.8 million passages and about 510,000 queries; the NQ collection uses 21 million Wikipedia passages.Source: §4.1 · p. 6

4.2 Implementation details

  • The setup uses a four-layer RQ codebook, NCI trained on query-code pairs, T5-ANCE and AR2 embeddings, brute-force search within generated clusters, and BM25, SPLADE, dense retrieval, and NCI baselines.The cluster search typically covers about ten thousand candidates at beam size 1000.Source: §4.2 · pp. 6–7

4.3 Results on MSMARCO Passage

On MSMARCO Passage, the ensemble of embedding-based and generation-based retrieval outperforms all baselines. MEVI improves retrieval metrics over ANN baselines and performs better than NCI, especially on MRR@10.

4.3 Results on MSMARCO Passage

  • Considering more generated clusters improves retrieval performance, and vanilla MEVI with top-1000 clusters outperforms dense retrieval methods.After ensembling, MEVI exceeds ANN performance using only top-10 clusters.Source: §4.3 · p. 7
  • MEVI performs better than NCI, especially on MRR@10, which the authors attribute to smaller decoder steps that allow the model to learn a better ranking.Source: §4.3 · p. 7
  • 3.62% / 2.62% for MRR@10, 7.32% / 5.43% for Recall@50, and 10.54% / 8.00% for Recall@1000: MEVI improves over AR2 / T5-ANCE ANN, respectively.The ensemble of embedding-based and generation-based retrieval outperforms all tested baselines on MSMARCO Passage.Source: Table 2 · p. 7, §4.3 · p. 7

4.4 Results on Natural Questions

On Natural Questions, MEVI improves recall over the ANN baseline; in a dynamic-document test, it retains performance on unseen documents. Retrieval recall declines less as more clusters are searched.

4.4 Results on Natural Questions

  • MEVI improves Recall@5 by 5.04%, Recall@20 by 5.46%, and Recall@100 by 5.96% over the ANN baseline on Natural Questions.After ensembling, it also outperforms AR2 (HNSW) while searching only 10 clusters.Source: Table 3 · p. 8, §4.4 · p. 8

4.5 Dynamic update of documents

  • MEVI’s recall drops less as more clusters are retrieved, which the experiments attribute to the additional semantic information available from more clusters.Source: §4.5 · p. 8
  • When trained on a random 90% of documents and evaluated on all documents, every tested method loses accuracy, but MEVI still performs well against ANN on unseen documents.Table 4 reports the train-on-90%, evaluate-on-all setting.Source: Table 4 · p. 8, §4.5 · p. 8

4.6 Residual quantization

Residual Quantization (RQ) generally yields better recall than hierarchical KMeans at the same cluster count. RQ configuration trades retrieval quality against candidate volume, memory, and inference latency.

4.6 Residual quantization

  • RQ(x × y) denotes x layers with y bits, or 2^y centroids, per layer, for 2^(xy) total clusters.The configuration analysis reports MRR@10, Recall@100, top-k cluster recall, and average retrieved documents per query.Source: §4.6 · p. 8, Table 6 · p. 9
  • RQ generally achieves better recall than normal hierarchical KMeans with the same number of clusters.The comparison uses depth 4 and 32 centroids per layer; RQ uses residual information to address errors from the previous layer.Source: §4.6 · p. 8, Table 5 · p. 9
  • RQ(4 × 5) is the more suitable MSMARCO configuration at a comparable order of retrieved-document volume, while RQ(5 × 5) performs better but requires more clusters.Larger configurations also require more decoder steps, increasing inference latency; the paper identifies memory challenges for RQ(5 × 5).Source: §4.6 · pp. 8–9, Table 6 · p. 9

4.7 Efficiency

MEVI offers a performance–latency trade-off: at k = 10, it improves MRR@10 by more than two absolute points over ANN with latency below 100 ms. Latency rises with cluster count, while ANN remains fastest.

4.7 Efficiency

  • MEVI latency increases with retrieved-cluster count because larger beam sizes extend autoregressive generation and increase the candidate search volume.Source: §4.7 · p. 9
  • ANN is the fastest method; FP16 or ONNX Runtime acceleration could further reduce MEVI’s average serving latency to less than 40 ms.NCI has substantially longer decoder steps than MEVI.Source: §4.7 · p. 9
  • At k = 10, MEVI improves MRR@10 by more than 2 absolute points over ANN with less than 100 ms latency.The latency-performance comparison was tested on a single A6000 card.Source: Table 7 · p. 9, §4.7 · p. 9

4.8 Hyperparameters

On MSMARCO Passage, MEVI’s ensemble consistently outperforms T5-ANCE with HNSW. The ensemble remains above the MEVI-only baseline across a range of α and β settings.

4.8 Hyperparameters

  • The selected hyperparameter configuration is reported to leverage information from both ensemble components.Source: §4.8 · p. 10
  • MEVI ensemble results consistently outperform T5-ANCE (HNSW) across the tested K values for Recall and MRR.Source: Figure 2 · p. 10, §4.8 · p. 10
  • The ensemble outperforms the MEVI Top-1000 Cluster baseline when 0.3 ≤ α ≤ 0.7 and 0.01 ≤ β ≤ 0.03.The reported MRR@10 configuration searches α and β; the grid search adds no training or inference cost.Source: Figure 3 · p. 10, §4.8 · p. 10

5 Limitations & future works

The authors identify separate training and inference-capacity limitations in MEVI and suggest joint training and model-efficiency techniques as future directions.

5 Limitations & future works

  • The twin-tower and sequence-to-sequence models are not jointly learned, which may prevent optimal retrieval performance.Source: §5 · p. 10
  • The sequence-to-sequence model lacks sufficient capacity for large-scale corpora within acceptable inference latency.Source: §5 · p. 10
  • The authors suggest joint training of RQ codebooks and both models, plus compression or acceleration techniques such as distillation and non-autoregressive generation.Source: §5 · p. 10

6 Conclusion

MEVI combines autoregressive sequence-to-sequence retrieval with dense representations, generating cluster identifiers before refining candidates with embedding-based results. It outperforms baselines on MSMARCO Passage and Natural Questions.

6 Conclusion

  • MEVI combines an autoregressive sequence-to-sequence model with a twin-tower dense representation model for large-scale retrieval.Source: §6 · p. 10
  • MEVI generates relevant cluster identifiers, then combines documents from the top-k clusters with embedding-based retrieval results for candidate re-ranking.Source: §6 · p. 10
  • MEVI achieves better model performance than baselines on MSMARCO Passage and Natural Questions.Source: §6 · p. 10

Related papers

Loading 2309.13335v2…