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:
- 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:
- $\rho_{pilot}$: The ratio of valid-to-total nodes visited during the probe.
- $\rho_{queue}$: The ratio of valid nodes currently waiting in the priority candidate queue.
- 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.
- 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