Inside FAISS: Billion-Scale Similarity Search

In modern AI, images, text, and audio are not understood by computers as "cat" or "symphony". Instead, they are converted into lists of numbers called embeddings or vectors.

These vectors live in a high-dimensional geometric space. The core idea is simple: items that are semantically similar are placed close together in this space.

Formally, given a query $x\in {\mathbb{R}}^D$ and a database $\mathcal{Y}=\{y_1,\dots ,y_n\}$ of $n$ vectors, exact nearest-neighbor search solves:

The naive Brute Force solution evaluates every distance explicitly. Cost per query: $\mathcal{O}(nD)$ time and $\mathcal{O}(nD)$ memory to hold the database in full precision. For $n=10^9$ SIFT descriptors ($D=128$, 4 bytes per float), that is 512 GB of RAM and one billion distance evaluations per search, a non-starter for real-time systems like web-scale retrieval or live LLM memory.

The rest of this article explores the two escape routes FAISS exploits:

• Partitioning: skip most of $\mathcal{Y}$ at query time (IVF).
• Compression: make each comparison cheap, and make the database fit in RAM (Product Quantization).

Production systems combine both.

FAISS (Facebook AI Similarity Search) introduces approximate search methods. By sacrificing a tiny bit of accuracy (maybe you get the 2nd best match instead of the 1st), we can speed up search by orders of magnitude.

Let's explore two key indexing strategies:

• Flat: The baseline brute-force. Slow but accurate.
• IVF (Inverted File):Partitions the space into "Voronoi cells". We only look in the most promising cells.

Try it yourself. Increase the dataset size and see how different indexes perform.

The Inverted File (IVF)index works like a library classification system. Instead of looking at every book to find a specific title, you go to the "Science Fiction" section first.

Mathematically, it uses K-Means clustering to partition the vector space into Voronoi cells. When we search, we first identify which cell our query vector falls into (using a "coarse quantizer"), and then we only calculate distances for vectors inside that cell (and perhaps a few neighboring ones).

IVF makes search fast by skipping most of the database, but leaves every vector uncompressed. One billion SIFT descriptors still cost 512 GB of RAM. Product Quantization (PQ), introduced by Jégou, Douze and Schmid (2011), is the compression trick FAISS builds on to shrink each vector to 8 bytes while keeping distance estimates meaningful.

Same centroids, a different job

§4 used centroids to partition the search space. PQ uses them to compresseach vector. Same K-Means math, new purpose: the centroid's index becomes the vector. If your codebook has $k$ centroids, any vector collapses to one integer in $\{0,1,\dots ,k-1\}$.

A pixel-sized analogy

A 24-bit RGB pixel can be any of 16.7 million colors. A GIF gives up some of that range: it picks a 256-color palette and replaces every pixel with an 8-bit index into it. Storage drops 3×, the picture still looks like the picture. That palette is a codebook; the index is a code.

A 128-D SIFT descriptor is just a very long pixel. We want the same trick: find a palette of representative vectors, replace every descriptor with its nearest palette index.

How many bits does an index cost?

To label $k$ centroids uniquely you need enough bits to distinguish all of them. Each bit doubles the number of labels, so the code length is $\lceil {\log }_{2}k\rceil$ bits. Concretely:

• $k=256$ centroids → ${\log }_{2}256=8$ bits per code (1 byte)
• $k=1,024$ centroids → ${\log }_{2}1024=10$ bits
• $k=2^{64}$ centroids → 64 bits (8 bytes)

More centroids means the quantizer discriminates finer detail, and the code grows accordingly. The codebook designer is playing a bit-budget game.

The paper's aggressive target

Jégou et al. want each 128-D SIFT descriptor to become a 64-bit code, which is 0.5 bit per dimension, a 64× compression ratio against the 512-byte original. Half a bit per dimension is ambitious: it means the quantizer has to encode all the variation along each axis with a single binary-ish choice.

Hitting 64 bits with one flat codebook means picking $k=2^{64}\approx 1.8\times 10^{19}$ centroids. That is roughly 18 quintillion, more than the number of grains of sand on Earth. Let's feel that number before we dismiss it.

Why 2⁶⁴ is not a codebook

Three walls hit simultaneously when $k$ gets that large:

• Storage.Each centroid is 128 floats × 4 bytes = 512 bytes. Times $2^{64}$ centroids gives about 9.4 zettabytes, more than all cloud storage on Earth in 2025. You cannot persist the codebook, let alone page through it at query time.
• Training data.Lloyd's algorithm needs at least tens of samples per centroid to converge. That is $\gtrsim 30\cdot 2^{64}$ training vectors. No dataset in existence is that large.
• Query cost.To encode one descriptor you compare it to every centroid. 18 quintillion distance computations per vector is not a latency you can ship.

The flat codebook dies on all three fronts. The paper's move is to keep the effective vocabulary the same size while shrinking the stored codebook by many orders of magnitude.

The factoring trick

Back to the GIF analogy. Instead of finding one 256-color palette that works for the whole image, cut the image into 8 tiles and give each tile its own 256-color palette. Each tile is now one byte; the image is 8 bytes; every tile had access to a full 256-color palette tuned to its own pixels. PQ does exactly this for vectors.

Formally: split $x$ into $m$ sub-vectors $u_j\in {\mathbb{R}}^{D/m}$ and learn one small sub-quantizer $q_j$ per block. The product quantizer is the tuple of their outputs:

With $m=8$ and $k^{\ast }=256$ centroids per block, the effective codebook has $(k^{\ast }{)}^m=256^8\approx 1.8\times 10^{19}$ possible combinations (same order of magnitude as the impossible flat case), but we only store $m\cdot k^{\ast }=2,048$ centroid vectors in ${\mathbb{R}}^{16}$ each. Total codebook storage is $m{k}^{\ast }{D}^{\ast }\cdot 4\text{ B}=128\text{ KB}$ (paper §II.B, Table I), small enough to live in L2 cache.

Each encoded vector fits in $m{\log }_2{k}^{\ast }=8\times 8=64\text{ bits}=8\text{ bytes}$, one byte per block index. Ratio: 512 B to 8 B, a 64× drop in memory, with a codebook that actually fits on the machine.

IVFPQ (also called IVFADC in the paper) stacks the two previous techniques: a coarse quantizer prunes the database to a handful of cells, and a product quantizer compresses what remains to 8 bytes per vector. One subtle choice makes the combination work: PQ encodes not the raw vector but its residual with respect to the coarse centroid.

Indexing a database vector $y$:

1. coarse quantize $c=q_c(y)$, the nearest of the $k^{\prime }$ coarse centroids;
2. compute the residual $r(y)=y-q_c(y)$;
3. encode the residual with the product quantizer, giving 8 byte codes $(i_1,\dots ,i_m)$;
4. append the pair $(\mathrm{id},\mathrm{codes})$ to the inverted list of cell $c$, where $\mathrm{id}$ is the database index of $y$ and $\mathrm{codes}=(i_1,\dots ,i_m)$ is the m-byte PQ code produced in step 3.

Residuals concentrate near zero, so the PQ codebook spends its bits modeling variation the coarse quantizer did not already capture. Same byte budget, better reconstruction.

Searching for a query $x$:

1. find the $w$ nearest coarse centroids to $x$;
2. compute the query residual $r(x)=x-q_c(x)$ for each selected cell;
3. precompute the $m\times k^{\ast }$ distance Look-Up Table (LUT). Index $j\in \{1,\dots ,m\}$ selects the PQ sub-block ($m=8$ in our setup), and index $i\in \{0,\dots ,k^{\ast }-1\}$ selects one of the $k^{\ast }$centroids of that sub-block's codebook ($k^{\ast }=256$). Each entry is the squared distance between the query's sub-block residual and that centroid:
   $$\mathrm{LUT}[j][i]=\Vert u_j(r(x))-c_{j,i}{\Vert }^2$$
4. scan the inverted list: for each stored entry with PQ codes $(i_1,\dots ,i_m)$ (one sub-block index per $j$), read the $m$ precomputed distances from the LUT and sum them:
   $${\tilde{d}}_{\text{ADC}}^2=\sum _{j=1}^m\mathrm{LUT}[j][i_j]$$
   $m$ table reads, $m-1$ additions per candidate. No float multiplications, no square roots.
5. keep a fixed-capacity max-heap of size $K$ holding the best candidates seen so far, keyed by their ADC distance. While the heap is not full, push every scanned candidate. Once full, compare each new ADC distance against the root (the current worst of the best-$K$): if smaller, pop the root and push the candidate, otherwise discard it. The heap is shared across the $w$ probed inverted lists. When the scan is done, drain the heap in ascending order to get the $K$ approximate nearest neighbors of $x$.

The walkthrough below runs the full pipeline with real arithmetic at every stage.

Going from CPU to GPU shifts the bottleneck. The hard question is no longer “how fast can we sum these numbers” but “how fast can we stream thousands of tiny PQ codes from DRAM into the compute units.” The answer is about memory bandwidth, not arithmetic.

Four tricks turn that crew into a billion-vector scanner:

1. Coalesced reads. Transpose the list so the warp picks up 32 sub-codes in one 128-byte DRAM burst instead of 32 scattered ones.
2. Shared-memory LUT. Copy the $m\times k^{\ast }$ table into SRAM once per list. Every thread then reads it at ~25 cycles instead of ~400 (§5.3).
3. Warp scan. One thread per vector, 32 distances per tick, partial sums held in registers.
4. WarpSelect. Top-K without a global lock: warp queue, then block merge, then global merge (§4.2).

Step through the four tricks below; click any figure to zoom in on the labels.

Scaling past one GPU is an explicit knob (§5.4): replication splits the query stream across $\mathcal{R}$ devices, sharding splits the database across $\mathcal{S}$ devices, and the two compose to $\mathcal{S}\times \mathcal{R}$ GPUs.

FAISS isn't just for benchmarks. Here are six production scenarios where vector search with FAISS powers real applications:

index.search(embed("climate change effects"), k=10)

index.search(clip_embed(query_image), k=5)

context = index.search(embed(user_query), k=3)
llm.generate(prompt + context)

similar = index.search(item_embedding, k=20)

lims, D, I = index.range_search(emb, thresh=0.95)

D, _ = index.search(point, k=5)
anomaly_score = D.mean()

Four ideas, layered on top of each other. Flat gives perfect recall at impossible cost. IVF partitions the space so most of it can be skipped at query time. PQ compresses every vector into roughly 8 bytes so a billion of them fit in RAM. IVFPQ combines the two, and on a single GPU the pipeline returns top-K in microseconds.

The move underneath is always the same: embed your data into a geometry where close means similar, then pick the index whose trade-offs match your constraints (latency, memory, recall). Graph indexes (HNSW, NSG) and hardware-aware accelerators (FastScan, IMI) reach the same goal through different tricks and will get their own articles.

Once the geometry and the trade-offs click, billion-scale nearest-neighbor search stops being a research problem and starts being a dial you turn.