--- title: "HNSW Explained: How Vector Search Finds Nearest Neighbors Fast" description: "HNSW is a layered graph index for vector search: sparse top layers for long jumps, a dense bottom layer for precision. How it works, M and ef, with benchmarks." date: 2026-10-31 last_modified_at: 2026-10-31 keywords: [HNSW, HNSW algorithm, hierarchical navigable small world, approximate nearest neighbor search, vector search, vector database index, HNSW parameters M ef_construction ef_search, hnswlib] categories: search algorithms vector-search math: true related: ["/blog_posts/elasticsearchNotes.html", "/blog_posts/bloom_filters.html", "/blog_posts/monte-carlo-simulation-explained.html"] faq: - q: "Is HNSW exact or approximate?" a: "Approximate. HNSW returns the true nearest neighbors most of the time, but it can miss some, because the search only explores part of the graph. How often it finds them is measured as recall. With sensible settings, recall@10 of 0.95 to 0.99 is normal. Raising ef at query time raises recall at the cost of speed. If you need guaranteed exact results, use a brute-force (flat) index." - q: "What is the difference between HNSW and IVF?" a: "HNSW is a graph: each vector links to nearby vectors, and a search walks those links. IVF (inverted file) clusters vectors with k-means and, at query time, scans only the few clusters nearest to the query. HNSW is usually faster at high recall and needs no training step, but uses more memory for its links. IVF builds faster, uses less memory and combines well with compression such as product quantization." - q: "Does Elasticsearch use HNSW?" a: "Yes. Elasticsearch's approximate kNN search on dense_vector fields uses Lucene's HNSW graphs, with m defaulting to 16 and ef_construction to 100. Recent versions compress the vectors by default (int8_hnsw or bbq_hnsw, depending on version and dimensions). From 9.4 the default can be bbq_disk, a cluster-based (IVF-style) index, but HNSW types remain available. At query time, num_candidates plays the role of ef." - q: "How much memory does an HNSW index need?" a: "Roughly the raw vectors plus the graph links. The vectors cost dimensions times 4 bytes each as float32; the links cost about M times 8 to 10 bytes per vector. For 1 million 768-dimension vectors with M = 16, that is about 3.1 GB of vectors plus about 0.14 GB of links. The vectors dominate, which is why vector databases compress them with int8 or binary quantization." - q: "Can you delete vectors from an HNSW index?" a: "Not cleanly. Removing a node would break the paths that run through it, so most libraries mark it as deleted instead: it stays in the graph for routing but is filtered out of results. hnswlib can later reuse the slot for a new vector. Lucene-based engines drop deleted vectors when segments merge and rebuild the graph. Heavy deletes slowly hurt recall, so indexes are periodically rebuilt." --- # HNSW Explained: How Vector Search Finds Nearest Neighbors Fast > **In short:** HNSW (Hierarchical Navigable Small World) is a graph index for finding the vectors closest to a query without comparing it to every vector. It stacks graph layers: sparse upper layers make long jumps, the bottom layer holds every vector. On 1 million SIFT vectors, it found 97.5% of the true top 10 in 0.23 ms, versus 9 ms for brute force. Every section starts with a picture or a small simulation; the full explanation sits under **Read more** if you want it. To play with a real HNSW graph straight away, jump to the [interactive demo](#demo). ## What problem does HNSW solve?

Figure: brute force compares a query with all 1,000,000 vectors and takes 9.00 ms. HNSW at ef = 80 compares it with 1,526 vectors (0.15%), finds 97.5% of the true top 10, and takes 0.23 ms, 39 times faster.

Same question, a sliver of the work. Measured on 1 million SIFT vectors, one CPU thread.

Read more: nearest neighbor search and why brute force is slow

HNSW solves **nearest neighbor search**: given a query vector, find the stored vectors closest to it. Modern search and AI systems turn text, images and audio into **embeddings**, lists of a few hundred numbers where similar meaning means nearby points. "Find documents like this one" becomes "find the closest points to this one". The obvious method, **brute force**, measures the distance from the query to every stored vector. That is exact but slow: with 1 million vectors of 768 dimensions, one query is about 768 million multiply-adds. It grows linearly, so 100 million vectors is 100 times slower. That's fine for thousands of vectors and too slow for millions behind a search box.

## What is approximate nearest neighbor (ANN) search?

Figure: of the true 10 nearest neighbors, the index returned 9 and missed 1, so recall@10 = 0.9.

ANN trades a few misses for speed. Recall@10 counts how many of the true top 10 came back.

Read more: recall, and why "approximate" is usually fine

**Approximate nearest neighbor (ANN)** search gives up a guarantee to gain speed: it returns the true nearest neighbors *most* of the time, after looking at only a small fraction of the data. Its quality is measured by **recall@k**: of the true k nearest neighbors, the share the index actually returned. Recall@10 = 0.95 means 9.5 of the true top 10, on average. For search and RAG (retrieval-augmented generation, where an LLM answers using retrieved documents), that trade is usually right. Embeddings are already a fuzzy representation of meaning, so the 11th-best match is rarely worse in practice than the 10th. HNSW is the most widely used ANN index today.

## How does HNSW work? Layers, like roads

Figure: three stacked graph layers. Layer 2 (motorways) has 2 of 25 points, layer 1 (main roads) 7, layer 0 (local streets) all 25. A search starts at the entry point on layer 2, hops greedily toward the query, drops to layer 1, hops again, drops to layer 0 and finishes at the nearest point.

Long jumps on top, precise steps at the bottom. Every point lives on layer 0; a random few also live higher up. The search drops one layer at a time, starting each layer close to the answer. The graph and path are computed with HNSW's own rules.

Read more: how the heuristic works

HNSW doesn't simply link a new vector to its M closest candidates. Its **neighbor-selection heuristic** (Algorithm 4 in the paper) walks the candidates from nearest to farthest and keeps one only if it is closer to the new vector than to every neighbor already kept. A candidate sitting "behind" an existing neighbor is skipped, since it's reachable through that neighbor anyway. The effect is links that point in **different directions** rather than all into one dense cluster. That matters most for clustered data: without it, two clusters can end up connected by no edges at all, and a search that starts in the wrong one never leaves. The paper reports the effect is largest for low-dimensional data, for mid-dimensional data at high recall, and for highly clustered data; for uniform, very high-dimensional data it makes little difference.

## How do M, efConstruction and efSearch affect HNSW? {: #parameters}

Figure, three knobs: M (links per node, set at build) raises recall but costs memory and build and query time; efConstruction (beam width while building) raises graph quality and recall and costs build time only; efSearch (beam width per query) raises recall and costs query time, and can be changed without rebuilding.

Set M and efConstruction once, tune efSearch. efSearch is the only knob you can turn without rebuilding the index.

Read more: typical values and each library's defaults

| Parameter | What it is | Raise it for | Cost of raising it | Typical values | |---|---|---|---|---| | **M** | Links per node (2M on layer 0) | Higher recall, especially at high dimensions | More memory, slower build and queries | 5-48 (the paper's range); 16 is the common default | | **efConstruction** | Beam width while inserting | A better graph, so higher recall later | Slower build only | 40-500 | | **efSearch** (ef) | Beam width per query, must be ≥ k | Higher recall | Slower queries | 10-500, tuned to a recall target | The practical recipe: pick M and efConstruction once (the defaults are usually fine), then tune **efSearch** until recall hits your target, since it is the only one you can change without rebuilding. The hnswlib authors give 2-100 as a reasonable range for M, with higher M better for high-dimensional data and high recall ([hnswlib ALGO_PARAMS](https://github.com/nmslib/hnswlib/blob/master/ALGO_PARAMS.md)). Defaults differ between libraries, so the same "HNSW" can behave differently out of the box. As of October 2026: | Library | M | efConstruction | efSearch | Source | |---|---:|---:|---:|---| | hnswlib | 16 | 200 | set with `set_ef()` | [README](https://github.com/nmslib/hnswlib) | | FAISS `IndexHNSWFlat` | you pass it | 40 | 16 | [HNSW.h](https://github.com/facebookresearch/faiss/blob/main/faiss/impl/HNSW.h) | | pgvector 0.8 | 16 | 64 | 40 (`hnsw.ef_search`) | [README](https://github.com/pgvector/pgvector) | | Elasticsearch | 16 (`m`) | 100 | `num_candidates` per query | [dense_vector docs](https://www.elastic.co/docs/reference/elasticsearch/mapping-reference/dense-vector) | FAISS's efSearch of 16 and pgvector's 40 favor speed. If your recall is lower than expected, ef is the first thing to check.

## How fast is HNSW? A benchmark on 1 million vectors {: #benchmark}

Figure: recall@10 against milliseconds per query on SIFT1M for efSearch 10, 20, 40, 80, 160 and 320: recall 0.710, 0.839, 0.927, 0.975, 0.993, 0.998 at 0.048, 0.078, 0.123, 0.230, 0.400 and 0.729 ms per query. Brute force takes 9.00 ms.

Pick an efSearch and see what it buys. Real measurements: hnswlib, M = 16, efConstruction = 200, 1,000,000 SIFT vectors, one CPU thread.

Read more: setup, full results table and what they show

I ran hnswlib on [SIFT1M](http://corpus-texmex.irisa.fr/), a standard ANN benchmark: 1,000,000 image descriptor vectors of 128 dimensions, 10,000 test queries, and the true nearest neighbors precomputed (I used the [ann-benchmarks](https://github.com/erikbern/ann-benchmarks) copy). The index used M = 16 and efConstruction = 200. Queries ran on **one CPU thread**, on a 4-core cloud VM, in Python 3.13 with hnswlib 0.8.0 and FAISS 1.15.1. Brute force used FAISS's exact `IndexFlatL2`, also on one thread. | Method | efSearch | Recall@10 | Time per query | Faster than brute force | Vectors compared per query | |---|---:|---:|---:|---:|---:| | Brute force | | 0.999\* | 9.00 ms | 1× | 1,000,000 | | HNSW | 10 | 0.710 | 0.048 ms | 188× | 393 | | HNSW | 20 | 0.839 | 0.078 ms | 115× | 572 | | HNSW | 40 | 0.927 | 0.123 ms | 73× | 904 | | HNSW | 80 | 0.975 | 0.230 ms | 39× | 1,526 | | HNSW | 160 | 0.993 | 0.400 ms | 23× | 2,655 | | HNSW | 320 | 0.998 | 0.729 ms | 12× | 4,640 | Brute force was timed on the first 1,000 queries, HNSW on all 10,000. Recall and time are from hnswlib. hnswlib doesn't report distance computations, so the last column comes from a FAISS HNSW index built with the same M and efConstruction; its recall matched hnswlib's to within 0.01 at every ef. \*Brute force scores 0.999 rather than 1.000 because a few SIFT queries have ties: different vectors at exactly the same distance. What the numbers show: - **The search touches very little of the data.** At ef = 80, HNSW compared each query with about 1,500 vectors instead of 1,000,000 (0.15%), found 97.5% of the true neighbors, and was 39 times faster. The time gain is smaller than the work saved (about 650×) because hopping around a graph jumps all over memory, while brute force streams through it with fast SIMD instructions. - **Recall is a dial, not a constant.** Each doubling of ef cost 1.6 to 1.9 times the time and cut the missed neighbors by 1.8 to 4 times, from 29% at ef = 10 to 0.2% at ef = 320. Most systems settle somewhere in the 0.95-0.99 range. - **Building is the expensive part.** The 1-million-vector index took 120 seconds to build with hnswlib on 4 threads (127 seconds with FAISS); brute force needs no build at all. The saved index was 661 MB: 512 MB of raw vectors plus about 149 MB of graph links and IDs. Your numbers will differ with hardware, data and dimensions; the shape of the curve is what carries over. On harder data, such as uniform random vectors with no structure, recall at the same ef is much lower, as the code below shows.

## How do you use HNSW in Python? Build an index with [hnswlib](https://github.com/nmslib/hnswlib) (by the paper's first author), then compare it with brute force at three ef values: ```python import hnswlib import numpy as np rng = np.random.default_rng(42) dim, n = 64, 20_000 vectors = rng.random((n, dim), dtype=np.float32) queries = rng.random((100, dim), dtype=np.float32) # Build the index: M = links per node, ef_construction = build-time beam width index = hnswlib.Index(space="l2", dim=dim) index.init_index(max_elements=n, M=16, ef_construction=200, random_seed=42) index.add_items(vectors, np.arange(n), num_threads=1) # 1 thread: same graph every run # Exact answer for comparison: brute force over every vector dists = ((queries[:, None, :] - vectors[None, :, :]) ** 2).sum(axis=2) exact = np.argsort(dists, axis=1)[:, :10] for ef in [10, 50, 200]: index.set_ef(ef) # query-time beam width labels, _ = index.knn_query(queries, k=10) recall = np.mean([len(set(labels[i]) & set(exact[i])) / 10 for i in range(len(queries))]) print(f"ef={ef:3d} recall@10 = {recall:.2f}") ``` Output (Python 3.13, hnswlib 0.8.0, NumPy 2.5): ```text ef= 10 recall@10 = 0.31 ef= 50 recall@10 = 0.71 ef=200 recall@10 = 0.96 ```

Read more: why recall is lower here than on SIFT

Uniform random vectors are close to the worst case for any ANN index: every point is about equally far from every other, so there is no structure to exploit. That's why recall at ef = 10 is only 0.31 here, against 0.71 on the real SIFT data, and why ef = 200 is needed to pass 0.95. Real embeddings are much more forgiving. Use `space="cosine"` or `space="ip"` for cosine similarity or inner product, which is what most text embedding models expect.

## What are the downsides of HNSW? {: #downsides}

Figure, memory calculator: for 1 million 768-dimension float32 vectors with M = 16, the raw vectors take about 3.07 GB and the graph links and IDs about 0.14 GB, about 3.22 GB in RAM in total.

Memory is mostly the vectors, not the graph. Change the sizes to estimate your own index (hnswlib's memory layout). That's why engines compress vectors with int8 or 1-bit quantization.

Read more: memory, build time, deletes, filters and exactness

- **Memory.** The vectors and graph normally live in RAM. Each vector costs its raw size (dimensions × 4 bytes as float32) plus roughly M × 8-10 bytes of links ([hnswlib](https://github.com/nmslib/hnswlib/blob/master/ALGO_PARAMS.md)). For 1 million 768-dimension vectors with M = 16: about 3.1 GB of vectors and 0.14 GB of links. This is why engines pair HNSW with **quantization** (storing int8 or 1-bit versions of the vectors). - **Slow builds.** Every insert is a search plus link updates. Building is far slower than a k-means-based IVF index. - **Deletes are awkward.** Removing a node would break the paths through it, so libraries mark it deleted and filter it out of results; recall drifts down until a rebuild. - **Filtered search is hard.** "Nearest vectors where `category = shoes`" can break the graph walk if most nodes fail the filter. Engines handle this in different ways (filtering during the walk, or falling back to brute force for very selective filters), and it's worth testing on your own data. - **No exactness guarantee.** Some true neighbors are missed. For legal, deduplication or audit use cases needing exact answers, use brute force or re-check candidates.

## HNSW vs IVF vs brute force: which should you use?

Figure, three indexes: brute force computes the distance to every vector (best under about 100k vectors or for exact answers; time grows with every vector). IVF scans only the clusters nearest the query (best for huge collections on little memory, with product quantization; needs training and gives lower recall at the same speed). HNSW walks a neighbor graph (best for fast, high-recall search on changing data; costs memory and build time).

HNSW is the sensible default for most vector search, and it's what pgvector, Elasticsearch, OpenSearch, Qdrant, Weaviate, Milvus, Redis and FAISS offer.

Read more: comparison table and where HNSW is used

| Index | How it works | Best for | Weak spot | |---|---|---|---| | Brute force (flat) | Compare the query with every vector | Under ~100k vectors, or when results must be exact | Query time grows linearly | | **HNSW** | Walk a layered neighbor graph | Low latency at high recall; data that changes over time | Memory; build time | | IVF (+ PQ) | Scan only the k-means clusters nearest the query; PQ compresses vectors | Very large collections on limited memory | Needs training; lower recall at the same speed | | DiskANN-style | Graph index designed to live on SSD | Billions of vectors without that much RAM | More complex to run | If you're starting out with a vector database, HNSW is the sensible default, and it's what most of them use under the hood: [pgvector](https://github.com/pgvector/pgvector), [Elasticsearch and OpenSearch](https://www.elastic.co/docs/reference/elasticsearch/mapping-reference/dense-vector) (via Lucene), Qdrant, Weaviate, Milvus, Redis and [FAISS](https://github.com/facebookresearch/faiss) all offer it. In Elasticsearch, the HNSW graphs are built per Lucene segment, so the shard and segment ideas in my [Elasticsearch notes](/blog_posts/elasticsearchNotes.html) apply to vector search too. HNSW sits in the same family as my post on [Bloom filters](/blog_posts/bloom_filters.html): data structures that accept a small, measurable chance of being wrong in exchange for large savings in time or space. The difference is the error. A Bloom filter can say "yes" when the answer is "no"; HNSW can miss a true neighbor, and you trade that against speed with ef.

## Sources - Yu. A. Malkov and D. A. Yashunin, [*Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs*](https://arxiv.org/abs/1603.09320), arXiv:1603.09320 (2016); IEEE Transactions on Pattern Analysis and Machine Intelligence 42(4), 824-836 (2020). - [hnswlib](https://github.com/nmslib/hnswlib) and its [parameter guide](https://github.com/nmslib/hnswlib/blob/master/ALGO_PARAMS.md). - [FAISS](https://github.com/facebookresearch/faiss), [`HNSW.h`](https://github.com/facebookresearch/faiss/blob/main/faiss/impl/HNSW.h) defaults. - [pgvector README](https://github.com/pgvector/pgvector), HNSW section (version 0.8.7). - [Elasticsearch `dense_vector` reference](https://www.elastic.co/docs/reference/elasticsearch/mapping-reference/dense-vector), `index_options`. - [SIFT1M dataset](http://corpus-texmex.irisa.fr/) (Jégou, Douze and Schmid) and [ann-benchmarks](https://github.com/erikbern/ann-benchmarks). - My [interactive HNSW demo](/blog_posts/experiments/hnsw-simul/), which implements the paper's insertion, neighbor-selection and search algorithms on 2-D points.