DevPath
Tracks

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.

dimension 1dimension 2a1a2a3b1b2b3c1c2c3query
Cluster A (probed)Cluster B (probed)Cluster C (skipped)Query
Illustrative 2D picture of IVF. The query sits between clusters A and B, so those two are probed and the far cluster C is never scanned. A true neighbour just across a boundary could still be missed.

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:

  1. Compare the query to the nlist centroids.
  2. Pick the nprobe closest centroids.
  3. 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.

Build: stored vectorsn vectors
K-meansnlist centroids
Assign each vectorto its nearest centroid
Query qat search time
Compare q to centroidsnlist distances
Pick nprobe closest lists
Scan those listsabout nprobe * n / nlist vectors
Top-k
The top half runs once when the index is built. The bottom half runs for every query and touches only a few lists.

A tiny example of one query. The numbers are illustrative: 4 lists of 150 vectors each (600 vectors in total) and nprobe = 2.

150
c0
150
c1
150
c2
150
c3
The index has 4 lists, one per centroid, 150 vectors each. Brute force would scan all 600.
step 1 / 5

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.

OperationTimeNotes
Brute force queryO(n * d)Exact; the baseline
IVF queryO((nlist + nprobe * n / nlist) * d)Needs balanced lists
HNSW query~O(log n * d)Empirical; depends on ef and data
IVF buildO(iters * n * nlist * d)K-means dominates
MemoryO(n * d) plus indexHNSW 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)

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.

01112nproberecall@5
recall@5
Recall from the printed output above. It climbs fast, then flattens at 1.00 from nprobe = 4. Going beyond that buys nothing.
nprobe=1
87 calcs
nprobe=2
104 calcs
nprobe=4
228 calcs
nprobe=12
612 calcs
brute force
600 calcs
Average distance calculations per query, from the printed output. nprobe = 4 already reaches full recall at well under half of brute-force cost; nprobe = 12 costs slightly more than brute force.

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 k results, 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

  1. 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.
  2. Explain IVF and its main knob. Cluster vectors, store a list per centroid, search only the nprobe closest lists; larger nprobe means higher recall and higher latency.
  3. 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.
  4. How do you evaluate an ANN index? Measure recall@k against brute-force ground truth on realistic queries, alongside latency, memory, and build time.
  5. 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?

Further resources

Related lessons