← 研踪 PaperTrailarXiv:2611.07579 · v1
Per-Query Recall Guarantees for Approximate Nearest Neighbor Search in Dynamic Vector Databases
首次提交 2026-11-05 15:30
版本更新 2026-11-05 15:30
雷达观测 2026-11-06 11:06
摘要
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)<τ]\leδ$ 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 $δ$ 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.
作者备注：66 pages, 15 figures, 19 tables. Extended version of a paper submitted to ICDE 2027
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-05 15:30 · 最新观测版本
Per-Query Recall Guarantees for Approximate Nearest Neighbor Search in Dynamic Vector Databases
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)<τ]\leδ$ 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 $δ$ 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.
查看此版本解读 →查看此版本原文 ↗