HNSW, explained

A Hierarchical Navigable Small World graph, or HNSW, is a data structure for approximate nearest-neighbor search over dense vectors. Yury Malkov and Dmitry Yashunin described it in Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, first posted to arXiv on March 30, 2016 and revised through August 14, 2018. The index is a stack of proximity graphs: every stored vector sits in the bottom layer, a random fraction of them also appear in the layer above, a smaller fraction in the layer above that, and so on. A query enters at the sparse top layer, walks greedily toward its nearest point, and drops a layer each time it stops improving, until it finishes with a wider search in the bottom layer. Faiss, Lucene and pgvector all ship an HNSW index, and the three parameters the paper defines, M, efConstruction and ef, are the knobs those systems expose.

How the layered graph works

The paper describes HNSW as a generalization of the probabilistic skip list, with the sorted linked lists replaced by proximity graphs. When a new element is inserted, its maximum layer l is drawn at random: Algorithm 1 sets l to the floor of minus the natural log of a uniform random number, multiplied by a normalization factor mL. Because the draw is exponentially distributed, most elements land only in layer 0, a few reach layer 1, fewer reach layer 2, and so on. The element is then added to every layer from l down to 0.

Insertion itself reuses the search routine. Starting from the index's single entry point in the top layer, the algorithm greedily descends through the layers above l, finding the closest element at each. From layer l downward it runs a wider search with a dynamic candidate list of size efConstruction, picks M neighbors from the candidates, and adds bidirectional links to them. If a neighbor now has more links than the layer allows, Mmax for upper layers and Mmax0 for layer 0, its link list is pruned back with the same neighbor-selection routine.

Search, in Algorithm 5, is the same descent with a different list size. From the top layer down to layer 1 the candidate list has size 1, so each step is a plain greedy move to the closest element; describing the same first phase during insertion, the paper states that ef is set to 1, a simple greedy search, to avoid introducing additional parameters. At layer 0 the list grows to ef, the search explores more widely, and the K nearest elements in the final list are returned. The upper layers exist to get the search quickly into the right region of the space; the bottom layer, which contains everything, does the fine work.

Two refinements matter in practice. The first is the neighbor-selection heuristic, Algorithm 4, which prefers candidates that are closer to the new element than to any already-selected neighbor, so that links spread across directions instead of all pointing into one cluster. The paper reports that the heuristic gives higher or similar search performance in every tested case and that the effect is most prominent for low-dimensional data, at high recall for mid-dimensional data, and for highly clustered data. The second is that search at layer 0 backtracks: the greedy walk alone can get stuck in a local minimum because the graph only approximates a Delaunay graph, and the wider ef list is what lets it climb out.

HNSW parameters: M, efConstruction and ef

The paper's Algorithm 1 takes four construction parameters. M is the number of connections a new element establishes per layer. Mmax is the maximum number of connections an element may hold in layers above 0, Mmax0 is the same limit for layer 0, and mL is the normalization factor that governs how many layers the structure grows. Section 4.1 then shows that two of these can be fixed. The paper proposes mL equal to 1 over the natural log of M, which corresponds to a skip list with probability 1 over M, and shows in its Figures 3 to 5 that this auto-selected value sits close to the optimum. For Mmax0 it recommends 2 times M: setting Mmax0 equal to M produced a strong performance penalty at high recall, and setting it higher degraded performance and used excessive memory.

That leaves M. The paper's words are that "the only meaningful construction parameter left for the user is M" and that a reasonable range is 5 to 48. Smaller M gives better results at lower recall or on lower-dimensional data; larger M is better for high recall or high-dimensional data. M also sets the memory of the index, which grows in proportion to it. The hnswlib parameter guide, gives a wider reasonable range of 2 to 100 and says 12 to 48 is fine for most use cases.

efConstruction is the size of the dynamic candidate list during insertion. The paper says it has to be large enough that recall during construction is close to 1, that 0.95 is enough for most uses, and that it can be set automatically by measuring recall on sample data. hnswlib describes it as having the same meaning as the search-time ef while controlling index time against index accuracy, and offers a test: run an M-nearest-neighbor search with ef set equal to ef_construction, and if recall is below 0.9 there is room to raise it. The same page suggests treating M times ef_construction as roughly constant when adjusting one against the other.

ef is the search-time list size at layer 0. hnswlib calls it the size of the dynamic list for the nearest neighbors used during the search, says a higher value is more accurate but slower, and notes that it cannot be lower than k, the number of neighbors requested. Faiss names the same two dials efConstruction and efSearch; its index reference calls the first "the depth of exploration at add time" and the second "the depth of exploration of the search".

Memory cost

HNSW stores the full vectors and, on top of them, the graph links. Section 4.2.3 of the paper gives the average link memory per element as (Mmax0 + mL times Mmax) times the bytes per link. With the index capped at about 4 billion elements, links fit in 4-byte unsigned integers, and the paper states that with typical near-optimal M between 6 and 48 the index costs about 60 to 450 bytes per object, not counting the data. hnswlib's parameter page rounds this to roughly M times 8 to 10 bytes per stored element.

The Faiss wiki's guidelines give the total for its flat HNSW index as d times 4 plus M times 2 times 4 bytes per vector, where d is the dimension. The second term is the layer-0 links at 2M entries of 4 bytes each. Worked out, a 768-dimensional embedding stored with M of 32 takes 3,072 bytes for the vector and 256 bytes for links; a 1,024-dimensional embedding with M of 16 takes 4,096 plus 128. The vectors dominate, which is why the memory argument against HNSW is mostly an argument about storing uncompressed vectors. The Faiss index reference lists IndexHNSWSQ and IndexHNSWPQ, which store the vectors under the graph with a scalar or product quantizer, and Faiss's guidelines say that if memory is a concern, the IVF family with product quantization is the route. The companion post on vector search and Faiss covers those index types and their per-vector figures.

pgvector's README adds an operational note: HNSW indexes build significantly faster when the graph fits into the PostgreSQL setting maintenance_work_mem, so the build memory as well as the resident memory needs planning.

Build time

Construction cost is the other side of M and efConstruction. The paper reports that on a 10 million vector SIFT dataset a reasonable-quality index was built with efConstruction of 100 on a server with 4 ten-core 2.4 GHz Xeon E5-4650 v2 processors in about 3 minutes, and that raising efConstruction further bought little extra search performance at a significantly longer build. Section 4.2 gives the construction time scaling as O(N log N), at least for relatively low-dimensional datasets. The paper also states that construction parallelizes with few synchronization points and no measurable effect on index quality.

The paper's largest build is its comparison against Faiss on a 200 million vector subset of the 1 billion SIFT set, in Table 3. HNSW with M of 16 and efConstruction of 500 took 5.6 hours and 64 GB of peak memory; the same M with efConstruction of 40 took 42 minutes at the same 64 GB. The Faiss configurations it compared against, OPQ64,IMI2x14,PQ64 and OPQ32,IMI2x14,PQ32, took 12 and 11 hours and 30 and 23.5 GB. The memory gap is the uncompressed vectors; the time gap at low efConstruction is the graph's advantage.

Because insertion is the construction algorithm, HNSW is incremental. The paper's discussion section says the structure supports continuous incremental indexing, and the Faiss library paper by Douze and colleagues names the ability to add vectors on the fly as a notable advantage of HNSW. The Faiss guidelines add two constraints: Faiss's HNSW does not require training, and it accepts only sequential adds, so an IDMap wrapper is needed to attach your own ids.

Recall versus speed

Approximate search trades recall, the fraction of true nearest neighbors returned, against query time, and HNSW's dial for that trade is ef. A larger ef means the layer-0 search keeps more candidates, visits more nodes, and computes more distances. The paper's Figure 8 plots recall error against query time for different M on 5 million SIFT vectors, and its comparisons in Section 5 report HNSW as the leader across SIFT, GloVe, CoPhIR, DEEP and random-vector datasets against FLANN 1.8.4, Annoy, a VP-tree, FALCONN 1.2 and the baseline NSW graph from nmslib 1.1. For the 200 million SIFT comparison with Faiss, run on a server with 4 Xeon E5-4650 v2 processors and 128 GB of RAM, Table 3 records the memory and Figure 15 plots recall against query time for the two libraries.

Recall figures depend on the setting, so the responsible way to read them is with the dataset, k, M, efConstruction and ef attached. The ANN-Benchmarks project by Aumüller, Bernhardsson and Faithfull, described in a July 2018 paper, exists to make those comparisons repeatable: it runs each algorithm over a range of parameter settings on standard datasets and plots quality against queries per second. One of its stated findings is that "very different approaches to k-NN search yield comparable quality-performance trade-offs", which is a caution against reading a single library's chart as a ranking.

Two points of hygiene follow. First, the recall a graph index reports is agreement with exact search, not retrieval quality; a passage that the embedding model placed in the wrong neighborhood is returned confidently at recall 1.0. Second, ef is a search-time setting: hnswlib lists it among its search parameters and sets it with set_ef, Faiss sets efSearch at search time, and pgvector's README shows hnsw.ef_search set with SET LOCAL for a single query, so a system can run cheap searches at low ef and expensive ones at high ef against one index. The build-time parameters cannot be changed without rebuilding.

HNSW vs IVF

The main alternative to a graph index is the inverted file, or IVF, which partitions the vectors into clusters with k-means and searches only the nprobe clusters closest to the query. The Faiss guidelines describe IVF as clustering the vectors with k-means into K buckets, with K between 4 and 16 times the square root of the dataset size, and say it needs between 30 and 256 times K training vectors. The tradeoff is set by nprobe, the number of buckets visited.

The Faiss library paper states the decision rule its authors use. Graph-based indexes are "a good option for indexes where there is no constraint on memory usage", typically below 1 million vectors; beyond 10 million vectors the construction time of a graph typically becomes the limiting factor; and for larger indexes, where the vectors have to be compressed just to fit in memory, IVF indexes are the only option. The Faiss guidelines say the same thing from the other direction: with plenty of RAM or a small dataset, HNSW is the best option and "a very fast and accurate index". pgvector's README summarizes the tradeoff for a database user: HNSW has better query performance than IVFFlat, while IVFFlat has faster build times and uses less memory.

The two are not exclusive. The Faiss guidelines' recipes for 1 million to 1 billion vectors, IVF65536_HNSW32 through IVF1048576_HNSW32, use an HNSW graph as the coarse quantizer that assigns queries to IVF clusters, because with hundreds of thousands of centroids the assignment step itself needs an approximate index. The Faiss paper notes that it is common to use a non-exhaustive HNSW index to perform the coarse quantization.

Deletions and updates

The original paper lists support for element updates and removal as future work, and the implementations have handled the gap in different ways. The Faiss guidelines state plainly that the Faiss HNSW index does not support removing vectors, and the Faiss paper says the graph index does not support suppression and mutation, adding that the heuristics to rebuild a mutated graph exist in hnswlib but are suboptimal for indexing. hnswlib's README provides mark_deleted, which marks an element as deleted so it is omitted from search results, while the element and its links stay in the graph; the same README documents insertions and updates. Lucene's HnswGraph documentation says there is no notion of deletions in the graph and deletion filtering must be handled by the caller, which is how Lucene handles deleted documents generally.

For a document corpus that changes, this means one of three things: tolerate tombstones and rebuild periodically, keep the graph in a system that layers deletion handling on top, or choose IVF, where Faiss supports removal.

Where HNSW is implemented

The paper's reference implementation was written in C++ inside the Non-Metric Space Library, nmslib, which already had the earlier NSW graph under the name sw-graph. The authors' standalone library, hnswlib, describes itself as a header-only C++ implementation with Python bindings supporting insertions and updates; it offers squared L2, inner product and cosine distance, and its README states that add_items calls are thread-safe with each other but not with knn_query.

Faiss implements the graph as IndexHNSW, with IndexHNSWFlat built by the factory string HNSW,Flat storing full vectors. The Faiss wiki's index table gives its memory as 4d plus a multiple of M times 2 times 4 bytes per vector, and the guidelines note that HNSW is not supported on the GPU. Faiss also has IndexNSG, a second graph index, and IndexBinaryHNSW for binary vectors.

Apache Lucene added vector-valued fields under LUCENE-9322 and LUCENE-9855 and approximate nearest-vector search via NSW graphs under LUCENE-9004 and LUCENE-10040 in version 9.0.0, and the 9.1.0 change log records LUCENE-10054, "Make HnswGraph hierarchical", along with filtering support in KnnVectorQuery. The HnswGraph class documentation maps Lucene's names to the paper's: maxConn has the same meaning as M, and beamWidth has the same meaning as efConstruction.

pgvector's change log records the HNSW index type in version 0.5.0 on August 28, 2023 and parallel HNSW index builds in 0.6.0 on January 29, 2024. The README gives the defaults: m of 16, ef_construction of 64, and a query-time hnsw.ef_search of 40, with the vector type indexable up to 2,000 dimensions.

What to check

• Which M, efConstruction and ef or efSearch was the index built and queried with, and were they chosen by measuring recall on this collection or left at the library defaults?
• What recall against exact search was measured, at which k and which ef, and does the latency figure quoted come from the same ef?
• Does the index fit in RAM on the target machine with the full vectors plus links, using the d times 4 plus M times 8 bytes per vector figure, and does the build fit in the build-time memory limit?
• How are deleted or updated documents handled, given that the Faiss HNSW index cannot remove vectors and hnswlib only marks them?
• At the collection's size, does the Faiss decision rule point to a graph index at all, or to IVF with compression?
• Is retrieval quality measured separately from index recall, against passages a person marked relevant?

Azcuna's TRACE is one offline viewer for S1000D, MIL-STD-3001 XML, and PDF technical manuals. It keeps the source location and the markings of everything it shows and never modifies the source. It was proposed to NAVAIR under Navy SBIR Phase I topic DON26BZ05-NV078, and the proposal was submitted on September 23, 2026.

Questions people ask

What is an HNSW index?

HNSW stands for Hierarchical Navigable Small World. The 2016 paper by Malkov and Yashunin describes it as a multi-layer structure of proximity graphs built over nested subsets of the stored elements. Each element is assigned a maximum layer at random from an exponentially decaying distribution. A search starts in the sparse top layer, moves greedily toward the query, and descends one layer at a time until it reaches layer 0, which holds every element. The result is an approximate nearest-neighbor index that scales logarithmically in the paper's tests.

What does M mean in HNSW?

In the paper's Algorithm 1, M is the number of established connections a new element makes in each layer during insertion. The hnswlib parameter page defines it as the number of bi-directional links created for every new element. The paper calls M the only meaningful construction parameter left to the user and gives a reasonable range of 5 to 48; hnswlib says 12 to 48 is fine for most use cases and that memory is roughly M times 8 to 10 bytes per element.

What is efConstruction in HNSW?

efConstruction is the size of the dynamic candidate list used while inserting an element, per Algorithm 1 of the HNSW paper. The hnswlib parameter page says it has the same meaning as the search-time ef but controls index time against index accuracy, and that a bigger value means longer construction but better index quality. The paper says it should be large enough that recall during construction is close to 1, with 0.95 enough for most cases.

What is efSearch or ef in HNSW?

ef is the size of the dynamic candidate list kept while searching layer 0, per Algorithm 5 of the HNSW paper. The hnswlib parameter page says a higher ef gives a more accurate but slower search and that ef cannot be set lower than the number of neighbors requested, k. Faiss exposes the same dial as efSearch, which its wiki calls the depth of exploration of the search, and says the speed-accuracy tradeoff is set through it.

How much memory does an HNSW index use?

The HNSW paper gives the average per-element cost of the graph as (Mmax0 + mL times Mmax) times bytes per link, and with 4-byte links and typical M between 6 and 48 that is about 60 to 450 bytes per object, excluding the vectors. The Faiss guidelines give the total for IndexHNSWFlat as d times 4 plus M times 2 times 4 bytes per vector, so a 768-dimensional vector with M of 32 takes 3,072 plus 256 bytes.

Is HNSW better than IVF?

The Faiss paper says graph indexes are a good option where memory is not constrained, typically below 1 million vectors, that construction time becomes the limit beyond 10 million, and that IVF is the only option when vectors must be compressed to fit in memory. The pgvector README says HNSW has better query performance than IVFFlat but slower builds and more memory. The HNSW paper itself reported a 200 million vector index that took 64 GB against 23.5 to 30 GB for Faiss PQ indexes.

Does HNSW need training?

No. The Faiss guidelines state that HNSW does not require training. Elements are inserted one at a time, each one assigned a random top layer and connected to M neighbors per layer. That is different from IVF, where the Faiss guidelines say the index must first cluster a sample of the data with k-means, needing 30 to 256 training vectors per cluster. The HNSW paper describes construction as incremental, so new vectors can be added after the index is built.

Can you delete vectors from an HNSW index?

The original paper lists element updates and removal as future work, and the Faiss guidelines say Faiss's HNSW does not support removing vectors. The Faiss library paper puts it as the graph index not supporting suppression and mutation. hnswlib offers a mark_deleted call that hides an element from search results rather than removing it from the graph, and the Lucene HnswGraph documentation says the graph has no notion of deletions, so the caller must filter them.

Which libraries implement HNSW?

The paper's own implementation went into nmslib, and the authors' hnswlib is a header-only C++ library with Python bindings. Faiss has IndexHNSWFlat, built by the factory string HNSW,Flat, and also uses HNSW as the coarse quantizer for large IVF indexes. Apache Lucene added vector search via navigable small world graphs in 9.0.0 and made the graph hierarchical in 9.1.0 under LUCENE-10054. pgvector added an HNSW index type in version 0.5.0 on August 28, 2023.

What are good HNSW parameters to start with?

The defaults the implementations ship are a reasonable starting point. pgvector uses m of 16, ef_construction of 64, and hnsw.ef_search of 40. The hnswlib README example uses M of 16, ef_construction of 200, and ef of 50. The HNSW paper says smaller M suits lower recall or lower-dimensional data and larger M suits high recall or high-dimensional data, and hnswlib suggests measuring recall at ef equal to ef_construction and raising ef_construction if recall is below 0.9.

Sources

1. 1Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs · arXiv (Malkov and Yashunin)
2. 2hnswlib ALGO_PARAMS.md · nmslib on GitHub
3. 3hnswlib README · nmslib on GitHub
4. 4Guidelines to choose an index · Faiss wiki
5. 5Faiss indexes · Faiss wiki
6. 6The Faiss library · arXiv (Douze et al.)
7. 7Apache Lucene 9.1.0 change log · Apache Software Foundation
8. 8Class HnswGraph (Lucene 9.0.0 API) · Apache Software Foundation
9. 9pgvector README · pgvector on GitHub
10. 10pgvector CHANGELOG · pgvector on GitHub
11. 11ANN-Benchmarks: A Benchmarking Tool for Approximate Nearest Neighbor Algorithms · arXiv (Aumüller, Bernhardsson and Faithfull)

Where this shows up in our work

• TRACE, the offline S1000D and IETM viewer opens S1000D, MIL-STD-3001 and PDF technical manuals on a tablet with every marking intact.
• BABEL, offline multilingual translation and search translates and searches foreign-language documents on-device, every fact tied to its source passage.