Explain HNSW and its main parameters.

30-second answer

HNSW builds a layered proximity graph: sparse upper layers for long jumps, a dense bottom layer with every vector. Search greedily walks from an entry point toward the query, descending layers. M controls edges per node (recall and memory), efConstruction controls build quality, efSearch controls query-time candidate list size (recall vs. latency). It gives high recall at low latency but uses significant memory.

Try answering out loud before reading on. The walkthrough below is paced for a 40-minute interview round.

0–5 min Clarify and frame

Framing: "HNSW is a graph-based approximate nearest neighbour index. I'll explain the structure, the search algorithm, the parameters, and its operational costs."

5–15 min Core explanation

Exact nearest neighbour search compares the query to every vector: O(N·d). HNSW makes search roughly logarithmic by navigating a graph.

Structure:

Every vector is a node in the bottom layer (layer 0), connected to its nearest neighbours.
Each node is also placed in higher layers with exponentially decreasing probability, like a skip list. Upper layers are sparse with long-range links.

Search:

Start at an entry point in the top layer.
Greedily move to the neighbour closest to the query until no improvement.
Drop to the next layer and repeat.
On layer 0, run a best-first search keeping a candidate list of size efSearch; return the top k.

Insertion: pick a level for the new node, search down to find its neighbours at each level, connect up to M neighbours using a heuristic that keeps diverse directions.

15–25 min Deep dive: parameters

Parameter	Effect	Typical
`M`	Max links per node. Higher → better recall, more memory, slower build	16–64
`efConstruction`	Candidate list at build time. Higher → better graph, slower build	100–500
`efSearch`	Candidate list at query time. Higher → better recall, slower queries	50–500 (≥ k)

efSearch is the runtime knob: you can tune the recall/latency curve per query without rebuilding.

Memory ≈ vectors (N × d × 4 bytes for float32) + graph (N × M × ~2 × 4 bytes for neighbour IDs on layer 0). For 10M vectors of 1024 dims: ~40 GB of vectors plus a few GB of graph.

25–32 min Trade-offs

Strengths:

High recall (often >95%) at low latency.
Supports incremental inserts without retraining.

Weaknesses:

Memory-heavy (everything in RAM for best performance).
Deletes are awkward (tombstones, periodic rebuilds).
Filtered search can break graph connectivity when filters are very selective; databases mitigate with filter-aware traversal or fallback to brute force on small filtered sets.
Build time is substantial at large scale.

Compression (scalar/binary quantization with re-scoring) reduces memory.

32–37 min Production example

A product-search service with 20M items used HNSW with M=32. At efSearch=64 p99 latency was 8 ms with 93% recall@10; raising to 128 brought recall to 97% at 14 ms. Since a reranker followed, they picked 128 for better candidates. Memory pressure led them to int8 scalar quantization with full-precision re-scoring of the top 200, halving RAM with negligible recall loss.

37–40 min Likely follow-ups

How do you measure recall for ANN? Compare against exact brute-force results on a sample of queries.
Why hierarchical layers? They provide long jumps early so search reaches the right region in few steps.
HNSW on disk? Possible but slower; disk-oriented indexes (e.g. DiskANN-style) are designed for that.

What interviewers listen for

Layered graph + greedy search explained clearly.
Knowing which parameter is build-time vs. query-time.
Memory, deletes and filtering caveats.

Red flags

Calling HNSW exact.
Not knowing how to measure ANN recall.