- 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, q, K));
const bfMs = (performance.now() - t0) / Q;
console.log(`brute force: ${bfMs.toFixed(2)} ms/query`);
With the exact answers in hand, the last block sweeps efSearch and scores each setting against them.
for (const ef of [10, 40, 100, 200]) {
const t = performance.now();
const got = queries.map((q) => index.search(q, K, ef));
const ms = (performance.now() - t) / Q;
let hits = 0;
got.forEach((ids, i) => {
const want = new Set(truth[i]);
for (const id of ids) if (want.has(id)) hits++;
});
const recall = hits / (Q * K);
console.log(
`efSearch=${ef} recall@10=${recall.toFixed(3)} ` +
`${ms.toFixed(3)} ms/query`,
);
}
Run it with node hnsw.ts. The build is the slow part: 50,000 inserts, each one a beam search in plain JavaScript with no SIMD. If you want a faster first run, drop N to 10,000.
Recall@10 is the share of the true ten nearest neighbors that HNSW returned, averaged over 500 queries. The timer wraps only the search calls, so the recall bookkeeping does not leak into the per-query time.
efSearch is a dial between finding more of the true neighbors and answering sooner.
I'm not printing a results table here, because the only numbers worth trusting are the ones your run prints. What the docs predict is the direction. pgvector says a higher ef_search gives "better recall" at the cost of speed, and hnswlib says "higher ef leads to more accurate but slower search". Your run will show by how much on your hardware, and whether the step from 40 to 100 buys you more than the step from 100 to 200.
Reading your numbers
Random vectors are the hard case. Uniform random data has no clusters, and its intrinsic dimension is close to its nominal one. A 2024 paper by Elliott and Clark links HNSW recall to the intrinsic dimensionality of the data and to insertion order, and a Marqo post on HNSW recall notes that clustered data "tends to produce higher recall than uniformly distributed data". Real text embeddings have structure, so treat your random-data recall as a pessimistic floor. Try DIM = 16 and DIM = 256 (pair the second with a smaller N, since every distance costs four times as much) and watch the same efSearch buy very different recall.
The brute-force line is your baseline. At 50,000 vectors an exact scan is cheap, and pgvector without an index does exactly that with perfect recall. HNSW starts paying for itself as N grows, because brute force scales with the corpus and the graph search, per the paper, scales roughly logarithmically.
Filters make a small beam smaller. pgvector applies WHERE filters after the index scan. Its README spells out the consequence: "If a condition matches 10% of rows, with HNSW and the default hnsw.ef_search of 40, only 4 rows will match on average." That is a top-10 query returning 4 rows. Since 0.8.0, pgvector has iterative index scans that keep scanning until enough rows pass the filter.
Turning the dial in production. In Postgres it is one setting, scoped to a transaction if you want:
BEGIN;
SET LOCAL hnsw.ef_search = 100;
SELECT id FROM chunks ORDER BY embedding <=> $1 LIMIT 10;
COMMIT;
In Qdrant you pass it per search as "params": { "hnsw_ef": 128 }, and the indexing docs say ef defaults to the ef_construct value, which is 100 out of the box. Both stores also let you skip the index for an exact answer: pgvector with SET LOCAL enable_indexscan = off inside a transaction, which its README suggests for monitoring recall, and Qdrant with "exact": true. That exact path is how you build your own recall test on real data. Take a few hundred real queries, get exact top-10s once, then compare what your production setting returns.
What this toy leaves out
Real implementations add what this one file skips: deletes and updates, concurrent inserts, storage on disk pages, quantized vectors, and SIMD distance kernels. The paper also has two optional switches on the neighbor heuristic, extending candidates and keeping pruned connections, that this version leaves off. To see why the heuristic is there at all, generate clustered vectors instead of calling randomUnit, swap selectNeighbors for a plain slice of the M closest candidates, and compare recall at the same efSearch.
If this was useful
Every RAG answer starts with a retrieval step, and that step is an approximate search with a recall number nobody wrote down. AI That Reads is the book in the series about that layer, in TypeScript: embeddings, vector search, chunking and grounding answers in your own documents, with the measuring habits that tell you when retrieval is the part that's failing.
It is book 2 of five in AI in TypeScript, from your first LLM call to agents in production: the whole series is here.
Top comments (0)