Improving Partition Routing in Approximate Nearest Neighbor Search with Query Expansion Routing

Approximate Nearest Neighbor (ANN) search methods often rely on space partitioning, where clusters are formed and partition routing is typically based solely on the query distance to cluster centroids. This approach neglects the incremental information gained during the search process. We present a novel query-expansion strategy that dynamically expands the set of scanned partitions using partial results from intermediate search stages. During indexing, we precompute neighborhood relationships between vectors and the partitions containing their nearest neighbors. At query time, initial results are retrieved based on centroid distances. Subsequently, an iterative expansion phase leverages these initial results to extend the partition ranking. This feedback loop can improve the recall–throughput trade-off by reducing unnecessary partition scans while maintaining high accuracy. We refer to this method as Query Expansion Routing (QER). We implemented QER in ScaNN and LoRANN, observing improvements on 14 of the 19 evaluated datasets for ScaNN-QER and 16 of 19 for LoRANN-QER. The gains are most pronounced in the high-recall regime. Across the five datasets with the largest gains for each method, ScaNN-QER and LoRANN-QER achieve geometric-mean QPS speedups of $1.34\times$ and $1.94\times$, respectively, computed for each dataset over the recall range jointly attainable by the baseline and the QER variant, within $Recall@100\in [0.95,1.0]$. We designed experiments to isolate the influence of approximate distance computation in ScaNN and LoRANN from QER. These experiments show that the method achieves the same recall while analyzing fewer partitions and scanning fewer vectors, demonstrating the value of candidate-driven feedback as a complementary signal for partition selection in clustering-based ANN search.