Hard-Negative Mining and Debiased Contrastive Training (ANCE)

Overview & motivation

Contrastive learning ended on a debt. It proved that the InfoNCE gradient on a negative is its softmax weight — $\partial \mathcal{L}/\partial s_i^- = p_i/\tau$ with $p_i = e^{s_i/\tau}/\sum_j e^{s_j/\tau}$ — so the hardest negative, the one nearest the query, dominates the push. It then named the catch it would not resolve: in retrieval the sampled negatives “include false negatives,” the contrastive setup “assumes TRUE negatives,” and choosing better, harder negatives without falling into that trap is “a topic of its own.” The dual-encoder topic deferred the same thing, calling the BM25 hard-negative recipe “an empirical engineering choice whose mining theory belongs to the negative-sampling topic.” This is that topic. We take the gradient theorem as given, mine the hard negatives it points to, and pay the false-negative bill it warned about.

The arc is four movements. First, why we mine: a random negative is near-orthogonal to the query, so its gradient weight is tiny and the encoder learns almost nothing from it; the same-sector hard negatives a miner surfaces carry the gradient. Second, the catch: mining samples near the anchor, and near the anchor is exactly where unlabeled true positives live, so the mined “negatives” are contaminated by accidental positives at a rate $\tau^+$ . Third, the fix, and the one theorem of the topic: the debiased contrastive estimator recovers the true-negative signal from contaminated samples. Fourth, the systems object: ANCE mines globally from an approximate-nearest-neighbor index that goes stale as the encoder drifts, trading a refresh interval against staleness against cost.

temperature τ = 0.20

hard gradient share Σ pᵢ

0.501

hard count fraction

0.143

hard-batch loss / random-batch loss

0.52 / 0.19

Each negative repels the query with a force equal to its softmax weight pᵢ = e^sᵢ/τ / Σ. The four same-sector hard negatives are only 14% of the batch, but because the weight is exponential in similarity they carry the share above — 50% of the gradient at this τ, rising toward 100% as τ → 0. And a hard-mined batch is harder to classify, so its loss (0.52) — the per-step gradient magnitude — far exceeds a random batch's (0.19). That is why we mine.

The first panel is the gradient geometry: the anchor’s mixed negative batch, each bar sized by its softmax weight, with the few same-sector hard negatives carrying a share of the gradient — recomputed live — that climbs toward one as the temperature falls. The second is the false-negative problem: the contamination rate $\tau^+$ of the mined nearest neighbors against the flat baseline of random sampling, as the mining depth $k$ changes. The third is the debiased estimator: the biased, true, and debiased estimates of the negative expectation, with a $\tau^+$ slider that drives the debiased bar onto the oracle exactly at the true prior. The fourth is ANCE staleness: the frozen index’s overlap with the fresh encoder decaying as it drifts, and the refresh-interval cost knee.

The setup and notation

Fix a query $q$ and its relevant document $d^+$ , both unit vectors on the sphere $S^{d-1}$ , and write the temperature-scaled score $s(q,d) = \langle q, d\rangle / \tau$ . From the prerequisite, the gradient weight on a candidate is its softmax share $p_i = e^{s_i}/\sum_j e^{s_j}$ . This topic adds the notation the mining story needs. A miner ranks the corpus by similarity to $q$ and returns the top $k$ ; the mining depth $k$ is the radius of the net. Because the true relevance labels are unavailable at training time, some returned candidates are unlabeled positives — false negatives — and we write $\tau^+$ for their rate (the probability that a sampled “negative” is actually positive) and $\tau^- = 1 - \tau^+$ for the true-negative rate. Robinson’s hardness knob is $\beta \ge 0$ , the exponent of the reweighting $q_\beta(d^-) \propto e^{\beta s}$ . And for ANCE we write $R$ for the refresh interval — the number of training steps between rebuilds of the index the miner reads from. The statistic the debiased estimator averages is $g(x) = e^{s(q,x)}$ , the contribution of a candidate to the contrastive denominator.

Movement 1 — why hard negatives: the gradient weights by similarity

The prerequisite’s gradient theorem is the whole reason mining is worth the trouble. The update magnitude on a negative equals its softmax weight, and that weight is exponential in similarity, so two negatives a fraction of a radian apart in cosine differ by a large multiplicative factor in how hard they push.

Proposition 1 (Hard negatives carry a disproportionate share of the gradient).

Let an anchor’s in-batch negatives have similarities $s_1, \dots, s_N$ to the query, and partition them into a hard set $H$ (here the same-sector negatives) and the rest. The fraction of the InfoNCE negative gradient that lands on $H$ is the softmax share

\text{hard share} \;=\; \sum_{i \in H} p_i \;=\; \frac{\sum_{i \in H} e^{s_i/\tau}}{\sum_{j} e^{s_j/\tau}},

which exceeds $|H|/N$ whenever the hard negatives are more similar than average, and increases monotonically as $\tau \to 0$ . A random negative, near-orthogonal to the query at high dimension, contributes a weight near $e^{0}$ and so a vanishing share; the gradient lives on the hard negatives.

This specializes the prerequisite’s proved gradient structure rather than re-deriving it: $p_i \propto e^{s_i/\tau}$ is the InfoNCE weight, and summing it over a subset is just reading the share. The force is what the share is on real geometry. On the finance cloud — sectors as von Mises–Fisher clusters, companies as tight sub-clusters — an anchor query has four same-sector hard negatives among its twenty-eight in-batch negatives: only $14.3\%$ of the batch. Yet at $\tau = 0.2$ those four carry $50.1\%$ of the gradient, and as $\tau$ falls the share climbs to $94\%$ at $\tau = 0.05$ toward $1.0$ . The first panel of the laboratory recomputes this share live: the hard bars tower over the near-orthogonal ones, and the temperature slider concentrates the gradient onto them. A near-orthogonal random negative is, by contrast, almost inert — the encoder barely moves for it.

The same gap shows in the loss itself. A hard-mined batch — the anchor’s $k$ nearest true negatives — is harder to classify than a random batch, so its InfoNCE loss, and thus the per-step gradient magnitude, is larger: $0.52$ against $0.19$ for a random batch of the same size on the worked anchor. Hard mining buys a larger, more useful gradient per step. That is the case for mining. Movement 2 is the case against doing it naively.

Movement 2 — the false-negative problem

The recipe Movement 1 motivates — sample the negatives nearest the query — has a defect that is not a tuning issue but structural. The nearest neighbors of a query are, by construction, the documents most similar to it, and the documents most similar to it include its own unlabeled positives. A miner that does not know the labels cannot tell a hard negative from an accidental positive; it surfaces both.

Proposition 2 (Mining hardness and false-negative rate rise together).

Let a query’s positives and hard negatives both cluster near it, and let the miner return the $k$ nearest non-anchor items. The false-negative rate among the mined set — the fraction that are actually positive — is highest at the smallest $k$ and falls toward the global class prior as $k$ grows, while uniform random sampling returns false negatives at exactly that class prior for every $k$ . Tightening the mining radius therefore raises hardness and contamination together; they are not separable.

Proof (Proof).

Order the non-anchor corpus by similarity to $q$ . The positives, clustering nearest $q$ , occupy the top of that order, so the top- $k$ prefix is enriched in positives relative to the corpus as a whole — the smaller the $k$ , the greater the enrichment, with the very nearest item the most likely to be a positive. As $k$ grows the prefix dilutes toward the full corpus, whose positive fraction is the class prior $\tau^+_0$ . Uniform random sampling draws from the full corpus at every $k$ , so its expected positive fraction is $\tau^+_0$ independent of $k$ . Hence mined contamination is a decreasing function of $k$ bounded below by $\tau^+_0$ , and random contamination is the constant $\tau^+_0$ . $\blacksquare$

∎

The finance pool makes this concrete because it carries the labels: four queries per company, so same-company duplicates genuinely exist, and a mined “negative” that shares the anchor’s company is an accidental positive. At $k = 1$ the nearest neighbor is the anchor’s own company with probability $1.0$ — every mined top-1 negative is a false negative — falling to $0.19$ at $k = 16$ , while random sampling hits accidental positives at the class prior $\tau^+_0 = 0.097$ throughout. The second panel draws the gap as a shaded contamination band between the two curves.

Remark (The trap both prerequisites flagged but neither corrected).

This is the false-negative trap the InfoNCE topic named when it noted that retrieval’s sampled negatives “include false negatives,” and the one the dual-encoder topic meant by its warning that some in-batch negatives are accidentally relevant. Neither corrected it; both deferred it here. The damage is precise: the contrastive loss treats every mined negative as something to push away from the query, so a false negative is a true positive the encoder is trained to repel — exactly backwards. Movement 3 corrects it without ever seeing the labels.

The substrate is load-bearing, and worth stating because it is a build-and-run trap the companion notebook had to navigate. A corpus with one document per company has $\tau^+ \equiv 0$ — there are no same-company duplicates to mine accidentally — and the whole movement is vacuous. The phenomenon is measurable only because the pool carries several queries per company; the notebook asserts $\tau^+ > 0$ before claiming any contamination at all.

Movement 3 — the debiased contrastive estimator

Here is the topic’s one theorem. We cannot remove the false negatives — we do not know which mined candidates they are — but we can correct the expectation they bias. The key is that the contaminated sampling distribution decomposes, and the decomposition can be solved for the quantity we actually want.

Theorem 1 (The debiased contrastive estimator (Chuang et al.)).

Write the unlabeled sampling law as the mixture $p = \tau^+ p^+ + \tau^- p^-$ , where $p^+$ is the (unobserved) positive distribution, $p^-$ the true-negative distribution, and $\tau^+ = 1 - \tau^-$ the class prior. Then the true-negative expectation of the contrastive statistic $g(x) = e^{s(q,x)}$ is recoverable from the unlabeled and positive distributions alone:

\mathbb{E}_{p^-}[g] \;=\; \frac{\mathbb{E}_{p}[g] \;-\; \tau^+\, \mathbb{E}_{p^+}[g]}{\tau^-}.

The plug-in estimator — averaging $g$ over an unlabeled sample for $\mathbb{E}_p[g]$ and over positive examples for $\mathbb{E}_{p^+}[g]$ — is asymptotically unbiased for $\mathbb{E}_{p^-}[g]$ , and is taken as $\max\!\big(\cdot,\, e^{-1/\tau}\big)$ to keep the corrected denominator positive in finite samples.

Proof (Proof).

Take the expectation of $g$ under the mixture: $\mathbb{E}_p[g] = \tau^+ \mathbb{E}_{p^+}[g] + \tau^- \mathbb{E}_{p^-}[g]$ , by linearity of expectation over $p = \tau^+ p^+ + \tau^- p^-$ . Solve the linear equation for the one unknown term, $\mathbb{E}_{p^-}[g] = (\mathbb{E}_p[g] - \tau^+ \mathbb{E}_{p^+}[g])/\tau^-$ , which requires only $\tau^- = 1 - \tau^+ > 0$ . Replacing the two right-hand expectations by sample means gives an estimator whose bias vanishes as the unlabeled and positive sample sizes grow, since each sample mean is consistent for its expectation. The clamp $\max(\cdot, e^{-1/\tau})$ is a finite-sample floor: the smallest value $g = e^{s}$ can take is $e^{-1/\tau}$ (at cosine $-1$ , where the scaled score is $s = -1/\tau$ ), so the true-negative expectation cannot fall below it, and clamping prevents a noisy correction from producing a negative denominator. $\blacksquare$

∎

The decomposition is exact, and on the full pool with the empirical prior it holds to floating point: the companion notebook asserts the debiased estimate equals the true-negative oracle to better than $10^{-9}$ for every anchor. The interest is what the correction buys under sampling. On the finance pool the three expectations separate sharply — the positive mean $\mathbb{E}_{p^+}[g] = 102.8$ towers over the true-negative mean $\mathbb{E}_{p^-}[g] = 4.4$ , and the contaminated mixture mean sits at $\mathbb{E}_p[g] = 14.0$ , dragged up by the few accidental positives. The biased in-batch estimator’s error against the oracle therefore plateaus at the contamination bias no matter how many samples we draw — about $9.4$ at every sample size — while the debiased estimator’s error converges toward zero, from $9.3$ at $N = 4$ down to $1.2$ at $N = 512$ . The third panel draws both curves; the bias does not wash out with scale, only the debiasing removes it. The $\tau^+$ slider drives the debiased bar across the plane: at $\tau^+ = 0$ it sits on the biased mean (no assumed contamination, no correction), and at the true class prior $\tau^+ = 0.097$ it lands on the oracle.

The hardness knob composes on top, and it closes the loop back to Movement 1.

Corollary 1 (β-reweighting toward harder negatives (Robinson et al.)).

Replacing the uniform average over negatives by the hardness-tilted distribution $q_\beta(d^-) \propto e^{\beta s(q, d^-)}\, p^-(d^-)$ concentrates the estimator on the harder negatives, where the informative gradient lives. The knob $\beta = 0$ recovers the uniform (Chuang) average; and at $\beta = 1/\tau$ the reweighting is exactly the InfoNCE softmax weighting of Movement 1 — the hardness knob and the temperature are one dial. The companion notebook verifies this identity to $10^{-12}$ .

Remark (β is empirical, and it can re-import what debiasing removed).

The reweighting has no theorem to set $\beta$ . Push it too high and the tilt concentrates the estimator on the very nearest neighbors — which, by Movement 2, are exactly the candidates most likely to be false negatives. So $\beta$ trades the informative gradient of hard negatives against the contamination of accidental positives, and the right setting is found by validation, not derived. Debiasing and hard-reweighting pull in tension; the production answer is to do both and tune the balance.

Movement 4 — ANCE: the asynchronous index and staleness

Everything so far mined in-batch: the negatives for a query were the other documents in the same training batch, a few hundred at most. The hardest negatives in a corpus of millions are almost never in the batch. ANCE mines them globally — from an approximate-nearest-neighbor index over the whole corpus — and in doing so creates a systems-math object the in-batch story never had.

Algorithm 1 (ANCE asynchronous hard-negative training).

Maintain an ANN index over the corpus, encoded by a checkpoint of the model. To train: for each query, retrieve its top hard negatives from the index, form the InfoNCE loss against them, and take a gradient step. In parallel, an asynchronous inferencer periodically re-encodes the corpus with the latest checkpoint and rebuilds the index, swapping it in every $R$ training steps. The encoder thus always mines against an index that is at most $R$ steps out of date.

The defect is built into the asynchrony. The index is encoded by an old checkpoint; the model that mines against it has moved on. We model the encoder’s drift deterministically — a non-isometric interpolation of the embedding space toward a fixed seeded target, a reproducible stand-in for the SGD trajectory — freeze the index at the last refresh, and measure staleness as the top- $k$ overlap between the frozen index’s mined set and what the current encoder would mine from a fresh index.

Remark (Staleness decays, costs recall, and has no convergence bound).

As the steps since the last refresh grow, the frozen index’s mined set overlaps the fresh encoder’s less and less — on the finance corpus the overlap falls from $1.0$ at refresh to $0.15$ after $64$ steps — and its gold recall@1 collapses from $1.0$ to $0$ while the fresh index holds recall@1 at $1.0$ throughout. A stale index surfaces stale negatives and drops the now-relevant document. The refresh interval $R$ trades this staleness against the re-encode cost: rebuilding every step ( $R = 1$ ) is perfectly fresh and maximally expensive, while a long interval amortizes the cost as $1/R$ at the price of average staleness. The cost-minimizing $R$ depends on how one weights staleness against compute, and the laboratory’s fourth panel recomputes the knee live as that weight slides. There is no convergence bound here: that the decay is monotone, that overlap is the right staleness functional, and that training converges under stale negatives are empirical observations on this drift model, not theorems.

The drift must be the right kind, and the reason is a clean anti-trap. A refreshed index that happens to be an orthogonal re-encoding of the old one — an isometry — changes no rankings at all: inner products are preserved, so the mined set is identical and the staleness is zero. Staleness exists only because the frozen index lags a genuinely non-isometric encoder. The companion notebook asserts both directions: an isometric refreshed index has overlap $1.0$ , and the lagging non-isometric index decays. The systems lesson is that the index must keep up with the encoder, and how closely is the refresh-interval knob.

Proposition 3 (What the laboratory measures).

Every number in the four panels is owned by the tested notebook and asserted by the harness: the same-sector gradient share rising as $\tau$ falls (and exceeding the count fraction); the mined false-negative rate above the random rate, which itself equals the class prior; the debiased estimator equal to the true-negative oracle at the full pool to $10^{-9}$ and closer than the biased mean at every sample size; the $\beta = 1/\tau$ reweighting equal to the InfoNCE weighting to $10^{-12}$ ; and the staleness overlap decaying monotonically while the fresh index holds recall, the isometric refreshed index staying at overlap $1.0$ , and the refresh tradeoff trading staleness against cost $1/R$ monotonically. The laboratory recomputes only closed forms in the browser: the softmax gradient weights and hard share, the debiased estimate $(\mathbb{E}_p - \tau^+ \mathbb{E}_{p^+})/(1 - \tau^+)$ , and the refresh total-cost knee.

§ Training the encoder that reads the filings text pdf news

A production retrieval system over financial filings, earnings calls, and analyst notes is only as good as the negatives it was trained against. Train the dual encoder on random in-batch negatives and it learns the easy distinctions — a refiner’s 10-K from a biotech’s — but never the hard ones the desk actually confuses: two regional banks, two payment networks, two refiners whose filings share boilerplate and sit a fraction of a radian apart. Those same-sector hard negatives are where the gradient signal lives, so we mine them — and immediately hit the false-negative trap, because two filings from the same issuer are the nearest neighbors of all, and treating one as a negative trains the encoder to push apart documents that should be together. The debiased estimator is the correction: with $\tau^+$ read off the desk’s own de-duplication and similarity-threshold survival rate, the contrastive loss recovers the true-negative signal without ever mislabeling a same-issuer filing. And because the hardest negatives live in the full corpus, not the training batch, the miner reads from an ANN index over every filing — which must be rebuilt as the encoder learns, on a refresh interval set so the index never drifts faster than a trading day’s re-index budget. The cross-encoder reranker of the previous topic resolves these same-sector confusions at inference; this topic trains the first stage to make fewer of them in the first place.

Honest accounting

⚠ Rigor flag

One result here is rigorous and three are honest empiricism. The debiased contrastive estimator is exact: the mixture decomposition $p = \tau^+ p^+ + \tau^- p^-$ is solved by linearity for the true-negative expectation, the plug-in is asymptotically unbiased, and at the full pool with the empirical prior it is an identity the notebook pins to $10^{-9}$ — that is Chuang et al.’s theorem, and the laboratory’s debiased curve meeting the oracle is its visible consequence. Three seams are softer. First, the estimator needs the class prior $\tau^+$ , the false-negative rate among mined negatives, and $\tau^+$ is unknown in retrieval — we read it off the toy’s labels, where in practice it is estimated from de-duplication or assumed, and the $\max(\cdot, e^{-1/\tau})$ floor is a finite-sample safeguard outside the asymptotic identity. Second, Robinson et al.’s $\beta$ -reweighting sharpens the estimator onto the informative negatives, but $\beta$ is an empirical hyperparameter with no theorem to pick it, and pushed too far it amplifies exactly the false negatives debiasing removes. Third, and sharpest, ANCE’s staleness has no convergence bound: the encoder drift is a seeded interpolation surrogate for SGD, not trained dynamics; the staleness decay is measured by re-mining against a drifted checkpoint, the optimal refresh interval minimizes a cost the laboratory recomputes but does not bound, and convergence under stale negatives is an empirical observation. The ANN index is an exact cosine-argsort stand-in with no quantization or graph error, and the whole laboratory is the deterministic synthetic von Mises–Fisher finance cloud reused from the InfoNCE and DPR topics — a sector a vMF cluster, a company a tight sub-cluster — not a trained dual encoder.

Where this sits

Hard-negative mining is where the contrastive training story becomes operational: the gradient theorem says hard negatives carry the signal, the false-negative problem says mining them naively poisons it, the debiased estimator fixes the poison, and ANCE supplies the negatives from the whole corpus rather than the batch. The cost it opens is the lever the next topic pulls. Knowledge distillation for retrieval turns the expensive cross-encoder of the previous topic into a teacher: its margins on exactly these mined hard negatives supervise a cheap student dual encoder, so the reranker’s judgments are compressed back into a precomputable first stage — the MarginMSE recipe, the practical answer to “the cross-encoder is too slow to run everywhere, so train the retriever to imitate it.” And cross-modal contrastive alignment carries the same mining and debiasing into the multimodal setting, where the negatives span text, tables, and charts and the hardest are the cross-modal near-duplicates. Each is named here and developed in its own topic; the mined, debiased hard negative is the training signal they both take as given.