The neighbour list you want isn't the nearest one

A graph index is a set of edges, and the search is only as good as the edges. The obvious way to choose them — link each vector to the vectors nearest it — produces a graph that looks correct, contains all the right information, and traps searches in local minima at a spectacular rate. The repair is a small change to one step of construction, and it is the difference between a working index and a broken one.

The naive approach

Build the graph the way the name suggests. For every vector, find its M nearest neighbours and store them as its edges.

build_knn_graph(vectors, M):
    for v in vectors:
        edges[v] ← the M nearest other vectors to v

This is the k-nearest-neighbour graph, it is the honest first idea, and every edge in it is true: each one connects two genuinely close points. Search it greedily — move to whichever neighbour is closest to the query, stop when none is closer — and on small or low-dimensional data it works.

How it fails: consider a collection with a tight cluster in it, say a few hundred near-duplicate documents. Every member’s M nearest neighbours are other members of that cluster, because they are genuinely the nearest. So every edge from every member points back into the cluster. The cluster has no edges leaving it.

A greedy search that wanders in stops there. Not because the cluster is close to the query — it may be far — but because from any node inside it, every neighbour is another cluster member, and none of them is closer to the query than where you already stand. The stopping rule fires, the search returns, and it has no way of knowing there is a better region it never had a path to.

This is not a pathological case constructed for the argument. Real embedding collections are full of tight clusters — templated documents, repeated boilerplate, chunks of one long source — and each one is a trap. Worse, hubness compounds it: in high dimensions a few central vectors are among the nearest neighbours of very many points, so those points spend their limited edge budget linking to the same handful of hubs and have nothing left for local structure or for the vectors on their far side.

The naive graph’s problem, stated in one line: it optimises the wrong quantity. It makes every edge as short as possible. What a search needs is edges that go somewhere — a set of directions out of each node covering the space around it. Shortness and coverage are different objectives, and maximising the first actively destroys the second.

The idea: cover directions, not just distance

Think about what greedy descent needs from a node’s edge list. Standing at node v, the query is somewhere — you don’t know where in advance, and it could be in any direction. To make progress you need at least one edge pointing roughly the way the query lies. So the useful edge list is one whose directions span the space around v: a few edges into each region surrounding it, so that whatever direction the query is in, some neighbour lies that way.

An edge into a direction already covered by a shorter edge adds nothing. If a is a neighbour of v, and b is in almost the same direction but slightly farther, then any search that would want to move towards b can move to a first and continue from there. b’s edge is redundant. Whereas a slightly more distant neighbour in an uncovered direction is the only way out of v towards that whole region, and without it the region is unreachable from v.

That is the entire insight. Given a limited edge budget, spend it on coverage rather than on shortness.

The pruning rule

The mechanism is a filter applied to candidate neighbours, and it is short:

select_neighbours(v, candidates, M):
    sort candidates by distance to v, nearest first
    selected ← ∅
    for c in candidates:
        if |selected| = M: break
        keep ← true
        for s in selected:
            if d(c, s) < d(c, v):        # the test
                keep ← false             # s is closer to c than v is: same direction, already covered
                break
        if keep: selected ← selected ∪ {c}
    return selected

The test is the whole thing, and it deserves a sentence of geometry. Candidate c is rejected when some already-selected neighbour s is closer to c than v is. Read that as: c is nearer to something we already link to than it is to us, so s sits between v and c. A search wanting to reach c can go via s. The edge to c would duplicate a path we already have, so we spend the budget elsewhere.

Walk it on the cluster example. The first candidate — the nearest cluster member — is always kept, since nothing is selected yet. The second cluster member is examined: is it closer to the first selected member than to v? Inside a tight cluster, yes, comfortably. Rejected. The third, likewise. The rule accepts one representative of the cluster and rejects the rest, and the budget freed up goes to candidates in other directions — including distant ones, which are exactly the edges that let a search escape.

The graph this produces has a mixture of edge lengths: mostly short edges, plus some long ones reaching regions that nothing shorter covered. That mixture is what makes the graph navigable, and it is the “small world” property arriving as a consequence of the pruning rule rather than as a separate mechanism.

What it approximates

The rule is not arbitrary; it approximates a structure from classical geometry, and knowing which one explains why it works.

The ideal graph for greedy nearest-neighbour search is the Delaunay graph — connect two points if their Voronoi cells share a face. Its defining property is exactly what we want: on a Delaunay graph, greedy descent from any starting node reaches the true nearest neighbour of any query, always. No local minima, by construction.

Two reasons you cannot use it. Computing it requires the full Voronoi diagram, whose cost explodes with dimensionality. And in high dimensions it becomes nearly complete — almost every pair of cells shares a face — so node degree approaches N, and a graph where every node links to everything is a flat scan with extra steps.

So we approximate it, cheaply, with a bounded degree. The pruning test above is the test for the relative neighbourhood graph, a sparse subgraph of the Delaunay graph: keep the edge v–c only if no third point is closer to both of them than they are to each other. It keeps much of the navigability and has degree small enough to store. The M cap then truncates even that.

This is where the guarantee is lost, and it is worth being exact about it. Greedy search on a true Delaunay graph is provably correct. On a bounded-degree, greedily-built approximation of a sparse subgraph of it, nothing is provable. Local minima are possible, which is why the search needs a candidate set with search breadth rather than a single walker, and why the index has no accuracy guarantee at all.

How the candidates are found in the first place

One more piece: the pruning rule filters candidates, but where do candidates come from? Computing the true nearest neighbours of every vector is itself an all-pairs problem, which is what we were trying to avoid.

The answer is bootstrapping. Insert vectors one at a time, and to find a new vector’s candidates, search the graph you have so far — using the same search procedure queries use, with a separate and usually larger breadth parameter. Then prune the result and add the edges.

insert(v, M, build_breadth):
    candidates ← search(graph, query = v, breadth = build_breadth)
    edges[v]   ← select_neighbours(v, candidates, M)
    for n in edges[v]:
        edges[n] ← select_neighbours(n, edges[n] ∪ {v}, M)   # add the reverse edge, re-prune

Three things follow from this that explain behaviours you can observe.

Build breadth is the cheapest quality knob available. It determines how good the candidate lists are, so it determines how good the edges are, and it costs build time only — nothing at query time. A graph built with a wider search has a better recall-latency curve at every operating point, permanently, and you pay once.

Reverse edges and re-pruning matter more than they look. Adding v to its neighbours’ lists is what gives new nodes incoming edges — without it, freshly inserted vectors are reachable from nothing. And when that overflows a neighbour’s budget, the same diversified rule must be applied, not a “drop the farthest” shortcut: dropping the farthest is precisely how you lose the long edges the graph depends on.

The graph depends on insertion order. Early vectors are connected using a nearly empty graph, so their candidate lists are poor. Later vectors get better candidates. The structure is not a deterministic function of the collection, which is one reason two builds of the same data give slightly different results, and why a graph built incrementally over a long period is not identical to one built in bulk from the same final contents.