# Improving Dual-Encoder Training through Dynamic Indexes for Negative Mining

arXiv: https://arxiv.org/abs/2303.15311 · HTML: https://mlsanity.com/paper/2303.15311/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 87 references that are in the map.
- First posted on arXiv 27 Mar 2023.

## Builds on (most cited first, 30 of 52)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [Categorical Reparameterization with Gumbel-Softmax](https://mlsanity.com/paper/1611.01144/) (2016)
- [REALM: Retrieval-Augmented Language Model Pre-Training](https://mlsanity.com/paper/2002.08909/) (2020)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables](https://mlsanity.com/paper/1611.00712/) (2016)
- [Atlas: Few-shot Learning with Retrieval Augmented Language Models](https://mlsanity.com/paper/2208.03299/) (2022)
- [Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval](https://mlsanity.com/paper/2007.00808/) (2020)
- [ColBERTv2: Effective and Efficient Retrieval via Lightweight Late Interaction](https://mlsanity.com/paper/2112.01488/) (2021)
- [Large Dual Encoders Are Generalizable Retrievers](https://mlsanity.com/paper/2112.07899/) (2021)
- [RocketQA: An Optimized Training Approach to Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2010.08191/) (2020)
- [Promptagator: Few-shot Dense Retrieval From 8 Examples](https://mlsanity.com/paper/2209.11755/) (2022)
- [Efficient Natural Language Response Suggestion for Smart Reply](https://mlsanity.com/paper/1705.00652/) (2017)
- [RocketQAv2: A Joint Training Method for Dense Passage Retrieval and Passage Re-ranking](https://mlsanity.com/paper/2110.07367/) (2021)
- [Condenser: a Pre-training Architecture for Dense Retrieval](https://mlsanity.com/paper/2104.08253/) (2021)
- [Zero-Shot Entity Linking by Reading Entity Descriptions](https://mlsanity.com/paper/1906.07348/) (2019)
- [Learning Dense Representations for Entity Retrieval](https://mlsanity.com/paper/1909.10506/) (2019)
- [Scalable Zero-shot Entity Linking with Dense Entity Retrieval](https://mlsanity.com/paper/1911.03814/) (2019)
- [On the Convergence of SGD with Biased Gradients](https://mlsanity.com/paper/2008.00051/) (2020)
- [A Review of the Gumbel-max Trick and its Extensions for Discrete Stochasticity in Machine Learning](https://mlsanity.com/paper/2110.01515/) (2021)
- [REBAR: Low-variance, unbiased gradient estimates for discrete latent variable models](https://mlsanity.com/paper/1703.07370/) (2017)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Gradient Estimation with Stochastic Softmax Tricks](https://mlsanity.com/paper/2006.08063/) (2020)
- [Efficient Passage Retrieval with Hashing for Open-domain Question Answering](https://mlsanity.com/paper/2106.00882/) (2021)
- [PECOS: Prediction for Enormous and Correlated Output Spaces](https://mlsanity.com/paper/2010.05878/) (2020)
- [Adaptive Sampled Softmax with Kernel Based Sampling](https://mlsanity.com/paper/1712.00527/) (2017)

## Built on by (most cited first, 5 of 5)

- [Retro-Rank-In: A Ranking-Based Approach for Inorganic Materials Synthesis Planning](https://mlsanity.com/paper/2502.04289/) (2025)
- [EMC2: Efficient MCMC Negative Sampling for Contrastive Learning with Global Convergence](https://mlsanity.com/paper/2404.10575/) (2024)
- [EHI: End-to-end Learning of Hierarchical Index for Efficient Dense Retrieval](https://mlsanity.com/paper/2310.08891/) (2023)
- [Adaptive Two-Phase Finetuning LLMs for Japanese Legal Text Retrieval](https://mlsanity.com/paper/2412.13205/) (2024)
- [A Fresh Take on Stale Embeddings: Improving Dense Retriever Training with Corrector Networks](https://mlsanity.com/paper/2409.01890/) (2024)

## Abstract (arXiv)

Dual encoder models are ubiquitous in modern classification and retrieval. Crucial for training such dual encoders is an accurate estimation of gradients from the partition function of the softmax over the large output space; this requires finding negative targets that contribute most significantly ("hard negatives"). Since dual encoder model parameters change during training, the use of traditional static nearest neighbor indexes can be sub-optimal. These static indexes (1) periodically require expensive re-building of the index, which in turn requires (2) expensive re-encoding of all targets using updated model parameters. This paper addresses both of these challenges. First, we introduce an algorithm that uses a tree structure to approximate the softmax with provable bounds and that dynamically maintains the tree. Second, we approximate the effect of a gradient update on target encodings with an efficient Nystrom low-rank approximation. In our empirical study on datasets with over twenty million targets, our approach cuts error by half in relation to oracle brute-force negative mining. Furthermore, our method surpasses prior state-of-the-art while using 150x less accelerator memory.