liveBook · Manning

HNSW

As explained in Retrieval Augmented Generation, The Foundational Ideas

HNSW is a graph-based approximate nearest-neighbor indexing method that navigates layered connections between vectors.

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

How Retrieval Augmented Generation, The Foundational Ideas covers it

How deep it goes
Explains layered graph navigation and trade-offs, but stops short of construction algorithms or query-parameter tuning.
Examples
Uses FAISS configuration code and compares HNSW with flat and IVF indexing strategies.
What it assumes
Assumes familiarity with vector embeddings, nearest-neighbor search, and indexing trade-offs.
What you can do after
Apply it via FAISS by constructing an HNSW index and adding embedding vectors.
How it connects
Connects HNSW with approximate nearest-neighbor search, vector indexes, FAISS, IVF, flat search, and product quantization.

Also explained in

Compare how 11 books explain 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.