Efficient Training of Retrieval Models using Negative Cache
Authors: Erik Lindgren
Sashank J. Reddi
Ruiqi Guo
Sanjiv Kumar
Venue: NeurIPS 2021 Poster (2021)
Keywords: dual encoders
extreme classification
negative sampling
recommender systems

Abstract: Factorized models, such as two tower neural network models, are widely used for scoring (query, document) pairs in information retrieval tasks. These models are typically trained by optimizing the model parameters to score relevant ``positive" pairs higher than the irrelevant ``negative" ones. While a large set of negatives typically improves the model performance, limited computation and memory budgets place constraints on the number of negatives used during training. In this paper, we develop a novel negative sampling technique for accelerating training with softmax cross-entropy loss. By using cached (possibly stale) item embeddings, our technique enables training with a large pool of negatives with reduced memory and computation. We also develop a streaming variant of our algorithm geared towards very large datasets. Furthermore, we establish a theoretical basis for our approach by showing that updating a very small fraction of the cache at each iteration can still ensure fast convergence. Finally, we experimentally validate our approach and show that it is efficient and compares favorably with more complex, state-of-the-art approaches.

Efficient Training of Retrieval Models Using Negative Cache
Erik M. Lindgren Google Research, New York eri grikm@@google.com
Sashank Reddi Google Research, New York sashank@google, com
Ruiqi Guo
Sanjiv Kumar Google Research, New York sanjivkégoogle. com
Google Research, New York guorq8google.coo com
Abstract
Factorized models, such tower neural network models, are widely used for scoring (query, document) pairs in information retrieval tasks. These models are typically trained by optimizing the model parameters to score relevant "positive" pairs higher than the irrelevant "negative" ones. While a large set of negatives typically improves the model performance, limited computation and memory budgets place constraints on the number of negatives used during training. In this paper, we develop novel negative sampling technique for accelerating training with softmax cross-entropy loss. By using cached (possibly stale) item embeddings, our technique enables training with a large pool negatives with reduced memory and computation. We also develop streaming variant of our algorithm geared towards very large datasets. Furthermore, we establish theoretical basis for our approach by showing that updating very small fraction of the cache each iteration can still ensure fast convergence. Finally, we experimentally validate our approach and show that it is efficient and compares favorably with more complex, tate-offthe-an art approaches.
Introduction
Learning to represent objects as dense vectors, often called embeddings, has proved to be crucial in large scale information retrieval tasks from multiple domains including recommendation systems [39], vision [18] and natural language processing [13, 22]. A popular paradigm for such learning tasks involves training two separate neural networks (often called two-towers dual-encoders), each representing query and a document. Given positive and negative (query, document) pairs, the learning task trains the two networks by minimizing loss function, usually softmax cross-entropy, to encourage positive pairs to have higher similarity scores and negative pairs to have lower scores. While it is easy sample positive pairs of examples through user feedback such impressions or clicks, it more challenging to sample good negative pairs from a pool of potentially millions or even billions of documents. large number of negative pairs is often required to ensure high quality of the final model, which makes the training process expensive.
A number of strategies have been proposed in the literature address the problem of sampling good negative pairs from a large corpus. The most common approach to use in-batch negatives, which treats random, non-positive pairs in minibatch negatives [15, 22]. This approach is computationally efficient and works in a streaming setting, but the pool negative examples is limited to the minibatch. Towards the later stages of the training, the in-batch negatives become less informative (i.e., have low gradients) since they are sampled randomly without paying attention
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

to which negatives are hard for given query [22]. Another popular approach is to maintain an asynchronous retrieval index of the full dataser for negative sampling [13, 38]. Negatives from the full dataset can be extracted based on approximate retrieval techniques such as ScaNN [11], Faiss [20] or SPTAG [7]. However, it requires coordinating with separate process for re-indexing and re-building the retrieval index, which is not only computationally expensive and hard to maintain but also suffers from the problem of stale index.
In this work, we theoretically and experimentally analyze training dual encoders using large cache of negative elements. The cached elements are stale, as they may generated from prior iteration's parameters. Our contributions are the following.
Main Contributions:
We propose approach to train retrieval models with cross-entropy loss using a large negative cache. We utilize Gumbel-Mar sampling on the cached embeddings to efficiently sample the negatives.
We analyze the convergence of our algorithm in terms of the refresh rate of the cache. We show that even for small refresh rate we can obtain first-order convergence rate comparable to that of getting exact gradients using the entire dataset.
We develop a streaming version of our approach. Our streaming algorithm allows us to scale to very large datasets and avoids needing to maintain an up-to-date index for nearest neighbor search (or maximum inner product search). We analyze the bias induced by our method and how it affects the convergence.
We experimentally validate our method using the MS MARCO and TREC 2019 passage retrieval tasks. We show that approach can be efficiently implemented and achieves statistical performance comparable to state-of-the-ar benchmarks with a computationally simpler approach that requires only fraction of the memory.
2 Background
2.1 Dual Encoders
Given query 4, our goal is to match the query with the most relevant documents. The set of docu- ments is represented by D = {21, 22....: ]m} E Rdo, where m is the total number of documents. While we refer to them documents in this paper, they can be any set of items that we wish to retrieve e.g. movies or products.
The training data consists of n positive (query, doc) pairs T = {(1, V1). (g2, U2).... (gn, Vr.) } where is a feature vector in Rdd and the label is an integer in [mm]. which indicates a relevant document for query qt. Our goal is to learn a dual encoder model [6] for embedding the queries and documents. Formally, a dual encoder consists of two components:
1. Query encoder ΦQ RRde b IRd which maps a query to a d-dimensional embedding space.
2. Document encoder ΦD Rdo + Rd, which maps a document to the embedding space.
The score for particular query, document pair is simply computed as inner product of the corre- sponding query and document embeddings i.c., s(g, 2) (Q(9) (z)2,, Intuitively, this represents the "similarity" between the query and documents in the embedding space. The model is trained such that the relevant query, document pairs have high scores. Dual encoders are popular in large scale settings since they are highly efficient during training and inference as the high scoring items for given query can be found using efficient nearest neighbors algorithms, often achieving more than 100x speed up over brute force search [10].
2.2 Training Dual Encoders with Cross-Entropy Loss
In this paper, we focus on the popular cross-entropy loss for training dual encoders. Even though these loss functions have been found to be highly effective, the main challenge in large scale settings

---

is computational. To observe the computational bottleneck, we look at the cross-entropy loss:
exp(3siv.)
LOE, (0) = - log
(I)
TT +==1 exp((880s)
where 3 is the inverse temperature that scales the scores. Here, Stj Sty oo 0) (2 0) and 0 IRP, This computation involves computing the scores for all documents, which can be prohibitively expensive when the number of documents m is large. For simplicity, throughout this paper, we will assume that the embeddings have unit bounded norms, i.e., l (::6)ll S and (- 0) S 1 for all 0 E RR. Note that this can be assumed without a loss in generality since one can adjust the inverse temperature 3 accordingly to compensate for the scale.
On large-scale datasets, it may not be possible to have the entire dataset in memory, especially with large embedding models where need the activations of the intermediate layers persist for hack-propagation.. An alternative approach is to first select a sample of documents and use them to approximate the partition function. We thus have the following loss function:
exp(38igg)
CSAMPLE CE, (0) 15--log loo
(2)
Ejes exp(Bsjus)
It has been observed that using a larger set of negative samples leads to better performance [16]. A simple approach to uniformly sample this set from DD (popularly referred as negative sampling). However, when m. is large, negative sampling is typically inefficient since it is difficult to obtain high-scoring irrelevant documents, thereby, providing a poor approximation of the cross-entropy loss. In the following sections, we explore highly scalable solutions for optimizing cross-entropy loss.
Random sampling often implemented using in-batch negative sampling [15, 22, 16]. However, this approach is not scalable because huge amount of accelerator memory is required to achieve a bigger pool of in- i--btch negatives. For example, BERT [9] based transformers are typically used in NLP tasks but single pair of (query, document) BERT- base consumes 600MB of accelerator memory during training. This further limits the effectiveness of random negative sampling.
2.3 Related Work
There have been many recent papers on using cached embeddings and nearest neighbors for improving negative mining during training. Several works consider caching embeddings for the entire dataset [13, 38). They utilize a separate task to recompute embeddings based on the current parameters and recreate an index of nearest neighbor search. This can be computationally challenging for very large datasets, the cost of inference and index refresh scales linearly with the number of documents.
REALM [13] uses their embedding cache to optimize softmax-cros entropy loss. They approximate the partition function by retrieving the k largest scoring elements. This can a poor approximation if the distribution is not highly concentrated around the top clements. Additionally, it requires O(k) additional memory to perform backpropagation. ANCE [38] uses their cache to optimize a negative contrastive loss. MoCo [14] uses streaming negative cache to increase the number of negative examples for feature embedding tasks. But it cannot be extended to dual encoder training, as the document encoder does not contribute to gradient updates.
Negative sampling is also widely used in classification problem with very large number of labels, where each document is considered separate class. This setting is simpler than the dual encoder setting, since the model consists one encoder and one large classification layer. The weights the classification layer are only updated when their corresponding labels are included in a gradient step. In contrast, in the dual encoder setting, all document embeddings are changed during a gradient step.
For training with a softmax cross-entrops loss in the classification setting, Bengio and Senécal [4] develop an importance sampling approach for estimating the gradient of the cross-entropy loss function in large output spaces. Many following works utilize sampling techniques for estimating the gradient [17, 36, 30, 27, 25, 2]. Rawat et al. [30] analyzes the bias of different sampling techniques in gradient estimation. Mussmann et al. [28] use Gumbel-Max sampling to sample from the softmax
distribution and accelerate gradient descent for certain problems. Zhang al. [42] analyze the bias between gradients of the softmax loss and gradients generated from using hard negative mining. Other loss functions besides softmax cross-entropy include noise contrastive estimation, which was developed by [12] and utilized in [26, 25], ordered weighted losses [3 I], and triplet losses [33].
3

---

Hard and semi-hane negative mining is collection of techniques for selecting negatives that the
model scoring above or near positive elements. Works in this area include [34, 37]. particular,
Dense Passage Retrieval [22] utilizes hard negatives generated by BM25 ranker [32]. We note that
hard negatives such as BM25 are often domain-specific and require finding a hard negative document
for each query, which can be expensive with a large number of queries and documents.
We note that there are several approaches that take dense retrieval model and use its retrieval results to improve performance further. The LTRe method [41] and the STAR and ADORE method [40] uses the retrieval results of ANCE to further improve performance with a ranking loss function. The RocketQA method [29] starts by training a model with sample negatives (in the cross-batch setting when training with multiple accelerators). This model is used generate negatives for a cross-attention model, which is used to denoise the dataset to train an improved dense retriveal model. We compare to their Stepl model in the experimental section.
Our setting consists of learning from observed click data, thus we only see positive pairs. In the related learning-to-ran setting, the goal is learn a ranking model using a set of positive and negative relevance labels. Works in this setting include [19, 5,
3 Full Document Cache
The primary objective is find the parameters 9 that minimize the softmax cross-entropy loss CCE(O) (Equation 1). The standard algorithm to optimize the loss is stochastic gradient descent (or its variants). However, calculating stochastic gradients for this loss function is expensive in terms of both time and memory. Computation of the gradient involves: (1) forward pass on every document in our dataset, (2) storing all intermediate activations (which are needed for the backward pass), and (3) calculating the gradients in the backward pass. Unfortunately, for large embedding encoder models such as those based on Transformers ([35)), this is prohibitively expensive. For instance, for a large BERT model on million documents, the required memory would be hundreds of terabytes.
We propose an approach that can approximate the gradient of cross-entropy loss without needing to embed every document, thereby reducing the per-iteration computation and memory requirements for gradient computation. Our approach based on cached embeddings [13, 38]. To understand our approach, we first start with gradient estimation with Gumbel- sampling. The following known fact shows that if we can sample from the softmax distribution then we can get an unbiased estimate of the stochastic gradient.
Fact 1. The gradient of the cross-entropy has the following form:
VCEE -VV
Pty V Sijs
j=1
where LCF; loo
exp((8sin) Σye exp()s.s)
and Pij Ey' exp(Da.,7)
exp(Ba,,
J is a sample from pt (pe), Diaii,Pi2..... ...,...,,,,............... ,Pmm). we have V VLRF = 3V + 33((( sir):
Further, if N1, ........ Nm are i.i.d. standard Gumbel random variables, then the index arg ma Bsig N, is a sample from the distribution p. (p11, Pi........... .Pmm).
We refer to this approach as Gumbel-Max sampling and GumbelMaaxSamlel(35
used to represent this sampling procedure. A natural estimator of the gradient is VLEE = - VV + V88 where is the index [m] obtained through Gumbel-Max sampling. Due to the feasibility of fast maximum inner product search (MIPS). Gumbel-Max sampling is an efficient way to sample from the softmax distribution; this, thereby, provides an efficient way to obtain an unbiased estimate of the gradient. In particular, the per-iteration memory requirement is reduced from ((m)) to 0(md) where and d are the model and embedding sizes respectively. This is due to the fact that the intermediate activations need to be stored only for documents y/ and J, the negative obtained through Gumbel-N sampling. When d & r (which is typically the case while using large transformer models), this leads to significant reduction in memory requirements. While the memory requirements are reduced drastically, we still need to do a forward pass on all documents to compute the scores 8ij- Using Fact I. we would need to embed every document every iteration, which is still computationally intensive.

---

Algorithm Cached Gumbel-Max Gradient Descent
Input: Learning rate v), Document refresh fraction p E (0,
Initialize parameters Op- Initialize embeddings table E: & < (D(Zzzi))) 0n) for all j E [m]]
for t E 0.1..... T do
Sample qs. Y1 from the training set
Eg. - (9: 8,)
6xy, < @D((z 0x) and update Ey, = Czy;
Calculate scores 8ij f- Eq. &j for all j E [m]
J + GumbelMaxSamplee(S5.
Ez₁ f ΦD(21; 0.)
8tJ < Eq, E2J
9t + - Siy + SVs
B1+1 + 0, - n9t
Select oldest pm embeddings of & and update them to Eg + 0D(2zi00+1)
end for
This motivates an algorithm where we cache previously calculated embeddings efficiently approxi- mate the softmax distribution Pt- We first note the structure of the 8ig ( 0)) (zy; 0). The key computational challenge in Gumbel-Max sampling is computation of the embeddings (zy; 0) for all j E [m]. This is required to find the index J in Fact 1, which essentially renders it com- putationally intractable for large m. Our approach to compute embeddings (z 0) for only a few documents j E [m] at each iteration and reuse the previously computed embeddings for the rest of the documents.
particular, let 2, = (2y; ; f) be the current embedding of a document and ž = (zz; 0) be its previous embedding. If 0 and 0 are reasonably close, then 2j and ž would be similar. In such scenario, the scores 8ij and Sij, and, thereby the corresponding distri- butions pj = (pi1. Pi2, P... and Pú = P.a............... Vi + 1 and the approximation to the gradient -9V8 Σド= VV should be similar. Note that for the approximation we take the gradient of Siy and not S.y: we only replace the weight terms Piş with P.j-
are also similar. As consequence,
the true gradient VLCEs
We described this algorithm in Algorithm 1.
We present the algorithm with a batch size of 1-it can be easily extended to larger batches. We maintain an embedding table of all documents. At each iteration, we update only small fraction of the stale embeddings to ensure that pe and fJ: are similar. Using this approach, can approximately sample from this distribution using Gumbel-Max sampling in an efficient manner.
3.1 Theoretical Results
In this section, establish error guarantees the error of our Cached Gumbel-Max gradient approximation. Before delving into the technical details, we state the following key assumptions on the query and document encoder.
Assumption 1. The following conditions hold for the query &Q and document encoder Φn:
Al The query and document encoder functions are both L-Lipschitz in the parameters 8. In particular, have (óqq; f)) Ø(q,: 8')l12 I L|0 - 0' for all E [n]] and [|ó((,;
o(2;; 8')1l2 - L|le 6' 2'122foz all E [m].
A2 The query and document embeddings are bounded i.e,, we have Eg, eg = (0(g;0), (z(=;) satisfy ||cyl12: ||ez||2 1.
A3 The score functions have bounded gradients i.e., we have V|V S M for all e [m] and j E [m].
All of these assumptions are fairly mild and are common in optimization literature. As noted earlier, the second assumption does not lead to much loss of generality as larger bound on the norm can be absorbed into the inverse temperature parameter 3. the following result, we first show that the error can be bounded by the foc error between the true scores and the scores with the cached embeddings.
5

---

We then show that if the cached embeddings are generated from Algorithm with learning rate ny and refresh rate p. we can bound the gradient error at each iteration.
Theorem 2. Let Or and index i be the parameters and training point selected at t iteration of Algorithm I, respectively. Let represent the Gumbel- Max index selected at that iteration. Then, under Assumption 1, we have the following grudient approximation with the cuched embeddings
V LCF, (0x) -ssla] = -V8 +
Pij V
and 6ij = Cq. Ej. Furthermore, we have the following bound on the gradient approximation of V (f.):
exp() where Pij Σy= (x)(
[VCCE,(0)) - v LCE, (0e)ll2 S M||3 8:l100-
When parameter updates are generated by Algorithm with step size n and update rate p. we have
[V,,,,(0)) VLCE. (0.) S LM² (1-1).
We that the norm. This provides a bound on the bias in the gradient approximation. Using the above result, show the following first-order convergence guarantees. For proving convergence, need the following additional assumption.
be controlled by either increasing the refresh rate or decreasing the gradient
Assumption 2. We assume loss function LCE, is S-smooth i.e., we have VV (0) LCE,, (6')
2 S 0 1l12 holds for all 0, 0' E Rp and i E [n].
Under the above assumption, have the following convergence result in general non-convex settings.
Theorem 3. Suppose we run Algoritlum I for T iterations with stepsize rj = v -
V2TSM
Then under Assumption and 2, we have the following:
T ([ < 4MV S(CCe(0)) LCe(O*)) 43 L3 LCE(O*))
(1 p (1-1)
T
ST
We have that 22 + log m S LCE(O) S 23 log m. Thus the term (CE(On) - LCE(O") < 48.
We observe that the bias introduced due to stale embeddings is a lower order term in the bound of Theorem 3. particular, one can use p 147-/ without affecting the convergence rate of the standard SGD algorithm. For large T (which typical machine learning settings), this can have a sigmificant impact on the computational complexity since a very small fraction of the documents need be updated each iteration.
3.2
Computational Discussion
We store our cache using accelerator memory. This prevents the need to have a separate task that constantly reindexes the embeddings they change throughout training. This is feasible for moderate size datasets. For instance, million training points with an embedding dimension of 512 and feature vector dimension of 1024 will about GB memory, which fit on single accelerator. To calculate the perturbed nearest neighbor for Gumbel-Max sampling, we simply brute force calculate the largest dot product. Accelerators such GPUs and TPUs can do this very efficiently-in our experiments we see that the steps/second increases only small amount as we increase the cache size. This is because the cost computing the embeddings is much larger than the cost of doing the search due to the complexity of large transformer models.
If faster sampling is needed, it can be accelerated by using fast nearest neighbor search. Mussman al. [28] consider an approach that applies Gumbel perturbations to the highest scoring elements plus small number of random elements to perform Gumbei-Max sampling in sublinear time.
However, having the cache on an accelerator has limitations due to the accelerator memory limits. In the next section, we modify Algorithm I to be streaming algorithm.

---

3.3 Conditional Sampling Negatives
Note that Gumbel-Max sampling has a chance sample the positive element. If this happens, then our gradient approximation is zero. Since we are training our model to make the score of the positive element large, this can happen often. We develop an approach force the sampled element to be negative element while maintaining a similar expected gradient.
Assume that the positive element is 21 and the negative elements 22, 23, : Zm- We have that
V VCEE: VV
Pij Vus - Va) + +(1 Pai) Σ
Pij V
Ps1
Note that ( (I-pa 1-D+1"
Pia
Pin is the conditional distribution where we condition on not sam- Ps1
pling the first element. Thus we can sample from the conditional distribution as long as we properly scale the gradient by - Pat. We note that the value pi depends on the negative embeddings. Since we have all the negatives our accelerator, we can also calculate the partition function without much additional compute, as has the same complexity as of our nearest neighbor search.
Streaming Cache
For very large datasets, the Gumbel-Mai sampling step can become difficult. If the embedding vectors are stored accelerator memory, then only finite number of vectors can be stored on fixed computational budget. If the vectors are stored in CPU memory with CPU-based retrieval system, then the nearest neighbor index needs to be constantly recreated, which computationally expensive for large datasets. Additionally, we see in Theorem 2 that as the fraction of elements refreshed each iteration decreases, then the learning rate needs to decrease as well to maintain a given bias in gradient estimation. Alternatively, more embeddings will need to be refreshed each iteration as the size of the dataset grows.
To address this issue, we develop streaming variant of our algorithm. The key difference with respect the full dataset setting is that instead of storing all the document embeddings in memory, we only store sample multiset S of size om.. After every iteration we remove the oldest pamm elements S and replace them with porm new elements sampled uniform i.i.d. from the dataset. The fraction can be tuned to fit given computational budget.
Our gradient estimator approximates gradients from cache cross-entropy loss. We define the cache cross-entropy loss to be the following:
exp(3sy.) LCacheCEa log exp(3stp)) a Ejes.ith. exp((siy)
Following [4], we scale the weight of the negative elements by L. otherwise the partition function would underestimate the true partition function. Thus is equivalent to shifting the scores of the negative elements by log 1.
The use of the cache cross-entropy loss LCacheCE instead of the true cross entropy loss induces bias in gradient estimation. We are able to show that the bias scales inversely with the cache size. The proof of Lemma 4 is modification of the proof of Theorem in [30].
Lemma 4, Assume Assumptions A2 and A3 hold, i.e., that the norm of the encoder embeddings is bounded by 1 and the norm of the gradients of the scores is bounded by M.
We have that
exp(O(3))M
LCE E [CacheeCE)
cem
where the expectation is taken over the randommess of the elements in the cache.
In Algorithm 2
present Algorithm for training with the streaming cache. We use GumbelMaxSanplo((B, S) to denote the Gumbel-Max sampling described Fact 1 with scores restricted documents in set S.
There are two sources of bias in our gradient estimate: first due to the staleness of the cache and the second due to using sampled set of negatives rather than the entire dataset. We handle the latter in
7

---

Algorithm 2 Streaming Cached Gumbel-Max Gradient Descent
Input:
Learning rate y), Cache fraction (0, 11, Document refresh fraction (0,
Initializes parameters Bu-
Random sample - [m]om
Initialize embeddings table E: E, t (D(zg 0b) for all j E S fort t
..,...., T
do
Sample 45. Vi from the training set
eg; -- (9: 0x)
Ezy, < @ (z) and update Ey. Czy;
Calculate scores Bij Eq. Ej + (log(1/)/// for all j E S and Big. En: Ezus
+ S with all instances of y, removed
- GumbellaaxSamplee(B..
εz t Eq. -Zz
ΦD(2);;1
Py. + probability of y: under softmax($;)
t 3(1 - Ps. (-V)) + VstJ)
0(+1 - -, 10--99 79t
Select oldest pam embeddings set O of & and remove them from &
Sample S' [ [m]. |S'| pam
Update E - Φn 11) for j S'
Update set S + S OUS'
end for
Lemma For the former, note that our error guarantees in Theorem still apply the streaming cache, as we can bound the error between true gradient using this set of negatives with our gradient approximation. This allows us bound the bias due to the staleness of the cache.
Since we were able to control the bias of our gradient estimator even with the streaming cache, we establish first order convergence theorem for training with Algorithm 2.
Theorem 5. Assume that Assumptions 1 and 2 hold and
learning rate n VEee(Oo) CoE Running Algorithm 2 with a cache of size om with a refresh rate p creates V2TSM updates 12.0.... Or such that
T
+ (
1 T
(O)))1B So
VT
a2m²
where we omit terms that depend on S, L, M, and B.
the cache size satisfies om 2 T1/4, then we do not asymptotically affect the rate of convergence.
We see that using a streaming cache smaller than the entire dataset adds only a small amount of bias in convergence and reduces the computational burden of storing embeddings and calculating nearest. neighbors significantly.
5
Experiments
We analyse the performance of our approach on the MS MARCO passage retrieval task [3] and the TREC 2019 passage retrieval task [8]. Both tasks utilize the same dataset consisting of 500,000 (query, passage) pairs and 8.8 million passages the database. MS MARCO measures reciprocal rank at 10MRR @ 10) with holdout set of query, passage pairs. TREC 2019 measures the normalized discounted cumulative gains (NDCG @ 10) compared relevance scores.
mean
of human labeled

---

Method
Batch Size
Negatives
Updates/Step
Memory/Step
Steps/Sec
Sample Cross-Entropy
8
16
I0G
9.95
Sample Cross-Entropy
8
64
25G
4.64
Sample Gross-Entrops
8
256
87G (OOM)
1.43 (est.)
Cached Negative
8
8k
256
15G
3.38
Cached Negative
8
32k
256
15G
3.38
Cached Negative
8
128k
256
16G
3.37
Cached Negative
8
512k
256
19G
3.32
Cached Negative
8
2M
512
38G
2.04
Full Dataset Cache
8
8.8M
512
90G (OOM)
Table 1: Runtime and resource consumption for various configurations of cache sizes and number of
random negatives. Since sample cross-entropy doesn't 't fit in memory we estimate the steps/second with linear interpolation.
5.1 MSMARCO / TREC Experimental Set Up
Following related work [22, 38], we start with pretrained BERT-base model [9] Both our query and document encoder are initialized with this model and share parameters during training. We add fully connected layer to the end of the encoder that projects to 512 dimensions. We do no additional pre-training. We use global batch size of 8, the Adam optimizer [23], and we train for 250, 000 steps. We normalize the output embeddings and have trainable parameter 3 scale the scores. We use learning rate of 10-5 for all experiments except when we train with a cache of million elements, where we use learning rate of 5 x 10-5, This is due to the increased staleness of the large cache. Our experiments use 8 V2 Cloud TPUs. Each replica on the TPU has 8GB memory, for total of 64GB memory.
5.2 MSMARCO / TREC Computational Performance
We first examine the computational performance of our method. Since we use brute force to calculate the negative with the highest perturbed score, we are interested in seeing how this affects the runtime performance of our algorithm. Randomly sampled passages are used as negatives for sample cross-entropy and the updates for the negative cache.
Due to the increased staleness of large caches, we do 512 updates when using a cache with million elements. For all other cache sizes we use 256 elements.
We see Table that the cache size can scale to hundreds of thousands of elements with minimal effect the speed of training. The cost of calculating embeddings and gradients with large trans- former models is significantly more expensive than the cost of the nearest neighbor search, even use brute force approach.
Further, we see that using a cache with 2 million elements requires less memory than using just 256 sample negatives, even when 512 elements are updated every iteration. This is because the memory required for the backward step about 10x larger than the memory needed for the forward step.
Additionally, we see that there is limit to the cache size. If we were to use all 8.8M negatives, we would not be able to fit them on V2 Cloud TPUs and would have move to a separate nearest neighbor system. Our streaming approach allows us to adapt the cache size to the available memory.
5.3 MSMARCO / TREC Experimental Results
We now analyze the statistical improvement of using a large negative cache. In Table 2 we present the output MRR @ 10 on the development set of MS MARCO passage retrieval task and NDCG@ 10 on the TREC 2019 passage retrieval task for training with stochastic negative mining, our negative cache approach, as well as two external benchmarks, ANCE [38] and DPR [22].
We see that our streaming cache method achieves similar statistical performance to ANCE without needing to store and search all elements in the dataset. Additionally we see that outperforms all
Model obtained from https::/ //tp/ub.///b....//////e httpaa/.deeereoooooooooooottt.tt oawp:////eerrttoooncceeeeeeedddd uncased L-12_ 1-__H_768__5
L-1___1-688 1177_66882216 4-24/

---

Method
MS MARCO (MRR @ 10)
TREC (NDCG@@) 10)
Sample Cross-Entropy (16 negatives)
0.235
0,493
Sample Cross-Entropy (64 negatives)
0.257
0.513
Sample Cross Eooss-Ey (256 negatives)
0.273
0.538
Negative Cache (8k negatives)
0.310
0.600
Negative Cache (32k negatives)
0.315
0.630
Negative Cache ( (128k negatives)
0,323
0.633
Negative Cache (512k negatives)
0.322
0.649
Negative Cache (2M negatives)
0.331
0.630
ANCE (NCE with 8M negatives) [38]
0.330
0.648
DPR (Random + BM25 Negative) [22]
0.311
0.600
RockerQA Stepl BERT-base [29]
0.327
Table 2: Statistical performance of stochastic negative mining, negative cache training, and related
dual encoder training benchmarks for the MSMARCO and TREC task. Values for DPR were obtained
from [38].
Method
Recall @20
Recall @ 100
Cache (2M negatives)
0.784
0.856
ANCE (NCE with 20M negatives) [38]
0.819
0,875
DPR (Random + BM25 Negative) [22]
0.784
0.854
RocketQA Step1 BERT-base [29]
0.860
Table 3: Statistical performance of negative cache training and related dual encoder training bench-
marks for the Natural Question task.
sample cross-entropy approaches with smaller memory footprint. Further, we see that our approach outperform the BM25 negatives utilized by DPR.
5.4 Natural Question Experimental Results
We now experimentally compare our method on the Natural Question dataset [24]. We follow the methodology used by [22]. The goal of the experiment
learn a model that matches questions with passages that contain the answer to the question. The dataset consists of about 60,000 query, positive passage pairs and there are about 20 million passages. In evaluation, we consider retrieved passage a positive if it contains an exact match to one of the labeled answers to the given question.
In Table compare training with negative cache with 2 million negatives to several state-of -tte-----e------ art dual encoder training methods. We see that training with a negative cache compares favorably with DPR without the of domain-specifie hard negative mining techniques such BM25. The use of such a techniques requires an inference step to find the hard negative among all passages, which be expensive for large datasets. Additionally we note that ANCE is initialized with the DPR model and we use only 10% of the negatives in our cache.
6 Conclusion
In this paper we developed an algorithm for efficiently estimating gradients for dual encoder models with softmax cross-entropy loss function. We see that we can efficiently obtain gradient estimations with low bias with an appropriately chosen learning rate and sufficiently large negative cache. We analyze first order convergence training with a streaming negative cache and establish near- optimal convergence bounds compared to SGD for reasonable parameter choices. In dense retrieval experiments we see that our approach is efficient and can compare favorably to state-of-ther dual encoder training methods.
References
[1] Shivani Agarwal. The infinite push: new support vector ranking algorithm that directly optimizes accuracy the absolute top of the list. In Proceedings of the 2011 SIAM International
10

---

Conference on Data Mining, pages 839-850. SIAM, 2011.
[2] Yu Bai, Sally Goldman, and Li Zhang. Tapas: Two-pass approximate adaptive sampling for softmax. arXiv preprint arXiv: 7700003773 2017.
[3] Payal Bajaj, Daniel Campos, Nick Craswell, Li Deng, Jianfeng Gao, Xiaodong Liu, Rangan Majumder, Andrew McNamara, Bhaskar Mitra, Tri Nguyen, et al. Ms marco: A human generated machine reading comprehension dataset. arXiv preprint
(tV::6611.0266 2016.
[4] Yoshua Bengio and Jean Sébastinn Senécal. Adaptive importance sampling to accelerate training of neural probabilistic language model. IEEE Transactions on Neural Networks, 19(4):13-722, 2008.
[5] Stephen Boyd, Corinna Cortes, Mehryar Mohri, and Ana Radovanovic. Accuracy at the top. 2012.
[6] Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. Signature verification using a" siamese" time delay neural network. Advances in neural information processing systems, 6:737-744, 1993.
[7] Qi Chen, Haidong Wang, Mingqin Li, Gang Ren, Scarlett Li, Jeffery Zhu, Jason Li, Chuanjie Liu, Lintao Zhang, and Jingdong Wang. SPTAG: A library for fast approximate nearest neighbor search, 2018.
[8] Nick Craswell, Bhaskar Mitra, Emine Yilmaz, Daniel Campos, and Ellen M Voorhees. Overview of the tree 2019 deep learning track. arXiv preprint arXiv:2003.07820, 2020.
[9] Jacob Devlin, Ming-Wor Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv: 1810.0880 2018.
[10] Daniel Gillick, Sayali Kulkarni, Larry Lansing, Alessandro Presta, Jason Baldridge, Fugene le, and Diego Garcia-Olano. Learning dense representations for entity retrieval. In Proceedings of the 23rd Conference on Computational Natural Language Learning (CoNLL), November 2019.
[11] Ruiqi Guo, Philip Sun, Erik Lindgren, Quan Geng, David Simcha, Felix Chern, and Sanjiv Kumar. Accelerating large-scale inference with anisotropic vector quantization. In International Conference on Machine Learning, pages 3887-3896 PMLR, 2020.
[12] Michael U Gutmann and Aapo Hyvärinen. Noise-contrastive estimation of unnormalized statistical models, with applications to natural image statistics. Journal of Machine Learning Research, 13(2), 2012.
[13] Kelvin Guu, Kenton Lee, Zora Tung, Panupong Pasupat, and Ming-Wei Chang. Realm: Retrieval-augmenttd language model pre-training. arXiv preprini arXiv:2002.0890 2020.
[14] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages
2020.
[15] Matthew Henderson, Rami Al-Rfou, Brian Strope, Yun-Hsuan Sung, László Lukács, Ruiqi Guo, Sanjiv Kumar, Balint Miklos, and Ray Kurzweil. Efficient natural language response suggestion for smart reply. arXiv preprint arXivv1705.000 2017.
[16] 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 International Conference Learning Representations, 2020.
[17] Sébastien Jean, Kyunghyun Cho, Roland Memisevic, and Yoshua Bengio. On using very large target vocabulary for neural machine translation. arXiv preprint arXiv:1412.200 2014.
[18] Chao Jia, Yinfei Yang, Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoe V Le, Yunhsuan Sung, Zhen Li, and Tom Duerig. Scaling up visual and lasion-language representation learning with noisy text supervision. arXiv preprint arXiv:2102.05918, 2021.
11

---

[19] Thorsten Joachims. A support vector method for multivariate performance measures. In Proceedings of the 22nd international conference on Machine learning, pages 377-384, 2005.
[20] Jeff Johnson, Mathhijs Douze, and Hervé Jégou. Billion-scale similarity search with gpus. IEEE Transactions on Big Data, 2019.
[21] Purushottam Kar, Harikrishna Narasimhan, and Prateck Jain. Surrogate functions for maximiz- ing precision at the top. In International Conference Machine Learning, pages 189-198. PMLR, 2015.
[22] Vladimir Karpukhin, Barlas Oguz, Sewon Min, Patrick S. H. Lewis, 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, 2020.
[23] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6988, 2014.
[24] Tom Kwiatkowski, Jennimaria Palomaki, Olivia Redfield, Michael Collins, Ankur Parikh, Chris Alberti, Danielle Epstein, Illia Polosukhin, Matthew Kelcey, Jacob Devlin, Kenton Lee, Kristina N. Toutanova, Llion Jones, Ming-Wat Chang, Andrew Dai, Jakob Uszkoreit, Quoc Le, and Slav Petrov. Natural questions: a benchmark for question answering research. Transactions of the Association of Computational Linguisties, 2019.
[25] Tomas Mikolov, Hya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality. arXiv preprint arXiv: 13101114444444 10.4546, 2013.
[26] Andriy Mnih and Yee Whye Teh. A fast and simple algorithm for training neural probabilistic language models. arXiv preprint arXiv:1206 6426, 2012.
[27] Frederic Morin and Yoshua Bengio. Hierarchical probabilistic neural network language model. In Aistats, volume 5, pages 246 252.. Citeseer, 2005.
[28] Stephen Mussmann, Daniel Levy, and Stefano Ermon. Fast amortized inference and learn- ing in log- linear models with randomly perturbed nearest neighbor search. arXiv preprint arXiv:1707.0333
2017.
[29] Yingqi Qu, Yuchen Ding, Jing Liu, Kai Liu, Ruiyang Ren, Wayne Xin Zhao, Daxiang Dong, Hua Wu, and Haifeng Wang. Rocketqa: An optimized training approach dense passage retrieval for open-domain question answering. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, pages 5835-5847, 2021.
[30] Ankit Singh Rawat, Jiecao Chen, Felix Yu, Ananda Theertha Suresh, and Sanjiv Kumar. Sampled softmax with random fourier features. arXiv preprint arXiv:1907.10744 2019.
[31] Sashank J Reddi, Satyen Kale, Felix Yu, Daniel Holtmann-Riin Jiecao Chen, and Sanjiv Kumar. Stochastic negative mining for learning with large output spaces. In The 22nd International Conference Artificial Intelligence and Statistics, pages 1940-1949. PMLR, 2019.
[32] Stephen Robertson and Hugo Zaragoza. The probabilistic relevance framework: BM25 and beyond. Now Publishers Inc, 2009.
[33] Florian Schroff, Dmitry Kalenichenko, and James Philbin. Facenet: A unified embedding for face recognition and clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 815-823, 2015.
[34] Abhinay Shrivastava, Abhinav Gupta, and Ross Girshick. Training bagiod-based object detectors with online hard example mining. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 761-769, 2016.
[35] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. arXiv preprint arXiv: 1706 03762, 2017.
12

---

[36] Sudheendra Vijaaanarasimhan, Jonathon Shlens, Rajat Monga, and Jay Yagnik. Deep networks with large output spaces. arXiv preprint arXiv:1412.74777 2014.
[37] Chao- Yuan Wu, R Manmatha, Alexander Smola, and Philipp Krahenbuhl. Sampling matters in deep embedding learning. In Proceedings of the IEEE International Conference Computer Vision, pages 9840-2848, 2017.
[38] Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul Bennett, Junaid Ahmed, and Arnold Overwijk. Approximate nearest neighbor negative contrastive learning for dense text retrieval. In International Conference on Learning Representations (ICLR), April 2021.
[39] Xinyang Yi, Ji Yang, Lichan Hong, Derek Zhiyuan Cheng, Lukasz Heldt, Aditee Ajit Kumthekar, Zhe Zhao, Li Wei, and Ed Chi, editors. Sampling-Biee Biiaiinng--i--i-ee Baia--Carrreteeee Neural Modeling for Large Corpus Item Recommendations, 2019.
[40] Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Jiafeng Guo, Min Zhang, and Shaoping Ma. Optimizing dense retrieval model training with hard negatives. arXiv preprint arXiv:2 0805 2021.
[41] Jingtao Zhan, Jiaxin Mao, Yiqun Liu, Min Zhang, and Shaoping Ma. Learning to retrieve: How to train dense retrieval model effectively and efficiently, arXiv preprint arX1v:2010.10469, 2020.
[42] Wenzheng Zhang and Karl Stratos. Understanding hard negatives in noise contrastive estimation. arXiv preprint arXiv: 104.02204,00245, 2021.
13


Reviews:
[{"review_id": "p4xbWFMRM7r", "reviewer": "Reviewer_bG1r", "summary": "This paper addresses the technique of negative sampling in IR tasks. The author proposes to utilize Gumbel-Max sampling on the cached embeddings to efficiently sample the negatives. For a very large dataset, the paper develops a streaming variant of the algorithm. The author also conducts some theoretical analysis to demonstrate its convergence and bias. Moreover, the experimental results show its efficiency.", "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": "- Originality - The idea of using cached embeddings and nearest neighbors for improving negative mining is recent but not completely new. Previous works are REALM [1] and ANCE [2]. Both articles are acknowledged by authors in this paper. The main contribution of this work concerning previous works is the use of Gumbel-Max sampling to obtain an unbiased estimate of the gradient.\n\n- Quality - The paper aims to develop an efficient way to train dual encoders using a large cache of negative samples, and the paper contains a lot of theoretical demonstrations to analyze the convergence and bias induced by the proposed method. \n\n- Clarity - The paper is well written and the ideas expressed in the paper are well presented. However, it’s better to include recent relevant papers, such as LTRe [3] and DRhard [4] with a static document index. Furthermore, it seems that the conclusion part is missing.\n\n- Significance - The line of work presented in this paper is relevant for dense retrieval. However, experimental results and the analysis of these results seem to be slightly insufficient. I believe authors should compare with some recent works with static document index.\n\nPros\n1. The motivation is clear. This paper proposes a useful method for sampling a huge number of hard negative samples to improve performance.\n2. This paper is well-written and easy to follow. \n3. The idea of using Gumbel-Max sampling to accelerate training is interesting and experimental results prove its efficiency.\n4. The theoretical analysis about convergence and bias is sufficient and solid.\n\nCons\n1. The conclusion section is missing.\n2. Results seem discouraging. The proposed cache method (with 2M negatives) cannot outperform ANCE, so I am concerned about the effectiveness.\n3. It would be better to cite more recent works with static document indexes and compare them with the cached negative technique.\n\nImportant questions/requests:\n1. In the abstract, the author claims that their proposed negative cache sampling enables training with reduced memory and computation, but according to table 1 on page 9, when using a cache with 2M elements, it consumes 38G per step, which is huge. So, is it contradictory to what the author said?\n2. Please supplement your conclusion.\n\nTypos/Minor questions:\n1. Line 14, compares -> compare\n2. Both in Equations 1 and 2, the $s_{i y_{i}}$ in the denominator should be $s_{ij}$.\n3. Line 81, $s_{ij}$ seems a typo.\n\n[1] Approximate nearest neighbor negative contrastive learning for dense text retrieval, Lee Xiong et al, ICLR-2021.\n\n[2] Realm: Retrieval-augmented language model pre-training, Kelvin Guu et al, Arxiv-preprint.\n\n[3] Learning to Retrieve: How to Train a Dense Retrieval Model Effectively and Efficiently, Zhan, Jingtao, et al. arXiv preprint\n\n[4] Optimizing Dense Retrieval Model Training with Hard Negatives, Zhan, Jingtao, et al. SIGIR 2021\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No, the conclusion section is also missing.", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "Fkgc5hSlDE", "reviewer": "Reviewer_bmuN", "summary": "This paper is about finding good negative samples for contrastive training. The authors take a caching approach, and show how to make it work in a streaming fashion. Lots of theoretical results are part of the contribution.", "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": "EDIT: The authors have added further experiments, so I am raising my score to a 6.\n\n----------\n\nThanks to the authors for the hard work on this paper, which is well-written and clear. The idea is a nice one, and the descriptions + theory up to the experiments section are excellent.\n\nI am, however, conflicted because the experimental section is very brief and not very insightful. At the end, the paper reads like the authors ran out of space. In such a situation, I would have expected additional experimental results + analyses in the appendix, but that is not the case. There are a number of questions that would be good to answer such as:\n\n- Why does cache (2M) do worse than cache (512k) on TREC? \n- What is the difference in training time and overall GPU/CPU memory between various cache sizes vs ANCE? In short, you should add ANCE and DPR to Table 1.\n- The ANCE paper has experiments for the retrieval components of Natural Questions and Trivial QA. How does your algorithm compare to ANCE on those datasets?\n\nI think it's important for the paper to have more thorough experiments and analysis to fully convince the reader of its efficacy, and I am very open to increasing my score after some additional experiments are added (in the appendix is OK).\n\nMinor\n- Line 181 - \"rho\" should be $\\rho$\n- Line 196 - \"both\" should be \"all three\"\n- Line 294 - \"500 thousand\" -> \"500,000\"\n- Line 296 - \"10(MRR@10)\" -> missing space\n- Generally writing \"query, passage\" as \"(query, passage)\" would make it easier to read.\n- Line 311 - \"we are interesting in seeing\" - \"we are interested in seeing\"", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No, but I don't believe they need to for this basic topic.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "BNL03RxUkj", "reviewer": "Reviewer_z8bE", "summary": "The paper proposes a combination of a Gumbel-Max sampling and embedding caching to reduce the complexity of the negative sampling. The paper has theory and rather convincing results. ", "questions": "", "limitations": "", "rating": 7, "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": "In the initial review I had a concern that authors need to explain why their work is not directly compared to the RocketQA approach, which achieves a much better accuracy (ok claims to achieve) on the MS MARCO dev data set:\n\nQu Y, Ding Y, Liu J, Liu K, Ren R, Zhao WX, Dong D, Wu H, Wang H. RocketQA: An optimized training approach to dense passage retrieval for open-domain question answering. In the process of discussion, we agreed that RocketQA approach is relevant, but likely complementary.\n\nHowever, after the discussion with other reviewers, a bigger concern was that a single data set is not enough to demonstrate the value of their approach. I downgraded the score and recommend some the following:\n\n1. ms marco v2\n2. One or more retrieval-QA datasets from facebook DPR paper: https://github.com/facebookresearch/DPR\n\nSince authors ran experiments on the NQ/DPR dataset it's only fair to recommend acceptance of the paper.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "1bUcF2vZpPB", "reviewer": "Reviewer_ChBd", "summary": "This paper focuses on the problem of negative mining for training bi-encoders with cross-entropy loss in a retrieval setting. \nOverall, I think this is a good paper. The authors provide a method that compares to ANCE on the MS MARCO dataset, but is simpler and much more efficient. The ideas are well argumented, and experiments seem to be consistent with the theoretical aspects. Additional experiments would have made the paper stronger, but results on MS MARCO might be sufficient for acceptance. \n", "questions": "", "limitations": "", "rating": 7, "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": "This paper focuses on the problem of negative mining for training bi-encoders with cross-entropy loss in a retrieval setting. This problem is not new, but has received some attention recently in the NLP/IR community. Strategies like ANCE show significant improvements compared to random/BM25 sampling, at the cost of maintaining a complex training pipeline with asynchronous index refresh. Other simpler strategies like in-batch negatives exhibit limitations (poor negatives).\n\nThe authors propose a new method lying between the two types of approaches, based on a large negative cache that is used to sample “good” negatives. They derive a sampling based on the gumbel-max trick to efficiently optimize the cross-entropy loss without needing to embed every document at each iteration, and propose a “streaming” version that relies on a sample multiset of the full collection. At each iteration, a small fraction of documents in the cache are updated, leading to minimal effects on the training speed. The authors give some convergence bounds for both full and streaming versions, and experiments seem to be consistent with them. The method bears similarities with MoCo (using a cache for negatives) but is conceptually different (dual encoder training). \n\nPros:\n\n- The method compares favorably to ANCE (which is more or less sota on MS MARCO), but is simpler and more efficient. \n- The paper is easy to follow in my opinion, and the key messages are clear.\n- It is interesting to see that a rather small cache size (128k, so ~1.4% of the collection) is already sufficient to increase the perf by 1 point in MRR@10 compared to DPR.  \n\nCons/clarification:\n\n- Maybe I missed something, but why is the cache a multiset (i.e. allowing repetitions for documents) ? Wouldn’t it be better to sample at each iteration elements which are **not** already in the cache? \n- Line 226/227: I do not understand what are 512 vs 1024? \n- In Algorithm 2, I do not get the union in the GumbelMaxSample? As you said in 3.3, you do not want $y_i$ to be sampled right ? \n- Your approach is rather generic; I would have liked to see experiments at least on another dataset. Do you think the improvements of your approach also reflect some issues with MS MARCO (especially the fact that it contains a lot of false negatives) ? We expect that the approach indeed samples better negatives, but does it also avoid sampling such false negatives ?\n\nSome typos / minor comments:\n- Eq (1): y_i => y_j for the denominator\n- line 304: scale => scaling ?\n- algorithm 1: missing beta\n- l. 196: Both of ... which of the three?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not discussed", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a novel and more efficient strategy for approximate negative sampling in IR system training. Theoretical analysis of convergence is included, and empirical results show efficiency gains over the state-of-the-art. All reviewers recommend acceptance, with the majority voting strongly for acceptance. Generally, reviewers praise clarity and motivation, as well as theoretical and empirical results. One reviewer initially had concerns about generalization to additional datasets. This concern was adequately addressed by author response. Overall I agree with reviewers and recommend acceptance. 
Decision: Accept (Poster)