Product Quantization, Composite Indexes, and FAISS

Brute force finds the exact nearest neighbor in a billion vectors. It takes a week. HNSW finds the approximately-nearest one in 800 microseconds. Most users cannot tell the difference, and nobody waits a week.

Vec, Approximate-and-Proud AI Agent

Building on the nearest neighbor problem and the graph and inverted-list indexes from Section 31.3 (which introduced the HNSW navigation pattern in Figure 31.4.1), this part adds the compression layer that lets these indexes scale to billions of vectors. Product quantization gives us aggressive memory savings, composite indexes combine the techniques we have seen, and the FAISS index factory provides a single notation for assembling them. We close with selection guidance.

31.4.1 Product Quantization (PQ)

Product Quantization compresses vectors by splitting each d-dimensional vector into m sub-vectors, then quantizing each sub-vector independently using a small codebook. A 768-dimensional vector split into 96 sub-vectors of 8 dimensions each, with 256 codes per sub-vector, requires only 96 bytes of storage instead of 3,072 bytes (768 × 4 for float32). This represents a 32x compression ratio. Figure 31.4.2 shows how product quantization compresses vectors by replacing sub-vectors with codebook indices.

Formally, PQ approximates a vector $x \in \mathbb{R}^d$ as a product (concatenation) of $m$ sub-quantizers, one per disjoint sub-space. Let $x = [x^{(1)}, \ldots, x^{(m)}]$ with each $x^{(i)} \in \mathbb{R}^{d/m}$ and let $\mathcal{C}_i = \{c_{i,1}, \ldots, c_{i,K}\}$ be the codebook learned for sub-space $i$ (typically by k-means with $K = 2^b$ centroids, $b = 8$). The quantizer is

$$ q(x) \;=\; \big[\, q_1(x^{(1)}), \; q_2(x^{(2)}), \; \ldots, \; q_m(x^{(m)}) \,\big], \qquad q_i(x^{(i)}) \;=\; \arg\min_{c \in \mathcal{C}_i} \lVert x^{(i)} - c \rVert_2, $$

so the full code space has $K^m$ effective entries while only $m \cdot K$ centroids are ever stored, giving the "product" in product quantization. The asymmetric distance computation (ADC) reuses this decomposition to score a full-precision query $y$ against compressed codes as a sum of $m$ table lookups,

$$ \tilde{d}(y, x)^2 \;=\; \sum_{i=1}^{m} \big\lVert y^{(i)} - q_i(x^{(i)}) \big\rVert_2^2, $$

which is what makes ADC essentially memory-bound rather than compute-bound at search time.

How PQ Works

1. Split: Divide each d-dimensional vector into m sub-vectors of d/m dimensions.
2. Train codebooks: For each sub-vector position, run k-means with 256 centroids (or another power of 2) on the training data. This produces m codebooks, each with 256 entries.
3. Encode: Replace each sub-vector with the index of its nearest codebook entry (a single byte for 256 codes).
4. Compute distances: At query time, precompute a distance lookup table from the query sub-vectors to all codebook entries, then sum table lookups for each compressed vector.

Algorithm: PQ Train + Encode + ADC search
Input:  corpus X in R^{N x d}, sub-vector count m (d mod m = 0),
        bits-per-subvector b (default 8 => K = 256 centroids per book)
Output: m codebooks {C_1, .., C_m}, compressed codes Q in {0,..,K-1}^{N x m}

  // ============= TRAIN =============
  d_sub := d / m
  For i = 1..m:
      X_i := X[:, (i-1)*d_sub : i*d_sub]                    // i-th sub-vector slice
      C_i := KMeans(X_i, K = 2^b)                           // K centroids in R^{d_sub}

  // ============= ENCODE =============
  For each vector v in X:
      For i = 1..m:
          v_i := v[(i-1)*d_sub : i*d_sub]
          Q[id(v), i] := argmin_k ||v_i - C_i[k]||          // one byte per sub-vector

  // ============= SEARCH (Asymmetric Distance Computation, ADC) =============
  Input: query q in R^d, codes Q, codebooks C_1..C_m, k
  // 1. Precompute the m * K lookup table once per query
  For i = 1..m, k = 1..K:
      LUT[i][k] := ||q[(i-1)*d_sub : i*d_sub] - C_i[k]||^2

  // 2. Score every encoded vector by m table lookups
  H := MaxHeap(k)
  For id = 1..N:
      d2 := 0
      For i = 1..m:
          d2 := d2 + LUT[i][ Q[id, i] ]                     // ~m additions
      H.push((id, d2))
      if |H| > k: H.pop_max()
  Return H

Storage: m * b bits per vector (e.g. d = 768, m = 96, b = 8 => 96 bytes, vs 3072 bytes
for float32, a 32x compression).
Asymmetric distance: q is in full precision, only stored vectors are quantized, so the
quantization error appears once per term, not twice (symmetric would quantize q too and
roughly double the error).

Figure 31.4.2a: Product Quantization splits each vector into sub-vectors and replaces each with a codebook index, achieving high compression ratios.

# IVF + Product Quantization composite index in FAISS
import faiss
import numpy as np
import time
dim = 768
n_vectors = 1_000_000
np.random.seed(42)
vectors = np.random.randn(n_vectors, dim).astype(np.float32)
faiss.normalize_L2(vectors)
query = np.random.randn(1, dim).astype(np.float32)
faiss.normalize_L2(query)
# IVF-PQ: combines partitioning with compression
nlist = 1024 # Number of IVF partitions
m_subquantizers = 96 # Number of sub-quantizers (must divide dim)
nbits = 8 # Bits per sub-quantizer (256 codes)
index = faiss.IndexIVFPQ(
    faiss.IndexFlatIP(dim), # Coarse quantizer
    dim,
    nlist,
    m_subquantizers,
    nbits
)
# Train and add
print("Training IVF-PQ index...")
index.train(vectors)
index.add(vectors)
# Memory comparison
flat_memory = n_vectors * dim * 4 # float32
pq_memory = n_vectors * m_subquantizers # 1 byte per sub-quantizer
print(f"Flat memory: {flat_memory / 1e9:.2f} GB")
print(f"PQ memory: {pq_memory / 1e6:.0f} MB")
print(f"Compression: {flat_memory / pq_memory:.0f}x")
# Search
index.nprobe = 32
start = time.time()
distances, indices = index.search(query, k=10)
search_time = (time.time() - start) * 1000
print(f"Search time: {search_time:.2f}ms")

31.4.2 Composite Indexes and Advanced Techniques

HNSW gives fast traversal; Product Quantization gives memory compression. The real production systems stack them, using HNSW to find candidate clusters and PQ to score within each cluster, layering two approximations to exploit different parts of the cost budget. The classic composite index is IVF-HNSW, where the inverted file's coarse quantizer is itself an HNSW graph.

IVF-HNSW

Instead of using a flat (brute-force) coarse quantizer in IVF, the coarse quantizer itself can be an HNSW index. This accelerates the cluster assignment step when there are many clusters (tens of thousands), which is important for very large datasets where you need fine-grained partitioning.

ScaNN (Scalable Nearest Neighbors)

Google's ScaNN algorithm introduces anisotropic vector quantization, which accounts for the direction of quantization error rather than minimizing error magnitude uniformly. Standard PQ minimizes the overall reconstruction error, but ScaNN specifically minimizes the error in the direction that matters for inner product computation. This produces better search quality at the same compression ratio.

31.4.3 Index Selection Guide

31.4.4 FAISS Index Factory

FAISS provides an index factory that lets you construct composite indexes using a string descriptor. This is the most convenient way to experiment with different configurations. Figure 31.4.5 shows how a factory string composes preprocessing, coarse quantization, and encoding into a single pipeline.

Figure 31.4.5a: The FAISS index factory parses a comma-separated string into a three-stage pipeline (optional preprocessing, coarse quantizer, encoder) and returns a single composite index. Swapping the IVF/HNSW coarse quantizer or the Flat/PQ/SQ encoder lets you walk the memory and recall axes without rewriting any client code.

# FAISS index factory: composing index types with string descriptors
import faiss
import numpy as np
dim = 768
n_vectors = 500_000
vectors = np.random.randn(n_vectors, dim).astype(np.float32)
faiss.normalize_L2(vectors)
# Index factory string format: "preprocessing,coarse_quantizer,encoding"
index_configs = {
    "Flat": "Flat",
    "HNSW32": "HNSW32",
    "IVF1024,Flat": "IVF1024,Flat",
    "IVF1024,PQ96": "IVF1024,PQ96",
    "IVF1024,SQ8": "IVF1024,SQ8", # Scalar quantization (8-bit)
    }
for name, factory_str in index_configs.items():
    index = faiss.index_factory(dim, factory_str, faiss.METRIC_INNER_PRODUCT)
    # Train if needed
    if not index.is_trained:
        index.train(vectors[:100_000]) # Train on subset
        index.add(vectors)
        # Estimate memory (rough approximation)
        if "PQ96" in factory_str:
            mem_mb = n_vectors * 96 / 1e6
        elif "SQ8" in factory_str:
            mem_mb = n_vectors * dim / 1e6
        else:
            mem_mb = n_vectors * dim * 4 / 1e6
            print(f"{name:>20}: {n_vectors:,} vectors, ~{mem_mb:.0f} MB")

pip install pgvector psycopg[binary]
import psycopg
from pgvector.psycopg import register_vector

conn = psycopg.connect("postgresql://user@localhost/rag")
conn.execute("CREATE EXTENSION IF NOT EXISTS vector")
register_vector(conn)
conn.execute("CREATE TABLE docs (id bigserial PRIMARY KEY, body text, emb vector(1024))")
conn.execute("CREATE INDEX ON docs USING hnsw (emb vector_cosine_ops)")
conn.execute("INSERT INTO docs (body, emb) VALUES (%s, %s)", (text, embedding))

rows = conn.execute(
    "SELECT body FROM docs ORDER BY emb <=> %s LIMIT 5", (query_emb,)
).fetchall()