Why does hard negative mining outperform 'just use a bigger batch' for embedding quality?

In early contrastive training, the model knows nothing. A random negative (a non-matching example) from the corpus is as likely to be near the query as the positive is. So the loss is high and the gradient is strong. The model learns coarse semantic structure quickly. After a few thousand steps, the geometry has settled. The model now places semantically related items near each other and unrelated items far apart. **The problem**: a random negative is now reliably far from the query in cosine space. The softmax in InfoNCE (the contrastive loss) gives it near zero probability. The loss for that pair is near zero, and it adds almost no gradient. Scaling batch size adds more random negatives, with diminishing returns. The remaining negatives are all in the "already easy" pile. **Hard-negative mining** is the fix. Instead of random sampling, you select negatives that are semantically similar to the query but not the correct positive. These sit near the model's current decision boundary, where it's still uncertain. The loss is real, the gradient is informative, and the model keeps learning. Models like E5 and BGE train with mined hard negatives, and papers report clear gains over random negatives.

Contrastive training saturates in a way batch size alone can't fix. The cause is in the gradient. In InfoNCE, a negative's gradient contribution scales with its softmax probability: $$\nabla_q \mathcal{L} \propto \sum_i p_i k_i - k^+, \quad p_i = \frac{\exp(q \cdot k_i / \tau)}{\sum_j \exp(q \cdot k_j / \tau)}$$ After early training, a random negative has cosine near zero with the query. With `τ ≈ 0.05`, its logit is tiny while the positive's logit is large. The softmax `p_i` for that random negative is near zero. It contributes almost no gradient. Adding more random negatives doesn't help. The positive's term dominates the sum in the denominator. Extra negatives with zero similarity barely move the loss. The MI bound `I(q; k+) ≥ log(N) - L` needs negatives that really compete with the positive to tighten. **Hard-negative mining** fixes this by selecting negatives with real similarity to the query. Three strategies: - **BM25-based**: retrieve top-K BM25 results, exclude the positive, use the rest. Lexically similar and hard. - **Prior-model top-K**: train an initial model, find top-K nearest neighbours of each query (excluding positives), use as hard negatives next stage. A curriculum. - Cross-encoder distillation: use a cross-encoder to label borderline candidates, train the bi-encoder to match. E5 and BGE-M3 both train with mined hard negatives. Retrieval papers such as DPR, ANCE, and RocketQA report clear gains from mined hard negatives at a fixed batch size. Caveat: mining introduces **false negatives** (relevant but unlabelled). Cross-encoder filtering or threshold-based denoising is needed at scale.