PQR-Search bounds recall for individual queries
Per-Query Recall Guarantees for Approximate Nearest Neighbor Search in Dynamic Vector Databases · arXiv:2611.07579
In plain words
Search indexes try to find the nearest vectors without checking every one. Tuning an index to do well on average can still leave many individual searches with too few of the right results, especially when real searches differ from the examples used for tuning.
PQR-Search uses short random codes to rule out vectors that cannot be close, then checks exact distances for the remaining candidates. Its guarantee applies to each fixed query over the index’s random setup. In audits across 168 static settings, 45 of 4,176,000 checks fell below the promised recall target.
The research
An average score can conceal searches that return too few of the right neighbors, especially when real queries differ from tuning examples. A bound for each fixed query changes what a recall target can promise, while its dependence on the index’s random setup determines when that promise applies.
PQR-Search uses randomized residual codes and exact checks to bound, for each fixed query, the chance of missing its target recall, including after independent updates.
PQR-Search tests randomized codes for unvisited vectors, then calculates exact distances for candidates that could still be neighbors. Its analysis bounds the chance that each fixed query falls below a chosen recall target, with probability taken over the index’s random transformation.
In static audits across 168 settings, 45 of 4,176,000 checks fell below target, within the stated bound. The result supports per-query protection under the method’s assumptions, rather than a guarantee averaged across a query distribution.
The guarantee assumes that queries, updates, and index construction do not depend on the index’s secret random transformation. The reported audits test the implementation on selected configurations; they do not remove that condition.
What the evidence shows
- A guarantee for each query
PQR-Search is an index and search method for approximate nearest-neighbor search in databases that change over time. It targets a gap in average-recall tuning: an index can meet its average target while leaving some individual queries below it.
The method instead gives a probability bound for each fixed query, with probability taken over the index’s internal random transformation.
- Average scores hide misses
These measurements show that average recall can hide many individual misses, especially when tuning queries differ from real ones. For indexes tuned on data vectors and tested on real queries from yandex, laion, and hotpotqa, 51.4–99.6% of queries fell below 0.99 recall at k=100.
- What the method changes
PQR-Search stores randomized one-bit codes for vector residuals and uses them to test whether unvisited vectors could lie within a query’s current pruning radius. It calculates exact distances for candidates that pass the test.
The analysis bounds the chance of falling below a chosen recall target for each fixed query, without assuming a particular query distribution. That changes what the guarantee protects: an average across queries becomes a bound for an individual query over index randomness.
- The bounds in practice
The audits support the claimed per-query bound in the tested configurations, while CTR’s distribution-level guarantee controls risk averaged across queries and can permit some individual queries to miss the target.
In 27 reported CTR settings, up to 16.4% of queries fell below target; the source does not establish that the methods used identical query sets.
- Dynamic search, with conditions
The index also handles insertions and deletions without retuning, subject to the same independence condition for queries, updates, and maintenance decisions. Evaluation included 20 datasets with up to 100 million vectors and a streaming runbook.
Together, the analysis and tests support a per-query guarantee for the stated dynamic design and tested scope; the guarantee’s assumptions remain part of the result.
Deep
- Original paper authors
- Woong-Kee Loh, Suan Lee
- Submitted to arXiv
- License
- arXiv non-exclusive