Anytime Cross-Modal Re-ranking by Layer-wise Candidate Elimination

Fast image–text search engines usually work in two steps. A cheap model scores every image against the query using precomputed vectors and keeps the top hundred or so. A slow, accurate model then reads each surviving query–image pair together, letting words attend to image regions, and re-orders them. That second model, a cross-encoder, is where the accuracy comes from and where the time goes. Today it spends the same effort on every one of the $K$ survivors, through every layer, for every query. We propose to make the re-ranker spend its effort where the ranking is still undecided. After each cross-attention layer it produces a provisional score for each candidate, drops candidates that can no longer reach the final top few, and returns the current ranking whenever a deadline arrives.

The case for this rests on two findings in the file. In dense text retrieval, most queries settle their nearest neighbours after a small fraction of the default search effort, and stopping when the result list stops changing gives 5.13x speedups on TAS-B (Early Exit Strategies for Approximate-NN Search in Dense Retrieval). Separately, removing cross-modal attention altogether costs measurable accuracy: 1.5–3.7% in Fusion or Defusion?, and far more on short, fragmented queries (Flickr30K-CFQ). Our bet is that the re-ranker's rankings also settle early for most candidates. If they do, much of the cross-encoder's accuracy can be kept at a fraction of its cost, and the system can honour a per-request latency budget without a separate model for each budget.

Core Claim

A cross-encoder re-ranker equipped with a cheap scoring head after every fusion layer, plus a calibrated rule for eliminating candidates, should trace a better recall-versus-wall-clock curve than three alternatives: every static (candidate count, depth) configuration, a distilled shallow re-ranker, and a query-level confidence cascade. It should do so while keeping deadline violations near zero.

The new ingredient is joint, per-query adaptivity over two axes, which candidates and how deep. Existing pipelines fix both. LightningDOT re-ranks a static top-100 (LightningDOT), RaSa a static top-128 (RaSa), and BLINK a fixed list (BLINK). The two closest pieces of prior work each cover only part of this. AdaLLaVA conditions a multimodal model on a latency budget and skips layers or heads (Learning to Inference Adaptively for Multimodal Large Language Models), but it does so uniformly for one input in a generative question-answering model. It never decides how to split compute across competing retrieval candidates. The patience-based early exit works in the vector index of a text-only retriever and never touches the neural re-ranker. Our method uses neither a learned scheduler nor a latency token: the budget is enforced by elimination and anytime output.

Research Program

We build on the RaSa codebase (Flame-Chasers/RaSa) and its ALBEF backbone. That backbone has a dual-encoder similarity for the first stage and a six-layer fusion encoder whose image–text matching head serves as the re-ranker, so the same model can be studied on person search and on general image–text retrieval.

First, we attach a small matching head after each fusion layer $l$. Each head is trained to reproduce the final layer's scores and its top-$K$ ordering over the candidate list. This reuses two existing techniques: distillation of intermediate states from Knowledge Distillation from Internal Representations, and top-$K$ soft targets from Ranking Distillation. The final head is unchanged, so full-depth accuracy is preserved by construction, and we will check that this holds.

Second, we add the elimination rule. Let $s_l(c)$ be candidate $c$'s score at layer $l$, and let $t_l$ be the $k$-th highest score among candidates still alive at that layer, where $k$ is the cutoff the user cares about, such as Recall@1 or Recall@5. A candidate survives to layer $l+1$ only if

$$s_l(c) + \delta_l \ge t_l,$$

where $\delta_l$ is a per-layer safety margin. We set $\delta_l$ on held-out queries as the smallest margin under which at most a fraction $\varepsilon$ of the candidates that the full model ranks in its top-$k$ would be eliminated at layer $l$. This is a plain quantile calibration. It gives an empirical bound on the false-elimination error the file flags as the main risk of early exiting, and the bound holds to the extent that test queries resemble the calibration queries.

Third, we enforce the deadline. We profile wall-clock time offline as a function of how many candidates survive at each layer. At serving time, the deadline $\tau$ selects $\varepsilon$ from a lookup table, so tighter budgets lead to more aggressive elimination. If the clock still runs out, the system returns survivors ordered by their latest score, with eliminated candidates placed below them in order of their last score.

On a GPU, shrinking the set of surviving pairs saves time only if the hardware stays busy. We will therefore measure two settings: a single query, and a serving setting where survivors from many concurrent queries are packed into shared batches at each layer.

The analysis asks three questions. Do rankings in cross-modal re-ranking actually stabilise at intermediate layers, the open question the file calls ranking saturation? Does stabilisation depend on query type, for example compact versus descriptive queries? And how much of the saving comes from dropping candidates versus stopping early in depth?

Baselines

The naive reference point is the dual-encoder alone, ALBEF's image–text contrastive similarity with no re-ranking. Next to it is the full static pipeline: dual-encoder top-128 followed by all six fusion layers, exactly RaSa's published inference. On CUHK-PEDES that pipeline reports 76.51% Rank@1 (RaSa). This is our accuracy ceiling, and we count the method a success only if it stays within 0.5 points of it at substantially lower measured latency.

The strongest competitor is the best static configuration at matched latency. We grid-search the candidate count $K$ and the fusion depth, applying the trained per-layer heads uniformly with no elimination, on validation data. For each latency level we then report the configuration with the highest recall. This baseline receives the same model, the same heads, and the same tuning data as our method. It isolates adaptivity as the only difference. Beating it means a higher Recall@1 at every matched mean and 99th-percentile latency on the test split.

A distilled small re-ranker is a second strong competitor. We distil a three-layer fusion encoder from the six-layer one, following the internal-distillation recipe of Knowledge Distillation from Internal Representations, and run it at full $K$.

A query-level cascade in the style of Intent Detection in the Age of LLMs tests a different kind of adaptivity. If the dual-encoder's margin between its top-1 and top-2 scores exceeds a threshold, it answers directly; otherwise the full re-ranker runs. We tune the threshold to the same latency levels.

We also report FOD's dual mode as a reference point for removing fusion entirely, using its published defusion tax (Fusion or Defusion?). We do not retrain FOD.

Two ablations isolate the key ingredient. The first replaces the calibrated margin with a fixed top-fraction cut, keeping the best half of candidates at each layer. The second uses our elimination rule but with uncalibrated heads that were never distilled.

Why not just…?

Why not just tune $K$ and depth per latency budget? This is the most serious threat. If rankings settle at roughly the same layer for all queries, a well-chosen static configuration captures most of the benefit, and our method would only add complexity. The matched-latency grid search above tests exactly this case. The prior evidence against it is the heavy skew in per-query difficulty found in dense retrieval (Early Exit Strategies). That evidence comes from text retrieval, so we treat it as a hypothesis for cross-modal re-ranking, not a result. If the static frontier matches ours, we will report that the gap closes and say so.

Why not just use a distilled shallow re-ranker? Distillation gives a fixed speedup, about 2x in Knowledge Distillation from Internal Representations. It still pays the same cost on easy and hard candidates and offers no deadline control. Distillation is also complementary to our method: the elimination rule can run on top of a distilled model, and we will test that combination.

Why not just route whole queries by dual-encoder confidence? A query-level cascade decides once, using the weakest model's confidence. The file notes that dual-encoder scores are poorly calibrated across query styles and confuse weak positives with true matches (RaSa, Flickr30K-CFQ). Our rule decides per candidate, using the cross-encoder's own intermediate scores. The cascade baseline, evaluated separately on compact and descriptive queries, will show whether this distinction matters.

Why not just drop cross-attention, as LightningDOT or BagFormer do? Pure dual-encoders are orders of magnitude faster: LightningDOT reports 1,927x over UNITER-base on COCO 5k (LightningDOT), and BagFormer 20.72x lower latency than ALBEF (BagFormer). They still pay the defusion tax, and they collapse on fragmented queries. Our method targets the regime where a deadline leaves room for some fusion but not all of it.

Proposed Experiments

We evaluate on four benchmarks. CUHK-PEDES, ICFG-PEDES, and RSTPReid use Rank@1, Rank@5, and mean average precision, with RaSa's top-128 protocol. COCO 5K and Flickr30K use Recall@1, @5, and @10. Flickr30K-CFQ serves as a compact-query stress test.

For each method we plot recall against measured median and 99th-percentile wall-clock latency, both per query and under batched concurrent load, and record how often the deadline is missed. The file contains no reported recall for LightningDOT, FOD, or BagFormer on COCO or Flickr30K, so we will produce every curve ourselves under one hardware setup.

The first decisive check is whether the elimination method's curve lies strictly above the best static configuration's curve on CUHK-PEDES and COCO. The second is whether the empirical false-elimination rate on test queries stays at or below the calibrated $\varepsilon$, including on Flickr30K-CFQ when $\delta_l$ was calibrated only on descriptive captions. That shift is the setting where the calibration is most likely to fail. The third is diagnostic: on Flickr30K-CFQ, the method should spend measurably more layers and keep more candidates for compact queries than for descriptive ones. If it does not, then whatever savings we see are not coming from difficulty-aware allocation, and the central claim fails even if the curves look good.