Hard negative mining trains a classifier or retriever by repeatedly finding the examples it currently gets wrong, or nearly wrong, and training on those. It is the standard way to build detectors and search engines where "negative" means "everything else." Practitioners know two things about it. Mining the very hardest negatives destabilizes training, and mining easy ones teaches nothing. The working fixes are hand-tuned rules about where in the score range to mine. Learning theory has a precise account of the same idea for linear classifiers, called band localization. It says to train only on points in a thin slab around the current decision boundary. That account is clean when the boundary passes through the origin (a "homogeneous halfspace"). When the boundary has an unknown offset, the theory works only if that offset is estimated first and the slab is centered on it.
This note proposes to carry that lesson into practice. In dense retrieval, the boundary between relevant and irrelevant documents sits at a different score for every query. Existing mining rules either ignore this offset (top-k hardest), or anchor on the labeled positive's score and shift it by one global constant tuned by hand. We propose to estimate a per-query offset explicitly. Negatives are then mined from a band centered on that offset, the band shrinks over mining rounds, and inside it we use a bounded loss so that likely false negatives and pathological queries cannot dominate. The companion theory asks how much offset error band localization tolerates, and how large a finite pool must be for the band to contain enough points. The main question is empirical. If a well-tuned global shift does as well as per-query offsets, the idea is wrong, and the experiments are designed to show that cleanly.
Core Claim
Current mining heuristics behave like homogeneous-halfspace learners forced onto non-homogeneous data. They assume the useful region sits at a fixed position relative to either the top of the ranking or the positive's score. The theory of general halfspaces in Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent shows something specific. It learns $\text{sign}(w^* \cdot x + t)$ under Gaussian inputs by first estimating $t$ from the average label. It then runs gradient descent with a bounded "ramp" loss restricted to slabs around the current hypothesis. Inside those slabs, the misclassified points push the weight vector toward the truth. The same paper sidesteps the constant-feature trick: it handles the offset directly rather than absorbing it as an extra weight.
Our claim is that the retrieval analog of "estimate $t$, then localize around it" beats both fixed-rank and fixed-shift mining. It should do so on ranking quality and, more clearly, on robustness to unlabeled relevant documents and on how concentrated the loss becomes on a few queries. The mechanism matters because ranking losses cannot see the offset. Adding any per-query constant to all scores leaves the ranking unchanged, so no amount of training the scorer will learn where the boundary is. The offset only matters for choosing what to train on, and so it must be modeled separately.
Where This Sits in Prior Work
The motivation comes from three empirical findings.
Optimizing Dense Retrieval Model Training with Hard Negatives makes two points. Static negatives from BM25, a classic keyword-matching retriever, quickly become easy for the model. Dynamic negatives mined from the model's own index are unstable. In their training, about 0.2% of queries account for up to 60% of the loss. That paper also supplies our compute harness. Its ADORE method freezes document embeddings and trains only the query encoder, which makes dynamic mining cheap: 4 hours versus 645 hours for ANCE on MS MARCO.
SimANS: Simple Ambiguous Negatives Sampling for Dense Text Retrieval shows that random negatives give near-zero average gradient. The hardest negatives give high-variance gradient because many are unlabeled relevant documents, known as false negatives. SimANS therefore samples negatives with probability $\propto \exp(-a(s(q,d_i) - s(q,d^+) - b)^2)$, a bell curve around the positive's score shifted by a global constant $b$. SimANS is the closest existing method and the one we must beat. It already mines in a band, but the band is anchored on one labeled document's score plus a shift shared across all queries, and its width is fixed. We replace the anchor with an estimated per-query boundary and shrink the width over rounds.
Hard Negative Examples are Hard, but Useful and Mathematical Justification of Hard Negative Mining via Isometric Approximation Theorem constrain the design. They show, in metric learning, that the hardest negatives can collapse the embedding space. Our bounded loss inside the band is meant to prevent this. We do not claim an intercept term fixes their normalization-gradient failure; that failure concerns gradient direction on the sphere, which a scalar offset does not change.
The theory side supplies the method. Beyond the online band algorithm above, Efficient Testable Learning of Halfspaces with Adversarial Label Noise localizes softly: it rejection-samples slabs of shrinking width around a weak initial classifier, a schedule we copy. Both analyses assume Gaussian or near-Gaussian inputs and an infinite stream of fresh samples. Mining, by contrast, draws repeatedly from a fixed, skewed pool.
Active Learning of General Halfspaces: Label Queries vs Membership Queries bears on the pool issue. It proves that when the minority side of an offset halfspace has mass $p$, pool-based label querying needs $\Omega(\tilde d/(p\log m))$ queries unless the pool size $m$ is exponential. We read this carefully rather than claiming to "bypass" it. In ordinary mining the positives are already labeled, so that lower bound does not apply directly. It does apply to the false negatives: a mined high-scoring unlabeled document is effectively a query about a rare relevant item. The lower bound therefore sets a finite-pool condition our theory must respect: the band must contain enough pool points to produce useful gradients.
Research Program
The method has three parts.
The first is an offset estimator. A small head on the query embedding predicts a boundary score $\tau_q$. It is trained with a pointwise logistic loss so that labeled positives score above $\tau_q$ and random negatives score below it. This is literally a non-homogeneous halfspace in score space, and it plays the role of the label-mean threshold estimate in the online band algorithm.
The second is band mining. At mining round $r$, negatives are drawn from the current index with scores in $[\tau_q - w_r, \tau_q + \kappa w_r]$. The width $w_r$ shrinks geometrically across rounds. Documents scoring far above $\tau_q$ are excluded as probable false negatives. The asymmetry $\kappa \le 1$ controls how far above the estimated boundary we will still trust an unlabeled document to be negative.
The third is a bounded loss inside the band. We use a ramp version of the margin loss:
$$\ell(q,d) = \min\big(1, \max(0, \; 1 + (s(q,d) - s(q,d^+))/\gamma)\big),$$
where $s$ is the retriever's score, $d^+$ the labeled positive, and $\gamma$ a margin scale. Because this loss saturates at 1, no single mined document or query can contribute an unbounded amount of gradient.
On the theory side we target one lemma and one condition. The lemma extends the angle-contraction argument of the online band algorithm to a band centered at an offset estimate with error $\delta$. We aim to show that contraction survives when $\delta$ is a constant fraction of the band width, and to allow log-concave rather than Gaussian inputs with a constant-factor loss. The condition concerns a finite pool of size $m$. If the band holds probability mass $\mu_r$, the round needs roughly $m\mu_r \gtrsim d$ points for a useful gradient estimate, since the analysis needs order-$d$ independent points per update. This says when shrinking must stop, and it links the schedule to the pool-size lower bound above. We treat the theory as explanatory, not as a guarantee for deep retrievers.
Baselines
The naive reference point is in-batch random negatives with the same encoder, data and steps. It establishes how much any mining helps. The documented reason to expect it to lose is the near-zero gradient average of random negatives reported by SimANS.
The static-mining baseline is BM25 negatives combined with in-batch negatives, the STAR recipe from Optimizing Dense Retrieval Model Training with Hard Negatives. It represents the "mine once" practice.
The dynamic top-k baseline is ADORE-style training on the hardest negatives from the frozen document index. It represents greedy mining and is where we expect false-negative and heavy-tail damage.
The strongest competitor is SimANS. It already mines a score band and has the best reported numbers in the file. Within the file, SimANS combined with AR2 raises MS MARCO passage MRR@10 from 39.5 to 40.9 and Natural Questions Recall@5 from 77.9 to 78.6, reported in SimANS. Our harness is a frozen-document setup, not AR2, so those figures are a reference, not a target to compare to directly. We will reimplement SimANS inside our harness with the same encoder, index refresh schedule, step count and number of negatives per query. We give its $a$ and $b$ the same hyperparameter search budget, in trials and in GPU hours, as our $\kappa$, $\gamma$ and width schedule. Beating it means a statistically reliable gain in MRR@10 on MS MARCO dev and in Recall@5 and Recall@20 on NQ, across three seeds. It also means a clearly larger margin under the false-negative stress test described below. Matching it on clean labels but winning under stress would still count as a narrower positive result.
Three ablations isolate the key ingredient. The first keeps everything but replaces $\tau_q$ with SimANS's $s(q,d^+) + b$ and a single tuned $b$; this tests whether per-query offsets matter. The second keeps per-query offsets but fixes the band width; this tests shrinkage. The third swaps the ramp loss for the standard softmax contrastive loss; this tests boundedness.
Why not just…?
Why not just tune SimANS's global shift and width more carefully? This is the real threat. If the relevance boundary sits at a roughly constant distance from the positive's score across queries, a tuned global $b$ already captures it, and per-query estimation only adds noise. The first ablation settles this directly under equal tuning budgets. We also report the spread of learned $\tau_q - s(q,d^+)$ across queries. If that spread is small relative to the band width, we expect no gain, and we will say the idea is refuted for this benchmark.
Why not just add a learnable bias to the score, the constant-feature trick? Ranking losses are unchanged by any per-query constant, so a bias inside the scorer receives no gradient toward the boundary and does not affect ranking. The theory literature also finds that absorbing the offset as an extra constant coordinate distorts margins. Kosuke Ishibashi et al. show the extra coordinate shrinks the effective margin and slows online learning. The online band algorithm handles the offset explicitly for the same reason. The offset has to live in the mining rule, which is why we model it there.
Why not just take hardest negatives and cap the loss? A bounded loss alone may remove most of the heavy-tail and collapse problems without any band. The third ablation and a fourth variant, top-k mining with the ramp loss, test exactly this. If top-k plus ramp matches the full method, the contribution reduces to "use bounded losses," and we will report it as such.
Proposed Experiments
The first study is synthetic, where the ground truth is known. We plant a non-homogeneous halfspace under isotropic Gaussian, anisotropic Gaussian, and log-concave inputs. We use pools of fixed size $m$, a minority mass $p$ down to $10^{-3}$, and a controlled fraction of false negatives hidden among unlabeled points. We then measure the angle to $w^*$ and the offset error against the number of examples processed, for every mining rule above. This checks the offset-tolerance lemma: contraction should hold until $\delta$ exceeds a fraction of the band width. It also checks the pool condition: gains should vanish once $m\mu_r$ falls below order $d$.
The second study is MS MARCO passage retrieval, reporting MRR@10 on dev, plus NQ Recall@5 and Recall@20, all in the frozen-document harness. Two diagnostics accompany the headline metrics. One is the share of training loss carried by the top 0.2% of queries, against the 60% figure from Optimizing Dense Retrieval Model Training with Hard Negatives. The other is embedding-space spread over training, to detect collapse.
The decisive stress test is false negatives. We deliberately remove a fraction of known positives from the training labels on queries with multiple judged positives, so that some mined "negatives" are known to be relevant. We then measure how often each method mines these hidden positives and how much its dev score degrades as the removed fraction grows. Per-query offset band mining predicts fewer hidden positives mined and a flatter degradation curve than both SimANS and top-k.
The project is falsified if, under matched tuning, the fixed-shift ablation equals the full method on clean and stressed data alike. In that case, what remains is the synthetic study of offset tolerance and pool size for band localization.
References
- Learning General Halfspaces with Adversarial Label Noise via Online Gradient Descent
- Optimizing Dense Retrieval Model Training with Hard Negatives
- SimANS: Simple Ambiguous Negatives Sampling for Dense Text Retrieval
- Hard Negative Examples are Hard, but Useful
- Mathematical Justification of Hard Negative Mining via Isometric Approximation Theorem
- Efficient Testable Learning of Halfspaces with Adversarial Label Noise
- Active Learning of General Halfspaces: Label Queries vs Membership Queries
- Online Learning of Maximum p-Norm Margin Classifiers with Bias