Source-linked AI summary
VADER: Filtered Vector Search with Declarative Recall
Manos Chatzakis, Duo Lu, Helena Caminal, Yannis Chronis, Fatma Özcan, Yannis Papakonstantinou, Timofey Asyrkin, Sebastian Infante Murguia, Itai Rosenblatt, Themis Palpanas
TL;DR
Filtered vector search is difficult to tune because predicate selectivity and correlation affect the search effort needed for a target recall. VADER predicts recall during execution and terminates search at the specified target; across datasets and correlations, achieved recall stays close to target, and the method outperforms existing baselines.
Problem
Predicate selectivity and correlation substantially affect the difficulty of achieving desired result quality and latency in filtered vector search.
Source: §1 · p. 1Method
VADER adaptively predicts per-query recall during execution and terminates search once the specified target is reached.
Source: §5 · p. 15Results
Across datasets and correlation settings, VADER achieves recall values close to the target, with an average deviation of 0.04, and outperforms existing baselines.
Source: §4.2.2 · p. 9, §5 · p. 15Takeaways & Limitations
VADER represents the state of the art for declarative recall in filtered vector search.
Source: §5 · p. 15Recall prediction after processing an entire leaf can overshoot the target on an out-of-distribution dataset, although VADER still achieves the targets.
Source: §4.2.11 · p. 14
Abstract
from arXiv · showhide
Approximate filtered vector search (FVS), a core operation in many data management tasks that combine structured data with vector embeddings, exhibits increased complexity due to the characteristics of filtering predicates. Each predicate is defined by selectivity (i.e., the fraction of vectors that satisfy the predicate) and correlation (i.e., the relationship between the filter and the vector space), which can significantly affect search difficulty even for the same query vector. This poses a key challenge for users aiming to integrate vector search with structured data, as efficient execution often requires extensive manual tuning of algorithm parameters. In this paper, we present VADER, the first approach that eliminates hyperparameter tuning by introducing declarative recall for approximate filtered vector search. With declarative recall, users specify a desired recall target, and VADER executes FVS queries to meet this target without requiring manual configuration. VADER achieves this by employing a filter-aware recall predictor that generalizes across varying selectivities and correlations without explicit tuning, and by performing early termination once the predicted recall reaches the user-defined target. Through extensive experimental evaluation, we show that VADER achieves near-optimal early termination, while providing significant speedups of up to 53% faster and improved result quality of 28% compared to the best-performing baseline.
1 INTRODUCTION
Filtered vector search combines vector similarity with structured predicates, whose selectivity and correlation make search effort difficult to predict and manual tuning impractical. VADER addresses this with declarative recall and early termination, reporting better quality and speed than the best-performing baseline.
1 INTRODUCTION
- At fixed selectivity 0.01, varying correlation requires up to 30× more search effort for recall 0.9; with no correlation, varying selectivity from 0.01 to 1.0 requires up to 8× more.The example uses GLOVE1M and illustrates why one search configuration may not suit every predicate.Source: §1 · p. 1
- Applying the same hyperparameters across queries makes easy queries oversearch and difficult queries risk falling short of the desired recall.Tuning per selectivity and correlation is impractical because correlation is unknown in advance and selectivity estimates may be inaccurate.Source: §1 · p. 1
- Declarative recall with early termination had been studied for unfiltered vector search, but FVS complexity had prevented methods tailored to that setting.Iterative scan's hard stop can also prevent discovery of closer predicate-satisfying vectors.Source: §1 · p. 1
- Up to 53% faster and 28% better in quality than the best-performing baseline, which is tuned for each selectivity and recall target.VADER also terminates within 4% of the optimal point and meets recall targets across selectivities and correlations without overhead.Source: Figure 1 · p. 2
- VADER combines a filter-aware recall predictor and asymmetric loss with early termination, and integrates with k-NN graph and IVF-based FVS algorithms.Its predictor uses features intended to support accurate predictions without prior knowledge of predicate selectivity or correlation.Source: Figure 1 · p. 2
2 PRELIMINARIES
The preliminaries define filtered approximate vector search and its quality measures, then describe filter-agnostic methods and prior approaches. They position declarative recall as a target-recall interface for a setting where existing early-termination work did not address FVS.
2.1.1 Filtered Approximate Nearest Neighbor Vector Search (FVS)
- FVS retrieves approximate nearest neighbors satisfying a predicate; filtering remains satisfied for returned results, while recall measures retrieved true filtered neighbors and latency measures query time.The paper focuses on approximate search and does not restrict the predicate to a particular filtering operation over structured data.Source: §2.1.1 · p. 2
2.1.3 Filter-Agnostic FVS
- Filter-agnostic methods build a standard vector index, test each vector against the predicate during search, and generalize across filtering mechanisms; this work focuses on inline filtering.Inline filtering combines search and filtering rather than separating them into pre- or post-filtering steps.Source: §2.1.3 · p. 2, §2.1.4 · p. 2
2.1.4 Filtering Strategies for Vector Search
- VADER replaces tuned search parameters in the FVS interface with a desired recall target, despite selectivity and correlation varying across queries and being unknown in advance.The interface changes from FVS(q, I, k, F, sp) to FVS(q, I, k, F, R_t).Source: §2.1.5 · p. 2
2.2 Related Work
- Prior FVS methods include graph-based traversal and IVF search, while iterative scan's hard-stop policy can miss closer vectors that satisfy the predicate.The described approaches include ACORN, Sweeping, iterative scan, and Filtered-ScaNN.Source: §2.2.1 · p. 3
2.2.1 Filter-Agnostic FVS Algorithms.
- Existing early-termination methods addressed unfiltered vector search; the paper identifies a lack of methods providing declarative recall specifically for FVS.Prior work included methods for particular index types and distance measures, as well as DARTH and DARTH+ for arbitrary index types without distance-measure assumptions.Source: §2.2.2 · p. 3
3 THE VADER APPROACH
VADER pairs a filter-aware recall predictor with adaptive invocation and early termination to meet user-specified recall targets. Its training and algorithm-specific features support predictions across filtering conditions and several filter-agnostic search algorithms.
3.1 Early Termination with Recall Prediction
- VADER executes filtered vector search with a user-specified recall target, invoking its predictor adaptively and terminating when predicted recall reaches that target.The predictor is called more often as predicted recall approaches the target, limiting unnecessary calls while seeking a timely stopping point.Source: §3 · p. 3, §3.1 · p. 3
3.2 Model Architecture
- GBDT balances prediction accuracy with low inference latency, and VADER adopts it as the recall-predictor architecture.The paper argues that complex deep-learning models are too costly for millisecond-scale search, while simpler regression lacks sufficient accuracy.Source: §3.2.1 · pp. 3–4
3.2.2 Asymmetric Loss Function.
- VADER’s optional asymmetric loss penalizes recall overpredictions more heavily than underpredictions, making predictions more conservative.It sets the penalty factor from the average training recall to avoid hand-tuning that parameter.Source: §3.2.2 · p. 4
3.3.1 Recall Prediction Features.
- VADER combines search-progression and nearest-neighbor statistics with dynamic predicate features, without requiring known selectivity or correlation as inputs.The shared feature set applies across k-NN graph and IVF methods; observed selectivity is identified as especially informative.Source: §3.3.1 · pp. 4–5
3.3.2 Training FVS Query Generation.
- VADER generates training queries across selectivities and positive, negative, or absent correlations, using simulated predicate bitmaps to form filtered workloads.A small set of representative selectivities can generalize to unseen values; training can use fewer correlation types when negative correlation is rare.Source: §3.3.2 · p. 5
3.3.3 Extracting Training Data from FVS Queries.
- For each training query, VADER records features and ground-truth recall more densely at high recall, stopping collection once maximum recall is reached.The data-generation process is parallelizable and can finish within minutes even in the worst case described.Source: §3.3.3 · p. 5
3.4.1 Sweeping.
- VADER’s shared features support multiple filter-agnostic algorithms, with Sweeping adding candidate-queue distance statistics to capture predicate-dependent search behavior.Sweeping’s candidate queue can differ from its predicate-satisfying result set as selectivity and correlation vary.Source: §3.4 · p. 5, §3.4.1 · p. 5
3.4 VADER in Filter-Agnostic FVS Algorithms
- ACORN’s predicate-filtered two-hop expansion makes Sweeping-style candidate features unnecessary, while Filtered-ScaNN uses the shared features with partition-level prediction.Filtered-ScaNN adds query-to-centroid distance as a feature.Source: §3.4.2 · p. 5, Table 2 · p. 6, §3.4.3 · p. 6
4 EXPERIMENTS
The experiments use diverse vector datasets and filtered workloads, with comparisons against declarative-recall and tuning-based baselines. They assess recall, latency, and prediction error.
Setup and query workloads
- The evaluation uses six datasets, 100 test queries, and workloads spanning selectivities 0.01–1.0 and positive, negative, and no correlation.CASELAW7M uses real structured metadata and its own filtered queries rather than generated predicates.Source: §4 · p. 6
Baselines
- Comparisons include DARTH/DARTH+ and two Recall-to-Effort Mapping baselines, which require training or tuning and do not provide declarative recall for filtered search.REM-Filtered tunes separately by selectivity; REM-Unfiltered reuses settings from unfiltered workloads.Source: §4 · p. 6
Quality measures
- The evaluation measures achieved recall and average latency, alongside query-level recall behavior and recall-prediction error.Prediction quality is assessed using mean absolute error between predicted and true recall.Source: §4 · p. 7
4.1 Recall Prediction Analysis
VADER’s all-correlation predictor maintains low recall-prediction error across settings, and its filter-aware features improve prediction. Training and loss-function experiments show the costs and trade-offs behind those results.
4.1.1 Recall Prediction Accuracy.
- Across settings, all-corr achieves MAE=0.046, compared with MAE=0.048 for no-corr and MAE=0.054 for pos-corr.Under negative correlation, all-corr achieves MAE=0.070, versus MAE=0.074 for no-corr and MAE=0.122 for pos-corr; at recall ≥0.80, the respective MAEs are 0.054, 0.086, and 0.080.Source: §4.1.1 · p. 7
- Table 3 reports MAE across training-query counts; performance stabilizes at approximately 500 queries for no-corr and all-corr, while pos-corr peaks at 1K.For all-corr, 100/500/1000 queries yield MAE=0.053/0.052/0.051 for Sweeping and 0.057/0.054/0.054 for ACORN; the evaluation uses 500 queries by default.Source: Table 3 · p. 7, §4.1.2 · p. 7
4.1.3 Training Sample Sizes.
- All-corr uses more training samples because it covers three correlation types, and negative-correlation searches generate more samples as they require more search to reach high recall.GLOVE1M requires the most samples across configurations, attributed to its highly clustered structure and the difficulty of distinguishing true nearest neighbors at high recall.Source: §4.1.3 · p. 7
4.1.4 Training Times.
- For Sweeping, all-corr training takes under 6 minutes, versus 1 minute for no-corr; for ACORN, it takes under 9 minutes, versus approximately 3 minutes.All-corr includes data generation and GBDT training: 5 and 0.85 minutes for Sweeping, and 8 and 0.46 minutes for ACORN.Source: §4.1.4 · pp. 7–8
4.1.5 Feature Selection.
- Filter-aware features lower average MAE by 12% for Sweeping and 16% for ACORN across k values and correlation settings.The analysis finds filtering-related features correlated with recall; observed selectivity is more influential in ACORN, whose expansion uses predicate-matching neighbors, than in Sweeping, which traverses unfiltered neighbors.Source: §4.1.5 · p. 8, Figure 4 · p. 8
- No single feature category dominates importance: filtering-related features account for 31% in Sweeping and 17% in ACORN, alongside other contributing categories.The model combines search progression, intermediate nearest-neighbor statistics, query-dimensional statistics, and filtering behavior.Source: §4.1.5 · p. 8
4.1.6 Asymmetric Loss Sensitivity Study.
- Increasing the asymmetric penalty reduces overpredictions but raises MAE, trading prediction quality against queries falling below target and latency.The automatic setting reduces overpredictions to around 33%, compared with 40% for symmetric loss, with MAE=0.053 versus MAE=0.052; it is used throughout the evaluation.Source: §4.1.6 · pp. 8–9
4.2 End-to-end Performance Results
VADER’s early termination tracks specified recall targets while speeding up search over plain search. Its termination points are close to an oracle’s, and recall remains near target across individual queries.
4.2.1 Summary of Achieved Recalls and Speedups over Plain Search.
- Sweeping reaches speedups up to 24.8× and 8.8× on average, with RQUT=0.27 and average recall deviation 0.04; ACORN reaches 15.1× and 3.4× on average.For ACORN, RQUT is 0.35 and average recall deviation is 0.05; achieved recalls closely match desired targets across correlation settings.Source: §4.2.1 · p. 9
4.2.2 Recall Distributions.
- Across configurations, average deviation from target recall is 0.04, and the lowest observed recall is 0.76 against the 0.9 target.The reported recall distributions cover Sweeping with k=100 and selectivity 0.3; other correlations and configurations show similar trends.Source: §4.2.2 · p. 9
4.2.3 Optimality of Early Termination Points.
- Across datasets, selectivities, and correlations, VADER’s termination points deviate from the oracle by only 4.1% with respect to plain search.The oracle gives the minimum distance computations needed for each query, selectivity, and correlation to reach the target, but is infeasible in practice.Source: §4.2.3 · p. 9
4.2.4 Predictor Invocations Heuristics.
Predictor-invocation frequency trades off target precision against latency: both coarse and frequent calls can be costly. The heuristic balances these outcomes, and VADER performs similarly on selectivities unseen during training.
4.2.4 Predictor Invocations Heuristics.
- Both coarse and frequent predictor calls can increase latency: coarse schedules cause redundant distance computations, while frequent calls add inference overhead.Large invocation intervals can exceed 100 ms latency with only 1–2 calls; small intervals can also exceed 100 ms with 31–71 calls per query.Source: §4.2.4 · p. 9, (e) T2I10M · p. 11
- The heuristic-selected settings achieve recall 0.92, RQUT 0.23, approximately 10 predictor calls per query, and average latency of approximately 26 ms.Small variations to the heuristic produce similar results, indicating a robust balance without parameter tuning.Source: (e) T2I10M · p. 11
(e) T2I10M
- On unseen selectivities, VADER’s average recall deviation is 0.045, compared with 0.041 for selectivities observed during training.The tested unseen selectivities are 0.02, 0.05, 0.2, and 0.8; the results cover all datasets.Source: §4.2.5 · p. 11
4.2.5 Generalization to Unseen Selectivities.
VADER maintains recall close to target across correlations and parameter settings, outperforming tuned baselines in the reported comparisons. The evaluation varies selectivity and recall targets, with baseline tuning protocols that differ in how much query-specific information they use.
4.2.5 Generalization to Unseen Selectivities.
- REM-Unfiltered uses one ef_search tuned at sel=1.0, while REM-Filtered is tuned per selectivity and recall target under no correlation, then reused across correlations.Both variants are tuned separately for ACORN and Sweeping; the authors describe REM-Filtered's tuning as impractical for deployment.Source: §4.2.6 · p. 11
4.2.6 Setting Up Baselines.
- The varying-selectivity comparison tests all methods across datasets, selectivities, and correlations at R_t=0.9 and k=100.The dashed line marks R_t=0.9; closeness to it indicates better result quality.Source: §4.2.7 · p. 11
4.2.7 Performance for Varying Selectivities.
- Across correlations, VADER's average deviation is 0.04; it improves performance over REM-Filtered by 12% on Sweeping and 28% on ACORN.On Sweeping, VADER is also 32% faster than REM-Filtered and 52% faster than REM-Unfiltered; ACORN can incur slightly higher latency.Source: §4.2.7 · p. 11
- For Sweeping at sel=0.3, VADER outperforms REM-Filtered, REM-Unfiltered, and DARTH by 5%, 20%, and 75% in target proximity, and is 29%, 48%, and 47% faster, respectively.On queries below target, it trails REM-Unfiltered (average error 0.05 against 0.03) but beats REM-Filtered by 12% and DARTH by 80%.Source: §4.2.8 · p. 11
- For ACORN at sel=0.3, VADER outperforms REM-Filtered, REM-Unfiltered, and DARTH by 56%, 65%, and 50% in target proximity, respectively.On below-target queries, its improvements are 59%, 70%, and 54%, respectively.Source: §4.2.8 · p. 11
4.2.8 Performance for Varying Recall Targets.
The experiments vary k and compare achieved recall with the target across Sweeping and ACORN. VADER's target proximity and latency trade-offs differ by algorithm.
4.2.8 Performance for Varying Recall Targets.
- For Sweeping, REM-Filtered matches the other methods' latency but reaches the target less often.This comparison varies k and includes results for both Sweeping and ACORN under no, positive, and negative correlation.Source: §4.2.8 · p. 12
- For ACORN, VADER improves target proximity over REM-Filtered, REM-Unfiltered, and DARTH by 45%, 58%, and 28%, and below-target performance by 79%, 83%, and 74%, respectively.For Sweeping, VADER's deviation is similar to DARTH and REM-Unfiltered, 9% better than REM-Unfiltered; REM-Unfiltered is marginally faster, while VADER is 11% faster than DARTH.Source: §4.2.8 · p. 12
4.2.10 Results on Real Structured Metadata.
On CASELAW7M, VADER's achieved recall closely tracks recall targets across Sweeping and ACORN. The evaluation also reports predictor accuracy and training costs on this real-metadata workload.
4.2.10 Results on Real Structured Metadata.
- CASELAW7M contains 7.4M vectors and approximately 89K filtered queries over real structured metadata, with average predicate selectivity 0.05.The evaluation reserves 5K queries and varies training-set size from 100 to 80K queries.Source: §4.2.10 · p. 12
- With 10K training queries, recall-prediction MAE is 0.045 for Sweeping and 0.037 for ACORN, and training takes 1.8 and 3.2 minutes, respectively.Prediction accuracy stabilizes at approximately 10K training queries; larger sets yield marginal improvements.Source: §4.2.10 · pp. 12–13
- On CASELAW7M, achieved recall closely matches targets; query deviations are approximately 0.07 for Sweeping and 0.05 for ACORN.Across recall targets, Sweeping has R_QUT=0.27 and ACORN has R_QUT=0.17.Source: §4.2.10 · p. 13
- For VADER with Filtered-ScaNN, the training procedure is the same as for the k-NN graph case; evaluation uses one ScaNN index per dataset, configured by official parameter-selection heuristics.Source: §4.2.11 · p. 13
4.2.11 VADER for Filtered-ScaNN.
With Filtered-ScaNN, VADER achieves recall close to target across datasets and recall targets, with one reported overshoot case. The authors attribute that behavior to out-of-distribution data and leaf-level prediction timing.
4.2.11 VADER for Filtered-ScaNN.
- Filtered-ScaNN predictor training, including training-data generation, takes approximately 4 minutes for 1M-scale datasets and 20 minutes for DEEP10M and T2I10M.The indexes use single-level IVF clustering.Source: §4.2.11 · p. 14
- Across datasets and recall targets, VADER's achieved recall is close to target, except on T2I10M, where it overshoots and is not as close.Figure 32 reports achieved recall for varying selectivities and recall targets at k=100 with no correlation.Source: §4.2.11 · p. 14, Figure 32 · p. 15
- On T2I10M, out-of-distribution behavior can cause recall overshoot because prediction occurs only after processing an entire leaf; VADER still achieves the targets.The authors say VADER does not terminate while processing vectors within a leaf.Source: §4.2.11 · p. 14
(e) T2I10M
Across datasets and recall targets, VADER achieves recall close to the target. Figure 33 presents recall distributions for Filtered-ScaNN with k=100 and no correlation.
(e) T2I10M
- Figure 33 shows the recall distribution for Filtered-ScaNN at k=100 with no correlation.Source: Figure 33 · p. 15
- VADER achieves recall very close to the target across datasets and recall targets.The average RQUT is 0.16.Source: (e) T2I10M · p. 15
- Individual query recalls deviate from the target by only 0.05, similar to the k-NN graphs.Source: (e) T2I10M · p. 15
5 CONCLUSIONS
VADER introduces declarative recall for filtered approximate vector search, using a filter-aware predictor to estimate recall per query and stop at the specified target. Experiments across diverse datasets and workloads show it outperforms existing baselines.
5 CONCLUSIONS
- VADER introduces the first declarative recall approach for filtered approximate vector search.Source: §5 · p. 15
- A filter-aware recall predictor estimates per-query recall during execution, and search terminates once the specified target is reached.Source: §5 · p. 15
- Experiments across diverse datasets and workloads show VADER outperforms existing baselines and is state of the art for declarative recall in FVS.Source: §5 · p. 15