Negative sampling.
Hatchway's "More like this" model learns from messages and saves, but no one records the 20 million listings a buyer ignored. A full softmax over all of them costs about 5 trillion multiply-adds per batch, so the trainer samples negatives instead. Random negatives are too easy, in-batch negatives punish popular listings, and hard negatives are sometimes secret positives. This topic covers where negatives come from, the popularity correction, and the mix that works.
Builds on Why imbalance hurts and Two-tower retrieval.
The idea.
Nobody logs the listings a buyer ignored; you pick the negatives, and the pick is the lesson.
There is no logged "no"
Hatchway is a fictional app for secondhand furniture. On a listing page it shows a "More like this" row, filled by a two-tower model that maps the buyer's context and every listing to 64-number vectors and returns the listings whose vectors score highest. A training positive is a listing the buyer messaged or saved in the session. What counts as a positive, and how position skews it, is covered in implicit labels.
The log has no matching negatives. A buyer who messaged about a teak sofa did not reject the other 19,999,999 active listings; almost all of them never appeared on screen. The ideal training signal is a softmax over the whole catalogue: turn every listing's score into a probability, then raise the messaged listing's share against all 20 million. Scoring 20 million listings for every example is far too slow, so the trainer approximates that softmax with a small set of chosen listings per positive. Those are the negatives, and choosing them is the design problem.
Every way of choosing answers three questions. How hard are the negatives, that is, how close to the positive? How biased is the choice, and which listings does it over- or under-punish? And what does it cost in extra embedding passes? The strip below walks one training row through the main answers.
One positive and its negatives
- Sofa, 1 item, Positive, Teak 3-seater sofa, the listing this buyer messaged.
- Bike, 1 item, Random negative
- Fan, 1 item, Random negative
- Shelf, 1 item, Random negative
- Cooker, 1 item, Random negative
- Guitar, 1 item, Random negative
- Rug, 1 item, Random negative
- Chair, 1 item, Random negative
- Positive
- Random negative
- In-batch negative
- Hard negative
- False negative
- Sofa
- Teak 3-seater sofa, the listing this buyer messaged.
As it starts. 4 steps follow.
How it works.
Why sample at all, where negatives come from, the popularity bias of each source and its fix, and how hard negatives are mined.
Why not score every listing?
- Active listings
- 20,000,000
- Embedding size
- 64 dims
- Positives per batch
- 4,096
- Shared random negatives per batch
- 1,000one set reused by every positive in the batch
- Full softmax, one example20,000,000 × 641.28 billion multiply-addsfrom Active listings and Embedding size
- Full softmax, one batch1.28 billion × 4,0965.24 trillion multiply-addsfrom Full softmax, one example and Positives per batch
- In-batch softmax (every positive against every other)4,096 × 4,096 × 641.07 billion per batch (≈ 4,900× cheaper)from Positives per batch and Embedding size
- In-batch plus the shared random set4,096 × (4,096 + 1,000) × 641.34 billion per batch (≈ 3,900× cheaper)from Positives per batch, Shared random negatives per batch and Embedding size
- Sampled softmax gives up an exact gradient for one that is thousands of times cheaper; which listings the sampler draws decides the bias that comes with it.
- Word2vec's negative sampling used k = 5–20 negatives per positive on small datasets and 2–5 on large ones (Mikolov et al. 2013). Retrieval systems use hundreds to thousands per positive because in-batch sharing makes them nearly free; YouTube's candidate generator sampled several thousand with importance weighting (Covington et al. 2016).
Where negatives come from
| Source | Cost | Hardness | Bias | Fix |
|---|---|---|---|---|
| Uniform random from the catalogue | Cheap; one listing-tower pass each | Easy | None relative to the catalogue, but stale and niche listings are drawn as often as live ones | Mix with harder sources |
| In-batch (other buyers' positives) | Free; vectors already computed | Medium | Proportional to popularity: popular listings are over-punished, and never-engaged listings are never drawn | logQ correction (Yi et al. 2019); mix in uniform negatives (Yang et al. 2020) |
| Popularity to the power 0.75 | Cheap | Medium | Deliberate, flattened popularity (word2vec's unigram^0.75) | Tune the exponent |
| Shown but not engaged (impressions) | Free from logs | Hard, but for the ranker's candidates | Tied to what the old system chose to show; poor for retrieval (EBR: 55% absolute recall loss in people search) | Use for the ranking stage instead |
| Mined hard (near neighbours of the query) | One ANN lookup per example | Hard | False negatives; alone, the model leans on non-text features and gets worse at text match (EBR) | Take ranks 101–500 (EBR), mixed with many easy ones; Hatchway caps them at 2 per positive |
Popularity bias and the logQ correction
Chance each listing is drawn as a negative
- In-batch (∝ frequency)
- Frequency^0.75
Data
| Listing | In-batch (∝ frequency) (%) | Frequency^0.75 (%) |
|---|---|---|
| Grey L-sofa | 64.3 | 58.2 |
| Kids' bicycle | 32.2 | 34.6 |
| Brass lamp | 3.2 | 6.2 |
| Record player | 0.32 | 1.1 |
- Uniform (25%): Share of negatives (%) = 25
What the bias does to recommendations
In a batch of 4,096 positives, the grey L-sofa turns up whenever anyone messaged about it, so in every other buyer's softmax it is a negative again and again. The gradient keeps pushing its vector away from queries it has nothing to do with, and it keeps doing so far more often than for a rare record player. The model ends up learning that popular means wrong, and popular listings sink in retrieval even for buyers who would want them. Raising frequency to the power 0.75 only softens this. The clean fix is to correct each logit for how often the item was likely to be sampled.
The logQ correction on two listings
- Grey sofa: chance of being drawn per draw (Q)
- 1 / 1,000
- Record player: chance of being drawn per draw (Q)
- 1 / 1,000,000
- Raw score s for both against one buyer's query
- 2.0
- Grey sofa's logit inside the training softmaxs − ln Q = 2.0 + ln 1,000 = 2.0 + 6.918.91from Raw score s for both against one buyer's query and Grey sofa: chance of being drawn per draw (Q)
- Record player's logit inside the training softmaxs − ln Q = 2.0 + ln 1,000,000 = 2.0 + 13.8215.82from Raw score s for both against one buyer's query and Record player: chance of being drawn per draw (Q)
- Gap between them15.82 − 8.91 = ln(1,000,000 / 1,000)6.91 nats, a factor of e^6.91 ≈ 1,000from Grey sofa's logit inside the training softmax and Record player's logit inside the training softmax
- Score used at serving timeraw s, no correction2.0 for bothfrom Raw score s for both against one buyer's query
- The sofa is drawn 1,000 times as often as the record player, and after the correction each of its appearances weighs about 1,000 times less in the softmax's denominator. The two effects cancel, so the sampled loss approximates the full one instead of penalising popularity (Yi et al. 2019, deployed in YouTube's retrieval).
- The correction lives only in the training loss. Serving ranks by the raw dot product; the correction does not boost anything at request time.
- Q has to be estimated as data arrives, because Hatchway's catalogue changes daily. Yi et al. estimate it from the training stream itself rather than from a fixed vocabulary count.
- Q is the chance of being drawn by whichever process produced that negative. The sketch's popularity share is right for in-batch negatives only. Hatchway's 1,000 uniform draws give each listing 1 / 20,000,000 per draw, so for a set that mixes both (the Mixed Negative Sampling recipe of Yang et al. 2020) the record player's Q is the blend: (4,096 × 1/1,000,000 + 1,000 × 1/20,000,000) ÷ 5,096 ≈ 1 / 1,230,000. Subtracting the popularity ln Q from a uniformly drawn listing would be wrong.
- Mined hard negatives come from an ANN lookup with no known draw probability, so Hatchway leaves them uncorrected; some teams down-weight them instead.
- Hatchway writes the correction as s − α·ln Q with a weight α: 0 turns it off and 1 is the full correction above. It keeps α = 1 and changes it only if head-versus-tail recall says so.
Mining hard negatives
Negative pipeline for one training day
Why skip the very top
The miner asks yesterday's index for the 500 listings nearest to each buyer's query and throws away the first 100. Facebook's embedding-retrieval team compared windows and found that negatives from ranks 101–500 gave the best recall (Huang et al. 2020); the paper does not say why. A plausible reason for Hatchway is that the very top holds relists, the same model of sofa from another seller, or listings the buyer would happily have messaged, and labelling those negative teaches the model the wrong lesson. Using a stronger scoring model to spot such hidden positives is covered in dense retrieval.
Two details keep the loop healthy. First, mining starts only after the model has trained on easy negatives for a while; a random model's neighbours are noise. Second, the index is rebuilt each night from the newest checkpoint, so the next day's negatives are hard for the current model rather than for one that has already learned them. Index internals are covered in ANN indexes.
In practice.
What published systems found, how Hatchway mixes its sources, and how to evaluate without being fooled by the sampler.
What large systems reported
Negatives per positive in one Hatchway batch
- Positives per batch
- 4,096
- Shared random negatives per batch
- 1,000
- Hard negatives per positive
- 2Hatchway's cap, borrowed from EBR's online-mining result
- In-batch negatives per positive4,096 − 14,095from Positives per batch
- Easy negatives per positive4,095 + 1,0005,095from In-batch negatives per positive and Shared random negatives per batch
- Easy to hard5,095 : 2≈ 2,500 : 1from Easy negatives per positive and Hard negatives per positive
- Extra listing-tower passes per batch1,000 + 4,096 × 29,192 (≈ 2.2× the positives)from Shared random negatives per batch, Positives per batch and Hard negatives per positive
- Hatchway sits far past EBR's 100:1 saturation point, so the hard negatives are a small, targeted addition to a bulk of cheap easy ones, not a replacement.
- The hard negatives cost more than the random ones: 8,192 extra listing embeddings per batch against 1,000. If the listing tower is heavy, cap hard mining at one per positive before touching the random set.
Negatives differ by stage
How the two stages hand candidates to each other is covered in multi-stage funnels, and a ranker trained on impressions is worked through in video ranking.
Evaluating a model trained with sampled negatives
Negatives sampled for training and negatives sampled for scoring are different choices. How sampled evaluation inflates a ranking metric, with worked numbers, is in ranking metrics.
Trade-offs.
The chosen recipe is first; the others stay visible so the reasoning can be checked.
- Pro:Mixed negative sampling (Yang et al. 2020); hard ones from ranks 101–500, added after a warm-up epoch
- Pro:A cheap bulk of easy negatives covers the whole catalogue
- Pro:Popularity bias is corrected in the loss
- Pro:Hard negatives teach teak sofa versus sheesham sofa
- Con:Needs a nightly re-index to feed the miner
- Con:The false-negative filter is one more thing to maintain
Listings nobody engaged with never appear as negatives, so the model never learns to push them down; logQ cannot fix items that are never sampled (Yang et al. 2020); Few hard cases; Quality depends on batch size
Inherits the old system's exposure bias; Poor retrieval recall (EBR)
Many false negatives; Unstable training; Loses to random negatives (EBR)
The knobs and what they trade
| Knob | Turning it up means | Watch |
|---|---|---|
| Batch size | More in-batch negatives per positive | Accelerator memory; step time |
| Random negatives per batch | Better tail and whole-catalogue coverage | Listing-tower compute |
| Hard negatives per positive | Finer distinctions | False negatives; Hatchway starts at 2, EBR's online-mining limit |
| Hard rank window (moving it toward the top) | Harder negatives | More false negatives |
| logQ weight α (logit s − α·ln Q; 0 = off, 1 = full) | Head and tail listings treated more evenly | Above 1, or with a stale Q, rare listings flood results |
| Popularity exponent | 0 is uniform, 1 is raw frequency | Too low wastes draws on dead listings |
What goes wrong
| Failure | Impact | Detection | Mitigation | Meanwhile |
|---|---|---|---|---|
| Relists slip past the false-negative filter6False-negative filter | The model learns to push away copies of what buyers want, and "More like this" stops showing the same sofa from other sellers | Share of mined negatives with the same seller or a near-identical photo hash as the positive | Perceptual photo hashing plus title similarity, and exclude everything the buyer engaged with in the last 30 days | Recall on near-duplicate queries drops while overall recall looks fine |
| The frequency sketch goes stale8Item-frequency sketch | New popular listings get too little correction and sink; items that have faded keep an outdated correction | Compare the sketch's top listings with the last hour of positives | Decay the counts over time and alert when the sketch has not updated | Training continues with a biased loss |
| The nightly re-index fails4Previous model's ANN index | The miner keeps using an older model's neighbours, which the current model already handles | Index build age in the training dashboard | Skip hard mining for that day rather than mine from a stale index for long | Training falls back to in-batch and random negatives |