INFS7410 · Information Retrieval and Web Search · Week 5

Exercise 5 (challenge): mining negatives harder than BM25, worked solution

You are training a dense retriever. BM25 hard negatives help, but training progress is slow. How can you mine negatives that are harder than top-ranked BM25 documents? This page gives the short answer (ANCE-style self-mined negatives), the step-by-step reasoning, the gradient argument for why easy negatives slow training, and the cost trade-off.

1. The question and the short answer

Sources: slides 19, 22–25, 28–30 · Video 2 (DPR), 05:50–11:10 · Video 4 (ANCE) · Week 5 in-class exercise 5 (Week 5 lecture notes, in-class exercises)

Question. You are training a dense retriever. BM25 hard negatives help, but training progress is slow. How can you mine negatives that are harder than top-ranked BM25 documents?

Key ideaThe answer the question is looking for: mine the negatives from the dense retriever itself, as it trains: the ANCE strategy. Periodically checkpoint the model, use that checkpoint to embed the corpus and retrieve for the training queries with ANN search, and take the documents it ranks highly that are not relevant as the new negatives. These are, by construction, exactly the documents the current model finds hardest: harder than anything BM25 can supply. Refresh them from new checkpoints as training continues.

DPR (slides 19, 22–25) already combines three sources of negatives: random negatives from the whole corpus, BM25 hard negatives from the BM25 top 1000, and in-batch negatives (the other queries' positives). ANCE (slides 28–30) adds a fourth kind, chosen by the model being trained.

harder for the dense model Random negatives sampled from the whole corpus: easy In-batch negatives other queries' positives: medium, free to encode BM25 hard negatives share keywords with q: hard for a lexical model ANCE negatives (self-mined) ranked highly by the dense model itself: hard for this model
DPR's three negative sources get harder from random to BM25; ANCE's self-mined negatives are the hardest for the model being trained.
PracticeName DPR's three negative sources and say how hard each one is for the model.
AnswerRandom negatives from the whole corpus (easy: usually off-topic); in-batch negatives, the positives of the other queries in the batch (medium: same domain, and free because they are already encoded); BM25 hard negatives from the BM25 top-k with labelled positives excluded (hard for a lexical model: they share the query's keywords but are not relevant). DPR combines all three (slide 25).

2. Worked reasoning

Sources: slides 22–23, 28–30 · Video 4 (ANCE), 00:49–03:43 · Week 5 in-class exercise 5

The figure places the query, its relevant documents and the three kinds of negatives in one dense embedding space; the reasoning below refers to it.

dense embedding space (2-D sketch) ★ q ★ query vector relevant docs: cluster near q BM25 negatives: mostly far away, easy for the dense model random negatives: far or mixed ANCE negatives: ranked highly by the dense model itself; close to q, not relevant Hard for THIS model ≠ hard for BM25
Most BM25 and random negatives sit far from the query; the self-mined (ANCE) negatives sit close to it, among the relevant documents.

Worked example 1Step-by-step reasoning

1

Diagnose why BM25 negatives run out of steam. BM25 negatives are hard for a lexical model: they share keywords with the query but are not relevant. Your model, however, is a dense retriever: it scores by embedding similarity, and term overlap plays no direct part. A document that fools BM25 can sit far from the query in the dense embedding space.

2

Picture the embedding space. Plot the query, the relevant documents, and the candidate negatives, as in the embedding-space figure above (the 2-D sketch from Video 4).

Most BM25 negatives (orange triangles; yellow in the lecture figure) and random negatives (grey circles) sit far from the query vector. The dense model separates them with ease, the InfoNCE loss on them is near zero, and the gradient it gets from them is tiny (section 3 shows why): this is why training progress is slow. The valuable negatives (blue triangles) are the irrelevant documents that sit close to the query in the dense space.

3

Define what “harder than BM25” means. A negative is hard for the model in training if the model itself currently scores it highly for the query: it is a mistake the model is actively making. The model is the best judge of its own mistakes. So: ask the model.

4

Mine from checkpoints (the ANCE procedure).

  1. Every ~1000 training iterations, save a checkpoint of the model.
  2. Use the latest checkpoint to embed the corpus and build an ANN (approximate nearest neighbour) index.
  3. Run the training queries through it and retrieve the top-ranked documents.
  4. Discard the ones labelled relevant; keep the highly ranked non-relevant ones as negatives.
  5. Train on these, and refresh them from the next checkpoint so the negatives stay hard as the model improves.

The loop figure below the example shows the cycle.

5

State the trade-off (full marks needs this). The negatives must be re-mined again and again (the corpus is re-embedded from each new checkpoint), so training cost is much higher than DPR's. Empirically it produces better dense retrievers than BM25 + in-batch negatives, and query-time cost is unchanged: the final model is still a plain bi-encoder.

ResultReplace (or supplement) BM25 hard negatives with self-mined, checkpoint-refreshed hard negatives: negatives ranked highly by the current dense model itself (ANCE, “Approximate nearest neighbour Negative Contrastive Estimation”). They target exactly the errors the model is still making, which BM25 negatives are unable to do.
Train model ≈ every 1000 iterations Save checkpoint frozen copy Retrieve with checkpoint rank corpus for training queries (ANN search) Keep top-ranked non-relevant docs = new hard negatives feed back as training negatives; repeat throughout training
ANCE refreshes its hard negatives from the latest checkpoint, so they keep matching the model's current mistakes.
PracticeIn step 4, why must the documents labelled relevant be discarded from the mined list?
AnswerA relevant document ranked highly is a correct answer. Training on it as a negative would push relevant documents away from the query and teach the model the wrong thing. Excluding labelled positives avoids these false negatives; unlabelled relevant documents can still slip through, which is a known risk of any mined negatives.

3. Why easy negatives give a weak training signal

Sources: slides 21, 28 · Video 2 (DPR), 04:12–05:50 · Video 4 (ANCE), 01:37–02:25 · Exercise 3 solution

Video 4 says there is “not much the dense retriever learns” from far-away negatives. The InfoNCE loss from Exercise 3 makes this precise: the gradient with respect to each negative's similarity equals that negative's softmax probability.

∂L∂sj−=P(pj−∣q)=esj−es++∑k=1nesk−∂L∂s+=P(p+∣q)−1 \begin{aligned} \frac{\partial L}{\partial s_j^-} &= P(p_j^- \mid q) \\ &= \frac{e^{s_j^-}}{e^{s^+} + \sum_{k=1}^{n} e^{s_k^-}} \\ \frac{\partial L}{\partial s^+} &= P(p^+ \mid q) - 1 \end{aligned}
Where
LL
the InfoNCE loss for one query
s+s^+
sim(q,p+)\mathrm{sim}(q, p^+), the positive's similarity
sj−s_j^-
sim(q,pj−)\mathrm{sim}(q, p_j^-), the similarity of the jj-th negative
k, nk,\ n
index over the negatives, and the number of negatives
∂L/∂s\partial L / \partial s
gradient: how much the loss changes when that similarity changes slightly; training moves each similarity against its gradient
P(pj−∣q)P(p_j^- \mid q)
the softmax probability the model currently gives to negative jj
P(p+∣q)P(p^+ \mid q)
the softmax probability of the positive
Read it aloud The partial derivative of L with respect to s-j-minus equals the probability of negative j given q, which is e to the s-j-minus divided by e to the s-plus plus the sum over all negatives of e to their similarity. The partial derivative of L with respect to s-plus equals the probability of the positive given q, minus one.
Formula in plain words Each negative pushes back on the model in proportion to how much probability the model currently wastes on it. A negative the model already scores far below the positive has a tiny probability, so its gradient is tiny and the update barely moves anything. A negative the model scores close to (or above) the positive takes a large share, so its gradient is large: that is where learning happens. The positive's gradient is negative (P−1<0P - 1 < 0), so training raises the positive's similarity, and the push fades as P(p+∣q)P(p^+ \mid q) approaches 1.

Worked example 2Gradient share of a far-away negative

Take Exercise 3's scores (positive 0.9; negatives 0.3, 0.1, 0.4) and add one easy random negative with similarity −3 (illustrative).

1
Exponentials: positive=2.4596negatives=1.3499, 1.1052, 1.4918easy negative=e−3=0.0498total=6.4562 \begin{aligned} \text{positive} &= 2.4596 \\ \text{negatives} &= 1.3499,\ 1.1052,\ 1.4918 \\ \text{easy negative} &= e^{-3} = 0.0498 \\ \text{total} &= 6.4562 \end{aligned}
2
Gradients on the negatives (their probabilities): 0.209, 0.171, 0.2310.209,\ 0.171,\ 0.231 for the exercise negatives, and for the easy negative 0.04986.4562=0.0077 \frac{0.0498}{6.4562} = 0.0077
3
The loss moves from 0.957 to −ln⁡(2.45966.4562)≈0.965 -\ln\Big(\frac{2.4596}{6.4562}\Big) \approx 0.965 The easy negative adds under 0.01.
ResultThe far negative receives a gradient about 30 times smaller than the hardest negative (0.0077 against 0.231). A batch full of such negatives teaches the model almost nothing new, which is exactly why training with only easy (or lexically hard but dense-easy) negatives is slow.
Gradient on each negative = its probability p₃⁻ (sim 0.4) p₁⁻ (sim 0.3) p₂⁻ (sim 0.1) random (sim −3) 0.231 0.209 0.171 0.008 far-away negatives give almost no training signal
The gradient each negative contributes is its current softmax probability, so negatives close to the query dominate learning.
PracticeIn Exercise 3 (four candidates), suppose p₃⁻ rises from 0.4 to 0.9, level with the positive. What happens to its gradient and to the loss?
Recompute the softmax with e0.9e^{0.9} for both the positive and p₃⁻.
AnswerThe new total is 2.4596+1.3499+1.1052+2.4596=7.3742 2.4596 + 1.3499 + 1.1052 + 2.4596 = 7.3742 The gradient on p₃⁻ rises from 0.233 to 2.45967.3742≈0.334 \frac{2.4596}{7.3742} \approx 0.334 The positive's probability falls to 0.334, so the loss rises to −ln⁡0.334≈1.10-\ln 0.334 \approx 1.10. A harder negative produces both a larger loss and a stronger gradient.

4. Trade-offs and exam tips

Sources: slides 19, 22–25, 28–30 · Video 2 (DPR), 06:40–11:10 · Video 4 (ANCE), 02:25–03:43 · Week 5 in-class exercise 5

Negative typeWhere it comes fromDifficulty for the dense modelExtra training cost
Randomsampled from the whole corpuseasylow (each must be encoded)
In-batchthe positives of the other queries in the batchmedium (same domain)none: already encoded
BM25 hardBM25 top-k (for example the top 1000), labelled positives excludedhard for a lexical model; often easy for a dense oneone BM25 run per training query
ANCE (self-mined)top-ranked non-relevant documents from the latest checkpoint, via ANN searchhard for this modelre-encode the corpus and rebuild the ANN index about every 1000 iterations
Exam angleThe key sentence to write: “hard for BM25 ≠ hard for the dense model: mine negatives from the dense model's own rankings, refreshed via checkpoints.”
Watch out
PracticeA teammate proposes re-mining ANCE negatives every 10 iterations instead of every 1000. What is the trade-off?
AnswerThe negatives would track the model's current mistakes more closely, but each refresh means re-encoding the whole corpus with the checkpoint and rebuilding the ANN index, so training cost would grow about 100-fold for the mining step. The checkpoint interval balances negative freshness against that cost; query-time cost is unaffected either way.

5. Summary and study checklist