QASP: Query-Adaptive Robust Vector Search Policy

The gist A fundamental challenge of vector search is achieving consistently high recall while minimizing computational costs.

QASP Overview

QASP (Query-Adaptive robust vector Search Policy) introduces a learning-based query-adaptive search that predicts fine-grained recall progress, from which a search policy is derived for any recall target<ref:2607.29606#pg2> QASP (Query-Adaptive robust vector Search Policy) introduces a learning-based query-adaptive search that predicts fine-grained recall progress, 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 presearch 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.

Search Policy Formalization

The paper formalizes a learning framework to design a robust search policy based on predicting fine-grained recall contributions of each index partition to optimize per-query performance. The goal is to find a policy which is optimal (or close to it) on Q, while also generalizing to unseen queries q ∈ R d ∩ Q and to recall values beyond r∗. This can be naturally cast as a supervised learning problem, where we train a machine learning model to predict the behavior of the index I(D) on the workload Q, using its observed performance on Q as well as the ground-truth nearest neighbors of Q in D as labels to train on.

Learning Frameworks

The paper develops two primary approaches for learning a probe policy. First, Ordinal Regression aims to find a function gθ∗ whose output is an ordinal value l ∈ 1,..., L by minimizing the empirical loss defined in equation (2). Second, Recall-based Regression learns a recall predictor f that maps a query q and number of probes l to the recall it expects to achieve for that query. This approach is justified by Proposition 4, which shows that zero loss in equation (4) implies zero loss in equation (2).

Model Features and Training

QASP employs supervised learning to model the relationship between query characteristics and retrieval performance. Model features are data signals that are informative for recall prediction task and accessible at inference with no additional computation. These features include Dataset Features such as Data Size, Index Features like Rank, Cumulative Cluster Size, and Query Features such as Relative Distance and Local Intrinsic Dimensionality. The training pipeline involves generating training signals by performing nearest neighbor search under configurations that approximate exhaustive retrieval for queries sampled from the dataset. Three variants are built: QASP-DL (lightweight deep learning architecture), QASP-GBDT (gradient boosted decision tree model), and QASP-LITE (polynomial regression model).

Theoretical Guarantees and Dominance

The paper establishes theoretical bounds on sample size to train QASP to near optimality, proving that a finite sample of queries suffices for training, independent of dataset size and dimensionality. It shows that fixed policies leave an inherent sub-optimality gap, and QASP is guaranteed to perform within this gap up to a negligible margin. Furthermore, it proves that QASP achieves strictly lower expected data access than fixed probing, with savings growing exponentially in the intrinsic dimensionality of the data.

Performance Evaluation

QASP is evaluated using a Query Variability-aware Evaluation (QVE) framework which includes Recall Variance, Absolute Query Deviation, and Query Satisfaction Rate. Experimental results show that QASP consistently outperforms Oracle Nprobe on QVE metrics achieving 57.7% lower recall variance and 33.6% lower deviation from recall target. QASP transfers effectively across datasets and index configurations with zero-shot or minimal fine-tuning, scaling to larger data and hierarchical indices achieving 99% recall with 80% less data access. The reactive complement guides policy behavior at search by detecting whether predicted rates underpredict or over-predict observed rates using EWMA smoothing.

Scaling and Deployment

QASP extends to hierarchical partitioning using inference-time scaling alone, achieving 99% recall with 80% less data access. In deployment efficiency, QASP involves a single inference plus search time, which becomes proportionally smaller at higher recall targets and with larger datasets. The theoretical dominance condition shows that QASP dominates whenever the predictor is “good enough” relative to the heterogeneity of the query distribution.

Conclusion

QASP decouples the policy from specific targets or index configurations and enables domain adaptation with zero-shot or minimal fine-tuning. The paper concludes that QASP achieves significantly lower variance, lower deviation from target, and higher satisfaction rate while accessing similar or less data, with improvements most pronounced for hard queries and high recall regimes.

How it works

1. QASP predicts the complete recall progression curve per query via a single upfront supervised regression.

2. A search policy is derived for any recall target from this prediction, avoiding iterative model invocations during search or separate predictors per target.

3. The policy uses normalized scale-invariant features and presearch inference to generalize across recall targets, index configurations, and datasets.

4. Fine-grained progress predictions enable a lightweight reactive complement that adjusts search depth based on predicted-versus-observed deviations without additional inference.

Theoretical Guarantees

1. The paper proves that a finite sample of queries suffices for training QASP to near optimality, independent of dataset size and dimensionality.

2. It shows a fundamental lower bound on the population loss of any fixed probe policy, determined by the variance in query difficulty, and that QASP’s loss exceeds that of the optimal fixed policy by only a negligible margin that vanishes with increased data.

3. QASP achieves strictly lower expected data access than fixed probing, with savings growing exponentially in the intrinsic dimensionality as query difficulty heterogeneity increases.

Performance Evaluation

1. The paper uses a Query Variability-aware Evaluation (QVE) framework with metrics like Recall Variance and Absolute Query Deviation to compare query variability even when r¯ ≈ r∗ between search policies.

2. QASP consistently outperforms Oracle Nprobe on QVE metrics achieving 57.7% lower σ2 and 33.7% lower δ, while satisfying 7.3% more queries and accessing just 0.06% more data for r∗ = 90%.

3. The reactive complement improves QVE metrics at higher average recall, with QASP + Reactive further boosting QASP performance.

Scaling to Hierarchical Index

QASP extends to hierarchical partitioning using inference-time scaling alone, achieving 99% recall with 80% less data access consistently across both datasets (SIFT1B: 82–87%, Deep1B: 80–84%).

Domain Adaptation

QASP models generalize well zero-shot to unseen indices without fine-tuning, and few-shot training with minimal data closes gaps effectively.

Reactive Complement

The reactive complement uses EWMA smoothing to detect consistent deviations between predicted and observed discovery rates, enabling early termination opportunities or extending search beyond initial predictions.

Cost Dominance Condition

QASP dominates whenever the predictor is “good enough” relative to the heterogeneity of the query distribution; conversely, when Fr is concentrated, all queries are equally hard and adaptive probing offers no advantage.

Conclusion

QASP enables search optimization beyond early termination, crossdomain transfer, and a lightweight reactive complement that can monitor predictions during search. The paper demonstrates that QASP achieves significantly lower variance, lower deviation from target, and higher satisfaction rate while accessing similar or less data. The paper extends to hierarchical partitioning using inference-time scaling alone, achieving 99% recall with 80% less data access. QASP’s progressive recall predictions further enable a lightweight reactive complement without additional inference.

References

[1] LanceDB, “IVF-PQ index,” LanceDB Documentation, https://lancedb.github.io/lancedb/concepts/index ivfpq/

[2] Facebook AI Research, “Guidelines to choose an index,” FAISS Wiki, https://github.com/facebookresearch/faiss/wiki

[3] OpenSearch, “Choose the k-NN algorithm for your billionscale use case with OpenSearch,” Amazon OpenSearch Service Blog, 2022, https://aws.amazon.com/blogs/big-data/choose-the-k-NN-algorithm-for-yourbillionscaleusecasewithopensearch/

[4] C. Li, M. Zhang, D. G. Andersen, and Y. He, “Improving approximate nearest neighbor search through learned adaptive early termination,” in Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data, 2020, pp.

1. textbfReal-time Query Adaptation via QASP Inference Policies: The improved system can predict a 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 and enables the derivation of an optimal probe count based on predicted performance, moving beyond fixed parameters or iterative reactive methods like LAET [4] or DARTH [20].

2. textbfGuaranteed Loss Minimization Across Data Scales: The system can leverage theoretical guarantees proving that QASP requires a finite training sample independent of dataset size and dimensionality and that its loss exceeds the irreducible lower bound of any fixed policy by a vanishing margin. This ensures robust performance regardless of the scale or complexity of the underlying vector database.

3. textbfExponential Data Access Savings in High Dimensionality: The system can achieve strictly lower expected data access than fixed probing, with savings growing exponentially in intrinsic dimensionality as query difficulty heterogeneity increases. This means that as data becomes more complex, QASP's efficiency advantage over traditional methods grows significantly.

4. textbfZero-Shot and Few-Shot Domain Adaptation: The improved system can generalize effectively across datasets and index configurations via zero-shot or minimal fine-tuning using features like normalized and scale-invariant features. This allows the system to operate on unseen data or different index structures without extensive retraining.

5. textbf Lightweight Reactive Complement: The search process can incorporate a lightweight reactive complement that adjusts search depth based on predicted-versus-observed deviations without additional inference. This mechanism, utilizing EWMA smoothing and Shewhart-type run rules, enables real-time validation of recall estimates during the actual vector traversal.