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

2609.02143 ↗ · 2026-09-02 · cs.DB, cs.AI, cs.IR, cs.LG

Sajad Faghfoor Maghrebi, Navid Eslami, Niv Dayan

17 pages, 10 figures

The finding

Headline claim

The prevailing belief that graph-based vector search (HNSW, Vamana) has poly-logarithmic query cost at fixed recall is wrong for practical scale: cost grows as a sublinear power law N^c until the dataset is large relative to its intrinsic dimensionality, after which it transitions to poly-logarithmic growth.

The test

Experiments across eight datasets measuring distance computations per query at fixed recall targets (90-99%) across dataset sizes, recall targets, query hardness levels, and index configurations for HNSW and Vamana, backed by proofs for exact and bounded-degree graph constructions and fitted cost models.

Effect size & scope

The Sublinear Power Law appears on all eight datasets, mostly up to full size, at every recall target, query hardness, and index configuration tested; the transition to poly-logarithmic scaling appears only on the two datasets large enough relative to their intrinsic dimensionality.

Limitations

Only two datasets were large enough to observe the transition to poly-logarithmic scaling empirically, so the regime boundary is mostly theory-supported rather than directly measured; the theory covers exact and bounded-degree constructions, which only approximate the heuristic indexes used in production; scaling results depend on fixed embedding models and distributions, and the paper does not report hardware wall-clock costs or memory footprint, only distance computations.

Counterpoint

A skeptic could note the claimed 'folklore' is attributed to HNSW's original paper based on low-dimensional synthetic data, so debunking it on high-dimensional real datasets may be attacking a strawman; the power-law exponents are fitted per dataset, so the theory's predictive power outside tested datasets is unproven; distance computations are a proxy, not end-to-end latency or dollar cost; and the full text provided is truncated before the experimental section, so effect sizes beyond stated coverage claims cannot be verified.

Economy implication

For vector database operators the near-term implication is that infrastructure cost per query grows faster with corpus size than vendor documentation and pricing models assume, so the cost of RAG-style retrieval at fixed quality will scale worse than logarithmically until datasets are very large relative to embedding intrinsic dimensionality; this is a marginal infra-cost correction, not a macro-level AI-economics result.

Who this matters for

Technical Capability: Corrects a foundational assumption about ANN search scalability that affects how retrieval-augmented systems should budget compute as their indexes grow.

Market & Valuation: Vector database vendors' cost and pricing story leans on logarithmic scaling folklore; if query cost is actually a power law over practical scales, gross margins on large-corpus customers are worse than advertised.

Abstract

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.