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
cs.IR, cs.CL, cs.LG
2020-07-02
ANCE samples hard negatives from an asynchronously refreshed ANN index, lifting dense retrieval near BERT cascade accuracy on TREC while cutting online latency about 100x.
First-stage retrieval long depended on bag-of-words match such as BM25, which fails when query and document use different words. Dense retrieval encodes both into one vector space and searches with approximate nearest neighbors (ANN). The representation is learnable, plugs into pretraining, and is fast at serving. Learned dual encoders still often lost to BM25, especially on documents.
The bottleneck is negatives. Rerankers inherit hard negatives from a previous retriever. First-stage retrieval must separate relevant documents from the rest of the corpus, so the true negative set is "everything else." The then-standard practice sampled random in-batch negatives or BM25 top hits. Through a variance-reduction lens, the paper shows why that fails: batch size is tiny relative to the corpus, truly hard negatives are rare, local samples almost never hit them, loss collapses toward zero, gradient norms vanish, and training crawls.
ANCE (Approximate nearest neighbor Negative Contrastive Estimation) uses the dual encoder under training to retrieve, from a corpus-wide ANN index, the documents the current model scores closest to the positive. Those are the hardest negatives for the model as it stands.
Re-encoding the full corpus every batch is impossible, so the index refreshes asynchronously. A Trainer keeps sampling from the previous index while an Inferencer re-encodes the corpus with a recent checkpoint and swaps the index when finished. Experiments split GPUs 1:1 between Trainer and Inferencer and refresh every 10k steps. For each positive, one negative is drawn uniformly from the ANN top 200.
The model is plain: a RoBERTa-base Siamese dual encoder, dot-product similarity, NLL loss. Long documents use FirstP (first 512 tokens) or MaxP (up to four 512-token chunks, then max-pool, which ANN supports natively). TREC runs warm up on BM25 negatives; OpenQA runs continue from DPR checkpoints.
On TREC 2019 DL, ANCE is the only negative scheme that reliably lifts BERT-Siamese past sparse retrieval.
| Method | MARCO Passage MRR@10 | TREC Passage NDCG@10 | TREC Document NDCG@10 |
| BM25 | 0.240 | 0.506 | 0.519 |
| DPR (BM25 + random) | 0.311 | 0.600 | 0.557 |
| ANCE FirstP | 0.330 | 0.648 | 0.615 |
| ANCE MaxP | n/a | n/a | 0.628 |
| BERT reranker | n/a | 0.742 | 0.646 |
MaxP at 0.628 on documents sits next to BERT rerank at 0.646. On Natural Questions, Top-20 / Top-100 coverage is 81.9 / 87.5 against DPR's 78.4 / 85.4. Swapping ANCE into the same readers raises NQ accuracy from RAG-Token's 44.1 to 46.0. Offline gains in a commercial engine are +18.4% on 250M docs and about +15% on 8B.
Online, one query retrieving 100 docs costs about 11.6 ms versus 1.42 s for BM25 plus BERT rerank, roughly two orders of magnitude. Training cost is dominated by corpus re-encoding, about 10 hours per refresh, amortized by the async loop.
Overlap between local negatives and the true hard test negatives is 0. ANCE negatives start at 63% overlap and converge to 100%. Training loss and per-layer gradient norms follow the theory: local negatives sit at near-zero loss with collapsed gradients; ANCE negatives stay hard, with gradient norms an order of magnitude larger.
The paper moved dense retrieval from "dual encoders lose to bag-of-words" to "dot-product retrieval can approach an interactive BERT cascade." The claim that training negatives must match the documents you need to separate at test time became the default premise for later hard-negative work. Asynchronous ANN refresh became a standard piece of large dual-encoder training.
If you already rerank and your negatives are hard, ANCE adds little. It solves first-stage retrieval inventing its own hard negatives.
TREC 2019 labels were pooled from sparse systems. Dense and BM25 top-100 overlap is under 25%, hole rates are high, and Recall is shaky; MARCO click labels are more trustworthy. Document runs depend on BM25 warmup; from-scratch ANCE is not reported. Large async gaps make training oscillate; the appendix only says a 1:1 GPU split is enough. FirstP truncates long documents. Negatives come from the model's own top hits, so unlabelled false negatives are not treated.