← 研踪 PaperTrailarXiv:2609.23036 · v2
ResGraph: Cross-Model Graph-based Index Migration via Residual Reachability in ANN Search
首次提交 2026-09-19 22:13
版本更新 2026-11-13 16:32
雷达观测 2026-11-16 10:40
摘要
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.
作者备注:ICDE 2027 under review
观测到的版本
相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-13 16:32 · 最新观测版本
ResGraph: Cross-Model Graph-based Index Migration via Residual Reachability in ANN Search
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.
查看此版本解读 →查看此版本原文 ↗