PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval

Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul Bennett, Junaid Ahmed, Arnold Overwijk

arXiv:2007.00808v2cs.IRcs.CLcs.LG

TL;DR

Dense retrieval struggles because sampled training negatives do not represent the irrelevant documents encountered during corpus-wide testing. ANCE samples negatives from an asynchronously refreshed ANN index of the corpus, and experiments report stronger retrieval across web search, OpenQA, and commercial search settings, with retrieval nearly matching BERT reranking accuracy.

  • Problem

    Dense retrieval training uses negatives that differ from the global irrelevant documents it must distinguish during first-stage retrieval, limiting representation learning.

  • Method

    ANCE constructs corpus-wide negatives with an ANN index asynchronously refreshed using updated dense-retrieval document encodings.

  • Results

    ANCE outperforms sparse retrieval on TREC 2019 DL, outperforms DPR in OpenQA passage retrieval, and achieves about 15% relative gains in a production system.

  • Takeaways & Limitations

    ANCE retrieval nearly matches cascade information retrieval with an interaction-based BERT reranker, indicating that its learned representation captures fine-grained search relevance.

  • Takeaways & Limitations

    Dense and sparse retrieval results show surprisingly small overlap below 25%, and the paper notes that DR behavior requires further study.

Abstract

from arXiv · show

Conducting text retrieval in a dense learned representation space has many intriguing advantages over sparse retrieval. Yet the effectiveness of dense retrieval (DR) often requires combination with sparse retrieval. In this paper, we identify that the main bottleneck is in the training mechanisms, where the negative instances used in training are not representative of the irrelevant documents in testing. This paper presents Approximate nearest neighbor Negative Contrastive Estimation (ANCE), a training mechanism that constructs negatives from an Approximate Nearest Neighbor (ANN) index of the corpus, which is parallelly updated with the learning process to select more realistic negative training instances. This fundamentally resolves the discrepancy between the data distribution used in the training and testing of DR. In our experiments, ANCE boosts the BERT-Siamese DR model to outperform all competitive dense and sparse retrieval baselines. It nearly matches the accuracy of sparse-retrieval-and-BERT-reranking using dot-product in the ANCE-learned representation space and provides almost 100x speed-up.

1 INTRODUCTION

Dense retrieval addresses sparse retrieval’s bottleneck by learning continuous representations, but its training negatives do not match the global irrelevant documents encountered at test time. ANCE addresses this mismatch by selecting corpus-wide negatives with an asynchronously updated ANN index.

  • Dense retrieval learns continuous representations that can support ANN search and reduce vocabulary mismatch, unlike discrete bag-of-words retrieval.It is designed as a first-stage retrieval alternative to sparse matching.
  • Global negatives in first-stage dense retrieval differ substantially from negatives retrieved by sparse models, making negative construction a central challenge.Dense retrieval must distinguish relevant documents from all irrelevant documents in the corpus.
  • Local in-batch negatives can produce diminishing gradient norms, high stochastic gradient variance, and slow training convergence under common dense-retrieval conditions.The analysis identifies local negative sampling as a bottleneck of dense retrieval effectiveness.
  • ANCE constructs global negatives using the being-optimized dense-retrieval model and aligns training-negative and testing-irrelevant-document distributions.The mechanism is intended to improve gradient estimation and learning convergence.
  • ANCE is implemented with an asynchronously refreshed corpus ANN index while experiments cover web search, OpenQA, and a commercial search engine.A parallel Inferencer recomputes corpus document encodings and refreshes the index as training proceeds.

2 PRELIMINARIES

Dense retrieval scores query–document similarity in a learned embedding space, then trains that space to bring relevant documents closer than sampled irrelevant documents. Because first-stage retrieval faces millions of corpus-wide negatives, choosing informative samples is essential.

  • Dense retrieval encodes queries and documents into dense embeddings and scores them with cosine or dot-product similarity.The encoder is often fine-tuned from pretrained transformers, and similarity functions support efficient ANN retrieval.
  • Representation learning seeks parameters that map queries toward relevant documents while separating irrelevant documents using a ranking loss.The loss may be binary cross entropy, hinge loss, or negative log likelihood.
  • First-stage dense retrieval treats the entire corpus excluding relevant documents as negatives, yielding potentially millions of training instances that must be sampled.This scale makes negative sampling unavoidable.
  • BM25 negatives can bias dense models toward sparse retrieval, while local mini-batch negatives do not significantly outperform BM25 negatives.Neither strategy reliably provides a substantial advantage for dense retrieval representation learning.

3 ANALYSES ON THE CONVERGENCE OF DENSE RETRIEVAL TRAINING

The convergence analysis links dense-retrieval learning speed to the informativeness and gradient norms of sampled negatives. It argues that local in-batch sampling is unlikely to find the few informative corpus negatives, while variance-minimizing sampling favors high-gradient instances.

  • An unbiased importance-sampled SGD update uses negative sampling probabilities to estimate the full gradient and govern parameter movement toward the optimum.The scaling factor compensates for the sampling probability.
  • Sampling negatives in proportion to per-instance gradient norm minimizes the variance of the gradient estimator and can improve convergence rate.This follows from the variance-reduction analysis for the unbiased estimator.
  • The gradient-norm analysis bounds per-sample gradients through network-layer quantities, with the last-layer gradient identified as the main moving component.Intermediate layers are described as more regulated by normalization techniques.
  • Dense-retrieval convergence depends on informative negatives because near-zero-loss negatives have near-zero gradients and contribute little to learning.The analysis therefore treats negative informativeness as central to training progress.
  • Local in-batch negatives are unlikely to be informative because batch size is far smaller than the corpus and only a small subset of negatives is difficult.The analysis states b ≪ |C| and |D−∗| ≪ |C|.
  • The probability that a random mini-batch contains meaningful negatives is close to zero, making local-batch sampling unlikely to provide optimal training signals.The probability is expressed as p = b|D−∗|/|C|^2.

4 APPROXIMATE NEAREST NEIGHBOR NOISE CONTRASTIVE ESTIMATION

ANCE operationalizes global negative sampling by retrieving hard negatives from an asynchronously updated ANN index over the corpus. This approximates informative negatives while allowing training and corpus re-encoding to proceed in parallel.

  • ANCE selects negatives from the entire corpus using an asynchronously updated ANN index.This directly implements the analysis’s conclusion that negatives should be constructed globally.
  • ANCE samples top documents retrieved by the dense-retrieval model from the ANN index, excluding relevant documents.The sampled set is defined as ANN_f(q,d) \ D+.
  • ANCE negatives approximately correspond to informative negatives and theoretically have higher training loss, larger gradient-norm bounds, and better convergence behavior.The claim is presented as a theoretical consequence of selecting hard corpus-wide negatives.
  • An up-to-date ANN index is difficult to maintain because refreshing corpus representations requires expensive inference over all documents before rebuilding the index.Per-batch index refreshing is therefore impractical.
  • Asynchronous refresh uses a recent checkpoint to re-encode the corpus while the Trainer continues learning with the previous index, then supplies the refreshed index.The index is updated every m batches in the described implementation.
  • The lag between the ANN index and model optimization depends on Trainer–Inferencer resource allocation, with a 1:1 GPU split reported as sufficient to minimize its influence.This describes a practical condition for limiting asynchronous-training gaps.

5 EXPERIMENTAL METHODOLOGIES

The experiments evaluate ANCE across web search, open-domain question answering, and a commercial search engine, comparing it with dense-retrieval baselines and established retrieval methods. The setups vary negative construction, data domains, retrieval configurations, and production-system conditions.

  • Benchmarks: Experiments cover TREC 2019 Deep Learning Track web search, Natural Questions and TriviaQA open-domain question answering, and a commercial search engine.The evaluation includes first-stage retrieval and, where applicable, reranking or downstream reader accuracy.
  • Baselines: Dense-retrieval baselines vary negative construction using in-batch random negatives, BM25 top-100 negatives, and a 1:1 BM25-plus-random combination.The baselines use the same BERT-Siamese architecture while changing how negative instances are selected.
  • Implementation Details: TREC DL models use BM25 warm-up training and are fine-tuned from RoBERTa base, while ANCE is also warmed up with BM25 negatives.The implementation choices reflect the reported usefulness of BM25 negatives for dense-retrieval training.
  • Implementation Details: ANCE handles long documents with FirstP or MaxP, splitting documents into up to four 512-token passages for max-pooled scoring in the latter setting.The ANN search uses Faiss IndexFlatIP, with index refreshing per 10k training batches and a 1:1 Trainer:Inference GPU allocation.

6 EVALUATION RESULTS

ANCE improves dense retrieval effectiveness across benchmark, OpenQA, and production settings while retaining major inference-speed advantages. Its training analyses link more realistic global negatives to stronger separation and convergence.

  • Effectiveness: ANCE significantly outperforms sparse retrieval baselines on TREC 2019 DL and outperforms DPR in OpenQA passage retrieval.In production search, ANCE delivers about 15% relative gains, and replacing DPR retrieval with ANCE improves answer accuracy with the same readers.
  • Effectiveness: ANCE retrieval nearly matches interaction-based BERT reranking accuracy, achieving the smallest retrieval–reranking gap among dense retrieval models.The result supports learning a representation space that captures fine-grained search relevance without interaction-based reranking.
  • Efficiency: 100x speed up is reported for standard-batched dense retrieval versus BERT reranking in TREC DL document retrieval.Siamese encoding and pre-computable document representations provide the online efficiency advantage.
  • Training convergence: 63% initial overlap between ANCE negatives and top DR-retrieved negatives converges to 100%, versus 15% for BM25 negatives and 0% for local negatives.The overlap measures how often training negatives include informative high-scoring negatives.
  • Training convergence: ANCE global negatives maintain higher training loss and larger gradient norms than trivial local negatives, which produce near-zero loss.These observations empirically validate the proposed connection between informative negatives, gradient behavior, and convergence.
  • Discussion: Dense retrieval results show less than 25% overlap with sparse retrieval results, indicating that dense retrieval behaves fundamentally differently from sparse retrieval.The paper states that further studies are needed to understand this behavior.

7 RELATED WORK

Related work improves retrieval through interaction modeling, sparse-retrieval enhancements, enlarged negative pools, and dense embedding search. ANCE belongs to the dense-retrieval path while addressing its negative-sampling challenge.

  • Neural information retrieval: Interaction models handle term-level matches and are generally more effective but more expensive, motivating distillation, caching, and related cost-reduction techniques.These approaches aim to reduce the computational cost of interaction-based neural retrieval.
  • Sparse and dense retrieval: Sparse retrieval has been improved with learned term weighting, query expansion, and document expansion, whereas dense retrieval conducts search in embedding space via ANN.The two approaches follow different paths for improving first-stage retrieval.
  • Negative sampling: Contrastive-learning research shows that enlarging the negative candidate pool beyond the training batch can improve representation learning.Prior vision work maintains recent-batch representations with momentum, while parallel retrieval work explores larger negative pools.
  • Applications: Dense retrieval also supports grounded language models, question answering, fact verification, and paraphrase-pair discovery for pretraining.In these systems, dense retrievers may be frozen or optimized indirectly.

8 CONCLUSION

The paper analyzes why local negatives limit dense-retrieval training and proposes ANCE to construct global corpus negatives. Experiments across web search, OpenQA, and commercial search support the analysis.

  • Conclusion: ANCE constructs training negatives globally from the entire corpus to address the bottleneck created by uninformative local negatives.The paper frames local negatives as yielding low gradient norms and contributing little to learning convergence.
  • Conclusion: ANCE experiments span web search, OpenQA, and a commercial search engine’s production system.These settings provide evidence across multiple retrieval scenarios.
  • Conclusion: ANCE negatives have much bigger gradient norms, reduce stochastic gradient variance, and improve training convergence.These empirical findings validate the paper’s theoretical analysis.

A.1 MORE EXPERIMENTAL DETAILS

The appendix describes TREC DL data and evaluation, OpenQA settings, baselines, model configuration, optimization, and ANN hyperparameters. It also records benchmark-specific data-quality limitations.

  • TREC DL benchmarks: TREC DL uses MS MARCO-derived training and development data, while NIST assessors evaluate document and passage test results through standard pooling.The official evaluation pools the top 10 results from participating runs.
  • TREC DL benchmarks: TREC DL reports NDCG@10 on test and MRR@10 on MARCO Passage Dev, while MARCO Document Dev recall is less meaningful because DR labels have low coverage.The document corpus was back-filled from passage URLs, introducing temporal and content inconsistencies.
  • OpenQA: OpenQA experiments use Natural Questions and TriviaQA, evaluating Coverage@20/100 and answer accuracy with RAG-Token or DPR Reader.The readers are run over passages retrieved by ANCE.
  • Baselines: TREC DL baselines include BM25, tuned sparse retrieval, DeepCT, and dense models differing in negative construction.Dense baselines include random, BM25, combined BM25-plus-random, and in-batch contrastive negatives.
  • Model configuration: ANCE uses RoBERTa-base BERT-Siamese models with a 768 × 768 projection layer and layer normalization.The configuration follows the setup used in prior dense-retrieval work.
  • Optimization: ANCE training takes about 1–2 hours per epoch, converges in about 10 epochs, and uses LAMB with learning rates of 5e-6 for documents and 1e-6 for passages.Learning-rate warm-up and decay begin after 5000 steps.
  • Hyperparameters: The appendix studies training loss and testing NDCG under different ANN refresh intervals, GPU allocations, and learning rates.The figure’s x-axis is training steps in thousands.
  • Hyperparameters: “Top K Neg” denotes the top k ANN-retrieved candidates from which ANCE samples negatives.This configuration controls the candidate pool used for negative sampling.

A.2 OVERLAP WITH SPARSE RETRIEVAL IN TREC 2019 DL TRACK

Dense retrieval results differ substantially from sparse retrieval in TREC 2019, complicating pooled evaluation. ANCE’s case studies show semantic gains over BM25, but also reveal mixed representations and errors involving near-relevance or missing domain knowledge.

  • Overlap and evaluation: TREC pooling labels only documents ranked in the top 10 by participating systems, so unlabeled documents are treated as irrelevant.The hole rate measures system difference from the pooled systems, not retrieval accuracy.
  • Overlap and evaluation: At most 25% of documents retrieved by dense retrieval overlap with BM25 in the top 100, producing high hole rates and less informative recall.All dense retrieval methods differed considerably from the sparse systems that created the TREC pool.
  • Case studies: ANCE outperforms BM25 on 29 of 43 TREC 2019 document queries, loses on 13, and ties on 1.Winning and losing queries are presented in Tables 8 and 9, with corresponding ANCE representations visualized by t-SNE.
  • Case studies: ANCE better captures document and query semantics than BM25, including cases where BM25 matches terms but retrieves a document about the wrong country.For the Switzerland food query, BM25 matched “most popular food” in a Mexico document because “Switzerland” appeared only in a related-question section.
  • Case studies: ANCE errors include retrieving related but not exactly relevant documents, lacking domain knowledge, and retrieving documents that make sense but are labeled irrelevant.Examples include “yoga pose” for “bow in yoga” and misunderstanding “active margin” as financial rather than geographical terminology.
  • Case studies: Winning cases often show clear document-group separation, whereas losing cases show mixed representations or too few relevant documents.The t-SNE plots cover the learned representation space for the TREC queries examined in the case studies.
Loading 2007.00808v2…