Reproduce “Attribute Filtering in Approximate Nearest Neighbor Search: An In-depth Experimental Study” on OpenResearch

About this paper

Mocheng Li, Xiao Yan, Baotong Lu, Yue Zhang, James Cheng, Chenhao Ma

An empirical study of filtered approximate nearest-neighbor search organizes existing methods by attribute type and filtering strategy, then evaluates 12 configurations across numerical ranges, categorical labels, and arbitrary predicates. Results show that no single index dominates: specialized subgraphs are most useful for highly selective range queries, conventional HNSW is competitive when most items pass the filter, and partitioned or IVF-based approaches are more reliable for sparse arbitrary predicates.

Key insights

• Filtering selectivity determines the preferred index design: fine-grained segmented subgraphs help at very low selectivity, whereas ordinary HNSW becomes competitive once more than roughly half the data is eligible.
• Attribute-aware connectivity matters more than unrestricted vector connectivity under restrictive predicates; retaining additional edges can outperform aggressive geometric pruning.
• Comparison counts alone are insufficient for evaluating filtered search, since edge-validation and predicate-processing overhead can reduce QPS even when traversal performs fewer graph comparisons.

Summary by alphaXiv.