Estimate the RAM cost of an HNSW index over 100M vectors at 1024 dimensions with M=32, including graph overhead.

Short answer·Hard·4.0 · 0·~3 min·Asked atPinecone·Relevant atMicrosoft NVIDIA

Attempt it

Compute (show your math) the RAM cost of an HNSW index for 100M vectors at 1024 dimensions with M=32, float32 storage. Include both the vectors themselves and the graph edges. Note any practical assumptions a senior engineer would explicitly call out.

Free · 2 AI evals / day

**Two storage costs per node.** *The vector itself.* 4 bytes per float * 1024 dimensions = 4096 bytes per vector. This is by far the dominant cost. *The HNSW graph edges.* Each node stores neighbor pointers. The canonical HNSW implementation uses 2*M edges at the base layer (where every node lives) and M edges at higher layers (where progressively fewer nodes live). At M=32, that's 2*32 = 64 edges at the base layer, plus a small additional contribution from higher layers averaged across the hierarchy decay. Each edge is a 4-byte node ID. Total: ~256-320 bytes per node for graph storage. **Per-node total: ~4352 bytes.** **Total for 100M nodes: 100M * 4352 = 4.35 * 10^11 bytes = ~435 GB.** **Practical considerations a senior engineer should call out:** 1. **RAM-resident requirement.** HNSW does distance computations at every graph hop. If the vectors lived on disk, each hop would page-fault and per query latency would balloon from sub-millisecond to 10-100ms. The 435 GB number is RAM, not disk. 2. **Operational padding.** Real production memory needs 15-25% more than the raw index size: OS overhead, allocator fragmentation, index metadata, and headroom for live writes/deletions. Plan for ~500-525 GB. 3. **Tombstones inflate over time.** HNSW deletions are typically soft (tombstones); reclaiming memory requires a partial or full rebuild. Active workloads can run 20-40% over the baseline size between rebuilds. 4. **The decision threshold.** 435 GB is near the upper end of single-instance RAM on most cloud tiers (typical max around 768GB-1TB at high cost). At this scale, the natural moves are: switch to DiskANN (puts the graph on SSD, RAM holds only PQ summaries), switch to IVF-PQ (drops per-vector storage from 4 KB to ~32 bytes via Product Quantization), or shard the HNSW across multiple instances.

**Step-by-step calculation.** *Per-vector storage.* Each vector is 1024 float32 values. 4 bytes per float, so 4 * 1024 = 4096 bytes = 4 KB per vector. *Per-node graph storage.* HNSW maintains a hierarchical graph; canonical implementations use 2*M edges at the base layer (where every node appears) and M edges at higher layers (where progressively fewer nodes appear, with the level-promotion probability typically 1/ln(M)). For M=32: - Base layer: 2*32 = 64 edges * 4 bytes per ID = 256 bytes per node. - Upper layers: contribute roughly an additional ~64 bytes per node averaged across all nodes (the geometric decay of the hierarchy means upper layers are sparsely populated). - Total graph overhead per node: ~256-320 bytes. *Per-node combined storage.* 4096 (vector) + ~256 (graph) = ~4352 bytes per node. *Total for 100M nodes.* 100,000,000 * 4352 bytes = 4.352 * 10^11 bytes = ~435 GB. **Senior-level callouts.** 1. **RAM-residency is structural, not configurable.** HNSW search performs ~50-200 distance computations per query, each requiring access to a vector and its neighbor list. If any portion lived on disk, per-hop SSD reads would push per query latency from <1ms to 10-100ms, breaking the entire value proposition. The 435 GB must be physical RAM on a single instance (or sharded across instances with cross-shard query coordination). 2. **Production overhead pads the number by 15-25%.** OS reserved memory, allocator fragmentation (modern allocators waste 5-15% to fragmentation under typical mixed allocation patterns), index metadata (entry points, layer tables, ID mappings), live-write buffers, and observability tooling all add up. Realistic sizing: 500-525 GB total RAM commitment. 3. **Tombstones from deletions inflate the working set.** HNSW deletions are universally implemented as soft deletes (tombstones); the node remains in the graph but is filtered from results. Memory is reclaimed only on rebuild.

Quick reference

TL;DR

Per-vector: 4 * 1024 = 4096 bytes. Per-node edges: ~256 bytes at M=32 (2*M at base + hierarchy decay). Per-node total ~4352 bytes. 100M nodes ~= 435 GB. Pad ~20% for overhead, land ~500-525 GB.

Memory aid

Easy to grasp

Think of HNSW like a huge interconnected card catalogue that has to live entirely on a single desk. Each vector is 1024 numbers, each 4 bytes, so 4 KB per card. With 100 million cards that's 400 GB just for the cards themselves. The cross-reference web that lets the search hop quickly between cards adds another ~25 GB. Total: about 425-450 GB of raw cost, padded to ~500 GB for operating-system overhead. **The key catch:** all of it has to stay on the desk (RAM) because the search hops hundreds of times per query, and walking to a filing cabinet (disk) for each hop would destroy performance. Once you cross this threshold on a single machine, you switch to DiskANN (lives on SSD), IVF-PQ (squeezes vectors 100x), or shard across machines.

Key concepts

HNSW

Detailed answer & concept explanation

~5 min read

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.

Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example.

Quick scan · 2–4 min

Everything important, quickly.

5 min: walk through the per-node calculation (vector + graph), multiply to ~435 GB, name the RAM-residency requirement, add the ~20% production padding, and map the number to the DiskANN / IVF-PQ / sharding decision threshold.

Side-by-side

Architecture	Per-vector RAM	Per-vector SSD	Total for 100M @ 1024-dim	Per-query latency	Recall ceiling
HNSW (M=32, fp32)	~4.35 KB	0	~435 GB	<1 ms	~0.97-0.99
HNSW (M=32, SQ-int8)	~1.35 KB	0	~135 GB	<1 ms	~0.96-0.98
HNSW (M=32, BQ)	~256 bytes	0	~25 GB	<1 ms	~0.92-0.97 (binary-aware)
IVF-PQ (pq_m=32)	~32-64 bytes	0	~5-10 GB	~3-10 ms	~0.85-0.92
DiskANN	~64-128 bytes (PQ)	~4 KB	~10 GB RAM + 400 GB SSD	~5-15 ms	~0.95-0.98

Real-world examples

Real products, models, and research that use this idea.

AWS r6i.x32large (1 TB RAM, ~$8/hr) is a typical instance choice for 100M-vector HNSW indexes.
Pinecone serverless transparently transitions to disk-backed storage past similar thresholds, hiding the cost cliff from users.
Milvus and Vespa both ship DiskANN as the recommended path at billion-scale.
Glean, Notion, and other B2B RAG products at the 100M-vector scale typically run sharded HNSW on multiple r6i.4xlarge instances.
ANN-Benchmarks routinely reports memory footprint alongside recall and latency, and the HNSW-at-M=32 numbers match the ~4.3 KB-per-vector estimate.

Interviewer follow-ups

What an interviewer would ask next. Try answering before peeking at the approach.

QHow does the per-node graph cost change if we switch to int8 SQ for the vectors?

QWhy don't HNSW implementations use 8-byte (uint64) node IDs by default?

QHow does the math change for 100M * 3072-dim (e.g., OpenAI text-embedding-3-large)?

Don't say this

Red flags and common mistakes that signal junior thinking. Click to expand.

Most common mistake

Forgetting that the full vectors must stay RAM-resident. HNSW graph traversal does distance computations at every hop, so any disk involvement would push per query latency from sub-millisecond to tens of milliseconds. This is what makes the ~400 GB number a hard constraint, not a soft one.

60-second cheat sheet

The night-before-the-interview bullets. Scan these on the way to the call.

References

Primary sources. Skim if you want the original framing.