Disentangling Graph Dependencies for Efficient Billion-Scale GPU Vector Search

Graph-based approximate nearest neighbor search (ANNS) drives high-performance vector search for AI systems. Nowadays, GPU becomes the emerging ANNS platform for its high performance and cost efficiency. However, GPU’s limited memory capacity hinders graph ANNS systems from scaling to billion-level, due to graph’s high memory consumption (239–334 GB). Existing efforts mitigate this by offloading graph to CPU memory; however, this incurs severe performance penalties due to data transfer overhead and GPU stalls. We identify the root cause of this inefficiency: a strict step-level dependency in graph search, where each step relies on the traversal and computations of all nodes in the previous step. Our key insight is that this monolithic step-level dependency can be disentangled into a more flexible, fine-grained node-level dependency. Specifically, for each node, it is first accessed as a neighbor via an edge (i.e., discovery), and later selected as a parent to traverse its neighbors (i.e., expansion). These two stages are typically separated by many steps, exposing a sufficient discovery-expansion window. Leveraging this time window, the edge fetching to access some neighbors can be deferred and overlapped with computation. Based on this insight, we propose FlowANN, a graph-based ANNS system that efficiently supports billion-scale search on a single GPU. FlowANN employs a tiered graph structure, offloading the edges connected to neighbors that have sufficient time windows to the CPU. It effectively pipelines GPU computation with edge fetching via optimized asynchronous transfer and dynamic coordination. Evaluations show that FlowANN outperforms state-of-the-art systems by 4.08–45.7× on average (up to 172.6×), without compromising search accuracy.