Metraipolis › archive › dc_97a2007e9300
OctEx: Billion-Scale Vector Search by Precomputed Lattice Neighbor Lists on GPUs — arXiv:2611.02556
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.02556
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T18:26:43.638Z
- SHA-256 of the archived text
faaedb663748013973e4d7233c8d42f7f62f6b3f43aff7bd416fd3246dfa010b- Stable URL of this page
https://metraipolis.com/documento/dc_97a2007e9300
How to cite
OctEx: Billion-Scale Vector Search by Precomputed Lattice Neighbor Lists on GPUs — arXiv:2611.02556 — arXiv (en), https://arxiv.org/abs/2611.02556 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_97a2007e9300 (Metraipolis archive dc_97a2007e9300, sha256 faaedb663748013973e4d7233c8d42f7f62f6b3f43aff7bd416fd3246dfa010b)
BibTeX
@misc{dc97a2007e9300,
title = {OctEx: Billion-Scale Vector Search by Precomputed Lattice Neighbor Lists on GPUs — arXiv:2611.02556},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.02556},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_97a2007e9300; sha256 faaedb663748013973e4d7233c8d42f7f62f6b3f43aff7bd416fd3246dfa010b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.02556. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Approximate nearest-neighbor search on GPUs serves retrieval-augmented generation, recommendation, and deduplication over datasets of up to billions of vectors. The fastest GPU indexes at high recall, such as CAGRA, walk proximity graphs in chained rounds, each of which waits for the distances of the previous one. High recall therefore costs many dependent rounds per query. Our insight is to spend the HBM of the GPUs on precomputed neighbor lists, so that a query reads its candidates in one parallel step instead of a chain of rounds. This paper turns the above insight into a GPU vector search system, namely OctEx, which holds hundreds of randomly projected copies of the dataset in GPU memory. Every copy rounds its vectors to the nearest points of a regular grid whose cells are nearly round and stores for every populated cell the list of vectors nearest to its center. A query reads the lists of its cells in all copies at once and then, in a fixed number of waves, the precomputed neighbor lists of its best hits. OctEx ranks the union of all hits by an int8 sketch before one exact rerank. OctEx runs the whole search of a batch as CUDA graphs over all GPUs of a server and places every part of its index in HBM or host memory by its access frequency. On four H100 GPUs at recall 0.95 to 0.995, OctEx outperforms CAGRA by 2.0x to 46.4x on seven datasets of up to one hundred million vectors, and by 1.46x to 2.05x on the one billion vectors of Deep1B and SIFT1B, whose indexes it builds in 44 to 47 minutes. OctEx also outperforms GGNN, PathWeaver, FlowANN, and the cuVS inverted file indexes IVF-PQ and IVF-RaBitQ by 5.4x to 343x. Tema degli esploratori: calcolo e infrastrutture (elenco arXiv cs.DC, nuovi lavori del giorno). Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC). Pagina del lavoro: https://arxiv.org/abs/2611.02556 — 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-11-03T18:10:22.835Z dalla pagina https://arxiv.org/list/cs.DC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).