FAISS Deep Dive

This is the mechanics post, and the cover sets the right expectation: the 'magic' of fast search is two concrete tricks. First, don't search everything — partition the space and only look at the relevant region. Second, if memory is tight, don't store full vectors — store compressed sketches you can still compute distances on. Everything technical in the post elaborates one of these two ideas.

Before the index machinery, this slide reasserts the boundary of FAISS's responsibility. You produce the embeddings with a model; FAISS only indexes the numbers. The two hard constraints are that every vector and query share the same dimension d, and that they come from the same model. A dimension mismatch raises a clear error. A model mismatch is far more dangerous: the dimensions can match by coincidence, the call succeeds, and you get confident neighbors that are semantically meaningless.

This is worth stating in the 'how' post because most real recall problems trace back to an upstream embedding inconsistency, not to the index itself.

IVF — the inverted file index — is the first big trick. At build time FAISS runs k-means over a training sample to carve the vector space into nlist cells, each represented by a centroid. Every stored vector is assigned to the cell of its nearest centroid, exactly like points falling into Voronoi regions.

At query time, instead of scanning all vectors, FAISS finds the centroids closest to the query and only searches the vectors filed under those cells. If you have 1024 cells and search a handful, you've skipped the vast majority of the dataset. This partitioning is what turns linear search into something far cheaper, and it's the backbone of most FAISS ANN setups.

The flow diagram traces an IVF query end to end: the query vector arrives, FAISS compares it to the cell centroids and picks the nprobe closest ones, searches only the vectors inside those cells, and returns the top-k. The single 'skip the rest' step is where all the speed comes from — and also where recall can be lost if the true neighbor happens to live in a cell you didn't probe.

Seeing it as a funnel makes the tuning intuitive: probe more cells and the funnel widens toward exhaustive (slower, higher recall); probe fewer and it narrows (faster, lower recall).

nprobe is the single most important runtime knob, and it deserves its own slide. It controls how many cells FAISS searches per query. At nprobe=1 the search is fastest but a neighbor sitting just across a cell boundary becomes invisible, because its cell was never visited. Raising nprobe widens the search and pushes recall toward the exact answer, at a roughly proportional cost in latency.

The right discipline is to set a recall target — say recall@10 ≥ 0.95 — measure recall on a held-out query set as you sweep nprobe, and pick the smallest nprobe that hits the target. Guessing, or shipping the default of 1, is how teams end up with silently degraded search quality.

Product Quantization is the second big trick and the answer to a memory problem. Storing a million 768-dim float32 vectors is several gigabytes; a billion is hopeless in RAM. PQ splits each vector into m subvectors and, for each subvector slot, learns a small codebook via k-means. Each subvector is then replaced by the single byte (or few bits) identifying its nearest codebook entry.

A 3KB vector can collapse to a dozen-or-so bytes. The clever part is that FAISS can compute approximate distances directly on these codes using precomputed lookup tables, so search runs on the compressed representation. You trade some precision for a dramatic reduction in memory, which is exactly what makes billion-scale indexes fit on one machine.

This comparison lays out the three-way tension that governs every FAISS tuning decision: speed, accuracy, and memory. Raising nprobe buys recall at the cost of speed. Stronger PQ compression saves RAM at the cost of recall. More IVF cells make each probe cheaper but require probing more of them to maintain coverage.

The right panel anchors the index families on this triangle: flat is exact but huge and slow, IVF+PQ is fast and compact but approximate, and HNSW is fast and accurate but memory-hungry. There is no universally best point — you choose based on which corner your application can least afford to sacrifice.

HNSW is the graph-based alternative to IVF, included in FAISS for a different sweet spot. Rather than partitioning into cells, it builds a hierarchical navigable small-world graph: upper layers contain few nodes with long-range shortcut links, and each lower layer adds more nodes and finer detail. A search enters at the top, greedily walks toward the query, then descends a layer and repeats — reaching close neighbors in roughly logarithmic time.

HNSW typically delivers excellent recall at very low latency, which is why it's so popular. The catch is memory: storing the graph's links per node is expensive, so HNSW is RAM-hungry compared to IVF+PQ. When you can afford the memory and want high recall without much tuning, it's an excellent default.

This snippet shows building and tuning an IVF+PQ index the explicit way. You create a flat L2 quantizer (used to assign vectors to cells), then construct IndexIVFPQ with d dimensions, nlist=256 cells, m=16 PQ subvectors, and 8 bits per code. The crucial line is train(xb): IVF and PQ both learn their structure from data, so you must train on a representative sample before adding anything.

After add() loads the vectors, setting index.nprobe = 16 tells FAISS to search 16 of the 256 cells per query — the recall dial in action. The search call then returns the familiar (D, I) distance and id arrays. This is the canonical pattern for a tuned, memory-efficient FAISS index.

The factory string is FAISS's compact recipe language and a huge ergonomic win once you know it. index_factory(128, "IVF256,PQ16x8", METRIC_L2) builds the same composite index as the previous slide in one readable string: 256 IVF cells, PQ with 16 codes of 8 bits each.

The other examples show the range: "Flat" is the exact baseline that needs no training, "HNSW32" builds a graph index with 32 neighbors per node, and "OPQ16,IVF1024,PQ16" prepends an OPQ rotation that reorganizes dimensions so PQ compresses them more effectively. Learning to read these strings lets you experiment with index designs by editing a string instead of rewriting object construction code.

These five lines compress the engine: you embed and FAISS indexes; IVF splits the space into cells via k-means; nprobe controls how many cells you search and is your primary recall dial; PQ compresses vectors into codebook bytes so huge datasets fit in RAM; and HNSW is the graph-based index that's fast and accurate but memory-heavy.

The cover and CTA bracket the mechanics and hand off to practice. Having seen IVF, nprobe, PQ, HNSW, and the factory string, the next post stops explaining and starts typing: a full runnable walkthrough from embeddings to a saved, reloadable index, including the part FAISS leaves to you — mapping result ids back to your original text.