Variance-Aware Selection of Synthetic Triplets for Composed Image Retrieval

Composed image retrieval means searching with an image plus a text edit, such as "this dress, but sleeveless." Training these systems needs triplets: a reference image, an edit sentence, and a target image. Human-labelled triplets are scarce, so recent work manufactures them. A captioning model describes many images, similar image pairs are matched, and a template turns the two captions into an edit sentence. The best-documented recipe found that this only works when the paired images have "moderate similarity": not near-duplicates, which yield empty edits, and not unrelated, which yield incoherent ones. That rule is a single global threshold on embedding similarity. It ignores how noisy the evidence is for each pair. A pair with a clear, consistent difference and a pair whose apparent difference flips when you re-caption or crop the image can have the same mean similarity.

We propose to treat each candidate pair as a small statistical test. For every pair we draw several stochastic "views": different captions sampled from the captioning model, and different image crops. We measure how consistently the text difference agrees with the image difference across views. A pair is accepted only if its edit signal clears a threshold set by its own variance. That threshold is taken from moderate deviation theory, the regime between "fixed gap, error vanishes exponentially" and "gap of order $1/\sqrt{n}$, error stays constant." The theory says how the threshold can shrink toward zero, so that finer edits are admitted as more views are drawn, while the chance of admitting a false triplet still goes to zero. It also makes a concrete prediction: the number of views needed per pair grows with the logarithm of the size of the candidate pool. This turns an empirical sweet spot into a selection rule that adapts to each pair, and the prediction can be checked directly.

Core Claim

The claim has two parts, and they can be falsified separately. The first is that the per-pair variance of the edit signal, not only its mean, predicts whether a synthetic triplet is valid, and that filtering on it improves zero-shot composed retrieval at a fixed training-set size. The second, which is more specific and riskier, is that a moderate-deviation threshold schedule keeps the false-triplet rate under control as the candidate pool grows. A fixed-confidence threshold of the usual central-limit kind would let that rate drift upward as the pool grows. If the second part fails but the first holds, the contribution narrows to "dispersion matters for synthetic triplets." That result is still useful, and we will report it as such.

Relation to Prior Work

The motivation comes from SPN4CIR, which builds triplets from captions written by a multimodal LLM using the template "{target caption} instead of {reference caption}." It reports that moderate image-pair similarity is essential and also scales negatives through a frozen target encoder. Its similarity criterion is a hand-set band on mean similarity with no notion of per-pair uncertainty. We keep its synthesis pipeline and replace only the selection step, so that any difference can be attributed to that step. Other synthesis pipelines, namely automatic high-quality triplet synthesis, MegaPairs and CoVR for video, also mine pairs at scale. Our selection rule is meant to plug into any of them.

The method comes from Optimal Learning via Moderate Deviations Theory. That work builds confidence intervals for estimated costs that both shrink to zero width and keep exponentially small miscoverage. It argues that intervals based on the central limit theorem become overly wide when high confidence is demanded, and that large-deviation intervals never shrink. It works with scalar costs and stochastic processes, not learned embeddings or data curation. We apply its interval construction to a scalar statistic computed per candidate pair. The exponent's dependence on the backoff squared over twice the variance is the shared structure across the information-theory results, from lossy source coding to compression with side information. Those results motivate the variance-scaled form of our threshold. We do not claim a coding theorem for retrieval.

Two lines of work constrain the design. QuRe samples hard negatives at "steep drops" in the corpus-wide score distribution. It shows that boundary regions matter, but it requires repeated full-corpus ranking. Our test runs per pair, offline, and needs no corpus ranking. The textual-inversion line, which maps an image to a pseudo-word inside a frozen text encoder, needs no triplets at all. It includes Pic2Word, SEARLE, iSEARLE and Context-I2W. These methods set the bar any synthetic-triplet method must clear in the zero-shot setting.

Research Program

For a candidate pair $(I_r, I_t)$ we draw $T$ views. Each view $j$ consists of a sampled caption for each image and a random crop of each image. For each view we compute $X_j$, the cosine between two difference vectors: the difference of the two caption embeddings and the difference of the two image embeddings, both taken in a frozen CLIP space. A large, stable $X_j$ means the edit sentence describes what actually changed between the images. We also compute a magnitude statistic $M_j$, the norm of the image-embedding difference, which guards against near-duplicates. With sample mean $\hat\mu$ and sample variance $\hat V$ of the $X_j$, a pair is accepted when

$$\hat\mu - \sqrt{\hat V}\,\kappa\,T^{-\alpha} > 0 \quad\text{and}\quad \hat m \in [m_{\text{lo}}, m_{\text{hi}}],$$

Here $\alpha \in (0, 1/2)$ sets the moderate-deviation rate, $\kappa$ is a constant, and $\hat m$ is the mean of $M_j$. The upper end $m_{\text{hi}}$ is a coherence bound, kept as in SPN4CIR. By the moderate deviation principle, the probability that a pair whose true mean is zero is accepted behaves like $\exp(-\kappa^2 T^{1-2\alpha}/2)$. This vanishes as $T$ grows even though the threshold itself shrinks. A union bound over a pool of $N$ pairs then requires $T^{1-2\alpha} \gtrsim (2/\kappa^2)\log N$, which yields the log-pool-size prediction.

We also build a sequential version. Each pair starts with a few views and draws more only while its interval straddles zero. This concentrates compute on ambiguous pairs. Accepted triplets train the same student retriever SPN4CIR uses, CLIP4CIR on CLIP features, with identical schedules and with SPN4CIR's negative-scaling stage left unchanged.

To measure triplet validity directly, we need ground truth. DFMM-Compose provides it, because its gallery carries structured attribute labels (Pix2Key). On pairs mined from that gallery, a synthetic edit counts as valid when the attribute difference between the two images matches the attributes named in the edit sentence. This gives a labelled audit set on which false-acceptance rates can be computed as a function of $N$, $T$ and the threshold rule. We supplement it with a small human audit of CC3M-derived pairs.

Baselines

The naive reference point is training on all mined pairs inside SPN4CIR's similarity band with no further filtering. For the strongest synthetic-triplet competitor we use SPN4CIR's own selection: its moderate-similarity band and positive scaling, re-run on our candidate pool. That paper reports an R@1 gain on CIRR of 5.9% for CLIP4CIR and 4.5% for TG-CIR. The file gives these only as gains, not absolute values, so we re-run SPN4CIR ourselves on the same captioner, pool, backbone and epoch budget. We tune its band on a held-out split with the same number of trials we give our $\kappa$ and $\alpha$.

For the triplet-free alternative we report Pic2Word, whose reported CIRR Recall@1 is 23.9% (Pic2Word). We also report SEARLE and iSEARLE on CIRCO. No absolute CIRCO number for them was found on Lacuna, so we re-run their released models.

QuRe reports a FashionIQ average Recall@10 of 52.60 (QuRe). That figure uses supervised triplets, so we treat it as a ceiling, not a competitor. We additionally test whether our filtered synthetic triplets, added to FashionIQ training, push QuRe's own recipe above that number.

The key ablations hold the number of accepted triplets fixed by matching acceptance counts. They are: a mean-only threshold, a fixed-confidence z-score threshold of the central-limit kind ($\hat\mu/\sqrt{\hat V/T} > z$ with constant $z$), the moderate-deviation schedule, and a random subset of the same size. Beating SPN4CIR means a CIRR R@1 and CIRCO mAP@5 improvement at matched training-set size and matched captioning compute that exceeds three-seed variance. Compute is counted including the extra views.

Why not just…?

Why not just tune SPN4CIR's similarity band more carefully? A mean-similarity band cannot separate a consistent edit from a noisy one with the same average. Tuning the band trades one kind of error for the other. The matched-size comparison against the tuned band on the DFMM-Compose audit set measures this directly. If the tuned band reaches the same false-acceptance rate, the variance term adds nothing and we will say so.

Why not just use a fixed z-score, which already accounts for variance? This is the real threat to the second part of the claim. At a single pool size a well-chosen $z$ may match our schedule exactly. The distinction is the scaling behaviour. With $z$ fixed and the pool growing, the expected number of false triplets grows roughly linearly in $N$. The moderate-deviation schedule ties confidence to $T$ and $\log N$. We test this by sweeping $N$ over roughly two orders of magnitude, from CC3M subsets up to CC12M-scale pools, and plotting false acceptances. If the curves coincide, we drop the moderate-deviation claim and keep the dispersion result.

Why not just ask a multimodal LLM to judge each triplet? This is plausible and may be strong. However, a single judgement has no calibrated error, and it costs at least as much as our views. We include an LLM-judge filter at matched compute. We also test whether combining it with our test, by treating repeated judge outputs as views, is better than either alone.

Why not skip triplets and use textual inversion? Inversion avoids synthesis entirely but inherits the modality gap and prompt brittleness (iSEARLE). Its gains over prior methods are around one to a few points (SEARLE, Context-I2W). Our comparison on CIRR, FashionIQ and CIRCO answers whether filtered synthetic triplets beat it.

Decisive Checks

Three results settle the proposal. The first is whether $\hat V$ predicts triplet invalidity on the DFMM-Compose audit after controlling for $\hat\mu$, measured as AUROC with and without the variance feature. The second is whether the false-acceptance rate under the moderate-deviation schedule stays flat as $N$ grows while the fixed-z rate rises, and whether the views needed track $\log N$. The third is whether, at matched set size and compute, the filtered triplets improve CIRR R@1, FashionIQ average R@10 and CIRCO mAP@5 over re-run SPN4CIR across three seeds. CIRCO matters especially here because its multiple ground truths reduce the false-negative noise that could otherwise mask selection effects. A positive first check with negative second and third checks would still be informative: it would mean variance identifies bad pairs, but current retrievers are robust enough to the remainder that filtering does not pay.