QASP: Query-Adaptive Robust Vector Search Policy

2026-07-31 · 16:38 UTC ·Hakan Ferhatosmanoglu, Kushal Kumar, Tal Wagner... ·1 min read

Brief

QASP addresses per-query performance variance in approximate vector search by predicting each query's full normalized recall-progression curve via a single upfront supervised regression and deriving recall-targeted search policies (avoiding per-target models or iterative inference). The method includes a lightweight reactive adjuster, provides finite-sample and near-optimal loss guarantees, and empirically achieves 99% recall with 80% less data access.

Why it matters

QASP predicts the complete per-query normalized recall-progression curve with a single upfront supervised regression (no iterative model calls or separate predictors per recall target), using scale-invariant features and a lightweight reactive adjuster that adapts search depth from predicted-vs-observed deviations.

Key details

The paper proves finite training-sample sufficiency independent of dataset size and dimensionality, shows QASP's loss exceeds the irreducible lower bound of any fixed policy by a vanishing margin, and that data-access savings over fixed probing grow exponentially in intrinsic dimensionality.

Empirically (preprint by Ferhatosmanoglu, Kumar, Wagner, Warfield; arXiv:2607.29606v1, 2026-07-31), QASP reduces per-query recall variance, increases satisfaction rate, and reaches 99% recall with 80% less data access while scaling to large and hierarchical indices without retraining.

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.

Comment: 12 pages, 6 figures, 6 tables, preprint