Metraipolis › archive › dc_cb47dbfab81a
A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search — arXiv:2609.02143
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.02143
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T03:37:13.503Z
- SHA-256 of the archived text
a27f049a777f2ada5923c0150b81c6366e65294ef900da7d9e2b16ed75f7f256- Stable URL of this page
https://metraipolis.com/documento/dc_cb47dbfab81a
How to cite
A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search — arXiv:2609.02143 — arXiv (en), https://arxiv.org/abs/2609.02143 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cb47dbfab81a (Metraipolis archive dc_cb47dbfab81a, sha256 a27f049a777f2ada5923c0150b81c6366e65294ef900da7d9e2b16ed75f7f256)
BibTeX
@misc{dccb47dbfab81a,
title = {A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search — arXiv:2609.02143},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.02143},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cb47dbfab81a; sha256 a27f049a777f2ada5923c0150b81c6366e65294ef900da7d9e2b16ed75f7f256},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.02143. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Most vector databases rely on graph-based indexes, notably HNSW and Vamana, for approximate nearest neighbor search. With embedding models widely adopted, the datasets these databases store grow rapidly. At a fixed accuracy, how does search cost scale with dataset size? The prevailing answer is poly-logarithmic growth. Yet the claim is proven only under special conditions and asserted without proof for the indexes used in practice. It is also largely untested: standard benchmarks measure cost at one dataset size, not across sizes. We put the claim to the test. The answer depends on the scale itself. While the dataset size $N$ is small relative to the data's intrinsic dimensionality, search cost grows as $N^c$ for a constant $0<c<1$. We call this scaling the Sublinear Power Law. Once $N$ is large enough, growth slows to subpolynomial, consistent with the poly-logarithmic claim. The Sublinear Power Law appears on every dataset, mostly up to its full size, at every recall target, query hardness level, and index configuration we test. The transition to subpolynomial growth appears on the two datasets that grow large enough relative to their intrinsic dimensionality. One mechanism underlies both behaviors: a dataset's intrinsic dimensionality grows with its size until the data resolves its underlying distribution. Higher intrinsic dimensionality packs more vectors into the query neighborhood the search must examine. We present a unifying theory of beam-search cost that explains our observations. For exact and bounded-degree constructions, we prove the Sublinear Power Law and the eventual transition to poly-logarithmic scaling, and derive the scale at which it occurs. We also develop models that predict the power-law exponents for any recall target and index configuration. These models give a principled way to navigate trade-offs among search cost, insertion cost, and recall as data grows. Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-03 in cs.AI). Categorie arXiv: Databases (cs.DB) ; Artificial Intelligence (cs.AI); Information Retrieval (cs.IR); Machine Learning (cs.LG). Pagina del lavoro: https://arxiv.org/abs/2609.02143 — 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-17T03:13:12.509Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).