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
