Image-text search engines usually run in two stages. A fast "dual encoder" such as CLIP embeds images and captions separately and returns a shortlist of candidates. A slower "joint encoder" then reads the query together with each candidate and reorders the list. To keep the second stage affordable, recent systems compress each image into a small, fixed number of visual tokens before the joint encoder sees it. The fixed budget is the problem. An easy query ("a dog on a beach") needs very little visual detail. A hard one, such as a query about a small object, or a query whose shortlist is full of near-identical distractors, may fail precisely because the needed detail was discarded. Average recall hides this, because the failures are concentrated in a minority of queries. Information retrieval has long treated that minority as the thing to protect.
We propose to decide, for each query, how much visual detail the reranker receives. After first-stage retrieval, a small predictor reads cheap signals from the shortlist, such as how tightly the candidates cluster and how flat their scores are. It then picks one of several nested token budgets produced by a single projection module, with coarse budgets for easy queries and high-fidelity budgets for hard ones. The claim is that this per-query selection raises worst-case retrieval quality at the same average compute as a fixed budget. It also closes most of the gap to always using full detail. It does this without the batch-level gradient updates that current robustness methods for cross-modal retrieval require.
Core Claim
The accuracy lost to visual token compression in cross-modal reranking is not spread evenly across queries. It concentrates in queries whose shortlists are semantically dense, whose targets involve small objects, or whose inputs are corrupted, and these queries can be identified before reranking from first-stage signals. If that holds, a router over nested token budgets recovers most of the full-fidelity worst-case recall at a fraction of its cost, and clearly beats any fixed budget with the same average cost. The proposal is falsified if an oracle that picks the best budget per query gains little over the best fixed budget at equal cost, or if a plain threshold on one shortlist statistic does as well as the learned router.
What Prior Work Does and Leaves Open
The reranking architecture comes from Efficient Discriminative Joint Encoders for Large Scale Vision-Language Reranking (EDJE). EDJE compresses 576 ViT tokens to 64 or 128 tokens with an attention adapter built on learnable query tokens, stores 49–98kB per image, and reranks with a 22M-parameter MiniLM at 50,000 pairs per second. We reuse this design as the method. Our change is to make the budget per-query instead of fixed.
The motivation for doing so comes from two papers that show where fixed compression should hurt. Rethinking Benchmarks for Cross-modal Image-text Retrieval builds MSCOCO-FG and Flickr30K-FG by filling candidate pools with CLIP nearest neighbours, and reports that X-VLM's text-to-image R@1 falls to 44.5% under those dense pools. Object-Aware Query Perturbation for Cross-Modal Image-Text Retrieval shows that BLIP2, CoCa and InternVL all fail on small-object targets. Its fix is a fixed, detector-driven amplification of the text query applied to every input. We instead act on the visual side, and only when the query appears to need it.
The routing idea comes from classical text retrieval. University of Glasgow at the Robust Track clusters queries by pre-retrieval statistics to choose a term-weighting model per query, protecting poorly performing topics. Investigating Retrieval Method Selection with Axiomatic Features shows that the right balance between lexical and neural rankers varies by query, so that static weighting dilutes both. Learning to select rankers finds that per-query selection beats static rank fusion. All three work on text-only rankers and choose between different scoring functions. We carry the logic into cross-modal reranking and choose among resolutions of one visual representation.
Two cross-modal works are the closest competitors, and they constrain the design. Test-time Adaptation for Cross-modal Retrieval with Query Shift (TCR) diagnoses two failures under query shift: query embeddings collapse together, and the gap between image and text embeddings widens. It repairs them by updating normalization layers with gradient steps over test batches. That requires a stream of similarly shifted queries, and it cannot give an easy query and a hard query different treatment. HyperLLaVA generates projector parameters conditioned on the input with a hypernetwork, but it is evaluated only on question-answering benchmarks. Its authors also report training instability when scaling, which argues against generating continuous weights when a discrete choice may suffice. Mixture of LoRA Experts similarly reports that gating degrades as the expert pool grows and needs a balancing loss to avoid collapse. That finding motivates a deliberately small action space of three or four budgets.
Research Program
The first component is a single compression adapter that produces nested budgets. The adapter is EDJE-style, with learnable queries cross-attending over frozen ViT features. It is trained so that its first 16, 64 and 256 output tokens each work as a standalone representation for the MiniLM reranker. The training loss averages the reranking loss over the budgets, and a fourth, full path passes all 576 tokens through a linear projection. The 64-token budget is stored offline, as in EDJE. Higher budgets are computed on demand, by re-encoding only the shortlisted images of routed queries. This cost is part of the compute accounting.
The second component is the router. It reads features available after first-stage CLIP retrieval: the score gap between rank 1 and rank $k$, the entropy of the top-$k$ score distribution, the mean pairwise CLIP similarity among the top-$k$ images (the same density notion used to construct the FG benchmarks), query length, and the variance of text-embedding norms. The last feature is a cheap proxy for the embedding collapse TCR describes. On held-out training queries, the router regresses the gain in reciprocal rank that each budget $b$ provides over the 16-token budget, giving a predicted gain $\hat g(q,b)$ for query $q$. At test time it chooses
$$b^*(q) = \arg\max_b \; \hat g(q,b) - \lambda\, c(b),$$
where $c(b)$ is the measured reranking cost of budget $b$ and $\lambda$ is swept to trace a curve of accuracy against average compute. There is no test-time gradient step and no dependence on other queries in the batch.
The third component is an analysis. Before building the router, we compute the per-query oracle budget on MSCOCO-FG, Flickr30K-FG, the small-object subset, and COCO-C/Flickr-C. We then measure how much of the fixed-budget loss falls in the worst decile of queries, and how well each shortlist feature correlates with the oracle gain. This analysis decides whether the project continues.
Baselines
The naive reference point is the first-stage CLIP ranking with no reranking, together with the 64-token EDJE-style reranker applied to every query. Both run on the same backbone, the same training data (MSCOCO and Flickr30k training splits), and the same shortlist size. For EDJE recall on MSCOCO or Flickr30k, no reported result was found on Lacuna, so we reproduce it ourselves. Our fixed-budget number is anchored against EDJE's reported 50,000 pairs per second to confirm the reimplementation is faithful. The router beats this reference point if worst-decile R@1 on the FG and corruption benchmarks improves at equal or lower average cost.
The strongest fixed-compute competitor is the always-full-fidelity reranker. It is the accuracy ceiling for this architecture. The router succeeds if it recovers at least most of the full reranker's worst-decile gain at a clearly smaller fraction of its cost. Results are reported as full compute-accuracy curves, not single points.
The strongest existing robustness method is TCR. It reports that Recall@1 on COCO-C under image shift rises from 45.0% to 59.1% for a BLIP baseline (Test-time Adaptation for Cross-modal Retrieval with Query Shift). We run TCR on our reranker with its published objectives, the same test streams, and the same hyperparameter search budget as the router. We also run it with batch size one and with deliberately mixed-shift streams, the setting where we expect batch adaptation to struggle. Since the two methods are orthogonal, we also report TCR combined with routing. Beating TCR means higher worst-decile R@1 on COCO-C and Flickr-C with shuffled per-query shifts, without test-time gradients. If TCR wins on homogeneous streams, we will say so.
For the small-object regime, Query Perturbation reports that BLIP2's Recall@1 on the Flickr30K small-object subset rises from 81.33% to 84.00% (Object-Aware Query Perturbation for Cross-Modal Image-Text Retrieval). We apply it to the same backbone and report it alone and combined with routing. For dense pools, the reference is X-VLM's 44.5% text-to-image R@1 on MSCOCO-FG (Rethinking Benchmarks for Cross-modal Image-text Retrieval). That model differs from ours, so it serves only as context, and our comparisons are internal.
Three ablations isolate the key ingredient. The first replaces the learned router with a single threshold on mean shortlist density. The second replaces it with random routing at matched budget frequencies, which tests whether the router knows anything beyond spending more compute on average. The third uses only query-text features, with no shortlist statistics, which tests whether the first-stage signal matters.
Why not just…?
Why not just fuse the scores of the compressed and full rerankers? Static fusion runs both paths on every query, so it pays the full cost everywhere. Per-query selection has consistently beaten static fusion in text retrieval (Learning to select rankers; Investigating Retrieval Method Selection with Axiomatic Features). We include linear fusion tuned on validation as a baseline. If it matches the router's worst-decile recall, the router's only advantage is compute, and the compute curves will show whether that is enough.
Why not just use TCR-style test-time adaptation? TCR is the real threat on corruption benchmarks, where whole streams share one shift. Its batch-level update assumes such coherent streams and cannot help a single dense-pool query arriving alone. TCR also reports that classification-style test-time adaptation methods degrade retrieval under severe shifts, which shows how fragile gradient-based repair can be. The batch-size-one and mixed-stream runs settle whether TCR's advantage survives heterogeneous traffic. The combined run shows whether routing adds anything on top of it.
Why not just always use full detail, or a bigger model? If full-fidelity reranking were cheap, routing would be pointless. EDJE's motivation, though, is that heavy joint encoders spend most of their time on visual feature extraction, and Object-Aware Query Perturbation shows that large models such as InternVL still miss small objects. Scale alone does not remove the blind spot. The compute-accuracy curve answers this question directly. If the full reranker's cost is within a small factor of the routed system's cost at matched worst-case recall, we would recommend the full reranker.
Why not just threshold one shortlist statistic? This is the alternative most likely to match the learned router, and we treat it as a real candidate outcome. If the density threshold matches the router, the contribution becomes the finding that shortlist density predicts where compression hurts, together with a one-line routing rule. That would still be a useful result, and a simpler one.
Decisive Checks
The first check comes before anything else is built. On MSCOCO-FG, Flickr30K-FG, the small-object subset and COCO-C/Flickr-C, we test whether the per-query oracle budget beats the best fixed budget at equal average cost by a margin larger than seed-to-seed variation in worst-decile R@1. If it does not, visual compression is not the bottleneck for hard queries and the project stops.
The second check tests whether the router's gain transfers out of domain. The router is trained only on MSCOCO and Flickr30k and evaluated, without retraining, on Fashion-Gen, CUHK-PEDES, RSICD and Nocaps from the TCR suite. For these datasets no reported result was found on Lacuna, so all numbers will be our own.
The third check measures risk. Following the risk-sensitive view of the TREC 2014 Web Track Overview, we report the fraction of queries whose target rank gets worse relative to the 64-token reranker, alongside R@1/5/10, worst-decile R@1 and per-query variance of reciprocal rank. The method succeeds only if it improves the tail without hurting more easy queries than the fixed baseline.
References
- Efficient Discriminative Joint Encoders for Large Scale Vision-Language Reranking
- Rethinking Benchmarks for Cross-modal Image-text Retrieval
- Object-Aware Query Perturbation for Cross-Modal Image-Text Retrieval
- University of Glasgow at the Robust Track- A Query-based Model Selection Approach for the Poorly-Performing Queries
- Investigating Retrieval Method Selection with Axiomatic Features
- Learning to select rankers
- Test-time Adaptation for Cross-modal Retrieval with Query Shift
- HyperLLaVA: Dynamic Visual and Language Expert Tuning for Multimodal Large Language Models
- Mixture of LoRA Experts
- TREC 2014 Web Track Overview