Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper focuses on the problem of negative mining for training bi-encoders with cross-entropy loss in a retrieval setting. 
Overall, 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. 

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).

The 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). 

Pros:

- The method compares favorably to ANCE (which is more or less sota on MS MARCO), but is simpler and more efficient. 
- The paper is easy to follow in my opinion, and the key messages are clear.
- 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.  

Cons/clarification:

- 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? 
- Line 226/227: I do not understand what are 512 vs 1024? 
- 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 ? 
- 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 ?

Some typos / minor comments:
- Eq (1): y_i => y_j for the denominator
- line 304: scale => scaling ?
- algorithm 1: missing beta
- l. 196: Both of ... which of the three?

limitations_and_societal_impact: Not discussed
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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. 
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:

Qu 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.

However, 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:

1. ms marco v2
2. One or more retrieval-QA datasets from facebook DPR paper: https://github.com/facebookresearch/DPR

Since authors ran experiments on the NQ/DPR dataset it's only fair to recommend acceptance of the paper.
limitations_and_societal_impact: N/A
review_title: null

final_score: rating: 7: Good paper, accept
review_content: 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.
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.

- 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. 

- 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.

- 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.

Pros
1. The motivation is clear. This paper proposes a useful method for sampling a huge number of hard negative samples to improve performance.
2. This paper is well-written and easy to follow. 
3. The idea of using Gumbel-Max sampling to accelerate training is interesting and experimental results prove its efficiency.
4. The theoretical analysis about convergence and bias is sufficient and solid.

Cons
1. The conclusion section is missing.
2. Results seem discouraging. The proposed cache method (with 2M negatives) cannot outperform ANCE, so I am concerned about the effectiveness.
3. It would be better to cite more recent works with static document indexes and compare them with the cached negative technique.

Important questions/requests:
1. 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?
2. Please supplement your conclusion.

Typos/Minor questions:
1. Line 14, compares -> compare
2. Both in Equations 1 and 2, the $s_{i y_{i}}$ in the denominator should be $s_{ij}$.
3. Line 81, $s_{ij}$ seems a typo.

[1] Approximate nearest neighbor negative contrastive learning for dense text retrieval, Lee Xiong et al, ICLR-2021.

[2] Realm: Retrieval-augmented language model pre-training, Kelvin Guu et al, Arxiv-preprint.

[3] Learning to Retrieve: How to Train a Dense Retrieval Model Effectively and Efficiently, Zhan, Jingtao, et al. arXiv preprint

[4] Optimizing Dense Retrieval Model Training with Hard Negatives, Zhan, Jingtao, et al. SIGIR 2021

limitations_and_societal_impact: No, the conclusion section is also missing.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: 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.
main_review: EDIT: The authors have added further experiments, so I am raising my score to a 6.

----------

Thanks 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.

I 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:

- Why does cache (2M) do worse than cache (512k) on TREC? 
- 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.
- 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?

I 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).

Minor
- Line 181 - "rho" should be $\rho$
- Line 196 - "both" should be "all three"
- Line 294 - "500 thousand" -> "500,000"
- Line 296 - "10(MRR@10)" -> missing space
- Generally writing "query, passage" as "(query, passage)" would make it easier to read.
- Line 311 - "we are interesting in seeing" - "we are interested in seeing"
limitations_and_societal_impact: No, but I don't believe they need to for this basic topic.
review_title: null

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)