What is path length?

Path length is a measure of how “big” a specific path through a graph is — in the simplest and most common sense, the number of edges the path uses to get from its starting node to its ending node. A path that moves through three edges to connect two nodes has a path length of three, regardless of how many alternative routes with different lengths might also connect the same two nodes. It’s a property of one particular path, not of the two nodes it connects, which is the detail that separates it from the related idea of a shortest path — the shortest path between two nodes is simply whichever path between them has the smallest path length, or the smallest total weight, out of every path that exists.

How is path length measured, and does it always mean the same thing?

In an unweighted graph, path length is unambiguous: it’s just a count of how many edges the path crosses. A path visiting four nodes in sequence — the start, two intermediate nodes, and the end — uses three edges to do so, so its length is three, one less than the number of nodes it touches. This hop-count version of path length is what most people picture first, and it’s the natural measure whenever every edge is treated as equally significant.

In a weighted graph, path length more often refers to the sum of the weights along the path rather than a simple edge count, since a graph that bothers to attach weights to its edges is usually doing so because some connections matter more, or represent more distance or cost, than others. A path using only two edges could have a longer weighted length than a path using five edges, if those two edges happen to carry much larger weights than the five do combined. Because a proximity graph attaches a distance to every edge, path length in that context is almost always meant in this weighted sense — the cumulative distance traveled by hopping from node to node along the path, not merely how many hops were taken to do it. Getting this distinction right matters because a search algorithm reasoning about “how far” something is needs to know which sense of path length is actually being used, since the two can rank paths differently.

Why does path length matter for reasoning about how a search graph behaves?

Path length is the building block that several other, more commonly discussed graph properties are defined in terms of. A shortest path is the path with the minimum length between two specific nodes. Graph diameter is the maximum, across every pair of nodes in the graph, of that pair’s shortest path length — in other words, the length of the single longest “shortest path” anywhere in the graph. Neither of these ideas means anything without path length as the underlying unit of measurement they’re built on top of, which is why it’s worth understanding on its own before moving to those aggregate properties.

For a search algorithm actually running on a graph, path length translates directly into cost. Every edge a traversal follows corresponds to one step of work — a distance computation, a check against the visited set, a possible update to the candidate and result queues — so the length of the path a search actually ends up tracing is a reasonable proxy for how much computational work that search did. This is part of why HNSW‘s layered hierarchy exists: a single flat graph might require a long path, in the hop-count sense, to get from an arbitrary entry point to the neighborhood near a given query, and stacking sparser layers on top gives the search a way to make large jumps toward the right neighborhood before dropping down to the denser base layer, effectively shortening the path length the search needs to trace in the layer that costs the most to search.

Does a shorter path always mean a better path for search purposes?

Not automatically. Path length only captures the length of a path — it says nothing about whether a search algorithm can actually find that path in practice. A graph might have a short shortest path between two nodes that a greedy search, making purely local decisions at each step, has no realistic way of stumbling onto, especially if the path requires temporarily moving away from the query before eventually converging on it. This is why HNSW‘s construction process cares not just about keeping path lengths short in principle, through a well-connected, diversified graph, but about making sure those short paths are actually discoverable by a greedy traversal that only ever looks at its current node’s immediate neighbors. A graph with excellent theoretical path lengths but poor local structure — where greedy decisions frequently lead away from the eventual answer — can still perform poorly in practice, which is exactly the gap that separates path length as an abstract property from the practical query difficulty and recall the algorithm actually delivers on real workloads.

With path length established as the basic unit that shortest paths and graph diameter are both built from, the graph diameter glossary page is the natural next stop for seeing how this idea aggregates across an entire graph rather than a single pair of nodes. From there, the query difficulty and search failure mode glossary entries are worth exploring, since they cover exactly the gap described above, between a graph having short paths in theory and a greedy search actually being able to find them in practice.