Similarity Search and ANN Indexes
Why exact nearest-neighbour search costs O(n*d), and how IVF clustering and graph indexes like HNSW trade a little recall for a big speedup.
intermediate45 min#ann#ivf#hnsw#lsh#nearest-neighbour#recall
Prerequisites: Vectors and Embeddings, Arrays and Dynamic Arrays
Why it matters
In the embeddings lesson you scored a query against every stored vector and kept the best few. That is correct, and for a hundred thousand vectors it is often fast enough. At fifty million vectors, with a latency budget of tens of milliseconds, it is not. Almost every semantic search, recommendation, and RAG system eventually meets this wall, and the answer is an approximate nearest neighbour (ANN) index: a structure that finds neighbours that are almost always the true ones, while looking at only a tiny fraction of the data.
Intuition
You are looking for the closest coffee shop. Exact search means measuring the distance to every coffee shop in the country. Nobody does that. You first narrow to your city (a coarse step), then check shops in that city (a fine step). You might occasionally miss a great shop just over the city border, and that miss is the price of speed.
The two big families of ANN index formalise two different shortcuts:
- Partition the space (IVF, LSH, trees): split vectors into buckets, then search only the buckets near the query.
- Navigate a graph (HNSW): link each vector to a few neighbours, then walk from a starting point toward the query, always stepping to a closer node.
Both accept that the answer may be slightly wrong. The knob that controls how wrong is the central idea of this lesson.
How it works
Exact (brute force). For n vectors of dimension d, one query computes n dot products of d multiplications each, so O(n * d) work, plus O(n log k) or so to keep the best k. It is simple, always correct, and parallelises well. It is the baseline you measure everything else against.
IVF (inverted file index). Run k-means on the stored vectors to get nlist centroids. Assign each vector to its nearest centroid, producing nlist lists. At query time:
- Compare the query to the
nlistcentroids. - Pick the
nprobeclosest centroids. - Scan only the vectors in those lists.
With balanced lists you examine roughly nlist + nprobe * n / nlist vectors instead of n. A common rule of thumb sets nlist near the square root of n. Raising nprobe scans more lists, raising recall and cost together.
A tiny example of one query. The numbers are illustrative: 4 lists of 150 vectors each (600 vectors in total) and nprobe = 2.
Click Next to follow one IVF query. Only the probed lists are scanned, which is where the saving comes from.
query q
| compare with centroids (nlist distances)
v
[c1] [c2] [c3] [c4] [c5] ... nprobe = 2 -> keep c2, c4
| |
list of c2 list of c4 scan only these vectors
\ /
top-k merged
HNSW (hierarchical navigable small world). Build a proximity graph where each vector links to nearby vectors. Add several layers: the top layer is sparse with long edges (a highway), lower layers are denser, and layer 0 holds everyone. A search enters at the top, greedily moves to whichever neighbour is closest to the query, drops a layer when it cannot improve, and at the bottom explores a small frontier whose width is a parameter usually called ef. Search cost grows roughly with the logarithm of n. The trade-offs: a graph needs extra memory for edges, building it is slower than k-means, and deleting or updating nodes is awkward. If graphs are new to you, see the graphs lesson; an HNSW layer is just an adjacency list.
LSH (locality-sensitive hashing). Use hash functions designed so that similar vectors collide in the same bucket with high probability. A classic one for cosine similarity picks random hyperplanes and records which side of each the vector falls on. This is a hash table (see the hash tables lesson) whose hash deliberately preserves similarity instead of scrambling it. It is elegant, but in practice graph and IVF indexes usually give better recall per unit of memory for dense embeddings.
Recall versus speed. The quality measure is recall@k: of the true top k neighbours, what fraction did the index return? You cannot get speed without giving some up. Every index exposes a knob (nprobe, ef, number of hash tables) that moves you along one curve. You choose a recall target (for example 95 percent), then tune the knob to the cheapest setting that reaches it.
| Operation | Time | Notes |
|---|---|---|
| Brute force query | O(n * d) | Exact; the baseline |
| IVF query | O((nlist + nprobe * n / nlist) * d) | Needs balanced lists |
| HNSW query | ~O(log n * d) | Empirical; depends on ef and data |
| IVF build | O(iters * n * nlist * d) | K-means dominates |
| Memory | O(n * d) plus index | HNSW adds edges per node |
Code: IVF from scratch with a recall measurement
We build 600 clustered 8-dimensional vectors with a tiny seeded random generator, so the output is the same every run and in both languages. A real system would load embeddings from a model instead; the index code does not change.
class Rng:
def __init__(self, seed):
self.s = seed
def next(self):
self.s = (self.s * 1664525 + 1013904223) % 4294967296
return self.s / 4294967296
def d2(a, b):
t = 0.0
for x, y in zip(a, b):
diff = x - y
t += diff * diff
return t
D, N, K = 8, 600, 5
rng = Rng(7)
centers = [[rng.next() * 10 for _ in range(D)] for _ in range(6)]
def make_point(i):
c = centers[i % 6]
return [x + (rng.next() - 0.5) * 3 for x in c]
data = [make_point(i) for i in range(N)]
queries = [make_point(i) for i in range(20)]
def kmeans(points, k, iters=10):
cents = [points[i * (len(points) // k)][:] for i in range(k)]
for _ in range(iters):
groups = [[] for _ in range(k)]
for p in points:
best = min(range(k), key=lambda c: d2(p, cents[c]))
groups[best].append(p)
for c, g in enumerate(groups):
if g:
cents[c] = [sum(p[j] for p in g) / len(g) for j in range(D)]
return cents
class IVF:
def __init__(self, vectors, nlist):
self.vectors = vectors
self.cents = kmeans(vectors, nlist)
self.lists = [[] for _ in range(nlist)]
for i, v in enumerate(vectors):
best = min(range(nlist), key=lambda c: d2(v, self.cents[c]))
self.lists[best].append(i)
def search(self, q, k, nprobe):
order = sorted(range(len(self.cents)), key=lambda c: (d2(q, self.cents[c]), c))
scored, work = [], len(self.cents)
for c in order[:nprobe]:
for i in self.lists[c]:
scored.append((d2(q, self.vectors[i]), i))
work += 1
scored.sort()
return [i for _, i in scored[:k]], work
def brute(q, k):
scored = sorted((d2(q, v), i) for i, v in enumerate(data))
return [i for _, i in scored[:k]]
index = IVF(data, 12)
truth = [brute(q, K) for q in queries]
for nprobe in (1, 2, 4, 12):
hits, work = 0, 0
for q, t in zip(queries, truth):
got, w = index.search(q, K, nprobe)
hits += len(set(got) & set(t))
work += w
print(f"nprobe={nprobe:2d} recall@{K}={hits / (K * len(queries)):.2f} avg_distance_calcs={work // len(queries)}")
print("brute force distance calcs:", N)class Rng {
constructor(seed) {
this.s = seed;
}
next() {
this.s = (Math.imul(this.s, 1664525) + 1013904223) >>> 0;
return this.s / 4294967296;
}
}
function d2(a, b) {
let t = 0.0;
for (let i = 0; i < a.length; i++) {
const diff = a[i] - b[i];
t += diff * diff;
}
return t;
}
const D = 8, N = 600, K = 5;
const rng = new Rng(7);
const centers = Array.from({ length: 6 }, () =>
Array.from({ length: D }, () => rng.next() * 10)
);
function makePoint(i) {
const c = centers[i % 6];
return c.map((x) => x + (rng.next() - 0.5) * 3);
}
const data = Array.from({ length: N }, (_, i) => makePoint(i));
const queries = Array.from({ length: 20 }, (_, i) => makePoint(i));
function argmin(n, f) {
let best = 0, bestVal = f(0);
for (let i = 1; i < n; i++) {
const v = f(i);
if (v < bestVal) { best = i; bestVal = v; }
}
return best;
}
function kmeans(points, k, iters = 10) {
const cents = Array.from({ length: k }, (_, i) =>
points[i * Math.floor(points.length / k)].slice()
);
for (let it = 0; it < iters; it++) {
const groups = Array.from({ length: k }, () => []);
for (const p of points) groups[argmin(k, (c) => d2(p, cents[c]))].push(p);
groups.forEach((g, c) => {
if (g.length) {
cents[c] = Array.from({ length: D }, (_, j) => {
let s = 0;
for (const p of g) s += p[j];
return s / g.length;
});
}
});
}
return cents;
}
class IVF {
constructor(vectors, nlist) {
this.vectors = vectors;
this.cents = kmeans(vectors, nlist);
this.lists = Array.from({ length: nlist }, () => []);
vectors.forEach((v, i) => {
this.lists[argmin(nlist, (c) => d2(v, this.cents[c]))].push(i);
});
}
search(q, k, nprobe) {
const order = this.cents
.map((c, i) => [d2(q, c), i])
.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
const scored = [];
let work = this.cents.length;
for (const [, c] of order.slice(0, nprobe)) {
for (const i of this.lists[c]) {
scored.push([d2(q, this.vectors[i]), i]);
work++;
}
}
scored.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
return { ids: scored.slice(0, k).map((s) => s[1]), work };
}
}
function brute(q, k) {
return data
.map((v, i) => [d2(q, v), i])
.sort((a, b) => a[0] - b[0] || a[1] - b[1])
.slice(0, k)
.map((s) => s[1]);
}
const index = new IVF(data, 12);
const truth = queries.map((q) => brute(q, K));
for (const nprobe of [1, 2, 4, 12]) {
let hits = 0, work = 0;
queries.forEach((q, qi) => {
const { ids, work: w } = index.search(q, K, nprobe);
const t = new Set(truth[qi]);
hits += ids.filter((i) => t.has(i)).length;
work += w;
});
const recall = (hits / (K * queries.length)).toFixed(2);
console.log(
`nprobe=${String(nprobe).padStart(2)} recall@${K}=${recall} avg_distance_calcs=${Math.floor(work / queries.length)}`
);
}
console.log("brute force distance calcs:", N);Both versions print:
nprobe= 1 recall@5=0.89 avg_distance_calcs=87
nprobe= 2 recall@5=0.96 avg_distance_calcs=104
nprobe= 4 recall@5=1.00 avg_distance_calcs=228
nprobe=12 recall@5=1.00 avg_distance_calcs=612
brute force distance calcs: 600
Notice that the sweet spot is in the middle: a small nprobe already does a fraction of the brute-force work, and nprobe = 12 (every list) is just brute force plus the centroid overhead, which is why it can cost more than the baseline.
Common pitfalls
- Judging an index without ground truth: speed numbers mean nothing without recall measured against brute force on a sample of real queries.
- Tuning on easy queries: if your test queries are copies of stored vectors, recall looks perfect. Use realistic held-out queries.
- Unbalanced IVF lists: if one centroid owns half the data, scanning it dominates cost. Check list sizes after training.
- Training on too little data: k-means centroids learned from a tiny sample (or from data that later drifts) give poor partitions. Retrain when the distribution changes.
- Ignoring the filter: if you filter by metadata after ANN search returns
kresults, you may be left with none. See the vector databases lesson. - Mixing metrics: build the index for the same metric (cosine, dot, Euclidean) that you query with.
Practice
Brute-force top-k without sorting everything easy
Hint
You only need the best k. What structure keeps the k best seen so far in O(log k) per update?
Show solution
Keep a max-heap of size k keyed by distance. For each vector compute its distance; if the heap has fewer than k items push it, otherwise replace the root when the new distance is smaller. This costs O(n * d + n log k) instead of O(n log n). In Python use heapq with negated distances; in JavaScript write a small heap or just sort when n is small.
Choose nlist and nprobe medium
Hint
Write the cost as nlist + nprobe * n / nlist and minimise over nlist.
Show solution
With nprobe fixed, cost is f(nlist) = nlist + nprobe * n / nlist. Setting the derivative to zero gives nlist = sqrt(nprobe * n), so a few times the square root of n is a sensible start. For n = 1,000,000 and nprobe = 8 that is about 2,800 lists and roughly 5,700 distance computations per query instead of a million. Then measure recall and raise nprobe until the target is met.
Random-hyperplane LSH for cosine similarity medium
Hint
Each hyperplane gives one bit: the sign of the dot product with a random vector.
Show solution
Draw b random vectors. The signature of a vector is the b signs of its dot products with them. Two vectors at angle theta agree on each bit with probability 1 - theta / pi, so close vectors share most bits. Store vectors in a hash table keyed by signature, and at query time look in the query's bucket (optionally also buckets one bit away). Use several independent tables to raise recall.
Why does HNSW search sometimes miss the true neighbour? hard
Hint
Greedy walks stop at local minima. What does ef change?
Show solution
Greedy descent moves to the neighbour closest to the query and stops when no neighbour is closer, which can be a local minimum that is not the global nearest. The search keeps a candidate list of size ef instead of a single node, so it can escape shallow minima by exploring several branches. Larger ef raises recall and latency. Missing the nearest node is an expected, tunable property, not a bug.
Interview questions
- Why is exact nearest-neighbour search hard at scale? The best known exact methods degrade toward scanning everything in high dimensions (the curse of dimensionality), so cost stays near O(n * d) per query.
- Explain IVF and its main knob. Cluster vectors, store a list per centroid, search only the
nprobeclosest lists; largernprobemeans higher recall and higher latency. - How does HNSW work at a high level? A layered proximity graph; greedy search from a sparse top layer down to a dense bottom layer, with a candidate list of width
ef. - How do you evaluate an ANN index? Measure recall@k against brute-force ground truth on realistic queries, alongside latency, memory, and build time.
- When would you skip ANN entirely? For small collections (tens of thousands of vectors), brute force is simple, exact, and fast enough.
Interviewers look for: naming the recall-versus-latency trade-off unprompted, knowing recall must be measured against brute force, and picking a simple exact scan when the data is small.
Quick check
You double nprobe on an IVF index. What most likely happens?
Finished this lesson?