What is neighbor-list capacity?

Neighbor-list capacity is the maximum number of connections a single node’s neighbor list is allowed to hold at a given layer — the concrete, enforced ceiling that Mmax and Mmax0 actually represent when translated from an abstract parameter into a real limit checked against a real data structure during construction. Where a neighbor list is the data structure itself, capacity is the specific numeric bound governing how large that structure is permitted to grow, and understanding capacity as its own concept clarifies exactly what gets checked, and when, as an HNSW index is built up one insertion at a time.

How does neighbor-list capacity actually relate to the Mmax and Mmax0 parameters covered elsewhere in this glossary?

Mmax and Mmax0 are the parameters that set neighbor-list capacity for the upper layers and the base layer respectively — capacity is really just the concrete, per-node consequence of whichever of those two parameters applies to the layer in question. A node’s neighbor list at layer two, for instance, has a capacity equal to Mmax, meaning it can hold at most that many connection entries before the construction process needs to intervene, while that same node’s neighbor list at layer zero has a capacity equal to Mmax0, almost always a different, typically larger number. This distinction is worth stating plainly because it’s easy to conflate “capacity” with a single fixed number applying uniformly across an entire node — in reality, a node’s capacity varies by layer, exactly mirroring the layer-specific difference between Mmax and Mmax0 already discussed on their own glossary pages.

What actually happens, mechanically, when an insertion would push a neighbor list past its capacity?

Every time the construction process considers adding a new bidirectional connection to an existing node, it first checks whether that node’s neighbor list at the relevant layer has already reached its capacity. If there’s still room, the new connection simply gets added, growing the list by one entry. If the list is already at capacity, the construction process instead re-runs the neighbor-selection heuristic over the node’s current full set of neighbors plus the new candidate, and the resulting selection gets pruned back down to fit exactly within the capacity limit, which may mean the new candidate gets kept and an existing connection gets dropped, or, if the heuristic judges the new candidate to be a worse fit than everything already present, the new candidate simply doesn’t get added at all and the existing neighbor list stays unchanged. This overflow-handling process, covered in more depth on the neighbor-list-overflow glossary page, is the actual mechanism that keeps every neighbor list’s size honestly bounded by its capacity throughout the life of a growing index, rather than capacity being merely an aspirational target that real neighbor lists might occasionally exceed.

This check-and-prune behavior happens routinely and repeatedly throughout construction — it isn’t a rare edge case reserved for unusual insertion patterns, but rather the normal, expected mechanism by which nodes that attract many incoming connections over the life of an index get kept within their capacity limit, since a popular node in a dense region of the vector space can easily attract more candidate connections over time than its capacity would allow if left unchecked.

Why does capacity matter as a hard constraint rather than simply a soft target the construction process aims for?

Enforcing capacity as a genuine hard limit, rather than a target that could occasionally be exceeded, is what keeps HNSW‘s memory usage and per-node search cost predictable and bounded regardless of how a specific dataset happens to be distributed. Without a strictly enforced capacity, a node sitting in an unusually dense or popular region of the embedding space could accumulate an unbounded number of incoming connections over the course of many insertions, eventually becoming a de facto hub whose expansion during search costs far more than a typical node’s — precisely the kind of unbounded, unpredictable degree growth the hub-node glossary page describes HNSW‘s explicit degree caps as being designed to prevent. Treating capacity as a hard ceiling, enforced through the overflow-and-pruning mechanism at every insertion, is exactly what guarantees that no node, however popular it becomes over an index’s lifetime, can ever exceed the bounded connectivity budget the rest of the graph was designed around.

Having covered exactly what capacity means as the enforced numeric limit behind Mmax and Mmax0, the neighbor-list-overflow glossary page is the natural next stop, since it goes deeper into the specific pruning mechanism this page describes only at a high level. From there, the graph‘s-connectivity-budget glossary page ties capacity back into the broader framing of degree limits as a shared, finite resource spent across the entire graph rather than a collection of unrelated per-node settings.