liveBook · Manning

Inverted File Index

As explained in Retrieval Augmented Generation, The Foundational Ideas

IVF is an inverted-file vector indexing method that partitions vectors into clusters and searches selected clusters.

An inverted file index (IVF) partitions vectors into clusters, identifies the most promising clusters for a query, and searches only those regions instead of scanning every vector. This reduces search time while trading against recall and parameter sensitivity. section 2.2.2

A practical IVF workflow separates offline indexing from online querying:

  • Choose a coarse quantizer and the number of centroids (nlist). section 2.2.2
  • Train the index, add the vectors, and search selected clusters using a probe setting (nprobe). section 2.2.2
  • Tune speed, recall, and memory for the workload; combine IVF with product quantization when memory reduction matters. section 2.2.2

FAISS search over one million vectors

A FAISS IndexIVFFlat uses an IndexFlatL2 coarse quantizer and 1,000 centroids. It trains on the embeddings, adds them, and searches for the ten nearest results; the demonstrated query completes in 0.0015 seconds. 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 with exact flat search and HNSW by dataset scale, priority, and trade-off. section 2.2.2

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Explains clustering, selected-cluster search, parameters, and FAISS construction without deriving clustering internals.
Examples
Uses a FAISS IndexIVFFlat example with one million vectors, 1,000 centroids, ten results, and measured query time.
What it assumes
Assumes vector embeddings and a basic nearest-neighbor search task; demonstrates the FAISS indexing workflow directly.
What you can do after
Apply it via FAISS by training an IVF index, adding embeddings, searching selected clusters, and tuning its trade-offs.
How it connects
Connects vector indexing with clustering, product quantization, flat search, HNSW, and FAISS.

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.