How does HNSW work in one paragraph?
hardAnswer
- Hierarchical Navigable Small World (Malkov 2018): build a multi-layer graph where higher layers are sparser 'highways' and the lowest layer has all points densely connected to nearest neighbors.
- Insertion: pick a random top layer for each new point, greedy-search from the top down to find its neighbors at each layer.
- Search: start at the top, greedy-descend to the query's neighborhood, then explore the lowest layer.
- Log-scale query time in the number of vectors, ~99% recall vs exact NN in practice.
- Memory-hungry (~30-100 bytes/vector for the graph).
Check yourself — multiple choice
- HNSW is a hash-based index
- Multi-layer graph with sparse top / dense bottom; log-scale search time, ~99% recall vs exact — memory-heavy
- Only for images
- Requires GPU
HNSW: hierarchical graph → log-scale search, high recall, memory cost.
#vector-db#retrieval
Practise LLMs & GenAI
214 interview questions in this topic.
Related questions
- What's the trade-off between embedding dimension and retrieval quality?
- How do vector databases differ from traditional databases?
- What is IVF-PQ and when do you use it?
- How do metadata filters interact with vector search?
- How does Retrieval-Augmented Generation (RAG) work?
- What are text embeddings and how are they used?