HNSW: The Index Powering Vector Search

Part of the free Generative AI course on LogicWiz, module: Finding the Needle: Hybrid Search & Retrieval.

Episode 41: HNSW — The Index That Powers Vector Search

Arjun stacked the express lanes on top of the small-world graph, ran the 500,000-product query again, and watched it come back in 12 milliseconds. "There it is," he said. "That's the one everybody uses."

Two Ideas You Already Know

Last episode you met the two building blocks. Here they are, side by side, one last time:

Skip list — express lanes: leap across most of the data on a sparse top level, then drop down for precision.
NSW graph — "getting warmer": always hop to the neighbour that's closest to what you want.

HNSW — Hierarchical Navigable Small World — is nothing more than those two glued together: a stack of NSW graphs, arranged like a skip list's express lanes. That's the whole idea. The intimidating name just means "small-world graphs, in layers."

Picture It Like Zooming a Map

Imagine finding a friend's house in a country you've never visited. You don't inspect every house — you narrow from coarse to fine:

Zoomed all the way out, you see only major cities. Jump to the right city. (A few big moves.)
Zoom in to streets — navigate neighbourhoods to the right block.
Zoom in to house numbers — a few short steps to the exact door.

HNSW searches in exactly this coarse-to-fine way:

The top layer is the "zoomed-out" map — very few nodes, huge jumps. It drops you into the right region of the data fast.
Each layer down is more detailed: more nodes, shorter links.
Layer 0 at the bottom holds every vector — the "house-numbers" view where you pin the exact match.

So a 5-layer index is really five NSW graphs stacked up, each denser than the one above. Step through a search and watch it descend:

How a Search Travels

Put the map-zoom into steps. Each search combines the vertical move of a skip list with the horizontal move of an NSW graph:

Enter at the sparse top layer and hop ("getting warmer") toward the query until no neighbour is closer.
Drop straight down one layer — same spot, but now with more neighbours to refine against — and keep hopping.
Repeat until you reach Layer 0, then return the closest nodes: your top-k matches.

The clever part is where the effort goes: the sparse top does the big coarse jumps, the dense bottom does the tiny fine-tuning. Most of the dataset is never even looked at.

📌 The payoff: HNSW's search time grows only logarithmically — double the data and you add roughly one more step, not double the work. That's why it's both blazing fast and highly accurate, and it's the default index in Qdrant, the database we'll build on.

"But Vectors Aren't Sorted!"

Good question to poke at. Remember the skip list from Episode 40: it searches a list of numbers laid out in sorted order, smallest to largest. That order is its superpower — since bigger values are always to the right, it can always tell which way to jump to get closer to a target.

But the things HNSW stores are vectors, not single numbers — points in 1024-dimensional space. There's no way to line them up smallest-to-largest, so there's no "left = smaller, right = bigger" to follow. So how does HNSW know which way to go?

The trick is in how the graph gets wired up in the first place. When the index is built, each vector is connected by short links to its most-similar neighbours — the very edges you followed in the "getting warmer" walk last episode. That wiring happens once, upfront, and it captures "what's near what."

Here's the everyday version. Picture a town with no street numbers — but every place has a few roads leading straight to its nearest neighbours. You don't need a master list of addresses to find somewhere: at each spot, you just take the road that heads closer to your destination, and repeat. The roads do all the work.

HNSW is that town. The edges are the roads, drawn at build time, and because a link only ever joins similar vectors, "follow the edge toward higher similarity" is always the road pointing the right way. The connections themselves replace the sorted order a skip list needed — no global ordering required.

See the wiring for yourself — click any product to reveal the short links (its "roads") it was given to its nearest neighbours, and turn on "every road" to see the whole network those links form:

The Costs Nobody Puts on the Brochure

HNSW is fast, but two honest trade-offs come with it:

It's memory-hungry. Every node's links, on every layer, live in RAM. That speed has a storage bill.
Writing is slower than reading. Searching is beautifully quick; adding or changing a vector means re-stitching links across the layers to keep the map correct. Vector databases handle this for you (an ordinary update), but the asymmetry is real: reads are cheap, writes cost more.

Step through it yourself — first watch a search find its answer, then count every single step it takes to add just one new product:

💡 Rule of thumb: HNSW loves read-heavy work — lots of searching, the occasional update. If your data changes every second, budget for that write cost.

You Don't Build HNSW — You Use a Library

Here's the good news after all that theory: nobody hand-writes HNSW in real projects. It's a solved problem, packaged in fast, battle-tested libraries — most famously faiss — and it's the engine built into vector databases like Qdrant. Everything you've learned becomes the settings you pass in: M (links per node), efConstruction (build effort), efSearch (search effort).

Walk through the real thing, line by line:

Now run it for real — this executes actual faiss on a server and returns the nearest neighbours:

Build It Yourself in the Lab

The theory sticks once you drive the real library. In the lab you'll use faiss to:

build a real HNSW index and add vectors to it — the write, tuning M and efConstruction, then
query it for the nearest neighbours — the fast read, tuning efSearch.

Same knobs you just met, on a genuine index — no wheels reinvented.

What Nova Learns Next

Nova's dense search is now fast at scale. But HNSW only speaks dense — packed, high-dimensional vectors. Her keyword side needs a completely different structure. In Episode 42 we build the other half: the inverted index that makes sparse, lexical search near-instant.