liveBook · Manning

Ivfpq

As explained in Retrieval Augmented Generation, The Foundational Ideas

IVF-PQ is a composite vector index that combines inverted-file clustering with product-quantized vector storage.

IVF-PQ combines inverted-file clustering with product-quantized storage: clustering avoids scanning every vector, while compression reduces the memory footprint of vectors inside the index. section 2.2.2

Its design separates two independent indexing decisions:

  • Narrow the search with an inverted file by scanning selected clusters instead of the entire dataset. section 2.2.2
  • Store vectors compactly with product quantization, replacing precise values with codebook-based integer identifiers. section 2.2.2

A two-stage search path

The search first takes the highway toward the relevant cluster, then follows local streets to reach nearby vectors. PQ makes those stored vectors smaller, helping large indexes fit in memory. section 2.2.2

Table 2.2 FAISS Indexing Strategies
Index Type
Best For
Key Trade-off
Seminal Paper / Origin
Flat Index (Exact Search)
The highest accuracy is required on smaller datasets (< 100K vectors). Critical for medical/legal diagnosis.
Slow, linear scaling time, making it unusable for big data.
Classical Baseline (Brute-force linear scan)
IVF (Inverted File)
Balance of speed and accuracy for mid-sized datasets (100K–10M vectors). Enterprise document search.
Parameter Sensitivity. Accuracy depends heavily on the number of clusters (nlist) and probes (nprobe).
"Video Google" (Sivic & Zisserman, 2003) adapted inverted indices for visual vectors.
HNSW (Hierarchical Navigable Small World)
Ultra-fast search is the top priority, especially for large datasets (> 1M vectors). Real-time recommendations.
High Memory Cost. ~90-95% accuracy with log-linear search time, but storing the graph structure consumes significant RAM.
Malkov and Yashunin (2016) introduced the hierarchical graph structure
Product Quantization (PQ)
Low Memory (mobile/embedded). Often combined with IVF (IVF-PQ) for billion-scale.
Lossy. Up to 10x memory reduction in exchange for a small drop in accuracy.
Jégou et al. (2011) defined subspace quantization for nearest neighbor search.

Compare IVF-PQ's clustered-and-compressed design with flat exact search and graph-based HNSW, focusing on speed, accuracy, memory, and tuning trade-offs. section 2.2.2

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Explains clustering and compression conceptually, with implementation detail shown for IVF rather than IVF-PQ.
Examples
Uses a highway-and-local-streets analogy, codebook-based image compression, and million-vector FAISS search examples.
What you can do after
Apply it via FAISS by combining cluster-based search with compressed vector storage for memory-efficient similarity search.
How it connects
Connects inverted-file indexing and product quantization within FAISS, while contrasting flat search and HNSW.

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Retrieval Augmented Generation, The Foundational Ideas. The section links point to the parts of the book it draws on.