PaperlayerView exact revision on arXiv

Source-linked AI summary

Web Scale on a Budget: Tail-Aware Retrieval Evaluation

Boaz Meivar, Shai Avidan

arXiv:2610.17986v1cs.CVcs.IR

TL;DR

Web-scale retrieval evaluation is costly because indexing large distractor galleries must be repeated for each model or ablation. The paper models per-query hardness and estimates it from a small random sample to predict large-gallery metrics; across five backbones and three benchmarks, its tail-aware estimates recover large-scale results with mean error 0.005.

  • Problem

    Web-scale retrieval benchmarks use large distractor galleries, but indexing 100M images costs hundreds of GPU-hours and about 200 GB of descriptors per model, while small-subset metrics can be optimistic and mis-rank methods.

    Source: §1 · p. 1

  • Method

    The paper models the number of distractors outranking each positive as Binomial in gallery size, then estimates size-independent per-query hardness from a small random sample to predict metrics at other scales.

    Source: §1 · p. 2, §3 · p. 4, §4 · p. 6

  • Results

    A 5% sample yields mean error 0.005 across five backbones and three benchmarks, recovering large-scale accuracy on ILIAS, INSTRE, and GLDv2.

    Source: §5 · p. 8, §6 · p. 9

  • Takeaways & Limitations

    The results support predicting web-scale evaluation from small random distractor samples for method comparisons whose margins exceed the extrapolation error.

    Source: §6 · p. 9

    The sampling law assumes distractors are drawn uniformly at random; convenience samples can bias hardness estimates, and its exact Binomial form assumes independent draws.

    Source: §3 · p. 5, §4 · p. 6

Abstract

from arXiv · show

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.

1 INTRODUCTION

Growing distractor galleries makes retrieval benchmarks more discriminative, but indexing 100M images is costly and the expense recurs for each model or ablation. The paper derives a per-query scaling law and uses sampled hardness to predict large-gallery metrics.

1 INTRODUCTION

  • A ViT-L backbone requires about 556 GPU-hours and produces approximately 200 GB of descriptors to index 100M images for one model.That indexing cost is repeated for each method, ablation, resolution, or backbone.Source: §1 · p. 1
  • Small random subsets are optimistic and may mis-rank methods, while hand-built proxies report a different number from the web-scale benchmark.These drawbacks have led practitioners either to index the full gallery or use smaller galleries.Source: §1 · p. 1
  • For a fixed query, outranking distractors follow a Binomial law in gallery size, with per-query hardness x independent of that size.The hardness is the fraction of the distractor similarity distribution above the positive; it can be estimated from a small random sample to predict metrics at other scales.Source: §1 · p. 2, Figure 1 · p. 2
  • The contribution adapts sampled-rank machinery to visual retrieval by estimating rare exceedance probabilities per query from a small sample and validating the resulting metric at web scale.The paper describes prior uses in classical IR, recommender systems, and biometrics, but says those lacked this combination of per-query estimation and true web-scale validation.Source: §1 · p. 2
  • A 1/20 distractor subset with a tail-aware estimator predicts large-scale metrics with mean absolute error 0.005 on ILIAS and at most 0.008 on INSTRE and GLDv2.The reported validation spans five backbones and three benchmarks, including 100M distractors on ILIAS and INSTRE and the full 759k pool on GLDv2.Source: §1 · p. 3

2 RELATED WORK

Prior work addresses training-data, query-count, judgment-sampling, or gallery-size questions, but the paper distinguishes its goal as predicting retrieval metrics along the distractor axis from a small random sample. It contrasts that approach with fixed-scale benchmarks, aggregate-rank estimators, and related scaling analyses.

2 RELATED WORK

  • Existing distractor-scaling benchmarks measure accuracy at fixed gallery sizes, whereas this work estimates the metric-versus-scale curve from a uniform random sample.mini-ILIAS uses a hard-mined, non-uniform subset as a proxy rather than predicting the true 100M result.Source: §2 · p. 3
  • Classical IR modeled collection-size effects, but the cited work used a shared score distribution and lacked sample-based estimation and 100M-scale validation.Hawking & Robertson (2003) observed that mAP rankings were largely preserved between a sample and the full collection.Source: §2 · p. 3
  • Sampled-judgment IR and recommendation methods estimate metrics from incomplete judgments or aggregate rank distributions, while this paper extrapolates the unobserved per-positive hard tail.The paper identifies its count baseline as the Krichene–Rendle unbiased estimator specialized to top rank, which does not recover the large-gallery value when the tail is unseen.Source: §2 · p. 3
  • tinyBenchmarks and Anchor Points reduce the number of queries; this work instead reduces the number of distractors, an orthogonal cost axis.The paper characterizes distractor indexing as dominant at web scale.Source: §2 · p. 4
  • Biometric identification work scales gallery size and uses extreme-value tails, but the paper uses tail fitting to extrapolate instance-retrieval metrics to much larger galleries.Rocher et al. (2025) forecast closed-set identification correctness from small experiments using a different law and task.Source: §2 · p. 4
  • Training-side scaling laws predict generalization from training data or model size, while this work treats evaluation budget as a separate scaling problem.The paper also describes extrapolating classification accuracy across label sets as an analogue along another axis.Source: §2 · p. 4

3 A SCALING LAW FOR RETRIEVAL UNDER DISTRACTORS

For each query, the number of distractors outranking a positive follows a Binomial law governed by size-independent hardness. Applying the resulting hardness-to-metric map gives an exact metric for realized exceedance fractions and a predictor from population hardness, with observed near-logarithmic decay over the studied range.

3 A SCALING LAW FOR RETRIEVAL UNDER DISTRACTORS

  • The distractors outranking a query’s best positive are Binomial(N, xq), so its rank is 1 + Binomial(N, xq), where xq is the population fraction of distractor scores above that positive.This hardness depends on the model and distractor source, not the number of distractors drawn.Source: §3 · p. 4
  • The map Rk assembles per-positive hardness values into a retrieval metric at gallery size N, using expected ranks rj = j + N xq,j.With realized exceedance fractions, the map gives the fixed gallery’s mAP exactly; with population hardness, it predicts that metric.Source: §3 · p. 4
  • The sampled-rank probability model itself has prior formulations in classical IR, recommender systems, and biometrics; this work contributes its heterogeneous per-query law, estimator, and 100M validation.The paper identifies its instance-retrieval form as related to Madigan et al. (2003), Krichene & Rendle (2020), and NIST (2022).Source: §3 · p. 4
  • Gallery growth never raises mAP@k(N), and in the rare-event regime the probability a positive ranks first is approximately e^-Nxq.The Poisson approximation applies when N is large, xq is small, and Nxq = O(1).Source: §3 · p. 5
  • The map is exact for a fixed gallery when fed realized exceedance fractions, but population hardness makes it a predictor whose accuracy depends on concentration and top-k truncation.The paper distinguishes the realized deterministic ranks from the Binomial population model.Source: §3 · pp. 4–5
  • At 100M, the population-hardness prediction has empirical error at most 0.006, while the pool-resampling expected AP is approximately 0.005 above the realized value.The paper targets the realized benchmark metric rather than the expected AP over resampled pools.Source: §3 · p. 5
  • Under log-uniform hardness, mAP@k(N) decays logarithmically for 1/b ≪ N ≪ 1/a rather than plateauing over that range.The paper reports approximate power-law hardness with α ≈ 1.2 across its studied datasets; this is an empirical regularity, not a universal law.Source: §3 · p. 5
  • The observed near-logarithmic decay reflects a slow accuracy bleed per decade, as many queries remain near-immune while others lie near the detection floor x ≈ 1/N.This tail explains why a small subset has not yet revealed the full-scale accuracy decline.Source: §3 · pp. 5–6

4 FROM LAW TO PROTOCOL

A size-independent per-query hardness lets a small random distractor sample predict retrieval metrics at a chosen gallery size. The protocol estimates that hardness, modeling the unseen tail when needed, and requires an i.i.d. sample.

4 FROM LAW TO PROTOCOL

  • The protocol reports mAP@k at a target gallery size from estimated per-query hardness, rather than requiring full-scale distractor indexing.The estimate can include a count/tail diagnostic and a query-bootstrap confidence interval.Source: §4 · p. 6
  • Estimate per-query hardness from a size-S sample; use a tail-aware EVT fit for queries with no sampled distractor above the positive, whose hardness is below 1/S.The alternatives are a quantized count estimate and a fit to the measured survival curve.Source: §4 · p. 6
  • The sampling law assumes distractors are drawn uniformly at random; hash-based or shuffled sampling helps ensure the sample represents the omitted pool.Shard-to-shard accuracy checks can detect drift within the sample but do not prove representativeness.Source: §4 · p. 6
  • A 5% sample recovers DINOv3-L’s ILIAS mAP@1000 at 100M as 0.26 versus the true 0.27, while the homogeneous single-x model collapses to zero.The estimate extrapolates 20× beyond the indexed 5M images.Source: Figure 2 · p. 7
  • A random small sample recovers mAP to within ∼0.01 across the studied datasets; tail modeling matters most for hard pools with large decay.For easy pools with little decay, counting already suffices.Source: §4 · p. 7

5 EXPERIMENTS

Across three benchmarks and two distractor pools, a tail-aware estimate from a small random sample tracks large-gallery retrieval metrics. The experiments compare it with common baselines, assess the scaling law, and quantify evaluation cost.

5 EXPERIMENTS

  • The evaluation uses ILIAS and INSTRE with 100M distractors and official mAP@1000, plus GLDv2 with 759k distractors and official mAP@100.Indexing 100M images through a ViT-L costs ≈556 GPU-hours and ≈89 kg CO2eq per backbone; the 5% protocol cuts this 20×.Source: §5 · pp. 7, 9
  • DINOv3-L’s measured mAP reaches 0.266 at 100M, while hardness follows an approximate power law with α ≈1.2 across the five backbones and three benchmarks.The independent prediction’s residual is at most a few percent at 100M across all five backbones.Source: §5 · p. 8
  • Nested bootstrap adds σ ≈0.003 of distractor-sample-plus-fit noise, and all 100 predictions from 20 disjoint 5% draws fall inside the reported interval.The reported interval is a query confidence interval.Source: §5 · p. 8
  • From the same 5% sample, evaluate-at-S is optimistic by 0.08–0.13 and the count estimator over-predicts by 0.037–0.068; power-law and log-uniform curve fits also do no better.The tail-aware estimate has mean error 0.005; the bounded GPD fit recovers the tail.Source: §5 · p. 8
  • Across INSTRE and GLDv2, 5% samples recover the target metric to within ∼0.01 across the benchmarks and two pools.INSTRE mean |err| is 0.005; GLDv2 mean error is 0.008 for official mAP@100.Source: §5 · pp. 8–9
  • Mean |err| 0.005: the tail-aware EVT estimate recovers true mAP@1000 at 100M from a 5% (5M) ILIAS sample, while all three baselines over-predict.Table 1 reports the mean errors as +0.041/+0.113/+0.057 for the three baselines; EVT intervals overlap the truth for all five backbones.Source: §5 · p. 8, Table 1 · p. 9

6 DISCUSSION AND CONCLUSION

Per-query hardness is a reusable, model- and distractor-source-specific artifact for deriving metrics at different gallery sizes. The conclusion reports small-sample recovery across the tested benchmarks and bounds its use to comparisons with margins larger than the extrapolation error.

6 DISCUSSION AND CONCLUSION

  • Per-query hardness is specific to a model and distractor source, and yields that method’s metric at any gallery size in closed form.The authors release hardness values for their backbones on ILIAS.Source: §6 · p. 9
  • Across five backbones, three benchmarks, and two distractor pools, the estimator recovers 100M-scale accuracy from a small random sample with 0.005 mean error.The authors frame the result as turning web-scale evaluation from an indexing problem into a prediction problem.Source: §6 · p. 9
  • The authors scope method comparisons to cases where margins exceed the extrapolation error.Source: §6 · p. 9

USE OF LARGE LANGUAGE MODELS

The paper discloses several uses of large language models during its preparation. The authors say they reviewed the AI-assisted work and take responsibility for the final content.

USE OF LARGE LANGUAGE MODELS

A DERIVATION OF MAP UNDER DISTRACTORS

The positive ranks follow a Binomial distractor-count model, letting sampled hardness predict truncated average precision at a chosen gallery scale.

A DERIVATION OF MAP UNDER DISTRACTORS

  • For each positive, its full-gallery rank is j + Kj, where Kj is the number of distractors scoring above it and follows Binomial(N, xq,j).The per-positive hardness is xq,j = 1 − Fq(spj).Source: A DERIVATION OF MAP UNDER DISTRACTORS · p. 11
  • Average precision is truncated at k, limiting the ranks contributing to the reported metric.For each positive rank, precision responds as j/(j + N x̂q,j), damping hardness-estimation error.Source: A DERIVATION OF MAP UNDER DISTRACTORS · p. 11
  • Evaluating the metric at observed exceedance fractions Kj/N reproduces that gallery’s mAP@k exactly, while sampled hardness can predict it.The tail-aware estimate is nearly exact for mAP@1000 at 100M; the count estimate over-predicts.Source: A DERIVATION OF MAP UNDER DISTRACTORS · p. 11

B THE TAIL-AWARE (EVT) ESTIMATOR

The tail-aware estimator extrapolates per-query hardness from sampled score tails; its mAP estimates closely recover large-scale results, subject to fit and sampling boundaries.

B THE TAIL-AWARE (EVT) ESTIMATOR

  • When no sampled distractor reaches the positive’s score, empirical hardness is zero, so the unseen tail probability must be estimated.This occurs when xq is small, the regime that dominates large-N accuracy.Source: B THE TAIL-AWARE (EVT) ESTIMATOR · p. 12
  • The estimator fits a generalized Pareto distribution to per-query excesses above a high threshold and extrapolates the probability of reaching the positive’s score.It retains the top 4,000 similarities, sets the threshold at their 95th percentile, and normalizes exceedances by the full sample size; when fewer than five sampled distractors exceed s⋆, it uses the fitted tail instead of the noisy count.Source: B THE TAIL-AWARE (EVT) ESTIMATOR · p. 12
  • Constraining ξ ≤ 0 respects the bounded cosine-score support and prevents physically impossible power-law tails from inflating hardness estimates.The threshold, scale, and exceedance rate remain fitted per query.Source: B THE TAIL-AWARE (EVT) ESTIMATOR · p. 12
  • Across q values 0.90–0.99, mAP@100M mean error stays 0.006–0.009; the fixed configuration is applied unchanged across benchmarks and pools.For DINOv3/ILIAS, error is 0.005 at 50k distractors and ≤0.011 for all S ≥50k, but rises to 0.09 at 10k and 0.15 at 5k; predictions vary by only 0.004 across three disjoint 5M blocks.Source: B THE TAIL-AWARE (EVT) ESTIMATOR · pp. 12–13
  • On the full 759k GLDv2 pool, tail-aware EVT has lower MAE for official mAP@100 than the K-R count estimator and curve fits.The comparison averages over five GLDv2 backbones.Source: Table 3 · p. 13
  • About 20–30% of fits place the estimated endpoint below s⋆, treating the positive as effectively immune—a coarse approximation for marginal positives.The end-to-end 100M validation absorbs this residual concern rather than bounding it in closed form.Source: B THE TAIL-AWARE (EVT) ESTIMATOR · p. 13, Table 2 · p. 13
  • For tail-dominated scales, the tail-aware estimate alone is nearly exact for mAP@1000 at 100M, while the count edge over-predicts on shallower pools.The metric’s rational per-positive precision response damps tail-estimate overshoot, unlike top-rank survival’s exponential response.Source: B THE TAIL-AWARE (EVT) ESTIMATOR · p. 13

C ERROR ANALYSIS OF THE MAP ESTIMATOR

The analysis separates estimation of the realized benchmark metric from uncertainty due to sampling, then tests recovery against large-gallery results. At equal indexing cost, tail-aware prediction is far more accurate than evaluating the sampled gallery directly.

Cross-pool results

  • Across ILIAS and INSTRE at mAP@1000 and GLDv2 at official mAP@100, small samples recover large-N mAP within ∼0.01.Table 4 reports INSTRE recovery within 0.007 for every backbone, with mean |err| 0.005 and preserved ranking.Source: Table 5 · p. 14, Table 4 · p. 14

Realized-metric error

  • The expected-rank map matches realized mAP@100M within 0.001, while exact Binomial E[AP] sits +0.004 to +0.006 above it.The expected-rank map targets the deterministic realized gallery value rather than an average over hypothetical pool resamplings.Source: C ERROR ANALYSIS OF THE MAP ESTIMATOR · pp. 14–15

Error decomposition

  • The concentration error is negligible relative to sample estimation; end-to-end error stays ≤0.008 across all five backbones.The dominant estimation challenge is the unresolved tail, where positives with xq ≲1/S are invisible to counting.Source: C ERROR ANALYSIS OF THE MAP ESTIMATOR · p. 16

Uncertainty

Ranking preservation

  • Predicted and true backbone rankings agree across the five reported estimates, but the PE-core–SigLIP2 gap of 0.010 is not reliably resolved.The method resolves rankings down to a margin of about 0.013 mAP.Source: C ERROR ANALYSIS OF THE MAP ESTIMATOR · p. 17

Equal-cost comparison

D REPEATED-SAMPLE VALIDATION: SAMPLING DISTRIBUTION, COVERAGE,

Repeated disjoint-sample tests assess prediction variability and interval coverage, while sample-size sweeps show how quickly estimates converge. At 5% of the pool, all tested models are covered and the error is low.

Repeated-sample coverage

Sample-size convergence

Sufficient budget

  • The sufficient budget is reached within 1% of the pool when successive doubled-sample predictions differ by no more than query-sampling noise.At 5%, mean absolute error against true 100M mAP is 0.005 across the ten ILIAS and INSTRE web-scale cells.Source: D REPEATED-SAMPLE VALIDATION: SAMPLING… · p. 19

Per-positive calibration

  • Deep-tail per-positive estimates are noisy but unbiased in the median, while averaging over ∼6000 positives recovers the metric to 0.005.The tail estimates have log-correlation ≈0.4 and median estimated-to-true hardness ratios of 0.9 to 1.3 across backbones.Source: D REPEATED-SAMPLE VALIDATION: SAMPLING… · p. 19, Figure 8 · p. 19

Ranking resolution

Related papers

Loading 2610.17986v1…