What is HNSW’s construction complexity?
HNSW‘s construction complexity describes how the total cost of building a complete index scales as a function of the dataset’s size — a quantity that, per typical theoretical analysis, grows a bit worse than strictly linearly with the number of vectors inserted, since each individual insertion’s own cost tends to increase somewhat as the graph it’s searching against grows larger and denser. Understanding this scaling behavior separately from the query-time search-cost claims covered elsewhere in this glossary category clarifies that HNSW‘s favorable logarithmic search-cost story is specifically about query time, not about how long the one-time process of actually building the index takes.
Why does the cost of a single insertion actually change as more of the dataset gets inserted before it?
Each insertion’s dominant cost comes from its construction search, covered on its own glossary page, which itself relies on the same SEARCH-LAYER routine used for ordinary queries. Early in construction, when the graph is still small and sparse, this search has relatively little to explore and completes quickly. As more vectors get inserted and the graph grows, later insertions’ construction searches are running against a larger, more fully developed structure, and while the layered hierarchy’s efficient routing keeps this cost from growing linearly with the current graph size, it doesn’t stay perfectly flat either — later insertions genuinely tend to cost somewhat more, on average, than earlier ones, reflecting the same bounded-but-growing routing-work behavior described on the bounded-expected-routing-work glossary page, applied here to construction-time searches rather than query-time ones.
How does this per-insertion cost growth actually add up across an entire dataset, and what overall scaling does that produce?
Summing the cost of every individual insertion across a dataset of N vectors, where each insertion’s own cost grows slowly — logarithmically, per the same reasoning behind HNSW’s favorable query-cost scaling — with however much of the graph already exists at that point, produces an overall construction cost that scales as N multiplied by a slowly growing logarithmic factor, rather than simply N on its own. This is sometimes described informally as “close to linear” or “linearithmic” scaling — meaningfully better than a naive approach whose per-insertion cost grew directly with the full current graph size, but not quite as favorable as a strictly constant per-insertion cost would produce. In practice, this scaling behavior is exactly why building an HNSW index over a dataset with a billion vectors takes proportionally longer than building one over a million vectors, but not dramatically or prohibitively longer — the logarithmic factor keeps the growth manageable even as the dataset scales up by orders of magnitude.
How does construction complexity actually depend on the specific parameters chosen, beyond just the dataset size itself?
efConstruction and M both directly influence the constant factors involved in this scaling relationship, even though they don’t change its fundamental shape. A larger efConstruction means each individual construction search explores more of the graph before concluding, directly increasing the per-insertion cost by a roughly proportional amount, which is exactly the construction-time cost side of the trade-off already discussed on the efConstruction glossary page. A larger M means more candidates need to be evaluated by the neighbor-selection heuristic and more bidirectional connections need to be formed and potentially pruned per insertion, adding further per-insertion overhead on top of what the construction search itself contributes. Neither parameter changes the overall N-times-logarithmic-factor shape of the scaling relationship, but both meaningfully affect the actual constant multiplying that shape, which is why doubling efConstruction or M, even without changing the dataset size at all, can noticeably lengthen how long a full index build actually takes in practice.
Why does this construction-time cost matter less, in most practical situations, than the corresponding query-time cost would?
Construction happens once, or incrementally as new data arrives, while queries happen continuously and repeatedly against the finished index for as long as that index remains in service — a system that serves millions or billions of queries against an index built just once can easily afford a construction process that takes considerably longer than any individual query would, since that one-time cost gets amortized across an enormous number of subsequent queries that all benefit from the resulting graph’s quality. This asymmetry is exactly why practitioners are often willing to set efConstruction considerably higher than the corresponding query-time efSearch, as discussed on the efConstruction glossary page — a slower one-time build that produces a meaningfully better-connected graph is a trade most production systems are happy to make, precisely because construction complexity, however it scales, is paid only once while query cost is paid over and over for the index’s entire operational lifetime.
Having covered how construction cost scales with dataset size and the parameters that influence its constant factors, the efConstruction and bounded-expected-routing-work glossary pages are worth revisiting together with this fuller picture of exactly where construction’s scaling behavior comes from. From there, the logarithmic-search-claim glossary page is worth rereading directly alongside this one, since the contrast between HNSW’s construction-time and query-time scaling behavior is precisely the distinction worth keeping clear when reasoning about an index’s overall cost profile.