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.
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.
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).
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.
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).
Every ~1000 training iterations, save a checkpoint of the model.
Use the latest checkpoint to embed the corpus and build an ANN (approximate nearest neighbour) index.
Run the training queries through it and retrieve the top-ranked documents.
Discard the ones labelled relevant; keep the highly ranked non-relevant ones as negatives.
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.
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.
index over the negatives, and the number of negatives
∂L/∂s
gradient: how much the loss changes when that similarity changes slightly; training moves each similarity against its gradient
P(pj−∣q)
the softmax probability the model currently gives to negative j
P(p+∣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<0), so training raises the positive's similarity, and the push fades as P(p+∣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).
Gradients on the negatives (their probabilities): 0.209,0.171,0.231 for the exercise negatives, and for the easy negative
6.45620.0498=0.0077
3
The loss moves from 0.957 to
−ln(6.45622.4596)≈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.
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.9 for both the positive and p₃⁻.
AnswerThe new total is
2.4596+1.3499+1.1052+2.4596=7.3742
The gradient on p₃⁻ rises from 0.233 to
7.37422.4596≈0.334
The positive's probability falls to 0.334, so the loss rises to −ln0.334≈1.10. A harder negative produces both a larger loss and a stronger gradient.
BM25 top-k (for example the top 1000), labelled positives excluded
hard for a lexical model; often easy for a dense one
one BM25 run per training query
ANCE (self-mined)
top-ranked non-relevant documents from the latest checkpoint, via ANN search
hard for this model
re-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
Mention why easy negatives slow training: they contribute near-zero loss/gradient, so most of the batch teaches the model nothing new.
Mention the cost: periodic corpus re-encoding + ANN index rebuilds make training much more expensive than DPR. A good answer names the trade-off along with the trick.
Related credit-worthy additions: exclude labelled positives from the mined set (avoid false negatives), and combine with in-batch negatives, which stay free.
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
Answer: self-mined, checkpoint-refreshed hard negatives (ANCE): top-ranked non-relevant documents from the dense model's own ANN retrieval.
BM25 negatives are hard for a lexical model; many sit far from the query in the dense space.
Under InfoNCE each negative's gradient equals its softmax probability, so far-away negatives give almost no signal.
Cost: repeated corpus re-encoding and ANN rebuilds during training; query-time cost is unchanged.
Exclude labelled positives; keep in-batch negatives, which are free.