Approximate nearest neighbor search finds the stored vectors closest to a query without scanning the whole database. Locality-sensitive hashing (LSH) does this with random hash functions that send nearby points to the same bucket. It has two main settings: how many hash functions are concatenated per table ($k$) and how many tables are built ($L$). Benchmarks summarize each method with one curve of recall against queries per second over a fixed query set. The resulting leaderboards are fragile. Fairer re-tuning has reversed them before: simple random-projection LSH beat eleven "smarter" hashing schemes once code lengths and search procedures were controlled (A Revisit of Hashing Algorithms). Hand-built hard datasets also make strong graph and tree methods collapse (PUFFINN).
This note proposes a missing control variable. Each query gets a difficulty score computed from the data alone, before any index is built, and every method is then evaluated and tuned within bands of difficulty. The score is the query's own relative contrast: its average distance to database points divided by its distance to its true nearest neighbor. The claim is that this score explains a large share of the hyperparameter sensitivity attributed to LSH variants. It should also explain some of the ranking reversals seen across hashing papers. Benchmark conclusions should therefore be reported as functions of query difficulty rather than as single averages over an arbitrary mix.
Core Claim
On the Difficulty of Nearest Neighbor Search defined relative contrast $C_r = D_{\text{mean}}/D_{\text{min}}$ as a property of a whole dataset. It proved that LSH time and space complexity are functions of $C_r$. That paper motivates this work, but it never looked at the per-query version. The per-query version is
$$C_r(q) = \frac{\mathbb{E}_{x \in X}\,\lVert q - x\rVert}{\min_{x \in X}\lVert q - x\rVert},$$
where $q$ is a query and $X$ is the database. Because public benchmarks ship exact ground-truth neighbors, $C_r(q)$ costs one sampled mean per query and needs no trained index.
The proposal makes three linked, falsifiable claims. First, $C_r(q)$ predicts which queries a fixed-$(k,L)$ index will miss or will answer slowly. Second, hard queries are largely the same across very different index families. This parallels the finding in Comparing Sample-Wise Learnability across Deep Neural Network Models that VGG-16 and ResNet-20 agree on which CIFAR-10 images are hard, with rank correlation 0.867. Third, once methods are compared within difficulty bands under equal tuning budgets, a meaningful fraction of published pairwise orderings between hashing variants change sign. Configurations tuned on validation sets dominated by easy queries also fail disproportionately on hard ones.
If the third claim fails, so that orderings are stable across bands, the proposal still returns a useful negative result: aggregate curves are adequate for this field.
Research Program
The first component is an evaluation harness modeled on the Docker-based infrastructure of the NeurIPS'21 Billion-Scale ANN Challenge. That challenge locked hardware and metrics but treated each dataset as one curve. The harness adds four things on top of that pipeline:
- per-query logging of recall and distance computations;
- a fixed definition of difficulty bands, using quantiles of $C_r(q)$ pooled across datasets;
- an explicit tuning budget, counted in configurations tried and in wall-clock time, that is identical for every method;
- a rule that tuning uses held-out validation queries and never the reported test queries.
The last rule addresses the test-set feedback exposed in Revisiting Point Cloud Shape Classification.
The second component is analysis. For fixed-parameter random-projection LSH, the study measures how well $C_r(q)$ rank-predicts per-query work, meaning the candidates verified before the true neighbor is found. It then compares the curve of work against $C_r(q)$ with the shape implied by He et al.'s dataset-level analysis. For adaptive methods such as PUFFINN, which already stops each query once its recall target is met, difficulty should show up as cost rather than as missed neighbors. The prediction is that PUFFINN's per-query work rises steeply as $C_r(q)$ approaches 1.
The third component is tuning. Each method is tuned twice under the same budget. One run uses a validation set drawn at random. The other uses a set re-weighted to match a target difficulty mix. The study measures how each configuration transfers to each band.
The fourth component is distribution shift. In the Yandex Text-to-Image dataset, text queries search a database of image vectors, and the challenge report found it the hardest task. The question is whether that degradation is "just" low contrast or something more. The test is to build an in-distribution query subset matched to the text queries' $C_r(q)$ histogram and check whether the performance gap closes. This also bears on the gap left by Automating Nearest Neighbor Search Configuration. Its analytical tuner is restricted to quantization indices and to static dataset-level statistics.
Baselines
The naive reference point is current practice. That means one aggregate recall–QPS curve per method, configurations tuned on a random validation sample, and per-method tuning effort left as reported or uncontrolled. Every stratified finding is measured against what this protocol would have concluded.
The first strong competitor is random-projection LSH with the grouped Hamming ranking search of A Revisit of Hashing Algorithms. It is the method that won once evaluation was made fair. Cai reports it ranked first of eleven hashing methods on SIFT1M and second on GIST1M. It also had the best performance above 99% recall on SIFT1M among FALCONN, FLANN, Annoy, Faiss and KGraph. Any claim that a newer method is better must survive this baseline under the same budget.
The second competitor is PUFFINN, the strongest existing answer to the "just adapt per query" objection. It removes static $(k,L)$ tuning by searching tries over hash codes and backing off from fine to coarse prefixes. Its 1-bit sketches give roughly 1.5× QPS on GloVe. Raising memory from 512MB to 4GB took it from 12 to about 300 QPS at 90% recall.
The third competitor is DB-LSH 2.0, which buckets points dynamically around each query using R*-trees. It reports roughly half the query time of competitors on SIFT100M and TinyImages80M, and 10–70% gains on Audio, Trevi and NUS.
Maximum Relative Contrast hashing from He et al. is included because it optimizes the same quantity used here, only globally. A graph index reference, KGraph as in Cai's audit, tests whether the "graphs dominate" view holds in every band.
All methods are run on the same machine and in the same container. They get the same number of configurations and wall-clock tuning time, the same validation queries, and the same test queries. A method "wins" a band only if its recall–QPS area exceeds the competitor's by more than the spread across five index-construction seeds. Locatello et al. (A Sober Look at Disentanglement) showed that seed and hyperparameter variance can exceed differences between methods.
The key ablation replaces $C_r(q)$ with random band assignment, and separately with bands defined by one method's own observed recall. This isolates whether a data-only score adds anything. No reported result was found on Lacuna for any per-query or difficulty-stratified LSH evaluation, so no prior stratified number exists to beat.
Why not just…?
Why not just report tail recall, such as the fifth-percentile per-query recall, instead of defining a difficulty score? This is the most serious threat. If hard queries are method-specific, tail recall is enough and $C_r(q)$ adds little. The cross-method agreement experiment settles it. If agreement on which queries fail is high and $C_r(q)$ predicts it, then a score known before indexing offers what tail recall cannot. It lets benchmarks be re-weighted to a deployment's difficulty mix, and it lets tuning sets be matched to that mix. If agreement is low, the proposal reduces to "report tails," and the note will say so.
Why not just use PUFFINN, which already guarantees per-query recall? PUFFINN guarantees recall, but it does not guarantee cost, and its own evaluation probed difficulty with only one synthetic dataset. Stratified cost curves are exactly what show whether its guarantee becomes near-linear work on low-contrast queries. That outcome would be consistent with the near-linear query-time lower bounds in Hardness of approximate nearest neighbor search. PUFFINN is a subject of the study, not a replacement for it.
Why not just tune harder with a black-box optimizer? Sorensen et al. show that Google Vizier, after 1,800 trials and 6 hours on DEEP1B, lost to an analytical model running in seconds. More budget is therefore not obviously the fix. The tuning-transfer experiment tests the deeper point directly. If the validation mix is skewed toward easy queries, any optimizer, black-box or analytical, faithfully fits the wrong objective. Matching difficulty should help regardless of which optimizer is used.
Proposed Experiments and Decisive Checks
The datasets are SIFT1M, GIST1M, GloVe-1.2M, GNEWS-3M, Deep1M, a 10M slice of Text-to-Image, and PUFFINN's SYNTHETIC set, all with exact ground truth. There are five decisive checks:
- Prediction. The Spearman correlation between $C_r(q)$ and per-query verified candidates under fixed-$(k,L)$ LSH. Below 0.5 on most datasets would undercut the core mechanism.
- Cross-method agreement. The rank correlation of per-query failure across the five index families, with Lee et al.'s 0.867 serving only as an informal reference from another domain.
- Ranking reversals. The fraction of method pairs whose seed-robust ordering differs between the easiest and hardest bands versus the aggregate.
- Tuning transfer. The hard-band recall at a fixed QPS for configurations tuned on random validation sets versus difficulty-matched ones.
- Shift. Whether contrast-matched in-distribution queries reproduce the Text-to-Image performance gap. If they do not, cross-modal difficulty involves more than contrast.
References
- A Revisit of Hashing Algorithms for Approximate Nearest Neighbor Search
- PUFFINN: Parameterless and Universally Fast FInding of Nearest Neighbors
- On the Difficulty of Nearest Neighbor Search
- Comparing Sample-Wise Learnability across Deep Neural Network Models
- Results of the NeurIPS'21 Challenge on Billion-Scale Approximate Nearest Neighbor Search
- Revisiting Point Cloud Shape Classification with a Simple and Effective Baseline
- Automating Nearest Neighbor Search Configuration with Constrained Optimization
- DB-LSH 2.0: Locality-Sensitive Hashing With Query-Based Dynamic Bucketing
- A Sober Look at the Unsupervised Learning of Disentangled Representations and their Evaluation
- Hardness of Approximate Nearest Neighbor Search