Negative Sampling

Negative sampling is the engine of contrastive learning, where a model learns representations by pulling relevant query-document pairs together in vector space while pushing non-relevant pairs apart. Instead of computing a softmax over millions of classes, the model only evaluates a small set of negative samples—documents that do not match the query. The InfoNCE loss (Noise Contrastive Estimation) formalizes this as a binary classification task: distinguishing the true positive from noise. This approach preserves the discriminative power of full softmax training while reducing the per-batch computation from O(N) to O(K), where K is the number of negatives (typically 5–100).

The most computationally efficient approach reuses other positive pairs within a training mini-batch as negatives. For a batch of B query-document pairs, each query treats the other B-1 documents as negatives, yielding B² pairwise comparisons from only B forward passes. This technique, popularized by SimCLR and adopted in Dense Passage Retrieval (DPR), requires large batch sizes (often 512–4096) to provide sufficient negative diversity. The primary limitation is batch bias: frequently occurring documents are over-sampled as negatives, which can push them away from legitimate queries unless corrected with debiasing techniques.

Random negatives are easy to distinguish and provide weak training signals. Hard negative mining selects documents that are superficially similar to the query but ultimately irrelevant—often retrieved by a previous model iteration using BM25 or ANN search. These challenging examples force the model to learn fine-grained semantic distinctions. For example, for the query 'Python programming language', a hard negative might be a document about 'Burmese pythons'. Techniques include top-k ANN retrieval from the current index and denoising to filter false negatives. Hard negatives significantly improve model discriminability but require periodic re-indexing during training.

A sophisticated pipeline uses a cross-encoder to identify the most informative negatives. The process: a bi-encoder retrieves top candidates, then a cross-encoder scores each candidate by processing the concatenated query-document pair through full cross-attention. Documents with high bi-encoder similarity but low cross-encoder relevance become high-quality hard negatives. This approach, used in training ColBERT and advanced DPR variants, captures nuanced irrelevance that vector similarity alone misses—such as documents that share keywords but contradict the query's intent. The cross-encoder provides a more accurate relevance signal for negative selection.

The ratio of negatives to positives per query is a critical hyperparameter. Common configurations include:

• 1:1 ratio: Balanced, used in basic pairwise ranking
• 5:1 to 20:1: Standard for bi-encoder training with InfoNCE loss
• 100:1 or higher: Used with large batch sizes and in-batch negatives Too few negatives cause representation collapse, where all vectors converge to similar regions. Too many negatives increase computational cost with diminishing returns. The optimal rate depends on corpus size, batch size, and the difficulty of the negatives. Gradient accumulation across multiple micro-batches can simulate larger effective batch sizes when GPU memory is constrained.

In-batch negative sampling introduces selection bias: popular documents appear frequently as negatives, causing the model to artificially push them away from relevant queries. Solutions include:

• LogQ correction: Adjusting loss weights based on document frequency in the corpus
• Cross-batch negatives: Maintaining a memory bank of embeddings from previous batches
• False negative detection: Using metadata or cross-encoder verification to identify and remove legitimate positives that were incorrectly sampled as negatives Without debiasing, models underperform on head queries and popular documents, reducing retrieval quality for common information needs.

The mathematical objective function that negative sampling serves. It explicitly pulls the vector representations of a query and its positive (relevant) document closer together in the embedding space while simultaneously pushing the representations of the query and its negative (irrelevant) documents apart. Common implementations include InfoNCE and triplet loss, which operate on the principle of maximizing mutual information between positive pairs.

A strategy to improve model discriminability by selecting negative samples that are superficially similar to the query but ultimately irrelevant. Instead of random negatives, hard negatives force the model to learn finer-grained semantic distinctions. For example, for the query 'Python programming language,' a hard negative might be a document about 'Python the snake,' requiring the model to move beyond simple keyword overlap.

A memory-efficient training technique where other positive examples within the same mini-batch are reused as negatives for a given query. This avoids explicit sampling overhead but introduces a selection bias: the negatives are not truly random and can accidentally include false negatives if the batch contains multiple relevant documents for the same query. Large batch sizes are critical for this method to be effective.

The dual-tower neural architecture that necessitates negative sampling. A bi-encoder processes queries and documents through separate, independent encoders, producing fixed-dimensional vectors. Because the towers are independent, the model cannot attend across query-document pairs during encoding. It must learn a global similarity function using contrastive loss, which requires explicit positive and negative examples to shape the embedding space.

A re-ranking methodology that avoids the need for negative sampling during inference by processing the concatenated query and document simultaneously through a transformer. This allows full cross-attention, yielding higher precision relevance scores. However, it is computationally prohibitive for first-pass retrieval. Cross-encoders are often used to re-rank the top-k candidates from a bi-encoder, which was trained using negative sampling.