Metric learning trains a network to map images to vectors (embeddings) so that pictures of the same product, bird or car land close together and different ones land far apart. Training only makes progress on "hard negatives": examples from a different class that currently sit too close. Most pipelines find them inside the loss at every step. They compute all pairwise distances in the mini-batch, then mask, sort and index to pick the worst offenders. On modern GPUs this kind of code is slow for a reason that operation counts hide. It launches dozens of tiny kernels, and the CPU time spent dispatching them, the "framework tax", outweighs the arithmetic. We argue that on the benchmarks where mining matters most, this per-step search is also mostly wasted. The datasets have tens of thousands of classes but only a few hundred embedding dimensions. Class centers therefore cannot all sit equally far apart, and each class ends up with a small set of genuinely close neighbor classes. A random batch almost never contains those neighbors, so the elaborate in-loss search spends its overhead finding negatives that are not actually hard.
The proposal is to do the mining once, in the sampler, at the level of classes. We keep a cheap, periodically refreshed graph of which classes are near each other. We build each batch from a few such neighborhoods. We then apply a fixed-shape dense loss with no sorting or index filtering, which can be captured as a single static GPU graph. The prediction ties the three directions together. The accuracy gain from neighborhood batching should grow with how overcrowded the space is, measured by the ratio of classes $C$ to dimension $d$. It should vanish when $d \ge C-1$, where every class is equally far from every other. The speed gain should come from removing data-dependent shapes from the training step.
Core Claim
The claim has two parts, and each can fail on its own. The geometric part is about crowded spaces. When $C \gg d$, the hardness of a negative is mostly a property of its class neighborhood, not of the individual sample. Sampler-side neighborhood batching should therefore match or beat in-loss sample mining at equal step count, and the advantage should grow with $C/d$. The systems part is about how the step runs. Once hardness is supplied by batch composition, the loss can be a dense, fixed-shape log-sum-exp over the whole batch similarity matrix. Such a step is graph-capturable and fusable. It should cut per-step wall-clock time well below that of mining losses, including mining losses rewritten to be compiler-friendly.
The intuition for the first part is simple counting. Suppose a batch holds $P$ classes drawn uniformly from $C$ training classes, and each class has $k$ true near-neighbor classes. The chance that a given class sees at least one of its neighbors in the batch is
$$1-(1-k/C)^{P-1} \approx Pk/C,$$
which follows from independent draws without replacement when $P \ll C$. Take Stanford Online Products, which has about 11k training classes. With $P \approx 90$ and $k = 10$, this is under 10%. The in-loss miner sorts through the batch and finds the "hardest" negative in a pool that rarely contains a real competitor. Saturation decides whether real competitors exist at all. Under the equiangular simplex geometry that neural collapse produces when $d \ge C-1$, every class is a neighbor of every other, and batch composition cannot matter. Under the hyperspherical-uniformity geometry that Generalizing and Decoupling Neural Collapse via Hyperspherical Uniformity Gap shows features approach when $d < C-1$, the spacing between classes is uneven at a local scale.
Relation to Prior Work
Two papers motivate the geometric question by stopping right before it. Hard-Negative Sampling for Contrastive Learning: Optimal Representation Geometry and Neural- vs Dimensional-Collapse proves that hard-negative sampling steers contrastive learning toward full-rank neural collapse. Its theory assumes $d \ge C-1$ and leaves the overloaded regime open. We study that open regime empirically and make a falsifiable prediction about it. Mathematical Justification of Hard Negative Mining via Isometric Approximation Theorem shows that triplet loss with hard mining can collapse every embedding to a single point. Very hard negatives, which large batches make more likely, cause it, and larger $d$ buffers against it. This paper constrains our design. Neighborhood batches deliberately concentrate hard negatives, so they could trigger exactly this collapse. We therefore expose a hardness knob and measure embedding diameter throughout training.
Three lines of work avoid sample-pair mining by summarizing each class with a single vector. Proxy Anchor Loss for Deep Metric Learning compares batch samples against learnable class proxies at cost $O(M \cdot C)$ for batch size $M$. Mean Field Theory in Deep Metric Learning replaces pair interactions with interactions against a class "mean field". Hyperspherical Classification with Dynamic Label-to-Prototype Assignment fixes prototypes on the sphere and reassigns labels to them with an $O(C^3)$ Hungarian matching. All three throw away sample-to-sample interactions. The Mean Field authors themselves attribute their loss to ProxyAnchor on Cars-196 to this. We keep sample-to-sample interactions, as Deep Metric Learning via Lifted Structured Feature Embedding does with its dense smooth loss over all in-batch pairs. We use class-level structure only to decide which samples share a batch. We borrow the momentum-averaged class features of the dynamic-assignment work but replace its cubic matching with a top-$k$ nearest-neighbor query computed on the GPU.
The closest prior work on batch construction is Global Selection of Contrastive Batches via Optimization on Sample Permutations. It optimizes sample permutations to make batches more informative. We use a much cheaper class-neighbor graph, and we tie the expected benefit to the $C/d$ ratio. We also co-design the batch with a fixed-shape loss so that the overhead of in-loss mining disappears, rather than treating batch selection as an accuracy device alone.
The systems side rests on measurements from the overhead literature. The Framework Tax: Disparities Between Inference Efficiency in Research and Deployment shows that small decomposed kernels leave GPU compute units around 2.6% utilized in eager PyTorch at batch size 1, rising to about 59% with CUDA Graphs. Nimble: Lightweight and Parallel GPU Task Scheduling for Deep Learning finds GPUs active only about 9% of the time on fine-grained models and recovers large speedups by pre-recording kernel traces. Recording a trace in advance is impossible when shapes depend on the data. Liger-Kernel: Efficient Triton Kernels for LLM Training supplies the fused, chunked loss-kernel technique, which reports roughly 3x speed and 5x less memory for large-vocabulary cross-entropy. That work never applies the technique to pairwise metric losses, and we reuse it there.
Research Program
We will build three pieces.
The first is a neighborhood sampler. It maintains a momentum-averaged mean embedding for every training class, updated from embeddings the forward pass already produces. Every few hundred steps it refreshes a top-$k$ class-neighbor graph with a single $C \times C$ similarity product on the GPU, which is about $10^8$ entries for SOP and runs on a side stream. Each batch is assembled from $P$ classes, a fraction $\rho$ of which are drawn as neighbor clusters around seed classes while the rest are uniform. $k$ and $\rho$ together are the hardness knob used to stay clear of the collapse described in the isometric-approximation paper.
The second is a fixed-shape loss: a multi-similarity or lifted-style log-sum-exp over the full $M \times M$ cosine matrix. Positive and negative pairs are selected by multiplicative label-equality masks rather than by nonzero-indexing, top-$k$ or ragged reductions. Every tensor shape is therefore fixed in advance. The whole training step, backbone included, can then be captured with CUDA Graphs. We will also write an optional Triton kernel that computes similarities and both log-sum-exps in chunks without materializing the matrix, following the Liger approach.
The third is a measurement harness. For each step it records kernel launch count, GPU active fraction measured as in Nimble, host dispatch time, peak memory, and the share of in-batch negatives that come from a class's true top-$k$ neighbors. Collecting that last quantity directly tests whether mining effort is being spent on real competitors.
Baselines
The naive reference point is a uniform class-balanced sampler with the same fixed-shape dense loss and no mining at all. It shows how much any hardness mechanism adds. It also shows the speed ceiling, since its step cost equals that of our method minus the sampler.
The standard practice baseline is in-loss mining in eager PyTorch: batch-hard and semi-hard triplet selection, and multi-similarity mining with its usual pair filtering, all on uniformly sampled batches. This is the pipeline whose overhead Discriminative Learning of Deep Convolutional Feature Point Descriptors and Hard Negative Examples are Hard, but Useful document.
The strongest systems competitor is that same mining rewritten in fixed-shape form, with dense masks and fixed-$k$ top-$k$ instead of nonzero filtering, and compiled with torch.compile and CUDA Graphs. It isolates whether our speedup comes from moving mining into the sampler or merely from writing the mining compiler-friendly.
The strongest accuracy competitors are Proxy Anchor and MFCWMS. On SOP, Mean Field Theory in Deep Metric Learning reports MFCWMS at 52.7 MAP@R and ProxyAnchor at 51.5 MAP@R. On Cars-196 ProxyAnchor beats the mean-field losses, though no number is quoted in our material. For Proxy Anchor Recall@1 on SOP, no reported result was found on Lacuna. For older context, Deep Metric Learning via Lifted Structured Feature Embedding reports roughly 62% Recall@1 on SOP. We will rerun all baselines rather than copy numbers.
Two ablations isolate the key ingredient. One runs neighborhood batches with the eager in-loss miner on top, which tests whether in-loss mining adds anything once batches are already hard. The other runs our fixed-shape loss on uniform batches.
Every method gets the same backbone, embedding dimension, image resolution, augmentation and number of training images seen. Each also gets the same hyperparameter search of 20 trials, on held-out training classes and never the test classes. Results are reported as the mean over three seeds, using the standard MAP@R protocol. Our method beats a baseline if it matches or exceeds that baseline's MAP@R and Recall@1 within seed noise while cutting time-to-target-accuracy by at least 1.5x. On SOP, our method must also beat MFCWMS's MAP@R at equal wall-clock time.
Why not just…?
Why not just compile the existing mining loss? This is the most serious threat to the systems claim, so the fixed-shape compiled miner is a headline baseline. Nimble's trace-recording approach and CUDA Graphs both need static shapes, and the usual miners produce variable numbers of violating pairs. A careful rewrite can remove that problem. If the compiled miner matches our step time, we will report that the speed claim reduces to "write mining with fixed shapes". The geometric claim would survive, because a compiled miner on uniform batches still searches a pool that rarely contains neighbor classes. The neighbor-coverage statistic and the first ablation settle this.
Why not just use Proxy Anchor or a mean-field loss and skip pair mining entirely? These losses are fast and strong on SOP. However, they fold each class into one vector, which the Mean Field paper links to its weaker Cars-196 results. They also carry a $C \times d$ table whose logit computation hits the same memory blowup Liger-Kernel addresses. If proxies win on every dataset at equal wall-clock time, sample-level interactions are not worth keeping, and we will say so. Our expectation is that the fine-grained datasets, Cars-196 and CUB, are where sample-to-sample terms pay off.
Why not just increase the embedding dimension? The Framework Tax paper shows that extra width is often free in latency. The isometric-approximation paper shows that larger $d$ buffers against collapse. But reaching $d \ge C-1$ on SOP would mean embeddings with more than 11k dimensions, which retrieval indices cannot afford. Rather than argue, our $d$ sweep tests this directly. If the neighborhood-batching gain vanishes at moderate $d$ such as 512 or 1024, then raising $d$ is the simpler fix, and our method only helps in tight-dimension deployments. That would be a narrower but still honest result.
Proposed Experiments
The decisive geometric check is a controlled sweep over saturation. On CIFAR-100 we train supervised contrastive models with $d \in \{8, 16, 32, 64, 128\}$, which spans $C/d$ from 12.5 down to below 1 with the boundary at $d=99$. On ImageNet-1K we use $d \in \{32, 64, 128, 512\}$. On SOP, which has the largest class count, we use $d \in \{64, 128, 512\}$. For each setting we measure the accuracy gap between neighborhood batching and uniform batching under the same fixed-shape loss. The claim predicts that the gap shrinks steadily as $C/d$ falls and is near zero at $d=128$ on CIFAR-100. If the gap is flat across $d$, the benefit is not about saturation, and the core claim fails.
We also track the singular-value spectrum of the embeddings, following the rank diagnostics in the hard-negative-sampling theory paper, together with embedding diameter. These show whether concentrated neighbor negatives cause dimensional collapse or full collapse as $\rho$ rises.
The retrieval experiments use CUB-200-2011, Cars-196, SOP and In-Shop. They report Recall@1 and MAP@R against all baselines under matched budgets, plus accuracy-versus-wall-clock curves in the style of Proxy Anchor's time-to-accuracy comparison.
The systems experiments run on two GPU generations, since the Framework Tax paper finds that dispatch overhead weighs more on faster hardware. For every method they report per-step kernel launches, GPU active fraction, dispatch time and peak memory, at batch sizes from 64 to 1024.
The decisive systems check compares our step against the compiled fixed-shape miner at equal accuracy. A speedup that survives this comparison means moving mining into the sampler is what helps. A speedup that disappears means the gain came from rewriting the mining code.
References
- Generalizing and Decoupling Neural Collapse via Hyperspherical Uniformity Gap
- Hard-Negative Sampling for Contrastive Learning: Optimal Representation Geometry and Neural- vs Dimensional-Collapse
- Mathematical Justification of Hard Negative Mining via Isometric Approximation Theorem
- Proxy Anchor Loss for Deep Metric Learning
- Mean Field Theory in Deep Metric Learning
- Hyperspherical Classification with Dynamic Label-to-Prototype Assignment
- Deep Metric Learning via Lifted Structured Feature Embedding
- Global Selection of Contrastive Batches via Optimization on Sample Permutations
- The Framework Tax: Disparities Between Inference Efficiency in Research and Deployment
- Nimble: Lightweight and Parallel GPU Task Scheduling for Deep Learning
- Liger-Kernel: Efficient Triton Kernels for LLM Training
- Discriminative Learning of Deep Convolutional Feature Point Descriptors
- Hard Negative Examples are Hard, but Useful