Challenges in Web-Scale Information Retrieval: From Keywords to Embeddings

Table of Links

Abstract and 1 Introduction

2 Background and Related work

2.1 Web Scale Information Retrieval

2.2 Existing Datasets

3 MS Marco Web Search Dataset and 3.1 Document Preparation

3.2 Query Selection and Labeling

3.3 Dataset Analysis

3.4 New Challenges Raised by MS MARCO Web Search

4 Benchmark Results and 4.1 Environment Setup

4.2 Baseline Methods

4.3 Evaluation Metrics

4.4 Evaluation of Embedding Models and 4.5 Evaluation of ANN Algorithms

4.6 Evaluation of End-to-end Performance

5 Potential Biases and Limitations

6 Future Work and Conclusions, and References

2 BACKGROUND AND RELATED WORK

2.1 Web Scale Information Retrieval

In traditional information retrieval, user queries and documents are represented as a list of keywords, and the retrieval is done based on keyword matching. However, simple keyword matching faces many challenges. First, it cannot clearly understand users’ intents. In particular, it cannot estimate users’ positive and negative sentiment and may return opposite results by mistake. Second, it cannot combine synonymous expressions, reducing the diversity of results [18]. Third, it cannot handle spelling errors and will return irrelevant results. Therefore, query alteration is employed to address the above challenges. Unfortunately, it is difficult to cover all kinds of query alterations, especially those newly-appeared alterations.

With the great success of deep learning in natural language processing, both queries and documents can be more meaningfully represented as semantic embedding vectors. Since embedding-based retrieval solves the above three challenges, it has been widely used in modern information systems to facilitate new state-of-the-art retrieval quality and performance. Numerous prior studies have concentrated on deep embedding models, from DSSM [21], CDSSM [46], LSTM-RNN [38], and ARC-I [20] to transformer-based embedding models [10, 16, 39, 40, 45, 53, 54]. They have shown impressive gains with brute-force nearest neighbor embedding search on some small datasets as compared with traditional keyword matching.

Due to the extremely high computational cost and query latency of brute-force vector search, there are many research approaches focusing on large-scale approximate vector nearest neighbor search (ANN) algorithms and systems design [5–7, 11, 19, 24–26, 26, 41, 48]. They can be divided into partition-based and graph-based solutions. Partition-based solutions, such as SPANN [11], divide the whole vector space into a large number of clusters and only do fine-grained search on a small number of the closest clusters to a query in online search. Graph-based solutions, such as DiskANN [48], construct a neighbor graph for the whole dataset and do the best-first traversal from some fixed starting points when a query comes in. Both of these approaches work well on some uniform-distributed datasets.

Unfortunately, when applying embedding-based retrieval in the web scenario, several new challenges emerge. First, web scale data volumes require large models, high embedding dimensions, and a large-scale labeled training dataset to guarantee sufficient knowledge coverage. Second, performance gains of state-of-the-art embedding models verified on small datasets cannot be directly transferred to a web scale dataset (see section 4.4). Third, embedding models need to co-work with ANN systems in order to serve large scale data volumes efficiently. However, different training data distributions may affect the accuracy and system performance of an ANN algorithm, which will greatly reduce the result accuracy as compared to embedding models with brute-force search. Distill-VQ [52] has verified that CoCondenser [17] embedding model with Faiss-IVFPQ ANN index achieves different result accuracy on MSMarco [35] and NQ [28] datasets. Moreover, even the same training data distribution will also result in different embedding vector distributions, which will lead to different ranking trends of the embedding models in brute-force search (KNN) and approximate nearest neighbor search (ANN) (see section 4.6).