Why does an HNSW index need more RAM than the vectors alone, and how much more?

## Two things are stored, not one A common sizing mistake is to budget an index at the size of the vectors. For HNSW that is only half the bill. The index stores the vectors *and* the graph over them, and on a high-M configuration the graph can approach or exceed the payload it indexes. **The vector payload.** Each vector is held so that distance can be computed against it during traversal, in whatever numeric format the store uses. **The graph.** Each node holds an adjacency list per layer it belongs to: a list of neighbour identifiers, conventionally 4-byte integers, plus a small header for the list length. Layer 0 is the expensive one because every vector is in it, and because implementations typically allow roughly twice M links there — the bottom layer needs denser connectivity since it is where the fine-grained search happens. ## The arithmetic Take M = 32 on an 80M-vector product catalogue. Layer 0 allows about 2M = 64 neighbour slots per node, at 4 bytes each, so about 256 bytes per vector. Across 80M vectors that is roughly 20 GB. The higher layers add a geometric tail: only a small fraction of nodes reach layer 1, a small fraction of those layer 2, so the whole hierarchy above layer 0 adds a modest percentage rather than another multiple. Now M = 64. Layer 0 allows about 128 slots, roughly 512 bytes per vector, so about 41 GB of edges. The recall improvement from that doubling is usually a couple of points at a fixed beam width — real, but bought with 20 GB of RAM that could have gone to a second shard or to headroom for a rebuild. In practice, on this kind of catalogue, the M decision is made by the memory budget and validated by a recall sweep, not the other way round. Two caveats on the numbers. Adjacency lists are usually allocated at their maximum size rather than at actual degree, so the figure is a ceiling that is also close to the typical case. And implementations differ in id width and per-node overhead, so treat the arithmetic as a sizing estimate to be confirmed against the actual process RSS after a build on a sample. ## Why it has to be resident The reason this memory is hard to economise on is the access pattern. A graph traversal reads one node's neighbour list, computes distances against those neighbours' vectors, then jumps to whichever it picks — a chain of dependent random accesses with no locality to exploit. There is no sequential scan to prefetch and no batch to amortise. Every one of those hops that becomes a page fault costs orders of magnitude more than the distance computation it was serving, and a query makes hundreds of hops. So HNSW is designed around a memory-resident graph. Where the corpus outgrows one machine, the usual answers are to shard it across nodes and fan out queries, or to move to a different index family whose payload compresses aggressively, or to a graph index explicitly engineered for SSD-resident layouts, which restructure the graph to make traversal contiguous rather than random. Those are architecture changes, not tuning. ## Sizing in practice A sane sizing exercise for a large index: estimate vector bytes, estimate edge bytes as roughly 2M ids per vector at 4 bytes, add both, then add headroom. The headroom matters more than people expect. A rebuild-and-swap deployment holds two copies of the index at once, which briefly doubles the requirement; deletes that are tombstoned rather than reclaimed keep paying for vectors nobody can retrieve; and the process needs room above the index for query working sets and the allocator's fragmentation. It is also worth noting what is *not* free to change. Because M is baked into the graph at insert, discovering after the fact that the index does not fit the box is not a config fix — it is a rebuild at a lower M, with the recall loss that implies. ## Where this sits in the tradeoff Every ANN index picks a corner of the recall-latency-memory triangle. HNSW's corner is high recall at low latency, paid for in RAM. That is an excellent trade at tens of millions of vectors on a machine with enough memory, and a bad one at billions of vectors or on a tight per-tenant memory budget. Being able to say that plainly — and to produce the per-vector byte figure that makes it concrete — is what separates a sizing answer from a preference. ## What interviewers listen for They want the mechanism (adjacency lists are stored data), the rough arithmetic (about 2M four-byte ids per vector at layer 0), the scaling behaviour (linear in M, linear in corpus size), and the reason it cannot be paged out (random dependent access). A candidate who also mentions the double-copy headroom during a rebuild has clearly operated one.