RecSys Part II · Candidate generation · chapter 7 of 19
Two-tower models: folding, negatives and LogQ
The move from learned vectors to computed ones — and the main trap along the way. A ranking loss that works excellently at the second stage is fatal for a candidate generator, and the reason is not the quality of the model but the degeneracy of the problem. Then comes the right formulation through a softmax over the catalogue, and the three engineering questions it raises: where to get negatives, what is wrong with them, and how that is fixed.
- Folding is degeneracy, not overfitting. If groups are never compared with each other, the loss falls apart into independent subproblems, and the relative placement of the groups is determined by nothing at all.
- The simulation: without cross-group negatives, half of the top 5 comes from another group. And inside its own group such a model is better: 0.392 against 0.362. It is not broken, it is undefined outside the training support.
- A negative's contribution to the gradient is \(\propto P(d \mid u)\) — how high the model itself placed it. A hard negative weighs 67 times more than a random one.
- The more useful the negatives, the stronger the bias they introduce. The choice of source and the LogQ correction are two halves of one decision.
1. Why two towers
Matrix factorisation ran into three things: no cold start for items, no context, no features. All three are removed by one move — make the vector computed rather than learned.
$$ s(u, i) \;=\; \bigl\langle f_\theta(\text{features of } u),\; g_\phi(\text{features of } i) \bigr\rangle $$One could feed the pair \((u, i)\) into a single network and get a score. That is what a ranker does, and the quality will be higher. But for candidate generation such an architecture is unusable arithmetically: to find the top over the catalogue you would have to run the network \(|I|\) times per request.
Splitting into towers gives the thing the whole exercise is for: item vectors are computed in advance, put into an ANN index, and at request time all that remains is to compute one user vector and go to the index. The price is that the score has to be an inner product, that is, interaction between \(u\) and \(i\) can only happen at the very end.
This is the fundamental trade: two towers sacrifice expressiveness so that half the computation can be done before the request arrives.
2. Folding: why a ranking loss does not work here
The temptation is understandable: we already have a ranking loss that works well. Let us train the candidate generator with it too. It will turn out badly, and working out why is half this chapter.
What «impression-aware» means
The term describes the composition of the training set. A row appears in the log only if the item was shown. A pair the previous system did not select never gets into the dataset — neither as a positive nor as a negative.
$$ P(\text{click} \mid \text{shown},\, u, i) \qquad\text{instead of}\qquad P(\text{relevant} \mid u, i) $$In the pairwise formulation negatives are taken from the same impression. So every comparison the model has ever made happened inside a single slate — that is, inside a set the previous system judged suitable for this user.
Between «a good item for one audience» and «a good item for another» there has not been a single comparison: they never appeared in the same output.
The mechanism: the problem falls apart
The term was introduced by Xin et al.: the unintended overlap of disjoint groups of users and items in a low-rank space, caused by mishandling missing data.
Suppose the matrix of observations is block-diagonal: \(K\) groups of users, \(K\) groups of items, interactions only inside the blocks. If unshown pairs do not enter the loss, then between the users of group \(k\) and the items of group \(l \ne k\) there is not a single constraint.
With no constraints, the loss falls apart into \(K\) independent subproblems. Inside a block the embeddings settle correctly, but the placement of the blocks relative to each other is determined by nothing: any of them is equally optimal. One of those optima is the one where the blocks lie on top of each other.
This is not overfitting and not poor convergence but a degeneracy of the problem: it has a continuum of solutions with the same loss, and the optimiser honestly returns one of them.
- Related. The user could have had an opinion but did not see the item; or the item is so popular that its absence is itself a signal. This is where lucky unexpected recommendations come from.
- Unrelated. The item does not interest the user in principle — children's cartoons and horror films, a film in a language they do not speak. The overwhelming majority of pairs are of this kind.
Folding is assigning high similarity to unrelated missing entries. Assigning it to related ones is, on the contrary, the generalisation the model is built for.
Hence an unpleasant consequence: generalisation and folding are the same action. The only difference is which kind of missing entry the model landed in. So «being more careful» does not help — the ability to recommend anything new dies along with the folding.
Why is the matrix of observations blocky in the first place? Country, language, interests, targeting. And the better the previous system works, the sharper the blocks — cutting off the irrelevant is exactly what it does. A good system generates data on which a candidate generator cannot be trained.
- Two disjoint groups, two-dimensional embeddings. On the left negatives are taken from the user's own group — that is what training on impressions looks like. On the right, from the whole catalogue.
- Pull the epochs up from zero: on the right the groups move apart in opposite directions, on the left they stay mixed — it costs the loss nothing.
- At 40 epochs, on the left 50.8% of the top 5 over the catalogue are items of the other group. With two groups, random guessing gives 50%: there is no signal about membership at all. On the right — 0.0%.
- The important part is the bottom rows. Inside its own group the «impression» model is better: HitRate@5 is 0.392 against 0.362. It is not trained worse, it spent all its capacity on the task the loss actually set.
- Widen the candidates to the whole catalogue: 0.392 → 0.196, exactly half. For the correctly trained model, 0.362 → 0.362. That pair of numbers is the diagnosis of folding.
What to say in an interview: «A ranker is trained impression-aware and makes all its comparisons inside a slate. A candidate generator is applied to the whole catalogue, so it needs negatives from the catalogue. It is checked by the difference between HitRate on the original pool and over the whole catalogue».
In the work of Xin et al., by MSE on a held-out set the model that ignores missing entries came out better than the one that accounts for them. The metric votes for the broken model.
The cause is common to all standard metrics: they are computed on observed data. The held-out set is impressions too, and it too lies inside the blocks. The metric physically cannot see what happens between blocks.
Plus an observation of the authors: the junk recommendations arrive mixed in with the good ones. An error like that is caught neither by tests nor by a dashboard — it surfaces as complaints.
Yes, and that is the main reason retrieval is trained with a batch softmax. A batch is drawn from the global stream rather than from one user's slate, so it contains representatives of every group, and the loss demands: «the user's score for their own item is higher than for the item of a neighbour in the batch».
But what saves you is not the words «in-batch» — it is global shuffling. If the data is sharded by country or segment, if a separate model is trained per region, or if examples are grouped by session for read locality — the batch neighbours are «one's own» again. In the simulation that regime gives 43.8% of foreign items in the top 5, that is, folding is back in full.
3. The right formulation: a softmax over the catalogue
A change of question, from which everything follows.
«Item \(i\) was shown to user \(u\). Will they click?» Binary classification on impressions — that is, the ranking formulation with all the problems of folding.
«We know user \(u\) chose something. What could it have been?» A problem of extreme classification: every item of the catalogue is its own class.
The denominator runs over the whole catalogue — and that is exactly what was missing: cross-group constraints appear by construction.
The distribution comes from multiplying the hidden state by a decoder matrix: \(s_\theta(u,i) = \langle g_\theta(u), v_i\rangle\). And the decoder is simply a matrix of trainable item embeddings.
So «extreme classification with a softmax» and «two towers» are one and the same construction described from different sides. It is useful to know both languages: papers use both.
A full softmax is not computable
A denominator with a million terms cannot be computed at every step. The catalogue is replaced by a sample — that is sampled softmax, and the whole question is where to draw it from.
Look at the gradient of the full softmax loss. Besides the term that pulls the positive up, there is a sum over the catalogue:
$$ \sum_{j \in \mathcal{I}} P(j \mid u)\, \nabla_\theta s_\theta(u, j) $$The factor \(P(j \mid u)\) is the probability the model itself produces. An item's contribution to the gradient is proportional to how high the model has already placed it. Numerically, for a positive with a score of 3.0:
| Negative | Score | \(P(d\mid u)\) | Contribution to the gradient |
|---|---|---|---|
| random from the catalogue | −2.0 | 0.0035 | ×1 |
| popular (a typical in-batch one) | +0.5 | 0.0430 | ×11 |
| hard negative | +2.8 | 0.4292 | ×67 |
The numbers are reproduced by the script _tools/twotower.py in this repository.
Hence the phrase «a full softmax mines hard negatives by itself»: nobody looks for them — the weights are assigned automatically, and almost all the mass of the gradient goes to those the model has wrongly placed high. That is exactly the property lost when the catalogue is replaced by a sample.
4. Where to get negatives
An item the current model scored highly which is not a positive. The definition is relative to the model, not to the content: what is hard at epoch one will be easy by epoch ten.
Hence: «similar in content» and «hard» are different things. And the correct source is unreachable in principle: to know who is hard right now you would have to score the whole catalogue, that is, do exactly what we are avoiding. All practical sources are approximations.
| Source | What we take | The distribution \(Q\) | Pros | Cons |
|---|---|---|---|---|
| Uniform | random items of the catalogue | \(1/|\mathcal{I}|\) | unbiased \(Q\), no correction needed | almost all are «easy», the contribution is minimal, you need a great many |
| In-batch | the positives of other users in the same batch | unigram, \(Q \propto\) popularity | free computationally, noticeably «harder» than uniform ones | biased towards the popular, \(Q\) cannot be controlled |
| Hard | a high score from the current model | concentrated on the head | maximum contribution for a minimum of negatives | many false negatives, training falls apart easily |
| Mixed | a mixture of a base and hard ones | a mixture with a known proportion | \(Q\) is known explicitly, the proportion is a lever | one more hyperparameter |
Why in-batch negatives are «harder» than uniform ones. An in-batch negative is somebody's positive, that is, an item somebody really chose. So on average it is more popular than a random one, and the model scores the popular higher. A higher score → a larger weight \(P(d\mid u)\) → a larger contribution. That is why fewer of them are needed for the same quality.
Why they are «free». The item tower has already computed the embeddings of all \(B\) items in the batch — they are needed as positives. Using them as negatives means reusing what has been computed: instead of \(B\) inner products, one \(B \times B\) matrix. Not a single extra pass through the network.
As soon as negatives are drawn not uniformly but from \(Q\), the estimate of the gradient stops being unbiased: items with a large \(Q(d)\) land in the sample more often and are punished more often than they should be. The model learns not \(\log p\) but \(\log p - \log Q\).
The «harder» and more useful the negatives, the stronger the bias they introduce. The choice of source and the correction are two halves of one decision, and separately they do not work.
The widget with the distributions of negatives is on the trainer page and in the catalogue.
5. The LogQ correction
Where the bias comes from
A batch is drawn from a stream of interactions, not from the catalogue. So an item's probability of ending up in a batch equals its share of the log — that is, its popularity, and popularity follows Zipf. With a catalogue of 2000 and \(\alpha = 1.5\):
| Group of the catalogue | Share of appearances in a batch | Skew against a fair share |
|---|---|---|
| top 4% | 93.1% | 23× |
| the other 96% | 6.9% | 0.072× |
The numbers are reproduced by the script _tools/twotower.py.
The gap between the groups is 322×. At \(B = 1024\) the most popular item ends up as a negative about 399 times per batch: it is somebody's positive for nearly every second pair. In a full softmax every item stands in the denominator exactly once.
The loss pushes the score of a negative down. Since a popular item is in the denominator orders of magnitude more often, it gets that many more downward pushes than a full softmax implies.
That is, the bias works against the popular, not in its favour. A model without the correction systematically underestimates the scores of hits — even though intuition suggests the opposite.
Deriving the correction
We need the gradient of the full softmax loss. For a positive \(d_+\):
$$ \nabla_\theta\bigl(-\log P(d_+\mid u)\bigr) \;=\; -\nabla_\theta s_\theta(u,d_+) \;+\; \underbrace{\sum_{d} P(d\mid u)\,\nabla_\theta s_\theta(u,d)}_{\text{unaffordable}} $$The second term is an expectation under the target distribution \(P(\cdot\mid u)\). Let us estimate it by sampling from the proposal \(Q\):
$$ \mathbb{E}_{d \sim P}\bigl[\nabla_\theta s\bigr] \;=\; \mathbb{E}_{d \sim Q}\Bigl[\tfrac{P(d\mid u)}{Q(d)}\,\nabla_\theta s\Bigr] \;\approx\; \sum_{d \in N} \frac{\omega_d}{\sum_{d'}\omega_{d'}}\,\nabla_\theta s_\theta(u,d) $$where the weights of the self-normalised estimate are
$$ \omega_d \;=\; \frac{e^{\,s_\theta(u,d)}}{Q(d)} \;=\; e^{\,s_\theta(u,d) - \log Q(d)} $$That is the whole correction: dividing by \(Q\) inside the exponent turns into subtracting \(\log Q\) from the logit:
$$ s^{c}_\theta(u,d) \;=\; s_\theta(u,d) - \log Q(d) $$It reads directly: the more often an item lands in the sample, the more we subtract, the smaller its weight in the denominator — and the more weakly it is punished. By exactly the factor by which it is over-represented.
- This is not a diagram but real training: two models — with the correction and without — learn on the same stream of batches.
- The teal points fall on the «learned = truth» diagonal. The pink ones do not, and the larger the point, the further down it has drifted — the popular is being underestimated.
- Without the correction the score correlates with \(\log p - \log Q\) — the model learned exactly what the theory predicts rather than what is wanted.
- With uniform popularity the correction changes nothing: \(Q\) is a constant, and subtracting a constant does not touch the order.
What to say in an interview: «In-batch negatives come from the popularity distribution, so without a correction the model converges to \(\log p - \log Q\) and sinks the popular. LogQ subtracts \(\log Q\) from the logit right during training».
Where to get \(Q\) on a stream
The formula requires \(Q(d)\) — the probability of an item landing in a random batch. If the catalogue is fixed, that is simply a frequency. On a stream there is no vocabulary, the distribution drifts, and training is distributed.
A technique from the work of Yi et al.: instead of a frequency, estimate \(\delta\) — the average number of steps between two consecutive appearances of an item in a batch. Then \(p = 1/\delta\).
We keep two hash arrays: \(A[h(y)]\) — the step of the last appearance, \(B[h(y)]\) — a running estimate of \(\delta\). At step \(t\):
$$ B[h(y)] \leftarrow (1-\alpha)\,B[h(y)] + \alpha\bigl(t - A[h(y)]\bigr), \qquad A[h(y)] \leftarrow t $$The estimate is \(\hat p = 1/B[h(y)]\). The bias tends to zero as \(t\) grows; \(\alpha\) is the usual compromise between how fast the initialisation error is forgotten and the variance.
Collisions understate the interval (several items update one bucket) and therefore overstate the frequency. The cure is as in a count-min sketch: several independent pairs of arrays and \(\hat p = 1/\max_i B_i[h_i(y)]\) — the maximum, because every individual estimate is understated.
Yang et al. point out a second problem beyond the bias. An item with no user feedback will never get into the training data as a positive — which means that under in-batch sampling it will never become a negative either. Nobody has ever pushed its embedding away.
This is the same mechanism as folding, only for a single item: fresh and tail items get arbitrarily high scores and leak into the output.
Mixed Negative Sampling adds \(B'\) items to the batch, sampled uniformly from the corpus rather than from the log. Then \(Q\) becomes an explicit mixture of the unigram and the uniform distribution, and \(B'\) is the knob that controls that mixture.
6. Cosine and temperature
Empirically \(u \leftarrow u/\lVert u\rVert\), \(v \leftarrow v/\lVert v\rVert\) improves both trainability and retrieval quality. The reason is familiar from the chapter on biases: with an inner product the norm does not cancel, and in training it grows with popularity.
But normalisation has a side effect: the logits end up squeezed into \([-1, 1]\), and a softmax over them is nearly uniform.
Logits \((1, -1, -1, -1, -1)\) — one right answer, the rest clearly worse:
| \(\tau\) | softmax | weight of the right answer |
|---|---|---|
| 1.00 | 0.649 · 0.088 · 0.088 · 0.088 · 0.088 | 0.649 |
| 0.50 | 0.932 · 0.017 · 0.017 · 0.017 · 0.017 | 0.932 |
| 0.20 | 1.000 · 0.000 · 0.000 · 0.000 · 0.000 | 0.9998 |
The numbers are reproduced by the script _tools/twotower.py.
Without temperature the right answer gets 64.9% of the mass; at \(\tau = 0.5\) it gets 93.2%. That is, on squeezed logits the softmax barely distinguishes right from wrong, and the gradient is smeared.
The options: fix \(\tau\); use a schedule that decreases it gradually; or make it trainable — then it becomes a learned measure of the model's confidence.
Interview questions
What is folding and why is it fatal for a candidate generator?
The overlap of disjoint groups of users and items in embedding space. The cause is formal: if unshown pairs do not enter the loss, there is not a single constraint between the users of one group and the items of another, the loss falls apart into independent subproblems, and the relative placement of the groups is determined by nothing. One of the equally valid optima is the one where the groups lie on top of each other.
This is degeneracy, not overfitting. It does not bother a ranker: it is applied to candidates from the same system that produced the logs. A candidate generator goes into an ANN over the whole catalogue — and gets items of another group with a high score.
The diagnosis: the difference between HitRate on the original pool and over the whole catalogue. In the simulation, 0.392 against 0.196 with 50.8% of foreign items in the top 5; for the model with catalogue negatives, 0.362 against 0.362 and 0.0%.
Why does a folded model work better inside its own group?
Because it is not broken. It spent all its capacity on exactly the task the loss set — telling items apart inside the shown pool — and it does that well: 0.392 against 0.362 for the correctly trained one.
The problem is that outside the training support it is undefined. Widening the candidate set to the catalogue costs it half its quality (0.392 → 0.196), while the correct model loses nothing.
This also explains why folding is invisible offline: the metrics are computed on a held-out set, and that set was collected by the same policy and lies inside the blocks too.
Do in-batch negatives solve the folding problem?
Yes, and that is the main reason retrieval is trained with a batch softmax. A batch is drawn from the global stream, so it contains representatives of every group and the loss creates cross-group constraints.
But what saves you is not «in-batch» — it is global shuffling. If the data is sharded by country or segment, if a separate model is trained per region, or if examples are grouped by session, the batch neighbours are «one's own» again and folding returns: 43.8% of foreign items in the top 5 in the simulation.
And at the level of individual items in-batch fixes nothing: an item with no feedback will never become either a positive or a negative, because only positives get into a batch. Hence Mixed Negative Sampling with a uniform addition from the corpus.
Why does a negative's contribution to the gradient depend on how the model scored it?
The gradient of a full softmax contains a sum over the catalogue with the factor \(P(d \mid u)\) — the probability the model itself produces. An item with a low score enters with almost zero weight: the model has already understood everything about it.
Numerically, with a positive scoring 3.0: a random negative scoring −2 contributes ×1, a popular one scoring +0.5 contributes ×11, a hard negative scoring +2.8 contributes ×67.
Hence the phrase «a full softmax mines hard negatives by itself»: nobody looks for them, the weights are assigned automatically. That property is what is lost when the catalogue is replaced by a sample, and the choice of negative source is an attempt to get it back.
Derive the LogQ correction and explain what it does.
The gradient of a full softmax needs the expectation of \(\nabla s\) under the target distribution \(P(\cdot \mid u)\). We sample from a proposal \(Q\) and apply importance sampling: the weight becomes \(\omega_d = e^{s}/Q(d) = e^{\,s - \log Q(d)}\).
That is, dividing by \(Q\) inside the exponent is subtracting \(\log Q\) from the logit: \(s^c = s - \log Q(d)\).
The meaning: the more often an item lands in the sample, the more we subtract and the smaller its weight in the denominator — it is punished more weakly by exactly the factor by which it is over-represented. Without the correction the model converges to \(\log p - \log Q\) and systematically underestimates the popular — the bias works against hits, not in their favour.
How do you estimate Q on a stream with no fixed vocabulary?
Estimate not the frequency but the average number of steps between an item's appearances in a batch: \(p = 1/\delta\). Two hash arrays are kept — the step of the last appearance and a running average of the interval, updated as \(B \leftarrow (1-\alpha)B + \alpha(t - A)\).
The scheme works without a fixed vocabulary, adapts to drift, and lives on parameter servers under distributed training.
Collisions understate the interval and therefore overstate the frequency, so several independent pairs of arrays are used and the maximum over them is taken — every individual estimate is understated, and the maximum is closer to the truth.
Why normalise the embeddings, and why is temperature then needed?
Normalisation removes the influence of the norm, which grows with popularity during training: without it the inner product systematically prefers the popular regardless of relevance.
But after normalisation the logits are squeezed into \([-1,1]\) and a softmax over them is nearly uniform. On logits \((1,-1,-1,-1,-1)\) the right answer gets only 64.9% of the mass — the gradient is smeared between the right one and the clearly wrong ones.
The temperature \(s/\tau\) brings the sharpness back: at \(\tau = 0.5\) the weight of the right answer is 93.2%. It is fixed, scheduled, or made trainable.
One-screen cheat sheet
Two towers
Item vectors are computed in advance and go into an index. The price — interaction only through an inner product.
Folding
The loss falls apart into K subproblems, the placement of groups is undetermined. 50.8% foreign in the top 5; inside a group the model is even better.
The formulation
Not \(P(y{=}1|u,i)\) but \(P(i|u)\) — a softmax over the catalogue. Cross-group constraints by construction.
Negatives
Contribution \(\propto P(d|u)\): random ×1, in-batch ×11, hard ×67. Hard is a property of the model, not of the content.
LogQ
\(s^c = s - \log Q\) from importance sampling. Without it the model learns \(\log p - \log Q\) and sinks the popular.
Temperature
After normalisation the logits are in [−1,1] and the softmax is nearly uniform: 64.9% against 93.2% at \(\tau=0.5\).
Primary sources
- D. Xin, N. Mayoraz, H. Pham, K. Lakshmanan, J. R. Anderson. Folding: Why Good Models Sometimes Make Spurious Recommendations, RecSys 2017 — related and unrelated missing entries, the formal cause, the folding metric.
- X. Yi, J. Yang, L. Hong et al. Sampling-Bias-Corrected Neural Modeling for Large Corpus Item Recommendations, RecSys 2019 — LogQ and the streaming frequency estimate.
- J. Yang, X. Yi et al. Mixed Negative Sampling for Learning Two-tower Neural Networks in Recommendations, WWW 2020 — selection bias and the knob for \(Q\).
- Y. Bengio, J.-S. Senécal. Adaptive Importance Sampling to Accelerate Training of a Neural Probabilistic Language Model, 2008 — where the idea of correcting the logit by \(\log Q\) came from in the first place.
- The numbers in this chapter:
_tools/twotower.pyin this repository.