What is graph quality, in the context of HNSW construction?
Graph quality, in the context of HNSW construction, is a way of summarizing how well-suited a finished graph actually is for fast, accurate greedy search — capturing properties like connectivity, diversity of connections, and navigability that together determine whether a search moving through the graph tends to find good answers efficiently, as opposed to getting stuck or wandering unnecessarily. It’s not a single number with one universal definition, but a cluster of related structural properties, and understanding what actually contributes to graph quality clarifies why so much of HNSW‘s construction machinery — neighbor selection, pruning, the layered hierarchy itself — exists specifically to push that quality in a favorable direction.
What are the actual structural properties that add up to a graph being described as high or low quality?
Connectivity is the most basic requirement: a graph, or at least each layer of it, needs to form a single connected component, since any region disconnected from the entry point is permanently unreachable regardless of how good the rest of the graph might be. Beyond basic connectivity, diversity of connections matters enormously — a node whose limited connection budget is spent on several genuinely different directions in the surrounding space offers a search far more useful navigational options than one whose connections are all clustered redundantly in a single direction, exactly the distinction covered on the diversified-neighbor-selection glossary page. Navigability, a somewhat broader and less formally defined property, describes how reliably a greedy, purely local search strategy actually succeeds at finding good answers on the graph, which depends on both connectivity and diversity together, but also on more subtle structural characteristics like how consistently a node’s neighbors actually lead in directions that make progress toward arbitrary queries rather than merely toward whatever happened to be nearby during construction.
These properties interact rather than acting independently — a graph can be technically fully connected while still navigating poorly if its connections are badly diversified, and a graph with excellent local diversity at every individual node can still suffer if some structural weakness leaves certain regions only reachable through a small number of fragile bridge connections, as covered on that glossary page.
How does graph quality actually manifest in measurable, practical terms rather than as an abstract structural description?
The most direct, practical signal of graph quality is recall achieved at a given efSearch setting — a higher-quality graph reaches strong recall with a comparatively narrow, cheap search, while a lower-quality graph needs a much wider, more expensive search to reach the same recall, if it can reach it at all. This is exactly why graph quality and search efficiency are so tightly linked in practice: two indexes built from identical data with identical M and efConstruction values can still end up with meaningfully different quality if other factors — insertion order, dataset density variation, or construction bugs — happened to produce different actual graph structures, and that difference shows up directly as a difference in the recall-versus-efSearch trade-off curve each index actually delivers.
Which specific construction-time decisions have the most direct influence on the finished graph’s quality?
efConstruction‘s influence is significant and direct: a wider construction-time search gives the neighbor-selection heuristic a richer candidate pool to choose diverse connections from at every single insertion, and this compounds across an entire build to produce noticeably better-connected graphs overall, which is exactly why efConstruction is treated as a primary quality lever throughout the tuning-and-optimization chapter of this documentation. The neighbor-selection heuristic’s own design matters just as much in a different sense — even with a rich candidate pool available, a heuristic that simply kept the closest candidates, as described on the simple-neighbor-selection glossary page, would still produce a lower-quality graph than one that actively favors diversity, regardless of how wide the candidate search feeding it happened to be. M and Mmax0 contribute too, since a larger connectivity budget gives every node more room to actually express a diverse, well-spread set of connections, though with diminishing returns and rising memory cost past a certain point specific to any given dataset.
Dataset characteristics play a role independent of any parameter choice as well — a dataset with highly uneven density, where some regions are sparsely populated relative to others, tends to produce lower-quality connectivity in those sparse regions regardless of how generously M and efConstruction are set, simply because there are fewer genuine nearby candidates available there for the neighbor-selection heuristic to work with in the first place.
Having covered the structural properties that together make up graph quality and the construction-time decisions that most directly shape it, the diversified-neighbor-selection and efConstruction glossary pages are worth revisiting together with this fuller picture of how they contribute to a well-navigable finished graph. From there, the recall-based-approximation and query-difficulty glossary pages pick up the practical, measurement side of graph quality, covering exactly how it gets evaluated and where its effects show up most visibly in real search results.