The Curse of Dense Low-Dimensional Information Retrieval for Large Index Sizes (2021)

Abstract: Information Retrieval using dense low-dimensional representations recently became popular and showed out-performance to traditional sparse-representations like BM25. However, no previous work investigated how dense representations perform with large index sizes. We show theoretically and empirically that the performance for dense representations decreases quicker than sparse representations for increasing index sizes. In extreme cases, this can even lead to a tipping point where at a certain index size sparse representations outperform dense representations. We show that this behavior is tightly connected to the number of dimensions of the representations: The lower the dimension, the higher the chance for false positives, i.e. returning irrelevant documents

## introduction information retrieval traditionally used sparse representations like tf-idf or bm25 to retrieve relevant documents for a given query. however, these approaches suffer from the lexical gap problem @xcite . to overcome this issue, dense representations have been proposed @xcite : queries and documents are mapped to a dense vector space and relevant documents are retrieved e.g. by using cosine-similarity. out-performance over sparse lexical approaches has been shown for various datasets @xcite @xcite . previous work showed the out-performance for fixed, rather small indexes. the largest dataset where it has been shown is the ms marco @xcite passage retrieval dataset, where retrieval is done over an index of 8.8 million text passages. however, in production scenarios, index sizes quickly reach 100 millions of documents. we show in this paper, that the performance for dense representations can decrease quicker for increasing index sizes than for sparse representations. for a small index of e.g. 100k documents, a dense approach might clearly outperform sparse approaches. however, with a larger index of several million documents, the sparse approach can outperform the dense approach. we show theoretically and empirically that this effect is closely linked to the number of dimensions for the representations: using fewer dimensions increases the chances for false positives. this effect becomes more severe with increasing index sizes. ## related work a common choice for dense retrieval is to finetune a transformer network like bert @xcite on a given training corpus with queries and relevant documents @xcite @xcite @xcite . recent work showed that combining dense approaches with sparse, lexical approaches can further boost the performance @xcite . while the approaches have been tested on various information and question answering retrieval datasets, the performance was only evaluated on fixed, rather small indexes. @xcite evaluated approaches for eight different datasets having index sizes between 3k and 454k documents. we are not aware of previous work that compares sparse and dense approaches for increasing index sizes and the connection to the dimensionality. the only work we are aware of that systematically studies the encoding size for dense approaches is @xcite ), but they only studied the connection to the document length. ## theory dense retrieval approaches map queries and documents 1 to a fixed size dense vector. the most relevant documents for a given query can then be found using cosine-similarity. using as few dimensions as possible is desirable, as it decreases the memory requirement to store (an index) of millions of vectors and leads to faster retrieval. however, as we show, lower-dimensional representations can have issues with large indices. given a query vector @xmath0, we search our index of document vectors d 1 , ..., d @xmath1: in the following we just show the case for cosine similarity. the proof extends to other similarity functions like dot-product and any p-norm (manhatten, euclidean) as long as the vector space is finite. a finite n-dimensional vector space can be mapped to an n+1-dimensional vectors space with vectors of unit length. in that case, dot-product in n dimensions is equivalent to cosine-similarity in n + 1 dimensions. similar, any p-norm in n dimensions can be re-written as cosine-similarity in n + 1 dimensions. theorem: the probability for false positives (i) increases with the index size n and (ii) with the decreasing dimensionality k. proof (i): given a query q and the relevant document d r . for simplicity, we assume only a single relevant document. if multiple documents are relevant, we consider only the one with the highest cosine similarity. in order that no false positive is returned, cossim(q, d r ) must be greater than cossim(q, d i ) for all @xmath2. assume the possible vectors are independent. then, the probability for a false positive is for an index with n -1 negative elements and p (false positive i ) the probability that a single element is a false positive, i.e. cossim(q, proof (ii): while the previous proof is straightforward, that the chance of false positives increases with larger index sizes, the more interesting aspect is the relation to the dimensionality, i.e., what is the probability p (false positive i ) 1 we use document as a cover-term for text of any length. = p (cossim(q, d i ) > cossim(q, d r )) for a random d i ? we show that this probability decreases with more dimensions. without loss of generality, we assume that the vectors are of unit length. the vectors are then on an k-dimensional sphere with radius 1. a false positive happens if cossim(q, d i ) > cossim(q, d r ), or, equivalent if 1-cossim(q, d i ) < 1-cossim(q, d r ). i.e., we intersect the sphere in k dimensions with a hyperplane in k -1 dimensions. the area of the cut-off portion is defined by 1cossim(q, d r ). all vectors within the cut-off portion (i.e. spherical cap) are false positives. the probability that a random vector will be returned as false positive is: with a cap the surface area of the spherical cap and a sphere the surface area of the sphere in k dimensions. define the surface area of the sphere in k dimensions as a k , then the surface area of a cap is @xcite : with i x (a, b) the regularized incomplete beta function and θ the polar angle, i.e. the angle between q and the relevant document d r . hence: for constant cosine similarity between query q and relevant document d r , i sin 2 θ k-1 2 , 1 2 is a monotonically decreasing function with increasing dimension k. in conclusion, more dimensions decrease the probability for false positives. combining (i) and (ii) shows that a low dimensional representation might work well for small index sizes. however, with more indexed documents, the probability of false positives increases faster for low dimensional representations than for higher dimensional representations. hence, at some index size, higher dimensional representations might outperform the lower-dimensional representation. ## empirical investigation in the proof, we have assumed that vectors are independent and uniformly distributed over the space, which gives us a lower bound on the false positive rate. however, in practice, dense representations are neither independent nor uniformly distributed. as shown in @xcite , dense representations derived from pre-trained transformers like bert map to an anisotropic space, i.e., the vectors occupy only a narrow cone in the vector space. this drastically increases the chance that an irrelevant document is closer to the query embedding than the relevant document. hence, we study how actual dense models are impacted by increasing index sizes and lowerdimensional representations. ## conclusion we have proven and shown empirically that the probability for false positives in dense information retrieval depends on the index size and on the dimensionality of the used representations. these approaches can even retrieve completely irrelevant, randomly generated passages with high probability. it is important to understand the limitations of dense retrieval: