Overcoming the Sync-Compute Dilemma in Parallel Graph-Based Vector Retrieval

Approximate Nearest Neighbor Search (ANNS) is fundamental to modern applications such as Retrieval-augmented Generation. Among various ANNS algorithms, graph-based methods have become the state-of-the-art due to their excellent search efficiency. The core of graph-based methods is to perform a Best-First Search (BFiS) on the proximity graph. However, with the continuous growth in data scale and dimensionality, the single-threaded BFiS algorithm is becoming increasingly inadequate to meet performance demands. In this paper, we first deconstruct the existing parallel graph-based ANNS algorithms (e.g., iQAN, Edge-wise). We find that they are constrained by the Bulk Synchronous Parallel model, which leads to a dilemma between reducing the synchronization overhead and reducing the computational overhead. To overcome this dilemma, we propose a decoupled search paradigm named ScatterSearch. In this paradigm, each thread independently conducts a full BFiS from a distinct entry point and maintains a private candidate queue, thereby eliminating explicit synchronization. Building on ScatterSearch, we further propose a leader-guided search pruning strategy to reduce computational overhead. It prunes search progress of some threads to avoid long-tail computation and redirects the pruned threads through a workstealing mechanism. Comprehensive experiments on real-world datasets show that with 16 threads and at Recall@100=0.99, our method reduces latency by up to 41.46% and increases throughput by up to $\mathbf{7 0. 8 2} {\%}$ compared to iQAN. Our method has been utilized on the Alibaba's taobao platform.