Natural Hard-Negative Mining from Positives for Instruction-Following Retrieval

Instruction-following retrieval asks one query to rank documents differently under different instructions: once an instruction adds a requirement, the original positive should drop if it fails that requirement. Training data for this is scarce, and existing methods keep the positive fixed and have an LLM invent a negative passage that violates the instruction. This paper does the reverse. It picks an existing negative that meets some extra condition, writes a short instruction that makes it the positive, and the original positive naturally becomes the hardest negative under that instruction. InstructIR gives each query several user instructions and scores the worst top-ten nDCG among them. With only 6,716 such examples built from MS MARCO, the small Qwen3-Embedding's score rises from 49.29 to 67.06, beating Promptriever, a model more than ten times larger.

Teams that want dense retrieval to respect user conditions should read this, because it makes the data cheap: the LLM writes one sentence of instruction, not a whole passage, both positive and negative are real corpus passages, and training fits on one RTX 3090. With the same model, data size and epochs, Promptriever-style data reaches only 51.84 and InF-IR-style data falls to 31.51, so the gap comes from how the data is built. The caveats: data comes only from MS MARCO, backbones stop at 4B, and FollowIR gains are much smaller than InstructIR gains, with an average of 23.7, still 1.6 below the best commercial API.

What problem is it solving?

Ordinary dense retrieval only asks whether a query and a document look alike. If a user appends "only about construction" or "not about history", the model usually still ranks by topic, and the instruction is ignored. To teach instruction following, training data must contain contrasts where adding the instruction changes which document should rank first.

A small example (illustrative). The query is "what is a guitar"; positive A gives a definition and negative B describes its construction.

A is highly query-relevant yet fails the instruction, the hardest kind of negative, and no passage had to be generated.

Pipeline overview

The candidate pool is designed as BM25 results minus labeled positives; for this dataset the provided negatives of each MS MARCO-W tuple are used directly. Then three stages follow.

Training uses standard InfoNCE with the instruction concatenated to the query: $s_{\theta }(I,q,d)=\mathrm{sim}(f_{\theta }(I\oplus q),f_{\theta }(d))$.

Design 1: clean before deciding what can be promoted

Why it is needed: BM25 negatives are messy. Some actually answer the query and are missed positives; some are only loosely on topic and no reasonable instruction would make them better than the positive. Writing instructions for them forces the LLM to invent conditions that contradict the query.

How it works: the LLM reads the query, the positive and all negatives at once, confirms the positive, and classifies each negative. For each convertible negative it drafts an instruction that must keep the query's entity, intent and answer type, add a condition supported by that negative, and leave the positive relevant but non-compliant. Only tuples with at least one convertible negative survive.

This shows not every negative can be promoted; skipping cleaning brings false negatives and forced instructions into training, and instruction sensitivity nearly returns to baseline.

Design 2: keep the original positive as a negative

Why it is needed: the old positive is highly relevant, so topic similarity alone would rank it first; only the instruction can tell the model to push it down.

How it works: relabel the chosen convertible negative as positive, the old positive as the first negative, keep the other cleaned negatives, and remove other convertible negatives that also satisfy the new instruction so they do not become false negatives.

This shows a large share of the gain comes from this natural hard negative: removing it costs 6.66 Robustness points and more than half the FollowIR instruction response, while plain FollowIR relevance only moves from 23.7 to 22.5.

Design 3: geometry filtering with the frozen encoder

Why it is needed: an instruction the LLM finds sensible may still confuse the encoder. If the query vector moves away from the new positive once the instruction is added, the sample pulls the pre-trained space in an odd direction.

How it works: with the pre-training encoder $f_0$, compute ${\Delta }^{+}=\mathrm{sim}(f_0(I\oplus q),f_0(d^{+}))-\mathrm{sim}(f_0(q),f_0(d^{+}))$ and keep samples with ${\Delta }^{+}>0$. It only requires the right direction, not that the new positive already outranks the old one, which would discard exactly the most useful samples. Hoot says▾

Hoot saysOne sample: kept by the direction rule, wrongly dropped by a rank-reversal ruleClose ✕

The filter only asks whether the instruction moves the query closer to the new positive; the rank reversal is what training must achieve, so requiring it up front deletes the most useful samples.

Paper's rule: keep if gain > 0

no instruction → new positive

0.52

with instruction → new positive

0.58

Gain

0.58 − 0.52 = 0.06 > 0, keep

The direction is right; training then pushes it past the old positive.

Wrong rule: require it already ranks first

with instruction → new positive

0.58

with instruction → old positive (illustrative)

0.65

Gap

still 0.07 behind, drop

It deletes exactly the samples training most needs to learn to reverse.

Illustrative: new-positive similarity rises from 0.52 to 0.58; old-positive similarity set to 0.65. Source: gain formula and illustrative example in Design 3; 0.65 is an added illustrative value

This shows the signal comes mainly from the reversal itself, while filtering nearly doubles the FollowIR instruction response. The filter depends on the encoder: Qwen3-Embedding-0.6B removes 754 samples, 4B removes 815, BGE-M3 only 116.

From 36,306 MS MARCO tuples, rule cleaning, LLM verification and reversal leave 6,716, under a fifth, meaning most tuples hold no negative a reasonable instruction can promote. A manual check of 100 samples found 88 fully valid.

Main results

This shows the 0.6B bi-encoder takes the best bi-encoder Robustness@10 and the best nDCG@10 overall; BGE-M3 gains far less, so the benefit depends on the backbone's instruction understanding.

This shows plain triples and positive-centred instructions do not teach instruction following and can even disturb the pre-trained space; what matters is two real, query-relevant documents separated only by the instruction.

FollowIR rewrites instructions so some relevant documents become irrelevant; p-MRR compares their ranks before and after, from -100 to +100, with 0 meaning no change. The average is over Robust04 MAP, News21 nDCG@5 and Core17 MAP. The 0.6B model gets 23.7 and +4.1, best among finetuned retrievers, 2.8 above the next on the average; the 4B model's p-MRR rises from +3.0 to +7.2. On full MS MARCO, Dev MRR@10 rises from 18.6 to 25.2, so ordinary retrieval is not sacrificed.

Limitations

First, one data source. MS MARCO queries and passages are short; 6,716 samples being enough there says little about long documents, products or code, and backbones stop at 4B.

Second, modest FollowIR gains: 23.7 is still 1.6 below the best commercial API and 1.1 below the 7B FollowIR cross-encoder.

Third, it depends on a strong LLM for cleaning and reversal, about 64.98M tokens for the main set, with an 88% manual pass rate; quality with smaller open models is unknown.

How a search or recommendation team could try it

1. Take queries, clicked documents and unclicked documents from the same impressions in search logs as triples.
2. Have a strong LLM find unclicked documents that one added condition, such as "second-hand only" or "suitable for children", would promote, and write that condition.
3. Label the promoted document positive, the clicked one as the first negative, and remove others that also meet the condition.
4. With the current production encoder, keep only samples where similarity to the new positive rises with the condition.
5. Train a small model for one epoch on a few thousand samples and check both an ordinary retrieval set and a condition-filtered set.
6. If it holds, mix the data into regular training.

Verdict

A clever data recipe: write instructions instead of negatives, and let the old positive be the hard negative; a few thousand samples teach a small model to follow instructions.