Enhancing the Ranking Context of Dense Retrieval through Reciprocal Nearest Neighbors (2023)

Abstract: Sparse annotation poses persistent challenges to training dense retrieval models; for example, it distorts the training signal when unlabeled relevant documents are used spuriously as negatives in contrastive learning. To alleviate this problem, we introduce evidence-based label smoothing, a novel, computationally efficient method that prevents penalizing the model for assigning high relevance to false negatives. To compute the target relevance distribution over candidate documents within the ranking context of a given query, we assign a non-zero relevance probability to those candidates most similar to the ground truth based on the degree of their similarity to the ground-truth document(s). To estimate relevance we leverage an improved similarity metric based on reciprocal nearest neighbors, which can also be used independently to rerank candidates in post-processing. Through extensive experiments on two large-scale ad hoc text retrieval datasets, we demonstrate that reciprocal nearest neighbors can improve the ranking effectiveness of dense retrieval models, both when used for label smoothing, as well as for reranking. This indicates that by considering relationships between documents and queries beyond simple geometric distance we can effectively enhance the ranking context.

## introduction the training of state-of-the-art ad-hoc text retrieval models @xcite @xcite @xcite @xcite , which are based on transformer language models, relies on large-scale datasets that are sparsely annotated, typically comprising only a small number of relevance judgements for each query. 2 these labels are usually derived from sub-mitting the strongest pseudo-relevance signals in user click logs to human judges for verification. despite potential future endeavors to extend annotation, this sparsity and the resulting issue of false negatives @xcite ., only a minuscule fraction of all documents pertinent to a query are ever seen by users or judges and identified as relevant -will inevitably persist. to eliminate the sparsity, it would be necessary to acquire either human judgements, or perhaps expensive evaluations from large language models, to verify the relevance of the entire document collection (typically tens of millions of documents) with respect to every query in the dataset, leading to an intractable cartesian product. consequently, it is crucial to explore optimizing the utilization of existing information, and extract richer structural relationships between documents and queries, without additional annotations. to this end, in the present work we follow a twopronged approach: first, we employ the concept of reciprocal nearest neighbors (rnn) to improve the estimation of semantic similarity between embeddings of queries and documents. two documents c i and c j are said to be k-reciprocal nearest neighbors if c j is within the k-nearest neighbors of c i , and at the same time c i is within the k-nearest neighbors of c j . second, we attempt to enhance the queryspecific ranking context used to train dense retrievers, going beyond the notion of using mined candidates merely as negatives for contrastive learning. by ranking context we mean a set of documents that are in meaningful relationship to the query and are jointly evaluated with respect to their relevance to the query @xcite . specifically, we use the similarity of ground-truth documents to candidates in the same ranking context as the query as evidence to guide the model's predicted relevance probability distribution over candidates. dense retrieval, the state-of-the-art approach for 1 2 figure 1: query (yellow star), positive (red cross) and negative (full blue circles) document embedding vectors in a shared 2d representation space. based on top-4 nearest neighbors, the positive would be ranked lower than the 3 nearest neighbors of the query. when using top-4 reciprocal nearest neighbors, its ranking is improved, because of its reciprocal relationship to the query, which one of 3 nearest neighbors of the query lacks. adding an extra negative to the context (circle #1) does not affect this ranking, but the second extra negative (#2) disrupts the reciprocal relationship, becoming the 4th nearest neighbor of the positive. on the one hand, the effectiveness of mined negatives is limited by how effectively this dense retriever can already embed queries and relevant documents in close proximity within the shared representation space, although the periodical or dynamic retrieval of negatives during training can partially alleviate this problem @xcite . on the other hand, when the retriever used to mine hard negatives indeed succeeds in retrieving candidates that are semantically relevant to the query, these are often not marked as positives due to the sparsity of annotation and are thus spuriously used as negatives for contrastive learning (false negatives) foot_2 , confounding the training signal @xcite . for this reason, in this work we investigate to what degree these issues can be mitigated through the use of reciprocal nearest neighbors, essentially extracting additional relationship information between queries and documents beyond flat geometric distances, such as the local degree of node connectivity. furthermore, unlike all existing dense retrieval methods, instead of using candidates exclusively as negatives, we propose using their estimated similarity to the ground-truth document(s) as evidence for label smoothing; we thus redistribute probability weight in the target score distribution from the ground truth to a larger number of likely false negatives. finally, our work places a strong emphasis on computational efficiency: label smoothing can be performed entirely offline on cpus and can be trivially parallelized, while no latency is introduced during training and our models can be trained (e.g., on ms marco) within hours, using a single gpu with a batch size of 32. reranking based on reciprocal nearest neighbors, when used, introduces a few milliseconds latency per query on a cpu. by contrast, the current state-of-the-art dense retrieval methods (e.g. @xcite ) depend on the existence of better performing, but computationally demanding re-ranking models such as cross-encoders, which are typically run offline on several gpus with huge batch sizes and are used either for pseudo-labeling additional training data, for discarding negatives which are likely unlabeled positives (i.e., false negatives), or directly for distillation through a teacher-student training scheme. however, besides the very high computational cost of such pipelines, the existence of a model that is more powerful than the retrieval model we wish to train is a very restrictive constraint, and cannot be taken for granted in many practical settings. our main contributions are: (1) we propose evidence-based label smoothing, a novel method which mitigates the problem of false negatives by leveraging the similarity of candidate documents within the ranking context of a query to the annotated ground truth in order to compute soft relevance labels. different from existing methods like teacher-student distillation or pseudo-labeling, our approach does not rely on the existence of more powerful retrieval methods. ## related work our proposed label smoothing, which encourages the model to assign higher relevance scores to documents intimately related to the ground truth, conceptually finds support in prior work that proposed local relevance score regularization @xcite , adjusting retrieval scores to respect local inter-document consistency. despite the entirely different methodology, both methods are premised on the intuition that documents lying closely together in the representation vector space should have similar scores; this in turn is related to the cluster hypothesis, which states that closely related documents (and thus proximal in terms of vector representations) tend to be relevant to the same request @xcite . @xcite recently argued that jointly scoring a large number of candidate documents (positives and negatives) closely related to the same query within a list-wise loss constitutes a queryspecific ranking context that benefits the assessment of relevance of each individual candidate doc-ument with respect to the query. thus, they extended well-established insights and empirical findings from learning-to-rank literature @xcite @xcite to the realm of dense retrieval through transformer-based language models. while in-depth annotation of candidate documents (i.e., hundreds of relevance judgements per query) explicitly provides a rich context for each query in learning-to-rank datasets @xcite @xcite , such information is not available in the sparsely annotated, large-scale datasets used to train dense retrieval models. the relationship exploited thus far to "build a context" (practically, this means mining hard negatives), is simply that of geometric proximity between the embeddings of a query and candidate documents. addressing the problem of sparse annotation, several works have utilized the relevance estimates from supervised (e.g. @xcite @xcite or unsupervised (e.g. lexical: @xcite retrieval methods or other dataset-specific heuristics (e.g. bibliography citations: @xcite to derive soft labels for documents used to train a model, e.g., in a teacherstudent distillation scheme. in this work, we instead shift the perspective from assigning labels based on similarity with respect to the query, to similarity with respect to the ground-truth document(s), but within a query-specific ranking context. we furthermore leverage the concept of reciprocal nearest neighbors, introduced as a reranking method for image re-identification @xcite , to improve the similarity estimate. false negatives have been identified as a significant challenge by prior work, which has employed powerful but computationally expensive cross-encoders @xcite to discard documents that receive a high similarity score to the query and are thus likely relevant from the pool of hard negatives @xcite . however, discarding top-ranking hard negatives also discards potentially useful information for training. recently, @xcite tackled the problem of false negatives through selective sampling of negatives around the rank of the ground-truth document, avoiding candidates that are ranked either much higher than the ground truth (probable false negatives) or much lower (too easy negatives). this approach differs from ours in the perspective of similarity (query-centric vs ground-truth-centric), and in the fact that information is again discarded from the context, as only a small number of negatives is sampled around the positive. additionally, a query latency of up to 650 ms is added during training. @xcite leverage the similarity of candidate documents to the ground truth document (positive), but in a different way and to a different end compared to our work: all documents in the batch ("in-batch negatives") as well as retrieved candidates are used as negatives in an infonce loss term, which penalizes the model when it assigns a low similarity score between a single positive and the query compared to the similarity score it assigns to pairs of this positive with all other candidates. thus, it requires that the ground truth lies closer to the query than other candidates, but the detrimental effect of false negatives on the training signal fully persists. by contrast, our method jointly takes into account all positives and other candidates in the ranking context, and through a kl-divergence loss term requires that the predicted relevance of the query with respect to all documents in the ranking context has a similar probability distribution to the target distribution, i.e., the distribution of similarity between all ground truth positives and all candidate documents in the context. false negatives are thus highly likely to receive a non-zero probability in the target distribution, and the penalty when assigning a non-zero relevance score to false negatives is lower. ## experimental setting datasets. to evaluate the effectiveness of our methods, we use two large-scale, publicly available ad-hoc retrieval collections: the ms marco passage retrieval dataset @xcite , and tripclick, a health document retrieval dataset @xcite . each has distinct characteristics and represents one of the two realistic data settings practically available for training dense retrieval models (see details in appendix a.2, a.3). baselines. to compute the similarity metric based on reciprocal nearest neighbors, and thus the scores used to either rerank candidates at inference time or calculate the smoothed labels for training, we only need access to the encoder extracting the document and query embeddings. the methods we propose are therefore applicable in principle to any dual-encoder dense retriever. however, we eschew training pipelines based on cross-encoders, both to ensure computational efficiency, as well as to eliminate the dependence on more powerful retrieval methods. instead, we choose coder @xcite , a fine-tuning framework that enhances the performance of dense retrievers used as "base models" through a large ranking context of queryspecific candidate documents and a list-wise loss: it serves as a natural framework to evaluate evidencebased label smoothing, because it allows us to directly utilize a large number of soft labels per query, while being very light-weight computationally. following @xcite , we select the ## conclusion we propose evidence-based label smoothing to address sparse annotation in dense retrieval datasets. to mitigate penalizing the model in case of false negatives during training, we compute the target relevance distribution by assigning non-zero relevance probabilities to candidates most similar to the ground truth. to estimate similarity we leverage reciprocal nearest neighbors, which allows considering local connectivity in the shared representation space, and can independently be used for reranking. extensive experiments on two large-scale retrieval datasets and three dense retrieval models demonstrate that our method can effectively improve ranking, while being computationally efficient and foregoing the use of resource-heavy cross-encoders. finally, we find that evaluating on sparsely annotated datasets like ms marco dev may systematically underestimate models with less sharp (i.e. more diffuse) relevance score distributions.