HNSW

Overview

HNSW stands for Hierarchical Navigable Small World. It is a graph-based index for approximate nearest neighbour (ANN) search. You give it a large set of vectors, it builds a layered network of links between them, and then it answers "which stored vectors are closest to this query?" in a tiny fraction of the time a full scan would need. It is the default index in most vector databases and vector search libraries, and it is often the first thing to try when you need fast, accurate similarity search on data that fits in memory.

The core idea is simple. Think of a road map with highways on top and local streets below. To drive across a country you take highways first, then main roads, then side streets. HNSW does the same with vectors. The top layers hold few points and long links, so a search can jump far in a few hops. The bottom layer holds every point with short links, so the search can finish with fine local steps. The result is search time that grows roughly with the logarithm of the data size, with recall that you can tune by changing a single search parameter.

What it is

HNSW is an index structure, not a model and not a database. It stores a set of points in a metric space (usually using Euclidean distance, inner product or cosine similarity) and keeps, for each point, a short list of neighbours. A query walks this graph greedily toward the query point.

The three ingredients

HNSW combines three older ideas:

• Proximity graphs. Each point links to a few points that are near it. Walking from neighbour to neighbour moves you closer to a target.
• Small world networks. Networks where most nodes can be reached from any other in a few hops, because a mix of short and long links exists.
• Skip lists. A layered list where upper layers skip over many elements so you can find a position quickly. HNSW applies the same layering to a graph.

What you get

• Query latency that is usually in the sub-millisecond to few-millisecond range for millions of vectors on one machine.
• High recall, often above 95 percent with sensible settings, and tunable up toward 99 percent at some extra cost.
• Incremental insertion, so you can add vectors without rebuilding from scratch.
• Support for several distance functions, chosen at build time.

What you pay

• Memory. The full vectors and the links usually live in RAM for best speed.
• Build time. Inserting each point requires a search, so building a big graph takes a while.
• Weak support for deletes and for filtered search, which need extra care.

Where it came from

The graph search story starts with navigable small world graphs, often called NSW. Those were flat graphs, built by inserting points one at a time and linking each to its nearest existing points. Early links tended to become long links, which acted like shortcuts. This worked well in low dimensions but suffered when the data was clustered or very large, because a greedy walk could take many hops.

The HNSW paper by Malkov and Yashunin appeared as a preprint in 2016 and was later published in a major pattern analysis journal. Its main contribution was to separate links by scale into layers, in the way a skip list does. Each point is randomly assigned a maximum layer. Higher layers are sparse. A query starts at the top, descends layer by layer, and finishes with a wider search at the bottom.

Since then HNSW has become the workhorse of vector search. An open source library called hnswlib offers a compact reference implementation. Many other systems ship their own versions, including FAISS, pgvector, Qdrant, Weaviate, Milvus, Vespa, Elasticsearch and Chroma. The rise of embedding based retrieval and retrieval augmented generation, covered in naive RAG, made it popular far beyond the research community.

Later work tried to fix its weak points. Graph indexes that live on disk, such as DiskANN, reduce memory use. Compressed indexes such as IVF-PQ trade accuracy for size. Library work like ScaNN focuses on quantization quality. HNSW remains the baseline against which these are compared.

How it works

Step 1: layers and random levels

When a new point is inserted, HNSW draws a random level for it. The draw is exponentially decaying. Most points get level 0 only. A smaller fraction also appear in level 1. An even smaller fraction appear in level 2, and so on.

The standard rule is:

level = floor( -ln(U) * mL ),   U uniform in (0, 1],   mL = 1 / ln(M)

With this choice, the chance that a point reaches level l or higher is M raised to the power of minus l. For M = 16, about 1 in 16 points reaches level 1, about 1 in 256 reaches level 2, and about 1 in 4096 reaches level 3.

Analogy: think of a company where everyone works on the ground floor, a few people are team leads, fewer are directors, and one person is the chief. To get a message to someone you ask the chief, who points to a director, who points to a lead, who points to the right person.

Step 2: searching one layer greedily

On a single layer, a search keeps a short list of the best candidates found so far. It repeatedly takes the closest unvisited candidate, looks at that candidate's neighbours, computes their distances to the query, and updates the list. It stops when no candidate is closer than the worst item in the result list.

The size of that list is the key tuning knob. It is called ef (for "exploration factor"). A larger ef explores more of the graph and finds better neighbours, but costs more time.

Step 3: descending from top to bottom

A query starts at a fixed entry point on the top layer. On each upper layer it runs the greedy search with ef = 1, which just means "keep moving to the closest neighbour until you cannot improve". The best point found becomes the entry point for the layer below. On layer 0 it runs the same search with the real efSearch value and returns the top k results.

Analogy: you fly to the right country, take a train to the right city, then walk the last few streets, checking house numbers carefully only at the end.

Step 4: inserting a point

Insertion reuses the search. For a new point with level L:

1. Start at the global entry point on the top layer.
2. For layers above L, descend greedily with ef = 1.
3. For each layer from L down to 0, search with efConstruction candidates, choose up to M neighbours from the candidates, and add links in both directions.
4. If a neighbour now has too many links, prune its list back to the allowed size.
5. If the new point's level is above the current top layer, it becomes the new entry point.

Layer 0 usually allows twice as many links as the upper layers (often written as M0 = 2 * M), since it is the layer where fine detail matters.

Step 5: the neighbour selection heuristic

Choosing the M nearest candidates sounds natural, but it creates problems in clustered data. All the links of a point may point into the same cluster, and the graph can lose its links between clusters.

HNSW uses a heuristic instead. It takes candidates in order of distance and keeps a candidate only if it is closer to the new point than to any neighbour already chosen. This favours neighbours that lie in different directions. The graph keeps links that bridge clusters, which keeps greedy search from getting stuck.

Analogy: when you choose five friends to call for advice, you do better with five friends who live in different cities than with five friends who live on your street.

Step 6: deletion and updates

Plain HNSW has no clean delete. Most implementations mark an element as deleted (a tombstone). It stays in the graph so that search paths do not break, but it is skipped when results are collected. Heavy deletion leaves the graph bloated, so systems rebuild or compact the index from time to time. Updating a vector is usually implemented as a replacement of the old entry.

Complexity in plain words

• Search cost grows roughly with the logarithm of the number of points, times a factor that depends on M and efSearch.
• Build cost is roughly the number of points times the cost of one insertion search.
• Memory is the raw vectors plus about M0 times 4 bytes of links per point on layer 0, plus a small amount for upper layers.

Key concepts and terms

A worked example

Numeric walk-through: memory

Suppose you index one million embeddings with 768 dimensions stored as 32-bit floats, and you use M = 16 with M0 = 32.

• Vector storage: 1,000,000 * 768 * 4 bytes = 3,072,000,000 bytes, about 3.07 GB.
• Layer 0 links: 1,000,000 * 32 * 4 bytes = 128,000,000 bytes, about 128 MB.
• Upper layers: roughly 1 in 16 points have extra links of at most 16 entries, so about 4 MB more.

The index is about 3.2 GB in total, and almost all of it is the raw vectors. This is why the vectors are the cost driver and why compression (see IVF-PQ) matters at scale.

Numeric walk-through: how many layers

With M = 16, the expected number of layers for one million points is about log base 16 of 1,000,000, which is around 5. So a query descends about 5 layers, doing a tiny greedy walk on each of the upper ones, then a wider search at the bottom.

Code: building and querying with hnswlib

import numpy as np
import hnswlib

dim = 64
n = 100_000
rng = np.random.default_rng(0)
data = rng.normal(size=(n, dim)).astype("float32")
ids = np.arange(n)

# Build the index
index = hnswlib.Index(space="l2", dim=dim)
index.init_index(max_elements=n, ef_construction=200, M=16)
index.add_items(data, ids)

# Query it
index.set_ef(64)  # efSearch
queries = rng.normal(size=(5, dim)).astype("float32")
labels, distances = index.knn_query(queries, k=10)
print(labels.shape, distances.shape)  # (5, 10) (5, 10)

Code: measuring recall against exact search

Never trust an ANN setting until you have compared it with exact results on a sample.

from sklearn.neighbors import NearestNeighbors

nn = NearestNeighbors(n_neighbors=10, algorithm="brute").fit(data)
_, exact = nn.kneighbors(queries)

hits = [len(set(a) & set(b)) for a, b in zip(labels, exact)]
recall = sum(hits) / (10 * len(queries))
print("recall@10:", round(recall, 3))

Code: the same idea in SQL with pgvector

CREATE TABLE items (id bigserial PRIMARY KEY, embedding vector(64));

CREATE INDEX items_embedding_hnsw
  ON items USING hnsw (embedding vector_l2_ops)
  WITH (m = 16, ef_construction = 200);

SET hnsw.ef_search = 64;

SELECT id
FROM items
ORDER BY embedding <-> '[0.1, 0.2, 0.3]'::vector  -- shortened example vector
LIMIT 10;

The names above follow the pgvector style. Check the documentation of your version for exact option names.

Tuning loop

1. Fix M and efConstruction at reasonable values (for example 16 and 200).
2. Build the index once.
3. Sweep efSearch (for example 16, 32, 64, 128, 256).
4. For each value, record recall@k and latency.
5. Pick the smallest efSearch that meets your recall target.
6. If you cannot reach the target, raise M or efConstruction and rebuild.

Strengths and limitations

Strengths

• Speed at high recall. For in-memory data it is among the best performing indexes in public ANN comparisons.
• Simple tuning. One query-time knob (efSearch) trades recall for speed without a rebuild.
• Incremental builds. You can add points as they arrive, with no separate training step as IVF-style indexes need.
• Metric flexibility. Works with L2, inner product and cosine.
• Wide support. It is available in nearly every vector store, so skills transfer.
• Good behaviour on varied data. No need to know the data distribution in advance.

Limitations

• Memory hungry. Full vectors plus links stay in RAM. At hundreds of millions of vectors this becomes costly.
• Slow bulk builds. Each insert is a search. Parallel builds help but do not remove the cost.
• Deletes are awkward. Tombstones accumulate, and recall can drift if many deletions are made.
• Filtered search is hard. If a metadata filter removes most points, the greedy walk may find too few valid results or become slow. Systems handle this with extra tricks such as filter-aware traversal or fallback to scan.
• Approximate by design. There is no guarantee that the exact nearest neighbour is returned.
• Hard to shard perfectly. Splitting a graph across machines means each shard gets queried, which multiplies the cost.
• Dimension effects. Very high dimensional data with weak structure shrinks the gap between near and far points, which hurts every ANN method.

How it compares with alternatives

A useful rule of thumb: pick HNSW when everything fits in memory and you want a strong default. Move to compressed or disk based indexes when memory cost, not latency, becomes the main problem.

Combining methods is common. A system may use IVF to prune the search space and HNSW to search the small coarse centroid set, or use HNSW to find candidates and a cross-encoder reranker to reorder them. Pairing with keyword scoring, as in hybrid search and BM25, is also standard.

Role in tabular foundation models

Tabular foundation models learn from raw tables: rows and columns, mixed numeric and categorical types, missing cells, and sometimes columns with no meaningful names. HNSW does not train on tables, but it is a very useful partner for them in several concrete ways. See the research overview at /model/research and the architecture notes at /model/architecture for how such models are structured.

Retrieval of similar rows for in-context learning

Models such as TabPFN and TabICL read a set of labelled rows as context and predict labels for new rows in a single forward pass. This is in-context learning. Context size is limited, so for a large training table you cannot feed all rows. A common remedy is to pick the most relevant rows for each query. If each row is turned into an embedding vector, HNSW can fetch the k most similar rows quickly, and those become the context. Retrieval based tabular methods, such as one named TabR, rest on the same intuition that near neighbours carry strong signal.

The practical flow looks like this:

1. Encode every training row into a vector (from a row encoder or from the model's own hidden state).
2. Build an HNSW index over those vectors.
3. For each query row, fetch the top k neighbours with their labels.
4. Feed these neighbours as the context for the model.

This gives a local, query-specific context instead of one random sample for everyone.

Mixed types and missing values

Row embeddings must cope with numbers, categories and gaps. Typical choices are scaling numeric columns, using learned embeddings for categories, and encoding missing cells with a mask value or a learned "missing" token. Because HNSW only sees vectors, all that work happens before the index. The quality of neighbours depends entirely on the encoder. If missing cells are encoded badly, rows that look alike in the data may end up far apart in the vector space.

No column names

Many real tables have headers like col_17 or none at all. A model trained to read raw tables cannot lean on names. When you want to match columns across tables, or find a table that resembles another, you can embed column value distributions or samples and search them with HNSW. The index helps with schema matching at scale: given a new unlabelled column, find stored columns with similar value patterns.

Imputation

A classic way to fill a missing cell is to look at the most similar complete rows and borrow from them (k-nearest-neighbour imputation). With an HNSW index over rows embedded using the observed columns, this becomes fast even for millions of rows. A foundation model's own imputation head (see imputation networks and masked cell modeling) can use neighbour values as extra hints or as a baseline to compare against.

Anomaly detection

Distance to the k-th neighbour is a standard anomaly score: points far from everything else are suspicious. HNSW gives that distance cheaply. This sits next to model based detectors such as isolation forest. See also anomaly detection. For tabular foundation models, the same score can validate model flags or catch new rows that fall outside the training distribution before a prediction is trusted.

Sector and semantic classification

When a model assigns a row, a column or a whole table to a sector or semantic type (see semantic sector heads), a nearest neighbour lookup over labelled examples is a strong, explainable baseline. Embed the item, find the closest labelled items with HNSW, and vote. It also helps with long-tail classes that have few examples, since you can add a new labelled item to the index without retraining.

Continual learning and memory

Continual learning wants a model to take in new data without forgetting the old. An HNSW index can act as an external memory of past rows or exemplars. New rows are inserted as they arrive (the index supports incremental insertion), and replay samples can be drawn from it by similarity. This relates to experience replay and to agent memory ideas. The model weights stay fixed or change slowly while the memory grows.

Benchmarks and checks

Benchmarks of tabular models appear at /model/benchmarks. When a retrieval step sits in front of a model, report recall of the index separately from the accuracy of the model. A model can look weaker simply because the index returned poor neighbours.

Practical guidance and best practices

Choosing parameters

• Start with M between 12 and 32. Use 16 as a default and go higher for high dimensional or hard data.
• Start with efConstruction between 100 and 400. Higher values give a better graph at the cost of build time. Once the graph is good, raising it further yields little.
• Set efSearch at least as large as k. Sweep it and choose the smallest value that meets your recall target.
• Keep efConstruction larger than efSearch in typical setups.

Preparing the vectors

• Normalise for cosine. If you want cosine similarity, normalise vectors to unit length and use inner product, which is often faster.
• Use consistent dtype. Keep float32 unless you have tested lower precision.
• Reduce dimensions when you can. Fewer dimensions mean less memory and faster distance computation. Methods like PCA can help, but test recall afterwards.
• Match the metric to training. If the embedding model was trained with a given similarity, use that same metric.

Operating the index

• Measure recall on your own data. Public benchmark numbers are a guide, not a promise.
• Build with a representative sample. Insert in random order if you can. Sorted insertion can hurt graph quality.
• Plan for deletes. Track the share of deleted items and rebuild when it grows past a threshold you define.
• Use filters carefully. Test filtered queries with selective filters. If recall drops, consider pre-filtering, partitioning by the filter, or a system with filter-aware traversal.
• Save and load. Persist the index to disk so a restart does not need a rebuild.
• Watch memory. Include link storage, the OS cache, and any copy made during a rebuild.
• Warm the cache. The first queries after load can be slow while pages are read in.

Evaluating end to end

If HNSW feeds a RAG system, measure the whole chain with tools such as RAGAS, and use tracing to see which stage costs time. The index is rarely the only bottleneck. Embedding the query and reranking can cost more.

A tuning recipe you can follow

Tuning HNSW is easier when you change one thing at a time and measure against a fixed ground truth. The steps below work for most projects.

1. Take a sample of 1,000 to 10,000 real queries, not random vectors. Real queries have the same structure as production traffic.
2. Compute exact nearest neighbours for that sample with a brute-force scan. This is your ground truth.
3. Build the index with a moderate setting such as M = 16 and efConstruction = 200.
4. Sweep efSearch over values such as 16, 32, 64, 128, 256 and record recall@10 and latency for each.
5. Pick the smallest efSearch that meets your recall target at your latency budget.
6. If you cannot reach the recall target even at a large efSearch, rebuild with a higher M or efConstruction.
7. Repeat the sweep after any change to the embedding model, because the geometry of the vectors changes.

The reason to start with efSearch is that it costs nothing to change. It is a query-time knob. M and efConstruction are build-time knobs and need a rebuild.

Parameter starting points by scale

These are starting points, not rules. Data with high intrinsic dimension, many near duplicates, or strong clusters can need very different values.

Using HNSW from Python

Two popular ways to use HNSW are the standalone hnswlib package and the HNSW index inside FAISS. The example below uses hnswlib with random placeholder data.

import numpy as np
import hnswlib

dim = 64
n = 100_000
rng = np.random.default_rng(0)
data = rng.normal(size=(n, dim)).astype("float32")

index = hnswlib.Index(space="cosine", dim=dim)
index.init_index(max_elements=n, ef_construction=200, M=16)
index.add_items(data, np.arange(n))

index.set_ef(64)                      # efSearch
queries = rng.normal(size=(5, dim)).astype("float32")
labels, distances = index.knn_query(queries, k=10)
print(labels.shape, distances.shape)  # (5, 10) (5, 10)

The same idea in FAISS looks like this.

import faiss

index = faiss.IndexHNSWFlat(dim, 16)   # 16 is M
index.hnsw.efConstruction = 200
index.add(data)
index.hnsw.efSearch = 64
distances, ids = index.search(queries, 10)

Notice that the two APIs expose the same three knobs. Once you know M, efConstruction and efSearch, you can read the documentation of almost any vector database.

Filtered search with HNSW

Real applications rarely ask for the nearest neighbours of everything. They ask for the nearest neighbours that also match a condition, such as "same region" or "created this year". There are three common strategies.

Engines such as Qdrant, Weaviate and Milvus pick between these automatically, using the estimated selectivity of the filter. If you build your own, measure recall under filters separately from recall without them. An index that looks perfect on unfiltered queries can degrade badly when only one percent of nodes are allowed.

Monitoring an HNSW index in production

• Track recall on a small canary set of queries with known answers. Re-run it on a schedule.
• Track p50 and p99 latency, not only the mean. Tail latency shows memory pressure first.
• Track the share of deleted or tombstoned nodes. When it grows past a threshold, rebuild or compact.
• Track memory resident size. HNSW wants its graph and vectors in RAM; swapping to disk destroys latency.
• Track build time per batch of inserts. A sudden rise can mean the graph is under contention or the machine is short of cores.
• Version the embedding model next to the index. Mixing vectors from two models in one index silently ruins recall.

When not to use HNSW

HNSW is a strong default, but it is not always the right tool. Skip it, or pair it with something else, in these cases.

• The collection is small enough that an exact scan takes a few milliseconds. Exact search has perfect recall and no tuning.
• Memory is tight and the collection is huge. Compressed indexes such as IVF-PQ or disk based graphs fit better.
• Data changes by constant heavy deletes and rewrites. Tombstones pile up and graph quality drifts.
• You need strict, provable guarantees on the result. HNSW is approximate by design.

Variants and related ideas

HNSW has many descendants and neighbours. Knowing their names helps when you read documentation or papers.

A short checklist before you ship

• The distance metric matches the way the embeddings were trained.
• Vectors are normalised if you use inner product as a stand-in for cosine.
• Recall was measured on real queries, with and without filters.
• efSearch is set per use case, not left at a library default.
• A rebuild plan exists for model upgrades and heavy deletes.
• Memory headroom covers growth for the next planning period.
• A fallback to exact search exists for audits and debugging.

Common mistakes

• Using the wrong metric. Building with L2 on vectors trained for cosine can quietly lower quality.
• Skipping the recall check. An index that returns fast but wrong results looks fine in a demo and fails in production.
• Setting efSearch below k. The index cannot return k good results if it explores fewer than k candidates.
• Over-tuning efConstruction. Very high values slow builds and rarely help beyond a point.
• Ignoring the cost of deletes. Heavy churn without rebuilds bloats memory and lowers recall.
• Assuming filters are free. Strict metadata filters can cause empty or low-recall results.
• Forgetting the encoder. The index is only as good as the embeddings. A poor row encoder gives poor neighbours however well the graph is tuned.
• Testing on tiny data. Behaviour at 10,000 points does not predict behaviour at 100 million.
• Mixing embedding versions. Vectors from two different encoders in one index produce meaningless distances.
• Ignoring duplicates. Many identical vectors can create dense clumps that waste links. Deduplicate first when you can.

Frequently asked questions

What does HNSW stand for?

HNSW stands for Hierarchical Navigable Small World. "Hierarchical" refers to the stack of layers, "navigable" means a greedy walk can reach a target, and "small world" refers to the property that any two points are connected by a short path.

Is HNSW exact or approximate?

HNSW is approximate. It usually returns most of the true nearest neighbours, but it can miss some. You control the balance between speed and accuracy by changing efSearch, and you should measure recall on your own data.

What is the difference between M, efConstruction and efSearch?

M sets how many links each point keeps, which shapes the graph and its memory use. efConstruction sets how many candidates are considered while inserting points, which shapes graph quality and build time. efSearch sets how many candidates are considered at query time, which shapes recall and latency.

How much memory does an HNSW index need?

You need space for all raw vectors plus the links, which are about M0 times 4 bytes per point on the bottom layer. For high dimensional float vectors the raw data dominates, so the index is only a little larger than the vectors themselves.

Can HNSW handle deletions and updates?

Most implementations mark deleted items rather than removing them, so the graph paths stay valid. Heavy deletion leaves waste behind, so you should rebuild or compact the index from time to time. Updates are usually done as a delete followed by an insert.

When should I choose IVF-PQ or DiskANN instead?

Choose a compressed index like IVF-PQ when memory cost is the main limit and you can accept lower recall. Choose a disk based graph like DiskANN when the collection is far too large for RAM but you still need graph level accuracy and low latency. For data that fits in memory, HNSW is the usual first choice.

Does HNSW work with metadata filters?

It can, but filtering is the hardest part. If the filter keeps most points, the graph works well. If the filter is very selective, the walk may struggle to find valid results, so systems add filter-aware search, partitioning, or a fallback to scanning the matching subset.

Can HNSW be used on tabular data?

Yes, once rows are turned into vectors. You can retrieve similar rows for context in tabular models, impute missing cells from near neighbours, flag far-from-everything rows as anomalies, and classify items by looking at labelled neighbours. The quality depends on how the rows are encoded.

Do I need to train HNSW before use?

No. Unlike IVF-style indexes that need a training step to learn cluster centres, HNSW can start empty and grow by inserting points. This makes it convenient for streaming or frequently updated data.

Why is recall sometimes lower on new data after many inserts?

A graph built on early data may not reflect later data well, especially if the data drifts. Many deletes can also thin out useful links. Rebuilding the index, or building with a larger efConstruction, usually restores recall.

Glossary

• ANN (approximate nearest neighbour): Search that returns close neighbours quickly instead of guaranteeing the exact closest.
• Recall@k: The fraction of the true top k neighbours that the search returns.
• Embedding: A vector that represents an item such as a sentence, an image or a table row.
• Proximity graph: A graph where each node links to nearby nodes.
• Small world network: A network where most nodes are reachable through few hops.
• Skip list: A layered list structure that allows fast lookup by skipping over elements.
• Entry point: The node where every search begins.
• Greedy search: A walk that always moves to the closest known node.
• efSearch: The candidate list size used at query time.
• efConstruction: The candidate list size used when inserting points.
• M: The maximum number of links per node on upper layers.
• Tombstone: A marker showing that an item is deleted but still sits in the structure.
• Quantization: Compressing vectors by storing approximate codes instead of full values.
• Filtered search: Nearest neighbour search that also applies metadata conditions.
• In-context learning: Predicting from examples supplied in the input, without updating model weights.
• Imputation: Filling in missing values in a table.

Summary

HNSW is a layered proximity graph that makes approximate nearest neighbour search fast and accurate. Upper layers give long jumps, the bottom layer gives fine detail, and one parameter, efSearch, trades speed for recall. It needs memory, builds slowly at large scale, and handles deletes and filters with care, but it remains the standard default for in-memory vector search. For tabular foundation models it is a practical helper: it retrieves similar rows for context, supports imputation and anomaly scoring, backs semantic classification, and gives a growing external memory for continual learning, as long as the row encoder produces good vectors. Compare it with IVF-PQ, ScaNN and DiskANN when memory or scale becomes the main constraint.

Related

It belongs to Vector search in my stack, under LLMs, retrieval, and evaluation. Others in the same group: