arXiv:2607.29606v1 [cs.IR] 31 Jul 2026
QASP: Query-Adaptive Robust Vector Search Policy Hakan Ferhatosmanoglu∗
Kushal Kumar∗
Tal Wagner
Andy Warfield
Amazon London, UK [email protected]
Amazon New York, USA [email protected]
Amazon and Tel-Aviv University Tel Aviv, Israel [email protected]
Amazon Vancouver, Canada [email protected]
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 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. 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. Index Terms—Vector Search Policy, Approximate Nearest Neighbor Search, Proactive Policy Learning
I. I NTRODUCTION Given a query vector q ∈ Rd and a dataset X ⊂ Rd , vector (similarity) search aims to find the k vectors {xq1 , . . . , xqk } ⊂ X that minimize dist(q, xq· ), where dist(·, ·) is a notion of distance. The fraction of k closest vectors found is the recall for that query. A vector search policy determines the search parameters to achieve high recall with low cost. Practitioners typically rely on heuristic guidelines to identify search parameters based on average performance, generating rules such as accessing a fixed proportion α ∈ [0.05, 0.1] √ of the dataset or ⌊ L⌋ out of L partitions [1]–[3]. Queryagnostic settings fail to capture heterogeneous query difficulty and the resulting variation in computational needs [4]–[7]. This causes over-reading for easy queries and under-reading for difficult ones. Conventional evaluation methods compound this problem by focusing on average recall, which masks per-query disparities. Figure 1 illustrates how query-agnostic ∗ Equal contribution.
policies access significantly more data than the query-adaptive approach. Our goal is to design a proactive search policy that consistently achieves high recall with minimal performance variance across queries regardless of difficulty. We present QASP, Query-Adaptive robust vector Search Policy, which addresses this through supervised regression that predicts the complete recall progression curve, from which a policy is derived for any recall target. A single upfront inference produces the fine-grained predictions, departing from recent approaches that invoke models iteratively during search or design separate predictors per recall target. QASP’s formulation predicts normalized recall values, and combined with scale-invariant features and pre-search inference, admits richer architectures and target-agnostic deployment. QASP’s fine-grained progress predictions also enable a lightweight reactive complement that treats each progress estimate as a testable hypothesis and adjusts search depth based on deviations between predicted and observed discovery rates, without additional model inference. QASP is designed for partitioning-based indices, e.g., Inverted File (IVF), clustering, quantization, multi-dimensional trees, due to their discrete, independent units that enable highly efficient upfront recall estimation with minimal training data, and enable proactive parameter selection and resource allocation. Partitioning-based methods are widely preferred in production systems due to their memory efficiency, parallelization across computational and storage units, compatibility with distributed architectures, and ability to achieve sublinear scaling [8]. We establish theoretical guarantees for QASP. We prove that a finite sample of queries suffices for training, independent of dataset size and dimensionality. We show a fundamental lower bound on the population loss of any fixed probe policy, determined by the variance in query difficulty, and show that QASP’s loss exceeds that of the optimal fixed policy by only a negligible margin that vanishes with increased data, establishing both generalization and competitive performance guarantees. Beyond loss, we show that QASP achieves strictly lower expected data access than fixed probing, with the savings growing exponentially in the data’s intrinsic dimensionality as query difficulty heterogeneity increases. To our knowledge, this is also the first work to explore transfer learning and domain adaptation in vector search,
cant performance improvements over baselines, with further gains on large datasets, at high recall targets, and for hard queries, where traditional approaches struggle with both consistency and cost. II. Q UERY-A DAPTIVE ROBUST V ECTOR S EARCH P OLICY
Fig. 1: Comparing fixed and adaptive policies: Query satisfaction rate (% of queries achieving 90% recall) versus data accessed (Deep1B 10M dataset). For fixed nprobe, we gradually increase probes and plot query satisfaction and data accessed. QASP adaptively sets parameters for the same query satisfaction. Fixed policy consistently over-reads, with the gap widening as more queries reach recall target. where prior solutions are predominantly coupled to specific index configurations and recall targets. We design normalized scale-invariant features that integrate query difficulty signals with index characteristics, and express both features and predictions as normalized ratios, enabling the learned function to better generalize across index configurations, recall targets, and datasets. Through ablation studies and feature importance analysis, we identify the most influential features for recall prediction. Experimental evaluation confirms that QASP consistently outperforms baselines and achieves around 57.7% lower recall variance, 33.6% lower deviation from recall target, and 7.3% higher query satisfaction rate with similar or lower data access. QASP transfers effectively across datasets and index configurations with zero-shot or minimal fine-tuning, and scales to larger data and to hierarchical indices achieving 99% recall with 80% less data access. To summarize, this paper makes following contributions: • We introduce QASP, a learning-based query-adaptive search that predicts fine-grained recall progress, from which search policies are derived for any recall target. QASP enables search optimization beyond early termination, crossdomain transfer, and a lightweight reactive complement that can monitor predictions during search. • We establish theoretical bounds on sample size to train QASP to near optimality. We show that fixed policies leave an inherent sub-optimality gap, and prove that QASP is guaranteed to perform within this gap up to a negligible margin. We further prove that QASP achieves strictly lower expected data access, with savings growing exponentially in intrinsic dimensionality. • We conduct experiments using both standard and query variability-aware evaluation metrics. QASP achieves signifi-
We formalize 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. Ideal ML-enhanced search should support low inference overhead. Partitioning-based data organization offers a well-suited setting that makes this feasible by decomposing search into units whose recall contributions can be predicted separately and upfront. We present our framework concretely for clustering/IVF (Inverted File) indices [9]–[13], though the approach extends to any partitioning-based organization, including hierarchical clustering as we study in Section II-D3. Partitioning-based indices are the core component of large-scale vector databases [12]–[16]. An IVF-type index I(D) built over a dataset D ⊂ Rd is meant to improve the computational cost of fully exhaustive search. To this end, it partitions D into L non-overlapping partitions (clusters) C1 , . . . , CL with corresponding centroids µ1 , . . . , µL . Given a query q ∈ Rd , exhaustive search is performed only on the l top-ranked clusters, where l ≪ L, and the clusters are ranked by their centroid distance from the query. This raises the question of how to set l, which is called the number of probes. Commonly, l is set to a fixed value for all queries (see Section V), which we refer to as fixed probe policy. Our goal is to leverage supervised learning in order to predict the optimal l per query. To start, we formally define query-dependent probe policies. Definition 1. A probe policy is a map g : Rd × [0, 1] → N, which maps a query q ∈ Rd and a recall target r ∈ [0, 1] to a number l = g(q, r) of top-ranked clusters to probe for q. The policy is valid for an index I(D) with L clusters if 1 ≤ g(q, r) ≤ L for all q ∈ Rd and r > 0 (thus, the policy instructs us to probe at least one cluster and no more than all clusters per query). Given a query set Q ⊂ Rd and recall target r∗ ∈ [0, 1], we say that a policy g is optimal for Q and r∗ if it probes exactly the minimal number of clusters necessary to achieve recall r∗ on each query q ∈ Q. Formally, let RI(D) (q, l) denote the recall attained for a query q when probing its l top-ranked clusters in I(D). Then, the optimal number of probes ℓ∗ can be defined as follows: ℓ∗ (q, r) := min{l : RI(D) (q, l) ≥ r}.
(1)
An optimal policy g ∗ for Q and r∗ satisfies g ∗ (q, r∗ ) = ℓ∗ (q, r∗ ) for all q ∈ Q. This does not specify the behavior of g on queries q ∈ Rd \ Q, i.e., it does not specify how to generalize beyond Q.
A. Ordinal Regression Our goal is thus to find a policy which is optimal (or close to it) on Q, while also generalizing to unseen queries q ∈ Rd \ 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. Supervised learning is useful here for two key properties: on the one hand, ML models can be efficiently trained to find high-quality solutions in the large function spaces, like that of probe policies; on the other hand, if trained with suitable features, ML models are known to generalize well to unseen inputs. We now formalize an appropriate supervised learning problem. Let Θ be the parameter space for a parameterized class G = {gθ : θ ∈ Θ} of probe policies. To find an optimal probe policy in G for queries Q and recall target r∗ , consider the optimization problem: 1 X ∗ 2 (ℓ (q, r∗ ) − gθ (q, r∗ )) . (2) θ∗ = arg min 2 θ∈Θ L |Q| q∈Q
This is an ordinal regression problem, since its goal is to learn a function gθ∗ whose output is an ordinal value l ∈ {1, . . . , L}. The normalization by L2 |Q| ensures that the minimized loss is in [0, 1] for convenience and does not alter the minimization problem. B. Recall-based Regression Since ordinal regression is notoriously difficult to optimize [17], we develop an alternative recall-based approach for learning the probe-policy. To this end, we learn a recall predictor as an intermediate step. It maps a query q and number of probes l to the recall it expects to achieve for that query by probing the index its l top-ranked clusters. A recall predictor gives rise to a probe policy by using the minimal number probes predicted to attain the recall target. Definition 2. Given an index I(D) with L clusters, a recall predictor is a function f : Rd × N → [0, 1] that maps a query and probe count to a predicted recall value. Definition 3. A recall predictor f induces a probe policy g [f ] defined as g [f ] (q, r) := min{l : f (q, l) ≥ r}.
(3)
e parameterize a class of recall predictors, F = {fθ : Let Θ e The induced class of parameterized probe policies θ ∈ Θ}. e We learn a recall predictor by is G = {gθ = g [fθ ] : θ ∈ Θ}. optimizing an L2 loss: L
2 1 XX fθ (q, l) − RI(D) (q, l) . θ∈Θ L|Q|
θ∗ = arg min
(4)
q∈Q l=1
Learning a recall predictor as a surrogate for learning a probe policy is justified by the following consistency property.
e is such that fθ∗ attains zero Proposition 4. Suppose θ∗ ∈ Θ loss in eq. (4). Then gθ∗ = g [fθ∗ ] attains zero loss in eq. (2). Proof. Zero loss in eq. (4) implies that fθ∗ (q, l) = RI(D) (q, l) for all q, l. Plugging this in eqs. (1) and (3) yields ℓ∗ (q, r) = g [fθ∗ ] (q, r) for all q, r. This yields zero loss in eq. (2). Recall-based regression (eq. (4)) offers numerous advantages over direct ordinal regression for the probe policy (eq. (2)). First, it is more tractable to optimize [17]. Second, since its target predictions are values in a fixed range [0, 1], independent of the number of clusters L, the same induced policy is transferrable across indices with different numbers of clusters. Third, the learning problem in eq. (4), unlike that in eq. (2), is independent of a recall target r∗ , and thus generalizes better across different recall values. Fourth, the loss function in eq. (4) directly involves L numerical values obtained from the index I(D) per query (the values {RI(D) (q, l) : l = 1, . . . , L}), compared to just one such value in eq. (2) (the value ℓ∗ (q, r∗ )). This allows the learning model to use more supervised labels per query from the index, increasing ground-truth utilization and learning effectiveness. Directly predicting nprobe couples the model to a specific recall target and index size, and provides L× fewer supervision signals per query. We confirm empirically (in Section VI-D) that single-nprobe prediction results in significantly higher variance and more data access than QASP (Table II). Fifth, recall-based regression inherently produces a recall prediction per cluster, and these values can be leveraged at search time for further optimizations without model inference, such as reactive early/late termination if rate of newly discovered neighbors per probe subceeds/exceeds (respectively) the initial recall predictions (see Section II-E). C. Model Training QASP employs supervised learning to model the relationship between query characteristics and retrieval performance. We share details on different parts of the training pipeline. 1) Training Data Generation: We obtain training signals by performing nearest neighbor search under configurations that approximate exhaustive retrieval for queries sampled from the dataset (or query workload if available). Recall measurements are obtained for every searched partition and serve as prediction targets. Query features are obtained as a by-product of this one time search with no additional overhead (see Section III). The resulting dataset is split into validation and testing. Training data generation involves the same operations as any search parameter optimization; ground-truth neighbors and recall at varying probe depths are needed even to select a fixed nprobe. QASP fits a lightweight model on the collected data. 2) Model Selection: We build three variants of pre-trained QASP models. First, QASP-DL is a lightweight deep learning architecture for tabular learning [18] with batch normalization and dropout. Second, QASP-GBDT is a gradient boosted decision tree model which is a de-facto architecture for tabular learning tasks due to their ability to handle decision manifolds
effectively [19]. Third, QASP-LITE is a polynomial regression model. All variants are trained to optimize mean squared error loss and differ in expressive power, inference latency, ease of integration and adaptability to unseen domains. D. Model Invocation Training QASP models on the recall regression task serves as a surrogate for the search policy during model invocation Section II-B. Beyond the naive application of QASP to the same data distribution as it is trained on, QASP can be effectively employed at search-time. 1) Model Inference: QASP model inference is performed proactively on the query workload prior to vector search execution. This design allows rich architecture such as deep learning unlike prior work [20] due to workload-level optimizations. Batching for large-scale inference allows easy parallelism and GPU acceleration can yield significant scaling benefits. By processing queries in batches, the approach amortizes computational overhead and sustains high throughput, even as the index partitioning scales to orders of magnitude beyond the size observed during training. 2) Domain Adaptation: Recall prediction serves as a foundational training objective for vector search, generalizing effectively across datasets, query distributions, and index configurations. We design features that are normalized and scale-invariant (see Section III), which capture fundamental search difficulty signals that transfer across heterogeneous scales and indexing schemes. This enables QASP to adapt to new domains via both zero-shot transfer, where the pre-trained model generalizes to unseen datasets and index configurations without adjustment, and few-shot transfer, with limited training on batch normalization [21] and final projection layers using very few queries from the target domain. 3) Scaling to Hierarchical Indices: At invocation time, QASP can be scaled to large indices without additional training by extending the same feature transformations on hierarchical partitioning. QASP models can effectively be trained once on a smaller flat index and applied across all hierarchy levels. At inference, model features at each level are computed using coresets, with second-level centroids already available from index construction providing a lightweight approximation. This combination enables fast, scalable model invocation across large indices. E. Lightweight Reactive Complement QASP’s fine-grained recall predictions R1 , . . . , RL enable real-time validation as search progresses: Each prediction Ri represents cumulative recall after searching i partitions, makg i = Ri − Ri−1 a testable ing the incremental contribution DR hypothesis about partition i’s value. For example, when QASP predicts that partition i will increase recall from 0.89 to 0.94, it asserts that this partition contains approximately 0.05k true nearest neighbors, which can be immediately verified during search. The actual discovery rate DRi is observed as partition i’s contribution to the running result set.
g i underThe goal is to detect whether predicted rates DR predict or over-predict observed rates DRi as search progresses. We adapt a lightweight statistical process control solution using EWMA smoothing: SDRi = α · DRi + (1 − α) · SDRi−1 to prioritize recent discovery rates. A Shewhart-type run rule detects consistent deviations ∆i = g i )/DR g i over consecutive steps. Consistently (SDRi − DR negative values indicate early termination opportunities, while consistently positive values suggest extending search beyond initial predictions. See Section VI-G for pseudocode. III. M ODEL F EATURES Model features are data signals that are informative for recall prediction task and accessible at inference with no additional computation. We define a set of features, with scaleinvariant transformations, designed to capture diverse query and index characteristics. A. Feature Types √ Dataset Features. Data Size: 1/ d n, where n = |D|, is the dataset size and d is the vector dimensionality. This quantity captures the expected separation (min distance) between n points packed in a unit sphere. Index Features. Rank: 1 − exp(−l/L), where l is centroid rank and L is total number of centroids. Normalization by L ensures rank ∈ (0, 1 − 1/e] for all indices. Exponential decay captures diminishing returns Plof accessing further clusters. Cumulative Cluster Size: i=1 |Cπq (i) |/|D|. This represents fraction of vectors read up to a given centroid rank l. This feature is especially useful for imbalanced indices. Cluster Coefficient of Variance: σ(d(vl , µl ))/µ(vl , µl ), where σ(d(vl , µl )) is the standard deviation and µ(d(vl , µl )) is the mean distance between data vectors vl ∈ Cl and centroid µl . Maximum Cluster Distance: max(vl , µl )/d(q, µπq (1) ), where max(vl , µl ) is the max distance between data vectors vl ∈ Cl and centroid µl and d(q, µπq (1) ) is the distance between query and the centroid of nearest cluster. We also consider other statistical summaries (like min, p25, p75) over the distance distribution. Normalization with (q, µπq (1) ) is performed at search time. Query Features. Relative Distance: tanh(δ(q, l) − 1), where δ(q, l) = d(q, µl )/d(q, µπq (1) ) and d(q, µπq (1) ) is the distance from query q to its nearest centroid. Query-to-centroid distances are normalized relative to the nearest centroid distance. Hyperbolic tangent compresses distances into bounded ranges and aims to capture diminishing returns of accessing distant clusters. Local Relative Contrast: µ(d(q, µπq (·) ))/d(q, µπq (1) ), where d(q, µπq (1) ) is the distance from query q to its nearest centroid and the numerator represents the average distance to all other centroids. This feature is an adaptation of the local relative contrast defined by [22] using centroid PLvectors. Local Intrinsic Dimensionality: −k/ i=1 [ln d(q, µπq (i) )− ln d(q, µπq (L) )], where d(q, µπq (i) ) is the distance from query q to the ith centroid and d(q, µπq (L) ) is the distance between q and the farthest centroid. It quantifies the difficulty of the query [22] and we adapt it using centroid vectors.
B. Feature Transformation The foregoing feature design incorporates various transformation (e.g., normalization with respect to L or |D|, using exponential decay and hyperbolic tangent) to bound feature ranges within fixed intervals, thereby providing a scaleinvariant feature representation across varying search configurations. By expressing features as normalized ratios, they remain meaningful across different vector space distributions, dataset scales or index configurations. Another transformation we consider is relative difference or “relative jumps” for any feature, call it φ(q, l), varying with l: φ(q, l) − φ(q, l − 1) . ∆(φ; q, l) = max1<j<l (φ(q, j) − φ(q, j − 1) This allows QASP to rely not only on the raw feature value but also on how much the feature value changes as more clusters are probed in order to detect diminishing returns. We pad the output of this transformation with 0 wherever undefined. We conduct feature analysis and ablations to find the feature set (see Section VII-C). IV. T HEORETICAL G UARANTEES FOR QASP In this section we analyze QASP’s optimization and connect the structure of the vector index to the provable advantage of QASP. We first show that every fixed policy suffers irreducible loss determined by the variance of query difficulty, and that QASP can be trained nearly optimally with a finite number of samples independent of dataset size and never outperformed by any fixed policy except by a vanishing margin. We then derive a dominance condition proving that QASP’s data access savings grow exponentially in intrinsic dimensionality. Let Q be a query distribution over Rd . Suppose that the given query set Q is a sample from Q. Let r∗ ∈ [0, 1] be the recall target. We define the population loss of a probe policy g on Q and r∗ as 1 ∗ ∗ ∗ 2 (ℓ (q, r ) − g(q, r )) , (5) L(g) := Eq∼Q L2 where ℓ∗ (q, r∗ ) is the minimum number of clusters in I(D) that need to be probed to attain recall r∗ for q, as per eq. (1). For a finite sample Q from Q, we define the corresponding empirical loss L̂(g) as follows. Observe that the probe policy learning problem in eq. (2) minimizes this empirical loss on Q. 1 X ∗ L̂(g) := 2 (ℓ (q, r∗ ) − g(q, r∗ ))2 . L |Q| q∈Q
A. Sub-Optimality of Fixed Probe Policies We first provide a suboptimality bound for the population loss of fixed policies. A fixed policy g maps all queries to a fixed number of probes. We denote by g (l) the fixed l-probe policy, defined as ∀q ∈ Rd ,
g (l) (q, r∗ ) = l.
(6)
We define a distribution over {1, . . . , L} from Q. Let Λ be a random variable in {1, . . . , L} drawn by sampling q ∼ Q and setting Λ = ℓ∗ (q, r∗ ). (7) Thus, Λ is the optimal number of clusters that needs to be scanned for a query drawn at random from Q, under the recall target r∗ . We can relate the sub-optimality of fixed probe policies to the distribution of Λ as follows. Theorem 5. For every l ∈ {1, . . . , L}, the population loss of the fixed-probe policy g (l) satisfies L(g (l) ) ≥ Var(Λ)/L2 . is a uniform lower bound Thus, the single quantity Var(Λ) L2 on the population losses of every fixed probe policy simultaneously. We can evaluate this quantity — either empirically from the given query workload, or analytically under a distributional query model — to quantify the sub-optimality enforced by restricting the search procedure to fixed-probe policies. Example—Zipfian probes: The ρ-Zipfian law, Pr[ℓ] ∝ 1/ℓρ , is commonly used to model access frequency patterns [23]. For simplicity, we focus on the most standard case ρ = 1. Thus, for a partition-based vector index with L clusters and a query drawn at random from Q, the probability that its optimal number of probes is ℓ is proportional to 1/ℓ. Hence,P Λ is distributed as Pr[Λ = ℓ] = 1/(ℓ · HL ), where L HL = i=1 1i = Θ(ln L) is the Lth harmonic number. A direct calculation yields that 2 2 L(L + 1) L L2 L Var(Λ) = . − 2 =Θ =Θ 2HL HL HL ln L Hence, by Theorem 5, the population loss (5) of every fixedprobe policy is at least Ω(1/ ln L) > 0. Proof of Theorem 5.. We recall the following basic fact: Lemma 6. For every real-valued random variable X with E[X] < ∞, it holds that arg minµ∈R E (µ − X)2 = E[X]. Using this, every fixed probe policy g (l) satisfies, 1 (l) ∗ ∗ ∗ 2 L(g (l) ) = Eq∼Q (g (q, r ) − ℓ (q, r )) eq. (5) L2 1 = 2 Eq∼Q (l − ℓ∗ (q, r∗ ))2 eq. (6) L 1 ≥ 2 min Eq∼Q (µ − ℓ∗ (q, r∗ ))2 L µ∈R i h 1 2 = 2 Eq∼Q (Eq∼Q [ℓ∗ (q, r∗ )] − ℓ∗ (q, r∗ )) L i Var(Λ) 1 h 2 = 2 E (E [Λ] − Λ) = . eq. (7) L L2 B. QASP versus Fixed Probe Policies We show that a finite sample of queries Q from Q suffices to train QASP to better loss than any fixed probe policy with high probability, up to a small gap that vanishes as the sample size grows. Importantly, the requisite sample size is independent of the dataset size |D|, and depends only on the number of clusters L and on the structure of the QASP model.
We start with some learning-theoretic definitions. The pseudodimension characterizes the number of samples required to certify generalization [24]–[28]. We define pseudo-dimension for probe policies as follows:
arithmetic operations and numerical comparisons, and (in the case of QASP-DL) exponentiations (in order to compute sigmoid activations). Therefore, the proposition follows from Theorem 9.
Definition 7 (pseudo-dimension of probe policy class). Let G be a class of probe policies. Let Q = {q1 , . . . , qM } ⊂ Rd . We say that Q is pseudo-shattered by G if there exist thresholds τ1 , . . . , τM ∈ R such that for every I ⊂ [M ], there is g ∈ G such that g(qi , r∗ ) > τi ⇔ i ∈ I. The pseudo-dimension of G is denoted pdim(G) and defined as the largest size of a set Q ⊂ Rd pseudo-shattered by G.
Theorem 11. Let ε, η ∈ (0, 1). Suppose the sample Q has size O(pdim(GQASP )/ε2 +log(1/η)). Let gQASP be the policy that minimizes eq. (2). Then, with probability 1 − η, it holds that
Function classes with finite pseudo-dimension are called learnable because their population loss can be approximately optimized from a finite sample. Specifically, the pseudodimension governs the sample size required to guarantee that the empirical loss approximates the population loss for every probe policy in the class, a property known as uniform convergence [29]. Theorem 8 ( [30], Theorem 19.2). Let ε, η ∈ (0, 1). Let Q be a sample from Q of size O((pdim(G) + log(1/η))/ε2 ). Then, h i Pr ∀g ∈ G : |L(g) − L̂(g)| < ε ≥ 1 − η. The pseudo-dimension can be bounded using the dimension of the parameter space and the complexity of the learned model, as per the following theorem, which is a specialization of Theorem 8 from [31] (based on [32], [33]) to probe policies. Theorem 9. Let G = {gθ : θ ∈ Θ} be a class of probe policies parameterized by an m-dimensional parameter space Θ. Let F (q) be any set of numerical features representing a query q ∈ Rd . Suppose that for every θ ∈ Θ and q ∈ Rd , it is possible to compute gθ (q, r∗ ) from θ and F (q) with an algorithm that can perform arithmetic operations {+, −, ×, ÷} and numerical comparisons {=, ̸=, >, ≥, <, ≤}. Suppose the algorithm has running time t. Then, pdim(G) = O(mt). Furthermore, if the algorithm is also allowed to perform exponentiation (x 7→ ex ), then pdim(G) = O((mt)2 ). We show that our implicit ML-based search policy, where probe decisions are induced through recall predictions can be analyzed through bounded pseudo-dimension theory. We prove that QASP’s compositionally-defined policy class has finite pseudo-dimension despite complex interactions between neural network recall predictors, query features, and the minimization operation that determines optimal probe counts. Lemma 10. The pseudo-dimension pdim(GQASP ) of all three QASP variants is finite. Furthermore, it depends only on L, and is independent of the dataset size n and the dimensionality d. Proof. Invoke Theorem 9. By Section III, the number of features |F (q)| per query q is O(L), hence so is the number of trainable parameters (i.e., the dimension of the parameter space) per QASP model. By Section II-C2, all three QASP architectures can be computed from F (q) using only
∀ l ∈ [L],
L(gQASP ) ≤ L(g (l) ) + 2ε.
(8)
Note that both the failure probability η and the performance gap 2ε vanish as we increase the sample size |Q|. Proof. With Lemma 10, we can proof Theorem 11. Since gQASP minimizes the empirical loss L̂, we have, ∀ l ∈ [L],
L̂(gQASP ) ≤ L̂(g (l) ).
(9)
By definition, the learned policy gQASP is realizable in the QASP model, meaning gQASP ∈ GQASP . Furthermore, all fixed-probe policies g (l) are realizable in the QASP model. Therefore, by Lemma 10 and Theorem 8, we have with probability 1 − η, |L(gQASP )− L̂(gQASP )| < ε and ∀ l, |L(g (l) )− L̂(g (l) )| < ε. Together with eq. (9), with probability 1 − η, eq. (8) follows. Remark. The same conclusion as Theorem 11 holds if we define the empirical loss with eq. (4) instead of eq. (2) and the appropriate analogous population loss (replacing Σq∈Q with Eq∼Q in eq. (4)). The formal proof goes by augmenting the feature set F (q) with the additional query features {RI(D) (q, l)}L l=1 , which enables computing the contribution of q to the loss from F (q) while maintaining the size bound |F (q)| = O(L). We omit further details. In Section IV-A we establish that fixed policies inherently leave room for loss improvement. Proposition 10 allows us to complement this result and prove that even in the worst case, with high probability, QASP’s loss is never worse than any fixed policy, except by a negligible margin that tends to zero as the sample size grows. C. Cost Dominance of Adaptive Probing Section IV-A and Section IV-B establish that QASP generalizes from finite samples and that fixed policies are inherently sub-optimal in loss. We now ask a complementary question: how much data access does QASP save, and under what conditions does it dominate fixed probing despite predictor imperfection? Fixed policies must provision for the tail of the query difficulty distribution, forcing every query, including easy ones, to pay the cost of the hardest queries. QASP instead pays what each query individually requires. We formalize this intuition and derive the precise conditions under which QASP dominates, connecting the geometry of the vector index to the quality of the learned predictor, with the gap growing exponentially in the intrinsic dimensionality of the data.
We introduce three quantities characterizing the index. Let DI = maxj maxx∈Cj ∥x − µj ∥ be the maximum cluster radius, σI = minj̸=j ′ ∥µj − µj ′ ∥ the minimum inter-centroid separation, and ∆ the doubling dimension 1 of the dataset union centroids. Write r(q) = ∥q − x∗ (q)∥ for the nearestneighbor distance of query q, Fr for its CDF over Q, and rδ = Fr−1 (1 − δ) for the (1 − δ)-quantile. Lemma 12 (Cell Intersection ∆ 4(r(q) + DI )/σI .
Bound). ℓ∗ (q, 1)
≤
Proof. Let j ∗ be the cluster containing x∗ (q). By the triangle inequality, ∥q − µj ∗ ∥ ≤ r(q) + DI , so µj ∗ ∈ B(q, r(q) + DI ). Every centroid ranked before µj ∗ also lies in this ball, so ℓ∗ (q, 1) is at most the number of centroids in B(q, r(q)+DI ). Since centroids are pairwise separated by ≥ σI , the balls {B(µj , σI /2)} are disjoint and contained in B(q, r(q) + DI + σI /2). By the doubling-dimension packing property [34], a ball of radius R contains at most (2R/ρ)∆ points with pairwise distance ≥ ρ. Setting R = r(q) + DI + σI /2 and ρ = σI gives ℓ∗ (q, 1) ≤ (2(r(q) + DI )/σI + 1)∆ ≤ (4(r(q) + DI )/σI )∆ when r(q) + DI ≥ σI /2. The ratio (r(q) + DI )/σI captures geometric query difficulty: queries far from their nearest neighbor or in poorly separated partitions require more probes. This bound is tight up to constants: by definition of doubling dimension, there exist point configurations where Θ((R/ρ)∆ ) points with pairwise separation ≥ ρ fit in a ball of radius R [34], so the upper bound is achievable. Note that ℓ∗ (q, 1) bounds the probes needed to retrieve the single nearest neighbor; for k-NN recall at target r∗ , the bound is conservative since achieving partial recall is strictly easier. Proposition 13 (Fixed Probe Requirement). A fixed-ℓ policy achieves recall ≥ 1 − δ when ∆ 4(rδ + DI ) ℓ ≥ ℓfix (δ) := . (10) σI Proof. By Lemma 12, r(q) ≤ σ4I ℓ1/∆ −DI implies ℓ∗ (q, 1) ≤ ℓ. Setting this threshold ≥ rδ gives (10). This is the cost every query pays under fixed probing — including easy queries with r(q) ≪ rδ that would succeed with far fewer probes. We now bound what QASP pays instead. Let ℓ̂(q) = gQASP (q, r∗ ) be QASP’s predicted probe count. Define the failure rate ε = Pr[ℓ̂(q) < ℓ∗ (q, r∗ )] and the overshoot η̄ = E[ℓ̂(q) − ℓ∗ (q, r∗ ) | ℓ̂(q) ≥ ℓ∗ (q, r∗ )]. The failure rate ε is the probability QASP under-probes (missing the recall target); the overshoot η̄ is the average wasted probes when it succeeds. Proposition 14 (QASP Expected Probes). E[ℓ̂(q)] ≤ E[Λ] + η̄ + ε · L. Proof. Condition on success (ℓ̂ ≥ ℓ∗ ) and failure (ℓ̂ < ℓ∗ ): E[ℓ̂] = (1 − ε)(E[ℓ∗ | success] + η̄) + ε E[ℓ̂ | failure]. Since 1 The smallest integer such that every ball of radius r is covered by 2∆
balls of radius r/2.
Fig. 2: Expected probes vs. recall target for fixed probing (black) and QASP (gray) under three NN distance distributions (∆ = 5, L = 1000, η̄ = 2, ε = δ). The vertical gap between matched curves is the data access savings from adaptive probing. QASP benefits most when Fr has a heavy tail (exponential, uniform) and at high recall targets, where fixed probing must provision for the worst-case quantile rδ . (1 − ε)E[ℓ∗ | success] ≤ E[Λ], (1 − ε)η̄ ≤ η̄, and E[ℓ̂ | failure] ≤ L (a worst-case bound; in practice failure queries cost far less than L probes), the bound follows. Corollary 15 (Dominance Condition). At matched recall (ε = δ), QASP has strictly lower expected data access than fixed probing whenever ∆ 4(rδ + DI ) η̄ + ε · L < (11) − E[Λ] . | {z } σI {z } | predictor overhead tail waste of fixed probing
Combining Propositions 13 and 14 yields the main result. The left side is the total cost of predictor imperfection: wasted probes from over-prediction (η̄) plus the penalty from underprediction failures (εL). The right side is the tail waste: the gap between the fixed probe count (driven by the hardest queries via rδ ) and the average difficulty E[Λ]. This gap grows as the ∆-th power of the ratio between worst-case and average query difficulty. QASP dominates whenever the predictor is “good enough” relative to this heterogeneity; conversely, when Fr is concentrated, all queries are equally hard and adaptive probing offers no advantage. Figure 2 illustrates the dominance condition under three NN distance distributions: the gap between fixed and QASP curves at any recall target represents data access savings, largest for heavy-tailed distributions at high recall and vanishing for concentrated distributions. Note that we do not model εL and η̄ as functions of the recall target, which in practice influences predictor performance. V. R ELATED W ORK QASP targets partitioning-based indexing, the most comprehensive class of vector search methods, which partition the space for pruning and scale to distributed architectures.
These include clustering and IVF (Inverted File Index) [5], [9]–[12], multi-dimensional space trees [34]–[37], and vector quantization [10], [11], [38] which uses clustering at its core. Partitioning-based indices achieve sublinear scaling [8], making them the preferred choice for large vector databases due to their parallelizability and resource efficiency. Partitioning also underpins distributed search architectures to distribute vectors across storage units or processors [13]–[16]. Vector search libraries predominantly relied on static empirical parameter settings and target average recall without adapting to query difficulty. These include defaulting to nprobe = 8 (number of clusters to search), recommending proportional scaling with nlist (total number of clusters) and experimental tuning [39]; setting nprobe to cover 5–10% of the dataset [1]; √ √ setting nlist based on dataset size (4 · N to 16 · N ) with limited nprobe guidance [2] and testing multiple values (1, 4, 16, 64, 256) [40]. SPANN [12] and SQUASH [16] use thresholds to decide which clusters to search. Popular graph-based methods [41] constrain the candidate list size at query time, traditionally fixed for all queries. Recent methods [4], [20], [42] set this parameter per query through either statistical scoring or reactive early termination. Statistical scoring offers lightweight runtime adaptation but requires distributional assumptions that may not hold across diverse workloads. Reactive early termination provides flexible stopping criteria but periodically invokes models during traversal, introducing per-step inference overhead that limits model capacity. These methods target graph indices. For IVF indices, PCE-Net [43] predicts a single nprobe per query, coupling the prediction to a specific recall target and resulting in higher variance and data access (Section VI-D). QASP instead learns fine-grained recall contributions over partitions proactively through a single upfront inference. This enables richer architectures and generalization across recall targets, with significant improvements also demonstrated experimentally. VI. P ERFORMANCE E VALUATION A. Experimental Setup All experiments are performed on Intel(R) Xeon(R) Platinum 8175M CPU @ 2.50GHz & 96 CPU cores. We use Python 3.10 with Pytorch 1.13 for deep-learning and scikitlearn 1.2.2 for gradient boosting, regression and kmeans++. 1) Vector Datasets: We build QASP on seven datasets from a range of vector spaces, distance measures and application domains. SIFT1M [44], 1 million 128-dimensional SIFT image descriptors; MNIST [45], 60k 784-dimensional vectors trained on handwritten digits; GIST1M [46], 1 million 960dimensional global color GIST descriptors. DEEP1B 10M, 10 million subset of Deep1B [47] with 96-dimensional deep learning embeddings; GLOVE-200 [48], 1.2 million 200dimensional word embeddings trained on Wikipedia; COCOI2I [49], 113k 512-dimensional vectors for image-to-image retrieval; COCO-T2I [49], 113k 512-dimension vectors for text-to-image retrieval. Each dataset has a Query Set with 100 true neighbors from exact search.
2) Training, Validation and Test Sets: We use a random sample of min(1000, ⌊|Query Set|/10⌋) queries for generating offline training and validation sets. Model features, as discussed in section III, are obtained per query and centroid rank by searching up to min(300, ⌊0.3L⌋) probes. Ground truth is used to obtain recall target labels. The offline dataset is split 80:20 for training and validation. For testing, 1000 queries are sampled from the remaining query set and features are obtained on-the-fly during search. See Section VII for model performance and fit analysis. 3) Model Details: Deep Learning (DL) neural architecture of QASP, called QASP-DL, contains 3 hidden layers with hidden dimension of 18 with ReLU activation [50]. Each input feature is projected on a 4-dim learnable embeddings space following tabular learning using DL [18]. We use batch normalization on input embeddings and dropout with rate 0.1 for regularization. Each DL model is trained for 100 epochs with a constant learning rate of 5e-3 and batch size of 512, though convergence is observed much earlier. The best model is selected using held-out validation set performance. Gradient boosting decision tree (GBDT) model variant of QASP, called QASP-GBDT, is trained using 100 trees with a maximum depth of 3 and a learning rate of 0.1. Polynomial variant of QASP, called QASP-LITE, is a lightweight and easy to adopt alternative in production environment, is fitted using Lasso regression with α=1e-5 on sklearn PolynomialFeatures processing with degree 3. Latency and Throughput - The DL model has a modest parameter count of 1513 trainable parameters and a total memory footprint of just 6-7 KB, making it practical for deployment even in memory-constrained environments. For DL model, mean latency on CPU with batch size 32 is 0.26 ms/batch, throughput 124K queries/sec and P99 latency 0.33 ms using 4 threads. For GBDT, mean latency on CPU with batch size 32 is 0.199 ms/batch, throughput 161K queries/sec and P99 latency 0.55 ms. For QASP-LITE, mean latency on CPU with batch size 32 is 0.06 ms/batch, throughput 524K queries/sec and P99 latency 0.09 ms. All measurement is over 100 runs with 10 warm-up iterations. 4) Index Details:√ We first build flat IVF indices with nlist as scalar × n where n is the base size and use three scalar values [0.5, 1, 4] to span across different index configurations per dataset. Distance metrics is either Squared Euclidean or Cosine Distance depending on the dataset and the clustering algorithm used is k-means++ [51]. We also build a hierarchical index using two-level kmeans clustering for scaling experiments to larger datasets of size (> 10M √ M ). Each level of the index is clustered using fixed nlist as 3 n that gives equal sized partitions ideal for disk-based experiments. B. Query Variability-Aware Evaluation The traditional method for evaluating vector similarity search results is to measure the deviation of observed average recallPfrom recall target. Given observed average recall, 1 r̄ = |Q| q∈Q r(q), where r(q) is the observed recall for query q and recall target r∗ , traditional evaluation concerns
TABLE I: Comparison of QASP-DL and Oracle Nprobe policy across three recall targets. Oracle Nprobe achieves recall target by over-reading in the 50% Easy split and under-reading in the 50% Hard split, while QASP optimizes search on both splits. We highlight r̄ with large deviation from r∗ in red otherwise in teal, while best average QVE metrics are emboldened when r̄ ≈ r∗ . These results empirically validate Corollary 15 where A% improvements are better at higher recall targets. Dataset AVERAGE 50% EASY 50% HARD
r∗ = 90%
Search Policy Oracle Nprobe QASP-DL Oracle Nprobe QASP-DL Oracle Nprobe QASP-DL
r∗ = 95%
r̄
σ2 ↓
δ↓
S% ↑
A% ↓
89.87 90.97 96.57 91.61 83.26 90.49
142.71 60.37 25.79 63.97 167.28 52.06
9.39 6.23 7.89 6.68 10.82 5.71
72.61 79.95 94.51 81.06 51.77 79.37
3.92 3.98 4.11 1.83 3.75 6.03
r∗ = 99%
r̄
σ2 ↓
δ↓
S% ↑
A% ↓
94.93 95.12 98.63 95.41 91.31 94.84
53.12 25.62 6.35 29.15 71.26 20.25
5.32 3.80 4.23 4.07 6.38 3.50
80.89 85.17 97.37 85.66 64.83 84.83
7.08 6.02 7.35 2.71 6.82 9.17
only with |r̄−r∗ |. While useful as a summary statistic, it masks performance variations across queries and fails to capture user experience consistency. To address this shortcoming, we propose a comprehensive Query Variability-aware Evaluation (QVE) framework with the following metrics to compare query variability even when r̄ ≈ r∗ between search policies. P 1 2 2 • Recall Variance: σ = |Q| q∈Q (r(q) − r̄) - Measures variance of the observed recall across test queries. P 1 ∗ • Absolute Query Deviation: δ = q∈Q |r(q) − r | |Q| Measures mean of absolute deviation from recall target. |{q∈Q:r(q)≥r ∗ }| • Query Satisfaction Rate: S% = 100 × |Q| % of queries satisfied by the search policy, i.e. achieve at least recall r∗ . Since exact r∗ per query is rarely useful, we subtract a small margin (5%) from r∗ to relax the criteria. P 100 • % Data Accessed: A% = q∈Q |{v ∈ D : |Q×D| d(v, q) is calculated}|, % of data accessed. C. QASP versus Oracle Fixed Policy We first compare QASP to policies that search a fixed number of probes, which are industry standard where several open source libraries like Faiss [2], Milvus [39], and OpenSearch [3] recommend tuning nprobe parameter for IVF for a given dataset and query workload. To simplify comparison, we obtain the best fixed policy, called Oracle Nprobe, which is the smallest nprobe that results in r̄ ≈ r∗ . The Oracle Nprobe policy represents a theoretical upper bound of what fixed policies can achieve and thus is a strong baseline to QASP. We obtain Oracle Nprobe from the same training dataset used for training QASP models. See Table I contains comparison results averaged across the seven datasets. Both Oracle Nprobe and QASP achieve similar r̄’s close to the target. However, 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%. As r∗ increases, QASP accesses much fewer data than Oracle Nprobe to achieve the same recall without lowering satisfaction rate. To further understand this behavior, we split the test dataset into two halves - 50% EASY and 50% HARD, using Local Relative Contrast feature. We observe that Oracle Nprobe consistently over-reads in the 50% EASY set and under-reads in the 50% HARD set. QASP, being query adaptive, does the opposite by
r̄
σ2 ↓
δ↓
S% ↑
A% ↓
98.93 98.60 99.66 98.74 98.27 98.46
4.49 4.19 0.50 4.23 6.73 3.49
1.21 1.26 0.85 1.19 1.53 1.27
95.85 95.07 99.71 95.54 92.29 94.74
18.64 12.23 19.06 6.56 18.24 17.82
reading less in the 50% EASY set and more in the 50% HARD set as intended. D. Baselines We extend our comparison to proactive baselines from popular vector search libraries and prior work. Several libraries recommend tuning nprobe parameter for IVF [2], [3], [39] for which we use Oracle Nprobe. LanceDB [1] suggests searching for a fixed % of vectors for which we obtain Oracle Access % from training dataset. SPANN [12] is a popular clustering index with query-aware pruning that searches until cluster rank j such that Dist(q, cj ) ≤ (1 + ϵ) × Dist(q, c1 ). SQUASH [16] also involves a scalar multiple on distance to create a search mask. We obtain Oracle Distance Multiplier to represent these methods. Vexless [14] uses a threshold on absolute distance, for which we derive Oracle Distance. PCENet [43] is a learned baseline that predicts a single nprobe per query using neural encoders over the query vector and centroid distance distribution; we evaluate them on the same IVF index for a fair comparison of the probing approaches. Table II contains comparative results across the seven datasets. First, we observe that all the oracle baselines can be tuned to achieve r̄ ≈ r∗ except Oracle Distance [14]. PCENet achieves high recall but at a steep cost: it reads 14.8% of data—more than twice QASP-DL’s 6.0%—as its asymmetric loss incentivizes over-probing. Its variance (σ 2 = 69.8) and deviation (δ = 5.6) also exceed all QASP variants. QASP consistently outperforms all baselines on QVE metrics while achieving recall target, satisfying more queries and accessing fewer vectors. We split test queries into easy and hard. We observe that fixed policies like Oracle Nprobe and Oracle Access% over-read by 4.3% for easy queries and underread by 2.3% for hard queries. Oracle Distance Multiplier is more adaptive; reading less in easy queries and more in hard queries. However, when compared to QASP models this policy had 176% higher variance. PCE-Net [43], which predicts per query nprobe, exhibits an inverted pattern: it over-reads on hard queries (r̄ = 97.7) and under-reads on easy queries (r̄ = 93.5). PCE-Net achieves recall target at higher variance and deviation compared to fixed policies like Oracle Nprobe and Oracle Access%. Moreover, while it achieves a higher S% than QASP, it achieves so by accessing ≈ 1.5× more than QASP-DL with A% = 14.78, highest among all methods.
TABLE II: Comparison of QASP to proactive baselines at recall target 95%. QASP outperforms Oracle policies averaged over seven datasets. QASP-DL outperforms other variants. Dataset AVERAGE
50% EASY
50% HARD
AVERAGE 50% EASY 50% HARD
r∗ = 95%
Search Policy r̄
σ2 ↓
δ↓
S% ↑
A% ↓
Oracle Nprobe [2], [3], [39] Oracle Access % [1] Oracle Distance Multiplier [12], [16] Oracle Distance [14] PCE-Net [43] Oracle Nprobe [2], [3], [39] Oracle Access % [1] Oracle Distance Multiplier [12], [16] Oracle Distance [14] PCE-Net [43] Oracle Nprobe [2], [3], [39] Oracle Access % [1] Oracle Distance Multiplier [12], [16] Oracle Distance [14] PCE-Net [43]
94.90 94.84 94.60 92.40 95.63 98.63 98.33 92.50 98.70 93.49 91.31 91.36 96.70 86.29 97.69
53.57 53.16 70.72 302.94 69.76 6.35 8.67 104.25 28.50 88.92 71.26 73.15 27.53 482.88 50.60
5.34 5.30 5.32 9.07 5.55 4.23 4.21 6.52 4.96 5.99 6.38 6.42 4.20 12.99 5.11
80.72 80.14 82.83 82.13 87.09 97.37 96.14 74.66 97.11 79.69 64.83 64.26 91.46 67.34 94.49
7.08 6.90 9.21 14.69 14.78 7.35 6.89 2.56 17.27 15.22 6.82 6.90 15.53 12.09 14.33
QASP-DL QASP-GBDT QASP-LITE QASP-DL QASP-GBDT QASP-LITE QASP-DL QASP-GBDT QASP-LITE
95.12 95.09 95.43 95.41 95.51 95.00 94.84 94.67 95.89
25.62 27.51 34.95 29.15 28.92 44.46 20.25 25.13 20.97
3.80 3.89 4.16 4.07 4.08 4.68 3.50 3.71 3.57
85.17 84.95 86.58 85.66 86.49 83.54 84.83 83.23 89.49
6.02 6.31 7.33 2.71 2.68 3.17 9.17 9.90 11.46
E. Deployment Efficiency Figure 3 evaluates QASP’s deployment efficiency in both in-memory and disk-based scenarios. We also include Oracle Nprobe which yields the most competitive latency and recall variance among all baselines (though still much higher than QASP, cf. Table I). For in-memory deployment, we measure total runtime (milliseconds) required to satisfy 95% of queries. QASP involves a single inference plus search time, while Oracle Nprobe only incurs search time. QASP-DL’s marginal inference overhead (∼1.5 ms/query) becomes proportionally smaller at higher recall targets and with larger datasets, as search time increases while inference time remains constant. We observe diminishing recall returns at higher recalls with Oracle Nprobe compared to QASP models, eventually offsetting inference cost. QASP-DL achieves significant gains for larger datasets (>10M) where the fixed inference cost is offset by more efficient search, as also shown in Section VI-H. For disk-based settings, QASP’s benefits are even more pronounced as I/O costs dominate search time. The single inference becomes negligible compared to I/O costs, and
QASP directly reduces disk operations. QASP variants consistently read 20-40% less data than Oracle Nprobe across all recall levels, with this efficiency gap widening as recall targets increase (Figure 3). This behavior is supported by the theoretical dominance condition illustrated in Figure 2. F. Domain Adaptation 1) Cross-Dataset Generalization: We evaluate QASP’s generalization to unseen datasets using two QVE metrics (r̄ and δ) under two transfer settings: zero-shot (direct application) and few-shot (fine-tuning with 1% of target data; see Section II-D2). As shown in Table III, QASP-DL often generalizes well zero-shot—e.g., GIST1M→SIFT1M achieves r̄ = 98.60 without tuning. Where gaps exist (e.g., SIFT1M→GIST1M), few-shot fine-tuning with minimal data closes them effectively. Training on diverse sources further helps: a model trained on SIFT1M+MNIST combined outperforms individual models on GIST1M in the zero-shot setting. TABLE III: Cross-dataset generalization of QASP for recall target 95%. QASP-DL models generalize well under zeroshot and achieve recall close to target, while few-shot training bridges the gap on average with fully trained. QASP models can be fine-tuned with just 1% queries from target domain. Source
Target
GIST1M MNIST SIFT1M SIFT1M + MNIST COCOI2I GLOVE200 AVERAGE
SIFT1M GIST1M GIST1M GIST1M GLOVE200 COCOI2I -
Zero-Shot r̄ δ↓ 98.60 95.50 26.80 93.70 93.10 91.80 83.25
4.01 3.97 68.22 4.57 5.52 6.30 15.76
Few-Shot r̄ δ↓ 93.70 92.00 92.90 94.60 94.90 96.80 94.15
4.23 5.09 4.36 3.87 3.84 3.63 4.17
Fully Trained r̄ δ↓ 95.47 92.30 92.30 92.30 95.23 95.83 93.91
3.44 4.56 4.56 4.56 3.46 3.98 4.09
2) Cross-Index Configuration Generalization: We investigate the robustness of QASP models to varying index configurations by testing how well they perform on the same dataset but with a different number of clusters L. As observed in Table IV, QASP-DL models generalize well on unseen index configurations without fine-tuning. Domain adaptation methods remain applicable where few-shot learning can bridge the gap. However, zero-shot application of QASP models to unseen indices produces competitive performance on average. TABLE IV: Cross-index generalization of QASP on QVE metrics for recall target = 95%. QASP models trained on one index configuration (source) generalize well zero-shot to unseen configurations (target) reducing the need of fine-tuning.
(a) In-Memory
(b) Disk-Based
Fig. 3: Search time (ms) vs. recall (in-memory) and data accessed vs. recall (disk-based). QASP achieves recall target with less search cost than Oracle Nprobe and PCE-Net, with gains further widening at higher recall targets. Legend: QASPDL, QASP-GBDT, QASP-LITE, Oracle Nprobe, PCE-Net
Dataset
Source Config
Target Config
SIFT1M SIFT1M GIST1M GIST1M COCOI2I COCOI2I GLOVE200 GLOVE200 AVERAGE
IVF(L=1000) IVF(L=4000) IVF(L=1000) IVF(L=4000) IVF(L=336) IVF(L=1346) IVF(L=1087) IVF(L=4531) -
IVF(L=4000) IVF(L=1000) IVF(L=4000) IVF(L=1000) IVF(L=1346) IVF(L=336) IVF(L=4531) IVF(L=1087) -
Zero-Shot r̄ δ↓ 85.00 96.30 91.50 92.30 87.80 97.20 94.70 95.10 93.84
10.83 3.30 5.17 4.56 9.28 3.74 3.79 3.59 4.78
Fully Trained r̄ δ↓ 93.50 95.47 91.40 92.30 95.10 95.83 94.70 95.23 94.29
4.08 3.44 5.17 4.56 4.08 3.98 3.79 3.46 4.07
Algorithm 1 Reactive Adaptive Search for a Single Query
G. Reactive Complement We evaluate the performance of QASP’s reactive complement described in Section II-E, which guides policy behavior at search. See Algorithm 1 for the psuedocode of the reactive complement policy based on observed discovery rates. The implementation parameters include a smoothing factor α = 0.3, Lδ = 3 and a threshold of 0.25 on δi to capture positive and negative rates. For baselines, we use LAET [4] which pauses search at a fixed nprobe and predicts when to stop and DARTH [20] which predicts recall at regular intervals to terminate the search early. We tune LAET’s multiplier parameter to attain recall target of 95%. For DARTH, we set mpi and ipi parameters using recommended defaults from training statistics. For a fair comparison, we train DARTH models for k = 100 and test on unseen queries and search parameters. Table V shows results when all mechanisms are applied on the same IVF index. Both QASP and QASP + Reactive consistently outperform LAET and DARTH on all three datasets with QASP + Reactive further boosting QASP performance. TABLE V: Comparison of QASP to reactive baselines at recall target 95%. QASP outperforms both baselines and reactive complement improves QVE metrics at higher average recall. Dataset SIFT1M
GIST1M
DEEP1B 10M
AVERAGE
r∗ = 95%
Search Policy r̄
σ2 ↓
δ↓
S% ↑
A% ↓
LAET [4] DARTH [20] QASP-DL QASP + Reactive LAET [4] DARTH [20] QASP-DL QASP + Reactive LAET [4] DARTH [20] QASP-DL QASP + Reactive
95.44 94.20 95.47 95.78 94.91 91.94 92.30 94.61 94.83 95.81 95.20 95.83
78.74 29.45 19.64 17.23 117.41 47.14 34.57 24.85 42.98 27.15 27.20 20.91
5.59 4.13 3.44 3.36 5.54 5.51 4.56 3.85 4.86 4.23 3.84 3.64
86.2 79.5 87.77 89.97 86.5 65.7 68.50 80.6 80.53 85.8 85.47 87.97
4.14 3.19 2.76 2.83 10.42 9.39 6.12 7.64 0.87 1.35 0.91 0.94
LAET [4] DARTH [20] QASP-DL QASP + Reactive
95.06 93.98 94.32 95.41
79.71 34.58 27.14 21.00
5.33 4.62 3.95 3.62
84.41 77.00 80.58 86.18
5.23 4.64 3.26 3.80
Require: Query q, nearest cluster ordering Cq , planned probes P , recall target r∗ |Cq | from QASP model Require: Recall estimates {r̂i }i=1 Require: Constants: ϵ (margin of error), δ (deviation threshold), α (smoothing factor), Lδ (consecutive deviation limit) Ensure: Top-k results and actual probes used 1: Pmin ← max(1, ⌊P (1 − ϵ)⌋ − Lδ ) 2: Pmax ← min(|Cq |, ⌈P (1 + ϵ)⌉ − Lδ ) 3: Initialize smoothed discovery rate SDR ← 0 4: Initialize counters c− ← 0, c+ ← 0 5: Initialize previous neighbors set Rprev ← ∅ 6: for p = Pmin to Pmax do 7: Rp ← S EARCH O NE C LUSTER(q, Cqp , Rprev ) 8: if p = Pmin then ▷ Skip comparison for first probe 9: Rprev ← Rp 10: continue 11: end if 12: DRp ← |Rp \ Rprev |/k ▷ True discovery rate f p ← max(1e−3 , r̂p − r̂p−1 ) 13: DR ▷ Estimated discovery rate 14: SDR ← α · DRp + (1 − α) · SDR f p )/DR fp 15: ∆p ← (SDR − DR 16: if ∆p < −δ then 17: c− ← c− + 1, c+ ← 0 ▷ Negative discovery 18: else if ∆p > δ then 19: c+ ← c+ + 1, c− ← 0 ▷ Positive discovery 20: else 21: c− , c+ ← 0 22: end if 23: if c− ≥ Lδ and r̂p ≥ r ∗ (1 − ϵ) then 24: break ▷ Over-search detected 25: end if 26: if p = P and c− = 0 and c+ = 0 then 27: break ▷ Consistent with estimation 28: end if 29: Rprev ← Rp 30: end for 31: return Rp
H. Scaling to Hierarchical Index We evaluate hierarchical scaling (Section II-D3) by applying a QASP-DL model trained on Deep1B-10M to larger subsets of both SIFT1B and Deep1B (10M–100M). For each subset, we√construct a two-level index with nlist1 = nlist2 = 3 n, yielding balanced partitions suitable for disk-based search. We compare against Oracle Nprobe, which optimizes nprobe1 via binary search with nprobe2=nlist2. QASP operates level-wise, predicting adaptive nprobe1 from firstlevel features and selectively probing second-level partitions based on predicted recall contribution. As shown in Figure 4, this reduces data access by ≥80% at 99% recall consistently across both datasets (SIFT1B: 82–87%, Deep1B: 80–84%), demonstrating that QASP’s efficiency gains generalize across data distributions and scale without retraining.
VII. R EGRESSION F IT A NALYSIS A. Training Error Analysis Figure 5 presents training error curves for three diverse datasets. All models converge rapidly, with most error reduction occurring within the first 20–30 epochs. Training and validation curves follow similar trajectories with minimal gaps, indicating good generalization without overfitting. Datasetspecific differences in convergence speed and final error levels reflect the varying complexity of the recall prediction task. Overall, QASP trains efficiently across diverse datasets, enabling rapid adaptation to new index configurations and query distributions in practice.
TABLE VI: Comparison of model fit across all feature ablations for Euclidean and Angular datasets on validation set. Feature Set ALL ALL \ Cumulative Cluster Size ALL \ Relative Distance ALL \ Local Relative Contrast ALL \ Cluster Coeff. of Variance ALL \ ∆(Relative Distance) ALL \ Data Size ALL \ ∆(Cumulative Cluster Size) ALL \ Rank ALL \ Maximum Cluster Distance
Fig. 4: A% for SIFT1B and Deep1B subsets (10M–100M) on a two-level hierarchical index at 99% recall target. QASP is trained on a 10M subset and applied at inference without retraining. QASP consistently yields ≥80% reduction in A%.
(a) MNIST
(b) GIST
(c) SIFT1M
(e) DEEP1B 10M (f) COCOI2I
(d) GLOVE200
Euclidean Dataset MSE ↓ R2 ↑ 0.00186 0.87123 0.00193 0.86634 0.00246 0.82950 0.00188 0.86954 0.00192 0.86678 0.00191 0.86783 0.00188 0.86990 0.00186 0.87096 0.00186 0.87094 0.00187 0.87078
Angular Dataset MSE ↓ R2 ↑ 0.00409 0.82741 0.00417 0.82387 0.00454 0.80837 0.00432 0.81743 0.00413 0.82565 0.00419 0.82296 0.00415 0.82464 0.00410 0.82686 0.00416 0.82444 0.00416 0.82407
model. Cumulative cluster size and relative distance contribute most to positive recall predictions for both Euclidean and Angular datasets, though with high variance—expected since large cluster sizes and relative distances do not guarantee high recall for extremely hard queries. Feature ablation results (Table VI) confirm that cumulative cluster size, relative distance, and local relative contrast are important across both dataset categories, while features such as jump in relative distance are more influential for angular datasets.
(g) COCOT2I
Fig. 5: Training loss (MSE) over epochs Fig. 7: Feature importance analysis. Left: Euclidean datasets. Right: Angular datasets.
B. Prediction Error Analysis Figure 6 shows actual versus predicted recall for DL and GBDT models (we omit Lite for brevity). Both models achieve MSE of 0.002 and similar R2 with DL slightly better. Errors are balanced around the diagonal with a slight bias toward over-prediction—preferable for meeting recall targets. Prediction accuracy remains high across the entire recall range.
(a) SIFT1M(G) (b) SIFT1M(D) (c) MNIST(G) (d) MNIST(D)
(e) GIST(G)
(f) GIST(D)
(g) DEEP10M(G)
(h) DEEP10M(D)
Fig. 6: Prediction error analysis showing actual vs. predicted recall between GBDT (G) and DL (D) recall predictor models. C. Feature Studies We fix a set of nine features (Fig.7) and analyze their contributions using SHAP values [52] from the QASP-GBDT
VIII. C ONCLUSION We introduced QASP to optimize vector search by predicting the complete recall progression curve per query via a single proactive inference, from which a search policy is derived for any recall target. QASP decouples the policy from specific targets or index configurations and enables domain adaptation with zero-shot or minimal fine-tuning. We provide theoretical guarantees, including that a finite sample suffices for convergence independent of dataset size and dimensionality, and a dominance condition where QASP’s data access savings over fixed policies grow exponentially in intrinsic dimensionality. Our query variability-aware evaluation demonstrates the importance of minimizing recall variance across queries. 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. QASP 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. R EFERENCES [1] LanceDB, “IVF-PQ index,” LanceDB Documentation, https://lancedb. github.io/lancedb/concepts/index ivfpq/#query-the-index.
[24] D. Pollard, “Convergence of stochastic processes,” Springer Series in [2] Facebook AI Research, “Guidelines to choose an index,” Statistics, 1984. FAISS Wiki, https://github.com/facebookresearch/faiss/wiki/ Guidelines-to-choose-an-index. [25] ——, Empirical Processes: Theory and Applications. Institute of Mathematical Statistics, 1990. [3] OpenSearch, “Choose the k-NN algorithm for your billion[26] A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, “Learnscale use case with OpenSearch,” Amazon OpenSearch ability and the vapnik-chervonenkis dimension,” Journal of the ACM Service Blog, 2022, https://aws.amazon.com/blogs/big-data/ choose-the-k-nn-algorithm-for-your-billion-scale-use-case-with-opensearch/. (JACM), vol. 36, no. 4, pp. 929–965, 1989. [27] R. Gupta and T. Roughgarden, “A pac approach to application-specific [4] C. Li, M. Zhang, D. G. Andersen, and Y. He, “Improving approximate algorithm selection,” SIAM Journal on Computing, vol. 46, no. 3, pp. nearest neighbor search through learned adaptive early termination,” in 992–1017, 2017. Proceedings of the 2020 ACM SIGMOD International Conference on [28] M.-F. Balcan, “Data-driven algorithm design,” Beyond Worst Case Management of Data, 2020, pp. 2539–2554. Analysis of Algorithms (Tim Roughgarden, ed.), 2020. [5] J. Mohoney, D. Sarda, M. Tang, S. R. Chowdhury, A. Pacaci, I. F. [29] V. N. Vapnik and A. Y. Chervonenkis, “On the uniform convergence Ilyas, T. Rekatsinas, and S. Venkataraman, “Quake: Adaptive indexing of relative frequencies of events to their probabilities,” in Measures of for vector search,” 2025. complexity: festschrift for alexey chervonenkis. Springer, 2015, pp. [6] Y. Fu, C. Chen, Y. Chen, W.-F. Wong, and B. He, “Vista: Vector indexing 11–30. and search for large-scale imbalanced datasets,” in 2025 IEEE 41st [30] M. Anthony and P. L. Bartlett, Neural network learning: Theoretical International Conference on Data Engineering (ICDE), 2025, pp. 543– foundations. Cambridge University Press, 2009. 556. [31] P. L. Bartlett and W. Maass, “Vapnik-chervonenkis dimension of neural [7] H. Wang, W. Wu, C. Luo, A. Bian, C. Meng, Y. Wu, and J. Sun, nets,” The handbook of brain theory and neural networks, pp. 1188– “Boosting accuracy and efficiency for vector retrieval with local scaling 1192, 2003. graph,” in 2025 IEEE 41st International Conference on Data Engineer[32] P. W. Goldberg and M. R. Jerrum, “Bounding the vapnik-chervonenkis ing (ICDE), 2025, pp. 336–348. dimension of concept classes parameterized by real numbers,” Machine [8] P. Sun, F. Chern, Y. Akhremtsev, R. Guo, D. Simcha, and S. Kumar, Learning, vol. 18, no. 2-3, pp. 131–148, 1995. “Scaling laws for nearest neighbor search,” in The 1st Workshop on [33] M. Karpinski and A. Macintyre, “Polynomial bounds for vc dimension Vector Databases, 2025. of sigmoidal and general pfaffian neural networks,” Journal of Computer [9] H. Ferhatosmanoglu, E. Tuncel, D. Agrawal, and A. El Abbadi, “Apand System Sciences, vol. 54, no. 1, pp. 169–176, 1997. proximate nearest neighbor searching in multimedia databases,” in Pro[34] A. Beygelzimer, S. M. Kakade, and J. Langford, “Cover trees for ceedings 17th International Conference on Data Engineering (ICDE). nearest neighbor,” in Proceedings of the 23rd International Conference IEEE, 2001, pp. 503–511. on Machine Learning (ICML). ACM, 2006, pp. 97–104. [10] E. Tuncel, H. Ferhatosmanoglu, and K. Rose, “Vq-index: An index struc[35] J. L. Bentley, “Multidimensional binary search trees used for associative ture for similarity searching in multimedia databases,” in Proceedings searching,” Communications of the ACM, vol. 18, no. 9, pp. 509–517, of the 10th ACM International Conference on Multimedia, 2002, pp. 1975. 543–552. [36] S. M. Omohundro, “Five balltree construction algorithms,” International [11] H. Jegou, M. Douze, and C. Schmid, “Product quantization for nearest Computer Science Institute Berkeley, 1989. neighbor search,” IEEE Transactions on Pattern Analysis and Machine [37] P. Zezula, P. Savino, G. Amato, and F. Rabitti, “Approximate similarity Intelligence, vol. 33, no. 1, pp. 117–128, 2010. retrieval with m-trees,” The VLDB Journal, vol. 7, no. 4, pp. 275–293, [12] Q. Chen, B. Wang, Y. Guo, Y. Zheng, Y. Li, X. Chang, E. Y. Sun, 1998. J. Zhang, X. Li, and X. Zhang, “Spann: Highly-efficient billion-scale [38] H. Ferhatosmanoglu, E. Tuncel, D. Agrawal, and A. El Abbadi, “Vectorapproximate nearest neighbor search,” in Advances in Neural Informaapproximation based indexing for non-uniform high dimensional data tion Processing Systems, vol. 34, 2021, pp. 10 337–10 349. sets,” Proceedings of the 9th International Conference on Information [13] M. D. Manohar, Z. Shen, G. Blelloch, L. Dhulipala, Y. Gu, H. V. and Knowledge Management (CIKM), pp. 202–209, 2000. Simhadri, and Y. Sun, “Parlayann: Scalable and deterministic parallel [39] Milvus, “Configure index parameters,” Milvus Documentation v2.3.0, graph-based approximate nearest neighbor search algorithms,” in Pro2023, https://milvus.io/docs/v2.3.0/index.md. ceedings of the 29th ACM SIGPLAN Annual Symposium on Principles [40] Facebook AI Research, “Autotune example,” FAISS Source Code, https: and Practice of Parallel Programming, 2024, pp. 270–285. //github.com/facebookresearch/faiss/blob/main/tutorial/cpp/4-GPU.cpp. [14] Y. Su, Y. Sun, M. Zhang, and J. Wang, “Vexless: A serverless vector data [41] Y. A. Malkov and D. A. Yashunin, “Efficient and robust approximanagement system using cloud functions,” Proceedings of the ACM on mate nearest neighbor search using hierarchical navigable small world Management of Data, vol. 2, no. 3, pp. 1–26, 2024. graphs,” IEEE Transactions on Pattern Analysis and Machine Intelli[15] S. Jayaram Subramanya, F. Devvrit, H. V. Simhadri, R. Krishnawamy, gence, vol. 42, no. 4, pp. 824–836, 2018. and R. Kadekodi, “Diskann: Fast accurate billion-point nearest neighbor [42] C. Zhang and R. J. Miller, “Distribution-aware exploration for adaptive search on a single node,” Advances in Neural Information Processing HNSW search,” Proceedings of the ACM on Management of Data, vol. 4, Systems, vol. 32, 2019. no. 1, 2026. [16] J. Oakley and H. Ferhatosmanoglu, “SQUASH: Serverless and dis[43] B. Zheng, Z. Yue, Q. Hu, X. Yi, X. Luan, C. Xie, X. Zhou, and C. S. tributed quantization-based attributed vector similarity search,” arXiv Jensen, “Learned probing cardinality estimation for high-dimensional preprint arXiv:2502.01528, 2025. approximate NN search,” in 2023 IEEE 39th International Conference [17] F. Pedregosa, F. Bach, and A. Gramfort, “On the consistency of ordinal on Data Engineering (ICDE), 2023, pp. 3209–3221. regression methods,” Journal of Machine Learning Research, vol. 18, [44] D. G. Lowe, “Distinctive image features from scale-invariant keypoints,” no. 55, pp. 1–35, 2017. Int. J. Comput. Vision, vol. 60, no. 2, p. 91–110, Nov. 2004. [18] Y. Gorishniy, I. Rubachev, and A. Babenko, “On embeddings for numer[45] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning ical features in tabular deep learning,” Advances in Neural Information applied to document recognition,” Proceedings of the IEEE, vol. 86, Processing Systems, vol. 35, pp. 24 991–25 004, 2022. no. 11, pp. 2278–2324, 2002. [19] R. Shwartz-Ziv and A. Armon, “Tabular data: Deep learning is not all [46] A. Oliva and A. Torralba, “Modeling the shape of the scene: A holistic you need,” Information Fusion, vol. 81, pp. 84–90, 2022. representation of the spatial envelope,” International journal of computer [20] M. Chatzakis, Y. Papakonstantinou, and T. Palpanas, “Darth: Declaravision, vol. 42, pp. 145–175, 2001. tive recall through early termination for approximate nearest neighbor [47] A. Babenko and V. Lempitsky, “Efficient indexing of billion-scale search,” Proc. ACM Manag. Data, vol. 3, no. 4, Sep. 2025. datasets of deep descriptors,” in Proceedings of the IEEE Conference [21] Y. Li, N. Wang, J. Shi, J. Liu, and X. Hou, “Revisiting batch normalon Computer Vision and Pattern Recognition, 2016, pp. 2055–2063. ization for practical domain adaptation,” 2016. [48] J. Pennington, R. Socher, and C. D. Manning, “Glove: Global vectors [22] M. Aumüller and M. Ceccarello, “The role of local dimensionality meafor word representation,” in Empirical Methods in Natural Language sures in benchmarking nearest neighbor search,” Information Systems, Processing (EMNLP), 2014, pp. 1532–1543. vol. 101, p. 101807, 2021. [49] T.-Y. Lin, M. Maire, S. Belongie, L. Bourdev, R. Girshick, J. Hays, [23] R. Rivest, “On self-organizing sequential search heuristics,” CommuniP. Perona, D. Ramanan, C. L. Zitnick, and P. Dollár, “Microsoft coco: cations of the ACM, vol. 19, no. 2, pp. 63–67, 1976. Common objects in context,” 2015.
[50] A. F. Agarap, “Deep learning using rectified linear units (relu),” 2019. [51] D. Arthur and S. Vassilvitskii, “k-means++: the advantages of careful seeding,” in Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, ser. SODA ’07. USA: Society for Industrial and Applied Mathematics, 2007, p. 1027–1035. [52] S. Lundberg and S.-I. Lee, “A unified approach to interpreting model predictions,” 2017.
IX. AI A SSISTANCE S TATEMENT We used Claude (Anthropic, Opus 4.6) to assist with implementation of the PCE-Net baseline directly from the original paper descriptions as the original implementation was not available. Claude was also used for refining figure aesthetics and layout. All experimental design, theoretical analysis, and scientific content are solely the authors’ work.