A vector index can average 99% recall while failing the queries that matter

Average recall is a comfortable metric because it compresses a workload into one number. It is also capable of hiding the exact failures that make a vector-powered filter, join or aggregate wrong. In a new 66-page preprint, Woong-Kee Loh and Suan Lee test that gap and propose PQR-Search, an approximate nearest-neighbor method designed around a per-query recall guarantee rather than a workload average.

The average hides a long tail

The paper first splits queries into calibration and test halves on three 1-million-vector datasets: SIFT, GIST and arXiv. IVF-Flat, HNSW32 and IVF-RaBitQ are tuned to average recall 0.99. At k=100, the test averages clear the target, but 5.0% to 19.2% of individual queries still fall below 0.99 recall. On real out-of-distribution queries from Yandex, LAION and HotpotQA, with indexes tuned from data vectors because no query log is assumed, that failure share rises to 51.4% to 99.6%.

Updates make the metric drift further. Starting from half of the Yandex data, the authors apply five rounds that each insert 10% and delete the oldest 10%, without retuning. The share of queries below 0.99 recall rises from 13.5% to 22.3% for IVF-Flat and from 7.9% to 17.5% for Quake, even though Quake directly accepts a recall target.

A stricter contract has a measurable price

PQR-Search instead promises that, for each query, the probability of recall falling below a chosen target is no greater than a chosen failure probability. Its randomness comes from a secret random orthogonal transformation inside the index; the guarantee assumes queries and updates are chosen independently of that transformation.

Across 168 static settings, the paper reports 45 failures in 4,176,000 trials. In the authors’ accounting, each configuration stayed at no more than 0.5% of its allowed failure budget. The guarantee also held through all 33 search steps of the official NeurIPS 2023 streaming runbook without retuning.

That protection is not free. Where average-tuned HNSW32 reached 0.99 average recall, PQR-Search had 2.5× its one-thread latency, while HNSW32 delivered 1.3× higher batch throughput. But HNSW32 still left 3.3% to 29.2% of test queries below 0.99 recall. Against exact FAISS CPU search, PQR-Search was faster in all 52 main settings, with geometric-mean gains of 22.9× for one-at-a-time queries and 26.4× for 1,000-query batches.

The result does not make average recall useless; it makes its scope explicit. For interchangeable retrieval results, an average can be enough. For vector operators feeding exact database logic, this paper argues that the benchmark should report the tail—and the cost of protecting it. The evidence is still author-reported in an ICDE 2027 submission, and no independent reproduction or public artifact is identified in the preprint, so the guarantee deserves verification as much as attention.