You have an IVF index over 10M 768-dim vectors, with nlist = 4096. You measure recall@10 and average query latency while sweeping nprobe across {1, 4, 16, 32, 50}. Predict the qualitative shape of both curves.Recall climbs steeply then plateaus near ~0.95 by nprobe ~32; latency rises linearly. Pick the smallest nprobe that hits your recall SLO; everything past that is wasted CPU.
An IVF index is like a library where every book has been presorted into one of 4096 themed rooms. When you walk in with a query, you don't search every room; you only open the few rooms whose theme is closest to what you want. **nprobe** is how many rooms you open. Open 1 room: you might miss the book if it ended up in a neighboring room. Open 16 rooms: you almost always find what you want. Open 50 rooms: you waste a lot of time walking through rooms whose contents you didn't need. The catch is that walking each new room takes a fixed amount of time (the room is a fixed size), but the chance of finding new matches drops off fast after the first few rooms. So time goes up in a straight line and accuracy goes up in a curve that flattens out.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
Concept explanation~2 min read
Everything you need to truly understand this topic: intuition, mechanics, step by step explanation, code, formulas, and worked example. Click to expand.
IVF tuning is one of those production tasks where the math is not deep but the intuition is load bearing. If a candidate cannot sketch the two curves on a whiteboard, they have never actually tuned an IVF index. The interview is testing whether they have moved from "I read about ANN" to "I have run a recall sweep and picked an operating point."
How IVF spends its query budget
IVF's query cost has two pieces. First, the centroid scan: compute the distance from the query to each of nlist centroids and sort to find the top nprobe. This is nlist distance ops regardless of nprobe. For nlist=4096, that is 4096 dot products per query, which is fast but not free.
Second, the partition scan: for each of the nprobe selected partitions, compute the distance from the query to every vector inside. If the partitions are balanced (which k-means roughly guarantees), each holds about N / nlist vectors. So the partition-scan cost scales linearly with nprobe.
For N=10e6 and nlist=4096, each partition holds ~2440 vectors. nprobe=16 scans ~39k vectors total; nprobe=50 scans ~122k. Compared to the 4096 centroid distances, the partition scan dominates once nprobe exceeds 2 or 3.
Situations where this technique stops working.
2–4 min · Everything important, quickly.
| nprobe | Recall@10 (typical) | Latency multiple |
|---|---|---|
| 1 | 0.50-0.65 | 1x |
| 4 | ~0.80 | ~4x |
| 16 | 0.90-0.93 | ~16x |
| 32 | 0.94-0.96 | ~32x |
| 50 | 0.95-0.97 | ~50x |
Real products, models, and research that use this idea.
- Faiss IndexIVFFlat and IndexIVFPQ both expose nprobe as a runtime parameter; tuning sweeps are the canonical first step in any Faiss deployment.
- Milvus exposes nprobe per query for IVF-family indexes; production deployments at LinkedIn and Salesforce pin it after ground-truth sweeps.
What an interviewer would ask next. Try answering before peeking at the approach.
QHow would you pick nlist for a new corpus?
Rule of thumb: nlist ~ sqrt(N) so partitions hold ~sqrt(N) vectors. For N=10M, nlist=4096 lands at ~2440 vectors per partition, which is the SIMD sweet spot.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Red flags & common mistakes
The phrases that signal junior thinking. Click to expand.
Pushing nprobe higher and higher in pursuit of recall without noticing that the curve has plateaued; you pay linear latency for sub-percent recall gains.
60 second bullets to scan on the way to the call.
Recall@10 curve is concave; latency curve is approximately linear
Per-partition scan cost is ~N/nlist distance computations
Primary sources. Browse if you want the original framing.
Same topic, related formats. Practice these next.