Sparse, Dense, and Attentional Representations for Text Retrieval (2021)

Abstract: Dual encoders perform retrieval by encoding documents and queries into dense low-dimensional vectors, scoring each document by its inner product with the query. We investigate the capacity of this architecture relative to sparse bag-of-words models and attentional neural networks. Using both theoretical and empirical analysis, we establish connections between the encoding dimension, the margin between gold and lower-ranked documents, and the document length, suggesting limitations in the capacity of fixed-length encodings to support precise retrieval of long documents. Building on these insights, we propose a simple neural model that combines the efficiency of dual encoders with some of the expressiveness of more costly attentional architectures, and explore sparse-dense hybrids to capitalize on the precision of sparse retrieval. These models outperform strong alternatives in large-scale retrieval.

## introduction retrieving relevant documents is a core task for language technology, and is a component of applications such as information extraction and question answering (e.g., @xcite @xcite . while classical information retrieval has focused on heuristic weights for sparse bag-of-words representations @xcite , more recent work has adopted a two-stage retrieval and ranking pipeline, where a large number of documents are retrieved using sparse high dimensional query/document representations, and are further reranked with learned neural models @xcite . this two-stage approach has achieved state-of-the-art results on * equal contribution. ir benchmarks @xcite @xcite , especially since sizable annotated data has become available for training deep neural models @xcite . however, this pipeline suffers from a strict upper bound imposed by any recall errors in the first-stage retrieval model: for example, the recall@1000 for bm25 reported by @xcite is 69.4. a promising alternative is to perform first-stage retrieval using learned dense low-dimensional encodings of documents and queries @xcite @xcite . the dual encoder model scores each document by the inner product between its encoding and that of the query. unlike full attentional architectures, which require extensive computation on each candidate document, the dual encoder can be easily applied to very large document collections thanks to efficient algorithms for inner product search; unlike untrained sparse retrieval models, it can exploit machine learning to generalize across related terms. to assess the relevance of a document to an information-seeking query, models must both (i) check for precise term overlap (for example, presence of key entities in the query) and (ii) compute semantic similarity generalizing across related concepts. sparse retrieval models excel at the first sub-problem, while learned dual encoders can be better at the second. recent history in nlp might suggest that learned dense representations should always outperform sparse features overall, but this is not necessarily true: as shown in figure 1 , the bm25 model @xcite can outperform a dual encoder based on bert, particularly on longer documents and on a task that requires precise detection of word overlap. 1 this raises questions about the limitations of dual encoders, and the circumstances in which these powerful models do not yet reach the state of the art. here we explore these questions using both theoretical and empirical tools, and propose a new architecture that leverages the strengths of dual encoders while avoiding some of their weaknesses. we begin with a theoretical investigation of compressive dual encoders-dense encodings whose dimension is below the vocabulary size-and analyze their ability to preserve distinctions made by sparse bag-of-words retrieval models, which we term their fidelity. fidelity is important for the sub-problem of detecting precise term overlap, and is a tractable proxy for capacity. using the theory of dimensionality reduction, we relate fidelity to the normalized margin between the gold retrieval result and its competitors, and show that this margin is in turn related to the length of documents in the collection. we validate the theory with an empirical investigation of the effects of random projection compression on sparse bm25 retrieval using queries and documents from trec-car, a recent ir benchmark @xcite . next, we offer a multi-vector encoding model, which is computationally feasible for retrieval like the dual-encoder architecture and achieves significantly better quality. a simple hybrid that interpolates models based on dense and sparse representations leads to further improvements. we compare the performance of dual encoders, multi-vector encoders, and their sparse-dense hybrids with classical sparse retrieval models and attentional neural networks, as well as state-of-the-art published results where available. our evaluations include open retrieval benchmarks (ms marco passage and document), and passage retrieval for question answering (natural questions). we confirm prior findings that full attentional architectures excel at reranking tasks, but are not efficient enough for large-scale retrieval. of the more efficient alternatives, the hybridized multi-vector encoder is at or near the top in every evaluation, outperforming state-of-the-art retrieval results in ms marco. our code is publicly available at https://github.com/google-research /language/tree/master/language /multivec . ## analyzing dual encoder fidelity a query or a document is a sequence of words drawn from some vocabulary v. throughout this section we assume a representation of queries and documents typically used in sparse bag-ofwords models: each query q and document d is a vector in r v where v is the vocabulary size. we take the inner product q, d to be the relevance score of document d for query q. this framework accounts for a several well-known ranking models, including boolean inner product, tf-idf, and bm25. we will compare sparse retrieval models with compressive dual encoders, for which we write f (d) and f (q) to indicate compression of d and q to r k , with k ≪ v, and where k does not vary with the document length. for these models, the relevance score is the inner product f (q), f (d) . (in §3, we consider encoders that apply to sequences of tokens rather than vectors of counts.) a fundamental question is how the capacity of dual encoders varies with the embedding size k. in this section we focus on the related, more tractable notion of fidelity: how much can we compress the input while maintaining the ability to mimic the performance of bag-of-words retrieval? we explore this question mainly through the encoding model of random projections, but also discuss more general dimensionality reduction in §2.2. ## multi-vector encodings the theoretical analysis suggests that fixedlength vector representations of documents may in general need to be large for long documents, if fidelity with respect to sparse high-dimensional representations is important. cross-attentional architectures can achieve higher fidelity, but are impractical for large-scale retrieval @xcite @xcite . we therefore propose a new architecture that represents each document as a fixed-size set of m vectors. relevance scores are computed as the maximum inner product over this set. formally, let @xmath0, . . . , x t ) represent a sequence of tokens, with x 1 equal to the special token @xcite , and define y analogously. then [h 1 (x), . . . , h t (x)] represents the sequence of contextualized embeddings at the top level of a deep transformer. we define a single-vector representation of the query x as f (1) (x) = h 1 (x), and a multi-vector representation of document y as f (m) (y) = [h 1 (y), . . . , h m (y)], the first m representation vectors for the sequence of tokens in y, with @xmath1. the relevance score is defined as max @xmath2...m f (1) (x), f (m) j (y) . although this scoring function is not a dual encoder, the search for the highest-scoring document can be implemented efficiently with standard approximate nearest-neighbor search by adding multiple (m) entries for each document to the search index data structure. if some vector f (m) j (y) yields the largest inner product with the query vector f (1) (x), it is easy to show the corresponding document must be the one that maximizes the relevance score ψ (m) (x, y). the size of the index must grow by a factor of m, but due to the efficiency of contemporary approximate nearest neighbor and maximum inner product search, the time complexity can be sublinear in the size of the index @xcite . thus, a model using m vectors of size k to represent documents is more efficient at run-time than a dual encoder that uses a single vector of size mk. this efficiency is a key difference from the poly-encoder @xcite , which computes a fixed number of vectors per query, and aggregates them by softmax attention against document vectors. @xcite propose a similar architecture for language modeling. because of the use of softmax in these approaches, it is not possible to decompose the relevance score into a max over inner products, and so fast nearestneighbor search cannot be applied. in addition, these works did not address retrieval from a large document collection. analysis. to see why multi-vector encodings can enable smaller encodings per vector, consider an idealized setting in which each document vector is the sum of m orthogonal segments such that @xmath3. 3 an orthogonal segmentation can be obtained by choosing the segments as a partition of the vocabulary. theorem 1. define vectors q, d 1 , d 2 ∈ r v such that q, d 1 > q, d 2 , and assume that both d 1 and d 2 can be decomposed into m segments such that: remark 1. the bm25 score can be computed from non-negative representations of the document and query; if the segmentation corresponds to a partition of the vocabulary, then the segments will also be non-negative, and thus the condition q, d 2 ≥ q, d the relevant case is when the same segment is maximal for both documents, q, d ## experimental setup the full ir task requires detection of both precise word overlap and semantic generalization. our theoretical results focus on the first aspect, and derive theoretical and empirical bounds on the sufficient dimensionality to achieve high fidelity with respect to sparse bag-of-words models as document length grows, for two types of linear random projections. the theoretical setup differs from modeling for realistic information-seeking scenarios in at least two ways. first, trained non-linear dual encoders might be able to detect precise word overlap with much lower-dimensional encodings, especially for queries and documents with a natural distribution, which may exhibit a low-dimensional subspace structure. second, the semantic generalization aspect of the ir task may be more important than the first aspect for practical applications, and our theory does not make predictions about how encoder dimensionality relates to such ability to compute general semantic similarity. we relate the theoretical analysis to text retrieval in practice through experimental studies on three tasks. the first task, described in §5, tests the ability of models to retrieve natural language documents that exactly contain a query and evaluates both bm25 and deep neural dual encoders on a task of detecting precise word overlap, defined over texts with a natural distribution. the second task, described in §6, is the passage retrieval sub-problem of the opendomain qa version of the natural questions @xcite ; this benchmark reflects the need to capture graded notions of similarly and has a natural query text distribution. for both of these tasks, we perform controlled experiments varying the maximum length of the documents in the collection, which enables assessing the relationship between encoder dimension and document length. to evaluate the performance of our best models in comparison to state-of-the-art works on large-scale retrieval and ranking, in §7 we report results on a third group of tasks focusing on passage/document ranking: the passage and document-level ms marco retrieval datasets @xcite . here we follow the standard two-stage retrieval and ranking system: a first-stage retrieval from a large document collection, followed by reranking with a cross-attention model. we focus on the impact of the first-stage retrieval model. ## containing passage ict task we begin with experiments on the task of retrieving a wikipedia passage y containing a sequence of words x. we create a dataset using wikipedia, following the inverse cloze task definition by @xcite , but adapted to suit the goals of our study. the task is defined by first breaking wikipedia texts into segments of length at most l. these form the document collection d. queries x i are generated by sampling sub-sequences from the documents y i . we use queries of lengths between 5 and 25, and do not remove the queries x i from their corresponding documents y i . we create a dataset with 1 million queries and evaluate retrieval against four document collections d l , for @xmath4,100,200,400. each d l contains 3 million documents of maximum length l tokens. in addition to original wikipedia passages, each d l contains synthetic distractor documents, which contain the large majority of words in x but differ by one or two tokens. 5 k queries are used for evaluation, leaving the rest for training and validation. although checking containment is a straightforward machine learning task, it is a good testbed for assessing the fidelity of compressive neural models. bm25-bi achieves over 95 mrr@10 across collections for this task. figure 4 (left) shows test set results on reranking, where models need to select one of 200 passages (top 100 bm25-bi and 100 random candidates). it is interesting to see how strong the sparse models are relative to even a 768dimensional de-bert. as the document length increases, the performance of both the sparse and dense dual encoders worsens; the accuracy of the de-bert models falls most rapidly, widening the gap to bm25. full cross-attention is nearly perfect and does not degrade with document length. de-bert-768, which uses 8 vectors of dimension 768 to represent documents, strongly outperforms the best de-bert model. even de-bert-64, which uses 8 vectors of size only 64 instead (thus requiring the same document collection size as de-bert-512 and being faster at inference time), outperforms the de-bert models by a large margin. figure @xcite shows results for the much more challenging task of retrieval from 3 million candidates. for the latter setting, we only evaluate models that can efficiently retrieve nearest neighbors from such a large set. we see similar behavior to the reranking setting, with the multi-vector methods exceeding bm25-uni performance for all lengths and de-bert models under-performing bm25-uni. the hybrid model outperforms both components in the combination with largest improvements over me-bert for the longestdocument collection. for document retrieval, a passage is correct for a query x if it contains a string that matches exactly an annotator-provided short answer for the question. we form a reranking task by considering the top 100 results from bm25-uni and 100 random samples, and also consider the full retrieval setting. bm25-uni is used here instead of bm25-bi, because it is the stronger model for this task. our theoretical results do not make direct predictions for performance of compressive dual encoder models relative to bm25 on this task. they do tell us that as the document length grows, low-dimensional compressive dual encoders may not be able to measure weighted term overlap precisely, potentially leading to lower performance on the task. therefore, we would expect that higher dimensional dual encoders, multi-vector encoders, and hybrid models become more useful for collections with longer documents. figure 5 (left) shows heldout set results on the reranking task. to fairly compare systems that operate over collections of different-sized passages, we allow each model to select approximately the same number of tokens (400) and evaluate on whether an answer is contained in them. for example, models retrieving from d 50 return their top 8 passages, and ones retrieving from d 100 retrieve top 4. the figure shows this recall@400 tokens across models. the relative performance of bm25-uni and de-bert is different from that seen in the ict task, due to the semantic generalizations needed. ## related work we have mentioned research on improving the accuracy of retrieval models throughout the paper. here we focus on work related to our central focus on the capacity of dense dual encoder representations relative to sparse bags-of-words. in compressive sensing it is possible to recover a bag of words vector x from the projection ax for suitable a. bounds for the sufficient dimensionality of isotropic gaussian projections @xcite are more pessimistic than the bound described in §2, but this is unsurprising because the task of recovering bags-of-words from a compressed measurement is strictly harder than recovering inner products. @xcite ask whether it is possible to exactly recover sentences (token sequences) from pretrained decoders, using vector embeddings that are added as a bias to the decoder hidden state. because their decoding model is more expressive (and thus more computationally intensive) than inner product retrieval, the theoretical issues examined here do not apply. nonetheless, @xcite empirically observe a similar dependence between sentence length and embedding size. @xcite represent sentences as bags of random projections, finding that high-dimensional projections (@xmath5. these empirical results provide further empirical support for the hypothesis that bag-ofwords vectors from real text are ''hard to embed'' in the sense of @xcite . our contribution is to systematically explore the relationship between document length and encoding dimension, focusing on the case of exact inner product-based retrieval. we leave the combination of representation learning and approximate retrieval for future work. ## conclusion transformers perform well on an unreasonable range of problems in natural language processing. yet the computational demands of large-scale retrieval push us to seek other architectures: cross-attention over contextualized embeddings is too slow, but dual encoding into fixedlength vectors may be insufficiently expressive, sometimes failing even to match the performance of sparse bag-of-words competitors. we have used both theoretical and empirical techniques to characterize the fidelity of fixed-length dual encoders, focusing on the role of document length. based on these observations, we propose hybrid models that yield strong performance while maintaining scalability.