Executive Summary

Any organization running retrieval-augmented generation or recommendations keeps piling up vectors. Documents accumulate, products accumulate, conversation logs accumulate, and the embeddings grow with them. Sooner or later everyone operating a vector database arrives at the same question. If the index holding ten million records today holds a hundred million next year, how much more will search cost? Almost everyone answers it from the same premise: a graph index slows down only logarithmically as the data grows.

The paper this article follows puts that premise on a test bench. "A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search" was posted to arXiv on 2 September 2026, and all three authors are at the University of Toronto. None of them works for a vector database vendor.

First, pin down a term. Search cost in this article means the number of distance computations performed per query. Not response time in milliseconds, not memory, not the cloud bill. The paper states its reason plainly: measuring in wall-clock time conflates algorithmic behavior with implementation idiosyncrasies such as cache evictions, prefetching, and hardware-optimized distance computations. Distance computations dominate graph traversal and hold steadier across implementations.

1.1Grow the data and recall drops first

The paper's first experiment confirms something already known. Leave the index parameters alone and grow the data, and distance computations per query rise a little while recall falls a lot. Recall is the share of the true nearest neighbors that the search actually returns. The reason is intuitive. As the dataset grows, more points crowd near the query, beam search converges more slowly, and the true nearest neighbors face more competition for slots on the candidate list. Search quality quietly degrades.

So a practice has grown up around it. Run an exact search periodically, measure recall, raise the search candidate list size (ef_search) if the number falls short of the target, measure again, and repeat until the target is met. The paper cites vendor documentation and recent research as describing this practice widely. It matters here because it becomes the experimental design. Pin recall to a target while the data grows, and what moves shifts from quality to cost. The shape of that cost curve is the paper's question.

How a graph index walks a query, and why the edges of deleted documents linger in the graph, is something the Pebblous blog worked through once in a piece on deleted records reshaping vector search results. The same store viewed from a security angle appears in stored embeddings exposing the contents of emails. This article looks only at what that store costs as it grows.

One of the paper's opening subsections is titled "The Logarithmic Folklore," its name for the received wisdom about logarithmic scaling. As the paper sorts it out, the folklore splits in two. For exactly constructed graphs there is a claim with a proof attached. For the heuristic indexes used in practice there is a claim with no proof. What we actually run is the second kind.

So what did the paper everyone cites actually measure? Rather than repeat the new paper's summary, we opened the original HNSW paper (Malkov & Yashunin, arXiv:1603.09320 v4) and checked. Two things turned out to be true.

2.1The only experiment that measured scaling was a single pair of panels

In the original HNSW paper, the experiment that varies dataset size and plots a scaling curve is the pair of panels in Fig. 12(b) and (c). The data was synthetic vectors drawn from an 8-dimensional random hypercube, the task was 10-NN search, and recall was fixed at 0.95. And the paper's own wording was not a flat claim of logarithmic scaling but an upper bound: "not worse than logarithmic."

A qualification has to go with that. It is not the case that the whole HNSW paper was validated on low-dimensional synthetic data. Sections 5.2 through 5.4 compare performance broadly on real datasets including SIFT, GIST, and GloVe. The accurate statement is narrower: among the experiments that varied dataset size to measure scaling, there was one, and it used 8-dimensional synthetic vectors.

2.2The authors already recorded the departure in their largest run

Section 5.4 of that same paper is the more interesting part. A 200-million-point subset of SIFT, embedding dimension 128, the largest experiment in the paper. The authors plotted query time against dataset size and wrote this alongside it.

That sentence has been in print since 2018. It is important not to overstate it. The high dimensionality the HNSW authors invoke refers to the embedding dimension of 128, and that is not the same quantity as the intrinsic dimensionality the new paper casts as the driver of the curve. Writing that the two papers said the same thing would be wrong. What the original authors did was see a departure in their largest run and guess that dimensionality was behind it. Eight years later, this paper identifies which dimension and writes the shape of the curve as an equation.

Vamana's situation differs again. According to the new paper, the original Vamana work argued that the number of greedy search steps on an exactly constructed graph is logarithmic, but never measured search cost against dataset size.

2.3What traveled into industry documentation was the conclusion

The new paper writes that the claim spread through industry documentation and surveys until it was restated as an established property. We opened those documents ourselves. All six do describe scaling as logarithmic, or as polylogarithmic, meaning a logarithm raised to some power. But they are not equally strong statements. Below is each document's own wording and the character of the claim, accessed on 5 September 2026. Only Milvus had to be read from a Wayback snapshot dated 12 May 2026, because the live page returns nothing to a bot.

The last row completes the picture. The Redis document quotes the original paper rather than making its own claim. A vendor cites a paper, and the scaling experiment that paper rested on used 8-dimensional synthetic vectors. The whole chain is visible inside one document. Worth noting too: the new paper's own list of these documents differs between its Section 1 and Section 2. Milvus, Weaviate, Pinecone, Redis, and OpenSearch appear in both, while Section 1 adds FAISS and Section 2 adds Elastic.

What did not travel is easier to see laid out on one page.

The paper adds one more piece. The reason the claim went so long without being tested lies in how benchmarks are run. Benchmarks generally measure the recall-cost trade-off at a single dataset size, the paper writes, rather than holding recall fixed and measuring cost across sizes. That is the paper's assertion, and we did not separately verify the protocol of each benchmark.

The experimental design simply transplants the operational practice described above. Holding recall fixed means finding, at each dataset size, the smallest search candidate list that reaches the target recall, and recording the distance computations at that point. Then the data grows and the same thing happens again. Ground truth came from exact search over the full dataset.

The size of the grid is what gives the paper its weight. Eight datasets and four recall targets (90%, 95%, 97.5%, and 99%) multiplied by sixteen configurations per index. The configurations combine out-degree cap M at 16, 32, 64, and 128 with build candidate list size (ef_construction) at 100, 200, 400, and 800. Two index types were used, HNSW and Vamana, with Vamana's slack parameter α left at its default of 1.2. A footnote records that testing α at 1.5 and 2 left scalability unchanged, because out-degree typically saturates at the cap M. The number of neighbors returned, k, was also varied across 1, 5, 10, and 20, and since it did not materially change the exponent the paper reports only k=10. For space, the figures show four of the sixteen configurations, with the rest described as behaving similarly.

3.1Under a logarithm the curves would have bent downward

Reading the result is straightforward. Put both axes on a log scale, and a straight line means a power law. Under logarithmic scaling, each doubling of the data adds a constant number of distance computations, so the curve has to bend downward. What the paper observed is that most of the curves did not bend. It gave the shape a name, the Sublinear Power Law: distance computations per query are proportional to dataset size N raised to the power c, where c is a constant between 0 and 1.

The same figures show what pushes the exponent up or down. A higher recall target raises it, while a larger build candidate list and a higher out-degree cap lower it. And harder datasets tend to carry larger exponents. The paper uses intrinsic dimensionality as its proxy for difficulty, and the contrast it offers is GloVe against SIFT. Measured at one million points, their intrinsic dimensionalities separate at 32.4 and 19.2, and at equal recall GloVe carried the higher exponent.

3.2Splitting easy queries from hard ones changed nothing

Difficulty also varies query by query within a single dataset. The paper ranked queries by local intrinsic dimensionality (LID), split off the hardest 20% and the easiest 20%, and reran the experiment on each. On SIFT, DEEP, and GloVe, the hard group's intrinsic dimensionality exceeded the easy group's by at least 7.9, 9.6, and 11.0 points respectively. The two groups had different exponents, but both still traced straight lines. Query difficulty changes the slope of the curve without changing what kind of curve it is.

3.3The run that reached a billion points came under narrow conditions

The grid experiment capped SIFT, DEEP, and SpaceV at 100 million points, to keep total runtime to roughly one week. So the paper runs one more set of experiments separately, growing those three datasets from 100,000 points up to a billion and repeating the same measurement. The conditions here are narrow. Three datasets, one algorithm in Vamana, and a single configuration at ef_construction 100 and M 32. Vamana was chosen because its smaller memory footprint allowed the largest available sizes. At that scale, the index for a single configuration occupies 300 GB to 1 TB and takes several days to build.

The result: the curves for SIFT and DEEP kept running straight all the way to a billion points. Only SpaceV sloped downwards. A further condition attaches to that dataset. It contains many duplicate points, and to compare it fairly against the others the paper de-duplicates it and samples the query set exclusively from the base dataset, as a footnote records.

3.4What the difference in exponents looks like in a budget

Multiply the numbers out and you can see how different a plan a single exponent produces. The table below gives the factor by which distance computations per query rise for a given growth in data, by exponent. This table is not in the paper; we computed N to the power c ourselves.

Our arithmetic. The rightmost column is a reference baseline, the multiplier you get starting from one million points and assuming distance computations grow in proportion to log N. What the paper actually targets is polylogarithmic scaling, so this column should not be read as the paper's logarithm. It serves only to show that the gap opens up even against the most generous logarithmic assumption.

Shrinking the individual vector is a story the Pebblous blog has told before, in a piece on training-free vector compression. The two multiply. Compression reduces the constant in this table, and this paper is about the exponent.

The paper does not discard logarithmic scaling. It attaches a range to it. Once the data grows large enough the curve does eventually flatten, and from that point on the existing polylogarithmic claims hold. So when does the transition arrive? Here the observation runs against intuition.

4.1Only one dataset clearly bent

The cost curve that clearly bent belongs to SpaceV alone. Grown to a billion points, its slope came down. For the OpenAI embeddings, the paper notes that some of the grid-experiment curves seem to drift very slightly below their fitted power laws, and then immediately withholds judgment. "Only larger dataset sizes can tell whether the drift is real." OpenAI already uses its full base dataset, so it cannot be grown further. The abstract summarizes the transition as appearing in two datasets; the body is more cautious.

Set those two side by side and the logic of scale collapses. The OpenAI embedding set, 2.32 million vectors in total, showed signs of sagging at the very end of its own size. SIFT and DEEP, grown to a billion points, ran straight to the end. Measured at one million points, intrinsic dimensionality puts OpenAI highest at 46.5 and SIFT down among the low values at 19.2. The dataset with the higher intrinsic dimensionality bent first, and the lower one never bent at all the way to a billion. The explanation the paper attaches here runs to a single line. The slowdown seen in SpaceV and OpenAI is not specific to those datasets, and the same transition would appear in the others if they could be scaled to sufficiently large sizes. But the paper does not explain why those two arrived first. We are not going to invent a reason either, so the facts sit side by side.

4.2Intrinsic dimensionality is not a constant of a dataset

The theory that explains the shape of the curve runs in five steps. First, search cost is dominated by the number of points that sit in a narrow region around the query. The paper divides beam search into a shortcut phase that travels toward the query's neighborhood and an exploration phase that searches around the query for the true nearest neighbors, and in every case measured, the exploration phase accounted for at least 80% of the cost.

Second, widen that region by a radius ratio of (1+ε) and the number of points it contains grows in proportion to (1+ε) raised to the intrinsic dimensionality. That is Theorem 1. Third comes the paper's central line. Rewrite the base (1+ε) as a power of N, and the point count takes the form of N raised to the exponent (d_int / log N) × log(1+ε). An exponential in log N is a power of N.

The argument assumes the ratio (1+ε) does not drift with scale, and the paper measures that too. As the data grows, the distances from a query to its neighbors all shrink by the same proportion, so the inner and outer regions contract together and the ratio of radii holds. Plot the normalized distances of the nodes actually visited and the distributions nearly coincide across dataset sizes.

The claim that intrinsic dimensionality grows is backed by measurement. Using local intrinsic dimensionality (LID) as its proxy, the paper measured it at each dataset size. For most datasets, LID rises almost linearly against a log axis, which is to say it grows alongside log N. There are two exceptions. OpenAI still rises but with a slope that keeps shrinking, and SpaceV rises and then nearly flattens. The two datasets that parted from the others on the cost curves part from them on the LID curves as well.

4.3The dimension that makes search hard is a different one

Put all eight datasets in one table and it becomes obvious that the two dimensions are different quantities. The embedding dimension is the length of the vector, decided by the embedding model. The intrinsic dimensionality is the dimension of the structure those vectors actually lie on.

Embedding and intrinsic dimensionalities are the values in the paper's Table 2. The size column is not in the paper and was checked against the original dataset documentation. GloVe is 1,183,514 vectors in the standard ann-benchmarks distribution, a figure the paper does not state itself. Wiki-all comes in 88M, 10M, and 1M variants, and the paper does not record which one it used. Rand64 is synthetic data the paper generated itself, uniformly distributed on the unit sphere in 64 dimensions, so it has no public distribution and no count is given.

Two rows carry the point. Rand64 has an embedding dimension of 64 and an intrinsic dimensionality of 40.2, while GIST has an embedding dimension of 960 and an intrinsic dimensionality of 42.5. A longer vector does not make search harder. Rand64 does come with a caveat: drawn from a uniform distribution, it cannot be cited as an example of real data. In the paper's coefficient table this one dataset holds both extremes by itself.

Intrinsic dimensionality driving cost is not unique to search. What the Pebblous blog gathered in a piece on how diffusion models learn low-dimensional distributions was the same quantity governing sample complexity.

If the exponent is a constant, what sets it? The paper models the measured exponent as a sum of three factors, fitting the coefficients separately for each dataset and algorithm. The equation is this.

That recall enters the exponent logarithmically has real operational weight. Move the recall target from 90% to 99% and ln(1/δ) goes from 2.30 to 4.61, doubling, and the exponent rises accordingly. A recall target does not merely raise today's response time. It also picks the slope of next year's growth curve.

5.1What one step of recall does to the exponent

The body of the paper prints no specific values of the exponent c. The fitted values appear only at the ends of the curves inside the figures. So the table below holds values we calculated, using the paper's equation and coefficient table directly. The conditions are fixed at HNSW, build candidate list 200, and out-degree cap 32.

Values we calculated from the paper's equation and its Table 4-a coefficients. The conditions are HNSW, build candidate list 200, and out-degree cap 32; change the conditions and the values change. Rand64, being synthetic, is left out. The spread runs from 0.17 to 0.66, so no single value can stand in as the exponent of vector search.

Following the GloVe row alone tells the story. Same data, same index, same configuration, and moving only the recall target from 90% to 99% takes the exponent from 0.311 to 0.518. Run that through the multiplier table from the previous section and the cost of a hundredfold increase in data splits between 4.2x and 10.9x. That is what actually gets decided when a meeting nudges the recall target up one step.

The model has limits too. Its coefficient of determination averages 0.88. It explains 88% of the variation in the measured exponents, which means 12% goes unexplained. The separate relation linking a target recall to the search candidate list size needed to reach it is far tighter, above 0.98.

5.2Flatten the query curve and the build curve stands up

The equation seems to offer an easy fix. Raise the out-degree cap and the build candidate list size, and since both terms are negative the exponent comes down. A denser graph lets beam search reach the query's neighborhood in fewer hops.

But the paper models insertion cost the same way. Insertion also runs a beam search to find the new point's neighbors, so the same distance computations dominate. In the build-side model, the out-degree cap sits in the position that raises the exponent on N. The denser the graph, the more steeply build cost grows with dataset size. The handle that flattens the query curve is the handle that stands the build curve up.

Doubling the build candidate list size raises average insertion cost by about 1.8x. Every figure in this paragraph is one the paper prints directly. Excluding the synthetic dataset, the build-side candidate-list exponent sits between 0.80 and 0.92, running 0.07 to 0.16 above its query-side counterpart. The paper attributes insertion's greater sensitivity to candidate list size to reverse-link rewiring. When a node that would accept the new point as a neighbor has already hit its degree budget, its links have to be rearranged, and the rearrangement costs extra distance computations.

There is a reason we do not print calculated absolute values for the build exponent. Put the paper's coefficients into the equation and some combinations yield a build exponent below 1, which would mean inserting N points costs less than proportionally to N, and that does not hold physically. Nor is this an artefact of extrapolating past the range the paper tested. GIST never exceeds 1 at any of the four out-degree caps that were tested (our calculation). Treating it as an artefact of the fit is the better reading, so this subsection uses only the direction.

Search cost curves eventually show up as time somebody spends waiting. That waiting is what the Pebblous blog looked at in an observation that agents wait longer for data than for the model.

Everything so far has been measurement and the model that explains it. The paper attaches formal proofs on top. For practitioners, the useful move here is to separate what got proven from what is still outstanding.

6.1The proofs stand on an idealized construction

What is proven is not the index as deployed. To keep the exposition clean, the paper studies an exact construction called SNG and states explicitly that it lets that index be built free of charge. It writes that the same results hold for the heuristic versions used in practice, but two conditions come attached. One is that this applies in the sparse regime. The other is that each node must be allowed to choose its neighbors from a candidate list of unbounded size, meaning an infinite build candidate list. The empirical half ran on real implementations; the theoretical half stands on these idealizations.

6.2The index most people run sits on the unproven side

The abstract summarizes the work as proving both the power law and the eventual transition for exact and degree-bounded constructions. The body is more careful. A footnote to the table of per-regime costs shows the difference in temperature. For some graph-based indexes, the expressions in that table are lower bounds on cost rather than tight ones, and the table's expressions are tight only for the exactly constructed version of Vamana. The same footnote gives SNG's cost lower bound as larger than the polylogarithmic term.

The paper itself is a preprint posted on 2 September 2026, and no information about peer review or conference acceptance is available. No reproduction code or measurement logs were released with it. It carries no funding or conflict-of-interest statement. With all three authors at a university there is no reason to suspect vendor bias, but this is not yet a result that can be described as independently verified.

And the concluding sentence should not be misread. The paper does not say logarithmic scaling is wrong. "Our experiments and theory confine this claim to scales beyond a transition point." The word is confine. Below the transition point the behavior is a power law, and most practical datasets stay in that regime through their entire size, is how the paper puts it.

6.3If you were rebuilding the capacity plan

Translated into the language of a planning document, this paper yields a checklist. The items that need no new infrastructure, only the embeddings you already have, come first.

1. Measure the local intrinsic dimensionality of your data across a range of dataset sizes. Measure it once and treat it as a constant and you have missed the paper's point. The method the paper used applies a maximum likelihood estimator to nearest-neighbor distances over 500 random queries and six values of k.
2. Check whether that value grows alongside the logarithm of dataset size. If it is still growing, you are in the sparse regime, and cost should be expected to grow as a power.
3. Set the recall target first. Without a target there is no exponent to estimate. Between 90% and 99% the term inside the exponent doubles.
4. Convert next year's data volume into query cost with that exponent. The growth in data raised to the power c is the growth in cost.
5. Look at the opposing effect the same parameters have on build cost. Densify the graph on the strength of the query curve alone and you pay for it on the insertion side.
6. If your queries come from a different distribution than your documents, which is the common case in RAG, the paper writes that cost growth is governed by the largest intrinsic dimensionality among the intersecting manifolds. Averaging across manifolds is the wrong move; take the maximum as your basis.

On measurement tooling and what it costs to run, this article offers no guidance. It stops at conveying the method the paper used.

Pebblous diagnoses data and issues quality reports on it. Where the cost curve of search infrastructure meets that work is clear enough. What this paper identifies as the owner of the curve is not the index but the data.

7.1Diagnosis widens from problems in the values to a problem in the distribution

AI-Ready Data is about data in a form a model can consume directly. In vector search, what governs that form is less how many embeddings you have gathered than the character of the data those embeddings came from, and that is this paper's practical implication. Two collections of a million records each will follow different growth curves if their intrinsic dimensionalities differ, and they should be budgeted differently. Where earlier diagnostics looked at problems in the values, such as missingness, duplication, and label error, what gets added here is a problem in the distribution. How far has this data revealed its own distribution? That question comes into DataClinic's list of diagnostic items.

7.2Quality is also the structure the data lies on

Look at quality only as correctness of values and this paper's observation stays invisible. The structure the data lies on is quality too. This paper showed by measurement that the structural property governs the growth curve of search cost. A decision to gather more data becomes a decision about which cost curve you are on, and most organizations have never measured this property of their own data. The argument that the data comes first comes back this time in the language of a search infrastructure budget.

7.3Starting with which index to switch to gets the order wrong

The checklist in Section 6.3 is the practical prescription as it stands. The emphasis is on the order. Start with which index to switch to and the conversation stalls at product comparison. Measuring intrinsic dimensionality across a range of sizes takes no new infrastructure, only the embeddings already in hand, and it tells you first whether you are in the sparse regime or the dense one. Then: do not copy the word logarithmic out of vendor documentation into a planning document, and know that a benchmark number was measured at one dataset size. Both are things you could do this afternoon.

7.4Measure the property of the data before growing the scale

If compressing vectors to cut storage cost was a question about the constant, this article is a question about the exponent. Both are editions of the same question. Before asking how many embeddings to gather, ask what structure the data behind those embeddings has. Measure the property of the data first and grow the scale after: that order is where this article lands.

The figures in this article come from three places. Experimental conditions and coefficients were checked directly against the full text of reference 1, and the conditions of the scaling experiment and the observed departure were confirmed in the full text of reference 2. The wording of the industry documents was taken verbatim from each document, with the access date recorded. Specific values of the exponent are printed in none of these sources, so we calculated them from the equation and coefficients in reference 1.

The backbone of this report (checked against the primary sources)

• 1.Sajad Faghfoor Maghrebi, Navid Eslami, Niv Dayan (University of Toronto). "A Power Law in Logarithm's Clothing: On the Scalability of Graph-Based Vector Search." arXiv: 2609.02143, v1 submitted 2 September 2026, 17 pages and 10 figures, cs.DB. The experimental design, Tables 2, 3, and 4, Theorem 1 and Corollary 2, the cost model in Section 5, and the concluding quotation were all confirmed in this full text. No peer review information and no released code could be confirmed.
• 2.Yu. A. Malkov, D. A. Yashunin. "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs." arXiv: 1603.09320, v4 dated 14 August 2018, cs.DS. The conditions of the scaling experiment (Fig. 12, 8-dimensional synthetic vectors, recall fixed at 0.95) and the sentence "the scaling deviates from the pure logarithm" in Section 5.4 were confirmed in this version. The journal version was not separately checked.

Industry documents (wording verified, accessed 5 September 2026)

• 3.Milvus. "Index Explained." milvus.io/docs/index-explained.md. The live page returns nothing to a bot, so this was confirmed from a Wayback snapshot dated 12 May 2026.
• 4.Weaviate. "Vector Indexing." weaviate.io/developers/weaviate/concepts/vector-index.
• 5.Pinecone. "Hierarchical Navigable Small Worlds (HNSW)." pinecone.io/learn/series/faiss/hnsw. The only one of the six whose notation leaves the polylogarithmic case open.
• 6.Redis. "How Hierarchical Navigable Small World (HNSW) Algorithms Can Improve Search." redis.io/blog/how-hnsw-algorithms-can-improve-search. Quotes reference 2 instead of asserting anything itself.
• 7.OpenSearch. "k-NN Performance Tuning." docs.opensearch.org/1.0/search-plugins/knn/performance-tuning.
• 8.Elastic. "Vector search and kNN implementation guide, API edition." elastic.co/search-labs/blog/vector-search-implementation-guide-api-edition. The only one of the six that attaches a condition.

Datasets (sizes verified)

• 9.SIFT1B (Jégou et al. 2011), DEEP1B (Babenko & Lempitsky 2016), SpaceV1B (Microsoft 2021). That each holds one billion points is stated directly in Section 3.3 of reference 1.
• 10.OpenAI-ArXiv (big-ann-benchmarks distribution). 2,321,096 vectors, 1536 dimensions, 20,000 queries. These figures are printed in the bibliography entry of reference 1.
• 11.GloVe-100 (standard ann-benchmarks distribution). 1,183,514 vectors, 100 dimensions, 10,000 queries, angular distance. Accessed 5 September 2026. Not a figure stated by reference 1 itself.
• 12.GIST1M (TEXMEX corpus, INRIA/IRISA). 1 million vectors, 960 dimensions, 1,000 queries. Accessed 5 September 2026.
• 13.Wiki-all (RAPIDS cuVS documentation). Three variants exist at 88M, 10M, and 1M, and the bibliography entry in reference 1 describes the 88M version. Which variant the experiments used is not stated in the body.