Metraipolis › archive › dc_fb47d87f26e4
Per-Query Recall Guarantees for Approximate Nearest Neighbor Search in Dynamic Vector Databases — arXiv:2611.07579
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.07579
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-06T14:54:15.601Z
- SHA-256 of the archived text
238a7783a72461e0ad4f2e59cb25c4bac19efae76a50294d25483cddc88cb211- Stable URL of this page
https://metraipolis.com/documento/dc_fb47d87f26e4
How to cite
Per-Query Recall Guarantees for Approximate Nearest Neighbor Search in Dynamic Vector Databases — arXiv:2611.07579 — arXiv (en), https://arxiv.org/abs/2611.07579 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fb47d87f26e4 (Metraipolis archive dc_fb47d87f26e4, sha256 238a7783a72461e0ad4f2e59cb25c4bac19efae76a50294d25483cddc88cb211)
BibTeX
@misc{dcfb47d87f26e4,
title = {Per-Query Recall Guarantees for Approximate Nearest Neighbor Search in Dynamic Vector Databases — arXiv:2611.07579},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.07579},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fb47d87f26e4; sha256 238a7783a72461e0ad4f2e59cb25c4bac19efae76a50294d25483cddc88cb211},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07579. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Vector search runs as an operator in database systems, where a missed neighbor can make a filter, join, or aggregate wrong, yet approximate nearest neighbor (ANN) indexes are tuned only for an average recall target. In our measurements, indexes tuned to an average recall of 0.99 left 5-19% of in-distribution queries and, tuned without a query log, up to 99.6% of real out-of-distribution queries below this target, and the misses grew under updates. We present PQR-Search, a k-ANN search method that guarantees $\Pr[\mathrm{Recall}(q)<\tau]\le\delta$ for every query. The probability is only over a random orthogonal transformation inside the index, so no distributional assumption is needed, only that queries and updates do not depend on it; the guarantee holds after insertions and deletions without retuning. PQR-Search stores 1-bit codes of rotated residuals with respect to IVF centroids and prunes with exact quantiles of their error distribution. A formula predicting the fraction of vectors that pass the code test, with no data-fitted constants, chooses index parameters and maintenance operations without affecting the guarantee. On 20 datasets of up to 100 million vectors, failure rates stayed at most $\delta$ in every audit, including all 33 steps of the official NeurIPS'23 streaming runbook, whereas CTR, a conformal guarantee averaged over queries, left up to 16.4% of queries below the target. Where HNSW tuned to an average recall of 0.99 met that target, PQR-Search had 2.5x its single-query latency and 1.3x lower batch throughput, yet that HNSW still left 3-29% of queries below 0.99. PQR-Search was faster than FAISS exhaustive search in every static setting (26.4x geometric mean in batch; 69-154x at 100M scale), faster than IVF with nprobe chosen afterwards for every test query in all 52 main settings, and 27-76x faster at one thread than PUFFINN, which also gives per-query guarantees.
Tema degli esploratori: statistica e scienza dei dati (elenco arXiv cs.DB, nuovi lavori del giorno).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2611.07579 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:26:12.515Z dalla pagina https://arxiv.org/list/cs.DB/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).