Module 2: How Vector Databases Work (Conceptual)

Capsule 06: PQ - Product Quantization

Understand HOW PQ works (Product Quantization) to compress vectors 4-8x, reducing memory dramatically with an accuracy trade-off.

By the end of this capsule:

✅ You'll explain what Product Quantization is (codebook compression)
✅ You'll understand the trade-off: 4-8x less memory vs 85-90% accuracy
✅ You'll know the key parameters (m, nbits)
✅ You'll decide when to use PQ (>5M vectors, RAM critical)

Estimated time: 8-10 minutes

📦 What is Product Quantization?

Definition

PQ = Product Quantization

It's a vector compression technique that divides a vector into sub-vectors, then replaces each sub-vector with a code (an index) from a codebook.

Result: A compressed vector 4-8x smaller with slightly lower accuracy.

Analogy: Image compression (JPEG)

Uncompressed image (PNG):

Each pixel: 24 bits (RGB: 8+8+8)
1000x1000 image: 24,000,000 bits = 3 MB

Compressed image (JPEG):

Divides the image into 8x8 blocks
Replaces similar blocks with codes
Result: 300 KB (10x compression)
Trade-off: 90% quality (visible artifacts when you zoom in)

Applied to vectors:

Original vector: 1536 dims × 4 bytes = 6 KB
Compressed vector (PQ): 1536 dims → 192 codes × 1 byte = 192 bytes
Result: 32x compression
Trade-off: 85-90% accuracy (vs 100% original)

🏗️ PQ architecture

Step 1: Splitting into sub-vectors

# Original vector (1536 dims)
vector = [0.1, 0.5, 0.8, ..., 0.3]  # 1536 dims

# Split into m sub-vectors
m = 8  # Number of sub-vectors
sub_vector_size = 1536 / 8 = 192 dims

sub_vectors = [
    [0.1, 0.5, ..., 0.2],  # Sub-vector 1 (192 dims)
    [0.8, 0.3, ..., 0.7],  # Sub-vector 2 (192 dims)
    ...
    [0.4, 0.9, ..., 0.3],  # Sub-vector 8 (192 dims)
]

Key: A 1536-dim vector is split into 8 sub-vectors of 192 dims each.

Step 2: Building the codebook (Training)

A codebook is a dictionary that maps sub-vectors to codes.

# For each sub-vector, run k-means
def build_codebook(all_vectors, m=8, k=256):
    codebooks = []
    
    for i in range(m):  # For each sub-vector position
        # Extract the sub-vectors from all vectors
        sub_vectors = [v[i] for v in all_vectors]
        
        # k-means to find k centroids
        centroids = kmeans(sub_vectors, k=256)
        
        # Store the codebook
        codebooks[i] = centroids  # 256 centroids for sub-vector i
    
    return codebooks

Result:

8 codebooks (one per sub-vector)
Each codebook: 256 centroids (192 dims each)

Visualization:

Codebook 0 (sub-vector 0):
  0: [0.1, 0.2, ..., 0.3]  ← Centroid 0
  1: [0.5, 0.1, ..., 0.7]  ← Centroid 1
  ...
  255: [0.8, 0.9, ..., 0.2]  ← Centroid 255

Codebook 1 (sub-vector 1):
  0: [0.3, 0.4, ..., 0.1]
  ...
  255: [0.6, 0.5, ..., 0.9]

... (8 codebooks total)

Step 3: Encoding (Compressing vectors)

def encode_vector(vector, codebooks, m=8):
    codes = []
    
    for i in range(m):  # For each sub-vector
        sub_vector = vector[i]
        
        # Find the closest centroid in codebook i
        nearest_centroid_id = find_nearest(sub_vector, codebooks[i])
        
        codes.append(nearest_centroid_id)  # 0-255 (1 byte)
    
    return codes  # [123, 45, 200, 12, 89, 150, 3, 67]

Result:

Original vector: 1536 floats × 4 bytes = 6144 bytes
Compressed vector: 8 codes × 1 byte = 8 bytes
Compression: 768x

But in practice: You also store the codebooks (overhead), so the effective compression is ~4-8x.

Step 4: Search with compressed vectors

def search_pq(query, compressed_vectors, codebooks, k=10):
    # 1. Encode the query using the codebooks
    query_codes = encode_vector(query, codebooks)
    
    # 2. Compute the asymmetric distance
    # (original query vs compressed vectors)
    similarities = []
    for compressed_vec in compressed_vectors:
        # Compute the distance using the codebooks
        dist = asymmetric_distance(query, compressed_vec, codebooks)
        similarities.append(dist)
    
    # 3. Return top-k
    return top_k(similarities, k)

Key: The query is NOT compressed (it uses the original vector). Only the database vectors are compressed.

📊 Trade-off: Accuracy vs Memory

Accuracy loss

Why accuracy drops:

When you replace a sub-vector with its closest centroid, you lose precision.

Example:

Original sub-vector:     [0.123, 0.456, 0.789]
Closest centroid:        [0.120, 0.450, 0.800]
Error:                   [0.003, 0.006, 0.011]

Multiplied across 8 sub-vectors → Accumulated error.

Typical accuracy:

Configuration	Accuracy	Memory (1M vecs)
No PQ (original)	100%	6 GB
PQ m=8, nbits=8	88-92%	1 GB (6x compression)
PQ m=16, nbits=8	85-90%	2 GB (3x compression)
PQ m=8, nbits=4	80-85%	0.5 GB (12x compression)

Memory saving

Calculation:

Original vector:
- Dims: 1536
- Type: float32 (4 bytes)
- Size: 1536 × 4 = 6144 bytes = 6 KB

Compressed vector (PQ):
- Sub-vectors: m = 8
- Bits per code: nbits = 8 (1 byte)
- Size: 8 × 1 = 8 bytes

Compression: 6144 / 8 = 768x

In practice with overhead:

Codebooks: 8 × 256 × 192 × 4 = 1.5 MB (shared)
Effective compression: ~6x for 1M vectors

⚙️ Key PQ parameters

1. m (Number of sub-vectors)

Definition: How many sub-vectors to split the original vector into.

Impact:

High m (16, 32):
- ✅ Better accuracy (smaller sub-vectors = more precise centroids)
- ❌ Less compression (more codes to store)
- ❌ Slower query (more lookups in the codebook)
Low m (4, 8):
- ✅ Higher compression
- ✅ Fast query
- ❌ Lower accuracy

Practical rule: m = 8 (accuracy/compression balance)

2. nbits (Bits per code)

Definition: How many bits to use for each code (it affects the codebook size).

Impact:

High nbits (8, 16):
- ✅ Large codebook (256, 65536 centroids)
- ✅ Better accuracy (more centroids = better representation)
- ❌ More memory for the codebooks
Low nbits (4, 6):
- ✅ Small codebook (16, 64 centroids)
- ✅ Less memory
- ❌ Lower accuracy

Practical rule: nbits = 8 (256 centroids, balance)

Trade-offs visualized

Accuracy vs Compression

High Accuracy   m=16, nbits=8
(90%)          ▲  ❌ 3x compression
               │
Medium         │  m=8, nbits=8
Accuracy       │  ⚖️ 6x compression
(88%)          │  ← Recommended
               │
Low Accuracy   │  m=8, nbits=4
(82%)          │  ✅ 12x compression
               └─────────────────
                 Low ← Memory → High

🆚 Comparison: HNSW vs IVF vs PQ

Complete comparison table

Dimension	HNSW	IVF	PQ	IVF + PQ
Complexity	O(log n)	O(sqrt(n))	O(n) compressed	O(sqrt(n)) compressed
Accuracy	95-99%	90-95%	85-90%	85-92%
Latency (1M)	15-20 ms	30-50 ms	20-40 ms	25-45 ms
Memory (1M)	4-8 GB	1-2 GB	0.5-1 GB	0.3-0.6 GB
Compression	1x	1x	6x	8x
Build time	5-10 min	2-3 min	10-15 min	15-20 min
Best for	<1M, critical accuracy	>1M, limited memory	>5M, RAM critical	>10M, extreme scale

When to use each one

HNSW:

✅ <1M vectors
✅ Accuracy >95% required
✅ You have enough RAM

IVF:

✅ 1-5M vectors
✅ 90% accuracy is OK
✅ Moderate memory

PQ:

✅ >5M vectors
✅ 85-90% accuracy is enough
✅ RAM very limited

IVF + PQ:

✅ >10M vectors
✅ 85-90% accuracy is enough
✅ Maximum scale (100M+ vectors)

🏭 PQ in practice: Faiss

PQ standalone

import faiss
import numpy as np

# 1. Create the PQ index
dimension = 1536
m = 8  # Sub-vectors
nbits = 8  # Bits per code (256 centroids)

index = faiss.IndexPQ(dimension, m, nbits)

# 2. Train (build the codebooks)
vectors = np.random.random((1_000_000, dimension)).astype('float32')
index.train(vectors)

# 3. Add vectors
index.add(vectors)

# 4. Query
query = np.random.random((1, dimension)).astype('float32')
distances, indices = index.search(query, k=10)

# Memory: ~1 GB (vs 6 GB without PQ)
# Accuracy: ~88%

IVF + PQ (Combined)

Best configuration for extreme scale:

# IVF + PQ combined
dimension = 1536
nlist = 1000  # IVF clusters
m = 8  # PQ sub-vectors
nbits = 8  # PQ bits

quantizer = faiss.IndexFlatL2(dimension)
index = faiss.IndexIVFPQ(quantizer, dimension, nlist, m, nbits)

# Train
index.train(vectors)

# Add
index.add(vectors)

# Query
index.nprobe = 10
distances, indices = index.search(query, k=10)

# Memory: ~600 MB for 1M vectors (10x compression)
# Accuracy: ~90%

Trade-off:

IVF reduces the search space (clusters)
PQ reduces memory (compression)
Combined = extreme scale with acceptable accuracy

📊 Benchmark: PQ in production

Scenario A: 5M vectors

Configuration	Accuracy	Latency	Memory	Build Time
HNSW	98%	30 ms	24 GB ❌	50 min
IVF	93%	50 ms	10 GB	15 min
PQ (m=8)	88%	35 ms	5 GB ✅	60 min
IVF+PQ	90%	45 ms	3 GB ✅	70 min

Conclusion: PQ or IVF+PQ are viable when HNSW requires too much RAM.

Scenario B: 50M vectors

Configuration	Accuracy	Latency	Memory	Viability
HNSW	98%	80 ms	240 GB ❌	Impractical
IVF	92%	90 ms	100 GB ❌	Very expensive
IVF+PQ	89%	85 ms	25 GB ✅	Viable

Conclusion: IVF+PQ is the only viable option for 50M+ vectors on reasonable hardware.

Scenario C: 100M vectors

Configuration	Memory	Cost (AWS)	Accuracy
HNSW	480 GB	$4000/month ❌	98%
IVF+PQ (m=8, nbits=8)	50 GB	$400/month ✅	88%

Trade-off: 10% accuracy loss → 10x cost reduction.

Decision: If 88% accuracy is enough → Use IVF+PQ (massive savings).

✅ Advantages and disadvantages of PQ

Advantages

4-8x less memory
- 1M vectors: 6 GB → 1 GB (HNSW vs PQ)
- Lets you handle 10M-100M vectors in reasonable RAM
Economical
- Reduces hardware/cloud cost dramatically
- AWS: $4000/month → $400/month (10x)
Acceptable latency
- 20-40ms (vs 15ms HNSW)
- Enough for many use cases
Combinable with IVF
- IVF+PQ = extreme scale
- Best of both worlds

Disadvantages

Lower accuracy (85-90%)
- vs 98% HNSW
- Can be a deal-breaker if accuracy is critical
Slow build time
- Computing the codebooks with k-means takes time
- 10-15 min for 1M vectors
Requires training
- You need a representative dataset
- If the distribution changes → rebuild the codebooks
No incremental updates
- Adding vectors requires rebuilding the codebooks
- Better for batch updates

🔗 Connection with RAG

When to use PQ in RAG

Signs you need PQ:

Dataset >5M vectors
- HNSW requires >40 GB RAM (impractical)
- PQ reduces it to 8 GB
85-90% accuracy is enough
- Not critically customer-facing
- Internal search, analytics, recommendations
Limited budget
- Cloud cost is critical
- Self-hosted with limited RAM
Batch processing
- You don't need latency <100ms
- Rebuilding codebooks nightly is OK

RAG example: Massive internal knowledge base (50M Confluence + Slack + Jira).

Tiered architecture (HNSW + IVF + PQ)

An advanced system can use multiple indexes:

Tier 1: Hot data (last 7 days, 50K vectors)

HNSW for high accuracy (98%)
Latency: 15ms

Tier 2: Warm data (last 30 days, 500K vectors)

IVF for balance (93% accuracy)
Latency: 30ms

Tier 3: Cold data (historical, 10M vectors)

IVF+PQ for memory efficiency (88% accuracy)
Latency: 60ms

Query strategy:

Search Tier 1 (HNSW)
If not enough results → Search Tier 2 (IVF)
If still not enough → Search Tier 3 (IVF+PQ)

✅ Comprehension checklist

Verify that you understood this capsule:

What is Product Quantization?
- Answer: A compression technique that divides vectors into sub-vectors, then replaces each sub-vector with a code from a codebook.
Why does PQ reduce memory 4-8x?
- Answer: A 1536-float vector (6 KB) is compressed to 8 codes (8 bytes). The codebook overhead reduces effective compression to 4-8x.
What does the m parameter do?
- Answer: The number of sub-vectors. High m = better accuracy + less compression. Low m = more compression + lower accuracy.
When to use PQ vs HNSW?
- Answer: PQ when >5M vectors, RAM critical, 85-90% accuracy is enough. HNSW when accuracy is critical (>95%), <1M vectors.
Why combine IVF + PQ?
- Answer: IVF reduces the search space (clusters), PQ reduces memory (compression). Combined = extreme scale (100M+ vectors).

If you answered 4-5/5 correctly → ✅ Ready for Capsule 07 (Comparison)

🚀 Next step

Now that you know HNSW, IVF, and PQ individually, we'll compare them directly.

Next capsule: 07 - HNSW vs IVF vs PQ comparison

You'll learn:

Decision tree: Which algorithm to choose based on requirements
Side-by-side benchmarks in real scenarios
Recommended configuration per RAG use case
Migration path (HNSW → IVF → IVF+PQ)

Key: A decision framework for choosing the right algorithm in your RAG system.

Reading time: 8-10 minutes
Next: 07-algorithm-comparison.md

← PreviousCapsule 05: IVF - Inverted File Index Next →Capsule 07: HNSW vs IVF vs PQ comparison - Decision Framework