Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval
Authors: Lee Xiong
Chenyan Xiong
Ye Li
Kwok-Fung Tang
Jialin Liu
Paul N. Bennett
Junaid Ahmed
Arnold Overwijk
Venue: ICLR 2021 Poster (2021)
Keywords: Dense Retrieval
Text Retrieval
Text Representation
Neural IR

Abstract: Conducting text retrieval in a learned dense representation space has many intriguing advantages. Yet dense retrieval (DR) often underperforms word-based sparse retrieval. In this paper, we first theoretically show the bottleneck of dense retrieval is the domination of uninformative negatives sampled in mini-batch training, which yield diminishing gradient norms, large gradient variances, and slow convergence. We then propose Approximate nearest neighbor Negative Contrastive Learning (ANCE), which selects hard training negatives globally from the entire corpus. Our experiments demonstrate the effectiveness of ANCE on web search, question answering, and in a commercial search engine, showing ANCE dot-product retrieval nearly matches the accuracy of BERT-based cascade IR pipeline. We also empirically validate our theory that negative sampling with ANCE better approximates the oracle importance sampling procedure and improves learning convergence.

Published as a conference paper at ICLR 2021
APPROXIMATE NEAREST NEIGHBOR NEGATIVE CON- TRASTIVE LEARNING FOR DENSE TEXT RETRIEVAL
Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul Bennett, Junaid Ahmed, Arnold Overwijk Microsoft Corporation.
lexion, chenyan. xiong, yelil, kwokfung. jialliu, paul, n. n...nnett, jahmed, arnold. overwi oeelld.overwikkkmm.cccoo jtemiikosmiiiiiee.e..eee com
ABSTRACT
Conducting text retrieval in learned dense representation space has many intrigu- ing advantages. Yet dense retrieval (DR) often underperforms word-based sparse retrieval. this paper, we first theoretically show the bottleneck of dense retrieval is the domination of uninformative negatives sampled in mini-batch training, which yield diminishing gradient norms, large gradient variances, and slow convergence. We then propose Approximate nearest neighbor Negative Contrastive Learning (ANCE), which selects hard training negatives globally from the entire corpus. Our experiments demonstrate the effectiveness of ANCE web search, question an- swering, and a commercial search engine, showing ANCE dot-product retrieval nearly matches the accuracy of BERT-based cascade IR pipeline. We also empiri- cally validate our theory that negative sampling with ANCE better approximates the oracle importance sampling procedure and improves learning convergence.
INTRODUCTION
Many language systems rely on text retrieval as their first step to find relevant information. For example, search ranking (Nogueira & Cho 2019), open domain question answering (OpenQA) (Chen ct al. 2017), and fact verification (Thorne et al. 2018) all first retrieve relevant documents for their later stage reranking, machine reading, and reasoning models. All these later-stage models enjoy the advancements of deep learning techniques (Rajpurkar et al. 2016 Wang et al.) 2019), while, the first stage retrieval still mainly relies on matching discrete bag-of-wordss e.g., BM25, which has become
the pain point of many systems (Nogueira & Cho. 2019 Luan et al. 2020 Zhao et al. 2020).
Dense Retrieval (DR) aims to overcome the sparse retrieval bottleneck by matching in a continuous representation space learned via neural networks (Lee et al.) 2019 Karpukhin et al. 2020 Luan al. 2020). has many desired properties: fully learnable representation, easy integration with pretraming, and efficiency support from approximate nearest neighbor (ANN) search (Johnson et al. 2017). These grant dense retrieval an intriguing potential to fundamentally overcome some intrinsic limitations of sparse retrieval, for example, vocabulary mismatch (Croft et al. 2009).
One challenge in dense retrieval is to construct proper negative instances when learning the represen- tation space (Karpukhin et al.) 2020). Unlike in reranking (Liu 2009) where the training and testing negatives are both irrelevant documents from previous retrieval stages, in first stage retrieval, DR models need distinguish all irrelevant ones corpus with millions or billions of documents. As illustrated in Fig. D these negatives are quite different from those retrieved by sparse models.
Recent research explored various ways to construct negative training instances for dense re- trieval KKrppkkhnn et al. 2020), c.g., using contrastive learning (Oord et al., 2018 He et al., 2020 Chen et al. (020aa) to select hard negatives in current or recent mini-batches. However, as observed in recent research (Karpukhin et al. 2020). the in-batch local negatives, though effective in learning word or visual representations, are not significantly better than retreveed negatives in representation learning for dense retrieval. In addition, the accuracy of dense retrieval models often underperform BM25, especially on documents (Gao et al. 2020b Luan et al. 2020).
"Iece and Chenyan contributed equally.

---

Published as a conference paper at ICLR 2021
In this paper, we first theoretically analyze the convergence of dense retrieval training with negative sampling. Us- ing the variance reduction framework (Alain et al. 2015: Katharopoulos & Heuret, 2018), we show that, under con- ditions commonly met in dense retrieval, local in-batch negatives lead to diminishing gradient norms, resulted in high stochastic gradient variances and slow training con- vergence the local negative sampling is the bottleneck of dense retrieval's 's effectiveness.
Query
Relevant
Neg
BM25 Neg
Rand Neg
Based on our analysis, we propose Approximate near- est neighbor Negative Contrastive Estimation (ANCE),
Figure T-SNE (Maaten & Hinton (2008) representations of query, relevant documents, negative training instances from BM25 (BM25 Neg) randomly sampled (Rand Neg), and testing nega- tives (DR Neg) in dense retrieval.
new contrastive representation learning mechanism for
dense retrieval. Instead of random or in-batch local neg- atives, ANCE constructs global negatives using the being- optimized DR model to retrieve from the entire corpus. This fundamentally aligns the distribution of negative ples in training and of irrelevant documents to separate in testing. From the variance reduction perspective, these ANCE negatives lift the upper bound of per instance gradient norm, reduce the variance of the stochastic gradient estimation, and lead to faster learning convergence.
We implement ANCE using an asynchronously updated ANN index of the corpus representation. Similar Guu et al. (2020), maintain Inferencer that parallelly computes the document encodings with a recent checkpoint from the being optimized DR model, and refresh the ANN index used for negative sampling once it finishes, to keep up with the model training. Our experiments demonstrate the advantage of ANCE in three text retrieval scenarios: standard web search (Craswell jtt al. 2020), OpenQA (Rajpurkar et al. 2016 Kwiatkowski et al.) 2019). and a commercial search engine 's retrieval system. We also empirically validate our theory that the gradient norms on ANCE sampled negatives are much bigger than local negatives, thus improving the convergence of dense retrieval models!
2 PRELIMINARIES
In this section, we discuss the preliminaries of dense retrieval and its representation learning.
Given a query q and a corpus C. the first stage retrieval is to find set of documents relevant to the query D+ = {d1..... di. dn from C' (DD+ < |CT), which then serve as input to later more complex models (Croft et al., 2009). Instead of using sparse term matches and inverted
Task Definition:
index, Dense Retrieval calculates the retrieval score f() using similarities in learned embedding
space (Lee et al. 2019
Luan et al. 2020 Karpukhin et al. 2020):
f(g. d) sim(g(g; 0), (dd
where g() is the representation model that encodes the query or document to dense embeddings. The encoder parameter provides the main capacity. The similarity function (sim() often simply casine or dot product to leverage efficient ANN retrieval (Johnson et al.) 2017: Guo et al. 2020).
BERT-Siamese Model: A standard instantiation of Eqn. T is to use the SERT-Siamese/two- tower/dual-encoder model (Lee et al. 2019; Karpukhin al. 2020 Luan et al. 2020):
f(g. d) BERT(g) BERT(d) MLP((CLSS,) MLP((CL'S).)
(2)
It encodes the query and document separately with BERT as the encoder 9(). using their last layer's [CLS] token representation, and applied dot product (-) on them. This enables offline pre- computing of the document encodings and efficient first-stage retrieval. In comparison, the BERT reranker (Nogueira al. 2019) applies BERT on the concatenation of each to-rerank query-document pair: BERT(g d). which has explicit access to term level interactions between query-document with transformer attentions, but is often infeasible in first stage retricval as enumerating all documents in the corpus for each query is too costly.
Our code and trained models available http://ake.mm//ancc
2

---

Published as a conference paper at ICLR 2021
Learning with Negative Sampling: The effectiveness of DR resides in learning a good representa- tion space that maps query and relevant documents together, while separating irrelevant ones. The learning of this representation often follows standard learning rank (Liu 2009): Given query 9,
set of its relevant document D
and irrelevant ones D7 find the best 1* that:
0 argming ΣΣ Σ d(flg.d) f,
(3)
d'EDD dDE;
The loss i() can be binary cross entropy (BCE), hinge loss, or negative log likelihood (NLL).
A unique challenge in dense retrieval, targeting first stage retrieval, is that the irrelevant documents separate are from the entire corpus (Dy CC CCAD D.)) This often leads to millions of negative
instances, which have to be sampled in training:
0" argming
Σ
Σ (((g, q ED d-ED-
Here we start to omit the subscript in Dg. All D and D are query dependent. A natural choice is to sample negatives Đー from top documents retrieved by BM25. However, they may bias the DR model to merely mimic sparse retrieval (Luan et al.) 2020). Another way is to sample negatives in local mini-batches, e.g., as in contrastive learning (Oord et al. 2018), however, these local negatives do not significantly outperform BM25 negatives (Karpukhin et al. 2020 Luan et al. 2020)
ANALYSES ON THE CONVERGENCE OF DENSE RETRIEVAL TRAINING
In this section, theoretically analyze the convergence of dense retrieval training. We first show the connections between learning convergence and gradient norms (Sec. (.1). then we discuss how non-informative negatives in dense retrieval yield less optimal convergence (Sec. 3.2..
3.1 ORACLE NEGATIVE SAMPLING ACCORDING TO PER-INSTANCE GRADIENT- NORM
Let = ((f(g, d+), f(q, d ) be the loss function on the training triple (g. d+ dd), PD- the negative sampling distribution for the given (q, (t), and pa- the sampling probability of negative instance d' a stochastic gradient decent (SGD) step with importance sampling (Alain et al. 2015) is:
0(11 0: Npa- Vo.l(dt.d")
(5)
with O, the parameter at (-th step, 0.+1 the one after, and N the total number of negatives. The scaling
factor Np,- ensures Eqn. is an unbiased estimator of the non-stochastic gradient on the full data.
Then we can characterize the converge rate of this SGD step the movement to the optimal d". Following derivations in variance reduction (Katharopoulos Fleuret 2018 Johnson Guestrin 2018), let Ia-
Np.- Vo d the weighted gradient, the convergence rate is:
EA'
||0, 12 Ep,- (10 |1++11 12)
(6)
= |102|12 - 20 0r - -Ep,- (1p,-(10) - 79d- 113) + 28-TEp,, (0, 19aa)
(7)
=-n"Ep, (119a-11 113) 20100 Ep, (ga-) 2n0 (ga-)
(8)
=2nEEr,- (ga-) (ff - 8*) "2²Er, (1lga- 112)
(9)
-2n/P,-- (ga T(e. 8*) -7 , (gx ( STEEp- (ga )- 11 Tr2 (ga ))-
(10)
This shows we can obtain better convergence rate by sampling from a distribution Pp that minimizes
the variance of the stochastic gradient estimator Er, [/- 112), or Tr(Vr,,- (g+-)) }) as the estimator
unbiased. The variance reflects how good the stochastic gradient from negative sampling represents the full gradient on all negatives-the latter is ideal but infeasible. Intuitively, we prefer the stochastic estimator to be stable and have smaller variances.
A well known result in importance sampling (Alain al. 2015 Johnson & Guestrin 2018) is that
there exists an optimal distribution that:
P4 = argmin, Tr(Vp,- (gs )) x Vo,, )12
(11)
3

---

Published as a conference paper at ICLR 2021
Index & Search
Index Search
Inferencing
Inferencer
ANCE
D
Negatives
Training
d
d+
d
dt*
d
Posilives
Trainer
Checkpoint R-1
Checkpoint
Checkpoint k+1
Figure 2: ANCE Asynchronous Training. The Trainer learns the representation using negatives from the ANN index. The Inferencer uses a recent checkpoint to update the representation documents in the corpus and, once finished, refreshes the ANN index with most up-to-date encodings.
To prove this, one apply Jensen's 's inequality the gradient variance and verify that Eqn. achieves the minimum. The detailed derivations can be find in Johnson & Guestrin (2018).
Eqn. shows that the convergence rate can be improved by sampling negatives proportional their per-instance gradient norms (though too expensive to calculate). Intuitively, an negative instance with larger gradient norm is likely reduce the non-stochastic training loss, thus should be sampled more frequently than those with diminishing gradients. The correlation of larger gradient norm and better training convergence is also observed in BERT fine-tuning (Mosbach al. 202T).
3.2 UNINFORMATIVE N--ATCCH NEGATIVES AND THEIR DIMINISHING GRADIENTS
Diminishing Gradients Uninformative Negatives: Though the close form of gradient norms often does not exist, Katharopoulos & Fleuret (2018) derives the following upper bound:
V Mdd d ) Lpl[V oz (dtt, d
(12)
where is the number of layers, p composed by pre-activation weights and gradients in interme- diate layers, and V/V Udd", d lll is the gradient on the last layer. The derivation of this upper bound is on multi-layer perception with any depths and any activation function that is Lipschitz continuous (Katharopoulos & Fleuret, 2018). On complicated neural networks, the intermediate layers are regulated by various normalization and this upper bound often holds empirically (Sec. 663)
In addition, for many loss functions, for example, BCE loss and pairwise hinge loss, that when the loss goes to zero the gradient norm the last layer also goes to zero: l(d dd)
verify
0 V 인b. ldd+ d I]l 0 (Katharopoulos & Fleuret 2018).
Putting everything together, using uninformative negative samples with near zero loss results in the following chain of undesirable properties:
oz Udt d l22
Ved . 1|2 + Tr(Vp, (ga ))
EA
(13)
low upper bound
diminishing gradient norm
large scholastic variance
slow convergence
The uninformative negative samples yield diminishing gradient norms, larger variances of the scholastic gradient estimator, and less optimal learning convergence.
Inefficacy of Local In-Batch Negatives: We argue that, when training DR models, the in-batch local negatives are unlikely provide informative samples due to two properties of text retrieval.
Let -** be the set of informative negatives that are hard to distinguish from D+ and be the batch size, we have (1) b & [C], the batch size far smaller than the corpus size; (2) DD~*| < |C]. that only few negatives are informative and the majority of corpus is trivially unrelated.
Both conditions hold in most dense retrieval scenarios. The two together make the probability that random mini-batch includes meaningful negatives (p $10="" close zero. Selecting negatives from local training batches unlikely provides optimal training signals for dense retrieval.
4

---

Published as a conference paper at ICLR 2021
4 APPROXIMATE NEAREST NEIGHBOR NOISE CONTRASTIVE ESTIMATION
Our analyses show the importance, if not necessity, to construct negatives globally from the corpus to avoid uninformative negatives for better learning convergence. In this section, we propose Approximate nearest neighbor Negative Contrastive Estimation (ANCE), which selects negatives from the entire corpus using an asynchronously updated ANN index.
ANCE samples negatives from the top retrieved documents via the DR model from the ANN index:
0 = argming ΣΣ Σ d+ ED
U[flg, (,
(14)
with D AACEE = ANN f(a.d) D+ and ANN f(0.a) the top retrieved documents by f() from the ANN index. By definition, D ANCE are the hardest negatives for the current DR model: DANCE ~ D In theory, these more informative negatives have higher training loss, elevate the upper bound on the gradient norms (first component of Eqn 13.. and prevent the slow convergence indicated in Eqn 13
ANCE can pair with many DR models. For simplicity, we use BERT-Siamese (Eqn. 2). with shared encoder weights between and d and negative log likelihood (NLL) loss (Luan al. 2020).
Asynchronous Index Refresh:
During stochastic training. the DR model s() is updated each mini- apdate-to-date ANN index to select fresh ANCE negatives is challenging, as
batch. Maintaining the index update requires two operations: 1) Inference: refresh the representations of all documents in the corpus with an updated DR model; 2) Index: rebuild the ANN index using updated representations. Although Index is efficient (Johnson et al.) 2017). Inference is too expensive to compute per batch as it requires a forward pass corpus much bigger than training batch.
Thus we implement an asynchronous index refresh similar to Guu et al. (2000) and update the ANN index once every m batches, i.e., with checkpoint fE. As illustrated in Fig. 2 besides the Trainer, we run an Inferencer that takes the latest checkpoint (e.g.. f&)) and recomputes the encodings of the entire corpus. parallel, the Trainer continues its stochastic learning using D/r- from ANN fe-.. Once the corpus is re-encoded, the Inferencer updates the index (ANN,) and feed it to the Trainer, e.g., through a shared file system. In this process, the ANCE negatives (D (DANCE) are asynchronously updated to "catch up" with the stochastic training, with an async-gap determined by the computing resources allocated to the Inferencer. Our experiment in Sec studies the influence of this async-gap in learning convergence.
5 EXPERIMENTAL METHODOLOGIES
This section describes our experimental setups. More details can be found in Appendix A.
and A.2
Benchmarks: The web search experiments use the TREC 2019 Deep Learning (DL) Track (Craswell et al. 2020). It is a standard ad hoc retrieval benchmark: given web queries from Bing, to retrieval passages or documents from the MS MARCO corpus (Bajaj al. 2016). We use the official setting and focus on the first stage retrieval, but also show results when reranking top 100 BM25 candidates.
The OpenQA experiments use the Natural Questions (NQ) (Kwiatkowski et al. 2019) and TriviaQA (TQA) (Joshi et al. 2017), following the exact settings from Karpukhin et al. (2020). The metrics are Coverage 20/100, which evaluate whether the Top-20/100 retrieved passages include the answer. We also evaluate whether ANCE's better retrieval can propagate to better answer accuracy, by running the state-of-the-e systems' readers on top of ANCE retrieval. The readers are RAG-Token (Lewis) et al. 2020bb on NQ and DPR Reader on TQA, using their suggested settings.
We also study the effectiveness of ANCE the first stage retrieval of a commercial search engine's production system. We change the training of production-quality DR model ANCE, and evaluate the offline gains in various corpus sizes, encoding dimensions, and exact/approximate search.
Baselines: In TREC DL, we include best runs in relevant categories and refer to Craswell et al.
(2020) for more baseline scores. We implement various DR baselines using the same Siameee (Eqn. 2). but with different training negative construction: random sampling in batch (Rand Neg). random sampling from BM25 top 100 (BM25 Neg) (Lee et al., 2019 Gao et al. (0206). and the 1:1
combination of BM25 and Random negatives (BM25 Rand Neg) (Karpukhin al. 2020
Luan
5

---

Published as a conference paper at ICLR 2021
Table 1: Results in TREC 2019 Deep Learning Track. Results not available are marked "n.a.", not applicable are marked as "-". Best results in each category are marked bold. Dense Retrieval baselines use the same BERT-Siamese but different training strategies.
MARCO Dev
TREC DL Passage
TREC DL Document
Passage Retrieval
NDCG@
NDCG@ 10
MRR@IN 10
Recall Ik
Rerank
Retrieval
Rerank
Retrieval
Sparse & Cascade IR
BM25
0.240
0.814
0.506
0,519
Best DeepCT
0,243
n.a.
n.a.
0,554
Best TREC Trad Retrieval
0.240
n.a.
0.554
0.549
BERT Reranker
0.742
0.646
Dense Retricval
Rand Neg
0,261
0,949
0.605
0.552
0.615
0.543
NCE Neg
0.256
0.943
0.602
0.539
0.618
0.542
BM25 Neg
0.299
0.928
0,664
0.591
0.626
0,529
DPR (BM25 + Rand Neg)
0.311
0,952
0,653
0.600
0,629
0,557
BM25 Rand
0,280
0,948
0.609
0,576
0.637
0,566
BM25 + NCE Neg
0.279
0,942
0.608
0.571
0.638
0.564
BM25 + BM25 Rand
0.306
0.939
0.648
0.591
0.626
0.540
ANCE (FirstP)
0.330
0.959
0.677
0.648
0.641
0,615
ANCE (MaxP)
0.671
0.628
Table 2: Retrieval results (Answer Coverage at Top-20/100) on Natural Questions (NQ) and Trivial QA (TQA) in the setting from Karpukhin et al. (2020).
Table 3: Relative gains in the first stage retrieval of a commercial search engine. The gains are from changing the training of a produc- tion DR model to ANCE.
Single Task
Multi Task
NQ
TQA
TQA
Retriever
Top-20/100
Top-20/100
Top-20/100
Top-20/100
BM25
59.1/73.7
66.9/76.7
Corpus Size
Dim
Search
Gain
DPR
78.4/85.4
79.4/85.0
79.4/86.0
78.8/84.7
Million
+18.4%
BM25+DPR
76.6/83.8
79.8/84.5
78.0/83.9
79.9/84.4
Billion
64
KNN
+14.2%
ANCE
81.9/7755
80.3/85.3
82.1/87.9
80.3/85.2
Billion
64
ANN
+15.5%
al. 2020). We also compare with contrastive learning/Noise Contrastive Estimation, which uses hardest negatives in batch (NCE Neg) (Gutmann & Hyvärinen 2010 Oord et al.] 2018 Chen et al.)
2020a). OpenQA, we compare with DPR, BM25, and their combinations (Karpukhin et al. 2020).
Implementation Details: In TREC DL, recent research found MARCO passage training labels
cleaner Yan et al. 2019) and BM25 negatives can help train dense retrieval (arpukhin et al. 2020
Luan al.) 2020). Thus, include "BM25 Warm Up" setting (BM25 *), where the DR
models are first trained using MARCO official BM25 Negatives. ANCE is also warmed up by BM25
negatives. All DR models in TREC DI. are fine-tuned from RoBERTa base uncased (Liu al.) 2019)
In OpenQA, we warm ANCE using the released DPR checkpoints (Karpukhin et al. 2020
To fit long documents in BERT-Siamese, ANCE uses the two settings from Dai & Callan 2019b).
FirstP which uses the first 512 tokens of the document, and MaxP, where the document is split to 512-token passages (maximum
and the passage level scores are max-pooled. The max-pooling operation is natively supported in ANN, The ANN search uses the Faiss IndexFlatIP Index (Johnson) al. 2017). We use batch size and gradient accumulation step 2 on V100 32GB GPUs. For each positive, we uniformly sample one negative from ANN top 200 (weighted sample and/or from top 100 also work well). We measured ANCE efficiency using one 32GB V100 GPU, Intel(R) Xeon(R) Platinum 8168 CPU and 650GB of RAM memory.
In asynchronous training, we allocate equal amounts of GPUs to the Trainer and the Inferencer, often four or eight each. The Trainer produces model checkpoint every 5k or 10k training batches. The Inferencer loads the recent model checkpoint and calculates the embeddings of the corpus in parallel. Once the embedding calculation finishes, negative construction. All their communications are through a shared file system. On MS MARCO, the ANN negative index refreshed about every 10K training steps.
ANN index is built and the Trainer switches to it for

---

Published as a conference paper at ICLR 2021
Table 4: OpenQA Test Scores in Single Task Setting, ANCE+Reader switches the retrieve of the OpenQA systems from DPR ANCE
Table 5: Efficiency of ANCE Serving and Training.
Operation
Offline
Online
BM25 Index Build
and keeps their QA components, which is RAG-Token on Natural Questions (NQ) and
BM25 Retrieval
37ms
BERT Rerank
1.15s
DPR Reader Trivia QA (TQA). T5 results
Sparse TR Total (BM25 + BERT)
1.42s
ANCE Inference
are "closed-bow" booedd.booo..... The others are book.
Encoding of Corpus/Per doe
10h/4.5ms
Model
NQ
TQA
Query Encoding
2mss
T5-118 (Closed) (Roberts dl 2020
34,5
ANN Retrieval (batched q)
9ms
T5-118- SSM (hoeserr Roteets
Dense Retrieval Total
11.6ms
REALM (Guu et al. 2020
40.4
ANCE Training
Karpukian
413
Eneoding of Corpus/Per doc
10h/4.5ms
DPR BBF25 (Karukk eh 2020
39.0
57.0
ANN Index Build
10s
Moken (Lewn AUAL
44.1
55.2
RAG-Sequence
(Ta.iieeeeewwssss (Lewss
Neg Construction Per Batch
72ms
ANCE Reader
46.0
57.5
Back Propagation Per Batch
19ms
15
14
Positive
35
35
Negative
12
30
30-
11
10
9
8
7
20
150
100
100
200
(a) ANCE FirstP (100%)
(b) NCE Neg (0%)
(c) Rand Neg (0%)
(d) BM25+Rand (7%)
Figure 3: The top DR scores for random TREC DL testing queries. The x-axes are their ranking order. The y-axes are their retrieval scores minus corpus average. All models are warmed up by BM25
Neg. The percentages are the overlaps between the testing and training negatives near convergence.
EVALUATION RESULTS
In this section, we first evaluate the effectiveness and efficiency of ANCE. Then we empirically study the convergence of ANCE training and the influence of the asynchronous gap. More comparisons of dense and sparse retrieval, hyperparameter study, and case study are in Appendix.
6.1 EFFECTIVENESS
In web search (Table T. ANCE significantly outperforms all sparse retrieval, including the BERT- based DeepCT (Dai et al. 2019). Among DR models with different training strategies, ANCE is the only one robustly exceeding sparse methods in document retrieval. In OpenQA, ANCE outperforms DPR and its fusion with BM25 (DPR+BM25) in retrieval accuracy (Table 2 It also improves end-to-end QA accuracy, using the same readers with previous state-of-the--rre arte but ANCE retriever (Table 4. ANCE's effectiveness is even more observed real production (Table 3)
Among all DR models, ANCE has the smallest gap between its retrieval and reranking accuracy, showing the importance of global negatives in training retrieval models. ANCE retrieval nearly matches the accuracy of the cascade IR with interaction-basee BERT Reranker (Nogueira & Cho 2019). even though BERT-Siamese does not explicitly capture term-level interactions. With ANCE, we can learn representation space that effectively captures the finesse of search relevance.
6.2 EFFICIENCY
The efficiency of ANCE (FirstP) in TREC DL doc is shown in Table In serving, we measure the online latency to retrieve/rank 100 documents per query, with query batched. DR is 100x faster than BERT Rerank, natural benefit of BERT-Siamese where the document encodings are calculated offline and separately with the query. In comparison, the interaction- BERT once per query and candidate document pair. The bulk of training computing is in calculating the encoding of the corpus for ANCE negative construction, which mitigated by making the index refresh asynchronous.
BERT Reranker runs
7

---

Published as a conference paper at ICLR 2021
ANCEIFENAM
0.6
6
BH25
0.4
4-
0.2
2
0.0
0
0k 5k 10k15k20k25k30k
5k 10k15k20k25k30k
0k 5k 10k15k20k25k33k
10k15k20k25k30k
(a) Training Loss
(b) Grad Norm (Bottom) (c) Grad Norm (Middle)
(d) Grad Norm (Top)
Figure 4: The loss and gradient norms during DR training (after BM25 warm up). The gradient norms
are the per-layer average of the bottom (1-4), middle (5-8), and top 12) transformer layers. Black dotted lines are the grad norm of the last layer in ANCE (FirstP). The x-axes training steps.
1.4
NDCG@10 10
1.1
Loss
NDCG@10
Loss
-0.5
-0.4
0.20k
100k
200k
100k
200k
0k
100k
200k
0k
100k
200k
(a) 10k Batch; 4:4;
le-5
(b) 20k Batch; 8:4; le-6
(c) 5k Batch; 4:8;
le-6
(d) 10k Batch; 4:4; 5e-6
Figure 5: Training loss and testing NDCG of ANCE (FirstP) on documents. The sub captions list the ANN index refreshing rate (e.g., per 10k Batch). Trainer:Infereneer GPU allocation (e.g., 4:4), and learning rate (e.g., le-5). The x-axes are the training steps.
6.3 EMPIRICAL ANALYSES ON TRAINING CONVERGENCE
We first show the long tail distribution of search relevance in dense retrieval. As plotted in Fig. there few instances per query with significant higher retrieval scores, while the majority form a long tail. In retrieval/rankking, the key challenge is to distinguish the relevant ones among those highest scored ones; the rest trivially irrelevant. We also empirically measure the probability of local in-batch negatives including informative negatives "), by their overlap with top 100 highest scored negatives. This probability, either using NCE Neg Rand Neg, is zero, the same shows. In comparison, the overlap between BM25 Neg with top dense retrieved negatives is 15%, while that of ANCE negatives starts 63% and converges 100% by design.
theory
Then we empirically validate our theory that local negatives lead to lower loss, bounded gradient norm, non-ideal importance sampling, and thus slow convergence (3)..[3). The training loss and pre-clip gradient norms during DR training are plotted in Fig. 4 As expected, the uninformative local negatives resulted in near-zero gradient norms, while ANCE global negatives maintain a higher gradient norm. The gradient norm of the last layer in the BERT-Siamese model during ANCE training (black dotted lines in Fig. 4 is consistently bigger than the other layers, which empirically theory suggests, the gradient norms of local
aligns with the upper bound in Eqn. 12 Also negatives are bounded close to zero, while those of ANCE global negatives are bigger by orders of magnitude. This confirms that ANCE better approximates the oracle importance sampling distribution (pz- x [dd ()2) and improves learning convergence.
6.4
IMPACT OF ASYNCHRONOUS GAP
The efficiency constraints enforce an asynchronous gap (async-gap) in ANCE training: The negatives selected using the encodings from earlier stage of the being optimized DR model. The async-gap is determined by the target index refreshing rate, which determined by the allocation of computing resource the Trainer versus the Inferencer, well the learning rate. This experiment studies the impact of this async-gap. The training curves and testing NDCG of different configurations plotted in Fig.
8

---

Published as a conference paper at ICLR 2021
A too large async-gap, either from large learning rate (Fig. 5(a)) low refreshing rate (Fig. 5(b) makes the training unstable, perhaps because the refreshed index changes too dramatically. as indicated by the peaks in training loss and dips of testing NDCG. The async-gap is not significant when we allocate an equal amount of GPUs to the index refreshing and to the training (Fig. ((d) Further reducing the gap (Fig. 5(c) does not improve learning convergence.
In many scenarios, using a same amount of extra GPUs for ANCE as a one-time training cost is a good return of investment. The efficiency bottleneck in production is often in inference and serving.
7 RELATED WORK
In early research on neural information retrieval (Neu-IR) (Mitra & Craswell 2018 a common belief was that the interaction models, those that explicitly handle term level matches, are more effective though more expensive (Guo et al.) 2016: Xiong et al. 2017 Nogueira & Cho. 2019). Many techniques are developed to reduce their cost, for example, distillation (Gao al. 2020a) and caching (Humeau et al. 2020) Khattab & Zaharia 2020 MacAvaney et al. 2020). ANCE shows that a properly trained representation- based BERT-Siamess can be effective as well. This finding will motivate many new research explorations in Neu-IR.
Deep learning has been used to improve various components of sparse retrieval, for example, term weighting (Dai & Callan, 2019b), query expansion (Zheng al., 22220) and document expan- sion (Nogueira et al. 2219)) Dense Retrieval chooses a different path and conducts retrieval purely in the embedding space via ANN search (Lee et al.] 2019 Chang et al.) 2020; Karpukhin al. 2020 Luan et al., 2020). This work demonstrates that a simple dense retrieval system can achieve SOTA accuracy, while also behaves dramatically different from sparse retrieval. The recent advancement in
dense retrieval may raise a new generation of search systems.
Recent research in contrastive representation learning also shows the benefits of sampling negatives from a larger candidate pool. In computer vision, He et al. (2020) decouple the negative sampling pool size with training batch size, by maintaining a negative candidate pool of recent batches and updating their representation with momentum. This en enlarged negative pool significantly improves unsupervised visual representation learning (Chen al.] 2020b). A parallel work (Xiong al. 2021) improves DPR by sampling negatives from a memory bank (Wu et al. 2018) in which the representations of negative candidates are frozen so more candidates can be stored. Instead of bigger local pool, ANCE goes all the way along this trajectory and constructs negatives globally from the entire corpus, using an asynchronously updated ANN index.
Besides being a real world application itself, dense retrieval is also core component in many other language systems, for example, to retrieve relevant information for grounded language models (Khan delwal et al.] 20200] Guu et al.] (2020), extractive/generativ QA (Karpukhin et al.) 22000] Lewis et al. 2020b), and fact verification (Xiong et al., 2021). or to find paraphrase pairs for pretraining (Lewis) al. (2020a). There dense retrieval models either frozen optimized indirectly by signals from their end tasks. ANCE is orthogonal to those lines of research and focuses on the representation learning for dense retrieval. Its better retrieval accuracy can benefit many other language systems.
8 CONCLUSION
In this paper, we first provide theoretical analyses on the convergence of representation learning in dense retrieval. We show that under common conditions in text retrieval, the local negatives used in DR training are uninformative, yield low gradient norms, and contribute little to the learning convergence. We then propose ANCE to eliminate this bottleneck by constructing training negatives globally from the entire corpus. Our experiments demonstrate the advantage of ANCE in web search, OpenQA, and the production environment of a commercial search engine. Our studies empirically validate our theory that ANCE negatives have much bigger gradient norms, reduce the stochastic gradient variance, and improve training convergence.
ACKNOWLEDGMENTS
We thank Di He for discussions learning theories and Safoora Yousefi for feedback in writing.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Guillaume Alain, Alex Lamb, Chinnadhurai Sankar, Aaron Courville, and Yoshua Bengio. Variance reduction in SGD by distributed importance sampling, arXiv preprint urXiv:1511.066 2015.
Payal Bajaj. Daniel Campos, Nick Craswell, Li Deng. Jianfeng Gao, Xiaodong Liu, Rangan Majumder, Andrew McNamara, Bhaskar Mitra, Tri Nguyen, al. MS MARCO: A human generated MAchine Reading COmprehension dataset. arxiv preprint arXiv: /61 1.09268, 2016.
Wei-Cheng Chang. X Yu Felix, Yin- Wen Chang. Yiming Yang, and Sanjiv Kumar. Pre-training tasks for baasdd based large- scale retrieval. Proceedings of the 8th International Conference on Learning Representations, ICLR 2020, Virtual Event, April 26-30. OpenReview.net, 2020.
embedding
Danqi Chen, Adam Fisch, Jason Weston, and Antoine Bordes. Reading wikipedia answer open-oomain questions. Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, ACL 2017, Vancouver, Canada, July 30 August 4, 2017. pp. 1870-1879. ACL, 2017.
Ting Chen, Simon Komblith, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, pp. 1597-1607. PMLR, 2020a.
Xinlei Chen, Haoqi Fan, Ross Girshick, and Kaiming He. Improved baselines with momentum contrastive learning. arXiv preprint ar 2it:2203304299,, 2020b.
Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Ellen M. Voorhees. Overview of the TREC 2019 deep learning track. Proceedings of the Text REtrieval Conference (TREC), TREC, 2020.
W Bruce Croft, Donald Metzler, and Trevor Strohman. Search Engines: Information Retrieval in Practice. Pearson Education, 2009. ISBN 978-0-13-136489)
Zhuyun Dai and Jamie Callan. Context-aware sentence/passage term importance estimation for first stage retrieval. arXiv preprint arxiv: 1910. 10687, 2019a.
Zhuyun Dai and Jamie Callan. Deeper text understanding for IR with contextual neural language modeling. In Proceedings of the 42nd International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2019, Paris, France, July 21-25. pp. 985-988. ACM, 2019b.
Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell, Quac Viet Le, and Ruslan Salakhutdinov, XX:: Attentive language models beyond fixed-length context. In Proceedings of the 57th Conference of the Association for Computational Linguistics, ACI. 2019, Florence, Italy, July 28- August 2, pp. 2978-2988. ACL, 2019.
Luyu Gao, Zhuyun Dai, and Jamic Callan. Understanding BERT rankers under distillation. In Proceedings of ICTIR 20: The 2020 ACM SIGIR International Conference on the Theory of Information Retrieval, Virtual Event, Norway, September 14-17, pp- 149-152. ACM, 2020a.
Luyu Gao, Zhuyun Dai, Zhen Fan, and Jamie Callan. Complementing lexical retrieval with semantic residual embedding. arXiv preprint arXiv:2004. 13969, 2020b.
Jiafeng Guo, Yixing Fan, Qingyao Ai, and W Bruce Croft. A deep relevance matching model for ad-hoc retrieval. In Proceedings of the 25th ACM International Conference on Information and Knowledge Management, CIKM 2016, Indianapolis, IN USA, October 24-28. pp. 55-64. ACM, 2016.
Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. arXiv preprint arXiv: 10396, 2020.
Michael Gutmann and Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnormal- ized statistical models. In Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, AISTATS 2010, Sardinia, Italy, May 13-15, JMLR Proceedings, pp. 297-304. JML..org, 2010.
Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming- Wei Chang. REALM: Retrieval-augmentee language model traitraning. arXiv preprint arXiv:2002.00 08900, 2020.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning, In 2020 JEEE/CVF Conference Computer Vision and Pattern Recognition, CVPR 2020, Seattle, WA, USA, June 13-19, pp. 9726-9735. IEEE, 2020.
Samuel Humeau, Kurt Shuster, Marie-Anne Lachaux, and Jason Weston. Poly-encoders Architectures and pre-training strategies for fast and accurate multi-sentence scoring. In Proceddings of 8th International Conference on Learning Representations, ICLR 2020, Virtual Event, April 26-30. OpenReview.net, 2020.
10

---

Published as a conference paper at ICLR 2021
Jeff Johnson, Matthijs Douze, and Hervé Jégou. Billion-scale similarity search with GPUs. arXiv preprint 17X.v01702008744 2017.
Tyler B. Johnson and Carlos Guestrin. Training deep models faster with rohust, approximate importance sampling. In Proceedins of the Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, Montréal, Canada, December 3-8, pp. 7276-7286, 2018.
Mandar Joshi, Eunsol Choi, Daniel S Weld, and Luke Zettlemoyer. TriviaQA: A large scale distantly supervised challenge dataset for reading comprehension. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, ACL 2017, Vancouver, Canada, July 30 August 4, pp. 1601-1611. ACL, 2017.
Vladimir Karpukhin, Barlas Oguz, Sewon Min, Ledell Wu, Sergey Edunov, Danqi Chen, and Wen-tau Yih. Dense passage retrieval for open-domain question answering. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20, pp. 6769-6781 ACL, 2020.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with impor- tance sampling. In Proceedings of the 35th International Conference on Machine Learning, ICMI, 2018, Stockholmssmässon, Stockholm, Sweden, July 10-15, pp. 2530-2539.. PMLR, 2018.
Urvashi Khandelwal, Omer Levy, Dan Jurafsky, Luke Zeulemoyer, and Mike Lewis. Generalization through memorization: Nearest neighbor language models. In Proceedings of the 8th International Conference on Learning Representations, ICLR 2020, Virtual Event, April 26-30. OpenReview.net, 2020.
Omar Khattab and Matei Zaharia. ColBERT: Efficient and effective passage search via contextualized late interaction over BERT. Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR 2020, Viriual Event, July 25-30, pp. 39-48. ACM, 2020.
Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Jacob Devlin, Kenton Lee, et al. Natural Questions: A henchmark for question answering research. Transactions of the A Association for Computational Linguistics, 7:453-466, 2019.
Victor Lavrenko and W Bruce Croft. Relevance- language models. In ACM Special Interest Group on Information Retrieval (SIGIR) Forum, volume 51, pp. 260 267. ACM, 2017.
Kenton Lee, Ming- Wei Chang, and Kristina Toutanova. Latent retrieval for weakly supervised open domain question answering. In Proceedings of the 57th Conference the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28- August 2, pp. 6086-6096. ACL, 2019.
Mike Lewis, Marjan Ghazvininejad, Gargi Ghosh, Armen Aghajanyan, Sida Wang, and Luke Zettlemoyer. Pre-training via paraphrasing. In Proceedings of the Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, virtual, December 6-12, 2020a.
Patrick Lewis, Ethan Perez, Aleksandara Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al. Retrieval-augmennte generation for knowledge- intensive nlp tasks. arXiv preprint arXiv:2005.1 /401, 2020b.
Tie- Yan Liu. Learning to rank for information retrieval. Foundations and Trends@ in Information Retrieval, 3 (3):225 1112253331,20 2009.
Yinhan Liu, Myle Out, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A robustly optimized BERT pretraining approach. arXiv preprint arXi: 1902. 2019.
Yi Luan, Jacoh Fisenstein, Kristina Toutanova, and Michael Collins. Sparse, dense, and attentional representa- tions for text retrieval. arXiv preprint arXiv:2005.001 2020.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, 9(Nov):257 2605, 2008
Scan MacAvancy, Franco Maria Nardini, Raffaele Perego, Nicola Tonellotto, Nazli Goharian, and Ophir Frieder. Efficient document re-ranking for transformers by precomputing term representations. In Proceedings of the 43rd International ACM SIGIR conference research and development in Information Retrieval, SIGIR 2020, Virtual Event, China, July 25-30, 2020, pp. 49-58. ACM, 2020.
Bhaskar Mitra and Nick Craswell. An introduction to neural information retrieval. Foundations and Trendy in Information Retrieval, 13(1):1-12,, 2018.
11

---

Published as a conference paper at ICLR 2021
Marius Mosbach, Maksym Andriushchenko, and Dietrich Klakow. On the stability of fine-tuning BERT: Misconceptions. explanations, and strong baselines. Proceedings of the 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, May 3-7. OpenReview.net, 2021.
Rodrigo Nogueira and Kyunghyun Cho. Passage re-ranking with BERT. arXiv preprint arXiv:9911000055. 2019.
Rodrigo Nogueira, Wei Yang, Jimmy Lin, and Kyunghyun Cho. Document expansion by query prediction. arXiv preprint arXiv:1904.08333 2019.
Aaron van den Oord, Yazhe Li. and Oriol Vinyals. Representation learning with contrastive predictive coding. arXiv preprint Xrx: 807.0378, 2018.
Pranav Rajpurkar, Jian Zhang. Konstantin Lopyrev, and Perey Liang. SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing. EMNLP 2016, Austin, Texas, USA, November 1-4. pp. 2383-2333 2392.2232.222 ACL, 2016.
Adam Roberts, Colin Raffel, and Noam Shazeer. How much knowledge can you pack into the parameters of language model? In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020, Online, November 16-20. pp. 5418-5426. ACL, 2020.
James Thome. Andreas Vlachos. Oana Cocarascu, Christos Christodoulopoulls, and Arpit Mittal. The fact extraction and verification (FEVER) shared task. In Proceedings of the 1st Workshop Fact Extraction and VERification (FEVER). pp. 1-9, 2018.
Ellen M Voorhees. Variations relevance judgments and the measurement of retrieval effectiveness. Information Processing & Management, 3655)697-776, 2000.
Alex Wang, Amanprect Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. GLUE: A multi- task benchmark and analysis platform for natural language understanding. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9. OpenReview.net, 2019.
Zhirong Wu, Yuanjun Xiong, Stella X Yu, and Dahua Lin. Unsupervised feature learning via non-parametric in- stance discrimination. In Proceedings of 2018 IEEE Conference on Computer Vision and Pottern Recognition, CVPR 2018, Salt Lake City, UT, USA, June 18-22, pp. 3733-3742. IEEE, 2018.
Chenyan Xiong, Zhuyun Dai, Jamic Callan, Zhiyuan I Liu, and Russell Power. End-to-end neural ad-hoc ranking with kernel pooling. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2017, Shinjuku, Tokyo, Japan, August 7-11, pp. 55-64, ACM, 2017.
Wenhan Xiong, Xiang Lorraine Li, Srini Iyer, Jingfei Du, Patrick Lewis, William Yang Wang, Yashar Mehdad, Wen-tau Yih, Sebastian Riedel, Douwe Kiela, and Barlas Oğuz. Answering complex open-domain ques- tions with multi-hop dense retrieval. In Proceedings of 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, May 2021.
Ming Yan, Chenliang Li, Chen Wu, Bin Bi, Wei Wang, Jiangnan Xia, and Luo Si. IDST at TREC 2019 deep learning track: Deep cascade ranking with generation-basee document expansion and pre-trained language modeling. In Proceedings of Text REtrieval Conference. TREC, 2019.
Chen Zhao, Chenyan Xiong, Corby Rosset, Xia Song. Paul Bennett, and Saurabh Tiwary. Transformer-Xi Multi-evidence reasoning with extra hop attention. In Proceedings of the 8th International Conference on Learning Representations, ICLR 2020, Virtual Event, April 26-30. OpenReview.net, 2020.
Zhi Zheng, Kai Hui, Ben He, Xianpei Han, Le Sun, and Andrew Yates. BERT-QE: Contextualized query expansion for document re-ranking. pp. 4718 4728, 2020.
12

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 MORE EXPERIMENTAL DETAILS
There are two tasks in the TREC DL 2019 Track: document retrieval and passage retrieval. The training and development sets are from MS MARCO, which includes passage level relevance labels for million Bing queries (Bajaj et al. 2016). The document corpus was post-constructed by back-filling the body texts the passage's ' URLs and their labels were inherited from its passages (Craswell ct al. 2020). The testing sets are labeled by NIST accessors on the top 10 ranked results from past Track participants (Craswell et al. 2020).
More Details on TREC DL Benchmarks:
TREC DL official metrics include NDCG @ 10 on test and MRR @ 10 on MARCO Passage Dev. MARCO Document Dev is noisy and the recall the DL Track testing is less meaningful due to low label coverage on DR results. There a two-year gap between the construction the passage training data and the back-filling of their full document content. Some original documents were no longer available. There is also a decent amount of content changes in those documents during the two-year gap, and many no longer contain the passages. This back-filling perhaps is the reason why many Track participants found the passage training data is more effective than the inherited document labels. Note that the TREC testing labels are influenced as the annotators were provided the same document contents when judging.
All the TREC DL runs are trained using these training data. Their inference results on the testing queries of the document and the passage retrieval tasks were evaluated by NIST assessors in the standard TREC-style pooling technique (Voorhees (200). The pooling depth is set to 10, that is, the top 10 ranked results from all participated runs are evaluated, and these evaluated labels are released the official TREC DL benchmarks for passage and document retrieval tasks.
More Details on OpenQA Experiments: All the DPR related experimental settings, baseline systems, and DPR Reader are based on their open source libarary The RAG-Token reader uses their open-source release in huggingfacd" The RAG-Seq release in huggingface not yet stable by the time did our experiment, thus choose the RAG-Token in our OpenQA experiment. RAG only releases the NQ models thus we DPR reader on TriviaQA. We feed top 20 passages from ANCE to RAG- Token on NQ and top 100 passages to DPR's 's BERT Reader, following the guideline in their open-source codes.
The most representative sparse retrieval baselines in TREC DL include the standard BM25 ("bm25base" or "bm25base p²). Best TREC Sparse Retrieval ("bm25tuned rm3" or "bm25tuned prf prr__"") with tuned query expansion (Lavrenko & Crofi 2017), and Best DeepCT
More Details on Baselines:
bm_ee2", doc only). which uses BERT to estimate the term importance for BM25 (Dai & Callan] 2019a). These three runs represent the standard sparse retrieval, best classical sparse retrieval, and the recent progress of using BERT to im- prove sparse retrieval. We also include the standard cascade retrieval-and-reaanee ("bm25exp marcomb" or "p_ exp rm3 bert"), which is the best run using standard BERT on top of query/doc expansion, from the groups with multiple top MARCO runs (Nogueira & Cho 2019 Nogueira et al. 2019).
systems BERT Reranker
BERT-Siamese Configurations: We follow the network configurations in Luan et al. (2020) in all Densc Retrieval methods, which we found provides the most stable results. More specifically, we initialize the BERT- Siamese model with RoBERTa base (Liu et al. 2019) and add a 768 x 768 projection layer on top of the last layer's "[CLS]" token, followed by layer norm.
We use BERT- Siames,, NLL loss, and dot product accuracy with more vectors per document, BCE loss, and cosine similarity, but that is not the focus of this paper.
consistent with recent research. We have obtained better
The training often takes about 1-2 hours per ANCE epoch, which is whenever new ANCE negative is ready, it immediately replaces existing negatives in training, without waiting. It converges in about 10 epochs, similar to other DR baselines. The optimization uses LAMB optimizer, learning rate 5e-6 for document and le-6 for passage retrieval, and linear warm-up and decay after 5000 steps. More detailed hyperparameter settings can be found in our code release.
Implementation Details:
A.2 OVERLAP WITH SPARSE RETRIEVAL IN TREC 2019 DL TRACK
As a nature of TREC-style pooling evaluation, only those ranked in the top 10 by the 2019 TREC participating systems were labeled. As result, documents not in the pool and thus not labeled all considered irrelevant, even though there may be relevant ones among them. When reusing TREC style relevance labels, it very important to keep track of the "hole rate" on the evaluated systems, i.c., the fraction of the top K ranked results without TREC labels (not in the pool). A larger hole rate shows that the evaluated methods are very different
13

---

Published as a conference paper at ICLR 2021
Table 6: Coverage of TREC 2019 DL Track labels on Dense Retrieval methods. Overlap with BM25 is calculated on top 100 retrieved documents.
TREC DL Passage
TREC DL Document
Method
Recall IK
Hole@ 10
Overlap BM25
Recall @ 100
Hole@ 10
Overlap w. BM25
BM25
0.685
5,9%
100%
0.387
0.2%
100%
BM25 Neg
0,569
25.8%
11.9%
0.217
28.1%
17.9%
BM25 Rand Neg
0.662
20.2%
16.4%
0.240
21.4%
21.0%
ANCE (FirstP)
0.661
14.8%
17.4%
0,266
13.3%
24.4%
ANCE (MaxP)
0,286
11.9%
24.9%
Table 7: Results of different hyperparameter configurations. "Top K Neg" lists the top k dense retrieved candidates from which sampled the ANCE negatives from.
Hyperparameter
MARCO Dev Passage
TREC DL Document Retrieval NDCG@10
Learning rate
Top K Neg
Refresh (step)
Retrieval MRR @10
Passage ANCE
le-6
200
10k
0.33
le-6
500
10k
0.31
2e-6
200
10k
0.29
2c-7
500
20k
0.303
2c-7
1000
20k
0.302
Document ANCE
le-5
100
10k
0.58
le-6
100
20k
0.59
le-6
100
5k
0.60
5e-6
200
10k
0.614
le-6
200
10k
0.61
from those systems that participated in the Track and contributed to the pool, thus the evaluation results are not perfect. Note that the hole rate does not necessarily reflect the accuracy of the system, only the difference of it.
In TREC 2019 Deep Learning Track, all the participating systems based on sparse retrieval. Dense retrieval methods often differ considerably from sparse retrievals confirmed in Table All DR methods have very low overlap with the official BM25 in their top 100 retrieved documents. At most, only 25% of documents retrieved by DR are also retrieved by BM25, This makes the hole rate quite high and the recall metric not very informative. also suggests that DR methods might benefit more this year's 's TREC 2020 Deep Learning Track if participants are contributing DR based systems.
general will retrieve many new documents. This
The MS MARCO ranking labels were not constructed based on pooling the sparse retrieval results. They were from Bing (Bajaj et al. 2016), which uses many signals beyond term overlap. This makes the recall metric in MS MARCO more robust as it reflects how single model can recover a complex online system.
A.3 HYPERPARAMETER STUDIES
We show the results of some hyperparameter configurations in Table The cost of training with BERT makes it difficult to conduct lot of hyperparameter explorations. Often a failed configuration leads divergence early training. We barely explore other configurations due the time-consuming nature working with pretrained language models. Our DR model architecture is kept consistent with recent parallel work and the learning configurations in Table are about all the explorations we did. Most of the hyperparameter choices are decided solely using the training loss curve and otherwise by the loss in the MARCO Dev set. We found the training loss, validation NDCG, and testing performance align well in (limited) hyperparameter explorations.
A.4 CASE STUDIES
In this section, show Win/Loss studies between ANCE and BM25, Among the 43 TREC 2019 DL Track evaluation queries in the document task, ANCE outperforms BM25 on 29 queries, loses on queries, and ties on the rest 1 query. The winning examples are shown in Table S and the losing ones are in Table 9 Their corresponding ANCE-leamer (FirstP) representations are illustrated by t-SNE in Fig. and Fig.
In general, we found ANCE better captures the semantics in the documents and their relevance to the query. The winning cases show the intrinsic limitations of sparse retrieval. For example, BM25 exact matches the "most popular food" the query "what is most popular food Switzerland" but document about Mexico. The term "Swiizerland" does match with the document but it in the related question section.
The losing cases in Table/are also quite interesting. Many times we found that it is not that DR fails completely and retrieves documents not related to the query's 's information needs at all, which was a hig concern when we started research in DR. The errors ANCE made include retrieving documents that related just exactly
14

---

Published as a conference paper at ICLR 2021
Table 8: Queries in the TREC 2019 DL Track Document Ranking Tasks where ANCE performs better than BM25. Snippets are manually extracted. The documents at the first disagreed ranking positions are shown. ANCE won on all of them. The NDCG@ 10 of ANCE and BM25 in the corresponding query is listed.
ANCE
BM25
Query:
qid (104861): J: Cost of interior concrete flooring
Title
Concrete network: Concrete Floor Cost
Pinterest: Types of Flooring
DocNo:
D293855
D22622155
Snippet:
For concrete floor with a basic finish,
Know About Hardwood Flooring And Its Types White Oak Floors Oak Floor- ing Laminate Flooring In Bathroom...
you expect to pay $2 to $12 per
square foot...
Ranking Position:
TREC Label:
3 (Very Relevant)
0 (Irrelevant)
NDCG@ TO:
0.86
0.15
Query:
qid (833860): What is the most popular food in Switzerland
Title:
Wikipedia: Swiss cuisine
Answers. com: Most popular traditional
food dishes of Mexico
DoeNo:
D1927155
D3192888
Snippet:
Swiss cuisine bears witness to many re- gional influences. Switzerland was historically country of farmers, tra- ditional Swiss dishes not be...
One of the most popular traditional Mex-
ican deserts is a spongy cake (in the related questions section) What is most popular food dish in Switzer- land?...
Ranking Position:
TREC Label:
3 (Very Relevant)
(Irrelevant)
NDCG@ 10:
0,90
0.14
Query:
qid (1106007): Define visceral
Title:
Vocabulary.com: Visceral D542828
Quizlet.com: A&P EX3 autonomic 9-10 D830758
DoeNo:
Snippet:
When something's 's visceral, you feel it in your guts. A visceral feeling is in- tuitive there might be rational explanation, but you feel that you know what's best...
Acetylcholine A neurotransmitter liber- ated by many peripheral nervous system neurons and central nervous sys- tem neurons...
Ranking Position:
TREC Label:
(Very Relevant)
(Irrelevant)
NDCG@ 10:
0.80
0.14
Relevant
Rand Neg
(a) 104861: interior flooring cost.
(b) 833860:: popular Swiss food
(c) 1106007: define visceral
Figure 6: t-SNE Plots for Winning Cases in Table Qids and queries are listed in the sub-captions.
relevant to the query, for example, "yoga pose" for "bow in yoga". In other cases, ANCE retrieved wrong documents due to the lack of the domain knowledge: the pretrained language model may not know "active margin" geographical terminology, not financial (which did not know neither and took time figure out when conducting this case study). There are also some cases where the dense retrieved documents make sense to us but were labeled irrelevant.
The t-SNE plots in Fig. and Fig. 7 show many interesting patterns of the learned representation space. The ANCE winning cases often correspond to clear separations of different document groups For losing cases the representation space is more mixed, there is too few relevant documents which may cause the variances in
15

---

Published as a conference paper at ICLR 2021
Table 9: Queries in the TREC 2019 DL Track Document Ranking Tasks where ANCE performs worse than BM25. Snippets are manually extracted. The documents at the first positions where BM25 wins are shown. The NDCG@ 10 of ANCE and BM25 on the corresponding query is listed. Typos in the query are from the realist web search queries in TREC.
ANCE
BM25
Query:
qid ( (182539): Example of monotonic function
Title
Wikipedia: Monotonic function
Explain Extended: Things SQL needs:
sargability of monotonic functions
DocNo:
D510209
D175960 In mathematics, monotonic function monotone function) function be-
Snippet:
I'm going to write a series of articles about the things SQL needs work
tween ordered sets that preserves or re-
faster and more efficienly...
verses the given order... For example, if y=g(x) is strictly monotonic on the range [a.b]
Ranking Position:
TREC Label:
0 (Irrelevant)
(Relevant)
NDCG@ 10:
0.25
0.61
Query:
qid (1117099: What is active margin
Title
Wikipedia: Margin (finance)
Yahoo Answer: What the difference between passive and active continental margins
DocNo:
D166625
D2907204
Snippet:
In finance, margin is collateral that the holder of a financial instrument...
An active continental margin is found on the lcading edge of the continent where
Ranking Position:
TREC Label:
0 (Irrelevant)
(Very Relevant)
NDCG@ 1O:
0.44
0.74
Query:
qid (1132213); How long hold bow in yoga
Title:
Yahoo Answer: How long should you
yogaoutlet.com: How to do bow pose in yoga
hold yoga pose for
DoeNo:
D3043610
D3378723
Snippet:
so I've been doing yoga for few weeks now and already notice that my flexi-
Bow Pose is an intermediate yoga back- bend that deeply opens the chest and the front of the body... Hold for up 30 seconds
ablity has increased drastically... That
depends the posture itself
Ranking Position:
3
TREC Label:
0 (Irrelevant)
3 (Very Relevant)
NDCG@ 10:
0.66
0.74
Query Relevant
ANCE Neg
BM25 Neg
Rand Nog
(a) 182539: monotonic function
(b) 1117099: active margin
(c) 1132213: yoga bow
Figure 7: t-SNE Plots for Losing Cases in Table 9
Qids and queries are listed in the sub-captions.
model performances. There are also many different interesting patterns in the ANCE-learned representation space. We include the t-SNE plots for all 43 TREC DL Track queries in open-source repo. More future analyses of the learned patterns in the representation space may help provide more insights on dense retrieval.
16


Reviews:
[{"review_id": "uLf22SM8Nr8", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\n \nThis paper studies the problem of dense text retrieval, which represents texts as dense vectors for approximate nearest neighbors (ANN) search. Dense text retrieval has two phases. The first phase learns a representation model to project semantically similar texts to vectors of large similarity scores (e.g. inner products or cosine similarity scores). The second phase adopts an ANN search algorithm to index these vectors and process queries. The paper claims key contributions at the first phase. Specifically, (1) The paper introduces a better negative sampling method to sample good dissimilar text pairs for training.  (2) The new method enables faster converge of model learning. (3) The new method leads to 100x faster efficiency than a BERT-based baseline, while achieving almost the same accuracy as the baseline. \n\n##########################################################################\n\nReasons for score: \n \nOverall, I like the idea of this paper and opt for a weak accept. A carefully designed negative sampling method should be able to outperform baselines that use simple heuristics. The efficiency improvement 100X is very promising. However, the paper can be better in experimental comparison and presentation. For experimental comparison, a stronger baseline using dense vectors should be included to strengthen the performance claim. For presentation, many important terms require clear definitions, without which the performance gain is not understandable. It will be good if the authors can address the above two issues in the rebuttal.\n \n##########################################################################\n\nPros:\n\n1. The paper proposes a novel negative sampling method. Based on the method, the paper proposes a new dense text retrieval framework ANCE. ANCE introduces an asynchronous index refresh to select the most dissimilar text pairs for training in a timely manner. \n \n2. The proposed ANCE achieves faster model training and equally accurate text retrieval when compared with a number of baselines. In a TREC 2019 task, ANCE achieves the best NDCG score against 11 baselines.  \n \n3. The authors promise to make code open source. That will greatly improve the reproducibility of the work.  The code, together with its performance, will serve as a new state-of-the-art for future study. \n\n##########################################################################\n\nCons: \n \n1.\tAn important baseline is missing. In section 5, the paper describes Baselines. According to the descriptions, all baseline use BM25 to retrieve samples for training. BM25 may not be the best for a strong baseline since it relies on sparse word tokens. An alternative is to use BERT [CLS] dense vectors of all texts and a similarity search algorithm such as locality sensitive hashing as the retriever. It will be good if the authors can add the baseline to the paper. \n\n2. The paper does not explain clearly why the proposed method runs faster than baselines. The experimental results support that the proposed method outperforms several baselines. However, the paper does not explain the performance superiority. I am not sure about which of dissimilar text pairs selection or index refresher or others in the proposed negative sampling leads to the superiority. The reason for uncertainty may be due to the lacking of definitions in the paper. For example, “BERT rerank” refers to a baseline but it has not a definition in the paper. The input and output of “BERT rerank” remain unclear. Similarly, “TREC 2019” is an important benchmark but it has not definitions related to the inputs and outputs. It is necessary to explain important concepts for the best readability of the paper.\n \n##########################################################################\n\nQuestions during rebuttal: \n \nI would like to see some experiments or discussions to clarify the above cons.\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "tp8S5VcPIB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the problem of representation learning for first-stage retrieval in text ranking/matching. Specifically, it investigates the role of negative instances and how to select them in the quality of representations. The paper is well-written and it does a fair job in motivating the problem and discussing related works.\n\nThe main pros are as follows:\n\n* Authors attempt to theoretically study the importance of negative instances and their impact on the gradients of objective function for text retrieval. Specifically, they posit that non-informative negative instances provide small gradients n the course of training, and thus adversely affect the convergence of gradient-based learnings.\n\n* Through various experiments, the authors show that by exploiting the top retrieved texts from the corpus, using the current learned representations, as 'hard' negative instances, the performance of text ranking methods can be significantly improved.\n\nThere are however some ambiguities and room for improvement:\n\n* As equation (10) suggests, the optimal distribution over negative instances is the one that minimizes the variance of gradients, or equivalently the norm of loss function. However, at many places it is pointed out that small losses prevent the model from learning and slow down the convergence rate. This is a kind of contradiction, and needs to be clarified,\n\n* Existing results from literature such as equation (11) are leveraged to connect the norm of loss function and the gradient of last layer of representation learning models. However, the arguments here are not quite rigorous. It should be clarified that these results hold for what types of ranking objectives, and what other assumptions such as smoothness, etc. are required.\n\n* The main bottleneck of using top retrieved documents as negative instances is the computational burden of updating the ANN indexing per batch. Therefore, the authors propose to perform this updating less frequently. It would be nice to have more comprehensive experiment to show that how sensitive is the performance vs the frequency of index updates.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ClJCjM897G4", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper explores how to effectively do negative sampling for dense retrieval. The paper shows that negatives sampled locally in batch are not informative, and proposes ANCE, a learning mechanism that selects hard training negatives globally from the entire corpus, using an asynchronously updated ANN index.\n\nStrength:\n1) Experiments show that the proposed method significantly outperforms state-of-the-art approaches such as DPR on MSMARCO, TRECDL, NaturalLanguages and TriviaQA.\n\nWeakness:\n1) The analysis on why in-batch local negatives are ineffective (in section 3) does not seem to be very insightful. Also, I did not see a big connection between this analysis and the negative sampling technique proposed in the following section.\n2) The idea of maintaining a set of global negatives is not new, and refreshing index asynchronously has also been explored in [Guu et al. 2020]\n\nOverall, I think this is a borderline paper. The experiments show improved performance over baseline methods, but the idea seems a bit incremental (a combination of existing tricks for training retrieval model).\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "08iPx7Tk8Ma", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\nSummary:\nAuthors start from an assumption: “local negative sampling is the bottleneck of dense retrieval’s effectiveness”. To overcome this limitation, authors propose ANCE (Approximate nearest neighbour Negative Contrastive Estimation), a new contrastive representation learning mechanism for dense retrieval. The basic idea is that of constructing negatives exploiting the being trained deep retrieval module. The idea is that the model considers as negatives borderline cases. They also show, theoretically, that this improves the variance of the stochastic gradient estimation thus leading to faster convergence.\n\n##########################################################################\nReasons for score: \nI honestly enjoyed reading the paper. It has a theoretical justification that explains the intuition of using hard negatives. Experiments are thorough and they show improvements over the state of the art. The discussion section is thorough. I believe that this research results are very important also in practice\n \n \n##########################################################################\nPros: \n \n1. The paper addresses a timely and important problem\n2. The paper gives a nice theoretical justification for the reasons why they have to use hard negatives\n3. Experiments are thorough and nicely done. Results are very good. I particularly enjoyed seeing that both on public datasets and on real world search systems the novel retrieval mechanism helps greatly.\n  \n##########################################################################\nCons: \n \n1. The only one thing that I believe might impair the utilisation of this method is that you need to reconstruct the embeddings every m batches. It takes 10h every reconstruction and it is not clear what happens every m batches. Do you start a novel reconstruction? Do you replace the current embedding version with a new one as soon as one finishes training? This aspect, in my opinion, is the weakest of the paper and it would deserve more attention by the authors.\n \n##########################################################################\nQuestions during rebuttal period: \n \nPlease address and clarify the cons above \n \n#########################################################################\nSome minor issues \n(1) In equation (2) I would call D^+ and D^-, D_q^+ and D_q^- in order to remark that negatives and positives are per-query.\n(2) an negative —> a negative\n(3) Citation Luan et al. —> It’s Toutanova not Toutanove\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper explores how to effectively conduct negative sampling in learning for text retrieval. The paper shows that negative examples sampled locally are not informative, and proposes ANCE, a new learning mechanism that samples hard negative examples globally, using an asynchronously updated ANN index.

Pros • The problem studied is important. • Paper is generally clearly written. • Solid experimental results. • There is theoretical analysis.

Cons • The idea might not be so new. The contribution is mainly from its empirical part.

During rebuttal, the authors have addressed the clarity issues pointed out by the reviewers. They have also added additional experimental results.
Decision: Accept (Poster)