Nearest Neighbour

What the layers in a hierarchical graph buy

The H in HNSW is for hierarchical, and the hierarchy is the part most often described and least often explained. A flat proximity graph already finds nearest neighbours perfectly well. The layers are an optimisation of one specific cost, they were added to a working flat design rather than being the foundation of it, and knowing which cost they address tells you when they matter and when they barely do.

The naive approach

Start from a single navigable proximity graph: every vector is a node, each links to a bounded number of well-distributed neighbours, and search is a greedy walk with a candidate set. This works. It is a complete index and it was a published, usable design — the flat navigable small world graph — before any hierarchy was added.

How it fails, and it’s a narrow failure: the approach phase is slow. Search has to start somewhere, and that entry point is wherever the index chose — for a fixed entry point, potentially the far side of the collection from your query. Since the graph’s edges are mostly short local ones, crossing the occupied region takes many hops, each costing a distance computation against every neighbour of the current node.

Be precise about what is expensive here. The final phase — the careful examination of the query’s neighbourhood, which decides recall — is unavoidable work. The wasted work is everything before that: a long walk across territory nobody cares about, just to arrive in the right area. That approach cost grows with the extent of the collection, and it is pure overhead.

The flat graph does have long edges, from the diversified pruning rule, so the walk is not as slow as “one cell at a time”. But the long edges are incidental, arising where the local structure happened to demand them, and there is no organised set of them for crossing distance.

The idea: a coarse map for the long journey

If the expensive part is travelling far, build a smaller graph over a sample of the points where the edges are long, use it to get close, and only then descend to the full graph for the precise work.

The geometry is simple: a graph over 1% of the points has edges roughly an order of magnitude longer, because each node’s nearest sampled neighbour is much farther away than its nearest neighbour among all points. Sparsity buys reach for free. One hop up there covers ground that takes many hops below.

Stack that idea:

  • Layer 0 contains every vector, with short local edges. This is the flat graph.
  • Layer 1 contains a random sample of layer 0, with edges among that sample only.
  • Layer 2 a sample of layer 1. And so on, until a layer holds a single node.

Each node’s top layer is drawn at insertion from a geometric distribution: with probability p it goes one layer up, with probability p² two layers, and so on. Most nodes exist only at layer 0. The expected number of layers grows logarithmically with the collection size, and the topmost layer has one node, which becomes the fixed entry point.

Search runs top-down:

search(query, k, breadth):
    node ← the single entry point at the top layer
    for layer from top down to 1:
        node ← greedy_descend(layer, query, from = node)   # breadth 1: cheap, approximate
    return candidate_set_search(layer 0, query, from = node, breadth)

Two distinct behaviours in one procedure, and the split is the point. Upper layers are traversed greedily with a candidate set of one — fast, sloppy, good enough, because all they must do is deliver a starting node in roughly the right region. Layer 0 runs the full candidate-set search with your breadth parameter, and that is where recall is determined. The upper layers do not improve recall; they reduce the cost of arriving.

The skip-list analogy, and where it breaks

The construction is deliberately modelled on a skip list: a sorted linked list with sparse express lanes above it, giving logarithmic search instead of linear. The layer sampling is the same geometric distribution, and the top-down descent is the same procedure. The analogy is genuinely useful.

It is also weaker than it looks, in a way worth knowing.

A skip list has a total order; a vector space doesn’t. In a skip list, “too far” is detectable — you compare with the next element and step down when you would overshoot. The descent is exact: the search provably lands in the correct interval. In a proximity graph there is no ordering and no overshoot test. The greedy descent at each layer stops at a local minimum of that layer, which is only approximately the right region, and there is no way to verify it.

So errors at the top propagate down. If the layer-2 descent stops in the wrong neighbourhood, layer 1 starts from there and greedy descent — which only moves closer — is unlikely to recover. The bottom-layer search with a wide candidate set can rescue a moderate mistake, but not a large one. This is one concrete source of the recall a graph index loses that no amount of breadth recovers: the search never got near the right region to begin with.

The logarithmic claim is therefore softer than the skip list’s. For a skip list, logarithmic search is a theorem. For a hierarchical proximity graph, “the number of hops grows roughly logarithmically with collection size” is an empirical regularity that holds well on real data, resting on assumptions about distribution and on the graph being well constructed. It is not proven, and it degrades as the intrinsic dimensionality rises.

The parameters the hierarchy introduces

The level probability p. How aggressively the layers thin out. Implementations typically derive it from the connectivity setting rather than exposing it, using 1/ln(M), which makes the expected number of nodes at each layer fall by a factor comparable to the node degree. The reasoning is a balance: layers should thin fast enough that there are few of them, and slowly enough that each layer’s graph is dense enough to navigate. Too aggressive and an upper layer is a sparse scatter of nodes whose greedy descent is nearly random; too gentle and you have many layers, each adding descent cost that buys little.

Connectivity at layer 0 versus above. Layer 0 holds every vector and dominates memory, so its degree budget is the expensive one. Upper layers have few nodes, so their edges are nearly free — which is why implementations commonly allow layer 0 twice the degree of the layers above. It costs almost nothing to be generous up there.

Nothing at query time. This is the practical headline: the hierarchy exposes no runtime knob. Search breadth is a layer-0 parameter. The layers are structure, fixed at build time, and they affect how long you spend getting to layer 0 rather than what you find when you arrive.

When the hierarchy earns its cost, and when it doesn’t

The honest summary is that layers optimise the approach phase, so their value scales with how expensive approaching is.

Large collections, memory-resident: worth it. The approach cost grows with collection extent while the neighbourhood work does not, so the fraction of a query spent travelling grows, and the hierarchy removes it.

Small collections: barely matters. If the flat graph can be crossed in a handful of hops, there is almost nothing to save, and the layers add insertion complexity and a little memory for no return.

Disk-resident designs often skip it deliberately. When each hop is a storage read rather than a memory access, the calculus changes: what matters is the total number of reads, not the number of hops, and several layers of pointer-chasing across a device is worse than a single well-laid-out flat graph with a good entry point. Some large-scale designs use a flat graph with a carefully chosen starting node — a medoid, the most central vector — precisely because a good entry point captures much of what the hierarchy was providing, without the extra structure. That is a strong hint about what the layers really are: a mechanism for choosing a good entry point, generalised.

Under heavy filtering, the layers can work against you. If the query has a selective predicate, the upper layers contain a random sample of the collection, and the odds that any sampled node satisfies the predicate fall with the sample rate. The descent routes you towards the query’s region regardless of the filter, and the filtered subset may be somewhere else entirely.

The framing worth keeping: a hierarchical graph is a flat graph plus an accelerator for getting to the right part of it. Recall comes from layer 0, its edges, and the breadth you give it. The layers only buy time — and knowing that tells you which parameter to reach for when it is recall you’re missing rather than latency.

graph-indextheory