Enhancing the Ranking Context of Dense Retrieval through Reciprocal Nearest Neighbors
Authors: George Zerveas
Navid Rekabsaz
Carsten Eickhoff
Venue: EMNLP 2023 Main (2023)
Keywords: dense retrieval
reciprocal nearest neighbors
ranking context
contrastive learning
list-wise loss
false negatives
label smoothing
transformers
Large Language Models
information retrieval
natural language processing
deep learning
TL;DR: To address sparse document annotation and false negatives when training dense retrieval models, we introduce evidence-based label smoothing that leverages reciprocal nearest neighbors to improve the ranking context.

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.

Enhancing the Ranking Context of Dense Retrieval through Reciprocal Nearest Neighbors
George Zerveas Brown University, USA
Navid Rekabsaz
Carsten Eickhoff
JKU Linz
University of Tübingen, Germany C. c.eickhoff@acm.org
ggorge
LIT AI Lab, Austria navid. rekabsazz@jk..at
mitting the strongest pseudo-relevance signals in user click logs to human judges for verification. training dense retrieval models, for example by distorting the training signal when unlabeled relevant documents are used spuriously as neg- atives in contrastive learning. To alleviate this problem, we introduce evidence-bard label smoothing, 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 con- text of given query, those candidates most similar the ground truth are assigned non- zero relevance probability based on the degree of their similarity to the ground-truth docu- ment(s). To estimate relevance we leverage an improved similarity metric based on recip- rocal nearest neighbors, which can also be used independently to rerank candidates in post- processing. Through extensive experiments on large-scale ad hoc text retrieval datasets, we demonstrate that reciprocal nearest neigh- bors can improve the ranking effectiveness of dense retrieval models, both when used for la- bel smoothing, as well as for reranking. This indicates that by considering relationships be- tween documents and queries beyond simple geometric distance we can effectively enhance the ranking context."
Abstract
Sparse annotation poses persistent challenges
Despite potential future endeavors to extend anno- tation, this sparsity and the resulting issue false negatives (Qu et al., 2021; Zhou et al., 2022) - i.c.. only minuscule fraction of all documents perti- nent to a query are ever seen by users or judges and identified relevant will inevitably persist. To eliminate the sparsity, would be necessary acquire either human judgements, or perhaps ex- pensive evaluations from Large Language Models, to verify the relevance of the entire document col- lection (typically tens of millions of documents) with respect to every query in the dataset, leading to intractable Cartesian product. Consequently, it is crucial explore optimizing the utilization of existing information, and extract richer struc- tural relationships between documents and queries. without additional annotations.
To this end, in the present work we follow a two- pronged approach: first, we employ the concept of reciprocal nearest neighbors (rNN) to improve the estimation of semantic similarity between embed- dings of queries and documents. Two documents and 0j are said to be k-reciprocal nearest neighbors if ej is within the k-nearest neighbors of c, and at the same time c, is within the k-nearest neighbors of cj. Second, we attempt to enhance the query- specific ranking context used to train dense retriev- ers, going beyond the notion of using mined candi- dates 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 (Ai et al., 2018; Zerveas et al., 2022). Specifically, use the similarity of ground-truth documents to candidates in the same ranking con- text as the query as evidence to guide the model's 's predicted relevance probability distribution over candidates.
1 Introduction
The training of statc-of-the-arr ad-hoc text retrieval models (Nogueira and Cho, 2020; Santhanam et al., 2021: Zhan et al., 2021; Ren et al., 2021b,a; Gao and Callan, 2021; Zhang et al., 2022; Lu et al., 2022), which are based on transformer Language Models, relies on large-scale datasets that are sparsely annotated, typically comprising only small number of relevance judgements for each query. These labels are usually derived from sub-
'Ou code other resources are available at: https://ggh /ogs:///gihubl com/ /eaa//CCC
FF.g., on average 1.06 documents per query in MS MARCO, Bajaj et al., 2018.
Dense retrieval, the state-of faute-of-the-ee the-art approach for

---

as relevant in the dataset.
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 dy- namic retrieval of negatives during training can partially alleviate this problem (Xiong et al., 2020; Zhan et al., 2021). On the other hand, when the retriever used mine hard negatives indeed suc- ceeds 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)², confounding the train- ing signal (Qu et al., 2021; Zhou et al., 2022). For this reason, in this work we investigate what degree these issues can be mitigated through the use of reciprocal nearest neighbors, essentially extracting additional relationship information be- tween queries and documents beyond flat geomet- ric distances, such as the local degree of node con- nectivity. Furthermore, unlike all existing dense retrieval methods, instead of using candidates ex- clusively negatives, we propose using their esti- mated similarity the ground-truth document(s) 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.
Figure 1: Query (yellow star), positive (red cross) and negative (full blue circles) document embedding vectors in shared 2D representation space. Based top-4 Nearest Neighbors, the positive would be ranked lower than the? 3 nearest neighbors of the query. When us- ing 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 nega- tive (#2) disrupts the reciprocal relationship, becoming the 4th nearest neighbor of the positive.
single-stage ad-hoc retrieval, is premised mod- eling relevance between query and document the geometric proximity (e.g., dot-product or cosine similarity) between their respective embed- dings in the common representation vector space. Top retrieval results are therefore the documents whose embeddings are the nearest neighbors of the query embedding. However, this modeling as- sumption may be sub-optimal: previous work in the field of image re-identification has shown that, while geometric similarity can easily differentiate between candidate embeddings in near proximity from a query embedding, the differences between relevance scores of candidate embeddings become vanishingly small as distance from the query in- creases (Qin et al., 2011). It was found that the degree of overlap between sets of reciprocal near- est neighbors can be used to compute improved measure of similarity between query and candidate embeddings (Zhong et al., 2017).
Finally, our work places a strong emphasis on computational efficiency: label smoothing can be performed entirely offline CPUs and can be triv- ially parallelized, while latency is introduced during training and our models can be trained (e.g., on MS MARCO) within hours, using single GPU with a batch size of 32. Reranking based on recip- rocal nearest neighbors, when used, introduces a few milliseconds latency per query on a CPU.
By contrast, the current state-of-the-as dense retrieval methods (e.g. (Qu et al., 2021; Ren et al., 2021b)) depend on the existence of better perform- ing, but computationally demanding re-ranking models such as cross-encoders, which are typically run onf 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 teacher-student
Moreover, geometric similarity is used in min- ing "hard" negatives, which have been consistently found to improve performance compared to random in-batch negatives (Xiong al., 2020; Zhan et al., 2021; Qu et al., 2021; Zerveas et al., 2022). Hard negatives are typically the top-ranked candidates re- trieved by a dense retriever (nearest neighbors to a query embedding) that are not explicitly annotated
'Qu et al., 2021 estimate that about 70% of the top 5 candidates retrieved by top- perforrrfoornngoom dense retrieval model that are not labeled as positive are actually relevant.

---

training scheme. However, besides the very high computational cost of such pipelines, the existence of model that is more powerful than the retrieval model we wish to train is a very restrictive con- straint, and cannot be taken for granted in many practical settings.
ument with respect to the query. Thus, they ex- tended well-established insights and empirical find- ings from Learning-to-Rant literature (Cao et al., 2007; Ai et al., 2019, 2018) to the realm of dense re- trieval through transformer-based Language Mod- cls. While in-depth annotation of candidate doc- uments (i.e., hundreds of relevance judgements per query) explicitly provides rich context for each query in Learning-to-Ran datasets (Qin al., 2010; Chapelle and Chang, 2010; Dato al., 2016), such information not available in the sparsely an- notated, 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 query and candidate documents.
Our main contributions are:
(I) We propose evidence-bast based label smoothing, a novel method which mitigates the problem of false negatives by leveraging the similarity of candidate documents within the ranking contexl 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-labelingg our approach does not rely the existence of more powerful retrieval methods.
(2) We explore the applicability of the concept of reciprocal nearest neighbors in improving the simi- larity metric between query and document embed- dings in the novel setting of ad-hoc text retrieval. (3) Through extensive experiments on two differ- ent large-scale ad-hoc retrieval datasets, we demon- strate that the concept of reciprocal nearest neigh- bors can indeed enhance the ranking context in computationally efficient way, both when reranking candidates inference time, as well as when ap- plied for evidence-bai label smoothing intended for training.
Addressing the problem of sparse annotation, several works have utilized the relevance estimates from supervised (e.g. Hofstätter et al., 2021; Qu et al., 2021; Ren et al., 2021b) or unsupervised (e.g. lexical: Dehghani et al., 2017; Haddad and Ghosh, 2019) retrieval methods or other dataset-specific heuristics (c.g. bibliography citations: Moro and Valgimigli, 2021) to derive soft labels for docu- ments used to train a model, e.g., in a teacher- student distillation scheme. In this work, we in- stead shift the perspective from assigning labels based on similarity with respect to the query, to sim- ilarity with respect to the ground-truth document(s), but within a query-specific ranking context. We fur- thermore leverage the concept of reciprocal nearest neighbors, introduced as a reranking method for image re-identification (Qin al., 2011; Zhong et al., 2017), to improve the similarity estimate.
2 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 pro- posed local relevance score regularization (Diaz, 2007), 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 to- gether 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 (Jardine and van Rijsbergen, 1971).
False negatives have been identified as a sig- nificant challenge by prior work, which has em- ployed powerful but computationally expensive cross-encoders (Nogueira and Cho, 2020) to dis- card documents that receive high similarity score to the query and are thus likely relevant from the pool of hard negatives (Qu et al., 2021; Ren et al., 2021b). However, discarding top-ranking hard neg- atives also discards potentially useful information for training.
Zerveas et al., 2022 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 query- specific ranking context that benefits the assess- ment of relevance of each individual candidate doc-
Recently, Zhou et al. (2022) tackled the problem of false negatives through selective sampling of negatives around the rank of the ground-truth doc- ument, 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 and in the fact that information again discarded from the context, as only a small number of nega- tives is sampled around the positive. Additionally, a query latency of up to 650 ms is added during training.
8" (9 A s(g, + 8) (1)
which we found to perform better both for rerank- ing (as in Zhong et al., 2017), as well as for label smoothing.
Importantly, unlike prior work (Qin et al., 2011: Zhong et al., 2017), which considered the entire gallery (collection) of images as a reranking con- text for each probe, we only use as a context a limited number of candidates previously retrieved for each query. This is done both for computational tractability, as well as to constrain the context to be query-specific when computing the similarity of documents to the ground truth; documents otherwise be similar to each other with respect many different topies unrelated the query. We empirically validate this choice in Section 5.1.
Ren et al. (2021a) leverage the similarity of can- didate documents to the ground truth document (positive), but a different way and differ- ent 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 single positive and the query compared to the similarity score it assigns to pairs of this positive with all other can- didates. Thus, 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.
3.2 Evidence-based label smoothing
Uniform label smoothing is a well-established tech- nique (Goodfellow et al., 2016) that is used to mit- igate the effects of label noise and improve score calibration, and was recently also employed for contrastive learning (Alayrac al., 2022). It in- volves removing a small proportion e E [0, 1] of the probability mass corresponding to the ground- truth class and uniformly redistributing it among the rest of the classes, thus converting, e.g., 1-hot vector = [1,0,.... E RR- to:
By contrast, our method jointly takes into ac- count all positives and other candidates in the rank- ing context, and through a KL-divergence loss term requires that the predicted relevance of the query with respect to all documents the ranking context has a similar probability distribution to the target distribution, i.e., the distribution of similarity be- tween all ground truth positives and all candidate documents in the context. False negatives are thus highly likely to receive non-zero probability in the target distribution, and the penalty when assign- ing non-zero relevance score to false negatives is lower.
y" = [L-,, 1...,
.... c/(N RN (2)
Nevertheless, naively distributing the probabil- ity mass uniformly among all candidates, as in Eq. (2), would result in true negatives predomi- nantly receiving portion of it, apart from the small number of false negatives*.
3 Methods
For this reason, we instead propose correcting the sparse annotation vectors by selectively dis- tributing relevance probability among negatives that are highly likely to be positive, or at least are ambiguous with respect to their relevance to the query. The proportion of probability mass each candidate shall receive depends on its degree of similarity to the annotated ground- document, which can be quantified by the Jaccard distance of Eq. (1 (I1), if we wish exclusively consider recip- rocal nearest neighbors, or the mixed geometric- Jaccard distance of Eq. (1), which allows any can- didate close to the ground truth to be considered.
3.1 Similarity metric based on Reciprocal Nearest Neighbors
Nearest Neighbors conventionally retrieved based on the geometric similarity (here, inner prod- uct) between embedding vectors of a query q and candidate document e; s(q, ca) = Ta,), with 2y - =m(g) and F,, = =m(c) embeddings obtained by a trained retrieval model m. We can additionally define the Jaccard similarity S. that measures the overlap between the sets of reciprocal neighbors of q and c₁. We provide detailed derivation of SJ in Appendix A.I.
Instead of the pure Jaceard similarity s,, we use a linear mixture with the geometric similarity s controlled by hyperparameter À E [0, 1]:
'Indeed, Qu et al. (2021) observe that among mined "hard negative" candidates, the pereentage of false negatives falls to 4% by rank 40.

---

Algorithm 1
Syvidnnce-based label smoothing
quires sorting the N candidates by their final simi- larity. The computational cost is thus O(N2) and O(N log N). respectively; if we are only interested in the top-k reranked candidates, the latter can be reduced to O(N log k-). We find (Sections 5.1, A.4) that a small subset of the full ranking context with size N, < N is generally sufficient when com- puting rNN- ANN-based similarities. For MS MARCO, Nr 60 and the delay per query when rerank- ing on single CPU and core (AMD EPYC 7532, 2400 MHz) is about 5 ms (Fig. 7).
Require:
Dense retrieval model m, set of queries Q, docu- ment collection C, set of all ground truth label documents per query (g)). vig E Q
1: Compute embedding vectors xt = m(x), Vg Q and Ze; (e.). Ve, E C.
2: for each query y do
3: Retrieve top-N Nearest Neighbors per query based (24, for all on geometric similarity: a(g, C.
4: for each candidate c,, = 1, ...... do
5: Compute relevance score r" mixed geometric
and reciprocal-NN Jaccard similarity &J with respect all ground-truth documents I:
Evidence-based label smoothing imposes no cost during training or inference; it only requires offline computation of rNN-similarities for each query context N, and sorting/top-k as above, followed by simple vectorized transformations, e.g. max- min normalization. Furthermore, all computations above can be trivially ('embarrassingly") paral- lelized in Multi-CPU/ccre setup.
r' a.) E(a)
8 (1,c),
lEC())
s (1. a) = X s(1, + (1 A) s)(l,c),
<<><1
6: Transform scores by applying normalization func- tion fu. boost factor and cut-off threshold Dema:
b- fa (r" (a)).))
if L());
(g,ce)
if > Thyas otherwise.
fn (r))
Experimental setting
7: end for
8: end for
Datasets. To evaluate the effectiveness of our methods, two large-scale, publicly avail- able ad-hoc retrieval collections: the MS MARCO Passage Retrieval dataset (Bajaj al., 2018), and TripClick, a health document retrieval dataset (Rek- absaz et al., 2021b). Each has distinct character- istics and represents one of the two realistic data settings practically available for training dense re- trieval models (see details in Appendix A.2, A.3).
9:
Fine-tune model m with target distribution: r(4)=
softmax (r' [q)). and loss function:
2 ((q)) DKL. (I(4) ((g)).
where 5(g) softmax (8' (g) is the model model-predicted
score distribution, with 7' a learnable temp. param.
Since the value range of similarity scores that each model outputs is effectively arbitrary, before applying a softmax to obtain a distribution over candidates, we (1) perform transformations (e.g.. max-min or std-based, see Appendix 1.5.1) and multiply the values of the original ground-truth truth documents by a factor > 1 to normalize the range and increase the contrast between the top and trailing candidates, and (2) we limit the num- ber of candidates that receive a probability above 0 to the top Max candidates in terms of their simi- larity to the ground-truit -ttut document(s). We found that these transformations primarily depend on the dataset rather than the model, and that training without limiting max leads to overly diffuse score distributions. In case more than one ground-truti documents exist for the same query, the similarity of each candidate is the mean similarity over all ground -oound-truth documents (see Algorithm 1).
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 ensure computational efficiency, as well as elim- inate the dependence on more powerful retrieval methods. Instead, we choose CODER (Zerveas et al., 2022), a fine-tuning framework that enhances the performance of dense retrievers used as "base models" through large ranking context of query- specific candidate documents and a list-wise loss: it serves as natural framework evaluate evidence- based label smoothing, because it allows us di- rectly utilize a large number of soft labels per query, while being very light-weight computationally. Following Zerveas et al. (2022), we select the
3.3 Computational efficiency
Computing rNN similarity involves computing pair- wise similarities among N + 1 ranking context elements (including the query), and reranking re-

---

MS MARCO devamall
MS MARCO dev
TREC DL 2019 2019
TREC DL 2020
Model
MRR mDCG
Recall
MRR
nDCG
Recall
MRR
nDCG
Recall
nDCG
Recall
RockerQAv2 (Ren et b021b)
0.388
ERNIE-Search et al., 2022)
0.401
AR2 (Zhing al., 2022)
0.395
AR2+ + SimANS (2hou et al., 2022)
0.409
TAS-B
0.344
0.408
0.619
0.344
0.407
0.618
0.875
0.659
0.222
0,832
0.620
0.302
R. TAS-B
0.347
0.411
0.625
0,346
0.410
0.623
0.886
0.664
0.226
0.828
0.627
0.311
CODER/TAS-B)
0.355
0.419
0.353
0.627
0.857
0.224
0.623
0.306
R. CODERITAS B)
0.357
0.421
0.637
0.354
0.418
0.631
0,853
0.679
0.231
0.860
0.634
0.317
CoCondenser
0.381
0.446
0
0.879
0.656
0.226
0.618
0.301
R. CoCondemerr
0.384
0.449
0.670
0,381
0.447
0.666
0,877
0,658
0.226
0.833
0.627
0.306
CODER/CoCuad)
0.382
0.362
0.895
0.228
0.639
0.314
R. CODER((CCood)
0.384
0.450
0.671
0.383
0.448
0.667
0,8995
0.664
0.230
0.844
0.641
0,316
Table 1: Recip. NN reranking, MS MARCO collection. Metrics cut-off @10. Bold: best in model class. As a reference, the top we include all SOTA dense retrieval models from literature that ourperform the methods we evaluated, noting that, unlike ours, they all rely heavily on cross-encoders for training (e.g. distillation, ranking, pseudolabeling etc). Blue: our contributions.
DCTR Head mDCG
RAW Head nDCG
5
Results and Discussion
Model
MRR
MRR
BM25'
0.276
0.224
0.199
0.128
5.1 Inference-time reranking with reciprocal nearest neighbors
BERT-Do (
0.530
0.243
BERT Cat (
0.595
0.294
RepBERT [abbrev: RB)
0.526
0,255
0.574
0.344
0.199
We first evaluate the effectiveness of reciprocal nearest neighbors at improving the similarity met- ric between queries and documents.
R. RepBERT
0.525
0.256
0.575
0.346
0.200
CODER(RB)
0.634
0.674
0.419
CODER(RB)
0.638
0.317
0.679
0.418
0.234
RB + CODER(RB)
0.637
0.318
0.679
0.421
0.235
Across all query sets in two important evalua- tion settings, MS MARCO (Table 1) and TripClick (Table 2), we observe that using a similarity based on reciprocal nearest neighbors can consistently improve ranking effectiveness for all tested models. The magnitude of improvement is generally small, but becomes substantial when measured on the TREC DL datasets (approx. +0.010 nDCG@ 10), where greater annotation depth and multi-level relevance labels potentially allow to better differen- tiate between methods.
RB + CODER(RB
0.641
0.319
0.681
0.422
0.236
Table 2: Recip, NN reranking. TripClick Test (cut-off @ 10). Bold: overall best, underline: best in model class. Row 1; from (Rekabsaz et al., 2021b), 2: (Hofstätter et al., 2022). Blue: our contributions.
following base models subjected to CODER fine- tuning:
1. RepBERT (Zhan et al., 2020), a BERT-based model with a typical dual encoder architecture which underpins all state-of-the-at dense retrieval methods, trained using triplet Max-Margin loss. 2. TAS-B (Hofstätter et al., 2021), one of the top- performing dense retrieval methods on the MS MARCO TREC-DL 2019, 2020 datasets, which has been optimized with respect their training process, involving a sophisticated selection of neg- ative documents through clustering of topically re- lated queries.
We furthermore observe that ranking effective- ness initially improves when increasing the size of the ranking context (i.c., the number of candi- dates considered for reranking), which is expected, because the probability to include remote ground- truth document in the context increases. However, as this size further increases, ranking effectiveness saturates, often peaking at context size of few tens of candidates (Figures 3, 4, 6, 9). We hypothe- size that this happens because, as we keep adding negatives in the context, the chance that they dis- rupt the reciprocal neighborhood relationship be- tween query and positive document(s) increases (see Figure 1).
3. CoCondenser (Gao and Callan, 2021), the state- of-the-art dense retrieval model, excluding those which make use of heavyweight cross-encoder (query-document term interaction) teacher models additional pseudo-labeled data samples; it re- lies on corpus-specific, sulf-supervised pre-training through a special architecture and contrastive loss component.
We therefore conclude that we may use rela- tively small number N of context candidates for computing reciprocal nearest neighbor similarities, which is convenient because computational com-

---

TREC DL 2019
2019
TREC DL 2020
Model
MRR
aDCG
MAP
Recall
MRR
RDCG
MAP
Recall
TAS-B
0.875
0.639
0.222
0.259
0.832
0.620
0.302
0.363
CODER(TAS-R)
0.857
0.668
0.224
0.270
0.844
0.623
0.306
0.361
CODERITAS B)+ uniform sum.
0.857
0.669
0.223
0.273
0.835
0.619
0.304
0.360
CODERITAS-BE goom. smooth labels
0,848
0.665
0.220
0.370
CODER(TAS-B) INN smaoth lahels
0.857
0.671
0.226
0.276
0.862
0.632
0.315
0.369
CODER(TAS-B) + mixed Ngegoom smooth Iah
0.889
0.675
0.227
0.277
0.842
0.637
0.318
0.376
CoCondemer
0.879
0.656
0.226
0.301
0.366
Conndena)))))eeet
0.895
0.655
0.228
0.269
0.844
0.639
0.314
0.384
CoDER(CoConleneer mixed rNNigeom. smooth lah.
0.884
0.661
0.232
0.278
0.856
0.646
0.316
0.383
Table Evaluation of label smoothing applied training CODER(TAS-B) on MS MARCO. Metries cut-off @ 10. Bold: best performance in each model class. Blue: contributions.
query (Figure 7). We expect the optimal context size to depend on the average rank that ground- truth documents tend to receive, and for models of similar ranking effectiveness, this would primarily be determined by the characteristics of the dataset. Indeed, we find that the hyperparameters in com- puting rNN-based similarity (e.g. k, X, т, sw). as well as the context size N, predominantly de- pend on the dataset, and to a much lesser extent on the dense retriever: hyperparameters optimized for CODER(TAS-B) worked very well for TAS- B, CoCondenser and CODER(CoCondensen on MS MARCO, but very poorly when transferred TripClick.
0.126
CODERITAS-B)
EB smoothing ing (rNN)
0.124 EB smooth ing (geom.)
Uniform smoothing
0.122
Distillation Ihparam, rNN)
Distillation (hparam, geam.)
0.120
REPBERT
0.118
0.116
0.114
0
50000
100000
150000
200000
0.3525
0.3500
0.3475
MRR320
0.3450
A more detailed description and discussion of reranking experiments is provided in Ap- pendix A.4.
0,3425
CODER(TAS-B)
EB smoothing (rNN)
0.3400
EB smoothing (gnom.)
Uniferm smoothing
0.3375
Distillation Ohparam. (NNI
0.3350
Distillation (hparam. geom.)) RepBERT
5.2 Evidence-base label smoothing
0.3325
In order to achieve the best possible results using evidence-basee label smoothing, one should ideally optimize the hyperparameters related rNN-based similarity for the specific task of training a retrieval model with recomputed soft labels. However, to avoid repeatedly computing soft labels for the train- ing set, we simply chose an rNN configuration that was optimized for reranking a large pool of candi- dates (N = 1000) in the MS MARCO collection ie.. the same one used in the previous section. Although this configuration may not be optimal for our specific task (e.g., small changes in score values might be sufficient for reranking candidates but ineffective as soft training labels), we expect that can still provide a reliable lower bound of optimal performance.
50000
100000
150000
200000
Step
Figure Evolution of performance of TAS-B (left- most point, step 0) on MS MARCO dev validation set, as the model is being fine-tuned through CODER. The red curve corresponds using evidence-basse based (EB) label smoothing computed with rNN-based similarity, whereas for the blue curve the smooth label distribution is computed using pure geometric similarity. EB label smoothing significantly reduces validation loss (com- puted with the original labels, top), indicating that the ground truth passages are receiving higher probability in the estimated relevance distribution, but the retrieval metric (bottom) fails to register an improvement due annotation sparsity (compare with Fig. 10, Appendix). Distillation leads to precipitous degradation perfor- mance.
Figure 2 shows how the ranking performance of the TAS-B base model (left-most point, step 0) on the validation set evolves throughout fine-tuning through CODER. The red curve corresponds to additionally using evidence-based label smooth-
plexity scales with O(N2). In MS MARCO, context of 60 candidates corresponds to peak effec- tiveness for CODER(TAS-P B) and introduces a CPU processing delay of only about 5 milliseconds per

---

ing computed with reciprocal NN-based similarity (rNN-related hyperparameters are the same as in Section 5.1), whereas for the blue curve the smooth label distribution is computed using pure geomet- ric similarity. We observe the following seem- ingly paradoxical phenomenon: compared to plain CODER training, label smoothing significantly re- duces the validation loss (computed with the orig- inal labels, top panel), indicating that the ground truth passages are now receiving proportionally higher scores in the estimated relevance distribu- tion, but the retrieval metric (bottom panel) does not register an improvement.
DCTR Head
RAW
Mode
MRR
aDCG
Recall
MRR
nDCG
Recall
RepBERT
0.525
0.255
0.342
0.574
0.344
0.199
CODERIRE)
0610
0,500
0.276
0.656
0.401
0.28
CODERIRE) hpprra.
0.608
0.500
0.277
0.649
0:401
0.229
CODERIRB)
0.611
0.305
0.280
0.661
0.234
Table 4: Evaluation of evidence- label smooth- ing (mixed rNN geom. similarity) on TripClick HEAD Test. Models were trained on TripClick HEAD U TORSO Train and validated on HEAD Val. Metrics cut-off @ 10. "hparam": model trained with same hyperparameters the one with label smoothing. Blue: our contributions.
(i.e., without any training) on TripClick Test and Val (Figures 7, 8, Appendix). We again observe that evidence-based label smoothing with an rNN- based metric improves performance compared plain CODER; however, we note that in this zero- shot setting, the best performing models were not in general the same as the best performing mod- els on TREC DL. The best ranking performance was achieved by CODER(TAS-BB B) using soft labels from pure rNN-based Jaccard similarity.
In fact, this phenomenon may be fully explained through the presence of false negatives: through the smooth target label distribution, the model learns to assign high relevance scores to a larger num- ber of documents (diffuse distribution). Therefore, it likely places a proportionally higher relevance distribution weight to the ground truth document compared to plain CODER, essentially improving the relevance estimate for the ground truth, but at the same time it distributes relevance weight to a higher number of candidates, such that the ground truth ends up being ranked slightly lower (see Fig- ure 1 1)).
We thus find that in sparsely annotated datasets like MS MARCO, validation loss might be bet- ter predictor of model generalization than IR met- rics such MRR, and that evaluation datasets with higher annotation depth (such TREC DL or TripClick), potentially even in zero-shot set- ting, might better reflect the ranking effectiveness of models.
The crucial question therefore is, whether the candidates now receiving higher relevance score are actually relevant. Since the MS MARCO dev dataset almost always contains only single positive-labeled passage per query, it is fundamen- tally ill-suited to measure ranking effectiveness im- provements by training scheme that primarily promotes a diffuse relevance distribution over sev- eral candidates.
A critical difference of evidence-based label smoothing from distillation is that soft document labels are computed based on their similarity to the ground truth instead of the query. To demon- strate the importance of this change of perspec- tive, we show how CODER fine-tuning performs when using soft labels coming from geometric sim- ilarity with respect the query, as in distillation (Figure 2, purple curves): even when applying the same transformations to the scores as in the case of evidence-based label smoothing, the model's per- formance rapidly degrades instead of improving. This is expected, because distillation only works when a superior model is available; training cannot be bootstrapped from the scores of the model itself.
For this reason, we must rely datasets con- taining more judgements per query, such as the TREC DL 2019, 2020 datasets: Table 3 shows that evidence-basel label smoothing using a similarity based on reciprocal nearest neighbors can signifi- cantly improve the performance of each dense re- triever even beyond the benefit of the plain CODER fine-tuning framework. Furthermore, using an rNN- based Jaccard similarity as metric for computing the soft labels yields significantly better perfor- mance than using geometric similarity, and the best results are achieved when using a linear combina- tion of the two metries.
We also observe that, unlike evidence- la- bel smoothing, uniform label smoothing fails to noticeably improve performance compared plain CODER fine-tuning (Figure 2, Table 3), even when we ensure that the exact same probability weight as in the case of evidence- based smoothing is dis- tributed from the ground-trus positive(s) among
As TripClick also contains several (pseudo- relevance) labels per query, we additionally eval- uate the MS MARCO-trained models zero-shot

---

the of the candidates.
Acknowledgements
Finally, examine how EB label smoothing performs when training in an important alterna- tive setting, TripClick: a dataset with significantly more relevance labels per query, that come from pseudo-relevance feedback without human judge- ments. Unlike above, here we investigate the joint optimization of rNN-related parameters together with training-specifie parameters (e.g., learning rate and linear warm-up steps), instead of using the same rNN-related hyperparameters for label smoothing as for reranking. To allow this, we train on the union of the HEAD and TORSO training subsets (avg. 42 and 9 annotations per query, respectively), and omit the TAIL subset, which consists of large number of rare queries (each with only 3 annota- tions on average). We use HEAD Val as a validation set, and evaluate HEAD Test.
G. Zerveas would like to thank the Onassis Founda- tion for supporting this research. The contribution of N. Rekabsaz is supported by the State of Up- per Austria and the Federal Ministry of Education, Science, and Research, through grant LIT-2021- YOU-215.
Limitations
We believe that principle, the methods we pro- pose are applicable to any dual-encoder dense re- triever: computing the similarity metric based on reciprocal nearest neighbors only requires access to the encoder extracting the document and query embeddings.
However, we note that the reason we were able to compute the soft labels for evidence-based la- bel smoothing completely offline was that we uti- lized CODER as fine-tuning framework: CODER only fine-tunes the query encoder, using fixed doc- ument representations. Using evidence- bel smoothing in training method with Icarnable document embeddings means that the rNN-based similarity has be computed dynamically at each training step (or periodically every few training steps), because their mutual distaaies/simillartties will change during training, albeit slowly. Simi- larly, every time candidates/negatives are retrieved dynamically (periodically, as in Xiong et al., 2020, or at each step, as in Zhan et al., 2021) the rNN- based similarity has to be recomputed among this set. Nevertheless, as discuss in the paper, we only need use a context of tens or at most a couple of hundred candidates in order to compute the rNN-based similarity most effectively. Even these cases, this would therefore introduce at most up to a hundred milliseconds of training delay per batch, while inference would remain unaffected.
Table 4 and Figure 10 show that training with mixed geometricc/NNN-aatee based smooth labels signif- icantly improves performance also in this dataset setting compared to plain CODER training (+0.010 nDCG@ 10). To ensure that any improvement can- not be attributed to better hyperparameters found during the joint optimization described above, we also apply the same hyperparameters to plain CODER training (denoted "hyperparam." in the table). We observe similar improvements on TORSO Test and TORSO Val (Appendix Table 9).
la-
6 Conclusion
We propose evidence-based label smoothing to ad- dress 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 rele- vance probabilities to candidates most similar to the ground truth. To estimate similarity we leverage reciprocal nearest neighbors, which allows consid- ering 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 demon- strate that our method can effectively improve rank- ing, while being computationally efficient and fore- going the use of resource-heavy cross-encoders. Fi- nally, we find that evaluating on sparsely annotated datasets like MS MARCO dev may systematically underestimate models with less sharp (i.c. more diffuse) relevance score distributions.
Ethics Statement
By being computationally efficient and foregoing the use of resource-heavy cross-encoders in its pipeline, our method allows top- por-perfonnnng dense retrieval models to be fine-tuned on MS MARCO within 7 hours lieve that it is well-aligned with the goal of training models in an environmentally sustainable way, the importance of which has been recently acknowl- edged by the scientific community Information Re- trieval and more broadly (Scells et al., 2022).
single GPU. We therefore be-

---

On the other hand, the transformer-based Infor- mation Retrieval models examined in our study may intrinsically exhibit societal biases and stereo- types. As prior research has discussed (Gezici et al., 2021; Rekabsaz et al., 2021a; Rekabsaz. and Schedl, 2020; Bigdeli et al., 2022; Krieg et al., 2022; Bigdeli et al., 2021; Fabris et al., 2020), these biases stem from the latent biases acquired by transformer-based language models throughout their pre-training, as well as the fine-tuning process on IR collections. Consequently, the practical use of these models might result in prejudiced treat- ment towards various social groups (c.g., as mani- fested in their representation or ranking in retrieval result lists). We therefore firmly encourage mind- ful and accountable application of these models.
Amin Bigdeli, Negar Arabzadeh. Morteza Zihayat, and Ebrahim Bagheri. 2021. Exploring gender biases in information retrieval relevance judgement datasets. In Advances in Information Retrieval, pages 216-224, Cham. Springer International Publishing.
Zhe Cao. Tao Qin, Tie- Yan Liu, Ming-Feng Tsai, and Hang Li. 2007. Learning to rank: from pairwise approach listwise approach. In Proceedings of the 24th international conference on Machine learning, ICML *07, pages 129-136. New York, NY, USA. Association for Computing Machinery.
Olivier Chapelle and Yi Chang. 2010. Yahoo! Learning to Rank Challenge Overview. In Proceedings of the 2010 International Conference on Yahoo! Learning to Rank Challenge Volume 14, YLRC 10. pages 1-24, Haifa, Israel. JMLR.org.
Domenico Dato, Claudio Lucchese, Franco Maria Nar- dini, Salvatore Orlando, Raffaele Perego, Nicola Tonellotto, and Rossano Venturini. 2016. Fast Rank- ing with Additive Ensembles of Oblivious and Non- Oblivious Regression Trees. ACM Transactions on Information Systems, 35(2):15:-11::31
References
Qingyao Ai, Keping Bi, Jiafeng Guo, and W. Bruce Croft. 2018. Learning a Deep Listwise Context Model for Ranking Refinement. In The 41 Interna- tional ACM SIGIR Conference on Research & Devel- opment in Information Retrieval, SIGIR 18, pages 135-144, New York, NY, USA. Association for Com- puting Machinery.
Mostafa Dehghani, Hamed Zamani, Aliaksei Severyn, Jaap Kamps, and W. Bruce Croft. 2017. Neural Rank- ing Models with Weak Supervision. In Proceedings of the 40th International ACM SIGIR Conference Research and Development Information Retrieval, SIGIR 17, pages 65-74, New York, NY, USA. Asso- ciation for Computing Machinery.
Qingyao Ai, Xuanhui Wang, Sehastian Bruch, Na- dav Golbandi, Michael Bendersky, and Mare Na- jork. 2019. Learning Groupwise Multivariate Scoring Functions Using Deep Neural Networks. arXiv:1811.04415 [cs). ArXiv: 1811.04415.
Fernando Diaz. 2007. Regularizing query-based re- trieval scores. Information Retrieval, 10(6):531-55)5
Jean- Cann-Baptiste Alayrac, Jeff Donahue, Pauline Luc, An- toine Miech, lain Barr, Yana Hasson. Karel Lenc, Arthur Mensch, Katie Millican, Malcolm Reynolds, Roman Ring. Eliza Rutherford, Serkan Cabi, Tengda Han, Zhitao Gong, Sina Samangooei, Marianne Monteiro, Jacob Menick, Sebastian Borgeaud, An- drew Brock, Aida Nematzadeh, Sahand Sharifzadeh, Mikolaj Binkowski, Ricardo Barreira, Oriol Vinyals, Andrew Zisserman, and Karen Simonyan. 2022. Flamingo: a Visual Language Model for Few-Shot Learning. ArXiv:2204.11 141992 [cs].
Alessandro Fabris, Alherto Purpura, Gianmaria Silvello, and Gian Antonio Susto. 2020. Gender stereotype reinforcement: Measuring the gender bias conveyed by ranking algorithms. Information Processing & Management.
Luyu Gao and Jamie Callan. 2021. Unsupervised cor- pus aware language model pre-training for dense pas- sage retrieval. ArXiv, abs/2 108.05440.
Gizem Gezici, Aldo Lipani, Yucel Saygin, and Emine Yilmaz, 2021. Evaluation metries for measuring bias in search engine results. Information Retrieval Jour- nal, 24(2):85-113.
Payal Bajaj. Daniel Campos, Nick Craswell, Li Deng. Jianfeng Gao, Xiaodong Liu, Rangan Majumder, An- drew McNamara, Bhaskar Mitra, Tri Nguyen, Mir Rosenberg, Xia Song, Alina Stoica. Saurabh Tiwary, and Tong Wang. 2018. MS MARCO: A Human Gen- erated MAchine Reading COmprehension Dataset. 1oXiv:6611.09600 [cs]. ArXiv:
Ian J. Goodfellow, Yoshua Bengio, and Aaron Courville. 2016. Deep Learning. MIT Press, Cambridge, MA, USA.
Dany Haddad and Joydeep Ghosh. 2019. Learning More From Less: Towards Strengthening Weak Su- pervision for Ad-Hoc Retrieval. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 19, pages 857-860, New York, NY, USA. As- sociation for Computing Machinery.
Amin Bigdeli, Negar Arabzadeh, Shirin Seyedsalchi, Morteza Zihayat, and Ebrahim Bagheri. 2022. liiht strategy for restraining gender biases in neural rankers. In Advances in Information Re- trieval, pages 47-55, Cham. Springer International Publishing.

---

Sebastian Hofstätter, Sophia Althammer. Mete Sertkan, and Allan Hanbury. 2022. Establishing Strong Baselines for TripClick Health Retrieval. arXiv:2201.00366 [es]. ArXiv: 2201.00365.
Navid Rekabsaz, Oleg Lesota, Markus Schedl, Jon Brassey, and Carsten Eickhoff. 2021b. TripClick: The Log Files of a Large Health Web Search Engine. In Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Infor- mation Retrieval, pages 2507-2513. Association for Computing Machinery, New York, NY, USA.
Sehastian Hofstätter, Sheng-Chieh Lin, Jheng-Hong Yang, Jimmy J. Lin, and A. Hanbury. 2021. Effi ciently Teaching an Effective Dense Retriever with Balanced Topic Aware Sampling. SIGIR.
Navid Rekabsaz and Markus Schedl. 2020. Do neural ranking models intensify gender bias? In Proceed- ings of the 43rd International ACM SIGIR Confer- ence on Research and Development in Information Retrieval, pages 2065-2068.
N. Jardine and C. J. van Rijsbergen. 1971. The use of hierarchic clustering in information retrieval. Infor- mation Storage and Retrieval, 7(59:217-240.
Klara Krieg, Emilia Parada- Cabaleiro, Markus Schedl, and Navid Rekabsaz. 2022. Do perceived gender bi- ases in retrieval results affect relevance judgements? In Proceedings of the European Conference on In- formation Retrieval, Workshop on Algorithmic Bias in Search and Recommendation (ECIR-BIAS 2022), pages 104-116, Cham. Springer.
Ruiyang Ren, Shangwen Lv. Yingqi Qu, Jing Liu, Wayne Xin Zhao, QiaoQiao She, Hua Wu, Haifeng Wang, and Ji-Rong Wen, 202 PAIR: Leveraging Passage-Centric Similarity Relation for Improving Dense Passage Retrieval. Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, pages 2173-2188 ArXiv: 2108.06021
Yuxiang Lu, Yiding Liu, Jiaxiang Liu, Yunsheng Shi, Zhengjie Huang, Shikun Feng Yu Sun, Hao Tian, Hua Wu, Shuaiqiang Wang, Dawei Yin, and Haifeng Wang. 2022. Search: Bridging Cross-Encoder with Dual-Encoder via Self On- fly-fly Distillation for Dense Passage Retrieval. ArXiv:2205.099 1900000.9133310 [cs].
Ruiyang Ren, Yingqi Qu, Jing Liu, Wayne Xin Zhao, QiaoQiao She, Hua Wu, Haifeng Wang. and Ji-Rong Wen. 2021b. RocketQAv2: A Joint Training Method for Dense Passage Retrieval and Passage Re-ranking. In Proceedings of the 2021 Conference on Empiri- cal Methods in Natural Language Processing, pages 2825-2835, Online and Punta Cana, Dominican Re- public. Association for Computational Linguistics.
Gianluca Moro and Lorenzo Valgimigli. 2021. Effi- cient Supervid Metric Information Retrieval: A Bibliography Based Method Applied to COVID Literature. Sensors, (19)))6433. Number: 19 Pub- lisher: Multidisciplinary Digital Publishing Institute.
Keshav Santhanam, Omar Khattab, Jon Saad-Falcon. Christopher Potts, and Matei Zaharia. 2021. Col- BERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction. ArX14:2112.01488 [cs].
Rodrigo Nogueira and Kyunghyun Cho. 2020. Pas- sage Re-ranking with BERT. 1eXiv:9901004083 [cs].
ArXiv: 1901.04085.
Harrisen Scells, Shengyao Zhuang, and Guido Zuccon. 2022. Reduce, reuse, recycle: Green information retrieval research. In Proceedings of the 45th Inter- national ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '22, page 2825-2837, New York, NY, USA. Association for Computing Machinery.
Danfeng Qin, Stephan Gammeter, Lukas Bossard, Till Quack, and Luc van Gool. 2011. Hello neighbor: Accurate object retrieval with k-reciprocal nearest neighbors. In CVPR 2011, pages 777-784. ISSN: 1063-6919.
Tao Qin. Yin Liu, Jun Xu, and Hang Li. 2010. LETOR: A benchmark collection for research on learning to rank for information retrieval. Informa- tion Retrieval, 3444333463374
Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang. Jialin Liu, Paul Bennett, Junaid Ahmed, and Arnold Overwijk. 2020. Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Re- trieval. arXiv22007.00808 [cs]. ArXiv: 2007.00808
Yingqi Qu, Yuchen Ding. Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. 2021. RocketQA: An optimized train- ing approach to dense passage retrieval for open- domain question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Hu- man Language Technologies. pages 5835-5847, On- line. Association for Computational Linguistics.
George Zerveas, Navid Rekabsaz, Daniel Cohen, and Carsten Eickhoff. 2022. CODER: An efficient frame- work for improving retrieval through COntextual document embedding reranking. In Proceedings of the 2022 Conference on Empirical Methods in Natu- ral Language Processing, pages 10626-1000 1064,, Abu Dhabi, United Arab Emirates. Association for Com- putational Linguistics.
Navid Rekabsaz, Simone Kopeinik, and Markus Schedl. 2021a. Societal biases in retrieved contents: Mea- surement framework and adversarial mitigation for bert rankers. In Proceedings of the 44th International ACM SIGIR Conference on Research and Develop- ment in Information Retrieval.
Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Jiafeng Guo, Min Zhang, and Shaoping Ma. 2021. Optimizing Dense Retrieval Model Training with Hard Negatives. Proceedings of the 44th International ACM SIGIR

---

Conference on Research and Development Infor- mation Retrieval, pages 1503-1512, Virtual Event Canada. ACM.
Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Min Zhang, and Shaoping Ma. 2020. RepBERT: Contextu- alized Text Embeddings for First-Stage Retrieval. arXiv:2006. 15498 [cs]. ArXiv: 15498.
Hang Zhang, Yeyun Gong, Yelong Shen, Jiancheng Lv, Nan Duan, and Weizhu Chen. 2022. Adversarial Sttriever-Ranke for dense text retrieval. In Inter- national Conference Learning Representations (ICLR).
Zhun Zhong, Liang Zheng. Donglin Cao, and Shaozi Li. 2017. Re-ranking Person Re-identification with Reciprocal Encoding. In 2017 IEEE Conference Computer Vision and Pattern Recognition (CVPR),
pages 3652-3661, ISSN: 1063-6919.
Kun Zhou, Yeyun Gong, Xiao Liu, Wayne Xin Zhao, Yelong Shen, Anlei Dong, Jingwen Lu, Rangan Ma- jumder, Ji-rong Wen, and Nan Duan. 2022. SimANS: Simple ambiguous negatives sampling for dense text retrieval. In Proceedings the 2022 Conference Empirical Methods Natural Language Processing: Industry Track, pages 548-559, Abu Dhabi, UAE, Association for Computational Linguistics.

---

A Appendix
Effectively, we examine the set of rk-nearest recip- rocal neighbors of each reciprocal neighbor of g (where 7 E [0, 1] is a real parameter), and provided that it already has a substantial overlap with the original set of reciprocal neighbors of q, add it to the extended set. The underlying assumption is that if a document is closely related a of doc- uments that are closely related the query, then most likely itself related to the query, even if there no direct connection in terms of geomet- ric proximity. Thus, one can improve recall at the possible expense of precision.
A.1 Jaccard similarity based on Reciprocal Nearest Neighbors
Let C. be collection of documents, including the query used for search, and (N( k) denote the set of k-nearest neighbors of probe q E C be- sides the query. 4 here can also a document or any other element that can be embedded in the common representation space. If d(g, ci) = (X X C E C is metric (distance) in the vector space within which the embeddings of the query Xq and documents x; reside, can formally write:
Although using this new set of neighbors the new set of candidates and sorting them by their distance d can form the basis of a retrieval method, Zhong et al. (2017) additionally proceed to define a new distance that takes into account this set, which is used alongside d. Specifically, they use the Jac- card distance between the (extended) reciprocal neighbor sets of query q and documents cú:
NN k) = {c dg (X,,, x,) S (Xex Xy); ViEN: i & (C]),
(3)
where |-| denotes the cardinality of set, and doc- ument c₁. is the k-nearest neighbor of the query based on d, i.e., the k-th element in the list of all documents in C sorted by distance d from the query in ascending orders. Naturally, [NN(q, k)]l = k. The set of k-reciprocal nearest neighbors can then be defined as:
ds(g,c)) = 1 (R k)] k) [q]
(6)
This distance quantifies similarity between two el- ements (here, g and Q4) as measure of overlap between sets of neighbors robustly related to each of them.
k) {c ////cc NN( NN(C, k)},
(4) i.e., to be considered a k-reciprocal neighbor, a doc- ument must be included in the k-nearest neighbors of the query, but at the same time the query must also be included in the k-nearest neighbors of the same document. This stricter condition results in stronger similarity relationship than simple nearest neighbors, and [R(q, k)] < k.
To reduce the computational complexity of com- puting the Jaccard distance, which relies the time-consuming, CPU-bound operations of finding the intersection and union of sets, one may instead carry out the computation with algebraic opera- tions, by defining for cach element g E sparse vectors of dimensionality |C). where non-zero di- mensions denote graph connectivity to other doc- uments. Instead of using binary vectors, one may assign to each neighbor e, weight that depends its geometric distance to the probe q. Thus, follow- ing Zhong al. (2017), we define the elements of reciprocal connectivity vectors v' E |C] as follows:
Since using the above definition as-is can be overly restrictive, prior work has proposed upplying it iteratively in order to construct an extended set of highly related documents to the query that would have otherwise been excluded. Thus, Zhong al. (2017) define the extended
Rt = R(g,k) R(Cr, Tk),
if E (2 4. ={ -{ fo (d(a,
s.t. (R(g,)) n R(G,, rk) > R(G,, (5)
(7)
3
0
otherwise
Ye, R(g,
While Zhong al. (2017) exclusively use fu) exp( (-p), one one can use any monotonically de- creasing function, and we found that fw( = - in fact performs better in our experiments.
'Ween some measure of similarity & is used instead of a distance d. the relationship cquivalently becomes: s(x,,, x,) 2 s(x,,, x,), and the k-nearest neighbors are the first le documents sorted by in descending order.

---

Finally, instead of directly using the sparse vec- tors above, which would yield discretized similar- ity metric, we perform a local expansion, mixing each one of them (including the query) with its kexp neighboring vectors (again including the query, if among the neighbors):
For validation of the trained models we use a subset of 10k samples from "MS MARCO dev". which a set containing about 56k labeled queries. and refer to it as "MS MARCO dev 10k". As a test set we use a different, officially designated sub- set of "MS MARCO dev", originally called "MS MARCO dev.small", which contains 6980 queries. Often, in literature and leaderboards it is mislead- ingly referred to "MS MARCO dev".
Vec
Veg E NN(C
keepp j=1
Because of the very limited annotation depth (sparsity) in the above evaluation sets, we also eval- uate on the TREC Deep Learning track 2019 and 2020 test sets, each containing 43 and 54 queries respectively. labeled to an average "depth" of more than 210 document judgements per query, and us- ing 4 levels of relevance: "Not Relevant" (0), "Re- lated" (1), "Highly Relevant" (2) and "Perfect" (3). According to the official (strict) interpretation of relevance labels a level of 1 should not be consid- ered relevant and thus be treated just like a level of O, while the lenient interpretation considers pas- sages of level 1 relevant when calculating metrics.
is possible to use the clement-wise min and max operators on the expanded sparse vectors from Eq. (8)) to compute the number of candidates in the intersection and union sets of Eq. (6) respectively as:
Σ min(v V..) (9)
(q) Σ max Vog);
(10)
and thus the Jaccard distance in Eq. (6) can be written as:
A.2.2 TripClick
d) =1 =1- Σ I min( )er.e) 1
TripClick is recently introduced health IR dataset (Rekabsaz et al., 2021b) based on click logs that refer to about 1.5M MEDLINE articles. The approx. 700k unique queries in its training set are split into 3 subsets, HEAD, TORSO and TAIL, based on their frequency of occurrence: queries in TAIL are asked only once or a couple of times, while queries in HEAD have been asked tens hundreds of times. As result, each query in HEAD, TORSO and TAIL on average ends up with 41.9, 9.1 and 2.8 pseudo-relevance labels, using a click-through model (RAW) where every clicked document is considered relevant. The dataset also includes alternative relevance labels using the Doc- ument Click Thrcuhh Rate (DCTR), on 4 distinct levels (the latter follow the same definitions the TREC Deep Learning evaluation sets). We note that, although the number of labels per query is much higher than MS MARCO, unlike the lat- ter, these labels have not been verified by human judges.
(11)
Σ 1== max(Pq.o Neary)
Finally, we note that instead of the pure Jaceard distance d,y we use as the final distance d' linear mixing between the geometric distance and d with hyperparameter X E [0, 1]:
d' c)) Xd(g,e) + (1- ci), (12)
which we found to perform better both for rerank-
ing (as in Zhong et al., 2017), as well as for label smoothing.
A.2 Data
A.2.1 MS MARCO and TREC Deep Learning Following the standard practice in related con- temporary literature, we use the MS MARCO dataset (Bajaj et al., 2018), which has been sourced from open-domain logs of the Bing search en- models. The
gine, for training and evaluating MS MARCO passage collection contains about 8.8 million passages and the training set contains about 503k queries labeled with one or (rarely) more rele- vant passages (1.06 passages per query, on average), on a single level of relevance.
For validation and evaluation of our models we use the officially designated validation and test set, respectively (3.5k queries each).
html

---

A.3 Evaluation
All training and evaluation experiments are pro- duced with the same seed for pseudo-random num- ber generators. We use mean reciprocal rank (MRR), normalized discounted cumulative gain (nDCG), mean average precision (MAP) and re- call evaluate the models TREC DL tracks, MS MARCO and TripClick, in line with past work (e.g. (Xiong al., 2020; Zhan al., 2021; Hofstätter et al., 2021; Rekabsaz et al., 2021 While relevance judgements are well-defined in MS MARCO and TripClick, for the TREC DL tracks there exist strict and lenient interpretations of the relevance scores of judged passages (see Sec- tion A.2) In this work, we use the official, striet interpretation. We calculate the metrics using the official TREC evaluation software.?
"trec,nist. bosst.govtreec_eva//iddeee html

---

A.4 Inference-time reranking with reciprocal nearest neighbors
novel finding. We hypothesize that it happens because the more negative candidates are added in the context, the higher the chance that they disrupt the reciprocal neighborhood relationship between query and positive document(s) (see Figure I).
Prior work on rNN reranking considered the en- tire gallery of images (collection C) as a reranking context for each probe, i.e. N = |C|. With [C] in the order of tens of millions, this is intractable for the task of web retrieval using transformer LMs, and a smaller context size must be used instead. To investigate the importance of the context size, we therefore initially fix the number of in-context candidates per query to large number within rea- sonable computational constraints (N = 1000) and optimize the hyperparameters of reciprocal nearest neighbors (e.g. k. Kexp, X, fww on the MS MARCO small subset.
We can therefore conclude that we may use a relatively small number N of context candidates for computing reciprocal nearest neighbors similar- ities, which is convenient because computational complexity scales with O(N3). For context of 60 candidates, CPU processing delay of only about 5 milliseconds per query is introduced (Figure 7). These results additionally indicate that the context size should best be treated as a rNN hyperparam- eter to be jointly optimized with the rest, which is reasonable, as it is expected to depend on the average rank that ground documents tend to receive.
We first rerank candidates initially ranked by a CODER-optimized TAS-B retriever, denoted as "CODER(TAS-B) To determine an appropriate size of reranking context, we first sort candidates by their original relevance score (geometric similarity) and then recompute query similarity scores with growing number of in-context candidates (selected the order of decreasing geometric similarity from the query), while measuring changes ranking effectiveness.
After optimizing rNN-related hyperparameters (including the context size) on MS MARCO dev. small for CODER(TAS-B), we evaluate rNN reranking the other evaluation sets (including its x8 larger superset MS MARCO dev) and present the results in Table 1. We observe that simi- larity based on reciprocal nearest neighbors can indeed improve ranking effectiveness compared to using purely geometric similarity. The improve- ment is more pronounced on the TREC DL datasets (+0.011 1 nDCG@ 10), where greater annotation depth and multi-level relevance labels potentially allow to better differentiate between methods.
Figure 3 shows that rNN-based reranking slightly improves effectiveness compared to rank- ing purely based on geometric similarity, with the peak improvement registered around a con- text size of 60 candidates. This behavior is consis- tent when evaluating rNN-based raranking using the same hyperparameterrs different query sets: MS MARCO dev (Fig. 4), which is an order of magnitude larger, and TREC DI. 2020 (Fig. 5) and TREC DL 2019 (Fig. 6), where the improvement is larger (possibly because can be measured more reliably due to the greater annotation depth). In all cases performance clearly saturates as the number of candidates grows (somewhat slower for TREC DL. 2019). The same behavior as described above is observed when reranking the original TAS-B model's results using the same hyperparameters chosen for the CODER-trained version, with the performance benefit being approximately twice as large (Fig. 8).
Additionally, we find that rankings from TAS- B whose embeddings relatively similar CODER(TAS-B) also improve, despite the fact that hyperparameters were chosen based on the CODER(TAS-B) BB) model (also see Figure 8).
The strongest dense retrieval models we eval- uate, CoCondenser and CODER(Cooondensee)) also show improved performance, again measured primarily on TREC DL: the former improves by +0.009 nDCG@ 10 on TREC DL 2020 and the lat- ter by 0.009 nDCG@ 10 on TREC DL. 2019. No- tably, reranking effectiivnness when using the exact same hyperparameters as for CODER(TAS-B) and TAS-B is only very slightly worse.
While it is expected that progressively increas- ing the context size will increase performance, as there is a greater chance to include the ground-truth passage(s) which may have been initially ranked lower (i.e. embedded farther from the query), the peak and subsequent degradation or saturation is
By contrast, when transferring hyperparameters selected for MS MARCO to reranking candidates on the TripClick dataset, we find that performance deteriorates with respect to geometric similarity. Therefore, we can conclude that rNN hyperparam- eters predominantly depend on the dataset, and to

---

Hyperparameter
TAS-B
CODER(TAS-B)
CoCondenser
CODER,(ooCondesse))
N;: context size
60
60
53
63
R: num. NN
21
21
21
19
Besp num. NN for expansion
3
3
5
8
trust factor
0
0
0,128
0.5
A: linear comb. coeff.
0.451
0.451
0,469
0.473
Table Hyperparameterss for reranking with Reciprocal Nearest Neighbors, MS MARCO.
Max: (60, 0.3563)
Recip, reranking
0.42050
Max: (60, 0.4205)
Recip, reranking
0.3562
geometric
geometric sim.
0.42025
0.3560
0.42000
0.3558
MAR@10
0.3556
nDCG@10
0.41975
0.41950
0.3554
0.3552
0.3550
0.41900
0.3550
0.3548
0.41875
0.4187
200
400
600
800
1000
200
400
600
800
1000
Number candidates
Number of candi dlttes
Figure 3: Performance of reciprocal nearest neighbors-based reranking CODER(TAS-B B) results on MS MARCO dev.small the number of candidates in the ranking context grows. Hyperparameters optimized for context of 1000 candidates. Performance is slightly improved compared to ranking exclusively based on geometric similarity and peaks at 60 in-context candidates.
Max: (60, 0.3540)
Recip, NN reranking
Max:
Recip, reranking geometric sim.
geometric
0.3540
0.4170
0.3538
MMRR900
hDCG@10
0.4168
0.3537
0.3536
0.4166
0.3535
0.4164
0.3534
0.3533
0.4162
200
400
600
800
1000
200
400
600
800
1000
Number of candidates
Number of candidates
Figure 4: Performance of reciprocal nearest neighbors-based reranking of CODER(TAS-BB B) results on MS MARCO dev, as the number of candidates in the ranking context grows. Hyperparameters the same as Fig, 3. Performance slightly improved compared ranking exclusively based on geometric similarity and peaks at 60 in-context candidates.

---

Recip, NN reranking geometric sim.
0.6310)
Recip, NN reranking geometric sim.
0.314
0.628
MAP@10
nDCG@10
0.626
0.308
0.624
0.6226
0.3057
0.306
600
800
Number of candidates
Number of candidates
Figure 5: Performance of reciprocal nearest neighbors based reranking of CODER(TAS B) results on TREC DL 2020, as the number candidates ranking context grows. Hyperparameters are the same as Fig. 3. Performance is improved compared ranking exclusively based geometric similarity and peaks 60 in-context candidates.
Recip, reranking
Max: (720. 0.2308)
Recip, reranking
Max: (720, 0.6770)
geometric sim.
geometric
0.228
0.674
Opt:
MAP@10
0.226
nDCG@
0.672
0.2240
Opt: (60, 0.6706)
0.224
0.670
0.222
0.668
0.220
200
400
600
800
1000
200
400
600
800
1000
Number of candidates
Number of candidates
Figure Performance of reciprocal nearest neighbors based reranking of CODER(TAS B) results on TREC DI. 2019, as the number of candidates in the ranking context grows. Hyperparameters are the same as in Fig. 3. Performance is improved compared to ranking exclusively based on geometric similarity but does not clearly saturate.

---

140
120
100
Time query
80
60
40
Opt: (60, 4.90)
20
200
400
600
800
1000
Number of candidates
Figure 7: Time delay per query (in milliseconds) when reranking using reciprocal nearest neighbors-base based similarity. as the number of candidates in the ranking context grows. Hyperparameters are the same as in Fig. 3. Processing time scales according to ( Processor (1 CPU, core): AMD EPYC 7532 32- 2--ore Processor, 2400 MHz.
0.34575
Max: (240, 0.
Recip, NN rerank
0.4090
Max: (240,
Recip. NN rerank
geometric
Oct: (60, 0.h988)
geometric
0.34550
0,4085
0.34525
0.34500
MRRA@00
IDCO@110
0.4080
0.34475
0.34450
0.4075
0.34425
0.4070
0.34400
0.3438
0.4066
0.34375
200
400
600
800
1000
200
400
600
800
1000
Number of candidates
Number of candidates
Figure 8: Performance of reciprocal nearest neighbors-based reranking of TAS-B results on MS MARCO dev, as the number of candidates in the ranking context grows. Hyperparameters the same as in Fig. 3. Performance is improved compared to ranking exclusively based on geometric similarity and peaks at approx. 60 in-context candidates.

---

Max: (120. 0.6511---
recancing
goometric
6,6810
0.0008
0.6800
0.0192
200
600
000
500
1000
Number of candidates
Recip, NK rerancing
geametie sm
0A2266
0.424
0.4222
0-1277
Number candidatees
Figure 9: Performance of reciprocal nearest neighbors- based reranking of CODER results on TripClick HEAD Test, number of candidates in the ranking context grows.
a much lesser extent on the dense retriever.
After optimizing hyperparameters on TripClick HEAD Val, we evaluate on HEAD Test, using both RAW (binary) as well as DCTR (multi-level) rele- vance labels; we present the results in Table 2. Also for this dataset, which differs substantially in char- acteristies from MS MARCO, again observe that using reciprocal nearest neighbors to compute the similarity metric can slightly improve ranking effectiveness for all examined retrieval methods. We also observe the same saturation behavior with respect to the ranking context size, i.c. the number of candidates considered when reranking (Fig. 9).

---

A.5 Svidence-based label smoothing
0.115
CODER(Rep8ERT)
0.68
CODER(ReP8ERT) (nyperparam.)
EB smoothing (geom.)
0.110
EB smoothing (rNIN)
0.66
RepBERT
0.105
MRR@10
0.64
Loss
0.62
0.100
0.60
CODER(RePBERT)
0.095
CODE R(RepBERT) (hyperparam.) smoathing (geom.)
0.58
smoothing (YNN) RepBERT
0.090
0.56
50000
100000
150000 200000 Step
250000
50000
100000 150000
200000 250000
Step
Figure 10: Evolution of performance of RepBERT (left-most point, step 0) on the TripClick HEAD Val validation set, as the model being fine-tuned through CODER on TripClick HEADUTORSO Train. The curve corresponds to additionally using evidence-based label smoothing computed with reciprocal NN-based similarity, whereas for the blue curve the smooth lahel distrihution is computed using pure geometric similarity. Only evidence-based smoothing with rNN similarity substantially improves performance compared to plain CODER(RpBERTT), despite "CODER(RepBERT (hyperparam.)" and "EB smoothing" with geometric similarity using the same training hyperparameters.
EB label smoothing hyperparam.
CODER(TAS-B) CODER(Co
b: boost factor
1.222
1.525
Rmax: softmax cut-off
32
fn: normalization func.
max-min
std-based
learning rate: peak value
1.73e-06
1.37e-06
learning rate: linear warm-up steps
9000
12000
Table 6: Hyperparameters for training with evidence-based label smoothing, MS MARCO. The hyperparameters related computing rNN-based similarity the in Table 5.

---

Originel predicted lbution
0.43
3.4%
0.4
23-
KL-div: 0.3133
MRR: 0.333
82-
Ground truth llabel) distribution
0.
Cand
Cand
Cand.3
Card.
Ct buth
Card.
00
Predicted distribution with label smoothing
221
0.20-
6.755
0123
MRR: 0.200
0.00
Cand
Car6.2
Cool
Cand 4
61tuth
Ca9d.5
6315
KL-div: 0,3002
032%
0and
Ca1d.2
cond.
Card.4
Cand.3
Figure 11: Because many more documents receive higher than zero relevance in the target distribution after label smoothing, by design promotes a diffuse predicted distribution (hottom). Thus, although the predicted relevance of the ground-truth positive document is significantly higher compared to when not using label smoothing (top), indicating model improvement, the document ends up ranking lower because of the dispersed relevance estimates, and thus the MRR metric decreases. By contrast, the KL-divergence (i.e. loss function) correctly captures the improvement in assessing the relevance of the ground-truth positive. We note that in sparsely annotated datasets like MS MARCO, the "1-hot" ground-trunt annotations (right) are very often incorrect among the top ranks, and of the candidates ranked more highly than the ground truth (e-g. Candidates 3 and 4 in the figure) may actually be relevant, which would render the MRR metric spurious; Qu al., 2021 estimate that about 70% of the top 5 candidates retrieved by oop-erforming dense retrieval model that are not labeled as positive are in fact relevant.
Test:
DCTR Head
RAW Head
Model
MRR 10
nDCG@10
Recall
MRR@
nDCG@10
Recall
TAS-B
0.278
0.139
0.130
0.339
0.188
0.113
CODER(TAS-B)
0,279
0.140
0.130
0,338
0.191
0.115
CODER(TAS-B)
0.285
0.143
0.134
0.344
0.195
0.116
+ geom. smooth labels
CODER/TAS-BI
0.288
0.144
0.134
0.347
0.195
0.116
+ rNN smooth labels
CODER(TAS-B)
0.284
0.142
0.132
0.342
0.192
0.115
+ mixed rNN/geom. smooth lab.
CoCondenser
0.242
0.114
0.105
0.293
0.157
0.092
CODER(CoCondenser)
0.251
0.117
0.107
0.306
0.161
0.093
CoDER(CoCondensse))
0.250
0.117
0.107
0.304
0.162
0.094
+ mixed rNN/geom. smooth lab.
Table 7: Performance of models trained MS MARCO but zeroshot-evaluated on TripClick Test. Bold: overall best, Underline: best in model class.

---

Val:
DCTR Head
RAW Head
Model
MRR@10
nDCG@10
Recall
MRR@ 10
nDCG@10
@ecall
TAS-B
0.299
0.145
0.136
0.355
0.200
0.118
CODER(TAS-B)
0.300
0.146
0.140
0.353
0.203
0.121
CODER(TAS-B)
0.297
0.147
0.140
0.355
0.204
0.121
geom. smooth lahels
CODER(TAS-B)
0.300
0.147
0.141
0.357
0.205
0.122
INN smooth labels
CODER(TAS-B)
0.299
0.147
0.141
0.355
0.204
0.122
mixed rNNggemm smooth lab.
CoCondenser
0.247
0.115
0.105
0.308
0.167
0.097
CODER(CaComdemeer)
0.254
0.120
0.111
0.314
0.173
0.101
CODER(CuCundenser)
0.254
0.118
0.109
0.311
0.169
0.098
mixed rNN/geom. smooth lab.
Table 8: Performance of models trained on MS MARCO zeroshot-evaluated on TripClick Val. Bold: overall best, Underline: best in model class.
Test RAW Torso
Val RAW Torso
Model
MRR@10 10
nDCG@ 10
Recall 10
MRR@ 10
nDCG@ 10
Recall 10
RepBERT
0.338
0.247
0.309
0.398
0.288
0.342
CODER(RepBERT)
0.390
0.276
0,330
0.426
0.310
0.354
CODER(RepBERT) hyperparam.
0.389
0.277
0.331
0.428
0.310
0.354
(eDER()))HERT)
0.391
0.282
0.340
0,421
0.312
0.367
mixed rNN/geom. smooth label.
Table 9: Label smoothing applied to CODER(RepBERT) trained TripClick HEAD U TORSO Train, validated
HEAD Val; evaluation on TORSO Test and Val.

---

A.5.1 Score normalization
standard contrastive learning, including when using a KL-diivrgence loss, as in CODER (Zerveas et al., 2022), there is a very stark difference between the probability of the handful of ground-truth documents and the zero probability of the negatives in the target (ground-truth) distribution.
In evidence-basee label smoothing, we using the continuous similarity scores of candidates with respect the ground-trutt positive document(s) as soft labels for training, which means that that there is a reduced contrast between the highest and smallest score values. Additionally, the output values of the model's s similarity estimate reside within an arbitrary value range, determined primarily by the model's weights, and for the same rank, there is large variance of values between queries (Fig. 12). This means that after passing through a softmax, which is highly non-linear, the target score distribution will be either concentrated or diffuse, depending on the range of score values for each particular query. Normalizing values into the same range will facilitate learning consistent relevance estimates, Furthermore, given a single query, wish that target scores rapidly decrease the rank increases (Fig. 13).
Score for each rank
Normaizzed score for each rank
0850
Median
0825
0.07
0.00
0.8
0775
0750
Score
0.
0725
0.6
0.700
05
0675
0.4
0850
Rank
Rank
Figure 12: Similarity scores per rank across large number of queries.
Score for each rank
Score after softmax for each rank
Narmakzed Iinpeerature
Nornalized
Impprraurr
06-
04
02-
0
200 400
600
300 1000
300 120
340
Bank
Rank
Figure 13: Similarity scores of the top 1000 candidates for single query, sorted in descending order. Since they are used training labels, to avoid very diffuse estimated score distributions, need to ensure that there is large contrast between the top and bottom candidates and that probability (i.e. values after the scores pass through softmax) abruptly decreases after the first few ranks. We achieve this through appropriate normalization here, max-min (blue) instead of dividing by max (orange).
Therefore, facilitate learning, we wish to ensure that (a) there large enough contrast between the first and last ranks, and (b) this true for all queries. We can achieve this by applying a normalizing function fn. such as max- max-min, on the vector s E IR of candidate scores for a single query:

---

s min(s) (s)
fn(()
(13)
max(s) min(s)
or the following, which is based on the standard deviation across N candidate scores for a single query:
(s()) min(s)
(14)
Σi 8: Eg )
where a
N


Reviews:
[{"review_id": "0TJ4T6hPF9", "reviewer": "Reviewer_LNyP", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful to the reviewer for their comments and suggestions, especially with respect to related work in IR before the advent of Dense Retrieval.\n\nWe entirely agree that a discussion of this work should be included, and funnily enough, in an earlier draft of our paper, we had a small section exactly on earlier Learning-to-Rank work demonstrating the importance of ranking context, including the Ai et al. 2018 paper. This was unfortunately cut due to aggressive downsizing to meet the 8 pages limit. Thankfully, the extra page available post-review will allow us to restore this section, as well as include the interesting Diaz 2007 paper, which, besides being a different method addressing the same phenomenon from a different angle, provides important additional background and justification for our work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "This paper innovatively utilizes the rNN method, essentially mining additional relationship information between queries and documents, to obtain more effective hard negative samples and improve training efficiency.\n\nThe paper addresses the efficiency of the proposed methods, which is a commendable attempt in academic research.", "reasons_to_reject": "I believe the method proposed in this paper, using rNN to improve the estimation of semantic similarity between query and document embeddings, is indeed novel. However, the challenges mentioned at the beginning of the paper, such as the sparsity of relevance annotations, have long been present in the field of Information Retrieval even before the advent of Dense Retrieval. There have been many similar discussions with similar ideas but different methods. I believe these works should also be cited and discussed, including:\n\nQingyao Ai, Keping Bi, Jiafeng Guo, and W. Bruce Croft. 2018. Learning a Deep Listwise Context Model for Ranking Refinement. In The 41st International ACM SIGIR Conference on Research & Development in Information Retrieval (SIGIR '18). Association for Computing Machinery, New York, NY, USA, 135–144. https://doi.org/10.1145/3209978.3209985\n\nDiaz F. Regularizing query-based retrieval scores[J]. Information Retrieval, 2007, 10: 531-562.", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper proposes an evidence-based label smoothing 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. Experiments demonstrate the effectiveness of the proposed methods.\n", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "6RWSyS4SFT", "reviewer": "Reviewer_BAUY", "summary": "", "questions": "", "limitations": "", "rating": 2, "confidence": 4, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments.\n\nAlthough we are not aware of the use of reciprocal NN in industry R&D (despite the relevant experience of some of our authorship team members in industry), we cannot exclude that the concept has been used in industry at some point. However, given that we have not been able to find any related references besides the two works on image re-identification cited in our paper, **we still believe that the academic retrieval community would benefit from dissemination of the idea.** We furthermore _quantify the expected performance benefit_ and _provide values for parameters found through optimization_, as well as an _analysis of the effect of key parameters_ such as the context size and the _potential for transferability of these parameters across datasets and models_. We believe that this investigation sets the basis for the use of rNN as a building block in academia and industry alike.\n\n\nMore importantly, however, besides simply applying the concept of rNN in a new domain, **the main contribution of this paper consists of devising a new method that allows to effectively leverage it** for improving retrieval performance. Our experiments show that simply using it as part of a similarity metric for post-processing reranking is not the optimal way, as performance improvements are smaller and an extra delay is introduced during inference time. Since this is the only reported use in literature, any related R&D work in industry would most likely follow that approach.\n\nInstead, we propose a completely new method for training retrieval models that utilizes similarity of candidate documents with respect to ground-truth documents  - _independent of rNN_ - to compute soft relevance labels. Using these computed labels within an appropriate list-wise loss allows us to mitigate the problem of false negatives when training dense retrieval models. It is within this new framework where the concept of rNN proves most valuable, and we provide all additional methodological techniques (e.g. normalization, score value boosting, hard candidate cut-off, etc.) that are required for it to work.\n\nRegarding the magnitude of performance improvements, we agree that it appears modest in absolute terms. However, as we discuss in the paper, due to its structural biases (biased selection of a single positive per query), **the MS MARCO dev dataset systematically underestimates the performance of methods that distribute relevance scores over multiple candidates** rather than concentrating scores on a couple candidates. When evaluated in a suitable setting, such as the TREC DL 2019, 2020 and TripClick datasets, our proposed method offers a _performance boost of about +0.010 nDCG@10, which is considered a significant improvement in IR literature_.\n\nImportantly, **this performance benefit comes “for free”**: there are no trade-offs, and given an existing model ready for deployment, one would only need to compute soft labels once (offline, fully paralllizable on CPUs), and then fine-tune the model for a few hours on a single GPU.\n\n\nWe thank the reviewer for their suggestions **regarding presentation**:\n \ngiven the additionally available space post-review, we will split Figure 1 into a sequence of subfigures.\nwe will explicitly define _ranking context_ early on in the paper. As ranking context we mean the set of candidate documents that are jointly taken into consideration when evaluated with respect to their similarity to the same query.\n\nLines 152-157: These lines correspond to our comment that “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”. By this we simply mean that when training a retrieval model, it is not guaranteed that there will always be an even more powerful model to use for pseudo-labeling or distillation. We consider this to be a modest and intuitive claim, but we can certainly improve our wording to facilitate clarity.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "The proposed similarity definition has marginal improvement on the relevance metrics (MRR, NDCG, etc.) of retrieved results.", "reasons_to_reject": "The use of reciprocal nearest neighbors may be common practice in research and development. Given the reported scale of improvement in this paper, I would consider it an expected result.", "questions_to_authors": "", "paper_topic_and_main_contributions": "This paper defines a similarity metric based on both inner product and reciprocal nearest neighbors or Jaccard similarity, and shows its effectiveness in inference-time reranking and offline label smoothing of training data.", "excitement": 2, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "The concept of ranking context is used throughout the paper but not formally defined.\n\nFigure 1 in its current form doesn't really help with the intuition in an easy way. It would be better to have multiple subfigures that show the difference between the rankings when (1) different similarity definitions are applied, and (2) new data points are added.\n\nLine 152-157: The claim here is obscure and seems to lack support in references."}}, {"review_id": "kvZ5i6RCqr", "reviewer": "Reviewer_GibY", "summary": "", "questions": "Can the authors provide more reasons why grouch-truths that are mostly single positive-labeled as in MS MARCO can be ill-suited?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their comments and suggestions, which we will incorporate into the revised paper.\n\nGiven the extra page available post-review, we will move definitions from the Appendix to the Methods section, and **we will include a discussion of contrastive learning in a dedicated section of the revised paper**, which we agree is important, as it is the leading training paradigm of dense retrieval methods.\n\nHere, we note the following: The list-wise setting of the CODER framework provides a natural setting for evaluating evidence-based label smoothing, as it jointly scores a large number of candidate documents for which we compute soft relevance labels. However, CODER itself is just a fine-tuning framework and our training starting point is always a model already trained to peak performance through contrastive learning (e.g. RepBERT, TAS-B or CoCondenser). Further training of these models through their original contrastive objectives (including a small set of hard negatives and numerous random documents) leads to deterioration of performance, as already demonstrated by the CODER paper (Zerveas et al, 2022); only a large enough set of pre-retrieved candidate documents within a list-wise loss leads to improved performance through further training/fine-tuning. In our work, we additionally incorporate soft labels when fine-tuning. Therefore, **as we start our training from a converged model trained through contrastive learning, in a sense we already have a reference point for comparison**, e.g., the original CoCondenser on TREC DL 2020 improves from 0.618 to 0.646 nDCG@10 through our method. \n\nNevertheless, an interesting question here is whether the benefits of evidence-based label smoothing can also be observed _independently_ of using CODER, i.e., _when applied directly to contrastive learning from scratch_, not when fine-tuning with a list-wise objective. We strongly believe so, because false negatives have been shown to be especially deleterious for contrastive learning (e.g.  Qu et al., 2021), and our label smoothing places a larger-than-zero target relevance on false negatives, which would reduce the penalty they incur within the contrastive loss function. Furthermore, the contrastive InfoNCE/Negative Log-Likelihood loss used in most methods when training dense retrievers is _even more susceptible_ to the effect of false negatives than the KL-divergence used in CODER (see discussion Appendix A.5 of Zerveas et al., 2022). Of course, dedicated experiments are required to conclusively demonstrate and quantify this effect.\n\n\n## Reviewer question: reasons why ground truths that are mostly single positive-labeled as in MS MARCO can be ill-suited\n\nDespite their importance for Information Retrieval research, the process in which large-scale datasets such as MS MARCO are compiled incorporates significant structural biases, many of which are largely inevitable. For every given query, we can naturally assume that there are several relevant documents on the Word Wide Web; yet, only a miniscule subset of those will survive in these datasets - in MS MARCO, almost always just a single one.\n\nFirst, data is gathered from click logs of a _deployed_ commercial search engine; for a given query, documents that have received the most clicks will be selected and referred to human judges for further confirmation. Thus, the users, and consequently judges, **will only see documents that are most likely to be ranked highly by the deployed search engine** based on its own idiosyncrasies (e.g. a lexical-based model was used by Bing when compiling MS MARCO).\n\nSecond, due to the extent of required human effort, each of the hundreds of thousands of queries is typically assigned to a **single human annotator** (with the exception of a miniscule subset, to assess labeling quality). Moreover, each human annotator can only afford to look at **only a handful of top-ranked documents/passages for a given query**, until they identify a document that appears relevant. Specifically, the authors of the MS MARCO paper note (Bajaj et al., 2016): _“As the editors were not required to annotate every passage that were retrieved for the question, this annotation should be considered as incomplete—i.e., there are likely passages in the collection that contain the answer to a question but have not been annotated”._ To create the MS MARCO passage collection and ranking task, which we use in our work, the MS MARCO dataset creators insert an additional bias in the pipeline: after selecting top-ranked documents, they use a separate system to extract the passages most likely to contain an answer, that are then submitted to the human judges. Thus, **for each query, a single human annotator examines at most a couple of passages, extracted by a single system from an even smaller number of documents, retrieved by a single retrieval model.**  It then comes as little surprise that when using a top-performing retrieval model for passage retrieval on MS MARCO, Qu et al. 2021 observe that about **70% of the top 5 candidates not labeled as positive are actually relevant** (i.e. false negatives).\n\nThe resulting sparse annotation may be sufficient to _train_ well-performing models; however, when _evaluating_ their ranking effectiveness, models that highly rank the same passage as the one incidentally selected in the dataset through the biased process above will be advantaged compared to models which highly rank passages that might be equally or more relevant, but were not selected in the annotation process. Therefore, **when evaluating on such datasets, models that most effectively learn to imitate the biases present in the selection process** (e.g. the strong lexical overlap heuristic of the Bing search engine pre-2016) **will be advantaged**.\n\nIn particular, since such datasets include only a single positive per query, **models which systematically distribute relevance over a larger number of candidates** (like ours do by design, due to label smoothing), **will be _systematically_ underestimated when computing performance metrics such as MRR and nDCG: this is because a larger number of positive but unlabeled documents will receive a high relevance score and will thus more likely displace the ground-truth annotated positive document.** For our models, this happens even when the gound-truth positive document receives a higher relevance score than it did prior to fine-tuning, evidenced by the lower validation loss (see Figure 10 in the Appendix of our paper, and Figure 2).\n\nConsequently, to properly evaluate such methods, one needs datasets with greater annotation depth. The TREC DL 2019, 2020 datasets:\n  1. include **for each query more than 210 passage judgements** on average,\n  2. **several** experienced human annotators examine the same queries,\n  3. judged **passages are retrieved directly from the collection** (not extracted from documents), and\n  4. are **retrieved by a variety of different retrieval systems**\n  5. **relevance ratings are multi-level**, in a scale of 0 (non-relevant) to 3 (perfectly relevant), instead of binary.\n\nThus, many of the biases of the MS MARCO annotation process are alleviated, with the trade-off that the number of judged queries is much smaller. For this reason, we further evaluate _models trained on MS MARCO_ on the out-of-domain TripClick dataset “zero-shot” (i.e. without additional training). The latter includes 7k evaluation queries annotated with tens of pseudo-relevance labels per query, both in a binary (RAW) and multilevel-level (DCTR) relevance scheme. Thus, _the very same models_ that do not register an improvement when evaluated on MS MARCO dev, show significant improvements on TREC DL 2019, 2020 (Table 3), as well as when zero-shot evaluated on TripClick (Tables 7, 8 in the Appendix). Of course, compared to zero-shot, performance is much better when training on TripClick and evaluating on TripClick (Table 9, Appendix). \n\nImportantly, because of the greater annotation depth of TripClick, the discrepancy between the validation MRR metric and the loss we observe for MS MARCO in Figure 10 (which we hypothesize is due to sparse annotation and false negatives), **is not present** in the corresponding Figure 11 (Appendix) when training on TripClick, where both MRR and loss improve substantially when training with our proposed method (evidence-based label smoothing based on rNN).\n\n\n### Supplementary comment on MS MARCO dev\n\nFinally, we note that we are not the first to observe puzzling performance behavior when evaluating on MS MARCO dev: in the paper _“MS MARCO Chameleons: Challenging the MS MARCO Leaderboard with Extremely Obstinate Queries”_, CIKM’21, Arabzadeh et al. observe that there are sets of “extremely obstinate queries” on which none of the state-of-the-art neural ranking methods they examined performs well. Furthermore, performance of the models on these sets is uncorrelated with their performance on the rest of the queries. The authors do not find **any special characteristics of these queries that distinguish them from other queries**, and observe that **query reformulation does not help**. While the authors seem to infer that there is something amiss with how state-of-the-art neural ranking methods interpret these queries, and that this set of “obstinate queries” should be therefore used as a special benchmark for ranking performance, we conjecture that the observed effect is explained well through flawed annotation of MS MARCO dev: the existence of a large number of false negatives (which is well documented in literature) means that models cannot highly rank the arbitrarily selected ground-truth positive among other (unlabeled) positives. The large inter-model agreement on which queries are “obstinate”, and the fact that query reformulation is not useful, are consistent with this hypothesis. In our own experiments with all models we considered (TAS-B, RepBERT, CoCondenser), when examining the ranked position of the ground-truth annotated document, we further observed that the ground-truth across all queries in MS MARCO very rarely ranks in middle or bottom ranks (lower than ~50). So it would appear that it is not as much a matter of the models misinterpreting queries (because then the ground-truth would have landed more often in middle and bottom ranks), as it is how low the ground-truth is displaced within the top ranks. Naturally, dedicated experimental work is necessary to verify this hypothesis.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "Various and detailed analysis results have shown the soundness of their methods.\n\nThe proposed methods are novel and practical.", "reasons_to_reject": "The authors could have compared with some contrastive learning loss functions, models, etc.", "questions_to_authors": "Can the authors provide more reasons why grouch-truths that are mostly single positive-labeled as in MS MARCO can be ill-suited?", "paper_topic_and_main_contributions": "The authors proposed an improved similarity metric based on reciprocal nearest neighbors, which can also be used independently to rerank candidates in post-processing. ", "excitement": 4, "reproducibility": 3, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Typos_Grammar_Style_and_Presentation_Improvements": "It could be nicer if the authors define concepts such as geometric similarity s and s_J directly in Section 3.1 instead of the Appendix. "}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces evidence-based label smoothing, a computationally efficient method that prevents assigning high relevance to false negatives by leveraging the similarity of candidate documents within the ranking context of a query to the annotated ground truth to compute soft relevance labels. Extensive experimentation on two large-scale ad hoc text retrieval datasets demonstrates that the method improves the ranking effectiveness of dense retrieval models. Overall a nice paper. Well well-written and well-supported by reproducible experimentation.
Decision: Accept-Main