# Web Scale on a Budget: Tail-Aware Retrieval Evaluation

arXiv: https://arxiv.org/abs/2610.17986 · HTML: https://mlsanity.com/paper/2610.17986/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 13 Oct 2026.

## Builds on (most cited first, 13 of 13)

- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Quantifying the Carbon Emissions of Machine Learning](https://mlsanity.com/paper/1910.09700/) (2019)
- [tinyBenchmarks: evaluating LLMs with fewer examples](https://mlsanity.com/paper/2402.14992/) (2024)
- [Google Landmarks Dataset v2 -- A Large-Scale Benchmark for Instance-Level Recognition and Retrieval](https://mlsanity.com/paper/2004.01804/) (2020)
- [The MegaFace Benchmark: 1 Million Faces for Recognition at Scale](https://mlsanity.com/paper/1512.00596/) (2015)
- [Revisiting Oxford and Paris: Large-Scale Image Retrieval Benchmarking](https://mlsanity.com/paper/1803.11285/) (2018)
- [Anchor Points: Benchmarking Models with Much Fewer Examples](https://mlsanity.com/paper/2309.08638/) (2023)
- [ILIAS: Instance-Level Image retrieval At Scale](https://mlsanity.com/paper/2502.11748/) (2025)
- [Scaling Laws For Dense Retrieval](https://mlsanity.com/paper/2403.18684/) (2024)
- [On Estimating Recommendation Evaluation Metrics under Sampling](https://mlsanity.com/paper/2103.01474/) (2021)
- [Towards Reliable Item Sampling for Recommendation Evaluation](https://mlsanity.com/paper/2211.15743/) (2022)
- [Surprise: Result List Truncation via Extreme Value Theory](https://mlsanity.com/paper/2010.09797/) (2020)
- [Predicting Classification Accuracy When Adding New Unobserved Classes](https://mlsanity.com/paper/2010.15011/) (2020)

## Abstract (arXiv)

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.