What is the M parameter in HNSW?
The M parameter in HNSW sets the target number of connections each node keeps to its neighbors in every layer above the base layer, functioning as the primary knob controlling how densely connected — and, correspondingly, how much memory and search cost — the layered part of the hierarchy actually requires. It’s one of the first parameters anyone tuning an HNSW index has to decide on, and understanding what it actually trades off makes the rest of the tuning process considerably easier to reason about.
What does M actually control, mechanically, during index construction?
When a new node is inserted into the graph, HNSW‘s construction process searches for good candidate neighbors at each layer the node participates in, and then uses the neighbor-selection heuristic to choose a final set of connections from among those candidates — M is the target size of that final set. A node with M set to sixteen aims to end up with roughly sixteen connections in each of the upper layers it belongs to, though the exact realized number can vary somewhat due to the bidirectional-connection process, where inserting a new edge to an existing node can occasionally push that existing node slightly above or require pruning back down to its own target degree.
M applies specifically to the layers above the base layer — the base layer conventionally uses its own separate, typically larger cap, often called Mmax0, precisely because the base layer carries so much more search traffic and benefits from more generous connectivity than the sparser upper layers need. This distinction is worth keeping straight, since conflating M with the base layer’s degree cap is a common point of confusion when reading HNSW implementation code or research papers.
What does increasing M actually buy, and what does it cost?
A larger M means each node in the upper layers keeps more connections, which generally improves the quality and robustness of the graph‘s navigability — more connections per node mean more alternative paths available during traversal, reducing the chance that a search gets stuck at a poor local decision with no good way to route around it. This tends to improve recall, particularly on harder datasets where the underlying vector space has more complex local structure that a sparser graph might fail to capture adequately with too few connections per node.
This improvement doesn’t come for free. Every additional connection a node keeps means additional memory spent storing that connection, and it also means more work during construction, since the neighbor-selection heuristic has a larger target set to fill and consider at each insertion. It also means somewhat more work during search, since a node with more neighbors takes proportionally longer to fully expand each time a traversal visits it. Doubling M roughly doubles the memory spent on upper-layer graph structure and increases both construction time and per-step search cost correspondingly, which is exactly the trade-off that makes M worth tuning deliberately rather than simply maximizing it without consideration for cost.
How should someone actually go about choosing a value for M in practice?
There’s no single universally correct value, since the right choice depends on the specific dataset’s characteristics — its intrinsic dimensionality, how densely or sparsely its points are distributed, and how demanding the target recall actually is — combined with how much memory and construction time the application can actually afford to spend. Commonly cited starting points in practice tend to fall somewhere in the range of about eight to sixty-four, with smaller values suited to easier, lower-dimensional or more uniformly distributed datasets where a sparser graph already navigates well, and larger values reserved for harder datasets with more complex local structure, where the extra connectivity meaningfully helps a greedy search avoid getting stuck.
The practical approach to settling on a value, much like choosing k in a k-nearest-neighbors classifier, is empirical: build an index with a candidate value of M, measure recall and resource usage against a representative benchmark workload, and adjust from there based on whether recall is falling short of what’s needed or resource usage is higher than the application can sustain. This kind of systematic, benchmark-driven tuning approach, applied not just to M but to the full set of HNSW’s construction and search parameters together, is covered in much greater depth in the tuning-and-optimization chapter of this documentation.
Having covered what M controls and the memory-versus-recall trade-off it represents, the Mmax0 and Mmax glossary pages are the natural next stop, since they cover the closely related degree caps that apply specifically to the base layer and to the enforced maximum any single node’s connections can reach. From there, the neighbor-selection-heuristic glossary page explains exactly how the construction process decides which specific connections to keep once M sets the target count for how many it should aim to retain.