Label-Balanced Graph Index for Filtered Approximate Nearest Neighbor Search with Low-Frequency Labels
Filtered Approximate Nearest Neighbor Search (FANNS) augments vector retrieval with categorical label predicates and is now standard in vector databases. Existing label-integrated graph indices, however, lose substantial recall on queries whose label is rare—the long-tail regime that dominates real workloads. We trace this failure to construction: distance-greedy neighbor selection and pruning systematically under-allocate edges to low-frequency labels, leaving their subgraphs poorly connected. Meanwhile, high-frequency labels accumulate redundant edges—slack that can be reallocated with limited impact on their search quality. Building on this insight, we propose LBGraph, which replaces both construction phases with label-balanced counterparts: a per-label round-robin candidate pool during exploration, and a label-then-distance rule during pruning. On low-frequency-label queries, LBGraph raises recall@10 by up to 71 percentage points (from 20% to 91%) over FilteredVamana on synthetic-label SIFT1M and GIST, with smaller gains on real-label LAION1M. Against ACORN-γ and StitchedVamana, it achieves up to 4 × their QPS at 90% recall@10 on low-frequency-label workloads while staying competitive on mixed workloads.