Approximate search: Embeddings and vector indexes

Approximate nearest neighbour (ANN)

An approximate index returns most of the true nearest neighbours while comparing far fewer vectors. You accept a small chance of missing a true neighbour in exchange for speed and memory.

Recall at k

Of the k true nearest neighbours (from exact search), the share that the approximate index also returned. Recall 0.95 at k=10 means about nine and a half of the ten. Do not confuse it with retrieval recall in module 7, which asks whether the relevant document was returned; here the question is only whether the index matches exact search.

A 2-D sketch of the three approaches on the same points. Real vectors have tens to thousands of dimensions, where intuition from a flat picture is weaker.

3.1 IVF: search only the nearest clusters

At build time, run k-means to group vectors into n_clusters clusters (each with a centre).
At query time, compare the query with the centres, pick the closest nprobe clusters, and search only the vectors inside them.

Knobs: more clusters make each list shorter; larger nprobe searches more lists, raising recall and cost. The failure is shown in the middle panel: a true neighbour sitting just across a cluster boundary is never looked at.

3.2 Graph indexes (the idea behind HNSW)

At build time, connect each new vector to its m nearest neighbours, forming a graph.
At query time, start at an entry point and repeatedly move to the neighbour closest to the query, keeping the best ef candidates seen. Stop when no candidate can improve the list.

HNSW adds layers: a sparse top layer lets the search take long jumps first, then lower, denser layers refine it. The example implements one layer (NSW) so the walk is easy to read. Knobs: m (links per point: more memory, better recall), ef_construction (effort when building), and ef at query time (bigger means wider search).

3.3 Other families

Locality-sensitive hashing puts similar vectors in the same bucket. Product quantization compresses each vector into small codes so many more fit in memory and distances are cheap to compute (at some accuracy loss). Tree methods such as Annoy split the space with random cuts. Large systems often combine them, such as IVF with product quantization.

Measuring the trade-off

The benchmark builds 3,000 clustered 32-dimensional vectors and 100 queries, computes exact top-10 as ground truth, then sweeps the main knob of each index. It counts distance computations per query, which is hardware-independent.

Real output of bench.py. Both indexes reach about 98 to 99 percent recall with a fraction of the 3,000 comparisons exact search needs.

IVF  nprobe  recall@10  comparisons/query
          1       0.79         124
          2       0.94         168
          4       0.98         255
          8       0.99         435
         16       1.00         805
NSW  ef      recall@10  comparisons/query
         10       0.74         123
         20       0.81         149
         40       0.92         196
         80       0.98         302
        160       0.99         580

What to take from it:

Going from recall 0.92 to 0.98 costs about 50 percent more work in the graph (196 to 302). The last few percent are the expensive ones.
At roughly the same work, the two methods are close in this toy. Real results depend on dimension, data shape, and implementation; do not generalise from this table.
Even at the cheapest setting, the index compared about 4 percent of the data. That is the saving.

Pick the recall you need, not the highest

A RAG system retrieves, then often reranks and shows only a few chunks. Missing one of the true 10 neighbours may not change the final answer. Decide the recall your task needs by measuring retrieval quality end to end (module 7), then choose the cheapest index setting that meets it.