Candidate generation — from CF to two-tower
The retrieval stage has one job: maximize recall at K₁ candidates, with a per-item cost measured in microseconds. That single constraint forces every architectural decision below.
Restating the problem from first principles
Lesson 1 established the funnel. Now zoom in on the first stage. The retrieval stage sees the full catalogue N ≈ 10⁸ – 10¹⁰ and must emit K₁ ≈ 10² – 10⁴ items in around 10 ms. That is roughly 1 – 100 ns of compute per catalogue item if you scan linearly, or ~10 µs per returned item if you have a sub-linear index. Either way: per-item compute is fixed and tiny.
Two architectural constraints follow immediately, and the rest of this lesson is downstream of them:
- Item representations must be precomputable. If scoring an item requires the user's identity as a model input at training time (e.g., a learned embedding keyed on
user_idshared between the user and item sides), you cannot build an item-only index. Every new user breaks it. - No cross-features at the top. If the final score is f(user_features, item_features) with a non-decomposable interaction (e.g., a transformer that attends across user and item tokens), then scoring item i requires the user's representation at index time. You're forced into a full cross-product over N items at request time, and you're back to the 28-hour problem from lesson 1.
The fix to both is the same: the final operation between the user side and the item side must be a late, cheap interaction — concretely, a dot product or cosine. This is called the two-tower constraint, and it is the single most important architectural fact about retrieval.
Collaborative filtering — the historical baseline
The earliest serious retrieval systems were collaborative filtering (CF). The interaction matrix R ∈ ℝU×I has a value when user u rated or clicked item i, and zeros (or missing) elsewhere. Two flavors:
- Item-item CF. Compute similarity between items by taking the cosine (or adjusted-cosine, mean-centered per user) between their columns of R. To recommend for user u, look at items u already engaged with, retrieve their nearest neighbours, union and de-duplicate. Famously what powered Amazon recommendations in the 2000s.
- User-user CF. Symmetric: similarity over rows of R. Recommend items popular among u's nearest user-neighbours.
CF is interpretable ("people who liked X also liked Y"), needs no item features, and works surprisingly well on dense interaction data. But it inherits three weaknesses that motivate everything that comes after: cold start (new items have no column, new users have no row), sparsity (when R is > 99.9% empty, cosines are noisy), and popularity bias (popular items co-occur with everything and dominate the neighbour lists).
Swing — popularity-debiased item-item CF
The third weakness — popularity bias — is severe enough that production i2i rarely uses raw co-occurrence. Walk through why it fails. Plain ItemCF scores a pair (i, j) by how many users clicked both, optionally normalized by each item's frequency. The problem: a megahit that 40% of all users have clicked will co-occur with everything. Those co-clicks are coincidental — the two users who both clicked the megahit and item j probably clicked the megahit for unrelated reasons. Co-occurrence count alone cannot tell a coincidental overlap from a meaningful one, so the neighbour list of every item fills up with the same few head items, and i2i collapses into a popularity recommender wearing a personalization costume.
Swing (the i2i algorithm behind Alibaba's Taobao recall) fixes this by asking a sharper question: do the two users who both clicked items A and B agree on much else? If user u and user v both clicked A and B but otherwise have almost-disjoint histories, their shared interest in this specific pair is a strong, non-coincidental signal — there is a real "swing" between A and B that brought two very different people to the same two items. If instead u and v overlap on dozens of items, their co-click on (A, B) is cheap: they agree on everything, so this pair tells you little. Swing therefore weights each co-clicking user pair by the inverse of how much that pair overlaps:
swing(i, j) = Σu ∈ Ui∩Uj Σv ∈ Ui∩Uj, v≠u 1 / ( α + |Iu ∩ Iv| )
Here Ui is the set of users who clicked item i, Iu is the set of items user u clicked, and α is a smoothing constant (typically α ≈ 1 – 5) that keeps the denominator finite when two users share nothing. The double sum ranges over pairs of users who both engaged with i and j; each such pair contributes 1/(α + |Iu ∩ Iv|). Two users with a small intersection contribute a large weight; two users whose histories overlap heavily (the broadly-active "everything-clickers" that drive popularity bias) contribute almost nothing. A common refinement also scales each user's term by 1/√(|Iu|) so that a hyperactive user — who is in the co-click set of countless pairs — does not dominate, the same intuition applied to single users instead of pairs.
Take α = 1. Two candidate item-pairs, each with exactly 3 co-clicking user pairs — so raw co-occurrence cannot tell them apart.
Pair P = (megahit movie, megahit soundtrack). The three user-pairs that co-clicked both are all heavy users with broad, heavily-overlapping histories — their pairwise intersections are |Iu ∩ Iv| = [60, 80, 100] items. Swing score:
swing(P) = 1/(1+60) + 1/(1+80) + 1/(1+100) ≈ 0.0164 + 0.0123 + 0.0099 ≈ 0.039
Pair Q = (niche jazz album, a specific vintage turntable). The three user-pairs that co-clicked both are otherwise near-strangers — intersections |Iu ∩ Iv| = [1, 2, 4] items. Swing score:
swing(Q) = 1/(1+1) + 1/(1+2) + 1/(1+4) = 0.5 + 0.333 + 0.2 = 1.033
Raw co-occurrence calls these pairs identical (both = 3). Swing ranks the niche pair ~26× higher (1.033 vs 0.039), because its co-clicks come from users who agree on this pair and almost nothing else — a clean, non-coincidental signal. The megahit pair's co-clicks come from people who click everything, so Swing correctly discounts them. That single denominator is the whole mechanism: it converts "how surprising is this co-click, given how much these two users overlap anyway?" into a number.
Compute-wise, Swing is heavier than plain ItemCF — it iterates over pairs of users within each item's click set rather than counting co-clicks once — so it is built offline on a batch cluster (the same Spark / map-reduce machinery as the ItemCF co-occurrence matrix in lesson 19) and the resulting top-k neighbour table is loaded into the online i2i recall channel. In the multi-source taxonomy below, Swing is what makes the recent-engagement / i2i source worth keeping next to the two-tower models: it captures behavioural item-item structure the towers' dot product smooths away, without the popularity collapse of raw co-occurrence.
Matrix factorization — CF, but with a generalization
Funk's Netflix Prize recipe (2006) reframed CF as a low-rank factorization. Approximate the sparse interaction matrix as a product of two dense low-rank matrices:
R ≈ U · VT, U ∈ ℝ|users|×d, V ∈ ℝ|items|×d
Each user gets a d-dimensional embedding ui; each item gets vj; the predicted preference is ⟨ui, vj⟩. The loss is either squared error on observed ratings (explicit feedback) or a pairwise ranking loss like BPR (Rendle et al. 2009 — Bayesian Personalized Ranking) on implicit feedback:
LBPR = − Σ(u, i⁺, i⁻) log σ(⟨u, vi⁺⟩ − ⟨u, vi⁻⟩)
where i⁺ is an item the user engaged with and i⁻ is sampled from the catalogue. SVD++ and friends add bias terms and implicit-feedback features but the skeleton is the same.
How you actually fit it: Funk-SVD and ALS
Two names dominate the classical literature, and both are worth getting right. "SVD" in recsys is not the linear-algebra SVD. Textbook SVD factorizes a fully observed matrix; here R is > 99% unobserved, and treating the missing entries as zeros is wrong (a missing rating is not a zero rating). So Funk's recipe minimizes squared error over the observed entries only, with L2 regularization, by SGD:
minp, q Σ(u, i) ∈ obs (rui − pu · qi)² + λ(‖pu‖² + ‖qi‖²)
In practice you add bias terms, which carry a surprising fraction of the signal: r̂ui = μ + bu + bi + pu · qi, where μ is the global mean, bu the user's leniency, and bi the item's baseline popularity. The dot product only has to explain what's left after the biases.
ALS (Alternating Least Squares) optimizes the same objective by a different route. Fix the item factors q and the objective becomes an ordinary ridge regression in each user's pu — solvable in closed form. Then fix p and solve for q. Alternate to convergence. Because each user's solve is independent given the item factors (and vice versa), ALS parallelizes embarrassingly across users and items — which is why it's the matrix-factorization implementation that ships in Spark MLlib. It's also the natural fit for implicit feedback (no explicit ratings, only clicks/plays): the Hu–Koren–Volinsky weighted-ALS treats every (user, item) pair as observed but attaches a confidence weight that grows with interaction count, so unobserved pairs are weak negatives rather than ignored.
The reason MF matters in 2025 is that it is structurally a special case of a two-tower model with one-hot input features. Read that sentence twice. ui = UT · onehot(user_id) is exactly what a single embedding-lookup layer computes. So MF is a two-tower model whose only input feature on each side is the ID — the linear, ID-only special case. The neural two-tower retriever generalizes it by replacing the lookup-embedding dot product with learned towers over features. Everything that follows is "what if the towers had more features and more layers?"
The two-tower model
Generalize MF: replace each embedding lookup with a deep network that takes arbitrary features.
Crucially: the two towers do not share parameters. They can be wildly different architectures — a transformer over the user's recent watch history on one side, a CNN over the thumbnail and an embedding bag over the title on the other. They only need to produce vectors in the same d-dimensional space, and the final operation is a dot product. d is small by neural-net standards: 64 – 256 is typical, because d sets the ANN index size and recall trade-off (lesson 3).
Training is done with sampled softmax or in-batch negatives: in a minibatch of (user, positive_item) pairs, every other item in the batch is treated as a negative for every user. The loss is
L = − Σu log [ exp(⟨u, v+⟩ / τ) / Σv ∈ batch exp(⟨u, v⟩ / τ) ]
This sidesteps the impossibility of a softmax over N = 10⁹ classes. There are well-known biases this introduces (popular items appear more often as in-batch negatives, so they get over-penalized) and well-known fixes (logQ correction, mixed-negative sampling) — those are the subject of lesson 6.
Why the late-interaction constraint is non-negotiable
Junior candidates often propose "what if I just add a few cross-features at the top of the two-tower?" — e.g., a user × item ID interaction, or a small MLP over [u; v; u⊙v]. Watch what happens at serving time:
| Architecture | Serving cost per request | Index possible? |
|---|---|---|
| ⟨u, v⟩ (pure two-tower) | 1 user forward + ANN lookup (O(log N) or O(N · d) linear scan) | Yes — item vectors are static. |
| MLP([u; v]) (late MLP on top) | 1 user forward + N × MLP forward — no factorization | No — every item needs the user vector concatenated and pushed through the MLP. |
| cross-attention(u tokens, v tokens) | Same as above, worse. N × attention per request. | No. |
| FM-style: u, v, ⟨u, v⟩, plus learned bias terms | Reducible to a dot product over an augmented vector (concat the bias dims into u and v). OK. | Yes, with care. |
The principle: any operation between the user side and the item side that is not a dot product (or that can't be algebraically rewritten as one) breaks the index. That's the architectural cost of expressiveness. The ranker can afford it — it sees K₁ = 10³ items, not N = 10⁹. The retriever cannot.
One retriever is never enough — multi-source retrieval
A single two-tower model captures one notion of relevance. Production systems run several retrieval sources in parallel and union their outputs, because each source captures a different slice of the catalogue.
| Source | What it captures | Failure mode in isolation |
|---|---|---|
| Collaborative two-tower | Co-engagement patterns. Strongest signal on head queries / popular items. | Item cold start. Popularity bias. |
| Content two-tower | Semantic match on item features (text, image, taxonomy). Scoreable on day-zero items. | Misses purely behavioural patterns (item A and item B share no content but co-occur in real users). |
| Recent-engagement retrieval | Item-item nearest neighbours of items the user just touched. Captures session intent. | Echo chamber within the session; doesn't broaden interests. |
| Popularity / trending | The (regional, daily) top items, irrespective of user. Cheap safety net. | Non-personalized. Drowns the tail. |
| Exploration | Random or Thompson-sampled items, often weighted toward items with low impression count. | By design noisy; needs the ranker to filter. |
YouTube's recsys is the canonical example: Covington, Adams, Sargin (2016) — Deep Neural Networks for YouTube Recommendations — describes a multi-source retrieval setup, and later writeups indicate the production system fans out to more than ten candidate sources. Each is a small, focused model with its own training data and ANN index. The ranker reconciles them.
Cold start, solved in the tower features
The seductive answer to cold start is "use a content-based source." The deeper principle: cold start is solved by which features go into the tower, not by which source you pick.
- New users. If the user tower's only input is
user_id(i.e., a learned embedding lookup), a new user has a random embedding and recommendations are useless. If the user tower also consumes context features (device, locale, query, time-of-day, demographic priors), then a new user has a sensible vector from request 1. - New items. Same on the item side. If the item tower consumes only
item_id, a new item is invisible until it accrues clicks. If the item tower consumes content features (title, image, creator, category), it has a sensible vector at indexing time and is retrievable from day zero. This is why content towers are essential for marketplaces with fresh inventory (jobs, news, listings, ads).
In-tower features get a fresh item a reasonable vector, but that is not the whole story at the retrieval stage. A brand-new item with a sensible content vector still loses every dot-product comparison to mature items that have accumulated engagement signal, so it may never enter K₁ — and an item that is never retrieved never accrues the clicks it needs to graduate, the classic cold-start feedback trap. The retrieval-stage countermeasure is a dedicated cold-start recall channel with a protected exposure budget: reserve a small fraction of the K₁ slots (commonly ~5%) exclusively for under-exposed items, so they are guaranteed a path into the funnel regardless of their score against the head. This is the retrieval-side hook only — the graduation rule (when an item leaves the cold pool), the bandit / Thompson-sampling exposure ramp, and the cold-start-specific metrics belong to the full treatment in lesson 15 and lesson 38. The exploration source in the mixer below is the simplest instance of this channel.
The four retrieval architectures, compared
| Item-item CF | Matrix factorization | Two-tower (content) | Two-tower (collaborative) | |
|---|---|---|---|---|
| Cold start (new items) | Bad — no column | Bad — no vj learned | Excellent — content features carry it | Good if tower has content features |
| Cold start (new users) | OK — works from first click | Bad — no ui learned | Excellent if user tower has context features | Good if tower has context features |
| Expressiveness | Low | Low — bilinear only | Medium — depth of tower | Medium — same, with behavioural signal |
| Sparsity tolerance | Bad — needs co-occurrence | Better — embeds through structure | Best — features fill the gaps | Best — features + behavior |
| Scalability (serving) | Pre-compute item-item table, O(I²) store | ANN over vj | ANN over vj | ANN over vj |
| Ease of debugging | Very high — "neighbours of X" | High — inspect embeddings | Medium — feature attribution | Lower — entangled signals |
Interactive · the candidate-sources mixer
Allocate your K₁ budget across five candidate sources and read the diagnosis. The numbers are illustrative toy estimates — the point is to feel how the trade-offs interact, not to calibrate a real system.
Where retrieval breaks — and what production fixes look like
Three failure modes specific to the retrieval stage. Each is the root of a real interview question and a real production incident.
| Failure | Symptom | Production fix |
|---|---|---|
| Retriever ↔ ranker mismatch | The ranker scores items highly that the retriever never surfaces, so improving the ranker offline does nothing online. The two models were trained on different objectives and disagree about what is "good." | Distill the ranker's scores into the retriever (the retriever's loss includes the ranker's verdict on hard negatives), or periodically mine the ranker's top-K items the retriever missed and add them as positives. This is the cross-stage version of the funnel mismatch from lesson 1. |
| Multi-source slot waste | You add a 6th source and online recall barely moves. The new source's candidates overlap heavily with sources you already had, so the extra K₁ slots are spent on duplicates. | Measure incremental recall (recall the source adds that no other source covers), not raw recall. Allocate K₁ by marginal contribution. A source with 90% raw recall but 5% incremental recall earns 5% of the slots, not 90%. |
| In-batch popularity bias preview · lesson 6 | Offline recall looks fine, but online the head dominates and the tail collapses. Popular items appear as in-batch negatives in nearly every batch, so the model systematically pushes their scores down — except they are so over-represented that the net effect distorts the whole geometry. | logQ correction: subtract log q(j) from each in-batch score to cancel the sampling frequency, so an item is neither rewarded nor punished for merely being popular. Built in detail in lesson 6. |
Interview prompts you should be ready for
- "Why don't you train one model that takes (user, item) features and outputs a score, then retrieve top-K from that?" (Probes: do you understand that no cross-features at the top is what makes the item index precomputable? Compute the cost: N × MLP_forward per request.)
- "Walk me through the loss function of a two-tower model." (Sampled softmax / in-batch negatives, temperature, logQ correction. Bonus if you mention popularity bias of in-batch negatives and the correction for it.)
- "Your two-tower retrieval has terrible recall on long-tail items. Diagnose." (Probes: item tower starved of content features so tail items have noisy embeddings; in-batch negatives over-penalize popular items but the tail isn't actually being trained on; missing exploration source; ranker filters tail out so positive labels never accumulate.)
- "When would you use matrix factorization in 2025 instead of a two-tower model?" (Honest answer: rarely, but — tiny catalogue, dense interactions, interpretability requirement, no item features available, baseline you need to ship in a week. MF is a special case of two-tower, not a different model class.)
- "Your item-item recall keeps surfacing the same few head items for every seed. Why, and what's the fix?" (Probes: raw co-occurrence rewards popular items because they co-occur with everything — coincidental overlaps the count can't distinguish from real ones. Fix is Swing: weight each co-click by 1/(α + |Iu ∩ Iv|) so co-clicks from broadly-overlapping users are discounted and co-clicks from otherwise-dissimilar users dominate. Bonus: the per-user 1/√|Iu| normalization for hyperactive users, and that it's computed offline.)
- "Your candidate gen has 10 sources. How do you decide K₁ allocation across sources?" (Probes: offline recall-at-K per source on held-out positives, online A/B on allocation, marginal-utility curve per source. Sources with overlapping coverage waste slots — measure incremental recall, not raw recall.)
- "What's the failure mode of training the two towers end-to-end on logged-click data?" (Probes: position bias propagates into the retriever. Items shown at top get clicked more, retriever learns to surface them again, the loop tightens. This is the setup for lesson 7 on debiasing.)