Chapter 5: HNSW

Time: 40 minutes. Cost: $0. This lab reuses the shared dataset from Chapter 4 and makes no API calls.

The short version

• HNSW, the most widely used vector index, links each vector to some of its nearest neighbors and searches by walking toward the query, one hop at a time.
• A walk that follows a single path gets stuck. Keeping a short list of promising places to explore, a setting called ef, is what makes it work.
• You can change ef on every query without rebuilding, so it is the first setting to tune. The price of HNSW is memory, build time, and awkward deletes and filters.

In 1967, the psychologist Stanley Milgram mailed letters to people in Nebraska and Kansas and asked them to get each letter to a specific stranger in Massachusetts. There was one rule. You could only pass it to someone you knew personally, who would pass it on the same way.

Many letters never arrived. The ones that did took a surprisingly short path, typically about five intermediaries. That result later became a phrase everybody knows, "six degrees of separation."

What does a mail experiment have to do with vector search? Look at what each person in the chain did. Nobody had a map of the whole country. Each one looked only at the people they knew and picked whoever seemed closest to the target. One local hop at a time, the letter got there.

That is exactly how the most widely used vector index works. This chapter builds that kind of walk by hand, shows where it gets stuck, and then measures the real thing.

From letters to links

Why did the letters arrive in so few steps? Your neighbors can only move a letter a few houses. What gets it across the country is one person who has a cousin on the other coast. A few long links like that turn a long chain into a short one. Networks with that property are called small worlds.

Short paths existing is not the same as finding them, though. Each person in the chain saw only their own contacts. It turns out that this kind of local, one-hop-at-a-time routing works only when the long links are spread the right way: some that cross the country, some that cross a city, some that cross a neighborhood. Then every hop can make real progress, whatever the distance left. A network like that is called navigable.

Researchers then applied the idea to vectors. Make each vector a point in a network, link it to some of its near neighbors, and search by walking toward the query one hop at a time. The version everyone uses now is HNSW, short for Hierarchical Navigable Small World. Lucene and Elasticsearch, pgvector, and many purpose-built vector databases offer it. Qdrant's documentation says it is the only dense vector index Qdrant uses.

Where this came from: from Milgram to Malkov

John Guare's 1990 play Six Degrees of Separation made the phrase famous, two decades after Milgram's experiment.

In 1998, Duncan Watts and Steven Strogatz showed in Nature why such short chains exist. Start with a network where everyone knows only their nearby neighbors, and paths across it are long. Rewire just a few links at random to faraway nodes, and the typical path collapses. They called these networks small worlds.

In 2000, Jon Kleinberg asked the question Milgram's letter carriers had answered without thinking: when can someone who sees only their own contacts find a short path? His answer was that greedy, local routing works only when the long links follow the right pattern. Random long links are not enough.

Yury Malkov and colleagues applied this to vectors. Their 2012 conference paper, followed by a 2014 journal paper, built navigable small world (NSW) graphs. In 2016, Malkov and Dmitry Yashunin posted HNSW. It was formally published in 2020.

Adoption followed. Apache Lucene added HNSW in version 9.0 in December 2021. Elasticsearch shipped approximate kNN search built on it in 8.0, as a technical preview, in February 2022. pgvector added an HNSW index in version 0.5.0 in August 2023.

Walk the graph by hand

Picture walking down a hill in thick fog to reach the bottom of the valley. You cannot see the valley. You can only see the ground right around your feet, so at every step you go whichever way is downhill. That rule, always take the step that looks best right now, is called greedy, and it is how the letter carriers worked.

The lab starts with the simplest possible version. Link each of the 18,896 paragraphs to its 8 nearest paragraphs. To search, stand on paragraph 0, which happens to be about the University of Notre Dame. Look at its 8 links. Move to whichever one is closer to the question. Repeat until none of the links gets you any closer.

graph                      found #1   hops  compared
nearest neighbors only           3%    2.6        30

That is a disaster, and it is worth understanding why. The walk compares only 30 paragraphs, which sounds great, until you see that it found the true nearest paragraph for 3% of the questions. It stops after fewer than three hops on average.

The walk is stuck in a dead end, the graph version of a hollow on the hillside: every direction goes up, so you stop, even though the real valley floor is somewhere else. It reached a paragraph whose 8 links all point to paragraphs farther from the question than itself, so the greedy rule says stop. The true answer might be about a different Wikipedia article entirely, and nothing near Notre Dame links that far.

The first fix is cheap. If paragraph A links to B, let B link back to A. Real HNSW links work both ways. Now popular paragraphs collect many links, and there are more exits from every dead end:

Average links per paragraph now: 12.1
graph                      found #1   hops  compared
two-way links                    9%    3.1        65

Better, but 9% is still useless. Committing to a single path is the real problem.

Keep a list, not a single path

Back in the fog. Suppose that instead of committing to one path, you carry a notebook with the few most promising spots you have seen so far. When the path you are on bottoms out in a hollow, you do not give up. You go back to the best spot in the notebook you have not tried yet.

That is the second fix, and it is the one that makes graph search work. Instead of standing on one paragraph, keep a short list of the best paragraphs found so far, and keep exploring from the most promising one you have not expanded yet. Stop when nothing left to explore could improve the list. The size of that list is called ef, and it is the setting you will tune most often.

A dead end no longer ends the search, because the list still holds other paths to try. Here is the same two-way graph with a list:

  ef  recall@10  compared   of all
  10       0.57       200     1.1%
  20       0.71       286     1.5%
  50       0.85       489     2.6%
 100       0.92       787     4.2%

At ef 100, the hand-built graph finds 92% of the true top 10 while scoring 4.2% of the collection. In Chapter 4, IVF needed to scan about 14% to reach 0.93. A plain neighbor graph with two-way links and a candidate list is already competitive, and it fits in a few dozen lines of Python.

What the "H" adds

HNSW adds two things to what you just built.

The first is the hierarchy. Think of driving to a friend's house in another state. You take the interstate to get near the right city, then a main road to get near the right neighborhood, then local streets for the last few blocks. Each kind of road gets you close quickly before the next, slower one takes over.

HNSW's layers are those roads. Every vector lives in the bottom layer, which holds the full graph. A random few also get copied into the layer above, a few of those into the layer above that, and so on. The top layer might hold a handful of vectors. Search starts at the top, walks greedily across a tiny graph to get roughly near the query, then drops down a layer and continues from there. The bottom layer gets the full ef search, starting from a good spot instead of a random one.

The upper layers are the long links from the letter experiment, organized so that a greedy walker always knows which ones to use.

The second addition is how neighbors are chosen. If you were collecting people to ask for directions, a second friend who lives on the same street as the first adds little. A friend across town adds a lot. You linked each paragraph to its 8 nearest. HNSW inserts vectors one at a time, searches the graph to find candidate neighbors, and then keeps a candidate only if it is closer to the new vector than to any neighbor already picked. That rule throws out links that point in the same direction as an existing link and keeps links that point somewhere new. It is what keeps bridges between topics alive, so clusters do not become islands.

The skip list behind the layers

The layers are arranged like a skip list, a data structure William Pugh published in 1990, where each level skips over more of the items below it. The HNSW paper itself points out the resemblance.

Here is a candid footnote. On 18,896 paragraphs, the walk is only a few hops long, so the upper layers matter little. A 2024 study went further. On high-dimensional datasets, they found that a flat navigable graph matched HNSW's speed and recall with less memory, because a few heavily linked "hub" nodes form a highway that does the job the layers were meant to do. On data like this, the candidate list and the links do the heavy lifting, not the layers.

The three settings

Every HNSW implementation exposes the same three settings, under slightly different names:

Setting	What it controls	Costs you	pgvector name and default
M	Links per vector	Memory, build time	m, 16
efConstruction	List size while inserting	Build time	ef_construction, 64
efSearch	List size while searching	Query time	hnsw.ef_search, 40

The defaults differ by library. FAISS uses an efConstruction of 40 and an efSearch of 16, and asks you to choose M yourself. hnswlib defaults to an M of 16 and an ef_construction of 200. Do not assume a "default HNSW" means the same thing in two products.

The lab builds a FAISS HNSW index with M set to 32 and sweeps efSearch:

Brute force: 0.738 ms/query, compares all 18,896
Built HNSW with M=32 in 1.4 s
efSearch  ms/query  compared  recall@10
      16     0.056       532       0.90
      32     0.084       815       0.95
      64     0.139      1330       0.98
     128     0.244      2230       0.99
     256     0.441      3699       1.00

Compare efSearch 32 with your hand-built graph. FAISS reached 0.95 comparing 815 paragraphs. Your version needed 787 comparisons to reach 0.92. I expected the clever neighbor choice to explain that gap, so I tested it. Give the hand-built graph 16 nearest neighbors instead of 8 and it reaches 0.94 at 786 comparisons, nearly matching FAISS. Most of the difference was simply the number of links: with M set to 32, FAISS allows up to 64 links per vector in the bottom layer, against about 12 in your two-way graph. The README shows you how to run that test yourself.

efSearch is the knob I would reach for first, because you can change it per query without rebuilding anything. Need more recall for an important search? Raise it for that query. Under heavy load? Lower it. M is fixed when you build the index:

       M  build s  links per vector  ms/query  recall@10
       8      0.8            81 B      0.068       0.90
      16      0.8           144 B      0.077       0.94
      32      1.4           272 B      0.129       0.98
      64      1.6           528 B      0.167       0.99

More links buy recall at the same efSearch, and cost memory and build time. Here the links are small next to the vectors themselves: 272 bytes against 3,072 bytes for each 768-number vector. Hold on to that comparison. In Chapter 6, when the vectors shrink to under 100 bytes, the links become the biggest thing in memory.

What HNSW costs you

HNSW is the default choice for good reasons. It gives high recall at low latency, and you tune it per query. It is not free, and I would know these costs before choosing it.

• Memory. The whole graph and, usually, the full vectors live in RAM. At a billion vectors, that is the problem Chapter 6 is about.
• Build time. Every insert is a search. The M=32 index took 1.4 seconds here, against 0.1 seconds for k-means in Chapter 4.
• Deletes. Removing a node from a navigable graph can cut paths through it. hnswlib, for example, marks a deleted vector as hidden from results and leaves it in the graph. Databases clean these up in different ways, and the cleanup has a cost.
• Filters. If you only want results from one product category, a search that collects ef candidates and then filters may end up with very few survivors. pgvector's documentation gives the example directly: with the default ef_search of 40 and a filter that matches 10% of rows, about 4 rows come back on average. Chapter 7 deals with that.

Hands-on lab: walk a graph, then tune HNSW

You will build a nearest-neighbor graph, run the greedy walk, make the links two-way, add a candidate list, and then measure FAISS's HNSW with different efSearch and M values.

Full instructions: download the Vector Databases labs ZIP. If you have not built the shared dataset yet, follow labs/vector-databases/dataset/README.md first. Then open labs/vector-databases/05-hnsw and follow its README.

The output is the tables in this chapter. Recall numbers will be close with the Ollama dataset. Timings depend on your machine.

Checkpoint

The greedy walk on the 8-neighbor graph found the true nearest paragraph only 3% of the time. What went wrong?

It got stuck in dead ends. The walk stops as soon as none of the current paragraph's links is closer to the question, and with only 8 one-way links from a starting point in an unrelated topic, that happens within a few hops. The true answer was usually in a part of the graph the walk never reached.

Your store's HNSW search uses pgvector's default ef_search of 40. A shopper filters to the Shoes category, which is 5% of products, and gets 2 results instead of 10. Why?

The search collects its list of 40 candidates first and applies the filter afterward. About 5% of 40 is 2, so when the category has little to do with what the shopper typed, that is roughly what survives. The graph walk does not know about the filter. Raising ef_search helps a little at a cost on every query. Chapter 7 covers the real fixes in PostgreSQL.

Your hand-built graph needed 787 comparisons for a recall of 0.92. FAISS's HNSW reached 0.95 with 815. What explains most of the difference?

The number of links. With M set to 32, FAISS allows up to 64 links per vector in the bottom layer, while the two-way hand-built graph averages about 12. Raising the hand-built graph to 16 nearest neighbors brought it to 0.94 at 786 comparisons. The neighbor-selection rule and the upper layers add less than you might expect at this size.

Check Your Knowledge

Click to start the quiz

1. Your HNSW-backed search slows down badly during a traffic spike, and you cannot rebuild the index today. Which setting can you change right away, and what do you give up?

M, lowered to 8, which gives up some memory savingsefSearch, lowered for each query, which trades some recall for speedefConstruction, raised to 200, which makes the next insert slowerNothing: HNSW settings are all fixed when the index is built

2. You rebuild an index with M raised from 32 to 64 and keep efSearch at 64. Based on the lab, what changes?

Recall rises a little (0.98 to 0.99), the links take about twice the memory, and the build and each query take somewhat longerRecall doubles, because every vector has twice as many linksNothing measurable, because efSearch alone decides recallRecall falls, because more links make the walk wander away from the query

3. A news site removes thousands of expired articles from its HNSW index every day. What should the team expect?

Each delete removes the node and its links at once, with no effect on other searchesHNSW cannot delete anything, so the index must be rebuilt for every removalDeleted articles still appear in results until the next rebuildDeleted vectors are often hidden from results but left in the graph, because removing a node can cut paths through it; that leftover data has to be cleaned up later, at a cost

4. A teammate tries HNSW in FAISS and in pgvector, keeps every setting at its default, and finds pgvector's recall clearly higher on the same data. They conclude pgvector has the better HNSW. What is wrong with that conclusion?

Nothing: different products implement HNSW differently, and the recall shows which one is betterRecall cannot be compared across products, because each one measures it its own wayThe defaults differ: pgvector searches with an efSearch of 40 and FAISS with 16, so the test mostly compares settings; set M, efConstruction, and efSearch the same and measure againFAISS is an approximate library, while pgvector always returns exact results

What's next

Everything so far assumed your vectors fit in memory. At 18,896 paragraphs they take 58 MB. At a billion, the same vectors take over 3 terabytes, before a single graph link. Chapter 6 shrinks vectors to a fraction of their size, measures what that costs in recall, and looks at how DiskANN serves a billion vectors from one machine by putting most of the data on an SSD.