Negative Sampling and Retrieval Training

Two-tower app recommenders are not hypothetical. Google applied one to a large-scale production app recommendation system, and in 2020 published the sampler it took to make the training work. Mixed Negative Sampling has a stated purpose: “In particular, different from commonly used batch or unigram sampling methods, MNS uses a mixture of batch and uniformly sampled negatives to tackle the selection bias of implicit user feedback.” Online A/B testing showed improved retrieval quality through more high-quality app installs. The model did not change. What each positive got compared against did.

Why a batch-only contrast is not enough has been measured. Count how often locally drawn negatives contain informative ones and the answer is none. The overlap of NCE or random in-batch negatives with the top-100 highest-scored negatives is zero. BM25 negatives reach 15%, ANCE negatives 63%. Microsoft's ANCE paper reports it. Zero overlap is what easy-negative saturation looks like with a number on it.

The risk on the other side has a number too. The RocketQA team went and looked: “Specifically, we manually examine the top-retrieved passages of 100 questions, that were not labeled as true positives. We find that about 70% of them are actually positives or highly relevant.” Mine from the top of your own ranked list and much of what you mine may be the right answer.

Large-catalog retrieval cannot compare every query with every item on every update. MS MARCO holds 8.8M passages. The neural retrieval system Google built for YouTube was deployed over a corpus with tens of millions of videos. Training therefore uses a subset of negatives, and the model learns the distinctions the sampler emphasises.

How much rides on that subset is said plainly in the Dense Passage Retrieval paper: “In practice, how to select negative examples is often overlooked but could be decisive for learning a high-quality encoder.” Table 3 of that paper is the demonstration, on the Natural Questions development set. Without in-batch reuse, the choice between random (64.3%), BM25 (63.3%) and gold (63.1%) negatives barely moved top-20 accuracy at all. Take the same seven gold negatives in-batch and it moves from 63.1% to 69.1%. The negatives were the same. Only how they were used changed.

Six samplers are in play: random, in-batch, popularity, mixed, cross-batch, and hard-negative. Each buys difficulty and coverage at a different price in compute and in false negatives. And when the sampled objective should approximate a full-corpus softmax, the sampling probability may need correcting as well.

Every row answers one question differently: what should this positive be compared against?

The in-batch row has a price, measured on the Natural Questions development set. Seven gold negatives with no in-batch reuse give 63.1% top-20 accuracy. The same seven taken in-batch give 69.1%. Thirty-one in-batch give 70.8%, and 127 in-batch give 73.0%. That is contrast bought cheaply, by reusing what is already in the batch. Random catalogue draws keep the comparison broad; in that same table, without in-batch reuse, they sit at 64.3%.

The popularity-and-mixed row is a shipped sampler, not a category in a diagram. Mixed Negative Sampling blends batch negatives with uniformly sampled ones precisely to tackle the selection bias of implicit user feedback.

The hard-or-retrieved row is where the boundary gets sharpened, and it is priced too. A single BM25 hard negative lifts DPR's top-20 accuracy to 77.3% (31+32) and 78.0% (127+128). A second BM25 negative does not help (76.4%).

Cross-batch memory buys size rather than aim. RocketQA's ablation on MS MARCO passage ranking gives that row its own number: 32.39 MRR@10 for in-batch negatives, 33.32 for cross-batch.

Against what, exactly, is each positive being contrasted? The universe of negatives is settled first, then mixed by difficulty, masked for known positives, and tracked while training runs.

Step 2 has published settings, not just an instruction to combine broad and hard. Blending random with hard negatives kept improving recall for Facebook Search, saturating at easy:hard = 100:1. For offline mining the hardest examples were not the best choice; sampling between rank 101-500 achieved the best model recall. Online mining worked best with at most two hard negatives per positive.

Step 4 has a price attached. In RocketQA's ablation, undenoised hard negatives collapse to 26.03 MRR@10, below the 32.39 in-batch baseline. Denoised hard negatives reach 36.38. Step 5 exists because Krichene and Rendle showed that a sampled evaluation cannot settle the question on its own.

Random catalogue negatives trained a two-tower app recommender: it learned to beat easy negatives and failed on substitutes. The recommender is invented, and the quiz below asks about it. Here is the routine run on it. All numbers are invented for the exercise.

One variable at a time is the whole design, and the ANCE experiments ran it: the BERT-Siamese encoder and the NLL loss held fixed, only the negatives varied. On the MS MARCO passage development set, MRR@10 is 0.261 with random in-batch negatives, 0.256 with hardest-in-batch NCE negatives, 0.299 with BM25 negatives, 0.311 with DPR-style BM25-plus-random negatives, and 0.330 with globally retrieved ANCE negatives. The mechanism is in the preprint's own words: “As expected, the uninformative local negatives are trivial to separate, yielding near-zero training loss, while ANCE global negatives are much harder and maintain a high training loss.” One variable moved. The ordering of those five rows is attributable.

Report loss together with full-corpus or large-candidate recall. The sampled number is not simply a noisier version of the real one. Krichene and Rendle proved the point in 2020: “This paper investigates sampled metrics in more detail and shows that they are inconsistent with their exact version, in the sense that they do not persist relative statements, e.g., recommender A is better than B, not even in expectation.” The smaller the sampling size, the less difference there is between metrics, until for very small sampling sizes all metrics collapse to AUC. Their conclusion is that sampling should be avoided for metric calculation, and that a study that must sample can improve the estimate with a correction obtained by minimising bias or mean squared error. A sampled score can rank two systems the wrong way round.

Inspect negative examples by hand as well — head, tail, new items, multilingual content, near-duplicate variants. A sampler that looks “hard” numerically may simply be exploiting bad metadata or stale embeddings.