📺 Prefer to watch?
[90-second YouTube Short]· 💬[Telegram] Originally published on software-engineer-blog.com.
Your documentation site has 2,000,000 help articles. A user types a question into the search box and gets the best match in 2 milliseconds—without the system ever comparing that question to almost any of them. This is not magic. It's HNSW: Hierarchical Navigable Small World, the graph structure that powers vector search in FAISS, pgvector, Qdrant, Weaviate, and Milvus.
Mental model: HNSW is a multi-layer graph where every vector points to its nearest neighbors, and search is a greedy walk that descends from sparse long-range links at the top to dense fine-grained links at the bottom—like taking highways down to local streets to find an address.
You already have the pieces:
The obvious solution is also the correct one: compare the query point against all 2,000,000 document points, measure distance to each, return the closest. With 768 dimensions per vector, that's roughly 1,540,000 arithmetic operations per document, summing to about 1,240 milliseconds on a single core.
Worse: it scales linearly. Double your documents, double your wait. Triple them, triple the wait. At 10 million documents, you are looking at 6+ seconds. At 100 million, a minute or more. And every new search pays the full price.
Your first instinct: Can't we just use a B-tree? B-trees are brilliant for one-dimensional sorting. They let you find the number 42 in a billion-element list in log(n) comparisons.
But "nearest neighbor" in 768 dimensions is not sorting on one axis. Closeness is simultaneous proximity across all 768 axes. A B-tree sorts on one—your longitude, your latitude, your price. The second you introduce a second dimension, tree structures collapse because there is no left-right order that preserves nearness in 2D, let alone 768D.
Some databases (PostgreSQL with pgvector) do attempt tree-based approaches like IVFFlat (Inverted File with flat clusters), but they still scan multiple clusters and fall back to brute force within each. They are faster than pure brute force, but still O(n) in the worst case.
You need a different shape: a graph.
HNSW solves this by building a graph where:
This is approximate search: you may not find the true global nearest neighbor. Instead, you find a local nearest neighbor—the best one reachable by greedily following edges. But because every node is connected to its nearby neighbors, and those neighbors connect to their neighbors, you can usually reach the true global nearest in a few hops.
On the AskDocs example: instead of 2,000,000 comparisons, you make roughly 1,800 comparisons across maybe 15–20 hops. That's 0.09% of the work. Latency drops from 1,240 ms to 2 ms.
One flat graph with M neighbors per node has a problem: a greedy walk might need hundreds of hops to cross the graph. Start at one end, need to reach the other; your neighbors are all locally nearby, so you take tiny steps.
HNSW solves this with layers—a skip-list-like idea: Search descends:
On layer 0, you refine the answer among nearby vectors. The higher layers got you in the right neighborhood fast; the lower layers get you to the exact street.
Result: 15–20 hops instead of hundreds. And the number of hops is logarithmic in the dataset size. HNSW has two main hyperparameters:
M: Edges per node (default ~16). Higher M = faster search but more memory and slower insertions.
ef_search: The size of a candidate list kept during search. The algorithm explores the graph, keeping the N best candidates seen so far. Higher ef_search = more of the graph explored = higher recall but slower search.
You set ef_search at query time, not build time. This lets you tune recall vs. latency per query. A strict recall requirement? Raise ef_search. A latency deadline? Lower it.
HNSW is approximate, not exact. A greedy walk can settle into a local minimum—the best neighbor you can reach from your current position, but not the global best. This is especially likely in sparse regions of the embedding space or when M is small.
Accuracy is measured as recall: the fraction of true nearest neighbors found. A recall of 0.99 means 99% of your top-10 results would have appeared in a brute-force top-10.
Recall is tunable:
You cannot have perfect recall at perfect speed. You choose your point on the recall-latency curve. Most production systems run at 95–99% recall to stay sub-10ms; some (e.g., recommendation systems) drop to 90% recall and trade 0.5ms latency for a small recall penalty.
Brute force on 2,000,000 vectors:
HNSW with M=16, ef_search=200: You trade 1% accuracy for a 600× speedup. In practice, that 1% is almost never noticed by users—the wrong answer is so close in meaning space that it is functionally equivalent.
| Approach | Lookups (2M vectors) | Latency | Recall | Scaling | Memory Overhead |
|---|---|---|---|---|---|
| Brute Force | 2,000,000 | ~1,240 ms | 100% | O(n) | Minimal |
| IVFFlat (clustering) | ~100,000 | ~60 ms | ~98% | O(n) worst-case | Low |
| HNSW (hierarchical graph) | ~1,800 | ~2 ms | ~99% | O(log n) | Moderate (M × n edges) |
In Retrieval-Augmented Generation (RAG), you embed a user's prompt and search a knowledge base to fetch relevant context before passing it to an LLM. Latency here is TTFT (time-to-first-token): every millisecond spent searching is a millisecond the user waits before the model starts generating.
HNSW is essential because:
When building a RAG pipeline, choose HNSW (via FAISS, Qdrant, Weaviate, or pgvector) over brute-force search; your TTFT will stay latency-bound by the LLM, not the retriever.
CREATE INDEX ... USING hnsw
.Reach for brute-force search when you have <100k vectors and latency is not a constraint (offline analytics, one-time batch jobs).
Reach for HNSW when you have millions of vectors, need sub-10ms latency, and can tolerate 1–5% recall loss (RAG, recommendation systems, real-time search).
Watch the 90-second reel on YouTube to see this in motion: the walk down the layers, the greedy hops, the latency ticking from 1,240 ms down to 2 ms.