HNSW is a graph-based approximate nearest-neighbor index for vector search. It builds layered connections: long-range highway links help searches approach a target quickly, while short-range links refine the result locally. section 2.2.2
Use HNSW when:
- Search speed is the primary requirement, especially for large datasets and real-time recommendations. section 2.2.2
- You can trade some recall and memory efficiency for log-linear search behavior and rapid retrieval. section 2.2.2
- You need to distinguish the search strategy from vector storage: HNSW walks a graph, while compression is a separate choice. section 2.2.2
FAISS configuration
Create an HNSW index with `faiss.IndexHNSWFlat(d, 32)`, then add the embedding matrix with `index.add(embeddings)`. This switches the search structure from an inverted-file baseline to HNSW. 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 HNSW with flat exact search and IVF across accuracy, scale, speed, and memory trade-offs. section 2.2.2










