
HNSW: the index behind fast vector search
In short: HNSW (Hierarchical Navigable Small World) is a layered graph index that makes approximate nearest-neighbour vector search fast, at a cost in memory.
HNSW (Hierarchical Navigable Small World) is a graph-based index for approximate nearest-neighbour search, described by Malkov and Yashunin in a paper submitted in March 2016. It organises vectors into layered graphs so a search can jump across the space in the sparse upper layers and refine locally at the bottom. Many vector databases and extensions, pgvector among them, offer it as an index type.
HNSW in plain words
Finding a house: first take the motorway to the right city, then main roads to the neighbourhood, then side streets to the door. You never check every house in the country.
How it works
Each vector is a node linked to its near neighbours. Higher layers contain fewer nodes with long-range links; the bottom layer contains all nodes. A query enters at the top, greedily moves to closer nodes, drops a layer and repeats. The paper says this layering is what lets search cost scale logarithmically with the size of the collection.
Two build settings and one query setting control the trade. In the pgvector README, read in November 2026, m is the maximum number of connections per layer (default 16), ef_construction is the candidate list size while building (default 64) and hnsw.ef_search is the candidate list size while searching (default 40).
Example
In pgvector:
CREATE INDEX ON chunks USING hnsw (embedding vector_cosine_ops)
WITH (m = 16, ef_construction = 64);
SET hnsw.ef_search = 100; -- higher = better recall, slower queries
Where you'll meet it
- pgvector, Elasticsearch, OpenSearch, Qdrant, Weaviate, Milvus and FAISS
- Index configuration screens in managed vector databases
- Benchmarks comparing approximate nearest-neighbour methods
- Capacity planning for RAG systems
What it changes for you
For developers, HNSW defaults are usually fine to start; raise the search setting when recall tests show misses. For platform teams, memory is the constraint to plan for: the pgvector README says builds are significantly faster when the graph fits into maintenance_work_mem. It also notes that vacuuming an HNSW index can take a while and suggests reindexing first, so schedule maintenance for tables with heavy deletes.
HNSW vs IVF
An IVFFlat index divides vectors into lists and searches only the lists closest to the query. The pgvector README says IVFFlat builds faster and uses less memory, while HNSW has the better speed-recall tradeoff.
Common mistake
My view: blaming the language model for missing answers when the vector index's recall is low. Measure recall of the index against exact search on a sample before tuning anything downstream.
Related terms
Vector search · Vector database · Embeddings · Retrieval-augmented generation
From the archive: Why your RAG pipeline returns irrelevant results
Measure the index's recall against exact search before you tune anything downstream.


