R3.4 · LESSON 4 OF 6

HNSW layers

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

THE IDEA

HNSW layers

HNSW stacks graphs in layers. Each node gets a top layer at random so that about 1/M of the nodes reach layer 1, 1/M² reach layer 2, and so on. Search starts at the sparse top, makes long hops, drops a layer at a time, and finishes with a detailed beam search of width efSearch on the dense bottom layer. Build parameters (such as M) affect connectivity and memory; efSearch affects search breadth and latency.

M (connectivity)16nodes1,000,000

layer ≥	chance for a node	expected nodes
0	1	1000000
1	0.0625	62500
2	0.003906	3906.25
3	0.000244	244.14

upper layers are sparse, so a search can take long hops there, then refine on the dense bottom layer small example (query x = 10, entry node 0, ef = 1): bottom layer alone ends on node 1 (stuck) with a sparse upper layer 0 → 3 → 4 the bottom search starts at node 4 and finds the nearest node ef (efSearch) is the width of the bottom-layer exploration, not the number of results k

How many nodes reach each layer? Then see why a sparse layer helps.

Predict first. Is efSearch the same setting as the number of returned results?

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

Compute layer populations by hand, then write level assignment and a multi-layer search.

M (connectivity)16nodes1,000,000

layer ≥	chance for a node	expected nodes
0	1	1000000
1	0.0625	62500
2	0.003906	3906.25
3	0.000244	244.14

chance of layer ≥ 1 for M = 16 nodes at layer ≥ 1 of 10⁶ nodes at layer ≥ 2 efSearch = results returned? (yes/no)

To do: HNSW draws each node's top layer from a geometric-like distribution: the chance of reaching layer 1 or higher is 1/M. With M = 16, that probability (4 decimals)?
To do: Out of 1,000,000 nodes, about how many appear on layer 1 or higher?
To do: On layer 2 or higher (10⁶ / 16², two decimals)?
To do: efSearch is the same setting as the number of results returned. Type yes or no

Part 2. Do it in code

level_for(u, M): the top layer of a node given a uniform random number u in (0, 1): floor(−ln(u) / ln(M)). u outside (0, 1) raises ValueError.
expected_at_least(n, M, layer): the expected number of nodes on that layer or above: n / M**layer.
greedy_layer(graph, pos, q, entry): move to a strictly closer neighbour until none is closer; return the final node. (Provided: beam_search below does the base-layer search.)
search_layers(layers, pos, q, entry, ef, k): layers[0] is the base graph with every node, higher layers are sparser. Descend from the top layer to layer 1 with greedy_layer, passing the result as the entry of the next layer down, then run beam_search on layer 0 with ef = max(ef, k) and return the first k ids.

import math

def beam_search(graph, pos, q, entry, ef):
    d = lambda i: abs(pos[i] - q)
    visited = {entry}
    cand = [(d(entry), entry)]
    best = [(d(entry), entry)]
    while cand:
        cand.sort()
        dc, c = cand.pop(0)
        best.sort()
        if dc > best[-1][0] and len(best) >= ef:
            break
        for nb in graph[c]:
            if nb in visited:
                continue
            visited.add(nb)
            dn = d(nb)
            best.sort()
            if len(best) < ef or dn < best[-1][0]:
                cand.append((dn, nb))
                best.append((dn, nb))
                best.sort()
                best = best[:ef]
    return [i for _, i in sorted(best)]

def level_for(u, M):
    pass

def expected_at_least(n, M, layer):
    pass

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

def search_layers(layers, pos, q, entry, ef, k):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Is efSearch the same setting as the number of returned results?

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.