Advanced 24 min read RecSysembeddingsnegative samplingcontrastivelogQ correction

Representation Learning for RecSys

Two-tower objectives, negative sampling (in-batch, hard, popularity-corrected) — why sampling dominates retrieval quality

Picture every user and every item as a point in the same embedding space: training's whole job, every step, is to drag a user's point closer to the items they'd click and further from the ones they wouldn't — pull here, push there, nothing more exotic than that. Here's a thought experiment that makes the point concrete before naming it: imagine training a shallow one-layer tower and a much deeper four-layer tower against the *same* lazy random negatives — with the negatives left alone, going deeper buys at most a small recall bump, because both towers are still learning from the same weak push-pull signal. Now imagine leaving that shallow tower exactly as it is and changing only *which points it gets pushed away from* — the negative-sampling scheme. That single change moves recall by far more than the encoder swap did, because the negatives are what define the push-pull signal in the first place, not the tower's depth. So the *encoder architecture* is rarely what limits recall — the negative-sampling scheme is. This module is about why that is, and about the single most famous failure mode in the field: naive in-batch negatives collapsing under popularity skew. Before you read the mechanism: if every negative comes from other users' positives in the same batch, what happens to the one item almost everybody likes — does it get pulled toward users, or pushed away?

The two-tower objective is contrastive: pull the positive together, push negatives apart. You have positives (user *u* clicked item *i⁺*) but no labelled negatives. Training frames it as a softmax over items: maximise the probability of *i⁺* against a set of sampled negatives, i.e. sampled softmax — equivalently the InfoNCE / contrastive loss L = −log( exp(u·v⁺) / (exp(u·v⁺) + Σⱼ exp(u·vⱼ⁻)) ). The gradient literally *pulls* u toward v⁺ and *pushes* it away from each negative vⱼ⁻. So the whole learning signal is shaped by which negatives you put in that denominator — the positives are fixed by the data; the negatives are your design choice, and they are where retrieval quality is won or lost.

The three negative-sampling schemes, and their tradeoffs

- In-batch negatives — the cheap default: within a batch of B (user, item) pairs, use every *other* user's positive as a negative, giving B×(B−1) negatives for free with no extra lookups. The problem: batches are sampled from the *interaction* distribution, so popular items appear as negatives far more often than rare ones. - Hard negatives — mined items that score *high but weren't clicked* (near-misses). Random in-batch negatives are usually trivially easy (a cooking video vs a random car part → near-zero gradient, nothing learned); hard negatives sit right on the decision boundary and produce the gradient that actually sharpens fine distinctions, which is what lifts recall. - Popularity / logQ correction — because in-batch sampling over-represents popular items as negatives, they get systematically *over-penalised*; the fix is to subtract each item's log sampling probability from its logit (u·vⱼ − log Q(j)), the sampled-softmax correction, restoring an unbiased objective.

A worked pass through the numbers, so this isn't just formulas. Take a batch of B = 256 (user, item) pairs: in-batch negatives give B×(B−1) = 256 × 255 = 65,280 negatives for free, one lookup each. Now take one popular item and one long-tail item that both happen to score the same raw dot product against a user, u·v = 2.0. Q(j) here isn't learned or guessed — it's estimated directly from a streaming count of how often each item appears as a positive in the interaction log (the same trick the YouTube two-tower retrieval paper uses): say the popular item is Q(popular) = 0.01 (roughly 1 in 100 interactions) and the long-tail item is Q(rare) = 0.0001 (roughly 1 in 10,000). The correction u·v − log Q(j) gives: popular → 2.0 − log(0.01) = 2.0 − (−4.61) = 6.61; rare → 2.0 − log(0.0001) = 2.0 − (−9.21) = 11.21. Both scores go up (subtracting the log of a fraction always adds a positive number), but the rare item's score jumps nearly twice as far — 9.21 versus 4.61 — because it was sampled far less often than its raw score alone would justify. That's the correction working: it inflates an under-sampled item's contribution to the denominator by more than an over-sampled item's, so a popular item that shows up as a negative in almost every batch stops getting a disproportionate share of the "push away" gradient just because it's popular.

Regularisation and temperature are a separate, secondary lever — they shape geometry, not sampling bias. L2 penalties on the embedding tables and unit-normalising u and v control how spread out the embedding space is and stop any one dimension from dominating; a temperature term scaling the logits (u·v / τ) controls how sharply the softmax separates near-tied scores. Neither one touches *which* negatives get sampled, so neither corrects for popularity skew — a heavily-regularised, low-temperature model trained on the same popularity-skewed in-batch negatives still learns "popular = negative." That's why the sampling scheme is the first-order lever on recall and regularisation/temperature the second: fix the negatives first, then use regularisation and temperature to sharpen a geometry the sampling already got right.

The classic failure: in-batch popularity collapse. Follow the mechanism. Popular items are positives for *many* users, so in any batch they show up as *negatives* for everyone whose positive they aren't. The contrastive gradient therefore pushes almost every user's embedding *away* from popular items — even users who would love them. The model learns "popular = negative," over-suppresses head items, and in the pathological case the popular-item embeddings get pushed into a degenerate region and retrieval collapses: recall on exactly the items most users want craters. This is why the logQ correction isn't a nicety — it's what keeps in-batch training from eating itself, and why an interviewer probing retrieval will ask about it. The takeaway that separates levels: *before you deepen the encoder, fix the negatives* — sampling scheme dominates recall.

Key points

The two-tower objective is contrastive (sampled softmax / InfoNCE): maximise exp(u·v⁺) against a denominator of sampled negatives. The positives are fixed by the data; the *negatives in the denominator* are the design choice, so retrieval quality is decided by the sampling scheme, not mainly by encoder depth.
In-batch negatives are free but popularity-biased. A batch of B pairs yields B×(B−1) negatives with no extra lookups — but batches follow the interaction distribution, so popular items appear as negatives disproportionately and get over-penalised.
Hard negatives supply the gradient that lifts recall. Random negatives (a cooking video vs a random car part) are trivially separable → near-zero gradient → nothing learned. Hard negatives (high-scoring non-clicks near the boundary) produce real gradient that sharpens fine distinctions — the actual recall driver.
The logQ / popularity correction de-biases the objective. Subtract each item's log sampling probability from its logit (u·vⱼ − log Q(j)); this sampled-softmax correction removes the systematic over-suppression of popular items that in-batch sampling introduces.
In-batch popularity collapse is the classic failure. Popular items appear as negatives for nearly everyone, so the gradient pushes almost all users away from them; the model learns "popular = negative," over-suppresses head items, and recall on the most-wanted items collapses. The logQ correction is what prevents this — sampling scheme, not encoder, dominates recall.

Takeaway

Retrieval embeddings are trained with a contrastive (sampled-softmax / InfoNCE) objective, and the negative-sampling scheme — not the encoder architecture — dominates recall. In-batch negatives are free but follow the interaction distribution, so popular items appear as negatives for nearly everyone; naive in-batch training therefore pushes almost every user away from popular items ("popular = negative"), over-suppressing the head until retrieval collapses. Hard negatives supply the boundary gradient that lifts recall, and a logQ / popularity correction (subtract log sampling probability) de-biases the objective and is what keeps in-batch training from eating itself.

Recap

Two-tower objective is contrastive (sampled softmax / InfoNCE): maximise exp(u·v⁺) against a denominator of sampled negatives; the gradient pulls u toward v⁺ and pushes it from each negative. Positives are fixed by data — the *negatives in the denominator* are the design choice that decides recall.
In-batch negatives: free (B×(B−1) per batch, no extra lookups) but sampled from the interaction distribution, so popular items appear as negatives disproportionately and get over-penalised.
Hard negatives: random negatives are trivially easy (near-zero gradient, nothing learned); mined high-scoring non-clicks sit on the boundary and supply the gradient that sharpens fine distinctions — the real recall driver.
logQ / popularity correction: subtract each item's log sampling probability from its logit (u·vⱼ − log Q(j)) to undo in-batch over-representation of popular items — restoring an unbiased objective.
In-batch popularity collapse (the classic failure): popular items appear as negatives for nearly everyone → gradient pushes almost all users away from them → model learns "popular = negative," over-suppresses the head, and recall on the most-wanted items collapses. The logQ correction is what prevents it. Bottom line: fix the negatives before deepening the encoder — sampling dominates recall.

Check your understanding

Q1. In a two-tower retriever trained with sampled softmax / InfoNCE, why is the choice of negatives often more decisive for recall than making the encoder deeper?

A) Deeper encoders systematically overfit past 3 layers in two-tower architectures, so a shallow 1-layer encoder always wins regardless of negative sampling strategy.
B) Positives are fixed by the data, so negatives in the softmax denominator shape the whole learning signal; a deeper encoder only refines a signal the negatives define.
C) Encoder depth is documented to affect only serving latency and never representation accuracy, since two-tower dot-product scoring is depth-invariant by construction.
D) Negatives directly rewrite the ANN index's HNSW graph geometry at training time, and index geometry is the sole factor determining recall in production.

Q2. Why do purely random in-batch negatives often produce near-zero gradient and fail to lift recall, and what fixes it?

A) Random negatives are documented to cause exploding gradients in the contrastive loss above a batch size of 512; gradient clipping at norm 1.0 is the standard fix that restores recall.
B) A random negative is trivially far from the positive, so the contrastive loss is already near zero and its gradient is tiny; hard negatives near the boundary produce real gradient.
C) Random negatives are simply too few in number; increasing batch size from 256 to 1024 alone is always sufficient to close the recall gap without any change to the sampling logic.
D) They don't — uniformly random negatives are provably optimal for a contrastive objective, and hard-negative mining only ever improves the downstream ranking stage, never retrieval.

Q3. Trace the in-batch popularity-collapse failure mode. Why does naive in-batch training over-suppress popular items?

A) Popular items develop measurably larger-norm embedding vectors over training, and those larger dot products saturate the softmax denominator, numerically drowning out every other term.
B) Popular items are positives for many users, so they appear as *negatives* for everyone else in the batch; the gradient pushes nearly all users away from them, over-suppressing the head.
C) Popular items are actually sampled less often as in-batch negatives than rare ones, leaving them under-trained with embeddings that stay close to their random initialization.
D) The ANN index's HNSW construction explicitly deprioritises high-degree graph nodes during indexing, which silently drops popular items from the candidate set at query time.

Q4. Select the *two* correct statements about what the logQ (sampled-softmax) correction does and why it matters for in-batch training.

A) It subtracts each item's log sampling probability from its logit (u·vⱼ − log Q(j)), undoing the fact that in-batch sampling over-represents popular items as negatives.
B) Without it, popular items are systematically over-penalised, which is the direct mechanism driving the popularity-collapse failure described earlier in this module.
C) It adds an L2 penalty term with coefficient λ=0.01 directly to the embedding tables, a regularization technique that is unrelated to negative-sampling bias.
D) It replaces the softmax denominator with a per-negative sigmoid loss, a substitution that is strictly required whenever training on implicit rather than explicit feedback.

Q5. A retriever trained with in-batch negatives under-recommends genuinely relevant popular items, while a colleague's model with the same encoder does not. What is the most likely difference, and the cross-cutting lesson?

A) The colleague used a measurably deeper 6-layer encoder instead of your 3-layer one; deepen yours to match and the popularity under-recommendation will resolve on its own.
B) The colleague applied a logQ / popularity correction, de-biasing the over-representation of popular items as negatives — same encoder, different sampling scheme.
C) The colleague used a larger embedding dimension, d=256 instead of d=64, which is documented to always fix popularity bias regardless of the sampling scheme used.
D) The colleague simply trained for more epochs, roughly 40 instead of 10; extending training duration alone is sufficient to remove popularity bias from a contrastive objective.

Q6. Where does embedding regularisation fit relative to the negative-sampling story?

A) Regularisation is a full substitute for negative sampling — with sufficiently strong L2 (λ≈0.1) on the embedding tables, a contrastive model needs no explicit negatives at all.
B) It's complementary and secondary: L2/normalisation and temperature control geometry but don't fix biased negatives — sampling is the first-order lever, regularisation the second.
C) Regularisation, specifically unit-norm constraints on item embeddings, is documented as the direct mechanical cause of in-batch popularity collapse and should be disabled.
D) Embedding regularisation via weight decay is only ever applied at the ranking stage's dense layers, and is architecturally inapplicable to a retrieval-stage two-tower model.

Try it interactively

ML Systems Lab is a free interview-prep platform for ML engineers — work through the full interactive module, quizzes, and drills.

Open ML Systems Lab →