roman bikbulatov

Filter-Aware Group Traversal for Adaptive ANN (Selectivity-Aware Group Scoring)

TL;DR. I work on filtered traversal in an architecture-aware ANN system where graph nodes are groups of vectors (offline KMeans clusters).
My core contribution is a selectivity-aware group scoring policy that re-orders traversal to reduce wasted expansions under selective filters and fixed ef_search / e_max budgets.
More details: technical note / code / full results available on request (subject to disclosure constraints).

Context

• Node = group: KMeans cluster (centroid + member vector IDs); typical group size ~1000 (also tested 500 and 100).
• Storage locality: vectors are stored contiguously per group, so wasted expansions directly translate to wasted memory and distance work.
• Overlap: vectors may appear in multiple groups; we treat overlap as a regime variable since it can dilute group-level selectivity signals.

Filters and selectivity

• Filters: categorical (OR over labels) and continuous range predicates (≤, <, ≥, >, =, between). Boolean can be encoded as categorical (k=2).
• Current schema: cat_uniform (k=128), cat_zipf (k=1024), x_uniform (f32 in [0,1]).
• Target selectivity s_target, realized s_real = match_count / N_base within ±10%.

Problem

Filtered workloads can make traversal wasteful:

• many expanded groups contain few or zero passing vectors,
• this increases coarse/exact distance work and hurts latency under fixed search budgets.

Goal: under fixed ef_search / e_max (and high-recall constraints), reduce wasted work and improve latency without degrading Filtered Recall@k.
Where it should matter most: low/mid selectivity and correlated workloads with group-level selectivity; weaker effects are expected for high selectivity and near-uniform groups.

Baseline traversal

Baseline policy is best-first traversal by centroid distance:

• seeds = nearest centroids,
• expansion via adjacency,
• stopping by e_max, queue size by ef_search,
• inside a group: coarse scoring + optional exact rerank (re_rank_k).

My contribution

1) Selectivity-Aware Group Scoring (v0)

I designed and integrated a filter-aware ordering policy for group-nodes, using per-group predicate statistics to estimate the expected fraction of passing vectors and re-order traversal (seeds + neighbor expansion).
v0 uses safe re-ordering only (no pruning/thresholding).

Score sketch pass_ratio(g) = estimate_cat_matches(g) / group_size
score(g) = base_score(g) / (1 + lambda * pass_ratio(g))

Aggregation details:

• sum within OR predicate (allowed labels),
• min across categorical predicates/columns (AND semantics).

2) Additional traversal optimizations (engineering)

• per-query continuous predicate cache (observed 8.9x–17.4x speedup in continuous-only runs),
• skip categorical-empty groups (up to ~23% p50 latency drop in correlated regimes without recall loss),
• conditional rerank when candidate set ≤ k (reduces exact distances; may cost ~1–2% recall; mixed),
• match-count fallback mode (fast at very low match-count; threshold calibration ongoing),
• skip continuous-empty groups via group min/max bounds (safe; mixed impact on uniform data).

Evaluation protocol

• Workloads: synthetic 128-D vectors with (i) an approximately homogeneous single-mode Gaussian distribution and (ii) clustered multi-modal mixtures (8 clusters), including a more strongly separated-cluster variant, to test both uncorrelated and correlated regimes under filters.
• Selectivity buckets: 1/5/10/20/50% + stress 0.5% and 0.2%.
• Metrics: Filtered Recall@10, p50/p95 latency, expanded/scanned groups, coarse/exact distance counts, skipped groups, match_count, realized selectivity.
• Budgets fixed by ef_search + e_max (+ re_rank_k).

Selected observations

• skip_empty_cat (correlated clustered workload, 30k): p50 43.39 → 33.35 ms; Recall@10 unchanged.
• skip_rerank_if_candidates<=k (homogeneous workload, 30k): Recall@10 1.0000 → 0.9905; exact distances 204 → 177; latency ~ unchanged.
• scoring v0 on/off (correlated fast eval, 100k): Recall and expansions similar; latency differences within run-to-run variance under current regimes.

Status and next steps

Status: scoring-based re-ordering is integrated and runnable as a pure ordering policy (no pruning). Preliminary results indicate the effect is regime-dependent: when group-level selectivity signal is weak (near-uniform labels / high overlap / large groups), ordering is close to neutral. Current work focuses on operating-regime characterization and calibration (λ sweeps, alternative score forms) using mechanism-level metrics such as wasted_expansions.
Next:

1. corr/uncorr sweeps in group-selective regimes (smaller groups, reduced overlap, clustered labels),
2. sweep lambda (0.1/0.25/0.5/1.0) and budgets with Recall@10 ≥ 0.97,
3. scale validation on a large-memory cluster to test regime stability at larger N_base.

Contact / access

• Name: Roman Bikbulatov
• Affiliation: University of Warwick
• Advisor: Prof. Hakan Ferhatosmanoglu
• Email: roman.bikbulatov@warwick.ac.uk