# HNSW: Efficient and Robust Approximate Nearest Neighbor Search using Hierarchical Navigable Small World Graphs

**Type:** paper
**Tier:** 2 (Foundational Paper)
**Author(s):** Yu. A. Malkov, D. A. Yashunin
**Date:** 2016 (submitted 2016-03-30; final revision 2018-08-14; published IEEE TPAMI 2020)
**URL:** https://arxiv.org/abs/1603.09320
**Accessed:** 2026-06-01

## Why This Source Matters

A vector database's speed is not magic — it is an algorithm. HNSW is the index that powers Chroma (and Qdrant, Weaviate, FAISS, pgvector, and most others). This paper is the primary source for *why* semantic search can rank a query against millions of vectors in milliseconds instead of doing a brute-force scan. It grounds the lesson's core scaling claim and the "approximate, not exact" tradeoff a learner must understand before trusting a vector DB's results.

## Key Claims

### The problem
- **Approximate K-nearest-neighbor (ANN) search**: find the vectors closest to a query without comparing against every stored vector. Exact (brute-force) search is `O(N)` per query — linear in corpus size — which becomes prohibitive at scale.

### What HNSW is
- A method that is "fully graph-based, without any need for additional search structures" — it builds proximity graphs and searches them, rather than partitioning space with trees.
- It constructs "a multi-layer structure consisting from hierarchical set of proximity graphs (layers) for nested subsets of the stored elements."

### How it works (intuition)
- Elements are assigned to layers "with an exponentially decaying probability distribution" — most elements live only in the bottom layer; few reach the top. This creates **scale separation**: upper layers have long-range links, lower layers short-range.
- Search starts at the top layer and **greedily routes** toward the query, descending layer by layer — like zooming in. The result is "graphs similar to the previously studied Navigable Small World (NSW) structures while additionally having the links separated by their characteristic distance scales."

### The payoff
- The structure "allows a logarithmic complexity scaling" of search — roughly `O(log N)` instead of `O(N)`.
- Empirically it "is able to strongly outperform previous opensource state-of-the-art vector-only approaches," making it the de facto standard ANN index.

## Relevant To

- concepts: [approximate-nearest-neighbor, hnsw, vector-database, retrieval, navigable-small-world, search-complexity]
- projects: [03-semantic-search, 04-pdf-research-assistant]

## Notes

- **Approximate is a feature, not a bug.** HNSW trades exact recall for `O(log N)` speed. Tunable knobs (`ef_search`, `ef_construction`, `M`/`max_neighbors`) move the recall-vs-speed/memory point. Higher `ef_search` → more candidates explored → higher recall, slower query.
- The exact baseline is the brute-force cosine scan from Project 02. Comparing HNSW results against that brute-force ranking on a small corpus is the way to *see* the approximation (and confirm it is near-perfect at small scale).
- This is why the vector DB matters: the database is essentially "an HNSW index + storage + a query API" around the embeddings Project 02 produced.