Candidate Generation & Retrieval
Two-tower embeddings, ANN retrieval, dot-product scoring, in-batch negatives
Retrieval has to do something that sounds contradictory: score a user against *every* item in the catalog, cheaply enough to run at request time. The trick that makes it possible is decoupling — and it's the single most important architecture in modern RecSys.
Why joint scoring fails and the two-tower model fixes it. The most accurate way to score a (user, item) pair is to feed both into one model so it can weigh every cross-interaction. But then the item's representation *depends on which user is asking*, so you must recompute all 10M item scores fresh per request — the impossible arithmetic again. The two-tower model breaks the dependency: a user tower encodes the user into a vector, an item tower encodes each item into a vector in the *same* space, and similarity is a plain dot product u·v. Because an item's embedding no longer depends on the user, you compute *all* item embeddings offline, once, and store them.
ANN turns "score everything" into "look up neighbors." With every item pre-embedded, retrieval becomes: encode the one live user (one forward pass), then find the item vectors nearest to u. Exact nearest-neighbor over 10M vectors is still too slow, so we use Approximate Nearest Neighbor (HNSW, IVF, ScaNN) — index structures that trade a little recall for a huge latency win, returning the top few hundred neighbors in ~10ms. Dot-product (or cosine) is chosen precisely because ANN indexes are built for it.
Training: in-batch negatives are the standard recipe, and *why* matters. You have positives (user clicked item) but no explicit negatives. The trick: within a training batch, treat every *other* user's clicked item as a negative for this user — one batch of B pairs yields B positives and B×(B−1) negatives for free, trained with a softmax/contrastive loss. But random in-batch negatives are too *easy* — separating a clicked cooking video from a random car-parts listing gives near-zero gradient and teaches nothing subtle. So you add hard negatives: high-scoring-but-not-clicked items that force the model to learn fine distinctions. Popularity also biases in-batch negatives (popular items appear as negatives more often, getting over-penalized), which is corrected with a logQ / sampled-softmax correction. Concretely, it subtracts each item's log sampling probability from its logit before the softmax, so an item isn't over-penalized just for being sampled as a negative more often.
Retrieval's output is a shortlist, not a final answer. The few hundred candidates ANN returns still aren't ordered — that's the next module's job. Ranking takes exactly this shortlist and runs a more expensive model over it to produce the final top-k.
Key points
- Two towers exist to make item embeddings query-independent. A joint (cross-attention) scorer ties an item's representation to the querying user, forcing 10M fresh scores per request. Two separate towers + a dot product let you precompute all item vectors offline and index them once.
- Dot-product / cosine is chosen because ANN indexes are built for it. Retrieval = encode one user live, then ANN-lookup nearest item vectors (~10ms over 10M). The item tower can be arbitrarily expensive (it runs offline); the user tower must be cheap (it runs per request). That asymmetry is the whole point. Retrieval's output — the few hundred nearest neighbors — is a shortlist for the ranking stage next, not the final recommendation list.
- In-batch negatives give free negatives, but random ones are too easy. B positives per batch yield B×(B−1) negatives at no cost. Random negatives produce tiny gradients; hard-negative mining (high-scoring non-clicks) forces fine distinctions and is what actually raises recall.
- Popularity bias in negatives needs a correction. Popular items appear as in-batch negatives disproportionately and get over-suppressed; a logQ / sampled-softmax correction (subtract log sampling probability from the logit) restores an unbiased objective.
Two-tower retrieval decouples user and item encoding so item embeddings can be precomputed offline and ANN-indexed — turning "score 10M items" into "encode one user + a ~10ms neighbor lookup." It's trained with in-batch negatives plus hard-negative mining (random negatives are too easy) and a logQ correction for popularity bias. The output is a shortlist of a few hundred candidates handed to the ranking stage next — not a final recommendation list.
Recap
- Joint scoring is most accurate but impossible at retrieval scale: it ties an item's representation to the querying user, forcing 10M fresh scores per request. Two-tower breaks the dependency — user tower + item tower into a shared space, similarity = dot product u·v.
- Query-independent items → precompute offline + ANN: compute all item embeddings once, index them (HNSW/IVF/ScaNN). At request time: encode one user (one forward pass) + ANN lookup for nearest item vectors ≈ 10ms over 10M. Dot-product/cosine is chosen because ANN is built for it.
- Cost asymmetry is the design lever: the item tower runs offline so it can be big and slow; the user tower runs live so it must be cheap. Exploit this — put expensive features on the item side.
- In-batch negatives = free negatives but too easy: a batch of B pairs gives B positives + B×(B−1) negatives. Random negatives yield near-zero gradient; hard-negative mining (high-scoring non-clicks) forces fine distinctions and actually lifts recall.
- Popularity bias in negatives needs a correction: popular items appear as negatives disproportionately and get over-suppressed → apply a logQ / sampled-softmax correction to restore an unbiased objective. Retrieval's output is a shortlist of a few hundred candidates, not a final list — the ranking stage (next module) takes over from here to produce the ordered top-k.
Check your understanding
Q1. Why can't a cross-attention model that jointly encodes (user, item) be used for retrieval, even though it is more accurate than a two-tower model?
- A) Cross-attention overfits on large catalogs above roughly 1M items, since its parameter count scales quadratically with vocabulary size and it memorizes training pairs instead of generalizing.
- B) Its item embedding depends on the querying user, so nothing can be precomputed — all 10M items must be scored fresh per request.
- C) Cross-attention can't emit fixed-length vectors, so downstream HNSW/IVF-PQ index-builders reject its variable-width output during the offline indexing pass.
- D) The dot product ANN relies on is mathematically undefined for cross-attention outputs, since those outputs live in a non-Euclidean similarity space by construction.
Q2. Your two-tower retriever gets recall@100 of only 0.55. A teammate proposes switching from random in-batch negatives to hard-negative mining. Why does this attack the recall problem specifically?
- A) Hard negatives shrink the effective embedding dimension from 128 to roughly 32, letting the ANN index scan a wider candidate set within the same ~10ms latency budget.
- B) Random negatives produce near-zero gradient (trivially easy), so the model never learns fine distinctions; hard negatives sharpen that boundary and lift recall.
- C) Hard negatives recalibrate the raw dot-product scores into true probabilities, so the ANN index's approximate distances become mathematically exact rather than approximate.
- D) They don't touch recall at all — hard-negative mining only sharpens ranking precision downstream, once retrieval has already produced its candidate set.
Q3. After training with in-batch negatives, your retriever systematically *under*-recommends genuinely relevant popular items. Select the *two* statements that correctly diagnose the cause and the fix.
- A) Popular items appear as in-batch negatives far more often than rare ones, because batches are sampled from the interaction distribution — so they get systematically over-penalized during contrastive training.
- B) Subtracting each item's log sampling probability from its logit (the logQ / sampled-softmax correction) restores an unbiased contrastive objective and is the standard fix.
- C) The ANN index is silently dropping popular items from its HNSW graph; rebuilding it with a larger ef_search parameter, e.g. 200 instead of 40, resolves the drop.
- D) Popular items accumulate stale embeddings because their high query traffic causes cache eviction in the serving layer; nightly full-tower retraining refreshes them.
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 →