# What is HNSW, and how does an HNSW index search vectors?

Hierarchical Navigable Small World: a vector index that links each vector to its near neighbours in layers of graphs, so a search hops from coarse to fine and checks only a small share of the vectors.

- Page: https://tecyfy.com/concepts/hnsw
- Subject: Data engineering in the AI era (https://tecyfy.com/concepts)
- Level: advanced
- Also called: Hierarchical Navigable Small World, HNSW index

HNSW, short for Hierarchical Navigable Small World, is a vector index: pgvector and the Faiss library both offer it. It finds the stored vectors nearest to a query without comparing the query with every one of them.

## The problem it solves

A [vector database](https://tecyfy.com/concepts/vector-database) answers one question over and over: which of my stored [embeddings](https://tecyfy.com/concepts/embedding) are closest to this one? Comparing the query with every stored vector always gives the right answer. pgvector does exactly that until you add an index. But with millions of vectors of a thousand or more numbers each, every query does millions of long sums.

HNSW trades a little accuracy for a lot of speed. It is one way to do [approximate nearest neighbour search](https://tecyfy.com/concepts/approximate-nearest-neighbor-search).

## How the graph is built

Every vector becomes a point in a graph, linked to a few of its nearest neighbours. Then a few points are also put in a second, smaller graph above, and fewer still in a third. In the original paper by Malkov and Yashunin, each point's top layer is drawn at random, with the odds falling sharply for each layer up. So the bottom layer holds every point, and the top holds a handful.

The upper layers have few points, so their links are long jumps across the map. The bottom layer has every point, so its links are short steps between close neighbours. The paper likens it to a skip list, the same idea used to search sorted lists quickly.

## How a search runs

1. Start at the entry point on the top layer.
2. Step to whichever linked point is closer to the query. Repeat until no neighbour is closer.
3. Drop to the layer below, starting from that point, and do the same.
4. On the bottom layer, keep a short list of the best candidates found so far, `ef` of them, and keep widening from the closest until no closer point turns up. Return the best.

Try it below. With a list of 1, the search sometimes stops at a point that only looks closest from where it stands. A longer list costs more distance sums but finds the true nearest more often.

## The settings that matter

| Setting | In pgvector | What it trades |
|---|---|---|
| Links per point (`m`) | 16 by default | More links: better recall, more memory, slower builds |
| Candidates while building (`ef_construction`) | 64 by default | Higher: a better graph, slower builds |
| Candidates while searching (`ef_search`) | 40 by default | Higher: better recall, slower queries |

`ef_search` can be changed per query, so you can tune recall against speed without rebuilding. Measure recall on your own queries against an exact search, then set it.

## What it costs

pgvector notes that HNSW gives a better balance of speed and recall than its other index, IVFFlat, but takes longer to build and uses more memory. The links are stored on top of the vectors: the Faiss documentation gives each vector's size as the full vector plus its links. HNSW also needs no training step, so you can create the index on an empty table and add rows as they come.

## A trap with filters

In pgvector, a `WHERE` filter is applied after the index has found its candidates. With the default `ef_search` of 40 and a filter that matches 10% of rows, only about 4 rows come back on average. Raise `ef_search`, or turn on iterative index scans (pgvector 0.8.0 and later), when you filter.

## Why it matters

Retrieval quality in [RAG](https://tecyfy.com/concepts/rag) depends on finding the right passages. An HNSW index set too lean quietly skips some of them, and the model answers from the next-best text. Check recall when you tune it.

(An interactive demo goes with this on the page: https://tecyfy.com/concepts/hnsw)

## Related

- [Approximate Nearest Neighbor Search](https://tecyfy.com/concepts/approximate-nearest-neighbor-search): Finding the stored vectors closest to a query without comparing it with every one, by using an index that may now and then miss the true closest in exchange for far faster searches.
- [Vector Database](https://tecyfy.com/concepts/vector-database): A database built to store embeddings and quickly find the ones closest to a query, which is how AI apps search by meaning.
- [pgvector](https://tecyfy.com/concepts#pgvector): A PostgreSQL extension that adds vector similarity search.
- [FAISS](https://tecyfy.com/concepts#faiss): Facebook AI Similarity Search library for fast vector similarity.
- [Cosine Similarity](https://tecyfy.com/concepts/cosine-similarity): A measure of how closely 2 vectors point the same way, from 1 for the same direction to −1 for opposite; with embeddings, a higher score means closer in meaning.
- [Embedding](https://tecyfy.com/concepts/embedding): A list of numbers that stands for the meaning of a piece of text, an image or other data. Things with similar meaning get similar numbers, so a computer can find them.

## Sources

- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://arxiv.org/abs/1603.09320)
- [pgvector](https://github.com/pgvector/pgvector)
- [Faiss indexes](https://github.com/facebookresearch/faiss/wiki/Faiss-indexes)