Basics
The whole idea first, then the terms the rest of this page uses.
1.1Whole idea
Comparing a query with a million vectors takes too long. HNSW builds a stack of graphs: sparse top layers for long jumps, and a dense bottom layer holding everything. Search starts at the top, walks greedily towards the query, then drops a layer, like taking a motorway, then main roads, then side streets.
Layered small-world graphs answer nearest-neighbour queries in milliseconds, trading exact recall and memory for speed.
1.2Key concepts
One idea per card, in plain words.
Finds most of the true closest vectors, far faster than checking them all.
Measures the share of the true top k that the index returned.
Gives each vector a random top layer, with higher layers exponentially rarer.
Sets how many links each node keeps. It drives both recall and memory.
Sets how widely inserts search for neighbours. It costs build time only.
Sets how many candidates a query tracks. It trades latency for recall at query time.
Question
What exactly you must answer, and what to settle before you start.
2.1Question
Search 10 million 768-dimension embeddings in under 20 ms at 95% recall. How does HNSW get there, which knobs do you set, and how much memory do you need?
2.2Clarify first
Each answer removes a guess.
| You ask | Answer |
|---|---|
| How often does data change? | A few thousand inserts an hour, with occasional deletes. |
| Do queries filter on metadata? | Yes, by tenant. Note it now: filters change the design. |
| Is 95% recall measured against exact search? | Yes, on a held-out query set. |
Detailed answer
How it works, and how to build or explain it.
3.1Step by step
The mechanism, in the order you would explain it.
- Assign a level
Each new vector draws a random top layer. Most stay at layer 0.
- Insert from the top
Walk greedily down to the vector's top layer, then search with efConstruction on each lower layer.
- Link the neighbours
Connect to the M closest nodes found, and trim any neighbour that now has too many links.
- Search greedily
A query walks each upper layer to its closest node, using that as the entry for the next layer.
- Widen at the bottom
Layer 0 tracks efSearch candidates, which turns a greedy walk into a small best-first search.
3.2Three knobs, and what they cost
For 10 million 768-dimension FP32 vectors, the vectors alone take about 31 GB. Links at M = 16 add a few GB more.
| Knob | Raises | Costs |
|---|---|---|
| M | Recall and connectivity | Memory per vector, build time |
| efConstruction | Graph quality | Build time only |
| efSearch | Recall | Latency per query |
3.3Code
Working code for the core of it.
Nearest-neighbour search with HNSW
Comparing against every vector is too slow. HNSW walks a graph: long jumps near the top, fine steps at the bottom.
1type Vec = number[];2const dist = (a: Vec, b: Vec) => a.reduce((s, x, i) => s + (x - b[i]) ** 2, 0);3 4/** A compact HNSW: layers of small-world graphs, searched greedily from the top down. */5export class Hnsw {6 private vecs: Vec[] = [];7 private links: number[][][] = []; // links[node][layer] = neighbours8 private entry = -1;9 private top = -1;10 private M: number;11 private efConstruction: number;12 private rand: () => number;13 14 constructor(M = 16, efConstruction = 100, rand: () => number = Math.random) {15 this.M = M;16 this.efConstruction = efConstruction;17 this.rand = rand;18 }19 20 private searchLayer(q: Vec, start: number, ef: number, layer: number): number[] {21 const seen = new Set([start]);22 const candidates = [start];23 const best = [start];24 while (candidates.length > 0) {25 candidates.sort((a, b) => dist(q, this.vecs[a]) - dist(q, this.vecs[b]));26 const c = candidates.shift()!;27 if (best.length >= ef && dist(q, this.vecs[c]) > dist(q, this.vecs[best[best.length - 1]])) break;28 for (const n of this.links[c][layer] ?? []) {29 if (seen.has(n)) continue;30 seen.add(n);31 candidates.push(n);32 best.push(n);33 best.sort((a, b) => dist(q, this.vecs[a]) - dist(q, this.vecs[b]));34 if (best.length > ef) best.pop();35 }36 }37 return best;38 }39 40 insert(v: Vec): void {41 const id = this.vecs.length;42 const level = Math.floor(-Math.log(Math.max(this.rand(), 1e-9)) / Math.log(this.M));43 this.vecs.push(v);44 this.links.push(Array.from({ length: level + 1 }, () => []));45 if (this.entry < 0) {46 this.entry = id;47 this.top = level;48 return;49 }50 let ep = this.entry;51 for (let l = this.top; l > level; l--) ep = this.searchLayer(v, ep, 1, l)[0];52 for (let l = Math.min(this.top, level); l >= 0; l--) {53 const found = this.searchLayer(v, ep, this.efConstruction, l);54 const limit = l === 0 ? this.M * 2 : this.M;55 this.links[id][l] = found.slice(0, this.M);56 for (const n of this.links[id][l]) {57 const list = this.links[n][l];58 list.push(id);59 if (list.length > limit) {60 list.sort((a, b) => dist(this.vecs[n], this.vecs[a]) - dist(this.vecs[n], this.vecs[b]));61 list.length = limit;62 }63 }64 ep = found[0];65 }66 if (level > this.top) {67 this.entry = id;68 this.top = level;69 }70 }71 72 search(q: Vec, k: number, ef = 50): number[] {73 let ep = this.entry;74 for (let l = this.top; l > 0; l--) ep = this.searchLayer(q, ep, 1, l)[0];75 return this.searchLayer(q, ep, Math.max(ef, k), 0).slice(0, k);76 }77}-Math.log(...) / Math.log(this.M)- A random level, so few nodes reach the top layers. That creates the long jumps.
for (let l = this.top; l > 0; l--)- Descends greedily, using each layer's best match as the next layer's start.
ef- How many candidates to keep. Raising it improves recall and costs time, and it's the main dial you tune.
list.length = limit- Trims each node's links, keeping memory bounded.
Tested by npm run test:modules.
Q&A
What interviewers ask next. Answer out loud, then open.
4.1Interview questions
Why add layers at all?
HNSW or IVF?
Why does recall drop over time?
Extra depth
Edge cases, counterpoints and what to read next.
5.1Edge cases and counterpoints
Includes the strongest argument against this approach.
Show detailsHide details
- Strict filters
- Filtering by a rare value can disconnect the graph. Use a filter-aware index, or fall back to exact search on small sets.
- Memory pressure
- Scalar or product quantisation compresses vectors in RAM. Keep originals on disk and rescore the top results.
- Counterpoint
- Below about 100,000 vectors, brute force often wins: exact, simple and fast enough.