Inside FAISS: Billion-Scale Similarity Search

January 23, 202645 min readBy Tom Salembien

FAISSVector SearchOptimizationMachine Learning

1. Everything is a Vector

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.

Cat

Dog

Pizza

Car

Foundations · Vectors & similarity

step 1 / 4

1. The Challenge

Computers don't have eyes or ears. They only understand numbers. How do we explain the concept of a 'Dog' or a 'Cat' to a machine?

step 2 / 4

2. Vectorization

We use Neural Networks to transform raw data (pixels, text) into a list of numbers. This list is the 'Embedding'. It captures the semantic meaning.

step 3 / 4

3. The Vector Space

These numbers act as coordinates (X, Y, Z...). We can plot every image or word as a single point in a high-dimensional space.

step 4 / 4

4. Similarity is Distance

In this space, concepts that are similar are placed close together. 'Cat' is close to 'Dog', but far from 'Car'. We measure this using distance (Euclidean or Cosine).

Above, we visualize a simplified 2D slice of this space. Imagine this in 1024 dimensions. Finding the "nearest neighbor" for a query point is equivalent to finding the most similar item in your database.

2. The NN Problem at Scale

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

NN (x) = ar g y \in Y min d (x, y), d (x, y) = ∥ x - y ∥_{2}

The naive Brute Force solution evaluates every distance explicitly. Cost per query: $O (n D)$ time and $O (n D)$ memory to hold the database in full precision. For $n = 1 0^{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 $Y$ at query time (IVF).
Compression: make each comparison cheap, and make the database fit in RAM (Product Quantization).

Production systems combine both.

3. FAISS to the Rescue

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.

Interactive Index Benchmark

Compare the performance of different indexing algorithms on random datasets.

Precomputed benchmarks

Dataset Size (N)

Index Type

4. Partitioning with IVF

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 Clustering1. Raw Data

K-means partitions random vectors into the Voronoi cells that IVF searches.

Start: Here is our raw dataset. 80 vectors in a 2D space. Searching this linearly (Brute Force) would require calculating distance to 80 points.

5. Compressing with Product Quantization

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 $⌈ lo g_{2} k ⌉$ bits. Concretely:

$k = 256$ centroids → $lo g_{2} 256 = 8$ bits per code (1 byte)
$k = 1, 024$ centroids → $lo g_{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 1 0^{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.

Flat codebook feasibility

Pick a vector dimension and a bit budget per dimension to see the centroid count and storage footprint a single flat quantizer would need.

Vector dimension (D)

Bits per dimension

Total bits per code64bits

Centroids needed (k = 2^64)1.84 × 10^19centroids

Codebook storage9.44ZB

Impossible

Bigger than all cloud storage on Earth. Lloyd's algorithm would need roughly 5.53 × 10^20 training samples.

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 $≳ 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 R^{D / m}$ and learn one small sub-quantizer $q_{j}$ per block. The product quantizer is the tuple of their outputs:

q (x) = (q_{1} (u_{1} (x)), q_{2} (u_{2} (x)), \dots, q_{m} (u_{m} (x)))

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

Each encoded vector fits in $m lo g_{2} k^{*} = 8 \times 8 = 64 bits = 8 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.

The walkthrough below builds the full index on the paper's reference SIFT setting ( $D = 128, m = 8, k^{*} = 256$ ), turning each concept above into a concrete operation on real numbers.

descriptor

x \in R^{128}

u₁

u₂

u₃

u₄

u₅

u₆

u₇

u₈

zoom on cell[row 4, col 9]= 0.259555

01111101

exponent

00001001110010001101101

mantissa

32 bits = 4 bytes per dimension · 128 dims × 4 B = 512 B per vector

Compression · Product Quantization

step 1 / 8

1. One descriptor, zoomed all the way in

A 128-D vector is 128 floats. Zoom into a single one and you find IEEE 754: 1 sign bit, 8 exponent bits, 23 mantissa bits.

Four bytes per dimension, 512 bytes per vector.

step 2 / 8

2. Cut it into 8 sub-vectors

Same 128 numbers, regrouped into 8 contiguous blocks of 16 dimensions each.

Each block gets its own colour because each one will get its own codebook.

step 3 / 8

3. Now multiply: a tiny demo database

A codebook needs a population, not a single vector. This demo uses 4 example vectors; the paper trains on millions.

Every database vector gets the same 8-block split, and each block contributes one point per vector to its own subspace.

step 4 / 8

4. Focus on one codebook: u₁

Each subspace gets its own codebook, trained alone. That independence is the product in Product Quantization.

To see the whole recipe, we zoom into just one subvector, u₁, rendered in 2-D for readability (the paper's subspaces live in d* = D/m = 16 dimensions, with D = 128 and m = 8). Four training vectors is a pedagogical cartoon; real PQ trains each subspace on roughly 10⁶ descriptors.

Lloyd's algorithm runs k-means on this subspace alone: assign every point to its nearest centroid, move each centroid to its cluster mean, repeat until the within-block distortion MSE(q₁) = 𝔼‖u₁(x) − q₁(u₁(x))‖² stops falling.

The 6 centroids you end with (k* = 256 in the paper) form the codebook C₁. Encoding any future vector's first block is then a nearest-centroid lookup: emit the index i of c₁,ᵢ.

step 5 / 8

5. Same thing, 8 times in parallel

All 8 subspaces are quantized the same way at once, each block over its own slice of the data with its own codebook.

Lloyd's runs per block, independently (k* = 256 clusters per codebook in the paper, shown here with 6).

step 6 / 8

6. Encoding a brand-new vector

A query x arrives at search time, it was never in the training set.

Split it into 8 sub-vectors and, in each plot, snap to the nearest centroid. The 8 indices concatenate into the 8-byte code.

step 7 / 8

7. Decoding and per-block error

Reconstruction is a table lookup: replace each index by its centroid.

The gap between the unknown raw point and its centroid is the per-block quantization error; the total reconstruction error is their sum of squares.

step 8 / 8

8. Distance without decoding: SDC vs ADC

Two ways to compute query-to-database distance from codes.

SDC quantises both points and reads centroid-to-centroid distances. ADC keeps the query in full precision and reads raw-to-centroid distances.

ADC has a tighter error bound; FAISS defaults to it.

Once encoded, how do we measure distances without decoding every vector back to its 512 bytes? The paper gives two options.

SDC (symmetric) quantizes both the query and the database vector and reads a pairwise centroid distance from a precomputed $k^{*} \times k^{*}$ table per sub-quantizer.
ADC (asymmetric) leaves the query in full precision and precomputes only $k^{*}$ query-to-centroid distances per block, then sums one lookup per block:
$\tilde{d}_{ADC} (x, y)^{2} = j = 1 \sum m d (u_{j} (x), q_{j} (u_{j} (y)))^{2}$

Per-query cost is similar (Jégou et al., Table II), but ADC has a tighter error bound: the mean squared distance error satisfies $MSDE (q) \leq MSE (q)$ for ADC(Eq 18) versus $2 MSE (q)$ for SDC. FAISS defaults to ADC.

6. Combining: IVFPQ

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$ :

coarse quantize $c = q_{c} (y)$ , the nearest of the $k^{'}$ coarse centroids;
compute the residual $r (y) = y - q_{c} (y)$ ;
encode the residual with the product quantizer, giving 8 byte codes $(i_{1}, \dots, i_{m})$ ;
append the pair $(id, codes)$ to the inverted list of cell $c$ , where $id$ is the database index of $y$ and $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$ :

find the $w$ nearest coarse centroids to $x$ ;
compute the query residual $r (x) = x - q_{c} (x)$ for each selected cell;
precompute the $m \times k^{*}$ 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^{*} - 1}$ selects one of the $k^{*}$ centroids of that sub-block's codebook ( $k^{*} = 256$ ). Each entry is the squared distance between the query's sub-block residual and that centroid:
$LUT [j] [i] = u_{j} (r (x)) - c_{j, i}^{2}$
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}_{ADC}^{2} = j = 1 \sum m LUT [j] [i_{j}]$
$m$ table reads, $m - 1$ additions per candidate. No float multiplications, no square roots.
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.

training · offline

Lloyd's on the training set

iter 0 / 6 · MSE 0.280

k-means produces 8 coarse centroids → 8 inverted lists

Phase 1 · Training (offline)

step 1 / 12

1. Train the coarse quantizer

Run k-means on a training set to learn $k^{'}$ coarse centroids. They carve $R^{D}$ into Voronoi cells, and these are the neighborhoods of IVFADC.

Paper setting: $k^{'} \in [1000, 1 0^{6}]$ for SIFT (Jégou et al. §IV.A). We render 8 cells here so each one stays readable.

step 2 / 12

2. From raw vectors to residuals

For every training vector $y$ , subtract its nearest coarse centroid:

r (y) = y - q_{c} (y)

Subtracting the centroid re-centers each cell's points on the origin of its own frame. Pooled together, all cells share one centered residual distribution, and that is what the product quantizer learns on.

step 3 / 12

3. Why residuals quantize better

Residuals carry much less energy than raw vectors: $∥ r (y)∥ ≪ ∥ y ∥$ on average. Same centroid budget, smaller region to cover, finer quantization steps.

Analogy: video compression. First send a coarse frame, then spend your bits on the difference. You encode motion and detail, not the whole picture from scratch.

Toggle the overlay in the visual to superimpose both histograms and read the variance ratio.

step 4 / 12

4. Train PQ on residuals

Split each residual into $m = 8$ sub-vectors $u_{j} (r (y)) \in R^{16}$ . Run Lloyd's on each block independently, with one codebook $C_{j} = {c_{j, 1}, \dots, c_{j, k^{*}}}$ per block.

The codebooks model variation the coarse quantizer already subtracted away. Same 8-byte footprint, sharper reconstructions. Training ends here; the next three chapters consume these codebooks at speed.

Phase 2 · Encoding the database

step 5 / 12

5. Assign the coarse bucket

A new database vector $y$ arrives. Compare it to every coarse centroid, pick the nearest. Call its index $i$ . This index identifies the inverted list $L_{i}$ where $y$ will be stored.

step 6 / 12

6. Encode the residual with PQ

Compute $r (y) = y - q_{c} (y)$ , split into eight sub-vectors, snap each to its nearest centroid in $C_{j}$ . Emit the 8 block indices $(i_{1}, \dots, i_{8})$ .

$lo g_{2} k^{*} = 8$ bits per block, 8 blocks, one byte each. Eight bytes of code locate $y$ inside its inverted list, with no need to store the raw coordinates.

step 7 / 12

7. Append to the inverted list

Append $(id, i_{1}, \dots, i_{8})$ to the inverted list $L_{i}$ . The raw coordinates of $y$ are discarded. Memory per vector:

lo g_{2} (k^{'}) + m \cdot lo g_{2} (k^{*}) = 10 + 64 = 74 bits

Click a Voronoi cell on the left to inspect the entries stored in its list.

Phase 3 · Search

step 8 / 12

8. Query arrives, probe w cells

Your true nearest neighbour can land near a cell boundary. To catch it, check the $w$ closest coarse centroids to $x$ , not just the top one (multiple assignment).

Adjust w on the left to probe more cells and see the pruning ratio update live.

step 9 / 12

9. Build the ADC lookup tables

For each probed cell $c$ , compute a query-specific residual $r_{q} = x - c$ , split it into 8 blocks, then for $j \in {1, \dots, 8}$ (one row per sub-block) and $i \in {0, \dots, 255}$ (one column per centroid), fill

LUT [j] [i] = u_{j} (r_{q}) - c_{j, i}^{2}

8 × 256 = 2,048 cells per LUT. Built once per probed cell, reused across every candidate in its inverted list.

Why is $u_{j} (r_{q})$ constant across the whole list?

The query residual relative to a specific coarse cell $c$ is

r_{q} = x - c

$x$ is the query, fixed for this search.
$c$ is the center of the coarse bucket we are currently scanning, fixed for this specific inverted list.
Therefore $r_{q}$ is identical for every comparison we make within that list.

Why is the LUT reused?

For a candidate $y$ inside that list we estimate

∥ x - y ∥^{2}

Using the residual decomposition $y \approx c + q_{p} (y - c)$ ,

∥ x - (c + q_{p} (y - c)) ∥^{2} = ∥(x - c) - q_{p} (y - c) ∥^{2} = ∥ r_{q} - q_{p} (r_{y}) ∥^{2}

$r_{q}$ is the query's offset from the cell center: same for every $y$ in this list.
$q_{p} (r_{y})$ (with $r_{y} = y - c$ ) is the candidate's offset from the cell center: different for every $y$ , but it is just a selection of centroids from the codebooks. For sub-block $j$ , the candidate stores an index $i_{j}$ , so the per-block contribution is

u_{j} (r_{q}) - c_{j, i_{j}}^{2}

Key realization. The specific index $i_{j}$ changes from candidate to candidate, but the set of possible centroids ${c_{j, 0}, c_{j, 1}, \dots, c_{j, 255}}$ is the same for the whole database, and $u_{j} (r_{q})$ is the same for the whole list. So we pre-compute the distance from the query sub-vector to every possible centroid and store it in the LUT. When the scan moves to the next candidate, there is no math: we look up the index the candidate already points to (say $142$ ) and read $LUT [j] [142]$ .

“For each subquantizer $q_{p_{j}}$ the distances between the partial residual vector $u_{j} (x - q_{c} (y))$ and all the centroids $c_{j, i}$ of $q_{p_{j}}$ are preliminarily computed and stored.” (Jégou et al., 2011)

Component	Status during list scan
Query $x$	Fixed
Cell center $c$	Fixed
Query residual $r_{q}$	Fixed
Sub-codebook centroids $c_{j, i}$	Fixed (permanent)
LUT values	Fixed (computed once at start of list scan)
Candidate $y$	Changes (iterating through the list)
Candidate indices $i_{j}$	Changes (used to look up the fixed LUT values)

step 10 / 12

10. Scan: 8 lookups, 7 adds

Each stored code $(i_{1}, \dots, i_{8})$ is 8 table indices. The ADC distance estimate is:

\tilde{d} (x, y)^{2} = j = 1 \sum 8 LUT [j] [i_{j}]

No float multiplications, no square roots. The scan loop is eight random reads from an L1-resident table plus seven adds per candidate. That is the inner loop of IVFADC.

step 11 / 12

11. Merge top-K across w lists

A fixed-capacity max-heap of size $K$ tracks the current best. Whenever a new estimate beats the heap root, the root is popped and the candidate is pushed. After scanning all $w$ lists, drain the heap in ascending order; those are the approximate nearest neighbours.

step 12 / 12

12. Why it scales

Scanning only $n w / k^{'}$ entries instead of $n$ , with each candidate costing 8 look-ups and 7 adds. Training runs once; encoding and search run forever.

Dispatched on GPU with WarpSelect (Johnson et al. 2017, §4.2), the same pipeline handles SIFT1B at 17.7 µsper query on a single Titan X.

Assuming balanced inverted lists, each query scans only about $n \cdot w / k^{'}$ entries instead of $n$ . Jégou et al. (§IV.A) recommend $k^{'}$ between 1,000 and 1,000,000 for SIFT; their Table V uses $k^{'} = 1024$ and $k^{'} = 8192$ with $w \in {1, 8, 64}$ . With $k^{'} = 1024, w = 8$ at $n = 1 0^{9}$ , that is roughly 7.8 million scanned entries per query, each costing 8 LUT look-ups and 7 additions.

On CPU, the 2011 paper reports 8.8 ms per query on a 1-million-vector GIST benchmark with these parameters (Table V). Billion-scale CPU latencies are an order of magnitude higher; the sub-millisecond regime belongs to the GPU implementation of Johnson, Douze and Jégou (2017), covered in §7.

7. Accelerating IVFPQ on GPU

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.

Mental model

Each inverted list is one aisle in a huge warehouse. A query is a shopping list split into $m$ features. The LUT is a tiny price sheet, one row per feature. A CPU sends one worker down the aisle; a GPU sends a warp: 32 threads moving in lock-step.

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

Coalesced reads. Transpose the list so the warp picks up 32 sub-codes in one 128-byte DRAM burst instead of 32 scattered ones.
Shared-memory LUT. Copy the $m \times k^{*}$ table into SRAM once per list. Every thread then reads it at ~25 cycles instead of ~400 (§5.3).
Warp scan. One thread per vector, 32 distances per tick, partial sums held in registers.
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.

Step 1 of 4

Memory layout

How the inverted list is stored decides how many DRAM transactions a warp costs.

The warp reads sub-q 0 for 4 different vectors. Where do those bytes sit in DRAM?

Row-major (CPU layout)

stride 4 → scattered

codes of vector v are stored together, one block per vector

v0q0

v0q1

v0q2

v0q3

v1q0

v1q1

v1q2

v1q3

v2q0

v2q1

v2q2

v2q3

v3q0

v3q1

v3q2

v3q3

4 threads fetch bytes at positions 0, 4, 8, 12 → 4 separate DRAM reads (32 threads → 32 reads)

transpose by sub-q

Transposed (GPU layout)

stride 1 → contiguous

codes of sub-quantizer q are stored together, one block per sub-q

v0q0

v1q0

v2q0

v3q0

v0q1

v1q1

v2q1

v3q1

v0q2

v1q2

v2q2

v3q2

v0q3

v1q3

v2q3

v3q3

4 threads fetch bytes 0, 1, 2, 3 → 1 coalesced read (32 threads → 1 × 128-byte transaction)

click to zoom

Takeaway.Row-major puts all codes of one vector together. Transposed groups all codes of one sub-quantizer together. With the transpose, 32 threads asking for sub-q j land on contiguous bytes and the memory controller answers with a single 128-byte transaction.

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

8. Real-World Use Cases

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

Semantic Search

Find documents by meaning, not just keywords. Query embeddings retrieve the most relevant passages from millions of documents.

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

Image Similarity

Reverse image search and visual deduplication. Find visually similar products, detect copyright infringement, or organize photo libraries.

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

RAG / LLM Memory

Retrieval-Augmented Generation grounds LLM responses in real data. FAISS serves as the fast retrieval backbone for context injection.

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

Recommendation Systems

Item-to-item and user-to-item recommendations. Embed user preferences and product features, then find nearest neighbors.

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

Document Deduplication

Detect near-duplicate documents at scale. Hash or embed content, then use range search to find items within a similarity threshold.

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

Anomaly Detection

Score outliers by distance to their nearest neighbors. Points far from any cluster are likely anomalies or novel inputs.

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

9. Conclusion

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.

References

Billion-scale similarity search with GPUs (Johnson et al., 2017) - The original FAISS paper.
Product quantization for nearest neighbor search (Jégou et al., 2011) - The foundation of PQ.
Least squares quantization in PCM (Lloyd, 1982, IEEE Trans. Inf. Theory) - Lloyd optimality conditions used in §5.
Improved Residual Vector Quantization for High-dimensional Approximate Nearest Neighbor Search (Liu et al., 2015) - Residual quantization.
FAISS GitHub Repository

Get in touch

We hope you enjoyed this article. If you have questions, found a bug, or just want to chat about AI and engineering, we'd love to hear from you.

Future articles?

We're planning more deep dives into:
• Graph Neural Networks
• Transformer Architecture
• System Design for ML

Share this article

All Articles