ResGraph: Cross-Model Graph-based Index Migration via Residual Reachability in ANN Search
Baoyuan Gu, Xiaoyao Zhong, Jiabao Jin, Peng Cheng, Wangze Ni, Haoyang Li, Haotian Li, Jingkuan Song 等 9 位作者
原文摘要
Approximate nearest neighbor search (ANNS) underpins large-scale vector retrieval in search, recommendation, and retrieval-augmented generation. Graph-based indexes have demonstrated state-of-the-art search performance for ANNS: they connect each corpus vector to a small set of nearby or navigationally useful vertices and answer queries by traversing the resulting graph. Because these edges are selected using construction-time distances, the graph index is tied to the embedding model; re-encoding a corpus with a new model may change distances and neighborhoods of the vectors, and reconstructing the graph for the new embedding vectors incurs substantial construction cost and delays deployment. When the embedding model changes, we observe a phenomenon in the old graph index that we call residual reachability: although derived from different models, the vectors describe the same underlying objects and often retain part of their similarity structure, which the old graph reflects as connectivity, leaving many exact new-model neighbors reachable within a few hops. Motivated by this observation, we develop ResGraph, an index-migration framework that exploits the residual reachability of the old graph index to construct the new graph index faster. ResGraph provides two migration paths. Res-Local performs parallel shallow expansion over the inherited graph index and screens second-hop candidates with packed position sign codes before exact evaluation. Res-Search uses hop-bounded beam traversal to explore beyond shallow expansion. Across eight text and image migrations, ResGraph attains up to 17.43 times speedup on constructing the new graph index than the fastest degree-matched reconstruction method while keeping competitive recalls.
cs.DB