Simple and Effective Unsupervised Redundancy Elimination to Compress Dense Vectors for Passage Retrieval (2021)

Abstract: Recent work has shown that dense passage retrieval techniques achieve better ranking accuracy in open-domain question answering compared to sparse retrieval techniques such as BM25, but at the cost of large space and memory requirements. In this paper, we analyze the redundancy present in encoded dense vectors and show that the default dimension of 768 is unnecessarily large. To improve space efficiency, we propose a simple unsupervised compression pipeline that consists of principal component analysis (PCA), product quantization, and hybrid search. We further investigate other supervised baselines and find surprisingly that unsupervised PCA outperforms them in some settings. We perform extensive experiments on five question answering datasets and demonstrate that our best pipeline achieves good accuracy–space trade-offs, for example, 48\times compression with less than 3% drop in top-100 retrieval accuracy on average or 96\times compression with less than 4% drop. Code and data are available at http://pyserini.io/ .

## introduction dense passage retrieval (dpr; @xcite improves end-to-end retrieval accuracy in open-domain question answering (qa) by representing queries and documents in a lowdimensional, dense vector space. however, the vastly increased space and memory demands for storing and loading the dense vectors call for effective compression methods @xcite . for example, the size of the original dpr vector (flat) index on the wikipedia corpus is about 61 gb, while its sparse counterpart-bm25 inverted index-only uses 2.4 gb. the staggering increase of around 25× in space requirements only yields an average gain of 2.5% in top-100 accuracy across * equal contribution five datasets @xcite , indicating potential redundancy in the dense representations. in this work, we quantify redundancy within the dense vectors encoded by the dpr model using explained variance ratio and mutual information. figure 1 shows that the original 768 dimensions is unnecessarily large as both the mutual information and explained variance ratio start to plateau at around 256 dimensions. based on this observation, we further propose a simple yet effective pipeline for dense retrieval compression that includes principal component analysis (pca), product quantization (pq), and hybrid search to reduce index size while retaining effectiveness. we also compare other compression options, including supervised dimensionality reduction, where we fine-tune a linear projection layer on top of the pre-trained dpr model using relevance labels. surprisingly, we find that pca achieves top-100 retrieval accuracy that is better than the two supervised dimensionality reduction techniques for 256 and 128 dimensions, while supervised techniques outperform (unsupervised) pca for 64 dimensions. our techniques support different accuracy-space trade-offs, but one sweet spot manages to compress the dense vectors by 96× with less than 4% drop in top-100 accuracy on average across five standard qa datasets. finally, we incorporate our pipeline with the bm25 inverted index for sparse-dense hybrid search, where we can achieve 16× compression without any accuracy drop compared to the original dpr results. ## background and related work sparse retrieval methods such as bm25 @xcite have established strong baselines in open-domain qa @xcite . recently, dense retrieval emerges as a promising alternative @xcite @xcite @xcite in end-to-end question answering, but at the cost of increased space requirements. efforts have been made towards developing memory efficient baselines @xcite , but the topic still remains under-explored. in the following, we briefly introduce how dense retrieval works during training and inference. given a collection of passages and a qa task, dpr @xcite adopts a bi-encoder structure where encoders f q (•) and f d (•) are independent bert @xcite models that encode questions/passages into dense vectors. the relevance between the question q and passage d is defined by the dot product between their corresponding vectors as v q v d , where v @xmath0. the relevance score is used to rank the passages during retrieval with nearest neighbor search techniques. during training, given a question q, a positive passage d + that contains the answer for q, and m negative passages d - 1 , d - 2 , ...d - m , the training objective is: ## compressing dense representations as mentioned above, dpr's encoders produce dense vectors of 768 dimensions by default, which we will show is unnecessarily large below. in this section, we discuss how to quantify the redundancy in the encoded vectors and how to improve dpr's space efficiency by reducing this redundancy. ## experimental setup datasets and metrics we evaluate the top-k retrieval accuracy of our compression methods on five qa datasets examined in the original dpr paper @xcite : nq, triviaqa, wq, curatedtrec, and squad. the top-k retrieval accuracy is defined as the fraction of questions that have at least one correct answer span in the top-k retrieved passages. following previous work, we use @xmath1, 100}. we use the combination of nq, triviaqa, wq, and curatedtrec to train our models, following the same setting as dpr. model training for dpr, instead of the original facebook implementation, we use the implementation of @xcite , which takes advantage of gradient caching to save gpu memory usage and mixed precision training to speed up the learning process. we find that using a learning rate of 10 -6 and training the model for 40 epochs achieve better effectiveness than the default dpr setting. we refer to the original dpr model, which has 768 dimensional output vectors, as dpr-768. other hyperparameters are identical to default dpr @xcite . for the compression methods, we consider the reduced dimensions @xmath2, 128, 64} according to figure 1 . for the supervised approach, the linear layer is trained for one epoch with a learning rate of 10 -3 while freezing the backbone dpr model (i.e., bert), and we refer to these models as lineard. for comparison, we train models with identical architecture to linear-d, but without freezing the bert model, and refer to them as dpr-d. for the unsupervised pca approach, we fit the pca transformation with question and passage embeddings produced by the original dpr-768 model. the question embeddings are from the original embeddings of questions in the training set. a total of 160k passage embeddings are randomly sampled from the passage embeddings of the entire corpus (i.e., original dense index). we utilize the pq features from faiss @xcite . the number of codewords for each sub-vector is fixed at 256 (i.e., using 8 bits). following @xcite , we change the number of sub-vectors for dense embeddings such that the average memory of each dimension is reduced. combined with dimensionality reduction methods, we decrease the occupied space of each dimension from 32 bits to 1 or 2 bits. sparse-dense hybrid search @xcite have shown that hybrid search significantly improves the retrieval accuracy of dpr. therefore, we fuse the dpr's and bm25's retrieval results following their same rule, where the final hybrid ## results in this section, we characterize the trade-offs between retrieval accuracy and space requirements using different combinations of our proposed techniques. all experiments are implemented using the pyserini ir toolkit @xcite . ## conclusions this paper analyzes the redundancy within dense representations from dpr, a popular dense retrieval model. we propose a simple yet effective compression pipeline that enables trade-offs between space and accuracy, which drastically reduces index size while preserving end-to-end retrieval accuracy at reasonable levels.