R3.3 · LESSON 3 OF 6

Navigable graphs

Trace IVF and HNSW search and explain how candidate exploration trades latency for recall.

THE IDEA

Navigable graphs

A graph index connects each vector to some neighbours. To search, start at an entry node and move to whichever neighbour is closer to the query. Pure greedy moves can get stuck: a node whose neighbours are all farther than itself, though a better node exists elsewhere. The usual fix is a beam: keep the best ef candidates and keep exploring while any could improve the result.

Greedy step 1 of 2

at node 0 (x = 0, distance to query 10) neighbours: 1 (distance 6), 2 (distance 8) moves to node 1

beam width ef1

beam search with ef = 1 keeps nodes: 1 (closest first) true nearest node: 4 NOT found: stuck in a local optimum An edge to a close neighbour is not a guarantee of global correctness; exploring more candidates is how the graph search escapes.

Step through greedy search, then widen the beam.

Predict first. Is a neighbour edge itself proof of global nearest-neighbour correctness?

Chapter context

An approximate index organizes vectors so a query can avoid most comparisons. Clustering and graph navigation use different mechanisms to choose candidates, and their build settings influence later search quality.

TRY IT YOURSELF

Part 1. Do it hands-on

Trace a greedy search by hand, then implement greedy and beam search and find the smallest beam that works.

Greedy step 1 of 2

at node 0 (x = 0, distance to query 10) neighbours: 1 (distance 6), 2 (distance 8) moves to node 1

beam width ef1

greedy moves to node greedy stops at node true nearest node smallest ef that finds it

To do: Nodes sit at x = 0, 4, 2, 9, 10 (ids 0 to 4); edges 0–1, 0–2, 1–2, 2–3, 3–4. Query x = 10, start at node 0. Greedy search looks at node 0's neighbours 1 (x=4) and 2 (x=2). Which does it move to? Type the node id
To do: From node 1 no neighbour (0 or 2) is closer to the query. At which node does greedy search stop?
To do: Which node is the true nearest to the query x = 10?
To do: Beam search keeps the best ef candidates and keeps exploring. What is the smallest ef that reaches node 4 here?

Part 2. Do it in code

greedy_search(graph, pos, q, entry): from the entry node repeatedly move to the neighbour that is strictly closer to q than the current node (if several, the closest; ties: lower id). Stop when none is closer. Return the list of nodes visited (the path), starting with the entry.
beam_search(graph, pos, q, entry, ef): keep the ef best nodes found so far and a queue of candidates to expand (closest first). Pop the closest candidate; stop when it is farther than the worst kept node and ef nodes are kept; otherwise expand its unvisited neighbours, adding any that beat the worst kept node (or while fewer than ef are kept). Return the kept node ids, closest first (ties: lower id).
true_nearest(pos, q): the id of the closest node (ties: lower id).
smallest_ef(graph, pos, q, entry, max_ef): the smallest ef from 1 to max_ef for which beam_search returns the true nearest node first, or None.

def greedy_search(graph, pos, q, entry):
    pass

def beam_search(graph, pos, q, entry, ef):
    pass

def true_nearest(pos, q):
    pass

def smallest_ef(graph, pos, q, entry, max_ef):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Is a neighbor edge itself proof of global nearest-neighbor correctness?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

Under the simplifying assumption of equally sized IVF lists, N vectors, C cells and p probes produce approximately

N_{candidates}\approx Np/C.

Add coarse scoring, uneven list sizes and any reranking costs separately. HNSW has no equivalent universal fixed candidate-count formula.

Worked example

For 102,400 vectors evenly divided among 1024 cells, a cell has 100 vectors. Probing eight cells scans about 800 candidates, compared with 102,400 in a full scan. This excludes coarse-centroid comparisons and says nothing by itself about recall.

Reference code

The following example uses the Python standard library and does not call a remote service.

total,cells,probes=102400,1024,8
assert total/cells == 100
assert total*probes/cells == 800
assert total/(total*probes/cells) == 128

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

An average candidate count is not an actual worst-case bound. More graph edges consume memory. Approximate search settings must be evaluated against the current corpus and metric.