HNSW Explained: How Vector Search Finds a Needle in a Billion-Vector Haystack

Nagesh Singh Chauhan

9 minutes ago

10 min read

Hierarchical Navigable Small World (HNSW) is a state-of-the-art algorithm used for an approximate search of nearest neighbours.

Why HNSW matters

HNSW is the algorithm that lets a vector database search millions of items in a few milliseconds instead of a few seconds. If you have used semantic search, a recommendation feed, or a RAG chatbot that pulls the right paragraph from a pile of documents, there is a good chance HNSW did the finding.

Modern AI turns text, images and products into vectors: long lists of numbers where similar things end up close together. "Find similar things" then becomes "find the nearest points." That sounds easy until you have ten million points and a user waiting.

This post explains how HNSW solves that problem, using everyday analogies first and the technical details second. By the end you should understand how it works, why it is fast, and what its three tuning knobs (M, efConstruction and efSearch) actually control.

The problem: checking everything is too slow

The simplest way to find the nearest vectors is to compare the query with every single vector and keep the closest ones. This is called brute-force or exact k-nearest-neighbor (kNN) search, and it is always correct.

The cost grows with the size of your data. Take 10 million documents, each embedded as 768 numbers. One query means 10 million distance calculations, or roughly 7.7 billion multiply-and-add operations. That is fine for one offline job, but not for thousands of users searching at once.

Approximate nearest neighbor (ANN) search makes a deal: give up a tiny bit of accuracy in exchange for a huge speedup. Instead of guaranteeing the true top 10, an ANN index returns results that are almost always the true top 10.

We measure that "almost" with recall@k. If the true 10 nearest neighbors are known and the index returns 9 of them, recall@10 is 0.9. A well-tuned HNSW index commonly reaches recall above 0.95 while checking only a small fraction of the data.

There are several families of ANN methods: clustering the space (IVF), compressing vectors (product quantization), trees, and hashing. HNSW belongs to the graph-based family, and it has become the most widely used of them all.

The big idea: it's a small world

HNSW borrows its core trick from social networks: in the right kind of network, any two people are connected by a surprisingly short chain of friends. This is the "six degrees of separation" idea, made famous by Stanley Milgram's letter-forwarding experiments in the 1960s.

Why are chains so short? Most of your friends live near you, work with you or share your interests. Those are short-range links. But a few of your connections are far-flung: a cousin abroad, a college friend in another industry. Those few long-range links act like shortcuts across the whole network.

Mathematicians call a network with this mix a small-world network. Mostly local links keep neighborhoods tight. A handful of long links keep the whole world only a few hops wide.

Now replace "people" with "vectors" and "friends" with "nearby vectors." If we connect our data points into a graph with the same small-world shape, we can travel from any point to any other point in a few hops. That is exactly what a search needs.

Step one: a navigable small world graph

A navigable small world (NSW) graph connects every vector to a handful of its nearest neighbors, and you search it by always stepping to whichever neighbor is closer to your target. This is called greedy search.

Picture asking for directions in an unfamiliar city with no map. At each street corner you ask, "Which way is closer to the railway station?" and walk that way. You never see the whole city, but each step gets you nearer.

In graph terms the search works like this:

Start at some entry point in the graph.
Look at all of the current node's neighbors and measure their distance to the query.
Move to the neighbor that is closest to the query.
Repeat until no neighbor is closer than where you already are. That node is your answer.

Each step only computes a few distances, so the search touches a tiny slice of the data.

Flat NSW graphs have two weaknesses, though:

Too many slow, short hops. If you start far from the target, you crawl there one local step at a time, like crossing a city by walking through every neighborhood.
Getting stuck. Greedy search can stop at a point that is closer than all its neighbors but still not the true nearest one. This is a local minimum, like reaching the top of a small hill and thinking it's the mountain.

HNSW fixes both problems by adding hierarchy.

Step two: add layers, like highways over local roads

HNSW stacks several NSW graphs on top of each other: a sparse top layer for long jumps, and denser layers below for finer steps. The bottom layer contains every vector; each layer above contains only a random fraction of the layer beneath it.

Think about driving to a specific house in a city 500 km away. You don't take local lanes the whole way. You take the expressway to get near the city, switch to city arterial roads to reach the right area, then use small lanes to find the house. Each level of road gets you closer with fewer, larger moves before you switch to finer detail.

HNSW layers work the same way:

Top layer: very few nodes, linked across long distances. Like the expressway network, it gets you to the right region fast.
Middle layers: more nodes, shorter links. Like city roads, they narrow you down to the right neighborhood.
Layer 0 (the bottom): every vector, linked to its close neighbors. Like local lanes, it finds the exact nearest neighbors.

If you know data structures, this is the same idea as a skip list, a sorted linked list with "express lanes" stacked on top. HNSW is essentially a skip list built out of small-world graphs instead of linked lists.

The layering also cures the local-minimum problem. By the time you reach the dense bottom layer, the upper layers have already placed you in the right neighborhood, so there are far fewer misleading hills to get stuck on.

How many layers are there? It grows only logarithmically with data size, so even a billion vectors needs only a handful of layers. That's where the "logarithmic" search speed comes from.

How a search actually runs

A search starts at the top layer, takes greedy hops until it can't get closer, drops down one layer from that same spot, and repeats until it finishes on layer 0.

The search covers most of the distance in one hop on the top layer; each lower layer then needs only a step or two to refine it.

In more detail:

Enter at the top. Every HNSW index has one fixed entry point, a node that lives on the highest layer.
Greedy hops on the upper layers. On each upper layer, the search moves to whichever neighbor is closest to the query, until no neighbor is closer. Here it only tracks the single best node, because the goal is just to find the right region.
Drop down. The best node found becomes the starting point on the next layer down. Because every node on a layer also exists on all layers below it, the search can descend without jumping.
Wider search at the bottom. On layer 0, the search keeps a candidate list of the best nodes found so far instead of just one. It keeps exploring neighbors of the candidates until the list stops improving. The size of this list is efSearch, one of the tuning knobs.
Return the top k. The k closest nodes from the candidate list are the answer.

The candidate list in step 4 is what makes HNSW reliable. Tracking only one "best so far" node is fragile; tracking, say, 100 candidates means the search explores several promising paths in parallel and is much less likely to miss the true nearest neighbors.

How the index is built

HNSW builds its graph one vector at a time: each new vector gets a random top layer, then is wired to its nearest neighbors on every layer from that top down to layer 0.

Choosing a node's layers with a coin flip

When a vector is inserted, HNSW randomly decides how high it reaches. Think of flipping a coin and climbing one floor for every "heads":

Every node lives on layer 0.
A smaller fraction also reaches layer 1.
A smaller fraction still reaches layer 2, and so on.

The real formula uses an exponentially decaying probability tied to M, but the effect is the same as the coin: tall nodes are rare. This randomness is what automatically produces the "few highways, many local roads" structure, without anyone planning which nodes become highways.

Wiring the new node in

The new node is connected using the same search procedure described earlier:

Search from the entry point down to the new node's top layer, to find where it belongs.
On each layer from there down to 0, run a wider search (with a candidate list of size efConstruction) to find the new node's nearest neighbors on that layer.
Link the new node to up to M of them, and link them back to it.
If a neighbor now has too many links, trim its list back down to the limit.

Picking diverse neighbors

HNSW doesn't simply link a node to its M closest points; it prefers neighbors that point in different directions. A candidate is kept only if it is closer to the new node than to any neighbor already chosen.

Why? Imagine a node whose 16 nearest neighbors all sit in one tight cluster to its east.

Linking to all of them gives 16 roads going the same way and none going west. The diversity rule keeps a few roads to other regions, which keeps the graph well connected and prevents search from getting trapped inside clusters.

The three knobs: M, efConstruction and efSearch

HNSW has three main settings: M and efConstruction shape the graph when it is built, and efSearch controls how hard each query searches. Getting them right is most of what "tuning HNSW" means.

Knob	What it controls	Raising it gives	Raising it costs	Typical range	Can change without rebuild?
M	Max links per node per layer (layer 0 usually allows 2×M)	Better recall, especially on hard or high-dimensional data	More memory, slower inserts	16 to 64	No
efConstruction	Candidate list size while inserting	A higher-quality graph	Slower index building	100 to 400	No
efSearch	Candidate list size while querying (must be ≥ k)	Higher recall	Higher query latency	50 to 500	Yes, even per query

M: how many roads leave each intersection

M sets how many neighbors each node keeps. More roads per intersection means more ways to reach any destination, so searches rarely get stuck. But every link costs memory and every insert must maintain more links. For most text embeddings, M of 16 to 32 is a sensible start.

efConstruction: how carefully you build the roads

When a new node is added, efConstruction decides how many candidate neighbors HNSW examines before picking the best M. A larger value means a more careful choice and a better-connected graph, at the cost of slower building. Because it only affects build time, it's often worth setting generously.

efSearch: how hard each query looks

efSearch is the size of the candidate list on layer 0 during a query. A small efSearch is like checking a few streets and settling; a large one is like checking many streets before deciding. Recall goes up and so does latency. This is the knob you adjust day to day, because it needs no rebuild and many databases let you set it per query.

Example configuration (illustrative):

Configuration	M	efSearch	Expected behavior
Fast search	8	32	Lower resource usage, potentially lower recall
Balanced	16	100	Balance of speed and recall
High recall	32	200	More exploration, higher memory and latency trade-offs

A simple tuning recipe

Build with M = 16 to 32 and efConstruction ≈ 200.
Take a few hundred real queries and compute their exact top-k by brute force. This is your ground truth.
Try efSearch values such as 32, 64, 128, 256 and 512. For each, record recall@k and p95 latency.
Pick the smallest efSearch that meets your recall target.
If even a large efSearch can't reach your target, rebuild with a higher M or efConstruction.

The names vary by product: hnsw.ef_search in pgvector, hnsw_ef in Qdrant and efSearch in FAISS all mean the same thing.

Strengths and weaknesses

HNSW is the default choice because it offers an excellent speed-versus-recall trade with almost no training, but it is memory-hungry and has some rough edges.

Why people love it:

Fast and accurate. It consistently sits near the top of public ANN benchmarks for recall at a given speed.
No training step. Unlike clustering-based indexes (IVF), it doesn't need to learn cluster centers from a sample, so it adapts as data arrives.
Incremental inserts. New vectors can be added at any time without rebuilding.
One easy dial at query time. efSearch lets you trade speed for recall on the fly.

Where it hurts:

Memory. HNSW normally keeps all vectors plus the graph links in RAM. Ten million 768-dimension float32 vectors already take about 30 GB before any links are counted.
Deletes are awkward. Removing a node can leave holes in the graph. Most systems mark deleted nodes as hidden ("tombstones") and clean up or rebuild later. Heavy update churn slowly degrades quality.
Slow builds at scale. Every insert runs a search, so building an index over hundreds of millions of vectors takes significant time and CPU.
Filtering is tricky. If a query also says "only hotels in Goa" or "only documents from 2026," many graph nodes become off-limits. Naive filtering can break the graph's paths and hurt recall. Modern databases add filter-aware traversal to handle this.

HNSW in the real world

You rarely implement HNSW yourself; it is the default vector index in most vector databases and libraries, and your main job is choosing settings and checking recall.

Where you'll find it

Vector databases: Qdrant, Weaviate and Milvus.
Databases with vector add-ons: PostgreSQL (pgvector), OpenSearch, Elasticsearch and Redis.
Libraries: FAISS (IndexHNSWFlat) and hnswlib, the reference implementation by the algorithm's authors.

Its role in RAG

In a retrieval-augmented generation (RAG) system, HNSW sits between the embedding model and the LLM:

Offline: documents are split into chunks, each chunk is embedded into a vector, and all vectors are inserted into an HNSW index.
Online: the user's question is embedded, HNSW finds the closest chunk vectors in milliseconds, and those chunks are passed to the LLM as context.

If HNSW misses a relevant chunk, the LLM never sees it, so index recall directly limits answer quality. A common safety net is to retrieve more candidates than needed (say 50) and let a reranker model choose the best 5 to 10.

Saving memory

To fight the memory cost, HNSW is often combined with quantization, which compresses each vector into fewer bits:

Scalar quantization stores each number in 8 bits instead of 32, roughly a 4× saving.
Product quantization compresses vectors much further, at a larger accuracy cost.
Binary quantization keeps one bit per dimension and works well with some embedding models.

A common pattern is to search the compressed vectors for speed, then re-score the top candidates using the original full-precision vectors. For datasets too large for RAM, disk-based graph indexes such as DiskANN are the usual alternative.

The short version

HNSW finds nearest neighbors fast by building a layered small-world graph: sparse "highway" layers on top get you to the right region in a few hops, and the dense bottom layer finds the exact neighbors.

Exact search checks everything; HNSW checks a tiny fraction and still finds 95% or more of the true neighbors when tuned well.
Layers come from random "coin flips" at insert time, and neighbors are chosen to point in diverse directions.
M and efConstruction set graph quality at build time; efSearch sets the speed-versus-recall trade for every query.
Its main costs are memory, awkward deletes and care needed with filters, which quantization and filter-aware engines help address.

Further reading: Malkov and Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, the original HNSW paper.