Filtered Approximate Nearest Neighbor Search Cost Estimation

Wenxuan Xia, Mingyu Yang, Wentao Li, Wei WangarXiv 2026 · DOI · arXiv

TL;DR

The E2E (Early probe-to-Early termination) framework significantly optimizes filtered vector searches by predicting search costs in real-time. By using a brief "early probe" to measure the local correlation between vector proximity and metadata filters, E2E achieves a 2x–3x reduction in search latency over state-of-the-art baselines while maintaining high accuracy.

What Problem Does This Paper Address?

Modern information retrieval often requires "hybrid queries"—finding items that are both semantically similar (vector search) and meet specific criteria (structured filters, like "price < $20" or "brand = A"). This is known as Filtered Approximate Nearest Neighbor (AKNN) search.

The core challenge is that search costs are highly unpredictable. In some cases, the most similar vectors easily pass the filter (an "easy" query); in others, the filter excludes all immediate neighbors, forcing the algorithm to traverse deep into the graph to find valid results (a "hard" query). Existing systems usually rely on conservative, worst-case configurations that waste computation on easy queries. Previous cost estimators were "filter-agnostic," meaning they looked at distance distributions but ignored the Feature-Filter Misalignment—the crucial correlation (or lack thereof) between where a vector sits in space and whether it satisfies a specific filter.

Methods

The authors propose E2E, a two-stage framework designed to bridge the gap between cost modeling and practical execution:

  1. Early Probing: Instead of relying on static statistics, the search begins with a short, "zero-overhead" traversal. The distance computations performed here are fully reused in the main search. This phase extracts "filter-aware" runtime features, most notably:
  2. $\rho_{pilot}$: The ratio of valid-to-total nodes visited during the probe.
  3. $\rho_{queue}$: The ratio of valid nodes currently waiting in the priority candidate queue.
  4. Cost Estimation: These features are fed into a lightweight LightGBM (Gradient Boosting Decision Tree) model. The model predicts the total "budget" (Number of Distance Computations, or NDC) required to reach the target recall. LightGBM was chosen for its extreme speed (0.025 ms inference), ensuring the estimation doesn't become a bottleneck.
  5. Adaptive Termination: The search continues until the accumulated computations reach the predicted budget, at which point it terminates early.

Datasets

The framework was evaluated on four large-scale, real-world datasets representing different domains and filter types:

  • Tripclick (1.0M base): Label-based filtering (Clinical Areas).
  • Youtube (1.0M base): Label-based filtering (Audio Tags).
  • Arxiv (1.7M base): Mixed Label (Categories) and Range (Dates) filtering.
  • MSMARCO (1.0M base): Range-based filtering (Synthetic Integers).

Key Insights and Ideas

  • Local Correlation is King: Global selectivity (e.g., "1% of the dataset is Brand A") is a poor predictor of search difficulty. What matters is the local density of valid points around the specific query vector. E2E captures this via the early probe.
  • Ranking vs. Absolute Accuracy: While predicting the exact number of computations is difficult due to the stochastic nature of graph traversals, the model excels at ranking query difficulty (Spearman’s $\rho$ up to 0.79). This allows for highly effective budget allocation.
  • Index Agnosticism: Although primarily tested on HNSW (a post-filtering approach), the authors demonstrate that E2E can be adapted to pre-filtering indices like ACORN by shifting the focus from queue validity to "neighbor inspection" rejection rates.

Key Results

  • Efficiency Gains: E2E achieved a 2.6x speedup on the Tripclick dataset and a 3x reduction in distance computations on Youtubeaudio compared to standard HNSW.
  • Robustness to Sparsity: Under "Equality" filters (which create extreme local sparsity), E2E maintained low latency by identifying hard queries early, whereas baselines suffered from massive traversal overhead.
  • High Recall Maintenance: The framework consistently outperformed "Naive HNSW" and "E2E without filter features," proving that explicitly modeling the filter-vector correlation is essential for maintaining accuracy while cutting costs.

Limitations and Future Work

  • Hardware Variability: The current metric (NDC) is hardware-agnostic. The authors note that future work could explore how cost estimation changes across different hardware environments (e.g., GPU vs. FPGA).
  • Predicate Complexity: While the paper covers label and range filters, the impact of more complex, multi-attribute boolean predicates on the estimator's accuracy remains an open area for investigation.
  • Offline Training: The model requires a one-time offline training phase with query logs. While parallelizable, this adds a pre-processing step whenever the underlying data distribution shifts significantly.

Summary updated

Abstract

Hybrid queries combining high-dimensional vector similarity with structured attribute filtering have garnered significant attention across both academia and industry. A critical instance of this paradigm is filtered Approximate k Nearest Neighbor (AKNN) search, where embeddings (e.g., image or text) are queried alongside constraints such as labels or numerical range. While essential for rich retrieval, optimizing these queries remains challenging due to the highly variable search cost induced by combined filters. In this paper, we propose a novel cost estimation framework, E2E, for filtered AKNN search and demonstrate its utility in downstream optimization tasks, specifically early termination. Unlike existing approaches, our model explicitly captures the correlation between the query vector distribution and attribute-value selectivity, yielding significantly higher estimation accuracy. By leveraging these estimates to refine search termination conditions, we achieve substantial performance gains. Experimental results on real-world datasets demonstrate that our approach improves retrieval efficiency by 2x-3x over state-of-the-art baselines while maintaining high search accuracy.
BibTeX
@misc{xia2026filtered,
  author = {Wenxuan Xia and Mingyu Yang and Wentao Li and Wei Wang},
  title = {{Filtered Approximate Nearest Neighbor Search Cost Estimation}},
  year = {2026},
  eprint = {2602.06721},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.06721},
}

Loading related content...

Figure