Nearest Neighbour

How graph indexes search

The default index in most vector databases is a graph. Understanding how it walks that graph explains nearly every parameter it exposes and most of the ways it disappoints you.

The naive approach

You have ten million vectors and a query. Which is closest?

Compare the query against all ten million and keep the best. This is exact, trivially correct, and called a flat or brute-force index.

How it fails: the work is linear in the collection size. Ten million vectors at 768 dimensions is ten million dot products of 768 terms each per query. It’s also memory-bandwidth-bound rather than compute-bound, so it doesn’t parallelise as well as the arithmetic suggests.

It’s genuinely fine up to some scale — often further than people assume, and it has the useful property of perfect recall. But it doesn’t survive growth, and at a hundred million vectors it’s hopeless.

We need to avoid looking at most of the collection. To do that we need some structure saying where to look.

The idea: neighbours know their neighbours

Suppose that for every vector, you precomputed a short list of other vectors near it, and stored those as links. Now you have a graph: vectors are nodes, “is near” is an edge.

Searching becomes navigation. Start anywhere. Look at your current node’s neighbours. Move to whichever is closest to the query. Repeat until no neighbour is closer than where you are.

greedy_search(query, entry):
    current ← entry
    loop:
        best_neighbour ← argmin over neighbours(current) of d(query, n)
        if d(query, best_neighbour) ≥ d(query, current):
            return current
        current ← best_neighbour

This is greedy descent, and it works remarkably well. Each hop moves closer to the query, and you touch a tiny fraction of the collection.

How the naive graph fails

Two problems, and the fixes for them are the whole design.

Problem 1: local minima. Greedy descent stops when no neighbour is closer. That doesn’t mean you’ve found the nearest vector — it means you’ve found a node whose immediate neighbourhood is worse than it is. You can be stuck on a small hill on the wrong side of the space with the true answer far away, unreachable because every step toward it goes uphill first.

Problem 2: long-range travel is slow. If every edge connects genuinely nearby points, crossing the space takes many small hops. Starting far from the query means a long walk.

Fix 1: search with a candidate set, not a single point

Instead of tracking one current node, keep a priority queue of the best candidates found so far and expand them in order. Don’t stop at the first dead end — keep expanding until the queue holds nothing promising.

search(query, entry, breadth):
    candidates ← {entry}                  # to expand, nearest-first
    visited    ← {entry}
    best       ← {entry}                  # the `breadth` closest seen

    while candidates not empty:
        c ← closest candidate to query
        remove c from candidates
        if d(query, c) > d(query, worst of best) and |best| = breadth:
            break                          # nothing left can improve `best`
        for n in neighbours(c):
            if n not in visited:
                visited ← visited ∪ {n}
                if d(query, n) < d(query, worst of best) or |best| < breadth:
                    candidates ← candidates ∪ {n}
                    best ← closest `breadth` of (best ∪ {n})
    return closest k of best

The breadth parameter is the one engines expose as efSearch or similar. It’s the size of the working set — how many candidates you’re willing to keep alive.

This is the recall knob, and now you can see why. Larger breadth means you keep more paths open, so a local minimum on one path doesn’t end the search — another candidate in the queue leads somewhere better. It also means more distance computations. Recall up, latency up, in one parameter.

Note the stopping rule: you halt when the closest unexpanded candidate is farther than the worst of your current best set. At that point nothing remaining can improve the answer, because you’d have to travel away first. It’s a sound rule for the graph you have — it just can’t account for a better region you never found an edge into.

Fix 2: layers, for long-range travel

The second problem is that all edges are short, so crossing the space takes many hops.

The fix is a hierarchy. Build several graphs stacked on top of each other:

  • The bottom layer contains every vector, with short local edges.
  • Each layer above contains a random sample of the layer below — typically each node is promoted with some fixed small probability — with edges among that sparser set.

Because upper layers are sparse, their edges span long distances. A hop up there covers ground that would take dozens of hops at the bottom.

Search runs top-down:

  1. Start at the single entry point in the top layer.
  2. Greedily descend to the closest node in that layer.
  3. Drop to the next layer down, using that node as the entry point.
  4. Repeat until the bottom layer.
  5. At the bottom, run the full candidate-set search with your chosen breadth.

The upper layers are a coarse approach — they get you into the right neighbourhood cheaply. The bottom layer does the precise work. Because each layer is geometrically smaller than the one below, the descent costs a number of hops that grows roughly logarithmically with the collection size rather than linearly.

This structure — a hierarchy of proximity graphs with a geometric layer distribution — is HNSW, hierarchical navigable small world. The “small world” part refers to the property that mixing mostly-local edges with a few long-range ones gives short paths between any two nodes, the same property that makes social networks have short chains.

Construction, and the connectivity parameter

The graph is built incrementally. To insert a vector:

  1. Choose its top layer randomly, from a distribution that puts most nodes only at the bottom.
  2. Search from the top down to find its nearest neighbours at each layer it belongs to.
  3. Connect it to the closest M of them at each layer.
  4. Prune the neighbours’ edge lists if this pushed them over their limit.

M — the connectivity parameter — is the other big knob. It controls how many edges each node keeps.

  • Higher M: more paths out of every node, so fewer local minima and better recall at a given search breadth. Costs memory (directly — see the graph term in any sizing estimate) and makes every hop more expensive, since you evaluate more neighbours.
  • Lower M: leaner and faster per hop, more prone to getting stuck.

Step 4 deserves attention, because it’s where the good implementations differ from a naive one. If you simply keep each node’s M closest neighbours, you get clusters of mutually-close nodes with no edges leading out — exactly the local-minimum trap. Real implementations use a diversity heuristic when pruning: prefer a neighbour that opens a direction no existing neighbour covers, even if it’s slightly farther. That keeps the graph navigable rather than clumped.

There’s usually a separate, larger breadth parameter used during construction (efConstruction). It buys a better-quality graph at build time. It costs build duration and nothing at query time — which makes it the cheapest quality knob available, since you pay once.

What it gives up

It’s approximate, and there’s no guarantee. The search can miss the true nearest neighbour. The graph might have no edge into the right region from anywhere you looked, or your breadth might have been too small to keep the winning path alive. There’s no bound saying “at least this good” — the recall you get is an empirical property of your data, your parameters, and your build.

Deletes are awkward. Removing a node means its neighbours lose an edge, potentially disconnecting regions. Most implementations mark deleted nodes and skip them at query time rather than surgically repairing the graph, reclaiming space during compaction or a rebuild instead.

Filtered search is genuinely hard. The graph encodes proximity in the full space, not in your filtered subset. If you filter to 1% of the collection, the traversal spends most of its budget walking through nodes it must discard, and can fail to reach the matching ones at all. This is a structural weakness of graph indexes and the reason engines add filter-aware traversal strategies.

Memory is the constraint. The graph must be resident for random access at memory speed. Serve it from disk and each hop becomes a seek.

The knobs, summarised

Parameter Raise it for Cost
Search breadth (efSearch) Recall Query latency
Connectivity (M) Recall, fewer local minima Memory and per-hop cost
Build breadth (efConstruction) Graph quality Build time only

Search breadth is a runtime parameter, so it’s safe to tune against a query set and revert. The other two require a rebuild.

Graph indexes bet on memory: keep everything resident, keep rich connectivity, navigate quickly. Cluster indexes make the opposite bet, and quantization attacks the memory constraint directly.

graph-indextheory