Hard Negative Mining for Retriever

Background

Training a retriever with random negatives produces a model that easily separates a doc about "machine learning" from one about "cooking" but fails between "machine learning" and "deep learning" - the queries it cares about. Hard negative mining picks negatives that the current model thinks look relevant but aren't, forcing it to learn the discriminative boundary.

Problem statement

Implement hard_negative_mining(query_emb, doc_embs, positive_idx, k=4). Score every doc by cosine similarity to the query, exclude the positive, return the top-$k$ negative indices.

Input

• query_emb - 1-D array shape $(d,)$.
• doc_embs - 2-D array shape $(N, d)$.
• positive_idx - int, the index of the true positive doc.
• k - int, number of hard negatives to return.

Output

• list[int] of length $\min(k, N - 1)$, the indices of the top-$k$ most-similar non-positive docs.

Examples

Input: 5 docs, positive=0, k=2
Output: top-2 most similar of docs 1-4

Constraints

• Excludes positive_idx from candidates.
• L2-normalise query and docs if not already (cosine, not dot).
• Tie-break by lower index.

Notes

• In-batch vs offline. In-batch negatives are cheap but weak. Offline hard-negative mining (this problem) is the next step - pre-mine for each query with the current model, retrain, repeat. Typically gives several recall@k points.