QASP: Query-Adaptive Robust Vector Search Policy
2026-07-31 • Information Retrieval
Information RetrievalMachine Learning
AI summaryⓘ
The authors address the problem of getting consistent and accurate search results in vector search without wasting too much computing power. They propose QASP, a method that predicts how well a search will perform for each query before actually searching, allowing it to adjust the search effort to meet a desired accuracy. QASP uses a single prediction step that works for different accuracy levels and setups, and can also react during the search if things go off track. Their results show QASP reduces unnecessary data checks significantly while keeping search accuracy high and stable across many types of searches.
vector searchrecallregressionsearch policyquery adaptationindexingdata accessintrinsic dimensionalityhierarchical indicessupervised learning
Authors
Hakan Ferhatosmanoglu, Kushal Kumar, Tal Wagner, Andy Warfield
Abstract
A fundamental challenge of vector search is achieving consistently high recall while minimizing computational costs. Fixed search parameters cause significant performance variance across queries, and conventional evaluation on average recall masks these per-query disparities. We introduce QASP (Query-Adaptive robust vector Search Policy), which predicts the complete recall progression curve per query via a single upfront supervised regression, from which a search policy is derived for any recall target; this avoids iterative model invocations during search or separate predictors per target. By predicting normalized recall values with scale-invariant features and pre-search inference, QASP generalizes across recall targets, index configurations, and datasets. Its fine-grained progress predictions further enable a lightweight reactive complement that adjusts search depth based on predicted-versus-observed deviations without additional inference. We prove that QASP requires a finite training sample independent of dataset size and dimensionality, that its loss exceeds the irreducible lower bound of any fixed policy by a vanishing margin, and that its data access savings over fixed probing grow exponentially in intrinsic dimensionality. Experimentally, QASP achieves significantly lower recall variance and deviation from target, higher query satisfaction rate, and scales to large data and hierarchical indices without retraining, achieving 99% recall with 80% less data access.