GAAF: Fast and Scalable Graph-based Vector Similarity Search with Any-Match Label Filtering
TL;DR
GAAF, a frequency-aware Graph Ensemble framework that decouples the handling of high- and low-frequency labels, is proposed, a frequency-aware Graph Ensemble framework that significantly outperforms state-of-the-art baselines.
Abstract
In many practical scenarios, vector retrieval is frequently coupled with keyword constraints, particularly under Any-Match semantics. Filtered Approximate Nearest Neighbor Search (Filtered ANNS) has emerged as a widely adopted solution. Within this domain, state-of-the-art methods often utilize graph-based indices that enforce constraints via runtime filtering on a monolithic graph. However, real-world label skew degrades this monolithic design: frequent labels waste computation on largely valid neighborhoods, while rare labels suffer from graph sparsity in locating limited candidates. To address this, we propose GAAF, a frequency-aware Graph Ensemble framework that decouples the handling of high- and low-frequency labels. GAAF partitions the dataset into specialized graphs: utilizing dedicated indexes for high-frequency labels to eliminate redundant comparisons, while consolidating the rest of the labels into shared graphs to restore connectivity. Leveraging the fine-grained control afforded by this ensemble, we introduce NUMA-aware data placement to minimize remote access, and Adaptive Inter-graph Pruning to bypass redundant traversals. Experiments on diverse datasets demonstrate that GAAF significantly outperforms state-of-the-art baselines.