Indexing Embeddings

The knobs behind "approximate"

Purpose and functionality explains why exact nearest-neighbour search stops scaling and what approximate search trades away. Performing similarity search covers the query side.

This page is the part in between: the index structure you choose, the parameters that tune it, and the three quantities you are trading against each other.

Those three are recall, latency and memory. Every index decision moves at least two of them, and no setting is best at all three. Knowing which one you are short of is most of the work.

Flat, when you can get away with it

An exhaustive index compares the query against every vector. Recall is perfect because nothing is skipped.

Faiss's own guidance recommends "Flat" for a few thousand searches, or whenever you need exact results. That covers more real systems than people assume. Fifty thousand vectors searched a few times a minute does not need an approximate index, and choosing one costs you recall in exchange for latency you were not short of.

Start here and measure. Move when the numbers say to.

IVF: partition, then search some partitions

An inverted-file index clusters the vectors and searches only the nearest clusters. Two parameters:

nlist is how many clusters exist, fixed at build time. Faiss suggests 4√N to 16√N for datasets under a million, and its guidance scales to powers of two above that: 65,536 clusters for 1M to 10M, 262,144 for 10M to 100M, 1,048,576 for 100M to 1B.

nprobe is how many clusters a query searches, and it is the dial you turn at runtime. Raising it raises recall and latency together, close to linearly.

That split matters operationally. nprobe can be tuned against live traffic without rebuilding, so it is where to look first when recall disappoints. nlist cannot, so getting it roughly right at build time saves you a rebuild.

IVF also needs training data to learn the clusters, in the region of 30,000 to 256,000 vectors. An index trained on unrepresentative data clusters badly, and the symptom is recall that is fine in testing and poor on real queries.

HNSW: a navigable graph

A hierarchical graph index gives strong recall at low latency, and pays for it in memory. Faiss recommends HNSW_M when memory is not constrained, with M from 4 to 64.

Three parameters, and they are not interchangeable:

M is how many neighbours each node keeps. Higher means better recall and more memory per vector.

efConstruction controls build quality. Higher builds a better graph, more slowly. You pay once.

efSearch controls query effort. Higher means better recall and more latency. You pay per query, and like nprobe it is tunable at runtime.

The pattern across both families: one build-time parameter you should not have to revisit, and one query-time parameter that is your recall dial.

Quantization, when memory is the binding constraint

Product quantization compresses vectors rather than organising them, so it addresses memory rather than speed.

Faiss's recommendation when memory matters is "OPQ_M_D,...,PQ_M x4fsr", costing M/2 bytes per vector. OPQ learns a rotation before quantizing, which compresses better than PQ alone. One constraint that catches people: the dimension D must be a multiple of M, and Faiss prefers D = 4M.

For maximum compression its guidance points at RaBitQ, alone or combined with IVF.

Compression costs recall. That is the trade, and it is worth making only once memory is the thing you are short of, because a compressed index that fits in RAM beats an uncompressed one that does not by a wide margin.

Combining them is normal

Real indexes stack. IVF65536_HNSW32,... uses HNSW to assign vectors to IVF clusters, so the coarse quantizer is itself fast. That is Faiss's recommendation above a million vectors, and it is why index specifications read like a recipe rather than a name.

If you are on a managed store you will not write these strings, and the parameters underneath are usually the same ones with different labels. Knowing that nprobe and efSearch are your runtime recall dials transfers even when the vocabulary does not.

Measure recall before you tune anything

You cannot tune recall you have not measured, and the measurement needs a ground truth: run exhaustive search over a sample of queries, keep the true top-k, then compare what the approximate index returns.

Without that, "recall is fine" means nobody checked. With it, tuning nprobe or efSearch becomes arithmetic. This is the same argument performing similarity search makes about disappointing results: the usual cause is not the index.

Further reading

• Faiss, Guidelines to choose an index: the decision path, the size thresholds and the parameters.
• Purpose and functionality: why approximate search exists.
• Faiss: the library these specifications belong to.
• Performing similarity search: the query side, and why results disappoint.