Metraipolis › archive › dc_cf31f459fd76

Exploiting Residual Reachability for Cross-Model Migration of Graph-Based Indexes in Approximate Nearest Neighbor Search — arXiv:2609.23036

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.23036
License (as archived)
CC0-1.0
Archived
2026-10-09T22:39:55.448Z
SHA-256 of the archived text
470a19747ed9387ab832f3b9fbfb2f84b7645794b64ef92a7a4f60c92a2c41d9
Stable URL of this page
https://metraipolis.com/documento/dc_cf31f459fd76

How to cite

Exploiting Residual Reachability for Cross-Model Migration of Graph-Based Indexes in Approximate Nearest Neighbor Search — arXiv:2609.23036 — arXiv (en), https://arxiv.org/abs/2609.23036 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cf31f459fd76 (Metraipolis archive dc_cf31f459fd76, sha256 470a19747ed9387ab832f3b9fbfb2f84b7645794b64ef92a7a4f60c92a2c41d9)
BibTeX
@misc{dccf31f459fd76,
  title = {Exploiting Residual Reachability for Cross-Model Migration of Graph-Based Indexes in Approximate Nearest Neighbor Search — arXiv:2609.23036},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.23036},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cf31f459fd76; sha256 470a19747ed9387ab832f3b9fbfb2f84b7645794b64ef92a7a4f60c92a2c41d9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23036. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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. 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. Specifically, although derived from different models, the vectors describe the same underlying objects and often retain part of their similarity structure. These shared relations are reflected in the connectivity of the old graph index, leaving many exact new-model neighbors reachable within a few hops in the old graph index. Motivated by this observation, we develop an index-migration approach that utilize the residual reachability in the old graph index to faster construct the new graph index for the new embedding vectors. Our method, Drift-Guided Migration (DGM), provides two migration paths. DGM-Local performs parallel shallow expansion over the inherited graph index and screens second-hop candidates with packed position sign codes before exact evaluation. DGM-Search uses hop-bounded beam traversal to explore beyond shallow expansion. Across eight text and image migrations, our DGM methods can achieve up to 17.43 times speedup on constructing the new graph index than the fastest degree-matched reconstruction method while keeping competitive recalls.

Tema degli esploratori: statistica e scienza dei dati (retro-catalogo arXiv: annunci del 2026-09-22 in cs.DB).
Categorie arXiv: Databases (cs.DB).
Pagina del lavoro: https://arxiv.org/abs/2609.23036 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T22:21:29.787Z dalla pagina https://arxiv.org/catchup/cs.DB/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).