Two-Tower Retrieval at Industrial Scale

Introduction

Picture a librarian who has read every book in a library of a hundred million volumes, and who can tell you with uncanny accuracy which single book you should read next. There is one catch. You get to ask, and she has to answer, in a tenth of a second. She cannot walk the stacks. She cannot even skim the titles. In a tenth of a second a photon travels thirty thousand kilometres, and she has to consider a hundred million books.

Obviously she does not consider a hundred million books. Nobody does. What she does instead is the thing this article is about: long before you walked in, she read every book and wrote down, for each one, a short list of numbers describing what it is about. When you ask, she turns you into the same kind of short list of numbers, and then finds the books whose numbers point in the same direction as yours. That geometric shortcut is called two-tower retrieval, and some version of it decides what you see on every large recommendation surface in the world.

The idea is simple enough to fit in a sentence. Encode the user with one neural network, encode the item with another, and score the pair with a dot product. The reason this article is fifty minutes long is that everything interesting happens in the consequences: what that dot product forbids you from modelling, how you train it when the softmax has a hundred million classes, why the naive training loop quietly teaches the model that popular items are bad, how you fit a hundred-million-row embedding table into memory that does not exist, and why the model that wins offline so often loses in production.

Three papers anchor the discussion. Covington, Adams and Sargin's 2016 description of the YouTube recommender is where the architecture entered the public literature. Yi and colleagues' 2019 RecSys paper is where the sampling-bias correction was written down clearly and shown to matter at YouTube scale. Huang and colleagues' 2020 KDD paper on embedding-based retrieval in Facebook Search is the most honest published account of what actually breaks when you deploy one. Everything else here is arithmetic.

1 — The Funnel

Before any model, a budget. A recommendation request arrives. Somewhere between the user tapping and pixels appearing, you get a fixed allowance of wall-clock time and a fixed allowance of compute per request, and the second one is set by your hardware bill rather than by anything about machine learning.

The 100 ms budget

Let us make the numbers concrete, because vague talk about "low latency" teaches nothing. A typical target for a personalized feed is that the recommendation service returns within about 100 ms at p99. That number is not arbitrary. It comes from the end-to-end page budget: perhaps 400 ms to first meaningful paint, of which network round trips, authentication, other backend calls, template rendering and client-side layout eat most of it. The recommender gets what is left.

Inside that 100 ms, a realistic split looks like this:

Read the third and fourth columns again. The catalog shrinks by a factor of 100,000 in the first stage and by a factor of 5 in the second. Every stage downstream of retrieval is allowed to be more expensive per candidate precisely because retrieval has already thrown almost everything away. That is the whole design.

Why not just rank everything

The obvious objection: why not skip the funnel and run the good model on all hundred million items? Let us find out how bad that is, in FLOPs.

A production ranking model is not small. It reads dozens of user features and dozens of item features, looks up several embedding tables, computes explicit feature crosses, and pushes the result through a multi-layer perceptron with a few hidden layers of width 512 to 1024. Call it 10 MFLOPs per (user, item) pair. That is a modest estimate; a cross-attention ranker that actually reads the item's text would cost 30 to 50 times more.

Scoring the whole catalog for one request:

A single A100 sustains roughly 3 × 10¹⁴ FLOP/s on well-shaped bf16 matrix multiplies. So one request needs

Against a 35 ms ranking budget, that is 95× over for a single user. Now multiply by traffic. At a sedate 10,000 requests per second you would need 33,000 A100s running flat out, continuously, to serve the ranking stage alone. At three dollars an hour that is roughly a hundred thousand dollars per hour. Nobody is doing this.

Now do the same arithmetic on a funnel. Retrieval hands the ranker 1,000 candidates:

Thirty-three microseconds of raw math, which in practice becomes a few milliseconds once you account for kernel launches, feature gathering, and the fact that you are nowhere near peak utilization on a batch of 1,000. But it fits, comfortably, and a single GPU can now serve thousands of requests per second.

Where embeddings sit in the stack

It helps to name the three stages by what they are allowed to know.

• Retrieval may know the user and the item, but never at the same time. It computes a user summary and an item summary independently and combines them with an operation so simple that a specialized index can evaluate it against millions of items at once. In practice that operation is a dot product or a cosine, and the specialized index is an approximate nearest neighbour structure.
• Ranking may know the user and the item together. It sees explicit crosses: "this user has watched 14 videos from this creator", "the item's language matches the user's locale", "time since this user last engaged with this topic". These features are enormously predictive and completely unavailable to retrieval.
• Re-ranking may know the user, the item, and the other items in the slate. It handles diversity, deduplication, business rules, freshness quotas, and anything that depends on the composition of the final list rather than on any single item.

So the retrieval stage is defined by a restriction, not by an architecture. Two-tower models are simply the most natural neural architecture that satisfies the restriction. If someone invents a different score function that an index can evaluate at a hundred million items per millisecond, that will be a retrieval model too. We will meet one candidate in section 8.

The demo below makes the funnel arithmetic tangible. Move the candidate count and watch two curves fight: ranking cost rises linearly with candidates, while the fraction of the truly best items that survive retrieval rises with diminishing returns. The sweet spot is where the cost curve crosses your budget line, and it is usually between 500 and a few thousand.

2 — Two Towers From Zero

Forget architectures for a moment. You have logs. Each row says: at time t, user x was shown some things and engaged with item y. You want a function that, given a fresh user, produces the items they are most likely to engage with.

The most direct thing to build is a classifier. Treat "which item did the user engage with next" as a multi-class classification problem where the classes are the items. This is exactly how Covington and colleagues framed YouTube candidate generation in 2016, and the framing is worth quoting because everything else descends from it: recommendation as extreme multiclass classification, where the number of classes is the size of the corpus.

The split, and where it comes from

Write the classifier the ordinary way. A network reads the user's features and produces a hidden vector; a final linear layer maps that hidden vector to one logit per class; a softmax turns logits into probabilities.

Now stare at W. It has one row per item. Row j is a d-dimensional vector, and the logit for item j is the dot product of that row with the user's hidden vector. Nobody designed this as an embedding. It is just the weight matrix of a linear classifier. But it is an item embedding table, and the score is already a dot product.

That observation is the whole trick. The moment you notice that logits = W u means "score every item by its dot product with the user vector", you realize that finding the top-k items is not a matrix multiply followed by a sort. It is a maximum inner product search, and there are index structures that solve that approximately in sublinear time. Covington et al. say this in about one sentence and move on, but it is the sentence that made the architecture deployable.

Once you see W as an item embedding table, the generalization is irresistible. Why should item j's vector be a free parameter learned only from clicks on item j? Replace the lookup with a second network that reads the item's features — its id, yes, but also its creator, language, topic, age, title tokens, thumbnail embedding — and produces the vector. Now you have two networks:

Two towers. They never talk to each other until the very last operation, which is a dot product. And upgrading from a raw table to a feature-driven tower buys something the table can never have: a new item with zero interactions still gets a sensible vector, because its features exist the moment it is created.

Most production systems normalize both vectors and divide by a temperature before the softmax:

Normalization is not cosmetic. Without it the model can lower its loss by simply inflating the norms of popular items, which turns the geometry into a popularity ranking and makes the ANN index behave badly — nearest-neighbour structures built for inner product handle wildly varying norms poorly. With normalization every vector lives on the unit sphere, the score is bounded in [−1, 1], and the temperature τ — typically 0.05 to 0.2 — controls how sharply the softmax discriminates. Yi et al. report that both the normalization and the temperature mattered materially for trainability.

import torch
import torch.nn as nn
import torch.nn.functional as F


class Tower(nn.Module):
    """One side of the model. Reads a feature dict, emits a unit vector."""

    def __init__(self, cat_cardinalities, n_dense, dims=(512, 256, 64)):
        super().__init__()
        # One embedding table per categorical feature. Widths follow the usual
        # heuristic: about 6 * cardinality ** 0.25, capped.
        self.emb = nn.ModuleDict({
            name: nn.Embedding(card, min(128, int(6 * card ** 0.25)))
            for name, card in cat_cardinalities.items()
        })
        in_dim = sum(e.embedding_dim for e in self.emb.values()) + n_dense

        layers, prev = [], in_dim
        for h in dims:
            layers += [nn.Linear(prev, h), nn.LayerNorm(h), nn.ReLU()]
            prev = h
        self.mlp = nn.Sequential(*layers)

    def forward(self, cats: dict, dense: torch.Tensor) -> torch.Tensor:
        # cats[name]: (B,) int64      dense: (B, n_dense) float32
        parts = [self.emb[name](cats[name]) for name in self.emb]
        x = torch.cat(parts + [dense], dim=-1)      # (B, in_dim)
        z = self.mlp(x)                             # (B, 64)
        return F.normalize(z, dim=-1)               # (B, 64), unit norm


class TwoTower(nn.Module):
    def __init__(self, user_spec, item_spec, temperature=0.07):
        super().__init__()
        self.user_tower = Tower(**user_spec)
        self.item_tower = Tower(**item_spec)
        # Learn the temperature in log space so it stays positive.
        self.log_tau = nn.Parameter(torch.tensor(temperature).log())

    def score(self, u, v):
        # u: (B, 64)   v: (M, 64)   ->   (B, M)
        return (u @ v.t()) / self.log_tau.exp()

Note the shapes, because they are the whole story of how this thing is served. u: (B, 64) is computed once per user. v: (M, 64) is computed once per item. u @ v.T: (B, M) is the only place the two ever meet, and it carries no learned parameters at all.

Serving asymmetry — the actual justification

Here is the argument that makes two towers not merely convenient but necessary. The two towers are evaluated on completely different schedules.

The item tower runs in a batch job. If it takes 40 ms per item on a GPU, so what — run it on a hundred machines overnight. It can read the item's full text with a transformer, run a vision model on the thumbnail, and consult a knowledge graph. Its output is 64 floats that you write to a file.

The user tower runs while somebody is staring at a loading spinner. It gets a couple of milliseconds and must not depend on anything you cannot fetch quickly.

And crucially: the item tower's output does not depend on the user. So you run it once, for all hundred million items, and store the results in an index. At request time you do not evaluate the item tower at all. You evaluate the user tower once, get one 64-vector, and hand it to the index. That is the entire economic argument.

Concretely, here is the online path with costs attached, and the offline path beside it:

request
  |- fetch user features from the online store          ~3-8 ms   (network)
  |- user_tower.forward(features)  -> u: (1, 64)        ~0.3 ms   (2 MFLOPs)
  |- index.search(u, k=1000)       -> ids, scores       ~1-5 ms   (touches ~0.2% of index)
  '- hydrate item metadata for 1000 ids                 ~5-10 ms  (network)
                                                        ---------
                                                        ~10-23 ms

offline, once per refresh
  '- for each of 100M items:
       item_tower.forward(features) -> v: (64,)         hours on a cluster
       write to index shard                             25.6 GB fp32 / 1.6 GB PQ-16

What the constraint costs you

Nothing is free. The price of factorizing the score is that the model can never form a feature that involves the user and the item jointly. Some examples a ranker uses every day and a two-tower model structurally cannot:

• "Number of videos this user has watched from this creator in the last 30 days."
• "Whether the item's language equals the user's preferred language."
• "Cosine between the item and the user's last item, as opposed to their average."
• "Whether we already showed this exact item to this user an hour ago."

Each requires knowing both sides at once. In a factorized model you cannot compute them, full stop. What you can do is approximate, and the approximations are where much of the craft lives:

1. Push the cross into the user tower as an aggregate. Instead of "watched from this creator", the user tower ingests an embedding of the user's top-20 creators. The dot product then partially recovers the cross, because an item from creator C has a vector that — if the model is any good — points along creator C's direction.
2. Give the item tower a user-independent version of the feature. "Is this item English" is an item feature; "is the user English" is a user feature; the dot product can learn to align the language dimensions. It is a weak, lossy version of an equality check, but it is not nothing.
3. Give up and let the ranker do it. Usually correct. Retrieval does not need to be right about the top item, it needs to contain the top item. Precision is the ranker's job.

There is a fourth option people reach for that deserves suspicion: adding a small MLP on top of the concatenation [u; v; u ⊙ v]. It works beautifully offline and destroys your serving story, because now the index cannot evaluate the score and you are back to scoring the whole catalog. If you truly need it, the honest version is to apply it as a cheap re-scoring pass over the top few thousand ANN results — which is just admitting you have added a stage to your funnel.

3 — The Training Signal

We have an architecture. Now: what do we train it on, and against what loss? This is where recommendation stops resembling supervised learning as taught in courses, because there is no labelled dataset. There is a log of things that happened.

Implicit feedback and its lies

A rating — a user gave this film four stars — is explicit feedback. It is rare, biased toward extremes, and mostly nonexistent at scale. What you actually have is implicit feedback: clicks, watches, plays, purchases, dwell time, saves. Its defining property is that it has positives but no negatives.

If a user watched video A, that is evidence they liked A. If they did not watch video B, the reasons could be any of:

• They saw B and were not interested. (A true negative.)
• They never saw B, because your system never showed it. (Not evidence of anything.)
• They saw B, wanted it, and were interrupted. (A false negative.)
• They already watched B somewhere else. (A false negative for a subtler reason.)

With a hundred million items, the second case dominates so overwhelmingly that "did not interact" carries almost no information. This is why implicit-feedback retrieval is trained with sampled negatives rather than observed ones: you assume a randomly drawn item is, in expectation, less relevant than the observed positive, and you train the model to separate them. The assumption is wrong on any individual pair and right on average, which is exactly the regime where stochastic gradient descent thrives.

Two choices about the positives are worth stating because they are cheap to get wrong.

Cap the examples per user. Covington et al. explicitly fix the number of training examples per user. Without this, your heaviest 1% of users contribute the majority of gradient steps and the model becomes a model of them. A cap of, say, 50 examples per user per day flattens the influence distribution considerably.

Predict forward, not sideways. The tempting setup is to hold out a random item from the user's history and predict it from the rest. The correct setup is to take a prefix of the history and predict the next item. Consumption is asymmetric: people discover a topic, binge it, then move on. A model trained to fill in the middle of a session learns to interpolate within a binge, which is trivially easy and useless at serving time, where you always stand at the end of the history looking forward. Covington et al. report this as a material win, and the same pathology has been rediscovered in sequential recommendation many times since.

The full-softmax impossibility

With positives in hand, the natural loss is cross-entropy over the whole catalog. For a training row (user x, positive item y):

This is exactly right and completely impossible. The denominator — the partition function — sums over every item in the catalog. Cost it out for one training step with batch size B = 8192 and N = 10⁸ items at d = 64.

A third of a second per step on a top-tier accelerator, needing 1.6 terabytes of activation memory that no single device has, and touching every row of the embedding table on every step so the optimizer must update all hundred million rows. A ten-thousand-step epoch would take an hour of pure matmul and you need dozens of epochs. It is not a matter of buying more GPUs; the memory alone rules it out.

So we approximate the denominator. The family of techniques is called sampled softmax, and it dates to Bengio and Sénécal in 2003, long before anyone was recommending videos with it.

In-batch sampled softmax

The cheapest possible sample is the one you already paid for. Your batch contains B training rows, each with a positive item. Those items are already encoded — you ran the item tower on them. So use every other row's positive as a negative for this row.

Take the batch of user vectors U: (B, d) and item vectors V: (B, d). One matrix multiply gives every pairwise score:

Row i of S holds user i's score against all B items in the batch. Entry S[i][i] is the true positive; every other entry in that row is a sampled negative. The label for row i is simply i, so the loss is a plain cross-entropy against arange(B).

def in_batch_loss(model, user_batch, item_batch):
    u = model.user_tower(**user_batch)      # (B, 64) unit norm
    v = model.item_tower(**item_batch)      # (B, 64) unit norm

    logits = model.score(u, v)              # (B, B)  = u @ v.T / tau
    labels = torch.arange(u.size(0), device=u.device)   # diagonal is positive

    return F.cross_entropy(logits, labels)

Three lines, and the accounting is beautiful. A batch of 8192 gives each row 8191 negatives for free — the item tower forward pass was already needed for the positives. Compare the cost:

Four orders of magnitude cheaper in matmul and infinitely cheaper in extra tower passes, because there are none. This is why in-batch negatives are the default everywhere, and why large batch sizes matter so much for retrieval training: batch size is your negative count. Doubling the batch does not merely smooth the gradient, it doubles the number of items each user is contrasted against.

And now the trap. Where did those in-batch negatives come from? They are the positives of other rows, and rows are drawn from your interaction log. So the probability that item j appears as a negative is proportional to how often item j is clicked. Interaction logs are savagely Zipfian: in most catalogs the top 1% of items collect something like half of all interactions.

Which means the top 1% of items appear as negatives in essentially every batch, while the long tail appears almost never. The model is being told, thousands of times per epoch, "push this user away from the most popular item in the catalog". Nobody intended this. It is a pure artifact of where the negatives came from, and left uncorrected it will wreck your model. Fixing it is the subject of the next section.

4 — The LogQ Correction

This section is the reason the article exists. Everything before it is architecture you could reinvent in an afternoon. What follows is a two-character change to a line of code — subtract a number from the logits — that separates a two-tower model which works from one which silently, confidently, ranks your best content last.

Where the bias comes from

Let us set up the problem with no hand-waving. Write q(j) for the probability that item j occupies any given slot in a training batch. Because slots are filled by sampling rows from the interaction log, q is the empirical click distribution:

A tail item with 100 interactions out of 10¹⁰ total has q = 10⁻⁸. A head item with 10⁸ interactions has q = 10⁻². That is a million-fold difference in how often the two appear as negatives.

Now recall what the cross-entropy gradient does. With logits s_j and softmax probabilities P̂_j, the loss for a row whose positive is item i is L = −s_i + log Σ_j exp(s_j), so

For every negative j, the gradient is +P̂_j: a push downward on that item's score, proportional to how confidently the model currently believes in it. That push travels back into item j's embedding and into the user tower. The item is being shoved away from this user in the geometry.

So the total downward pressure on item j across all of training is, in expectation:

Compare that to what the full softmax would do. In a full softmax, every item appears in every denominator exactly once, so the frequency term vanishes and the pressure is proportional to exp(s) alone. The in-batch estimator multiplies that by q(j), which is precisely the bias.

The symptom in production is unmistakable once you know to look for it. Offline loss looks fine. Recall@k on your held-out set looks acceptable. But the retrieved lists are full of obscure items, the head of the catalog barely appears, and the online metrics are flat or negative. Engineers usually respond by adding a popularity feature or a popularity prior at serving time, which papers over the symptom while the geometry stays broken.

Deriving the correction from importance sampling

The fix falls out of a standard idea: importance sampling. We want to estimate a sum we cannot compute, using samples from a distribution we did not choose.

The quantity we need is the partition function:

We are given samples j ~ q, not uniform samples. The importance-sampling identity rewrites the sum as an expectation under q by multiplying and dividing:

Read that carefully, because it is the whole derivation. Each term of the true sum is reweighted by 1/q(j). An item you draw often gets divided by a big number; an item you almost never draw, when it finally shows up, gets divided by a tiny number and therefore stands in for the enormous mass of rare items you did not draw. It is a survey weight, exactly as in polling: if you sampled one rural voter for every hundred urban ones, that rural voter counts for a hundred.

With B samples j₁ … j_B from the batch, the Monte Carlo estimate is

and this estimator is unbiased: 𝔼[Ẑ] = Z. Now the last move, the one that makes it a one-line code change. Division inside an exponential is subtraction outside it:

So instead of dividing the exponentials, we subtract log q from the logits and then run an ordinary softmax. Define the corrected logit

and the corrected in-batch loss for row i is the plain cross-entropy over s^c:

The 1/B factor from the Monte Carlo average cancels between numerator and denominator, which is why you never see it in code. This is the estimator in Yi et al. (2019), and the same correction appears in TensorFlow's sampled_softmax_loss, in tf.nn.fixed_unigram_candidate_sampler, and in the noise-contrastive estimation literature under a different name.

Getting the sign right is worth pausing on, because it is easy to talk yourself into the opposite. The correction does not punish popular items harder. It punishes them less, per appearance, precisely because they appear so often. The product of (frequency of appearance) and (per-appearance penalty) is what must come out right, and the correction is designed to make that product independent of frequency.

Worked: three items, by hand

Let us verify that claim with arithmetic small enough to check on paper. A catalog of three items:

• A — a mega-hit. It receives 80% of all interactions, so q(A) = 0.80.
• B — a solid mid-tail item. q(B) = 0.15.
• C — a niche item. q(C) = 0.05.

For some user x, the model currently produces raw scores (temperature already folded in, so these are the logits):

The model genuinely thinks A is the best match. Good. Now, three columns of arithmetic.

Column 1 — what the full softmax would do. Every item appears exactly once in the denominator, so the downward pressure on item j is proportional to exp(s_j).

Shares of the total pressure:

This is the ground truth. It says: A is the strongest candidate, so most of the "push it down unless it is the positive" force lands on A; C barely matters.

Column 2 — what uncorrected in-batch negatives do. Now pressure is proportional to q(j) × exp(s_j), because item j appears in a fraction q(j) of negative slots.

Column 3 — with the logQ correction. Pressure is proportional to q(j) × exp(s_j − log q(j)). Expand the exponential:

The q cancels exactly. So the corrected pressures are 7.389056, 2.718282, 1.000000 — identical to column 1, the full softmax. The correction is not an approximation that happens to help; it exactly recovers the full-softmax gradient allocation in expectation.

The last column is the ratio of uncorrected to correct pressure. Item A absorbs 1.40× the repulsion it should. Item C absorbs 0.09× — it is eleven times under-penalized.

A 40% over-penalty on the head does not sound catastrophic until you remember that it applies on every step, for millions of steps, and that the head is where most of your engagement lives. In a real catalog the skew is far worse than 0.80/0.15/0.05. With a Zipf exponent near 1 and a hundred million items, the top item's q can exceed the median item's q by seven orders of magnitude, and the over-penalty ratio grows with the skew. That is the regime where uncorrected models produce retrieval sets full of obscure junk.

Play with the demo below before reading on. Turn the popularity skew up and watch the uncorrected bars distort while the corrected bars stay pinned to the full-softmax reference.

Estimating q in a stream

The correction needs q(j) for every item that lands in a batch. Where does that number come from? The obvious answer — count interactions per item and divide — has three problems in a real training pipeline.

1. You would need a counter per item. A hundred million int64 counters is 800 MB, which is survivable on one machine but awkward to keep consistent across hundreds of distributed training workers.
2. The distribution is not stationary. A video uploaded this morning has a q that is climbing by the minute. Yesterday's global counts are wrong for today's batches. Training is continuous, and the model must be corrected for the sampling distribution of the batches it is actually seeing right now.
3. You may not have a separate counting pass at all. In a streaming trainer, examples arrive once, are trained on, and are discarded. There is no corpus to count.

Yi et al. solve this with a lovely little online estimator that uses a fixed amount of memory and no counting pass. The idea: instead of counting appearances, track the average gap between appearances. If an item shows up on average every 40 steps, then its probability of showing up in any given step is about 1/40.

Keep two arrays of size H (say a few million), indexed by a hash of the item id:

• A[h] — the global step at which the item hashing to h was last seen.
• B[h] — an exponentially-weighted moving average of the gap between sightings.

When item y arrives at global step t:

and the estimate is simply the reciprocal:

That last identity is a small gift: the correction term you add to the logit is just the log of the stored gap. No division, no probability normalization, nothing to keep in sync.

Worked example. Suppose item y is seen at global steps 5, 15, 30 and 40, with α = 0.5 and both arrays initialized to zero.

The true average gap over those four sightings is (5 + 10 + 15 + 10)/4 = 10, so the true sampling probability is 0.1. The estimator lands on 0.0970 after four observations — an error of 3%, from four data points and two floats of state. The first estimate (0.40) is badly off because the array started at zero; in practice you either warm up on a prefix of the stream or initialize B to a prior gap, and you clamp q̂ into a safe range like [10⁻⁹, 10⁻²] so a pathological estimate cannot blow up a logit.

import numpy as np


class StreamingFrequency:
    """Yi et al. (2019) style streaming estimate of P(item in a batch slot).

    Tracks the moving-average GAP between sightings, hashed into fixed memory.
    Multiple hash functions guard against collisions: a collision can only make
    the observed gap SHORTER (another item refreshes your slot), which inflates
    q-hat, so we take the LARGEST gap across hashes as the safest estimate.
    """

    def __init__(self, n_buckets=2_000_000, n_hashes=2, alpha=0.01,
                 init_gap=1000.0, q_min=1e-9, q_max=1e-2):
        self.H, self.M, self.alpha = n_buckets, n_hashes, alpha
        self.A = np.zeros((n_hashes, n_buckets), dtype=np.int64)      # last-seen step
        self.B = np.full((n_hashes, n_buckets), init_gap, np.float32)  # avg gap
        self.salts = [0x9E3779B1 * (m + 1) for m in range(n_hashes)]
        self.q_min, self.q_max = q_min, q_max

    def _idx(self, item_ids):
        # (M, n) bucket indices
        return np.stack([((item_ids * 0x27220A95) ^ s) % self.H
                         for s in self.salts])

    def update(self, item_ids: np.ndarray, step: int):
        idx = self._idx(item_ids)
        for m in range(self.M):
            gaps = (step - self.A[m, idx[m]]).astype(np.float32)
            self.B[m, idx[m]] = (1 - self.alpha) * self.B[m, idx[m]] + self.alpha * gaps
            self.A[m, idx[m]] = step

    def log_q(self, item_ids: np.ndarray) -> np.ndarray:
        idx = self._idx(item_ids)
        gap = self.B[np.arange(self.M)[:, None], idx].max(axis=0)  # largest gap wins
        q = np.clip(1.0 / np.maximum(gap, 1e-6), self.q_min, self.q_max)
        return np.log(q).astype(np.float32)

Wiring it into the loss is one line. The correction is applied to the logits, and — this is the detail people get wrong — it is applied to every column, including the diagonal. The positive is also a sample from q, so it needs the same weight; correcting only the off-diagonal entries reintroduces a bias in the opposite direction.

def corrected_in_batch_loss(model, user_batch, item_batch, item_ids, freq, step):
    u = model.user_tower(**user_batch)          # (B, 64)
    v = model.item_tower(**item_batch)          # (B, 64)

    logits = model.score(u, v)                  # (B, B)

    # --- the correction: one broadcast subtraction over columns ---------------
    log_q = torch.as_tensor(freq.log_q(item_ids), device=logits.device)  # (B,)
    logits = logits - log_q.unsqueeze(0)        # every row, every column

    # --- mask accidental hits: same item appearing as another row's positive --
    same = item_ids.unsqueeze(0) == item_ids.unsqueeze(1)       # (B, B)
    eye = torch.eye(len(item_ids), dtype=torch.bool, device=logits.device)
    logits = logits.masked_fill(same & ~eye, float('-inf'))

    labels = torch.arange(u.size(0), device=u.device)
    loss = F.cross_entropy(logits, labels)

    freq.update(item_ids.cpu().numpy(), step)   # update AFTER using the estimate
    return loss

Two failure modes to watch for once it is in.

Over-correction on a stale estimator. If q̂ is much smaller than the true q for the head — for example because your moving average has a long half-life and an item has just gone viral — then the correction over-boosts that item's logit as a negative and you swing the bias the other way. Symptom: head items suddenly vanish from retrieval after a traffic spike. Fix: shorten α, or clamp the correction magnitude.

Hash collisions. Two items sharing a bucket look like one item that appears twice as often, so both get an inflated q̂ and both are under-penalized. With 100M items and 2M buckets, average occupancy is 50, so collisions are the rule, not the exception. Multiple hash functions with a max-gap reduction (as in the code above) helps, because a collision can only ever shorten the gap you observe. Reserving exact counters for the top 100,000 items and hashing only the tail is a common production compromise: those are the items where the correction matters most and where exact counting is cheapest.

5 — Hard Negatives

The logQ correction fixes which items get penalized. It says nothing about whether those items are useful to learn from. That is the second half of the negatives problem, and the paper with the most useful things to say about it is Huang et al.'s account of embedding-based retrieval in Facebook Search.

The training/serving mismatch

Think about what your model is asked to do at each of the two times it operates.

At training time, with in-batch negatives, it sees one positive and a few thousand items drawn from the global click distribution. Those items are, overwhelmingly, about nothing to do with this user. If the positive is a deadlift tutorial, the negatives are a makeup review, a football highlight, a cooking video, a music clip. Separating the deadlift tutorial from that field is easy. After a few epochs the model achieves it essentially perfectly and the gradients go quiet.

At serving time, the ANN index hands back the thousand items closest to the user vector. Every one of them is already plausible. The model's actual job is to order deadlift tutorial against squat tutorial, deadlift form check, and deadlift PR compilation. That is a completely different discrimination problem, and nothing in training ever asked the model to solve it.

Huang et al. put this crisply: training with random negatives teaches the model to reproduce the "easy" separation, but the retrieval task is defined over a candidate set that is already filtered by the model itself. The distribution the model is evaluated on is the distribution it induces, and random negatives are not drawn from it.

The EBR recipe

Facebook's paper is unusually specific about what worked, and the numbers are worth memorizing because they generalize surprisingly well across domains.

Online hard negatives. Within each batch, for each query, score all the in-batch non-positive documents and take the top-scoring ones as extra negatives. The critical finding: use at most two hard negatives per positive. Going beyond two degraded quality. This surprises people who assume more hard examples must be better.

Offline hard negatives. Periodically run the current model over the corpus, retrieve the top-K for each training query, and sample negatives from the results. The critical finding: do not sample from the very top. The best negatives came from around rank 101 to 500. Items ranked 1 to 100 are, in a well-trained model, mostly items the user would have liked and simply never saw. Training on them teaches the model to suppress good recommendations.

Blending. Hard negatives alone are worse than random negatives alone. That is the finding that most contradicts intuition, and the mechanism is worth understanding: a model trained only on near-miss negatives never learns the coarse structure of the space. It becomes exquisitely good at local discrimination and forgets that a football highlight is not a deadlift tutorial, because nothing ever told it so. The reported sweet spot is roughly 100 easy : 1 hard.

The same conclusions were reached independently in dense text retrieval. The ANCE line of work observed that negatives sampled from a stale index become useless as the model moves away from them, and made the index refresh part of the training loop: every few thousand steps, re-encode the corpus and rebuild the negative index. RocketQA added an explicit denoising step — score candidate hard negatives with a stronger cross-encoder and drop the ones it thinks are actually relevant, which is a direct attack on the false-negative problem.

class MixedNegativeSampler:
    """Blend in-batch (easy, popularity-distributed) with mined hard negatives.

    Ratio follows the EBR finding: roughly 100 easy per 1 hard, and never more
    than 2 hard negatives attached to any single positive.
    """

    def __init__(self, index, hard_per_positive=2, mine_from=(100, 500),
                 refresh_every=5000):
        self.index = index                      # ANN over CURRENT item vectors
        self.hard_per_positive = hard_per_positive
        self.lo, self.hi = mine_from            # sample from this rank window
        self.refresh_every = refresh_every
        self.step = 0

    def maybe_refresh(self, item_tower, all_item_features):
        """Stale negatives are useless negatives — the model has moved."""
        if self.step % self.refresh_every == 0:
            with torch.no_grad():
                vecs = item_tower.encode_all(all_item_features)   # (N, 64)
            self.index.rebuild(vecs)

    def mine(self, u, positive_ids):
        """u: (B, 64). Returns (B, hard_per_positive) item ids."""
        # Retrieve deep enough to reach the sampling window.
        cand = self.index.search(u, k=self.hi)                    # (B, hi)
        window = cand[:, self.lo:self.hi]                         # (B, hi - lo)

        # Drop anything that is actually this row's positive.
        mask = window != positive_ids.unsqueeze(1)
        picks = []
        for row, m in zip(window, mask):
            valid = row[m]
            idx = torch.randperm(len(valid))[:self.hard_per_positive]
            picks.append(valid[idx])
        return torch.stack(picks)


def loss_with_hard(model, user_batch, item_batch, item_ids, hard_ids,
                   freq, step, hard_weight=0.01):
    """hard_weight ~ 1/100 realizes the 100:1 easy:hard blend."""
    u = model.user_tower(**user_batch)                   # (B, 64)
    v = model.item_tower(**item_batch)                   # (B, 64)
    vh = model.item_tower(**gather_features(hard_ids))   # (B, H, 64)

    easy = model.score(u, v)                             # (B, B)
    easy = easy - torch.as_tensor(freq.log_q(item_ids)).unsqueeze(0)

    # Hard negatives are MINED, not sampled from q — no logQ term for them.
    hard = torch.einsum('bd,bhd->bh', u, vh) / model.log_tau.exp()   # (B, H)

    logits = torch.cat([easy, hard * 1.0], dim=1)        # (B, B + H)
    labels = torch.arange(u.size(0), device=u.device)

    # Down-weight the hard block so it does not dominate the denominator.
    weights = torch.cat([
        torch.ones(easy.shape[1], device=u.device),
        torch.full((hard.shape[1],), hard_weight, device=u.device),
    ])
    logits = logits + weights.log().unsqueeze(0)   # log-weight == logit shift
    return F.cross_entropy(logits, labels)

Two implementation details in that code carry real weight.

First, mined negatives get no logQ term. The correction compensates for a known sampling distribution; mined negatives are not sampled from q, they are selected by the model. Applying log q to them would be correcting for a bias that is not there. If you mix sources, each source needs its own treatment, and a mined source with an unknown selection distribution needs none.

Second, a multiplicative weight on a term is an additive shift on its logit, since w·exp(s) = exp(s + log w). That is how you implement a 100:1 blend without literally materializing a hundred easy negatives per hard one.

When hard is too hard

The failure mode deserves its own treatment because it is the most common way a hard-negative pipeline destroys a model that was working fine.

You mine negatives from the top of your own retrieval results. Your model is good. The top of your retrieval results is full of items the user would love. You label them negative. You compute a gradient that pushes them away. You have now taught your model that its best predictions are wrong.

The mathematics of this is not subtle: cross-entropy with a wrong label produces a large gradient precisely because the model is confident, so false negatives are the highest-magnitude gradients in your batch. A few percent of false negatives among your hard negatives can outweigh all your true positives.

Defences, roughly in order of cost:

1. Sample from a rank window, not the top. Ranks 101-500 is the published heuristic. Cheap, effective, no extra model.
2. Exclude anything the user actually engaged with, ever. Not just this session's positive — their whole history. An item they watched last month is not a negative today.
3. Exclude by exposure. If the item was never shown to this user, "they did not click it" is not evidence. If you log impressions, restrict hard negatives to impressed and not engaged, which is the only genuinely observed negative you have.
4. Denoise with a stronger model. Score candidate hard negatives with the ranker (which sees the crosses retrieval cannot) and drop the ones it scores highly. This is the RocketQA move, and it costs a batch scoring pass per refresh.
5. Soften the labels. Instead of a hard 0, use a small target probability for mined negatives, or clip the per-negative gradient. Blunt, but it bounds the damage from any single mislabel.

6 — Serving the Index

A trained two-tower model is not a retrieval system. It is half of one. The other half is an index that has to be built, refreshed, versioned, sharded and kept consistent with a user tower running in a different process on a different machine on a different deploy cadence. Most of the operational pain of retrieval lives here, and almost none of it is discussed in the modelling papers.

Index refresh cadence

Item vectors go stale for two reasons, and they have different clocks.

The model changes. You retrain, you ship new weights, and every item's vector is now wrong because it was produced by the old item tower. This forces a complete rebuild — all hundred million vectors — and it is the expensive one. Budget: a hundred million item-tower forward passes. If the item tower is a modest MLP over cached features, that is minutes on a GPU cluster. If it reads item text with a transformer, it is hours, and you cache the expensive sub-encoders separately so that a model refresh only has to redo the cheap head.

The items change. New items are created continuously; existing items acquire new statistics (view counts, engagement rates, age). This forces incremental updates: encode the changed items and upsert them into the index.

A workable production cadence looks like this:

The "fresh shard" pattern deserves a note. Rebuilding an IVF or HNSW index is expensive because the structure — the coarse quantizer centroids, the graph edges — depends on the whole dataset. Adding a single vector to an HNSW graph is cheap; adding ten million and expecting the graph to stay well-connected is not. So production systems typically keep a large, well-built base index that is rebuilt on a slow clock, plus a small incremental index (often brute-force, since it holds only thousands of vectors) that is searched in parallel and merged. Queries hit both, results are merged by score, and the fresh shard is folded into the base at the next rebuild.

The version-skew trap

This one takes down retrieval systems, and it is entirely avoidable once you have seen it.

Suppose the user tower is deployed as part of your serving binary and the item index is built by a separate pipeline. You retrain. The new binary rolls out at 14:00; the new index finishes building at 15:30. Between 14:00 and 15:30, model v2's user vectors are being dot-producted against model v1's item vectors.

The result is not "slightly worse". It is noise. There is no constraint tying the coordinate systems of two independently trained networks together. Dimension 17 of v1's space and dimension 17 of v2's space have nothing to do with each other — the model is free to permute, rotate and rescale its latent axes between runs, and it will. Cosine similarity between a v2 user vector and v1 item vectors is approximately random, so for ninety minutes your retrieval stage is a random sampler and nobody notices until the daily metrics land.

The deployment protocol that avoids it:

1. Stamp every artifact with a model_version: the trained checkpoint, the built index shard, the serving binary.
2. Build and deploy the index first, alongside the existing one. Two indexes now live in memory.
3. Deploy the user tower with the new version tag. It queries only shards whose tag matches.
4. Hold a dual-read window (hours) so a rollback of the binary still finds its matching index.
5. Drop the old index only after the new binary is at 100% and past its rollback window.

The memory cost of holding two indexes is real — 2 × 1.6 GB per shard with PQ compression — and it is the price of not shipping a silent outage.

User-vector freshness

The user tower has the opposite problem from the item tower: it is cheap to run but its inputs change by the second. A user who has just watched three woodworking videos should get woodworking recommendations now, not tomorrow.

There are two extremes and one sensible middle.

Fully precomputed. Run the user tower nightly for every user, store the vector, look it up at request time. Costs almost nothing online. Completely blind to the current session. Fine for a daily digest email; useless for a feed.

Fully online. Fetch all features at request time, run the tower, use the result. Maximally fresh. Costs you the feature fetch (typically the largest single latency item in the whole path — 3 to 8 ms of network to a key-value store) plus the forward pass.

The split representation. Decompose the user vector into a slow part and a fast part:

The slow part is computed nightly from the user's long-term history and cached. The fast part is computed at request time from a short event buffer that lives in a low-latency store — the last 20 item ids the user touched, pooled through a small attention or mean-pooling head. The fast head is tiny (an embedding lookup and a pooling op, well under 100 μs), so you get session-level responsiveness for almost no online cost.

You must train the model in this decomposed form. Training a single monolithic user tower and then splitting it at serving time does not work, because the tower's nonlinearities do not distribute over the sum. Define the split in the architecture, train it end to end, and the serving path is then an exact evaluation of the trained function rather than an approximation of it.

Cold start, on both sides

New items. An item created five minutes ago has no interactions, so a pure ID embedding for it is whatever the initializer produced — noise. Three mechanisms, used together:

• Content features in the item tower. This is the main answer and the main reason to prefer a real item tower over a raw weight matrix. A new video has a title, a creator, a language, a category, a thumbnail. If the tower reads those, the new item lands in a plausible neighbourhood on its first day, before anybody has clicked it.
• An exploration quota. Reserve a fraction of retrieval slots (say 2%) for items below an interaction threshold. This is not charity; it is how you acquire the data that lets the model learn about them at all. Without it, new items are never shown, never accumulate data, and never become showable — the classic feedback trap.
• An age feature, handled carefully. Covington et al.'s "example age" trick: feed the item's age at the time of the training example as a feature, then set it to zero (or slightly negative) at serving. During training the model can use age to explain popularity dynamics; at serving you ask it "what if this item were brand new", which removes the model's learned bias toward items that have simply been around longer. This is a small feature that produces a large, visible change in how fresh the recommendations feel.

New users. Symmetric and easier. Because the user tower reads features rather than a user ID embedding, a first-time visitor still has a locale, a device, a referrer, a time of day, and possibly one page view. The tower maps those to a reasonable prior region of the space. The failure mode is the opposite of the item side: if you do include a learned per-user ID embedding, new users get noise, and you have reintroduced cold start on the side where you did not need it. Many production user towers deliberately omit the user ID entirely for exactly this reason, and rely on behaviour features to carry identity.

7 — Embedding Tables at Scale

Everything above assumed you can look up an embedding for an item id. At a hundred million items that assumption is the single largest engineering problem in the system, dwarfing the model itself. In most large recommenders, well over 99% of the parameters live in embedding tables and well under 1% live in the neural network. The "model" is a rounding error attached to a very large hash map.

The memory arithmetic

Start with the base case and do it slowly.

25.6 GB is already awkward — it does not fit on a 24 GB consumer card and leaves no room on a 40 GB A100. But inference memory is the easy half. Training with Adam requires, per parameter:

A hundred gigabytes for one embedding table, and that is with a modest d = 64. This is why large-scale recommender training uses sparse optimizers (only the rows touched this step get updated, so gradients are stored sparsely), sharded parameter servers, and Adagrad rather than Adam (one moment instead of two — a 25% saving on the total, and Adagrad's accumulator suits the wildly uneven update frequencies of head and tail rows).

Even so, at some scale the table simply does not fit. There are three families of answers, each with a different loss.

The hashing trick

The bluntest instrument: pick a table of H rows with H ≪ N, and map item i to row h(i) = i mod H (or any decent hash). Memory drops by N/H immediately.

The cost is collisions. With 10⁸ items in 2 × 10⁶ buckets, average occupancy is 50 items per row. Every row is a blend of fifty unrelated items, and any two items sharing a row are, as far as the model can tell, the same item.

In practice this is less catastrophic than it sounds, for a reason worth internalizing: gradient mass is as skewed as traffic. A row shared by one head item with a million interactions and forty-nine tail items with ten each will be dominated by the head item's gradients — it will effectively become the head item's embedding, and the tail items will inherit a vector that is wrong but not random. Meanwhile the item tower has other features (creator, category, language) that are not hashed, so a collided item still gets most of its signal. Hashing degrades the tail gracefully and leaves the head almost untouched, which is exactly the tradeoff you want, though it is uncomfortable to state out loud.

Quotient-remainder: unique codes from a tiny table

There is a far more elegant construction, from the compositional-embedding work of Shi et al. (2020). The insight: you do not need a unique row per item, you need a unique code. Two small tables can generate a huge number of distinct combinations.

Pick a modulus m. For item id i, compute the remainder and the quotient:

Keep table R with m rows and table K with ⌈N/m⌉ rows, and combine:

The pair (r, k) is unique for every i — that is just the division algorithm. So unlike naive hashing, no two items get the same code, even though they share rows.

Worked memory calculation. Take N = 10⁸ and m = 10⁴:

Five megabytes instead of twenty-five gigabytes, with every item still uniquely addressable. It looks like a free lunch and it is not, so let us be precise about the bill.

Capacity, not addressability, is the constraint. The table holds 20,000 × 64 ≈ 1.28 million free parameters, down from 6.4 billion. Those 1.28 million numbers must encode a hundred million items. Each item's embedding is a deterministic function of two shared rows, so items sharing a remainder are constrained to differ only through their quotient row, and vice versa. Every row is shared by 10,000 items, and its gradient is the sum of theirs.

What this means in practice: head items still learn well, because they dominate the gradients of the rows they touch and can pull those rows toward themselves. Tail items are pushed toward a structured average of their row-mates. The embedding space becomes lower-rank in a specific, arithmetic way — items with the same quotient (that is, consecutive blocks of 10,000 ids) share a factor, which is meaningless unless your ids are assigned meaningfully. A common refinement is to choose the two indices from semantically meaningful buckets rather than from arithmetic on the raw id, which is a direct bridge to the semantic-ID idea in the next section.

Mixed dimensions: spend where the data is

The third family accepts a full-size table and shrinks the columns instead of the rows, per item. The observation is simple: an item with ten million interactions can support a 256-dimensional representation. An item with three interactions cannot — you would be fitting 256 parameters to 3 data points, which is pure memorization. So give the head wide vectors and the tail narrow ones.

Worked example. A Zipf-ish catalog of 10⁸ items, three tiers:

Check the arithmetic on one row:

That is an 11.3× reduction against a uniform wide table, and — this is the part that surprises people — it usually improves quality, because the narrow tail vectors regularize items that had no business carrying 256 parameters.

The mechanical catch: the dot product needs both sides at the same width. So each tier gets a small learned projection up to the common serving dimension:

Those three matrices hold 64 × (256 + 64 + 16) = 21,504 parameters — 86 KB. Utterly negligible against nine gigabytes.

Finally, do not forget the cheapest lever of all: precision. Serving the index in fp16 halves it for a quality loss that is normally unmeasurable, and product quantization to 16 bytes per vector (from 256 bytes at d=64 fp32) compresses the served index 16× while keeping recall@1000 within a point or two of exact search. The training table and the served index are separate artifacts with separate precision budgets, and conflating them costs money.

Drag the sliders below to see all four levers interact. The bars are drawn on a log scale because the range spans five orders of magnitude.

8 — Beyond Dot Products

The two-tower architecture is defined by its constraint: one vector per side, combined by an inner product. Every current research direction in retrieval is an attempt to relax that constraint without losing the sublinear search that justifies it. Two are worth understanding in depth, because they represent genuinely different bets.

Multi-vector users and late interaction

Start with the most obvious failure of a single user vector. Consider a user whose history is half competitive powerlifting and half French pastry. The user tower pools their history into one vector, which lands somewhere between the two clusters — in a region of the embedding space that corresponds to nothing. Nearest neighbours to that midpoint are neither lifting videos nor baking videos; they are whatever happens to sit in the void between them.

This is not a training failure. It is arithmetic. The mean of two distant unit vectors has small norm and points nowhere useful, and no amount of data fixes it while the representation is a single point.

The fix is to give the user K vectors instead of one. Approaches like MIND and ComiRec do this with a small routing or attention head that clusters the user's history into K interest vectors. Serving changes shape: you issue K independent ANN queries, take the top-k/K from each, and merge.

The max is the key operator. It says "this item is a good match if it matches any of the user's interests", which is exactly the semantics a mean cannot express. It is also the same operator as the MaxSim in ColBERT-style late interaction for text retrieval — the same idea, applied to the query side instead of the document side.

The main practical hazard is interest collapse: with a max-based loss, only the winning head receives gradient, so one head can capture everything while the other K−1 wither. Standard mitigations are a diversity or orthogonality penalty between the heads, and routing that is soft during early training and sharpens later. Serving cost is the honest price: K× ANN queries, which at K = 4 turns a 2 ms search into an 8 ms search unless you parallelize across shards.

Semantic IDs and generative retrieval

The more radical bet abandons the index entirely. Instead of storing a vector per item and searching for neighbours, give each item a short code and train a sequence model to generate the code of the item the user will want next. This is generative retrieval, and the clearest recommender formulation is the TIGER work of Rajput et al. (2023).

The construction has two stages.

Stage one: build the semantic ID. Take the item's content embedding (from a text encoder over its title and description, say) and quantize it with a residual-quantized variational autoencoder. Residual quantization works like long division with vectors:

1. Start with the content embedding z.
2. Find the nearest codeword c₁ in codebook 1. Emit its index.
3. Compute the residual r₁ = z − c₁.
4. Find the nearest codeword c₂ in codebook 2 to r₁. Emit its index.
5. Repeat for L levels. The item's semantic ID is the tuple of L indices.

With L = 3 levels and codebooks of 256 entries, the address space is

which is not enough for a hundred million items. You need four levels:

Even then, distinct items sometimes land on the same code (residual quantization is lossy), so implementations append a disambiguating suffix index to make the ID unique.

The property that makes this interesting is that the code is hierarchical and semantic: the first index is a coarse topic, the second refines it, and so on. Two similar items share a prefix. That means a brand-new item, quantized from its content alone, inherits a code that already sits in the right neighbourhood — cold start is solved by construction rather than by a special mechanism.

Stage two: generate. Train a sequence-to-sequence model on the user's history expressed as a sequence of semantic IDs, predicting the next item's ID token by token. Retrieval at serving time is beam search over the code tree — no ANN index, no hundred-million-row table, no vectors at all.

# Residual quantization: the whole idea in nine lines.
def rq_encode(z, codebooks):
    """z: (d,) content embedding.  codebooks: list of L arrays (256, d).
    Returns L integer codes — the item's Semantic ID."""
    codes, residual = [], z.copy()
    for C in codebooks:                      # one codebook per level
        dists = ((C - residual) ** 2).sum(axis=1)   # (256,)
        k = int(dists.argmin())
        codes.append(k)
        residual = residual - C[k]           # what level k could not explain
    return codes                             # e.g. [37, 201, 6, 148]


def rq_decode(codes, codebooks):
    """Reconstruct an approximation of z by summing the chosen codewords."""
    return sum(C[k] for C, k in zip(codebooks, codes))

# Retrieval becomes constrained decoding: at each step, only allow tokens that
# extend the current prefix to a real item. A trie over all semantic IDs does it.
def retrieve(seq_model, history_codes, trie, beam=50):
    beams = [([], 0.0)]
    for level in range(trie.depth):
        nxt = []
        for prefix, logp in beams:
            allowed = trie.children(prefix)               # prevents invalid IDs
            scores = seq_model.next_token_logprobs(history_codes, prefix)
            for tok in allowed:
                nxt.append((prefix + [tok], logp + scores[tok]))
        beams = sorted(nxt, key=lambda t: -t[1])[:beam]
    return [trie.item_for(p) for p, _ in beams]

Honest tradeoffs

Generative retrieval is genuinely exciting and it is not, today, a drop-in replacement for a two-tower model at industrial scale. The honest accounting:

Read the query-cost row carefully, because it is the crux. A two-tower query is one index lookup. A generative query is L sequential transformer decode steps, each with a beam of size B, and sequential steps cannot be parallelized away. At L = 4 and beam 50, you are running four small autoregressive steps in the request path where the two-tower model ran one search. That is affordable for a hundred thousand items and an open research question at a hundred million.

The strategically interesting reading is that the two ideas are converging rather than competing. Semantic IDs are useful inside a two-tower model: use the RQ codes as the item's features instead of a raw id, and you get hierarchical parameter sharing, graceful cold start, and a table whose size is set by the codebooks rather than by the catalog — which is quotient-remainder embedding again, except with semantically meaningful buckets instead of arithmetic ones. Several production systems have adopted exactly that, keeping ANN retrieval and taking only the ID scheme.

9 — Evaluation

You have a two-tower model. Is it good? This turns out to be the hardest question in the article, and the honest answer is that offline evaluation of a retrieval model is structurally unable to tell you. Understanding exactly why is what separates people who ship retrieval improvements from people who ship offline wins that do nothing.

Recall@k, from zero

Start with the metric everyone uses. Hold out a slice of interactions the model never trained on — usually a time slice, the last day or the last hour, because a random slice leaks the future into the past. For each held-out pair (user x, item y):

1. Build the user vector from features available before the interaction.
2. Retrieve the top k items from the index.
3. Score 1 if y is in that list, 0 otherwise.

Note that with exactly one relevant item per query, recall@k, hit-rate@k and precision@k × k are all the same number. The name "recall" is a holdover from settings with many relevant items per query.

Calibrate your expectations with the random baseline. With N = 10⁸ items and k = 500, a model that retrieves uniformly at random achieves

Against that floor, almost anything looks miraculous. A pure popularity baseline — always return the globally most-clicked 500 items — will often reach recall@500 in the range of 0.05 to 0.15, purely because engagement is so concentrated. That is your real baseline, and a distressing number of reported retrieval improvements do not clear it.

This is why you must always report recall alongside a popularity control, and better, report recall on the tail: restrict the held-out set to interactions with items outside the top 1% by popularity and measure recall there. A model that has learned genuine personalization keeps most of its recall on that slice; a model that has learned popularity falls off a cliff.

That last row is a discipline worth adopting. Measure the index and the model separately. Compute exact top-k by brute force on a sample of a few thousand queries, then measure what fraction of those exact neighbours your ANN structure returns. If ANN recall against exact is 0.95, your index costs you 5% and the rest is the model. Teams that conflate the two spend months tuning a model when the actual regression was an nprobe setting.

The offline-online gap

Now the structural problem. Read the definition of recall@k again and ask: where did the held-out interactions come from?

They came from your production system. A user engaged with item y because your current retrieval model surfaced y, your current ranker ranked it highly, and your current UI displayed it. Items the current system never showed cannot appear in the held-out set, because the user could not possibly have engaged with them.

So recall@k measures: how well does the new model reproduce the old system's choices?

Three practical responses, in increasing order of cost and rigour.

1. Evaluate on randomized traffic. Reserve a small slice of requests — a fraction of a percent — where the slate is filled by uniform or stratified random sampling instead of by the model. Interactions from that slice are exposure-unbiased, and recall computed on them is a genuine measurement. The slice is small, so the estimate is noisy, but it is unbiased noise rather than confident wrongness. Almost every serious recommendation team maintains such a slice, and it is the single highest-value piece of evaluation infrastructure you can build.

2. Inverse-propensity weighting. If you log the probability that the old system had of showing each item, you can reweight held-out interactions by the inverse of that propensity, in the same spirit as the logQ correction earlier. Items the old system rarely showed count for more. The weights have high variance and need clipping, and the estimate is only as good as your logged propensities, but it is a real improvement over naive recall.

3. Counterfactual replay on a slate. If your logs record the full candidate set that was shown, you can ask what the new model would have retrieved from that same set and evaluate against the observed outcome. Sound, and limited to comparisons within candidate sets the old system produced — which is exactly the thing retrieval is supposed to expand.

A/B realities: dilution and power

Eventually you run an experiment. Two facts about retrieval experiments will determine whether it tells you anything.

Fact one: the ranker dilutes you. Your improvement acts on the candidate set; the user sees a slate chosen by the ranker from that set. If the ranker was already finding good items among the old candidates, better candidates change nothing. Retrieval improvements are only visible to the extent that the ranker was candidate-limited.

Fact two: the arithmetic of detection is brutal. Work an example. Suppose your retrieval source contributes 30% of final impressions, and your change makes those impressions convert 4% better in relative terms. The end-to-end relative lift is

If your baseline conversion rate is p = 5%, the absolute effect you are trying to detect is

The standard sample-size rule for a two-arm test at 80% power and 5% significance is n ≈ 16 σ² / δ² per arm, with σ² = p(1 − p) for a binary outcome:

Four and a quarter million users, minimum, to see a real 4% improvement in your retrieval source. If you have ten million monthly users, this experiment consumes almost your entire population and runs for weeks. If you have one million, the experiment is not possible and no amount of patience fixes it, because you cannot buy variance reduction with time when the population is the constraint.

What you do instead: measure the thing your change acts on directly. Instrument per-source attribution — for every impression, log which retrieval source proposed it — and then measure your source's contribution rate (what fraction of final impressions it won) and its win rate (how those impressions performed). Both are far higher-signal than the diluted global metric, and both move within days rather than weeks. The global metric remains the decision criterion for shipping; the source metrics are how you steer.

10 — Reference Implementation

Everything above, assembled. This is the shape of a working two-tower training loop with the logQ correction, accidental-hit masking, mixed negatives, and a serving path. It is a sketch in the sense that the feature plumbing and the distributed setup are elided, but the parts that matter are all here and none of them is hand-waved.

"""Two-tower retrieval: training loop.

Shapes are annotated everywhere. B = batch, d = 64, H = hard negatives per row.
"""
import torch
import torch.nn.functional as F


def train_step(model, opt, batch, freq, sampler, step,
               hard_weight=0.01, use_hard=True):
    # ---- 1. Encode both sides ------------------------------------------
    u = model.user_tower(**batch["user"])          # (B, 64) unit norm
    v = model.item_tower(**batch["item"])          # (B, 64) unit norm
    ids = batch["item_id"]                         # (B,) int64
    B = u.size(0)

    # ---- 2. In-batch logits --------------------------------------------
    logits = model.score(u, v)                     # (B, B)

    # ---- 3. logQ correction: subtract log q from EVERY column ----------
    #        (including the diagonal — the positive is also drawn from q)
    log_q = torch.as_tensor(freq.log_q(ids.cpu().numpy()),
                            device=logits.device)  # (B,)
    logits = logits - log_q.unsqueeze(0)

    # ---- 4. Accidental hits: another row's positive is not a negative --
    dup = (ids.unsqueeze(0) == ids.unsqueeze(1))                   # (B, B)
    eye = torch.eye(B, dtype=torch.bool, device=logits.device)
    logits = logits.masked_fill(dup & ~eye, float("-inf"))

    # ---- 5. Mined hard negatives (no logQ — not sampled from q) --------
    if use_hard:
        hard_ids = sampler.mine(u.detach(), ids)                   # (B, H)
        vh = model.item_tower(**batch["hard_features"])            # (B, H, 64)
        hard = torch.einsum("bd,bhd->bh", u, vh) / model.log_tau.exp()
        # multiplicative blend weight == additive logit shift
        hard = hard + torch.log(torch.tensor(hard_weight, device=hard.device))
        logits = torch.cat([logits, hard], dim=1)                  # (B, B+H)

    # ---- 6. Loss: the positive is always column i ----------------------
    labels = torch.arange(B, device=u.device)
    loss = F.cross_entropy(logits, labels)

    opt.zero_grad(set_to_none=True)
    loss.backward()
    torch.nn.utils.clip_grad_norm_(model.parameters(), 5.0)
    opt.step()

    # ---- 7. Update the streaming frequency estimate AFTER using it -----
    freq.update(ids.cpu().numpy(), step)
    return loss.item()

The serving side, with the version guard that section 6 argued for:

"""Two-tower retrieval: offline index build + online query."""
import numpy as np


def build_index(item_tower, item_stream, model_version, d=64, pq_bytes=16):
    """Runs on a cluster. Emits a version-stamped, compressed index."""
    index = ANNIndex(dim=d, metric="ip", pq_bytes=pq_bytes,
                     version=model_version)
    for chunk in item_stream:                       # chunk: ~100k items
        with torch.no_grad():
            v = item_tower(**chunk.features)        # (100000, 64) unit norm
        index.add(chunk.ids, v.cpu().numpy().astype(np.float32))
    index.train_quantizer()                         # IVF centroids + PQ codes
    index.seal()                                    # immutable from here
    return index


class RetrievalService:
    def __init__(self, user_tower, model_version, base_index, fresh_index):
        self.user_tower = user_tower
        self.version = model_version
        self.base = base_index      # 100M items, rebuilt daily
        self.fresh = fresh_index    # thousands of items, brute force, minutes

    def retrieve(self, user_features, k=1000):
        # THE GUARD. A user vector from model v2 against an index built by v1
        # returns noise, silently, with every health check green.
        for idx in (self.base, self.fresh):
            if idx.version != self.version:
                raise VersionSkew(f"index {idx.version} != tower {self.version}")

        with torch.no_grad():
            u = self.user_tower(**user_features)     # (1, 64)
        u = u.cpu().numpy().astype(np.float32)

        a_ids, a_scores = self.base.search(u, k=k)          # approximate
        b_ids, b_scores = self.fresh.search(u, k=k // 10)   # exact, tiny

        ids = np.concatenate([a_ids, b_ids])
        scores = np.concatenate([a_scores, b_scores])
        order = np.argsort(-scores)[:k]
        return ids[order], scores[order]

And the checklist that turns the sketch into something you would actually deploy:

1. Normalize both towers and learn the temperature. Unnormalized towers drift into popularity ranking and break the index.
2. Apply logQ to every sampled column, positives included. Half-corrections introduce their own bias.
3. Mask accidental hits. Otherwise you train against your own positives.
4. Blend negatives roughly 100 easy : 1 hard, at most 2 hard per row. Hard-only is worse than random-only.
5. Mine hard negatives from rank 101-500, never from the top. The top is false negatives.
6. Refresh the negative index on a step clock, not a wall clock. Stale negatives are random negatives with a bill attached.
7. Version-stamp the tower and every index shard, and fail closed on mismatch.
8. Give the item tower content features. It is the only real answer to item cold start.
9. Reserve an exploration slice. It is both how new items get data and how you measure without exposure bias.
10. Measure the index separately from the model. ANN recall against exact search, on a fixed query sample, every build.

Connections

This article sits in the middle of a cluster of material on the site. If you want to go sideways or deeper:

• Recommender Systems — the Gleam that builds collaborative filtering, matrix factorization and the ranking stack from zero. Read it first if the funnel language here was new.
• CS224W 11 — Recommender Systems on Graphs — the graph-learning view of the same problem, where the user-item bipartite graph is the primary object rather than a table of features.
• PinSage — the Veanor on Pinterest's graph-convolutional item embeddings, which is the most-deployed answer to "what if the item tower were a GNN over the item graph".
• Dense Passage Retrieval and ColBERT — the text-retrieval siblings. DPR is a two-tower model with the towers replaced by BERT; ColBERT is the late-interaction relaxation referenced in section 8.
• Vector Databases — what is actually inside the ANN index: IVF, HNSW, product quantization, and the recall/latency knobs this article treated as a black box.
• Vector Embeddings — the geometry underneath everything here, including why cosine and inner product diverge when norms vary.
• Article 09 — Build a Semantic Spine — the same retrieval machinery at four orders of magnitude smaller scale, where everything can be precomputed at build time and shipped as files.
• Evaluation Statistics and Evaluation Plots — the sample-size arithmetic from section 9, done properly, including sequential testing and variance reduction.

References

The papers this article is built on, plus the ones worth reading next.

1. Covington, Adams & Sargin. "Deep Neural Networks for YouTube Recommendations." RecSys, 2016. ACM
2. Yi, Yang, Hong, Cheng, Heldt, Kumthekar, Zhao, Wei & Chi. "Sampling-Bias-Corrected Neural Modeling for Large Corpus Item Recommendations." RecSys, 2019. ACM
3. Huang, Sharma, Sun, Xia, Zhang, Pronin, Padmanabhan, Ottaviano & Yang. "Embedding-based Retrieval in Facebook Search." KDD, 2020. arXiv:2006.11632
4. Bengio & Sénécal. "Quick Training of Probabilistic Neural Nets by Importance Sampling." AISTATS, 2003.
5. Bengio & Sénécal. "Adaptive Importance Sampling to Accelerate Training of a Neural Probabilistic Language Model." IEEE Trans. Neural Networks, 2008.
6. Shi, Mudigere, Naumov & Yang. "Compositional Embeddings Using Complementary Partitions for Memory-Efficient Recommendation Systems." KDD, 2020. arXiv:1909.02107
7. Ginart, Naumov, Mudigere, Yang & Zou. "Mixed Dimension Embeddings with Application to Memory-Efficient Recommendation Systems." ISIT, 2021. arXiv:1909.11810
8. Xiong, Xiong, Li, Tang, Liu, Bennett, Ahmed & Overwijk. "Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval." ICLR, 2021. arXiv:2007.00808
9. Qu, Ding, Liu, Liu, Ren, Zhao, Dong, Wu & Wang. "RocketQA: An Optimized Training Approach to Dense Passage Retrieval." NAACL, 2021. arXiv:2010.08191
10. Karpukhin, Oğuz, Min, Lewis, Wu, Edunov, Chen & Yih. "Dense Passage Retrieval for Open-Domain Question Answering." EMNLP, 2020. arXiv:2004.04906
11. Khattab & Zaharia. "ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT." SIGIR, 2020. arXiv:2004.12832
12. Li, Liu, Wu, Xu, Zhao, Huang & Lee. "Multi-Interest Network with Dynamic Routing for Recommendation at Tmall." CIKM, 2019. arXiv:1904.08030
13. Cen, Zhang, Zou, Zhou, Yang & Tang. "Controllable Multi-Interest Framework for Recommendation." KDD, 2020. arXiv:2005.09347
14. Rajput, Mehta, Singh, Keshavan, Vu, Heldt, Hong, Tay, Tran, Samost, Kula, Yi & Sathiamoorthy. "Recommender Systems with Generative Retrieval." NeurIPS, 2023. arXiv:2305.05065
15. Zeghidour, Luebs, Omran, Skoglund & Tagliasacchi. "SoundStream: An End-to-End Neural Audio Codec." 2021. arXiv:2107.03312 — origin of the residual-quantization scheme reused for semantic IDs.
16. Johnson, Douze & Jégou. "Billion-scale Similarity Search with GPUs." IEEE Trans. Big Data, 2019. arXiv:1702.08734
17. Malkov & Yashunin. "Efficient and Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs." IEEE TPAMI, 2020. arXiv:1603.09320