About this article: AI-assisted writing, reviewed against the cited sources. This is source research, not a lab validation of the procedures. Check the stated versions and your own recovery requirements before making changes.
An HNSW index is a stack of graphs. The top graph is small and has long links. Each layer below is denser. A query starts at the top and walks downhill until the bottom layer, where the real neighbours live. Three numbers decide how that walk behaves. M is how many links a point keeps. efConstruction is how wide the search is while the graph is being built. The search-time list, which the paper calls ef, is how wide the walk is when you query. Recall is the fraction of the true nearest neighbours that walk actually returns. Excluding stored vectors, index memory is mostly graph links; full vectors can dominate total memory.
An AI writing system produced this article for NetLeverage's editorial studio. "The index remembers a neighbour" means an edge in this graph. It is not a claim about experience.
Nothing was built or queried for this article. The parameters are the ones in Malkov and Yashunin's paper and in the hnswlib README. A library that spells the search-time width efSearch is not documented on those two pages. Read that library before you assume the spelling is the same knob.
Why it matters
Exact nearest neighbour looks at every vector. The paper's point is that this cost grows with the number of stored elements, and that exact tree methods lose their advantage once the dimension is high. Approximate search allows a miss. You choose how many misses you will tolerate, and you pay for fewer misses with a longer candidate list and a fatter graph.
A small M limits connectivity. The paper's specific clustered-data trapping result concerns the nearest-only neighbour-selection rule, rather than small M alone. If ef at query time is barely larger than the number of neighbours you asked for, you will not have inspected enough candidates to reach high recall. If you raise both without looking at bytes, the index, which the paper prices in links per point, grows in proportion to M.
How the hierarchy is built
The paper's construction inserts points one by one. Each new point is assigned a maximum layer
with a uniform draw. The probability of a high layer decays exponentially. The paper gives as an approximate layer count, ignoring the floor in the draw. Including the floor gives layers on average for positive ; at , this is . They suggest setting . That choice showed up as a sensible automatic value on the plots they printed, including 5 million 128-dimensional SIFT vectors and a high-dimensional random set. Setting to 0 collapses the structure to a single layer.
Insertion then searches from the top. On layers above the new point's own layer, the candidate list width ef is 1: a greedy step, so construction does not grow a second family of parameters. From the new point's layer downward, ef becomes efConstruction. The neighbours found on the way are the candidates for the new point's links. The insert stops when the links exist on layer 0, the ground layer.
Two ways exist to pick which candidates become links. One connects to the nearest. The other is a heuristic that also looks at distances among the candidates, so the links point in different directions instead of all falling inside one cluster. The paper shows the nearest-only rule getting stuck on cluster boundaries and failing to reach high recall on clustered data. The heuristic, with its option to extend the candidate set, does not. On uniform and very high-dimensional data the two rules are close. extendCandidates defaults to false in their description and matters for extremely clustered data. keepPrunedConnections keeps the link count fixed by allowing some discarded candidates back.
Each point has a cap on links. Mmax is the cap on layers above 0. Mmax0 is the cap on the ground layer. If a point is already full, its list is shrunk with the same neighbour rule. The authors' simulations say setting Mmax0 equal to M hurts high-recall search badly, and that Mmax0 = 2M is a good choice: higher wastes memory and can slow the search. Their figure on the 5 million SIFT learn set, on a Core i5 2400, puts that automatic value near the best query time across recalls.
The only construction parameter they tell a user to treat as the real choice is M. A reasonable range in the paper is 5 to 48. Smaller M tended to win at lower recall and lower dimension. Larger M tended to win at high recall and high dimension. efConstruction is the other construction dial, and they say to set it high enough that the nearest-neighbour recall during construction is close to 1. They write that 0.95 is enough for most use cases. In a separate timing example, a 10-million-vector SIFT build used M=16 and efConstruction=100 on four 2.4 GHz 10-core Xeon E5-4650 v2 processors and finished in about three minutes. Their “little extra performance” observation for larger construction width belongs to that example, not a universal threshold at 0.95 recall.
Search is the same walk with the new point's layer fixed at 0. The ground-layer candidates are the result, not new edges. Quality is the search-time ef. The paper defines recall as the number of true nearest neighbours found, divided by K. Recall error in their plots is 1 minus that.
hnswlib, the library README opened from the nmslib repository on 10 November 2026, uses the same names with different spelling. init_index takes M and ef_construction. The examples use M = 16 with ef_construction of 200, and another example uses 100. set_ef(ef) sets the query-time trade-off. The README says this ef is not saved with the index, so a process that loads a file and does not call set_ef is not necessarily using its previously configured query width. A comment in the README says ef should always be greater than k. The paper's search parameter and this function are the same idea: the width of the candidate list at query time. They are not efConstruction.
Recall against work
Raising search-time ef lengthens the candidate list the walk keeps. The paper's curves are query time against recall for a fixed graph: you do not rebuild to try a higher ef. You pay CPU at query time. Construction-time efConstruction changes which edges exist. Our inference: a graph built with a low efConstruction cannot be rescued by a huge query ef as reliably as one whose edges were chosen from a near-exact neighbour list. That is consistent with their advice to target construction recall near 0.95 even if production queries will run at a lower ef.
M changes the graph permanently. More links give the heuristic more directions to keep, which is why high recall and high dimension wanted a larger M in their plots. More links also mean more distance evaluations when the walk expands a node. The memory note and the speed note are the same parameter.
Their recall numbers are on the datasets in the paper, including SIFT and random vectors, and on the machines they name. Do not copy "M = 16, ef = 50, recall will be 0.95" onto an embedding collection. Dimension, cluster structure and the distance (their hnswlib examples include l2, cosine and ip) move the curve. Measure recall on a sample whose true neighbours you computed by brute force, with the same distance the index uses.
Memory
The paper says index memory, excluding stored data, is mostly graph connections. Per element, the ground layer stores up to Mmax0 links and the other layers contribute on average through m_L and Mmax. Its approximate average link-storage estimate, using its layer approximation, is
If the index holds at most about four billion elements, a link can be a 4-byte unsigned integer. With M in the range they call typical, about 6 to 48, they estimate about 60 to 450 bytes per object for the index, excluding the vectors themselves. The vectors are extra. A million 768-dimensional float32 embeddings are about 3 GB of vectors before a single link is stored. The graph on top, at a few hundred bytes per object, is small beside that, and it is still large enough to matter when M is 48 and the collection is hundreds of millions.
hnswlib's resize_index changes capacity and is not thread-safe with inserts. set_ef after load is mandatory if you care about the query width, because that value is not in the file. Those are library facts from the README, not from the revised PDF of arXiv:1603.09320.
What to choose and why
| Goal | Set | Why the paper says so |
|---|---|---|
| High recall, high dimension | Larger M, inside 5–48, and Mmax0 around 2M |
Bigger M helped high recall; Mmax0 = M hurt it |
| Lower recall or lower dimension | Smaller M |
Their plots went the other way at the low-recall end, and memory scales with M |
| Edges that are not trapped in one cluster | The neighbour heuristic, not "connect to the nearest only" | Nearest-only stalled on cluster boundaries |
| A graph that can reach high recall later | efConstruction high enough for construction recall near 0.95 |
They say 0.95 covers most use cases; more buys little |
| A faster query once the graph exists | Lower search-time ef, at least k |
Recall depends on this width; the README recommends above k, while the parameter guide specifies no lower than k |
| Layer balance | m_L = 1/\ln(M) unless you have measured otherwise |
That was their automatic value |
Our recommendation, not a default from either document: fix M and efConstruction from a brute-force recall sample, then use search-time ef as the knob you can change without a rebuild. Do not tune recall by rebuilding on every query.
The safe order
1. Name the distance. hnswlib's examples construct an index with space of l2, cosine or ip. Recall measured under a different distance is a different problem. Cosine and inner product are not the same ranking unless the vectors are normalised. That identity is not re-derived here; do not mix them inside one index.
2. Build a small exact baseline. On a sample, compute true neighbours with a full scan. Recall is found true neighbours divided by K, as the paper defines it. If you cannot afford the scan on the full set, say that the recall figure is on the sample.
3. Set M, then efConstruction, then search ef. Change one at a time. M and efConstruction require a rebuild. Search ef does not. In hnswlib, call set_ef after every load.
4. Read memory as links plus vectors. Use the paper's per-element link formula as an average estimate, and add the raw vectors. A recall gain from M = 48 that doubles link memory and does not move recall on your sample is not worth it.
5. Do not raise efConstruction forever. The paper reports little extra search performance above efConstruction=100 in its specified 10M SIFT example; check the curve on your data rather than treating that as a universal ceiling.
Risks and limits
- The ranges 5–48 and 6–48, the 0.95 construction recall, and
Mmax0 = 2Mare the paper's simulation advice, much of it on SIFT and on CPUs they name. They are not a guarantee for a 1000-dimension embedding set. - 60–450 bytes per object excludes the data and assumes 4-byte links under about four billion points. Past that, links widen.
- Search
efandefConstructionare different. One is query width. One is build width. hnswlib does not storeefin the index file. - The name
efSearchdoes not appear in the paper or in the hnswlib README opened here. If another library uses that spelling, confirm it against that library's page before you copy a number across. - Recall in the paper is inexact-search quality, the fraction of true neighbours returned. It is not a relevance grade for a language query.
- No index product and no NetLeverage search service is measured.
Sources
- Yu. A. Malkov and D. A. Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, arXiv:1603.09320 — https://arxiv.org/pdf/1603.09320 (PDF opened 10 November 2026). Layer draw,
M,efConstruction, searchef,m_L,Mmax0, recall definition, memory formula. - nmslib/hnswlib README — https://github.com/nmslib/hnswlib/blob/master/README.md (raw master opened 10 November 2026).
M,ef_construction,set_ef,ef > k,efnot saved with the index, spacesl2,cosine,ip.
This article was originally published on .