What is a graph’s connectivity budget?

A graph‘s connectivity budget is the total amount of connection capacity available across the whole structure, determined by how many edges each node is allowed to keep and how many nodes exist in total — a useful way of thinking about degree caps like M and Mmax0 not as isolated per-node settings, but as a resource that gets allocated across the entire graph, with real consequences for how well that graph can be navigated once every node’s individual allowance has been spent. Framing degree limits this way makes clear why simply raising every cap as high as possible isn’t a free way to improve search quality, and why the neighbor-selection heuristic’s job of spending each node’s limited allowance wisely matters as much as the size of the allowance itself.

Why does it help to think about degree caps as a shared, finite budget rather than isolated per-node limits?

Every node in an HNSW graph has a limited number of connections it’s allowed to keep, set by M in the upper layers and Mmax0 at the base layer, and every one of those connections is a genuine, finite resource — it costs memory to store, it costs time to traverse, and once a node has spent its full allotment, adding a new connection means giving up an existing one rather than simply accumulating more without bound. Viewed across the whole graph rather than one node at a time, this creates a genuine budget: the total number of edges the graph can ever contain is bounded by the sum of every node’s individual cap, and every one of those edges has to be spent on some specific connection, meaning a graph that spends its budget poorly — clustering redundant connections in a few directions rather than spreading them usefully — gets less navigability out of the same total edge count than a graph that spends the identical budget more thoughtfully.

This reframing is exactly why the neighbor-selection heuristic exists as a deliberate design choice rather than a simple “keep the closest candidates” rule. Simply keeping the closest available candidates spends a node’s connectivity budget on whatever happened to be nearby, which, as covered on the k-nearest-neighbor-graph glossary page, tends to produce redundant clusters of connections in dense regions of the space. A smarter spending strategy — the diversified selection HNSW‘s heuristic actually performs — treats each node’s limited budget as something to allocate deliberately across different directions in the surrounding space, getting more genuine navigability out of the exact same total number of edges.

What happens to overall search quality when the connectivity budget is spent poorly versus well?

A graph that spends its connectivity budget poorly tends to develop exactly the kind of structural weaknesses covered elsewhere in this documentation — nodes whose neighbors are all clustered in roughly the same direction, leaving other directions poorly reachable from that node even though its degree cap was fully used; regions of the graph that rely on a thin scattering of bridge-like connections to stay linked to the rest of the structure, since the budget available wasn’t spent building enough redundant paths between regions; and, in the worst cases, missing bridges in connectivity that directly cause specific queries to fail regardless of how generously efSearch is tuned at query time. None of these problems come from having too small a budget in an absolute sense — they come from that budget, however large, being spent in ways that don’t actually serve the graph’s overall navigability.

A graph that spends the same total connectivity budget well tends to avoid these failure modes even without necessarily using a larger M or Mmax0 than a poorly built comparison graph would — which is exactly the practical argument for why the neighbor-selection heuristic’s design matters at least as much as the raw degree-cap parameters themselves, and why simply increasing M in response to a recall problem sometimes helps less than expected if the underlying issue is really about how that budget is being allocated rather than how large it is.

How does this framing connect to the broader memory-versus-recall trade-off that runs through HNSW’s tuning story?

Every unit of connectivity budget spent is also, directly, a unit of memory spent — a node’s degree cap and the graph’s total memory footprint are two sides of the same coin, which is exactly why M and Mmax0 sit at the center of HNSW’s memory-versus-recall trade-off discussed throughout the tuning-and-optimization chapter of this documentation. Thinking in terms of a connectivity budget makes that trade-off concrete: increasing the budget by raising M or Mmax0 buys more room for genuinely useful connections, at a direct, proportional memory cost, while improving how that existing budget gets spent — through a better neighbor-selection strategy — can improve navigability without spending any additional memory at all.

Having covered why it helps to think of degree caps as a shared, finite budget rather than isolated per-node settings, the neighbor-selection-heuristic and diversified-neighbor-selection glossary pages are the natural next stop, since they cover exactly how HNSW tries to spend this budget wisely rather than merely allocating it generously. From there, the missing-bridge-in-connectivity and bridge-edge glossary pages look at what happens in practice when a graph’s connectivity budget, however large, ends up spent in ways that leave real gaps in the structure’s navigability.