Web Scale on a Budget: Tail-Aware Retrieval Evaluation

Boaz Meivar; Shai Avidan

cs.CVOct 13, 2026

Web Scale on a Budget: Tail-Aware Retrieval Evaluation

Authors: Boaz Meivar, Shai Avidan

Organizations: Tel Aviv University

Abstract

A common practice in instance retrieval is to grow the gallery size to improve a benchmark's discrimination capability. One prominent example is ILIAS, which adds up to 100 million distractor images. The prevailing assumption is that faithful evaluation demands web scale, and that indexing all 100M images through the backbone is the unavoidable price of a comparable number. That price is steep: hundreds of GPU-hours and ~200 GB of descriptors per model, paid again for every method or ablation. We show the web-scale indexing price is largely avoidable: evaluation itself obeys a scaling law. The number of distractors that outrank a positive is Binomial in the gallery size. We define the per-query retrieval hardness, a gallery-scale agnostic quantity that yields a retrieval metric at any scale, and demonstrate it can be derived from a small random sample. The underlying sampled-rank machinery is long established in recommender-system and biometric evaluation, but to our knowledge has never been adapted to visual retrieval. We make the law per-query and estimable, and validate it at true 100M scale on ILIAS and INSTRE, and on the full 759k-distractor Google Landmarks v2 pool. Concretely, within a 5% sample (a flat 20x less indexing), every backbone's tail-aware (EVT) estimate has converged onto the large-scale mAP, to within ~0.01 (mean absolute error 0.005), across five backbones, three benchmarks, and two distractor pools (mAP@1000 at 100M on ILIAS/INSTRE; the official mAP@100 at the full 759k pool on GLDv2); the recommender-systems count baseline over-predicts everywhere (+0.037 to +0.068). This is an order of magnitude better than naively reporting the metric on the same subset (+0.08 to +0.13). We release code and the per-query hardness to facilitate faster, cheaper, and greener retrieval evaluation.

Figures & tables

Figure 1: Why web-scale evaluation is predictable—and how a small sample makes it cheap. Retrieval in embedding space for one query (

\star

); its target/answer (the

\blacklozenge

) sits at a fixed distance (dashed circle). A distractor inside the circle scores above the target and outranks it, so over

N

distractors the number beating the target is

\mathrm{Binomial}(N,x_{q})

and the target’s rank is

1+\mathrm{Binomial}(N,x_{q})

. The per-query hardness

x_{q}=\#\text{inside}/\#\text{all}

—the fraction of the distractor distribution inside the circle—is size-independent . Measuring it on the full gallery (every blue point) is the unaffordable 100M indexing; instead we draw a small random sample (green, inside and outside) and estimate

x_{q}

from the green points alone (

\hat{x}_{q}\approx x_{q}

). That one number fixes mAP at any gallery size

N

, so a

5\%

sample predicts the 100M-scale result without indexing 100M distractors. (Illustrative 2-D points; the sample is drawn larger than

5\%

for legibility.)

Figure 2: A $5\%$ sample predicts the $100$ M metric. Left: mAP@1000 against gallery size $N$ for DINOv3-L on ILIAS. Only the shaded $5\%$ is indexed ( $N\!\leq\!5$ M, solid law); past it the per-query law of Eq. ( 3 ) is pure EVT extrapolation (dashed), carrying the metric $20\times$ to the true $100$ M value ( X , $0.27$ ), which the $5\%$ estimate recovers ( $0.26$ )—while a homogeneous single- $x$ model collapses to zero. Right: the per-query hardness distribution— $55\%$ of queries stay immune (never outranked even at 100M) and the resolved rest follow an approximate power law $x^{-\alpha}$ , $\alpha{\approx}1.2$ (dashed) across ${\sim}6$ decades toward the $1/N$ floor.

		estimate from a $5\%$ ( $5$ M) sample
backbone	true mAP@100M	official 5M	naive 5M	count	EVT (ours)
		(hard-mined)	(random)
DINOv3-L	0.266	0.311	0.374	0.317	0.260
PE-core-L	0.223	0.271	0.355	0.287	0.225
SigLIP2-L	0.213	0.253	0.341	0.280	0.221
SigLIP-L	0.200	0.242	0.324	0.268	0.208

Table 1: Recovering the 100M metric from a

5\%

(

5

M) sample. For each backbone: the true mAP@1000 at 100M (our recompute, matching the official ILIAS leaderboard to

{\leq}0.001

), and four numbers obtainable at a

5

M (

20\times

smaller) budget—the leaderboard’s official hard-mined

5

M column, a naive uniform-random

5

M evaluation, the tail-blind count baseline, and our tail-aware EVT estimate. All three baselines over-predict (mean

+0.041/+0.113/+0.057

); only EVT recovers the true value (mean

|

err

|

0.005

), and it needs no reference 100M numbers—unlike a fixed

5

M-to-

100

M rescaling of the leaderboard column, which INSTRE and GLDv2 lack. All differences are statistically significant : each baseline’s

95\%

query-bootstrap interval lies above the truth (

0/5

) and every EVT interval overlaps it (

5/5

); detailed intervals in App. C (Tab. 6 ).

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

backbone	fit	$\xi{>}0$	med	med	endpt
	fail	(cap)	$\hat{\xi}$	endpt	${<}s^{\star}$
DINOv2-L	0.0%	10%	-0.14	0.77	22%
SigLIP-L	0.0%	29%	-0.06	0.86	22%
SigLIP2-L	0.0%	30%	-0.06	0.89	20%
PE-core-L	0.0%	21%	-0.09	0.84	25%
DINOv3-L	0.0%	14%	-0.11	0.75	31%

Appendix

Table 2: Per-query GPD fit diagnostics on a

5\%

sample: fraction of queries whose tail is too small to fit (fail), fraction where the unconstrained MLE wants

\xi{>}0

so the cap binds, the median fitted shape

\hat{\xi}

and upper endpoint, and the fraction whose endpoint falls below the positive’s score

s^{\star}

estimator	mAP@100 MAE
raw / evaluate-at- $S$	0.038
count (K-R)	0.038
log-linear	0.111
log-quadratic	0.095
power-law	0.117
log-uniform fit	0.075

Appendix

Table 3: Estimators vs. baselines , MAE of the official GLDv2 mAP@100 at its full

759

k landmark pool, recovered from a

5\%

sample and averaged over the 5 GLDv2 backbones. The recsys (K-R) count estimator and curve fits trail tail-aware (EVT) extrapolation.

backbone	true@100M	EVT-at- $5\%$	count-at- $5\%$
PE-core-L	0.613	0.607 ( $-0.006$ )	0.621 ( $+0.008$ )
DINOv3-L	0.547	0.540 ( $-0.007$ )	0.555 ( $+0.008$ )
SigLIP-L	0.532	0.528 ( $-0.004$ )	0.541 ( $+0.009$ )
SigLIP2-L	0.460	0.454 ( $-0.006$ )	0.469 ( $+0.009$ )
DINOv2-L	0.355	0.352 ( $-0.003$ )	0.363 ( $+0.008$ )
mean $\|$ err $\|$	—	$0.005$	$0.008$

Appendix

Table 4: INSTRE at true 100M, all 5 backbones. True mAP@1000 at the full YFCC-100M pool and its recovery from a

5\%

sample. The tail-aware (EVT) estimate is within

0.007

for every backbone (mean

|

err

|

0.005

) and preserves the full ranking, while the recommender-systems count edge over-predicts throughout (mean

+0.008

). Same frozen configuration (

T{=}4000

q{=}0.95

\xi\leq 0

) as ILIAS and GLDv2.

Figure 3: A second query set and the independence assumption. Left: mAP@1000 (vertical) vs. number of distractors $N$ (horizontal, log) for INSTRE against the ILIAS-100M pool—the law tracks the truth on a different query set. Right: sensitivity to near-duplicate clustering on ILIAS; treating each cluster of size $c$ as one effective item (top-rank survival $(1-x)^{N/c}$ ) shifts accuracy up —an illustrative case (a deduplicated gallery), not a general bound on truncated mAP under retained duplicates. The measured real-order curve sits at $c\!\approx\!1$ , so clustering is mild.

Figure 4: Recovering mAP@100M from a

5\%

sample, all five ILIAS backbones. True mAP@1000 vs. number of distractors

N

(linear axis); each solid curve grows to its true 100M value (

\circ

). Reading the metric at the

5\%

(

5

M) sample (dashed line; shaded) overstates the 100M value by

+0.08

+0.13

; the tail-aware (EVT) estimate from that same sample (

\times

) recovers each true value to within

{\sim}0.01

. Estimate markers are the

20

-draw means of Tab. 9 .

Figure 5: GLDv2. Left: mAP@100 (vertical) vs. number of index distractors $N$ (horizontal, log) for DINOv3-L—the per-query law (dashed) tracks the measured curve (MAE $0.010$ ). Right: recovery of the official mAP@100 at the full $759$ k pool from a $5\%$ sample: the count edge over-predicts (lands above the band), while the tail-aware (EVT) estimate lands on the truth (black line), inside the $\pm h$ query-bootstrap noise band (shaded).

Figure 6: Predicted mAP@100M (vertical) vs. sample size $S$ (horizontal, log scale) for DINOv3-L, with a $95\%$ query-bootstrap band; dashed line is the true 100M value.

dataset	pool	metric @full pool	EVT err
ILIAS	YFCC-100M	0.266	0.005
INSTRE	YFCC-100M	0.547	$0.005$
GLDv2	index-759k	$0.31$	$0.008$

Appendix

Table 5: Three benchmarks, two distractor pools. A small random sample recovers the large-

N

mAP within

\sim

0.01 with the tail-aware estimator; ILIAS/INSTRE are mAP@1000, GLDv2 is the official mAP@100. The metric column is DINOv3-L; error is the mean over each pool’s 5 backbones (per-backbone detail in Tab. 8 for ILIAS, Tab. 4 for INSTRE, Tab. 3 for GLDv2).

Figure 7: Estimated indexing carbon, kg CO 2 eq (vertical, log scale): indexing 100M for one backbone ( $\approx$ 89 kg), a 7-backbone sweep ( $\approx$ 622 kg), and our $5\%$ protocol ( $\approx$ 4.4 kg per backbone, $20\times$ less). Illustrative estimate under the named hardware assumptions.

backbone	true mAP@100M	count ( $5\%$ )	EVT ( $5\%$ )
DINOv2-L	0.154 [0.141,0.167]	0.191 [0.177,0.205]	0.153 [0.140,0.166]
SigLIP-L	0.200 [0.185,0.214]	0.268 [0.252,0.285]	0.208 [0.193,0.222]
SigLIP2-L	0.213 [0.199,0.228]	0.280 [0.263,0.297]	0.221 [0.207,0.236]
PE-core-L	0.223 [0.209,0.238]	0.287 [0.271,0.304]	0.225 [0.211,0.240]
DINOv3-L	0.266 [0.250,0.283]	0.317 [0.300,0.335]	0.260 [0.244,0.277]

Appendix

Table 6: Detailed

95\%

query-bootstrap intervals for Tab. 1 . The true value, the tail-blind count estimate, and our tail-aware EVT estimate, each with a

95\%

query-bootstrap interval (resampling the

1{,}232

queries). The EVT interval overlaps the true interval for every backbone (

5/5

coverage); the count interval lies entirely above the truth for every backbone (

0/5

)—its error is a systematic bias, not query-sampling noise.

backbone	true mAP@100M	query-only 95%	full 95% (q+samp+fit)	$\sigma_{\mathrm{samp+fit}}$
DINOv3-L	0.266	[0.240, 0.273]	[0.243, 0.277]	0.002
DINOv2-L	0.154	[0.140, 0.166]	[0.139, 0.167]	0.003
SigLIP-L	0.200	[0.193, 0.221]	[0.192, 0.223]	0.003
SigLIP2-L	0.213	[0.207, 0.238]	[0.203, 0.236]	0.004
PE-core-L	0.223	[0.209, 0.238]	[0.209, 0.240]	0.003

Appendix

Table 7: Full predictive interval (nested bootstrap). Folding distractor-sample and EVT-fit noise into the query-bootstrap interval (via

K{=}8

disjoint

5

M redraws with per-draw tail refits) adds only

\sigma_{\mathrm{samp+fit}}\!\approx\!0.003

std—the endpoints shift slightly rather than always widen—and still covers the true 100M mAP for every backbone (

5/5

backbone	eval-at-5M	EVT-at-5M	true@100M
DINOv2-L	0.230 ( $+0.076$ )	0.153 ( $-0.001$ )	0.154
SigLIP-L	0.324 ( $+0.124$ )	0.208 ( $+0.008$ )	0.200
SigLIP2-L	0.341 ( $+0.128$ )	0.221 ( $+0.008$ )	0.213
PE-core-L	0.355 ( $+0.131$ )	0.225 ( $+0.002$ )	0.223
DINOv3-L	0.374 ( $+0.108$ )	0.260 ( $-0.006$ )	0.266
mean $\|$ err $\|$	$0.113$	$0.005$	—

Appendix

Table 8: At equal 5M cost, predict beats evaluate. Naive mAP@1000 measured on a uniform 5M subset (evaluate-at-5M) is optimistic by

+0.08

+0.13

; the tail-aware prediction from the same 5M sample (EVT-at-5M) is within

0.005

of the true 100M value. Parentheses are signed error vs. true@100M.

backbone	true	mean pred	MAE	std	worst	cover
	mAP@100M	(5%)			$\|$ err $\|$	$\|$ err $\|{\leq}h$
DINOv2-L	0.154	0.153	0.002	0.002	0.007	20/20
SigLIP-L	0.200	0.208	0.008	0.003	0.013	20/20
SigLIP2-L	0.213	0.221	0.008	0.003	0.012	20/20
PE-core-L	0.223	0.225	0.002	0.003	0.008	20/20
DINOv3-L	0.266	0.260	0.006	0.002	0.010	20/20

Appendix

Table 9: Interval coverage over

20

disjoint

5\%

samples. Each backbone’s

99

M pool is split into

20

disjoint

5\%

blocks; mean prediction, MAE, draw-to-draw std, worst error, and the number of draws inside the reported interval (

|

err

|{\leq}h

). Coverage is

100/100

overall.

fraction	$n$	draws	mean MAE	worst	mean std
		(disjoint)	(5 bb)	$\|$ err $\|$
0.5%	0.50M	12	0.020	0.039	0.003
1.0%	0.99M	12	0.015	0.031	0.003
2.0%	1.98M	12	0.010	0.023	0.003
5.0%	4.96M	20	0.005	0.013	0.003

Appendix

Table 10: Accuracy vs. sample fraction (mean over the five backbones, disjoint draws per row, at the paper’s

T{=}4000

). Error and worst case shrink monotonically with the sample;

5\%

is the point at which every backbone is covered.

Figure 8: Per-positive hardness: estimate vs. truth. EVT estimate from a $5\%$ sample (vertical) vs. the true value at 100M (horizontal), per backbone, log–log. Blue: positives the sample resolves by counting; red: the deep tail ( $x<1/S$ , dotted line) reached only by EVT extrapolation. The tail scatters about the diagonal—noisy per positive, unbiased in the median—so the aggregated mAP is accurate.

IR Evaluation

Information Retrieval (IR) Evaluation measures how well search systems find, rank, and cover useful evidence across queries, collections, and settings.

See all 185 papers

Oct 8, 2026

Beyond Resolution: Object-to-Image Ratio Mismatch in Instance Retrieval

Visual instance retrieval often fails when the same object appears at different apparent sizes in the query and gallery. We show that the dominant cause is usually not resolution loss but object-to-image (O2I) ratio mismatch: the object occupies different fractions of the two images. On a controlled benchmark of 3,021 Objaverse objects rendered at five camera distances, more than 80% of the cross-distance degradation is attributable to O2I mismatch rather than resolution for 9 of 12 pretrained backbones; multi-scale architectures cut the resolution-only effect to single digits yet remain equally susceptible. The failure is also asymmetric: tight queries retrieve more reliably against wide gallery images than the reverse. Guided by this analysis, query-side scale augmentation and an OWLv2 crop reranker reach state of the art on ILIAS 100M (29.2 mAP@1000 before reranking, 42.0 after) without training or modifying the precomputed gallery index, and a LoRA fine-tune matches the query-side gains at a single forward pass, showing that O2I robustness is learnable.

Boaz Meivar, Ofir Kedem, Amit Edenzon +2

Tel Aviv University · Bar-Ilan University

Image Retrieval Retrieval Robustness Image Matching

Ask PDF

Apr 14, 2026

Indexing Multimodal Language Models for Large-scale Image Retrieval

Multimodal Large Language Models (MLLMs) have demonstrated strong cross-modal reasoning capabilities, yet their potential for vision-only tasks remains underexplored. We investigate MLLMs as training-free similarity estimators for instance-level image-to-image retrieval. Our approach prompts the model with paired images and converts next-token probabilities into similarity scores, enabling zero-shot re-ranking within large-scale retrieval pipelines. This design avoids specialized architectures and fine-tuning, leveraging the rich visual discrimination learned during multimodal pre-training. We address scalability by combining MLLMs with memory-efficient indexing and top-

k

candidate re-ranking. Experiments across diverse benchmarks show that MLLMs outperform task-specific re-rankers outside their native domains and exhibit superior robustness to clutter, occlusion, and small objects. Despite strong results, we identify failure modes under severe appearance changes, highlighting opportunities for future research. Our findings position MLLMs as a promising alternative for open-world large-scale image retrieval.

Bahey Tharwat, Giorgos Kordopatis-Zilos, Pavel Suma +2

Mohamed bin Zayed University of Artificial Intelligence, Abu Dhabi, UAE · VRG, FEE, Czech Technical University in Prague, Prague, Czech Republic

Image Retrieval Image Matching Multimodal Reranking Fine-Grained Image Retrieval Multimodal Large Language Models

Ask PDF

Mar 6, 2026

Visual Words Meet BM25: Sparse Auto-Encoder Visual Word Scoring for Image Retrieval

Dense image retrieval is accurate but offers limited interpretability and attribution, and it can be compute-intensive at scale. We present BM25-V, which applies Okapi BM25 scoring to sparse visual-word activations from a Sparse Auto-Encoder (SAE) on Vision Transformer patch features. Across a large gallery, visual-word document frequencies are highly imbalanced and follow a Zipfian-like distribution, making BM25's inverse document frequency (IDF) weighting well suited for suppressing ubiquitous, low-information words and emphasizing rare, discriminative ones. BM25-V retrieves high-recall candidates via sparse inverted-index operations and serves as an efficient first-stage retriever for dense reranking. Across seven benchmarks, BM25-V achieves Recall@200

\geq

0.993, enabling a two-stage pipeline that reranks only

K{=}200

candidates per query and recovers near-dense accuracy within

0.2

% on average. An SAE trained once on ImageNet-1K transfers zero-shot to seven fine-grained benchmarks without fine-tuning, and BM25-V retrieval decisions are attributable to specific visual words with quantified IDF contributions.

Donghoon Han, Eunhwan Park, Seunghyeon Seo

Moreh · Seoul National University

Learned Sparse Retrieval Fine-Grained Image Retrieval

Ask PDF

Abstract

IR Evaluation

Explore similar work

Beyond Resolution: Object-to-Image Ratio Mismatch in Instance Retrieval

Indexing Multimodal Language Models for Large-scale Image Retrieval

Visual Words Meet BM25: Sparse Auto-Encoder Visual Word Scoring for Image Retrieval