Vector Search — how HNSW finds nearest neighbours

Prefer to watch? ▶ Vector Search — how HNSW finds nearest neighbour in 90 seconds ✈ Telegram

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.

The Problem: Why Brute Force Is Correct but Unusable

You already have the pieces:

Each of your 2,000,000 help documents is embedded—a point in a 768-dimensional space.
A user's question becomes a point in that same space.
"Best answer" means the nearest point in that space (highest cosine similarity).

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.

Why You Cannot Index Your Way Out

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.

Enter HNSW: The Navigable Small World

HNSW solves this by building a graph where:

Every vector is a node.
Every node is wired to M of its nearest neighbors (M is typically 5–48; higher M = more accuracy, more memory).
Search is a greedy walk: starting from a random node (or a designated entry point), hop to whichever neighbor is closer to the query. Repeat until no neighbor is closer—you have arrived.

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.

The H: Hierarchy and Layer Skip

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:

Layer L (top, sparse): Contains only a fraction of vectors, wired with long-range links. Think highways connecting cities 500 km apart.
Layer L-1 (denser): More vectors, tighter links. Main roads connecting towns 50 km apart.
Layer 0 (bottom, densest): Every single vector, linked to its M nearest neighbors. Local streets.

Search descends:

Start at the entry point on the top layer.
Greedily walk until no neighbor is closer.
Drop to the next layer and walk again from your current position.
Repeat until layer 0.

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.

Two Tuning Knobs: M and ef_search

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.

The Catch: Approximation Is a Tradeoff

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:

Raise M → more edges per node → more paths to the true nearest → higher recall, higher memory, slower build.
Raise ef_search → larger candidate set during search → more graph explored → higher recall, slower query.

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.

The Payoff

Brute force on 2,000,000 vectors:

2,000,000 comparisons
~1,240 ms
100% recall
O(n) scaling

HNSW with M=16, ef_search=200:

~1,800 comparisons
~2 ms
~99% recall
O(log n) scaling

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.

One Table: HNSW vs. Alternatives

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)

HNSW for LLM Inference and RAG

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:

Vector databases store millions of chunks (customer docs, code, research papers). Brute-force search would add 1+ seconds per query—unacceptable for interactive LLM chat.
HNSW keeps TTFT under 10ms, letting the bottleneck shift to the LLM's token generation (TPOT, time-per-output-token), not retrieval.
Approximate recall is fine here. An LLM is robust to slightly off-topic context; 99% recall is indistinguishable from 100% in practice.

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.

Tools That Use HNSW

FAISS (Meta, open-source): low-level vector search library; HNSW is one of many indices.
hnswlib (Yu. Malkov, open-source): the reference HNSW implementation; often embedded in other databases.
pgvector (Postgres extension): HNSW available via CREATE INDEX ... USING hnsw.
Qdrant (vector database): HNSW is the default index type.
Weaviate (vector database): supports HNSW alongside other structures.
Milvus (open-source vector database): HNSW available as an index option.

Verdict

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.