The default approximate nearest-neighbors (ANN) algorithm for vector search at scale.

Data Flow

   Layer 3: few long-range edges   o - - - - o        (express train)
   Layer 2:                       /  \      | \
   Layer 1:        more edges    o - o  -  o - o       (local bus)
   Layer 0:  dense local graph   all points connected

   query --> enter top layer --> greedy descend
                                 each layer brings you closer
                                 final layer: nearest neighbour

Why it works

Each layer is a small world: average path length grows like log(N) instead of N. Searching top-down is logarithmic.

Parameters (pgvector / hnsw)

CREATE INDEX ON docs USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);
SET hnsw.ef_search = 40;

• m: edges per node; bigger = better recall, slower build, more memory.
• ef_construction: candidate list during build.
• ef_search: candidate list during query; bigger = better recall, slower query.

Pitfalls

• HNSW memory cost is high (~1.5x raw vectors in pgvector) — plan RAM carefully.
• Once built, insert is O(log N) but rebuild is the only way to change m.

Analogy

A multi-layer transit system: express buses at top, local buses at bottom; switch layers as you get closer.

Interview tip: ef_search is the recall-latency knob. Bigger it = better recall, slower query.