Hierarchical Navigable Small World (HNSW) Graphs

Layered small-world graphs answer nearest-neighbour queries in milliseconds, trading exact recall and memory for speed.

Part 1 of 5

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.

Why it matters

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.

01Approximate nearest neighbour

Finds most of the true closest vectors, far faster than checking them all.

02Recall@k

Measures the share of the true top k that the index returned.

03Layer assignment

Gives each vector a random top layer, with higher layers exponentially rarer.

04M

Sets how many links each node keeps. It drives both recall and memory.

05efConstruction

Sets how widely inserts search for neighbours. It costs build time only.

06efSearch

Sets how many candidates a query tracks. It trades latency for recall at query time.

Part 2 of 5

Question

What exactly you must answer, and what to settle before you start.

2.1Question

Interviewer

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 askAnswer
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.
Part 3 of 5

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.

  1. Assign a level

    Each new vector draws a random top layer. Most stay at layer 0.

  2. Insert from the top

    Walk greedily down to the vector's top layer, then search with efConstruction on each lower layer.

  3. Link the neighbours

    Connect to the M closest nodes found, and trim any neighbour that now has too many links.

  4. Search greedily

    A query walks each upper layer to its closest node, using that as the entry for the next layer.

  5. 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.

KnobRaisesCosts
MRecall and connectivityMemory per vector, build time
efConstructionGraph qualityBuild time only
efSearchRecallLatency 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.

hnsw.tsTypeScriptCopy
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}
77 linesUTF-8TypeScript
-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.

Part 4 of 5

Q&A

What interviewers ask next. Answer out loud, then open.

4.1Interview questions

Why add layers at all?
Without long links, greedy search takes many short hops and gets stuck in local clusters. Layers give roughly logarithmic search.
HNSW or IVF?
IVF clusters vectors and scans a few lists. It uses less memory and pairs well with product quantisation. HNSW gives higher recall at low latency but holds links in RAM.
Why does recall drop over time?
Deletes leave tombstones and weaken the graph. Heavy churn needs periodic rebuilds.
Part 5 of 5

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.