- Book: AI That Reads
- The series: AI in TypeScript — 5 books, from your first LLM call to agents in production — all five here
- My project: Hermes IDE | GitHub — an IDE for developers who ship with Claude Code and other AI coding tools
- Me: xgabriel.com | GitHub
The pgvector README says it in one line: adding an approximate index "trades some recall for speed", and your results will differ from an exact scan once it is there. The default HNSW search setting, hnsw.ef_search, is 40. If your RAG app runs on Postgres and nobody on the team has ever changed hnsw.ef_search, then 40 is the number deciding which chunks your model gets to read.
Qdrant has the same dial under a different name, hnsw_ef, passed per request. Different databases, same algorithm, same trade.
You can read about that trade, or you can build the index yourself and watch it happen. Below, you write a small HNSW in TypeScript, index 50,000 random vectors in Node, and measure recall@10 against brute force at efSearch 10, 40, 100 and 200. The script is deterministic and short enough to read in one sitting, and every number it prints comes from your machine.
Three ideas: layers, greedy descent, a beam
HNSW comes from a 2016 paper by Malkov and Yashunin on approximate nearest neighbor search with Hierarchical Navigable Small World graphs. Strip away the proofs and three ideas remain.
Layers. Every vector lives on layer 0. A random few also live on layer 1, fewer still on layer 2, and so on. The paper draws each element's top layer as floor(-ln(uniform) * mL) and suggests mL = 1/ln(M), where M is the number of links per node. That gives you something shaped like a skip list: a sparse top for long jumps, a dense bottom for precision.
Greedy descent. A query starts at a single entry point on the top layer and walks to whichever neighbor is closer, until nothing is closer. Then it drops one layer and repeats from there. In the paper's search algorithm, the upper layers run with ef = 1: one candidate, pure greed.
A beam on layer 0. On the bottom layer the search keeps a list of the ef best nodes found so far and keeps expanding the nearest unexpanded one. It stops when the nearest unexpanded candidate is farther than the worst node in the list. That ef is efSearch. A bigger beam explores more of the graph, finds more true neighbors, and computes more distances.
HNSW in one picture: long hops on the sparse top layers, a wide beam on the dense bottom layer.
Building the graph reuses the same search. To insert a vector you search for its neighbors with a beam of efConstruction, link it to up to M of them on each of its layers, and trim any neighbor that now has too many links. The paper recommends 2·M links on layer 0; this version caps every other layer at M.
Helpers first
Everything below goes in one file, hnsw.ts: append each code block in order. Node runs .ts files directly since v22.18.0 and v23.6.0 by stripping the types, so there is no build step. The code avoids enums and parameter properties, which type stripping does not support.
// hnsw.ts: run with `node hnsw.ts` (Node 22.18+) type Vec = Float32Array; type Hit = { id: number; d: number }; // mulberry32: tiny seeded PRNG, same data every run function mulberry32(seed: number): () => number { let a = seed >>> 0; return () => { a = (a + 0x6d2b79f5) >>> 0; let t = a; t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61); return ((t ^ (t >>> 14)) >>> 0) / 4294967296; }; } function randomUnit(dim: number, rand: () => number): Vec { const v = new Float32Array(dim); let norm = 0; for (let i = 0; i < dim; i++) { v[i] = rand() * 2 - 1; norm += v[i] * v[i]; } norm = Math.sqrt(norm); for (let i = 0; i < dim; i++) v[i] /= norm; return v; } The generator is seeded, so every machine builds the same 50,000 vectors and two readers' runs are comparable. Next come the distance function and a sorted insert.
// squared L2; on unit vectors it ranks like cosine function dist(a: Vec, b: Vec): number { let s = 0; for (let i = 0; i < a.length; i++) { const d = a[i] - b[i]; s += d * d; } return s; } // keep `arr` sorted by distance, nearest first function insertSorted(arr: Hit[], h: Hit): void { let lo = 0; let hi = arr.length; while (lo < hi) { const mid = (lo + hi) >> 1; if (arr[mid].d < h.d) lo = mid + 1; else hi = mid; } arr.splice(lo, 0, h); } The vectors are normalized, so squared Euclidean distance orders results the same way cosine similarity does: for unit vectors, |a - b|² = 2 - 2·cos(a, b). A sorted array stands in for the two priority queues the paper uses. It is slower than a heap, but at beam sizes of a few hundred it stays readable and correct, which matters more here.
Brute force is the answer key. It scores every vector and keeps the k closest.
function bruteForce(data: Vec[], q: Vec, k: number): number[] { const best: Hit[] = []; for (let id = 0; id < data.length; id++) { const d = dist(q, data[id]); if (best.length < k || d < best[best.length - 1].d) { insertSorted(best, { id, d }); if (best.length > k) best.pop(); } } return best.map((h) => h.id); } Insert and search
searchLayer is the paper's Algorithm 2, selectNeighbors is its neighbor heuristic (Algorithm 4, without the optional extensions), and insert and search follow Algorithms 1 and 5.
class HNSW { M: number; M0: number; efC: number; mL: number; rand: () => number; vecs: Vec[] = []; links: number[][][] = []; // links[node][layer] -> ids entry = -1; maxLayer = -1; constructor(M: number, efC: number, rand: () => number) { this.M = M; this.M0 = 2 * M; // layer 0 gets twice the links this.efC = efC; this.mL = 1 / Math.log(M); this.rand = rand; } // beam search on one layer, returns the ef best searchLayer(q: Vec, eps: number[], ef: number, lc: number) { const seen = new Set<number>(eps); const cand: Hit[] = []; const best: Hit[] = []; for (const id of eps) { const h = { id, d: dist(q, this.vecs[id]) }; insertSorted(cand, h); insertSorted(best, h); } while (cand.length > 0) { const c = cand.shift()!; if (c.d > best[best.length - 1].d) break; for (const n of this.links[c.id][lc]) { if (seen.has(n)) continue; seen.add(n); const d = dist(q, this.vecs[n]); const worst = best[best.length - 1].d; if (best.length < ef || d < worst) { insertSorted(cand, { id: n, d }); insertSorted(best, { id: n, d }); if (best.length > ef) best.pop(); } } } return best; } // keep a candidate only if it is closer to the base // than to every neighbor already kept selectNeighbors(cands: Hit[], m: number): number[] { const kept: Hit[] = []; for (const c of cands) { if (kept.length >= m) break; let ok = true; for (const k of kept) { if (dist(this.vecs[c.id], this.vecs[k.id]) < c.d) { ok = false; break; } } if (ok) kept.push(c); } return kept.map((h) => h.id); } shrink(n: number, lc: number, cap: number): void { const base = this.vecs[n]; const hits = this.links[n][lc] .map((id) => ({ id, d: dist(base, this.vecs[id]) })) .sort((a, b) => a.d - b.d); this.links[n][lc] = this.selectNeighbors(hits, cap); } insert(v: Vec): void { const id = this.vecs.length; const level = Math.floor(-Math.log(1 - this.rand()) * this.mL); this.vecs.push(v); const layers: number[][] = []; for (let l = 0; l <= level; l++) layers.push([]); this.links.push(layers); if (this.entry < 0) { this.entry = id; this.maxLayer = level; return; } let ep = [this.entry]; for (let lc = this.maxLayer; lc > level; lc--) { ep = [this.searchLayer(v, ep, 1, lc)[0].id]; } for (let lc = Math.min(level, this.maxLayer); lc >= 0; lc--) { const found = this.searchLayer(v, ep, this.efC, lc); const nbrs = this.selectNeighbors(found, this.M); this.links[id][lc] = nbrs; const cap = lc === 0 ? this.M0 : this.M; for (const n of nbrs) { this.links[n][lc].push(id); if (this.links[n][lc].length > cap) { this.shrink(n, lc, cap); } } ep = found.map((h) => h.id); } if (level > this.maxLayer) { this.maxLayer = level; this.entry = id; } } search(q: Vec, k: number, ef: number): number[] { let ep = [this.entry]; for (let lc = this.maxLayer; lc > 0; lc--) { ep = [this.searchLayer(q, ep, 1, lc)[0].id]; } const found = this.searchLayer(q, ep, Math.max(ef, k), 0); return found.slice(0, k).map((h) => h.id); } } 1 - this.rand() keeps the logarithm away from ln(0), because the generator can return 0 but never 1. search also clamps the beam to at least k, matching the hnswlib parameter notes: ef "cannot be set lower than the number of queried nearest neighbors k".
The neighbor heuristic is what keeps the graph navigable. Linking to the M closest points sounds right, but in clustered data the links stay inside each cluster and the search gets stuck at cluster boundaries. The paper's figure 7 shows this: the simple rule stalls at low recall on clustered data while the heuristic, with its candidate-extension option on, does not.
The benchmark: recall@10 against brute force
Append this to the same file. It builds the index with M = 16 and efConstruction = 64, which are pgvector's defaults, computes exact answers by brute force, then sweeps efSearch.
const N = 50_000; const DIM = 64; const Q = 500; const K = 10; const rand = mulberry32(42); const data: Vec[] = []; for (let i = 0; i < N; i++) data.push(randomUnit(DIM, rand)); const queries: Vec[] = []; for (let i = 0; i < Q; i++) queries.push(randomUnit(DIM, rand)); let t0 = performance.now(); const index = new HNSW(16, 64, rand); // pgvector defaults for (const v of data) index.insert(v); const buildS = (performance.now() - t0) / 1000; console.log(`build: ${buildS.toFixed(1)} s`); console.log(`top layer: ${index.maxLayer}`); t0 = performance.now(); const truth = queries.map((q) => bruteForce(data, Source：https://dev.to/gabrielanhaia/build-hnsw-in-typescript-and-watch-recall-fall-as-you-lower-efsearch-14im Related posts
FiveM Script Database Migrations: What to Check Before You Install
The insurance edge case that breaks event-driven policy pipelines
The fix for an empty state isn't filling it
Five Things That Make Dependabot Painful for Terraform
Tracking Roblox player counts: what the public data actually gives you
