HNSW — Layers, Greedy Search, M and ef
HNSW is a stack of proximity graphs. Layer 0 holds every vector, and each higher layer keeps an exponentially smaller sample. A query greedily walks the sparse top layers, then runs a beam of width efSearch on layer 0. M, efConstruction, and efSearch are the three knobs that set memory, graph quality, and the recall versus latency dial.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What lives on layer 0, and what lives above it?
Answer
Every vector is on layer 0. Each higher layer keeps about 1/M of the layer below, drawn from an exponential distribution, so there are about log base M of N layers.
L2
What are the two phases of search?
Answer
Greedy descent with ef 1 from the global entry point down to layer 1, then a best-first beam of width efSearch on layer 0. Return the top k of that beam.
L3
What do M, efConstruction, and efSearch each control?
Answer
M is links per node: memory and the recall ceiling. efConstruction is the beam during insert: graph quality and build time. efSearch is the beam at query time, and it does not need a rebuild.
L4
Why not keep the M closest neighbors?
Answer
Closest-only links form cliques inside clusters and no bridges between them. The diversity heuristic keeps a candidate only when it is closer to the new node than to any neighbor already kept.
L5
Recall is stuck at 0.9 no matter how high efSearch goes. Why?
Answer
The graph cannot reach some neighbors. M or efConstruction is too low, the heuristic is off, deletes left holes, or a filter stranded the walk. Rebuild, compact, or fix the filter. Also check the metric.
L6
Estimate HNSW memory for 10 million 768-d fp32 vectors at M = 16.
Answer
Vectors are 10 million times 768 times 4, about 30.7 GB. Layer-0 links are 10 million times 32 times 4 bytes, about 1.3 GB, plus about 10 percent for upper layers. About 32 GB per copy before replicas. int8 cuts vectors to about 7.7 GB.
L7
HNSW or IVF for a write-heavy workload?
Answer
HNSW inserts without retraining, but each insert is a search and deletes degrade the graph. IVF inserts are an assignment to a centroid, then centroids drift. Buffer into a small segment and merge, which is what Lucene does.
Failure modes
efSearch raised, recall flat
The graph is the ceiling. Rebuild with a higher M or efConstruction. Query-time beam width cannot invent missing bridges.
Deletes left in place
Tombstones break paths. Recall and hop count both rot. Compact or rebuild past roughly 20 to 30 percent dead nodes.
Selective filter on a plain walk
The matching nodes are not connected. The filtered page owns the strategies. Do not pretend efSearch fixes a disconnected walk.
One tiny graph per segment
Lucene searches every segment graph. Too many small segments multiply overhead. Force-merge read-only indexes.
Misconceptions
efSearch, M, and efConstruction are all query-time knobs.
Only efSearch changes without a rebuild. M and efConstruction shape the graph.
Greedy search with ef 1 is enough on layer 0.
ef 1 stops at a local minimum. The beam exists to keep runner-up paths alive.
You can update a vector in place.
Most engines tombstone and re-insert. Lucene writes a new document into a new segment.
Interviewer traps
Quoting efSearch = 128 as a universal default.
efSearch must be at least k. Sweep it against an exact oracle. If the curve plateaus, the graph is the problem.
Reciting the HNSW paper abstract and skipping the bytes.
Give the 10 million by 768 fp32 estimate, then say what int8 changes.
Design scenario
Same prompt for every reader.
Requirements
Recall at 10 at least 0.95, interactive p99, and a compaction story for deletes.
Traffic / scale
10 million vectors, online queries, a steady insert rate, and deletes that can reach tens of percent between compactions.
Latency
The layer-0 beam dominates. Upper layers stay a handful of greedy hops.
Consistency
Builds are order-dependent, so two replicas can differ at the margin. Recall is measured per copy.
Availability
The graph must fit in RAM. A page fault is an availability bug, not a slow query.
Failure assumptions
- efSearch climbs and recall does not.
- Deleted documents stay in the graph until a merge.
- A filter is applied by deleting edges instead of walking through non-matches.
Constraints
- Name M, efConstruction, and efSearch as three different times.
- Do not promise in-place updates.
Prompt
Serve 10 million 768-d vectors with HNSW on nodes that have a fixed RAM budget, with a weekly delete rate.
API
Which parameter can a query change, and which parameters require a reindex?
Data
What is stored per node on layer 0, and how many bytes is that?
Architecture
Where do tombstones get compacted, and who owns the filter walk?
Search, then insert
Search and insert share the same walk. Insert adds links. Query only reads them.
- 1
Enter on the top layer
One global entry point sits on the highest layer. Greedy search with ef 1 hops to any neighbor closer to the query. - 2
Drop until layer 0
When no neighbor is closer, drop one layer and keep the current node as the entry. Repeat until the bottom. - 3
Beam-search layer 0
A min-heap is the frontier. A bounded max-heap holds the best efSearch results. Stop when the closest unexplored node is already worse than the worst result you are keeping. - 4
Link on insert
Draw a level, descend to it, beam-search with efConstruction, keep M diverse neighbors, link both ways, and prune anyone who overflowed.
Overview
HNSW is the default ANN index in most vector stores because it has the best recall-latency curve when the vectors fit in RAM. It is a stack of proximity graphs. Layer 0 contains every vector. Each higher layer keeps an exponentially smaller random sample. A query greedily walks the sparse top layers to get close fast, then runs a beam search of width efSearch on layer 0.
Inserts use the same search to find neighbors, link bidirectionally, and prune with a diversity heuristic. Three knobs matter: M (links per node, memory and recall), efConstruction (build-time beam, graph quality), and efSearch (query-time beam, the recall versus latency dial).
The metric itself is not this page. If you are unsure whether the model wants cosine or dot product, start at Embeddings & Similarity — Dense Vectors, Metrics & Chunking Basics. A dense_vector field inside a search mapping is Inverted Index, Analyzers, Tokenization & Mappings.
The structure
- Each node gets a random top level
L = floor(-ln(U) times mL), withmL = 1 / ln(M). About 1/M of nodes reach layer 1, 1/M squared reach layer 2, and so on, so there are about log base M of N layers. - On every layer it lives in, a node keeps up to M links. Layer 0 allows 2M in hnswlib and Lucene.
- One global entry point sits on the top layer.
The Python sandbox prints this for 2,000 vectors with M = 8: nodes per layer 2000, 251, 26, 2. That is the skip-list idea applied to a proximity graph. Upper layers are express lanes. Layer 0 is the local street grid.
Search, step by step
Decisions
- 1
1. Start at top-layer entry
- next2. Greedy walk, ef = 1
- 2
2. Greedy walk, ef = 1
- next3. Closer neighbor?
- ?
3. Closer neighbor?
- yes2. Greedy walk, ef = 1
- no4. Drop one layer
- 4
4. Drop one layer
- next5. On layer 0?
- ?
5. On layer 0?
- no2. Greedy walk, ef = 1
- yes6. Beam search, efSearch
- 6
6. Beam search, efSearch
- next7. Stop when frontier loses
- 7
7. Stop when frontier loses
- next8. Return top k
- 8
8. Return top k
Lesson map
HNSW — Layers, Greedy Search, M and ef
HNSW is a stack of proximity graphs. Layer 0 holds every vector, and each higher layer keeps an exponentially smaller sample. A query greedily walks the sparse top layers, then runs a beam of width efSearch on layer 0. M, efConstruction, and efSearch are the three knobs that set memory, graph quality, and the recall versus latency dial.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB entry["1. Start at top-layer entry"] greedy["2. Greedy walk, ef = 1"] closer["3. Closer neighbor?"] drop["4. Drop one layer"] entry -->|1. Start at top-layer entry| greedy greedy -->|2. Greedy walk, ef = 1| closer closer -->|yes| greedy closer -->|no| drop
Two structures run the beam: a min-heap of frontier candidates, and a bounded max-heap of the best ef results. The stop rule is the whole trick. If the closest unexplored node is already farther than the worst result you are keeping, nothing reachable through it can improve the answer, on a good graph.
Why the layers matter
Without layers, a flat NSW graph starts somewhere far away and spends many hops just approaching the target, and greedy routing gets trapped in local minima. The TypeScript sandbox shows a flat graph with pure greedy search (ef = 1) landing on the true nearest neighbor only about 58 to 70 percent of the time. Widening the beam fixes it, but the distance evaluations grow with N. HNSW's upper layers hand layer 0 a starting point that is already close, so the expensive beam runs over a short distance.
Insert, step by step
Decisions
- 1
1. Draw level from exponential
- next2. Greedy descent above level
- 2
2. Greedy descent above level
- next3. Closest node is the entry
- 3
3. Closest node is the entry
- next4. Beam search, efConstruction
- 4
4. Beam search, efConstruction
- next5. Keep M diverse neighbors
- 5
5. Keep M diverse neighbors
- next6. Add bidirectional links
- 6
6. Add bidirectional links
- next7. Prune overflow neighbor lists
- 7
7. Prune overflow neighbor lists
- next8. Level above current top?
- ?
8. Level above current top?
- yes9. New node becomes entry
- no9. Insert complete
- 9
9. New node becomes entry
- 10
9. Insert complete
- Draw level
lfrom the exponential distribution. - Greedy ef = 1 descent from the entry point down to layer
l + 1. - The closest node found becomes the entry for layer
l. - On each layer from
ldown to 0, beam-search with efConstruction. - Sort that candidate list by distance.
- Select M neighbors with the diversity heuristic.
- Add bidirectional links.
- Neighbors over capacity prune their own lists.
- If
lis above the current top, the new node becomes the global entry point.
The neighbor selection heuristic
Keeping simply the M closest candidates creates tight cliques inside clusters and no links between clusters, so search cannot cross from one region to another. The heuristic keeps a candidate only if it is closer to the new node than to any neighbor already kept. Links point in diverse directions, including a few longer bridges. In the sandbox, with M = 4, the heuristic is the difference between recall 0.97 and 0.69 at efSearch = 160.
The knobs
| Knob | When set | Raises | Costs | Typical values |
|---|---|---|---|---|
| M | Build time | Recall ceiling, robustness on clustered data | RAM, about M times 2 times 4 bytes per vector on layer 0, and slower hops | 12 to 48; 16 is a common default |
| efConstruction | Build time | Graph quality, recall at a given efSearch | Build time, roughly linear in it | 100 to 512 |
| efSearch | Query time | Recall | Latency, roughly linear in it | k to a few thousand; start by sweeping |
| mL | Build time | Layer spacing | Rarely touched | 1 / ln(M) |
Product names for efSearch: efSearch in hnswlib and Faiss, num_candidates in Lucene and Elasticsearch (per shard), ef_search in OpenSearch, hnsw.ef_search in pgvector, hnsw_ef in Qdrant, ef in Weaviate.
Rules of thumb:
- efSearch is the only knob you can change without a rebuild, so use it to hit the recall target.
- If recall plateaus below the target as efSearch rises, the graph is the problem. Raise M or efConstruction and rebuild.
- efSearch must be at least k. Elasticsearch requires
num_candidatesat least k.
Sandbox: a small HNSW
Upper layers are sparse. Layer 0 holds every node, and the ef-sized beam there is what buys recall. M and efConstruction are build-time. The diversity heuristic keeps long-range links so the graph does not fragment into cliques.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Seeded reading:
- With M = 8 and the heuristic, nodes per layer are 2000, 251, 26, 2. Recall rises 0.73, 0.86, 0.95, 0.99, 1.00 as efSearch doubles, and distance calls rise roughly linearly.
- Halving M to 4 lowers the recall ceiling at the same efSearch. Build-time choices cap what query-time tuning can buy. At efSearch 160, recall is about 0.97.
- Turning the heuristic off at M = 4 caps recall near 0.69 even at efSearch 160. The graph fragments into cluster cliques.
- The percent-of-N column is high only because N is 2,000. At 10 million vectors the same efSearch visits a tiny fraction of the corpus.
Sandbox: flat NSW and greedy traps
ef = 1 is pure greedy. It stops at a local minimum, which is often not the true nearest neighbor. A wider beam keeps runner-up paths alive. Without layers, a search that starts far away needs many short hops, and the hop count grows with N.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Seeded reading: at N = 500, ef = 1 hits the true nearest neighbor about 0.70 of the time. At N = 8,000 that greedy hit rate is about 0.58. A beam of 10 or 50 restores top-1 and pushes recall at 10 toward 1, and the distance evaluations creep up with N. HNSW's upper layers exist so that beam does not have to start at a fixed, usually far, node 0.
Where HNSW hurts
| Pain | Why | Mitigation |
|---|---|---|
| Memory | Full vectors plus links in RAM. Random access means it must be RAM, not disk | Scalar or binary quantization with re-score, or DiskANN |
| Deletes | Removing a node breaks paths through it | Tombstones, periodic rebuild or merge, hnswlib mark-deleted plus replace |
| Restrictive filters | The walk passes through non-matching nodes, or strands if you delete those edges | Filter-aware traversal, exact fallback, two-hop expansion. The filter page owns this |
| Build time | Each insert is a search | Parallel build, bulk load then merge, GPU builders |
| Segment merges | Each Lucene segment has its own graph. Merging rebuilds graphs | Fewer, larger segments. Force-merge read-only indexes |
| Many small graphs | Each shard and segment is searched separately | Fewer shards. The production page owns fan-out |
Interview Q&A
Explain HNSW in 60 seconds.
Answer
A multi-layer proximity graph. Every vector is on layer 0, and a random geometric sample sits on each layer above. Search greedily descends the top layers to find a good entry, then runs a best-first beam of width efSearch on layer 0 and returns the top k. Inserts run the same search and link to M diverse neighbors in both directions. It is a skip list for nearest neighbors.
What do M, efConstruction, and efSearch each control?
Answer
M sets links per node: memory, the recall ceiling, and robustness. efConstruction sets the beam width during inserts: graph quality and build time. efSearch sets the beam width at query time: recall versus latency, tunable per query without a rebuild.
Recall is stuck at 0.9 no matter how high you set efSearch. Why?
Answer
The graph cannot reach some neighbors. M is too low, efConstruction is too low, the diversity heuristic is off, heavy deletes left holes, or a filter stranded the walk. Rebuild with higher M or efConstruction, compact deletes, or fix the filter strategy. Also check that the metric matches the model.
Estimate HNSW memory for 10 million 768-d fp32 vectors, M = 16.
Answer
Vectors: 10 million times 768 times 4 is 30.7 GB. Layer-0 links: 10 million times 32 times 4 bytes is 1.3 GB, plus about 10 percent for upper layers. About 32 GB per copy before replicas and headroom. int8 cuts the vectors to 7.7 GB.
Why is HNSW search roughly logarithmic?
Answer
The layer count is about log base M of N. On each upper layer, greedy search takes a small, roughly constant number of hops because that layer is a navigable small world at that scale. Layer 0 then costs about efSearch times M distance computations. In practice the cost grows slowly with N for a fixed recall.
Can you update a vector in place?
Answer
Not cleanly. Most engines delete with a tombstone and re-insert. Lucene writes a new document into a new segment, and the old one is filtered until merge. Heavy update rates call for periodic rebuilds and a deleted-document ratio you actually alert on.
HNSW versus IVF for a write-heavy workload?
Answer
HNSW supports incremental inserts without retraining, but each insert is expensive and deletes degrade it. IVF inserts are cheap, an assignment to a centroid, but centroids drift and need retraining. For bursty writes, buffer into a small flat or HNSW segment and merge. That is what Lucene and many vector databases do.
Why does layer 0 allow more links than the upper layers?
Answer
hnswlib and Lucene keep up to 2M links on layer 0 and M above it. The bottom layer is where recall is won. The upper layers only need to be navigable enough to deliver an entry point.
Pitfalls
Sketch three layers, pick a level for a new node, mark the greedy hops above that level, and circle the M links you keep. Say which of those links a closest-only rule would have dropped, and why the beam still needs them.