Hard Negative Mining in a Contrastive Batch

hardPROContrastive Objectives: CLIP and SigLIPVision-Language ModelsVLM 1: Vision-Language Models

Problem Statement

Not all negatives are equal: the ones that hurt are the off-diagonal texts scoring close to or above the true match. For each image, find its hardest negative and flag the images whose hardest negative beats the positive by more than a margin — the ones the model is actively getting wrong.

Background

Given the N x N similarity matrix sim (row = image, col = text), for image i:

the positive score is sim[i][i];
the hardest negative is max_{j != i} sim[i][j], with ties broken by the smallest column index;
image i is a violation when hardest_negative - positive > margin.

Your Task

Implement:

def hard_negatives(sim, margin):

Return a dict:

"hardest_idx": list where entry i is the column index of image i's hardest negative.
"violations": sorted list of image indices that violate the margin.
"mean_gap": mean of (positive - hardest_negative) over all images, rounded to 4 decimals.

For N == 1 there are no negatives: hardest_idx = [-1], violations = [], mean_gap = 0.0.

Input Format

sim: N x N nested list.
margin (float).

Output Format

A dict with the three keys above.

Sample

print(hard_negatives([[0.9, 0.8], [0.1, 0.7]], 0.0))

Output:

{'hardest_idx': [1, 0], 'violations': [], 'mean_gap': 0.35}

Example

Input

print(hard_negatives([[0.9, 0.8], [0.1, 0.7]], 0.0))

Output

{'hardest_idx': [1, 0], 'violations': [], 'mean_gap': 0.35}

Reasoning

Image 0: pos 0.9, hardest neg 0.8 (col1), gap 0.1. Image 1: pos 0.7, hardest neg 0.1 (col0), gap 0.6. Neither violates margin 0; mean gap (0.1+0.6)/2 = 0.35.

Constraints

1 <= N <= 1000.
Hardest negative excludes the diagonal; ties go to the smallest column index.
A violation is hardest_negative - positive > margin (strict).
N == 1 is the documented special case.

Learn this in

Question Answering & Information RetrievalNLP Study Plan Contrastive Learning & CLIPVLM Study Plan Training Recipes: Pretraining, SFT & RLHFVLM Study Plan

More from VLM 1: Vision-Language Models

Visual Token Pruning by Attention Masshard CHAIR-i and CHAIR-s Hallucination Ratesmedium Merge a LoRA Update into the Base Weightmedium QLoRA Memory Footprint Estimatemedium POPE Precision, Recall, and F1medium

Concept primerPREVIEW

1. Background Knowledge

Hard Negative Mining (HNM) is a core technique in contrastive learning. In a standard InfoNCE or CLIP-style batch, the loss for image $i$ is computed against $N-1$ negatives. Most negatives are "easy" (low similarity), contributing little gradient signal. The hardest negative is the off-diagonal text $j \neq i$ with the highest similarity score $\text{sim}[i][j]$ . If this score exceeds the positive score $\text{sim}[i][i]$ , the model is actively misranking the pair, which is a critical failure mode.

The margin concept introduces a tolerance threshold. A violation occurs when $\text{hardest\_negative} - \text{positive} > \text{margin}$ . This is analogous to the hinge loss in SVMs: we only care about errors that exceed a certain boundary. In practice, HNM is used to re-weight or select samples for the next training step, focusing capacity on the most confusing examples.

Tie-breaking is a subtle but important detail. When multiple negatives share the maximum score, we select the smallest column index. This ensures deterministic behavior, which is crucial for reproducibility in training pipelines and debugging.

2. Algorithm Approach

This is a row-wise reduction problem with a specific exclusion constraint. For each row $i$ of the $N \times N$ matrix:

Exclude the diagonal: The positive pair $(i, i)$ must be ignored when searching for the hardest negative.
Find the maximum: Scan the remaining $N-1$ elements in row $i$ to find the maximum value.
Track the index: Record the column index $j$ where this maximum occurs, using the smallest index in case of ties.
Evaluate the margin: Compare the found maximum against the diagonal value $\text{sim}[i][i]$ to determine if a violation exists.
Aggregate: Collect the indices, violation flags, and compute the mean gap across all rows.

The pattern is essentially a constrained argmax per row, followed by simple arithmetic aggregation.

3. Step-by-Step Strategy

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

Editor locked

The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.

solution.py

Python 3.13

Test results