IVF-PQ Vector Indexing: Scaling Vector Databases to Billions of Vectors

While Hierarchical Navigable Small World (HNSW) graphs offer unmatched search latency and recall, they suffer from a severe operational bottleneck: extreme RAM consumption.

To index 100 million 1536-dimensional vectors using HNSW:

• Raw vector storage: $100\text{M}\times 1536\times 4\text{ bytes}=614.4\text{ GB}$
• Graph edges and pointer metadata: $\approx 120\text{ GB}$
• Total Server RAM required: $>730\text{ GB}$ of expensive host memory!

To scale vector search to hundreds of millions or billions of items without paying hundreds of thousands of dollars in cloud RAM instances, infrastructure teams rely on Inverted File with Product Quantization (IVF-PQ) (FAISS).

IVF-PQ compresses raw high-dimensional floating-point vectors by up to 95% while enabling ultra-fast Asymmetric Distance Computation (ADC) directly in compressed byte space.

---

1. Stage 1: Inverted File (IVF) Coarse Partitioning

The purpose of the Inverted File (IVF) layer is Non-Exhaustive Search: avoiding scanning the entire database by partitioning vector space into $K$ discrete Voronoi Cells.

Ingestion & Search Workflow:

1. Clustering: During index training, K-Means clusters the dataset into $K$ coarse centroids (${\mathbf{c}}_1,{\mathbf{c}}_2,\dots ,{\mathbf{c}}_K$).
2. Posting Lists: Each document vector is mapped to its closest centroid and appended to that centroid's inverted posting list.
3. Query Probing (nprobe): When a query $\vec{q}$ arrives, the engine computes distances to all $K$ centroids, selects the nprobe closest centroids (e.g. nprobe = 16 out of $4096$), and searches only the posting lists attached to those 16 centroids.

• Pruning: 99.6% of the database is pruned from the search space instantly!

---

2. Stage 2: Product Quantization (PQ) Compression

Once a vector is assigned to a Voronoi cell, storing the raw 1536-dimensional floating-point vector still consumes 6,144 bytes of RAM. Product Quantization (PQ) compresses this vector into a compact array of 1-byte integers.

The PQ Algorithm:

1. Split the $D$-dimensional vector space into $M$ orthogonal sub-spaces of dimension $d^{\prime }=\frac{D}{M}$.
2. Run K-Means independently within each sub-space to learn $K^{\ast }=256$ sub-centroids (requiring exactly 8 bits = 1 byte to address each centroid).
3. Replace each sub-vector with the 1-byte integer ID of its nearest sub-centroid.

• A 1536-dimensional vector ($6,144\text{ bytes}$) split into $M=64$ sub-vectors is stored as exactly 64 bytes in RAM ($96\times$ memory reduction!).

---

3. Asymmetric Distance Computation (ADC)

How does the search engine compute distances between an unquantized query $\vec{q}$ and millions of 64-byte compressed PQ codes without decompressing them?

Asymmetric Distance Computation (ADC) computes the exact distances between the query sub-vectors and the 256 codebook centroids once upfront, storing them in a small lookup table:

$\text{Table}[m,c]=\Vert {\vec{q}}_m-{\mathbf{c}}_{m,c}{\Vert }^2,m\in [\mathrm{1..}M],c\in [\mathrm{0..255}]$

When scanning a compressed vector code $\mathbf{c}=[c_1,c_2,\dots ,c_M]$:

$d(\vec{q},\vec{v})\approx {\sum }_{m=1}^M\text{Table}[m,c_m]$

The search reduces to 64 array lookups and additions in CPU L1 cache using SIMD vector instructions—executing tens of millions of distance calculations per second!

---

4. HNSW vs IVF-PQ Architecture Trade-Off Matrix

---

5. Summary & Key Takeaways

1. HNSW is Fast but Memory-Heavy: Indexing hundreds of millions of vectors in HNSW requires terabytes of expensive RAM.
2. IVF Prunes Vector Space: Inverted File clustering into $K$ Voronoi cells prunes over 98% of the database during candidate lookup.
3. PQ Compresses Vectors to Bytes: Product Quantization splits high-dimensional vectors into sub-vectors, compressing 6,144-byte vectors into 64 bytes.
4. ADC Enables Instant SIMD Lookups: Asymmetric Distance Computation evaluates compressed vectors using CPU cache lookup tables, scanning millions of vectors in milliseconds.