Memory consumption of HNSW indexes

Breaking down the footprint

Roughly: vector storage is n × d × 4 bytes for n float32 vectors of dimension d. Graph overhead is on the order of n × M × (average number of layers) × size_of_id. The average number of layers per node is typically O(log n) with the usual level distribution, so each node stores roughly M × O(log n) neighbor IDs. With 4- or 8-byte IDs, that adds tens to hundreds of bytes per vector depending on M and n.

For large M and high dimensions, the graph can be a significant fraction of total memory. Quantization (e.g. int8 or PQ) reduces vector size; lowering M or using pruning reduces graph size at the cost of recall.

Vector storage vs. graph storage

Vector storage dominates when d is large and M is modest; graph storage grows with M and the number of layers. For 1M vectors of dimension 384 (float32), vectors alone are about 1.5 GB. With M=16 and ~20 layers per node on average (for skip-list style), graph links might add on the order of 1M × 16 × 20 × 4 bytes ≈ 1.3 GB—so the graph can be comparable to vector size. For higher M or lower d, the graph share increases.

Scale and alternatives

For billion-scale vectors, in-memory HNSW can exceed available RAM, which motivates on-disk or hybrid designs and tiered storage. Memory per million vectors is a common benchmark; HNSW typically uses more memory than IVF-style indexes but offers better recall for a given query latency.

When RAM is a hard limit, options include: quantizing vectors (int8, PQ) to shrink vector storage; reducing M or using aggressive pruning; moving to disk-backed HNSW (load segments on demand); or using IVF (e.g. IVFPQ) which trades some recall for lower memory and better scalability to billions.

Pipeline and query-time memory

Index memory grows as vectors are inserted: each new node adds its vector and its neighbor lists. There is no separate “graph build” phase that doubles memory; growth is incremental. At query time, each search allocates a temporary candidate list of size efSearch (and possibly other buffers), so peak memory during a query is index size plus O(efSearch) per concurrent query. For high throughput, limit concurrency or efSearch to avoid memory spikes.

Trade-offs and practical tips

Trade-off summary: memory scales with n, d, and M; reducing any of these or using quantization saves memory but can hurt recall or build cost. Practical tip: estimate footprint before scaling—n × (d × 4 + M × 20 × 4) bytes for a rough in-memory HNSW with float32 and default layer distribution. If the result exceeds available RAM, plan for quantization, disk-backed index, or IVF-based design.

Pipeline summary: when designing for scale, compute vector + graph footprint first; use memory usage per million vectors as a reference. How quantization reduces memory footprint and trade-off between compression ratio and accuracy apply if you quantize; HNSW on disk vs. HNSW in RAM and overcoming RAM limitations for billion-scale vectors describe alternatives when in-memory HNSW does not fit.