BANCO: Drift-Aware Batched Bandits for Adaptive Proximity Graph Pruning

Proximity graphs are the state-of-the-art solution for approximate nearest neighbor (ANN) search, supporting applications such as Web search and retrieval-augmented generation (RAG). Sustaining long-term performance requires adaptive pruning as data and query workloads evolve. However, existing approaches are largely static and uniform. Adaptive pruning faces three key challenges: temporal drift in data and query distributions, spatial heterogeneity across graph regions, and costly feedback due to graph-level evaluations. We present BANCO, a bandit-based framework for adaptive proximity graph pruning. BANCO unifies diverse pruning strategies within a common decision space and optimizes them via a drift-aware batched bandit algorithm. It addresses temporal drift through drift-aware updates, captures spatial heterogeneity using contextual features for region-specific pruning, and reduces evaluation costs through batched feedback aggregation. We establish a dynamic regret bound with sublinear loss and polynomial computational complexity. Extensive experiments on four real-world datasets demonstrate that BANCO helps maintain long-term ANN search efficiency and accuracy under evolving data and workloads.