10. IVF vs HNSW

Chapter 10 of 18 · 15 min

KEY INSIGHT

IVF scales better with dataset size; HNSW offers better query latency for in-memory data. Choose based on your data size and latency requirements. ### Quantitative Comparison Testing with 500,000 384-dimensional vectors: ```python import faiss import numpy as np import time dimension = 384 n_vectors = 500000 # Generate test data np.random.seed(42) vectors = np.random.random((n_vectors, dimension)).astype('float32') queries = np.random.random((100, dimension)).astype('float32') # IndexFlatL2 (baseline) print("IndexFlatL2 (exact):") flat = faiss.IndexFlatL2(dimension) flat.add(vectors) start = time.time() for q in queries: flat.search(q.reshape(1, -1), 10) elapsed = time.time() - start print(f" Total time: {elapsed:.2f}s, per query: {elapsed*10:.1f}ms") # IndexIVFFlat print("\nIndexIVFFlat (nlist=4096, nprobe=40):") quantizer = faiss.IndexFlatL2(dimension) ivf = faiss.IndexIVFFlat(quantizer, dimension, 4096) ivf.train(vectors[:100000]) # Train on subset ivf.add(vectors) ivf.nprobe = 40 start = time.time() for q in queries: ivf.search(q.reshape(1, -1), 10) elapsed = time.time() - start print(f" Total time: {elapsed:.2f}s, per query: {elapsed*10:.1f}ms") # IndexHNSWFlat print("\nIndexHNSWFlat (M=32, ef=128):") hnsw = faiss.IndexHNSWFlat(dimension, 32) hnsw.hnsw.efSearch = 128 hnsw.add(vectors) start = time.time() for q in queries: hnsw.search(q.reshape(1, -1), 10) elapsed = time.time() - start print(f" Total time: {elapsed:.2f}s, per query: {elapsed*10:.1f}ms") ``` Typical results on CPU: | Index | Build Time | Memory | Query/Latency | |-------|------------|--------|---------------| | FlatL2 | <1s | 768MB | ~500ms | | IVFFlat | ~10s | 770MB | ~50ms | | HNSW | ~30s | ~1200MB | ~5ms | ### When to Use Each **Use FlatL2 when:** - Dataset < 10,000 vectors - You need exact results - Memory is not constrained **Use IVFFlat when:** - Dataset is millions of vectors - Memory is limited - You can tolerate 1-5% recall loss **Use HNSW when:** - Sub-10ms queries are required - Dataset fits in RAM - Memory is not severely constrained ### Combining IVF and HNSW FAISS supports composite indexes: use HNSW as the IVF quantizer for faster clustering: ```python # HNSW-based quantizer for IVF hnsw_quantizer = faiss.IndexHNSWFlat(dimension, 32) index = faiss.IndexIVFFlat(hnsw_quantizer, dimension, nlist=1024) index.train(vectors) index.add(vectors) ```

EXERCISE

Load 100,000 real document embeddings. Build both IVFFlat and HNSW indexes. Compare query results (not just speed) by checking if both return the same top-5 results.