GPU原生设计的混合搜索索引,速度比现有系统快240倍
GRAB-ANNS: High-Throughput Indexing and Hybrid Search via GPU-Native Bucketing
- 用分桶内存布局替代传统结构,适配GPU并行架构
- 在大规模数据上实现240.1倍的查询吞吐提升,召回率高
- 适合需要实时向量检索与过滤的AI系统开发者
混合搜索联合优化向量相似性与结构化谓词过滤,已成为现代AI系统的核心组件。尽管近期基于谓词感知的近似最近邻(ANN)索引提升了CPU上的过滤效率,但其性能受制于有限的内存带宽和并行度。虽然GPU具备极强的并行能力和更高的内存带宽,但直接将面向CPU的混合搜索算法移植到GPU会导致严重性能下降,主要由于不规则内存访问、分支发散及频繁的CPU-GPU同步。本文提出GRAB-ANNS,一种面向动态混合搜索的高吞吐GPU原生图索引。核心思想是从硬件出发重新设计混合索引:引入基于分桶的内存布局,将范围谓词转化为轻量级分桶选择,实现合并内存访问与高效的SIMT执行;为保持任意过滤下的全局可导航性,设计了结合密集内部边与稀疏跨桶远程边的混合图拓扑;进一步开发支持批量插入与并行图维护的追加式更新流水线。大规模数据集上的实验表明,GRAB-ANNS的查询吞吐量最高达当前最优CPU系统240.1倍,索引构建速度提升12.6倍,相比优化后的GPU原生重实现也达到10倍吞吐优势,同时保持高召回率。
原文摘要 · Abstract (English)
Hybrid search, which jointly optimizes vector similarity and structured predicate filtering, has become a fundamental building block for modern AI-driven systems. While recent predicate-aware ANN indices improve filtering efficiency on CPUs, their performance is increasingly constrained by limited memory bandwidth and parallelism. Although GPUs offer massive parallelism and superior memory bandwidth, directly porting CPU-centric hybrid search algorithms to GPUs leads to severe performance degradation due to architectural mismatches, including irregular memory access, branch divergence, and excessive CPU-GPU synchronization. In this paper, we present GRAB-ANNS, a high-throughput, GPU-native graph index for dynamic hybrid search. Our key insight is to rethink hybrid indexing from a hardware-first perspective. We introduce a bucket-based memory layout that transforms range predicates into lightweight bucket selection, enabling coalesced memory accesses and efficient SIMT execution. To preserve global navigability under arbitrary filters, we design a hybrid graph topology that combines dense intra-bucket local edges with sparse inter-bucket remote edges. We further develop an append-only update pipeline that supports efficient batched insertions and parallel graph maintenance on GPUs. Extensive experiments on large-scale datasets show that GRAB-ANNS achieves up to 240.1 times higher query throughput and 12.6 times faster index construction than state-of-the-art CPU-based systems, and up to 10 times higher throughput compared to optimized GPU-native reimplementations, while maintaining high recall.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。