HNSW

HNSW (Hierarchical Navigable Small World) is the default ANN index in most modern vector stores. It builds a multi-layer graph. The bottom layer contains every vector, densely linked to nearby neighbors. Upper layers are successively sparser "highways" with long-range edges.

Search starts at the top, greedily walks to the neighbor closest to the query, then drops a layer and repeats. Upper layers jump across the space. The bottom layer refines locally.

A highway system is the usual picture. You take the interstate to the right city, then local streets to the address. The analogy breaks because the graph is built from your vectors, not from a map, and a bad build (efConstruction too low) leaves missing on-ramps.

Parameters

Rule of thumb: start with M around 16–32, efConstruction 100–200, tune efSearch online (32–128+) until recall plateaus. OpenSearch and others publish configuration portfolios. Always validate on your vectors.

Inserts are not free. Each new point must be connected into multiple layers. Bulk-building from a static snapshot is faster and usually higher quality than inserting one vector at a time with a low efConstruction. For streaming corpora, batch upserts (every N minutes or N documents) and periodically rebuild if recall drifts.

Walking through memory

Vectors:     10,000,000
Dimensions:  1,024
Precision:   float32 (4 bytes)

Raw payload = 10e6 × 1024 × 4
            = 40,960,000,000 bytes
            ≈ 38.1 GiB   (often quoted as "~40 GB")

HNSW overhead (edges, links): commonly another ~1–2×
→ plan on ~80–120 GiB RAM for a comfortable in-memory HNSW of this size

Parameters tuned at 1M vectors may under-recall at 20M with the same efSearch. Re-measure after growth.

Common mistakes

• Raising M to fix recall when you are already RAM-bound. Try efSearch first, then PQ or disk.
• Inserting one vector at a time with a low efConstruction. Bulk-build when you can.
• Never rechecking recall after the corpus grows 10×.

Check yourself

1. efSearch=32 gives recall@10 = 0.88 at 8 ms. You need ≥ 0.95. What do you try first? Raise efSearch (to around 64 in the example) and re-measure latency.
2. Why can 10M × 1,024 float32 vectors need ~80–120 GiB with HNSW? Raw vectors are ~40 GB. Graph edges often add another 1–2×.

Key takeaways

• HNSW walks sparse upper layers, then a dense bottom layer.
• Tune M, efConstruction and efSearch. Start with M 16–32.
• Budget several times the raw vector RAM.
• Bulk-build when you can. Re-measure recall after the corpus grows.

Further learning

HNSW graphs (Malkov & Yashunin)We present a new approach for the approximate K-nearest neighbor search based on navigable small world graphs with controllable hierarchy (Hierarchical NSW, HNSW). The proposed solution is fully graph-based, without a…arXiv.org

OpenSearch: practical HNSW hyperparametersStruggling to balance search quality and speed in your LLM applications? This post dives into optimizing HNSW for vector search, offering pre-computed configurations to help you achieve better recall and throughput wi…OpenSearch

Next, indexes for when HNSW no longer fits: IVF, PQ and DiskANN.