What is the space complexity of a graph index?
The space complexity of a graph index describes how the total memory a structure like HNSW requires scales as a function of the dataset’s size — for HNSW specifically, this scaling is linear in the number of vectors, meaning doubling the dataset roughly doubles the total memory needed, since the graph‘s degree caps keep each node’s own storage cost bounded and independent of how large the overall dataset grows. Understanding this linear relationship, and exactly what fixed per-node cost it multiplies, clarifies why HNSW’s memory footprint is generally predictable and plannable, even for datasets whose ultimate size isn’t known precisely in advance.
Why does HNSW’s memory usage actually scale linearly, rather than growing faster as the dataset gets larger?
Every node in the graph carries a bounded, fixed amount of structure regardless of how many total nodes the graph contains — its own raw vector, capped at a fixed number of coordinates by the embedding model’s ambient dimension, and a set of neighbor-list entries at each layer it participates in, each capped by M or Mmax0 depending on the layer. Because these per-node costs don’t grow as the dataset grows — a node’s own vector size and its own connection caps stay exactly the same whether the dataset has a thousand vectors or a billion — the total memory used by N such nodes scales as simply N multiplied by this fixed per-node cost, which is the definition of linear scaling. This is a direct structural consequence of HNSW’s explicit degree caps, covered on the graph’s-connectivity-budget glossary page: those caps exist specifically to keep this per-node cost bounded, and bounded per-node cost is exactly what produces linear overall space complexity.
What actually goes into this fixed per-node cost, broken down into its separate pieces?
The raw vector itself contributes a cost proportional to the embedding‘s ambient dimension, as covered on that glossary page — more coordinates per vector directly means more memory per node, entirely independent of anything about the graph structure built on top of it. The graph structure’s own contribution is dominated overwhelmingly by the base layer, as discussed on the Mmax0 glossary page, since every node participates in the base layer and it carries the largest degree cap of any layer in the hierarchy; the sparse upper layers, by contrast, contribute comparatively little to a typical node’s total cost, since only a small, exponentially shrinking fraction of nodes ever reach those higher layers at all. A small amount of additional bookkeeping — the current entry point, whatever metadata a specific implementation tracks — rounds out the total, though this piece is generally negligible compared to the raw vector data and base-layer graph structure for any dataset of meaningful size.
How does this linear scaling in N actually compare to how memory usage changes with the other workload dimensions — ambient dimension and the M and Mmax0 parameters?
Space complexity is linear in N specifically, holding the other quantities fixed, but it scales differently along those other dimensions. Doubling the ambient dimension d roughly doubles the raw vector storage per node, contributing linearly to overall memory in exactly the same proportional way N does. Doubling M or Mmax0 roughly doubles the graph structure’s contribution to memory, since it directly doubles how many neighbor-list entries each node maintains, again a linear effect but applied to a different, separate component of the overall total. None of these relationships interact multiplicatively with each other in any surprising way — the overall memory footprint is, roughly, the sum of a term scaling with N times d for the raw vectors and a term scaling with N times M (or Mmax0) for the graph structure, making the total space complexity straightforwardly linear in each of these quantities considered individually.
Why does this predictable, linear scaling actually matter for planning a real deployment?
Linear space complexity means memory requirements for a growing dataset can be projected fairly reliably from a smaller-scale test — measuring the actual memory footprint of an index built from a representative sample of the full dataset gives a reasonably accurate basis for extrapolating what the full-scale deployment will require, since the relationship between dataset size and memory usage doesn’t bend unpredictably at larger scales the way a worse-than-linear relationship would. This predictability is genuinely valuable for capacity planning, particularly for datasets expected to grow substantially over time, since it means memory budgeting doesn’t need to account for the kind of surprising, accelerating cost growth that a quadratic or otherwise superlinear space complexity would introduce.
Having covered why HNSW’s space complexity scales linearly and what specific per-node costs that linear relationship actually multiplies, the graph’s-connectivity-budget and Mmax0 glossary pages are worth revisiting together with this fuller picture of exactly where a node’s memory footprint comes from. From there, the graph-storage-overhead and vector-storage-overhead glossary pages break this same total down further into its two separately-scaling components, which is useful when trying to identify specifically where a real index’s memory is actually being spent.