# A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search

arXiv: https://arxiv.org/abs/2609.02143 · HTML: https://mlsanity.com/paper/2609.02143/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 29 of its 103 references that are in the map.
- First posted on arXiv 2 Sep 2026.

## Builds on (most cited first, 29 of 29)

- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [wav2vec 2.0: A Framework for Self-Supervised Learning of Speech Representations](https://mlsanity.com/paper/2006.11477/) (2020)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [MPNet: Masked and Permuted Pre-training for Language Understanding](https://mlsanity.com/paper/2004.09297/) (2020)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2101.12631/) (2021)
- [Verifying the Union of Manifolds Hypothesis for Image Data](https://mlsanity.com/paper/2207.02862/) (2022)
- [When Large Language Models Meet Vector Databases: A Survey](https://mlsanity.com/paper/2402.01763/) (2024)
- [FreshDiskANN: A Fast and Accurate Graph-Based ANN Index for Streaming Similarity Search](https://mlsanity.com/paper/2105.09613/) (2021)
- [High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations](https://mlsanity.com/paper/2303.09855/) (2023)
- [ParlayANN: Scalable and Deterministic Parallel Graph-Based Approximate Nearest Neighbor Search Algorithms](https://mlsanity.com/paper/2305.04359/) (2023)
- [Results of the Big ANN: NeurIPS'23 competition](https://mlsanity.com/paper/2409.17424/) (2024)
- [Worst-case Performance of Popular Approximate Nearest Neighbor Search Implementations: Guarantees and Limitations](https://mlsanity.com/paper/2310.19126/) (2023)
- [Graph-based Nearest Neighbor Search: From Practice to Theory](https://mlsanity.com/paper/1907.00845/) (2019)
- [DeDrift: Robust Similarity Search under Content Drift](https://mlsanity.com/paper/2308.02752/) (2023)
- [MUST: An Effective and Scalable Framework for Multimodal Search of Target Modality](https://mlsanity.com/paper/2312.06397/) (2023)
- [boldsymbolSteiner-Hardness: A Query Hardness Measure for Graph-Based ANN Indexes](https://mlsanity.com/paper/2408.13899/) (2024)
- [Graph-based time-space trade-offs for approximate near neighbors](https://mlsanity.com/paper/1712.03158/) (2017)
- [Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits](https://mlsanity.com/paper/2405.18680/) (2024)
- [VIBE: Vector Index Benchmark for Embeddings](https://mlsanity.com/paper/2505.17810/) (2025)
- [Fast k-Nearest Neighbour Search via Prioritized DCI](https://mlsanity.com/paper/1703.00440/) (2017)
- [GLOW : Global Weighted Self-Attention Network for Web Search](https://mlsanity.com/paper/2007.05186/) (2020)
- [Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry](https://mlsanity.com/paper/2110.10283/) (2021)
- [TRIM: Accelerating High-Dimensional Vector Similarity Search with Enhanced Triangle-Inequality-Based Pruning](https://mlsanity.com/paper/2508.17828/) (2025)
- [PGTuner: An Efficient Framework for Automatic and Transferable Configuration Tuning of Proximity Graphs](https://mlsanity.com/paper/2508.17886/) (2025)
- [Distribution-Aware Exploration for Adaptive HNSW Search](https://mlsanity.com/paper/2512.06636/) (2025)
- [Evaluating and Generating Query Workloads for High Dimensional Vector Similarity Search](https://mlsanity.com/paper/2606.14511/) (2026)

## Abstract (arXiv)

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 Nc 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.