Per-Query Recall Guarantees for Approximate Nearest Neighbor Search in Dynamic Vector Databases
Vector search now runs as an operator inside database systems, where a missed neighbor makes a query answer wrong, yet approximate nearest neighbor (ANN) indexes are tuned only for a target average recall. Tuned to an average recall of 0.99, indexes left 5-19% of in-distribution queries and, without a query log, up to...