QASP: Query-Adaptive Robust Vector Search Policy

Source: arXiv:2607.29606 · Published 2026-07-31 · By Hakan Ferhatosmanoglu, Kushal Kumar, Tal Wagner, Andy Warfield

TL;DR

The paper addresses a core challenge in large-scale vector similarity search: achieving high recall consistently across heterogeneous queries while minimizing computational cost. Existing fixed-parameter policies lead to significant variance in recall and over-probing on easy queries, causing inefficient resource use. The authors propose QASP, a Query-Adaptive robust vector Search Policy that predicts an entire recall progression curve per query using a single supervised regression at query time. This recall curve prediction enables deriving a probe policy for any recall target without iterative model calls or separate predictors for each target, addressing limitations of prior adaptive methods.

QASP leverages scale-invariant, normalized features capturing query difficulty and index structure, allowing effective generalization to new recall targets, index configurations, and datasets, including hierarchical indices. The method includes a lightweight reactive component that monitors observed versus predicted incremental recall during search and dynamically adjusts probing without supplemental inference. Theoretically, the authors prove QASP can be trained to near-optimality with a finite number of queries independent of dataset size and dimensionality, and it outperforms any fixed probe policy by a margin that vanishes as training data grows. Empirically, QASP achieves approximately 57.7% lower recall variance, 33.6% lower deviation from recall targets, and 7.3% higher query satisfaction compared to fixed probing baselines, while reducing data access by up to 80% to achieve 99% recall on large datasets. The paper thus presents a robust, scalable, and transferable approach to optimize vector search performance on a per-query basis.

Key findings

• QASP reduces recall variance by approximately 57.7% compared to fixed-parameter probing policies.
• QASP decreases deviation from recall targets by 33.6%, improving query-level recall consistency.
• QASP achieves 7.3% higher query satisfaction rate (queries meeting recall targets) than baseline fixed policies at similar or lower data access.
• At 99% recall on large hierarchical indices, QASP reduces data access by 80% compared to fixed probe settings.
• Theoretical lower bound shows any fixed probe policy incurs a population loss at least equal to Var(Λ)/L^2, where Λ is query difficulty distribution; QASP's loss approaches this bound up to a vanishing margin with sufficient training data.
• The required training sample size for QASP generalizes independently of dataset size and vector dimensionality, depending only on index cluster count and model complexity.
• Data access savings of QASP over fixed probing grow exponentially with intrinsic dimensionality and query difficulty heterogeneity, quantified via doubling dimension.
• QASP shows effective zero-shot and few-shot domain adaptation across datasets and index configurations without retraining or with minimal fine-tuning.

Threat model

The paper considers the challenge of unpredictable query difficulty from a benign but heterogeneous workload rather than active adversaries. The system must robustly adapt per-query search parameters to maintain recall targets while minimizing computational cost. It assumes no malicious attacker but instead a supervised training scenario with known query distributions and access to exact nearest neighbors to train models. The adversary model is thus a non-adaptive environment posing uncertainty in query hardness rather than an adversary subverting the system.

Methodology — deep read

1. Threat Model & Assumptions: The adversary is implicitly the vector search system subject to heterogeneous query difficulties and index structures. The threat is inefficiency and inconsistent recall caused by static fixed probe parameters. The model assumes supervised access to ground-truth nearest neighbors during training and no adversarial interference during search deployment.

2. Data & Preprocessing: Training data consists of queries sampled from the workload or dataset (Deep1B, SIFT1B, and others). For each query, exhaustive or near-exhaustive search is performed to collect recall values attained when probing increasing numbers of clusters (1 to L). This generates recall progression curves per query as regression targets. Query features (scale-invariant, normalized ratios reflecting dataset size, index partition structure, and query-to-centroid distances) are extracted without additional overhead. The data is split into training, validation, and test sets, enabling evaluation on unseen queries.

3. Architecture & Algorithm: QASP parametrizes a recall predictor function f(q, l), mapping query and number of probes to predicted cumulative recall. Minimizing squared L2 loss over all probe counts per query fits this predictor. From f, a probe policy g[q,r] (minimal number of probes to reach recall r) is derived by thresholding f(q,l) >= r. Three model variants are implemented:

• QASP-DL: Deep neural network with batch normalization and dropout for tabular regression.
• QASP-GBDT: Gradient boosted decision trees, efficient for tabular data.
• QASP-LITE: Polynomial regression baseline. Features include cluster ranks, cluster size statistics, local intrinsic dimensionality, and relative distances normalized for scale invariance.

4. Training Regime: Training optimizes mean squared error between predicted and ground-truth recall curves over probe counts. Training is performed offline on sampled queries using standard optimizers (details not explicit, presumably Adam/gradient boosting frameworks), with batch sizes and epochs tuned by validation error. Pre-search inference amortizes cost. Reactive correction policies apply lightweight EWMA smoothing and statistical tests online during search.

5. Evaluation Protocol: Metrics include recall variance across queries, deviation from recall targets, query satisfaction rate (% queries reaching target recall), and data accessed (number of vectors/clusters probed). Baselines are fixed nprobe settings selected heuristically. Ablations consider feature importance and impact of single-target prediction vs full recall curve. Large-scale datasets (Deep1B, SIFT1B subsets) and hierarchical indices are evaluated. Cross-validation and zero-/few-shot transfer tests evaluate generalization. Theoretical well-founded population loss bounds complement empirical results.

6. Reproducibility: Code release is not explicitly specified. Dataset references are standard benchmarks; label acquisition requires ground-truth nearest neighbors, standard in research. Model architectures and feature engineering are described in detail to enable reproduction. Overall, detailed algorithmic pseudocode and proofs provide theoretical backing and practical guidance.

Concrete Example: Given a query vector, features such as normalized cluster rank, cumulative cluster size, and local intrinsic dimensionality are extracted. A single model inference produces predicted recall values for probes 1 to L (e.g., 0.65 at 10 probes, 0.82 at 20 probes, etc.). For desired recall 0.9, the minimal probe count l with predicted recall >= 0.9 is selected as the search depth. During actual search, observed incremental recall per cluster is monitored against predicted increments; if significant deviation is detected using EWMA smoothing, probing can be stopped early or extended, improving efficiency.

Technical innovations

• Predicting the entire query-specific recall progression curve via a single supervised regression, enabling flexible probe policy derivation for arbitrary recall targets without separate models.
• Design of normalized, scale-invariant features that combine query difficulty and index structural signals, supporting zero-shot and few-shot domain adaptation across indices and datasets.
• A lightweight reactive adjustment mechanism for search depth based on real-time statistical monitoring of predicted versus observed recall increments, requiring no additional model inference.
• Theoretical proofs establishing finite sample training sufficiency independent of dataset size/dimensionality and a population loss gap that vanishes compared to any fixed policy.
• Demonstration that data access savings from adaptive probing grow exponentially with intrinsic dimensionality of data and query difficulty heterogeneity.

Datasets

• Deep1B 10M subset — 10 million vectors — public benchmark derived from Deep1B
• SIFT1B subsets (10M–100M) — up to 100 million vectors — public benchmark
• Deep1B full set (implied in large-scale evaluations) — 1 billion vectors — public benchmark

Baselines vs proposed

• Fixed probe policy (nprobe fixed across queries): Query satisfaction rate at 90% recall = X% vs QASP: X% + 7.3% higher
• Fixed probing: Recall variance = baseline vs QASP: 57.7% lower variance
• Fixed probing: Deviation from recall targets = baseline vs QASP: 33.6% lower deviation
• Fixed probing data access to achieve 99% recall on hierarchical indices = baseline vs QASP: 80% less data access
• Single probe-count prediction model (ordinal regression) results in higher variance and data access than QASP’s full recall curve regression (Table II, Section VI-D)

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.29606.

Fig 1: Comparing fixed and adaptive policies: Query sat-

Fig 2: Expected probes vs. recall target for fixed probing

Fig 3: evaluates QASP’s deployment efficiency in both

Fig 5: presents training error curves for three diverse

Fig 4: A% for SIFT1B and Deep1B subsets (10M–100M)

Fig 6: shows actual versus predicted recall for DL and

Fig 7: Feature importance analysis. Left: Euclidean datasets.

Fig 8 (page 12).

Limitations

• Empirical evaluations rely primarily on standard nearest-neighbor benchmarks; real-world workloads with adversarial query distributions are not tested.
• The reactive component’s effectiveness and overhead in highly dynamic indexing or streaming contexts is not fully explored.
• Model training and feature extraction assume availability of ground-truth nearest neighbors for queries, which may be costly or unavailable in some domains.
• Theoretical guarantees depend on assumptions like bounded doubling dimension and cluster structure that might not hold for all datasets or indexing approaches.
• Details on training hyperparameters, hardware used, and runtime latency for inference are limited, reducing reproducibility clarity.
• No evaluation against adversarial attempts to intentionally exploit adaptive policies or data poisoning.

Open questions / follow-ons

• How does QASP perform under adversarial query patterns designed to exploit its adaptive mechanisms or reactive components?
• Can the framework extend beyond partitioning-based indices to other indexing paradigms such as graph-based approximate nearest neighbor search?
• What are the latency and system-level overhead trade-offs integrating QASP’s model inference and reactive correction in real-time distributed vector search services?
• To what extent can unsupervised or self-supervised methods approximate QASP’s recall predictor without reliance on ground-truth nearest neighbors?

Why it matters for bot defense

Bot-defense and CAPTCHA systems increasingly rely on scalable vector similarity search for risk scoring, user interaction pattern matching, and behavioral biometrics. QASP offers a way to dynamically tune search parameters per query (e.g., user/session vector embedding) to consistently achieve high recall in nearest neighbor retrieval with efficient resource use. This ensures more consistent detection accuracy without unnecessary compute overhead, important in latency-sensitive bot defense scenarios. Moreover, QASP’s domain-adaptive and zero-shot capabilities allow deployment across evolving datasets and model updates without costly retraining, which aligns well with the frequent re-indexing and model refresh cycles common in security applications.

The fine-grained monitoring and reactive adjustment mechanisms can, in principle, improve robustness during bursty or novel bot attack patterns by detecting deviations in recall patterns and adapting search effort in real time. However, given the lack of adversarial robustness evaluation in this work, practitioners would need to complement QASP with adversarially hardened components when applying in hostile CAPTCHA or bot-defense environments. Overall, QASP’s theoretical and practical advances provide a promising foundation for performance predictability and efficiency in large-scale similarity search components central to modern bot detection and CAPTCHA learning architectures.

Cite

@article{arxiv2607_29606,
  title={ QASP: Query-Adaptive Robust Vector Search Policy },
  author={ Hakan Ferhatosmanoglu and Kushal Kumar and Tal Wagner and Andy Warfield },
  journal={arXiv preprint arXiv:2607.29606},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.29606}
}

Read the full paper

• arXiv:2607.29606 (abstract)
• arXiv:2607.29606 (PDF)