How should HNSW’s data structures be laid out in memory for performance?

Created: Updated: 4 min read

HNSW’s data structures should be laid out so that the pieces of information a search touches together in time also sit close together in memory, because modern CPUs fetch memory in chunks and cache recently used chunks for fast reuse — an implementation that ignores this and scatters related data across memory pays a real, measurable performance cost that has nothing to do with the algorithm’s logic being wrong.

When a CPU reads a single byte from main memory, it doesn’t fetch just that byte — it pulls in an entire block surrounding it, called a cache line, on the theory that nearby data is likely to be needed soon too. If a node’s neighbor list is stored as a short, contiguous block of neighbor IDs, reading that list and then visiting each neighbor tends to stay within a small number of cache lines that get reused efficiently. If the same information is scattered — neighbor IDs stored far apart, or mixed in with unrelated data — each step of a graph traversal can trigger a fresh trip out to main memory, which is dramatically slower than reading from cache. Because HNSW search fundamentally means jumping from node to node along edges, this cache behavior isn’t a minor detail; it’s a large part of what determines whether a given implementation feels fast or sluggish at scale, independent of how good its search logic is.

Should vector data and graph metadata be stored together or separately?

The base layer, holding every vector and the densest set of connections, benefits from keeping a node’s vector data, its label, and its neighbor list close together in memory, since a base-layer search step typically needs all three in quick succession — the vector to compute a distance, the label to identify the result, and the neighbor list to continue the traversal. The upper layers behave differently: they hold a much smaller, sparser subset of nodes, and their own neighbor lists are shorter, so it often makes sense to store upper-layer connection data in its own smaller structure separate from the dense base layer’s records, rather than forcing every node’s storage layout to accommodate the rare case of participating in many layers. This split reflects the same asymmetry that motivated the layered design in the first place: the base layer is doing the bulk of the work and the bulk of the storage, while the upper layers exist purely to provide fast, cheap navigation toward the right neighborhood.

Does something as small as neighbor-ID width actually matter at scale?

It does, once the numbers involved get large enough. A neighbor ID stored as a 32-bit integer can address up to roughly four billion distinct nodes and takes half the space of a 64-bit ID; for a dataset comfortably under that ceiling, using 32-bit IDs throughout a graph with many millions of connections adds up to a meaningful reduction in total memory use compared to defaulting to 64-bit IDs everywhere, purely because every single connection in the graph carries this cost multiplied by however many connections exist. This is a small decision in isolation, but graph link overhead is exactly the kind of cost that scales directly with the size of the dataset, so small per-connection savings compound into a real difference in total memory footprint once a graph reaches production scale.

What does a complete memory budget for an index actually include?

A realistic accounting of an HNSW index’s memory footprint needs to include more than just “vectors plus edges.” The raw vector payload contributes a cost proportional to the number of vectors multiplied by their dimensionality and the size of each number’s numeric type. Each node’s connections at the base layer and, to a lesser extent, at the layers above it add a separate cost proportional to the maximum connections per node. Beyond these two obvious components, labels or metadata attached to each vector, and the overhead a memory allocator adds on top of every individual allocation it manages, both contribute real bytes that a naive “vectors times dimensions” estimate leaves out entirely — which is why measured memory use on a real dataset is generally somewhat higher than the simplest back-of-envelope calculation predicts, and why that gap shouldn’t be mistaken for a bug.

With data laid out for good memory access patterns, the next page turns to the other half of the performance picture: how the distance calculations that dominate search time can themselves be sped up on modern CPU hardware. For a concrete illustration of how these layout choices translate into actual measured memory numbers, the persistence and database-concepts sections of this site work through bytes-per-vector accounting and serialized index size in more depth.