R3.2 · LESSON 2 OF 6

Probing and candidate counts

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

THE IDEA

Probing and candidate counts

nprobe sets how many lists are visited. A higher value scans more candidates and usually raises recall, up to the exact result when every list is probed. But cost depends on the sizes of the probed lists, not on their count: if lists are skewed, two big lists can hold most of the corpus.

k (neighbours wanted)2

nprobe	candidates scanned	fraction of corpus	returned ids	recall@2
1	3	0.3	3, 4	0.5
2	6	0.6	2, 3	1
3	10	1	2, 3	1

True top-2 for q = 5.1: ids 2, 3. More probes means more work and (usually) more recall.

list sizes: 250, 250, 250, 250 probing the two nearest lists (order 0 then 3) scans 500 of 1000 vectors the same nprobe costs different work depending on which lists are probed

Same query, increasing nprobe; then compare even and skewed lists.

Predict first. Does an equal number of lists imply equal actual list sizes?

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

Count candidates and recall by hand, then write the probe-count helpers.

k (neighbours wanted)2

nprobe	candidates scanned	fraction of corpus	returned ids	recall@2
1	3	0.3	3, 4	0.5
2	6	0.6	2, 3	1
3	10	1	2, 3	1

True top-2 for q = 5.1: ids 2, 3. More probes means more work and (usually) more recall.

list sizes: 250, 250, 250, 250 probing the two nearest lists (order 0 then 3) scans 500 of 1000 vectors the same nprobe costs different work depending on which lists are probed

scanned, nprobe 1 scanned, nprobe 2 fraction of the 10 points recall@2 with nprobe 1

To do: Same toy index, query 5.1. Candidates scanned with nprobe = 1 (the lists, nearest centroid first, are 10, then 0, then 20)?
To do: With nprobe = 2?
To do: That is what fraction of the 10 points?
To do: recall@2 for nprobe = 1 (the true top-2 are ids 2 and 3; nprobe = 1 returns ids 3 and 4)?

Part 2. Do it in code

probe_order(q, centroids): centroid indices nearest first (ties: lower index).
candidates_scanned(lists, order, nprobe): the number of vectors in the first nprobe lists of the order.
scan_fraction(lists, order, nprobe): candidates scanned divided by the total number of vectors.
recall_at_nprobe(q, xs, centroids, lists, k, nprobe): the fraction of the exact top-k ids that the IVF search finds.
smallest_nprobe(q, xs, centroids, lists, k, target): the smallest nprobe whose recall is at least target, or None if even probing all lists falls short.

def probe_order(q, centroids):
    pass

def candidates_scanned(lists, order, nprobe):
    pass

def scan_fraction(lists, order, nprobe):
    pass

def recall_at_nprobe(q, xs, centroids, lists, k, nprobe):
    pass

def smallest_nprobe(q, xs, centroids, lists, k, target):
    pass

Ctrl/⌘ + Enter runs it

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

CHECK YOUR UNDERSTANDING

Does equal list count imply equal actual list sizes?

ANoBYes

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.