Skip to Content

HNSW (Hierarchical Navigable Small World)

When to use

Pick an ANN algorithm for high-recall, low-latency vector search — the default choice for production quality.

Analogy

A subway map layered on top of a road map. Skip layers to jump across the city; descend into finer layers to reach your destination. Each node has a few friends per layer.

Data-flow diagram

    upper layer  (sparse, long jumps)
  o   o        .   .   o
   .   .  .   .   .  .    .   .  .
    lower layer (dense, local steps)
  o-o-o-o-o-o-o-o-o-o-o-o-o

  search: top-down, greedy descent

Deep explanation

HNSW (Malkov & Yashunin 2018) is the workhorse ANN algorithm for vector databases. It builds a multi-layer graph where each entry layer has progressively fewer nodes. Queries start at the top, greedily descend to nearest neighbours, then continue at lower layers. Effective nearest-neighbour in logarithmic-ish time with very high recall. Two key parameters: M (degree per node) and ef_construction (build-time accuracy). Higher M = more memory but better recall; ef_construction higher = slower build but tighter graph. Default values (M=16, ef_construction=64) work for most production setups.

Examples

Example 1

# Postgres pgvector
sql
CREATE INDEX idx_chunks_hnsw ON chunks
USING hnsw (embedding vector_cosine_ops)
WITH (m=16, ef_construction=64);

hnsw with default M=16 ef_construction=64 is a sensible production starting point.

Example 2

-- tune at query time
SET hnsw.ef_search = 100;     -- higher = slower but more recall
SELECT id, content
  FROM chunks
 ORDER BY embedding <=> :query_vec
 LIMIT 5;

ef_search higher than ef_construction trades latency for higher recall at runtime.

Example 3

# faiss HNSW index
efaiss
import faiss, numpy as np
d = 1536
index = faiss.IndexHNSWFlat(d, 16)         # M=16
index.hnsw.efConstruction = 64
index.hnsw.efSearch = 100
index.add(np.random.random((100000, d)).astype('float32'))

faiss IndexHNSWFlat matches pgvector semantics; benchmarks on the actual corpus before committing.

Common mistake

Setting M=64 to chase recall. Memory grows quadratically; you may run out of RAM before you run out of vectors.

Key takeaway

HNSW is the default ANN algorithm. Tune M and ef_construction at build, ef_search at query. Always benchmark on production data.

Production Failure Playbook

Failure scenario 1: memory-blowup

Failure scenario 2: ef-search-too-low