ANN Algorithms

The index that walked past the answer

You run a duplicate-question finder over 522,931 Quora questions, each embedded with all-MiniLM-L6-v2 (384 dimensions, unit length). Brute-force search is exact, but on one core it takes a median 31.5 ms per query, and the corpus is about to grow tenfold. So you build an HNSW index with hnswlib's default settings, and queries drop to about 0.13 ms. Then a user types this:

How can I remove humidity in laptop?

No error and no warning: ten results, every one of them about losing weight. The near-perfect duplicate is in the index. The search never reached it.

The cause is one number. hnswlib searches with ef = 10 unless you call set_ef, and ef is not saved in the index file, so even a team that tuned it in a notebook can ship 10 by accident. Across all 10,000 test queries of this dataset, 310 queries lost a labeled duplicate that brute force had in its top 10. At ef = 64 it was 30 queries, for about 0.44 ms per query.

That is the deal every approximate nearest neighbor (ANN) index offers. It skips almost all of the corpus, which is why it is fast, and occasionally the part it skipped held the answer. This lesson is about making that deal on purpose: which structure to build, which knob trades what, and how to measure what you gave up.

Everything here runs on one real dataset, so the numbers are comparable from section to section. What a vector database adds around the index (storage, updates, filtering, sharding) is in Vector Database Architecture. Choosing a distance metric is in Cosine Similarity & Distance Metrics.

The test bench

The setup below is used for every table in this lesson. It downloads the Quora set from the BEIR benchmark: 522,931 questions, plus 10,000 test questions with their labeled duplicates. The script embeds everything once and saves the vectors.

# embed_quora.py: run once, as its own script (see the warning below)
import csv, io, json, os, urllib.request, zipfile
import numpy as np
from sentence_transformers import SentenceTransformer

URL = "https://public.ukp.informatik.tu-darmstadt.de/thakur/BEIR/datasets/quora.zip"
if not os.path.exists("quora"):
    zipfile.ZipFile(io.BytesIO(urllib.request.urlopen(URL).read())).extractall(".")

texts = [json.loads(line)["text"] for line in open("quora/corpus.jsonl")]
queries = {q["_id"]: q["text"] for q in map(json.loads, open("quora/queries.jsonl"))}
test_ids = sorted({row["query-id"] for row in
                   csv.DictReader(open("quora/qrels/test.tsv"), delimiter="\t")})

model = SentenceTransformer("sentence-transformers/all-MiniLM-L6-v2")
X = model.encode(texts, batch_size=256)                          # unit-length, 384-d
Q = model.encode([queries[i] for i in test_ids], batch_size=256)
np.save("X.npy", X)
np.save("Q.npy", Q)
print(X.shape, Q.shape, X.dtype, f"{X.nbytes / 1e6:.0f} MB")
# (522931, 384) (10000, 384) float32 803 MB

Encoding took a few minutes on an M2 Max GPU; on a laptop CPU, expect much longer. To start smaller, embed only the first 100,000 questions: the ANN-recall experiments work unchanged, but skip the IR-recall block in Move 2 (it maps labels onto the whole corpus), and expect numbers that differ from the tables here.

⚠️ Keep the embedding step in its own process. On macOS, importing PyTorch (through sentence-transformers) and then running a multi-threaded FAISS search in the same Python process crashed with a segmentation fault in our environment. Both libraries ship their own OpenMP runtime. Embed in one script, search in another.

Measurements in this lesson come from one Apple M2 Max shared with other heavy jobs. Recall numbers are stable. Latencies are not: medians moved by up to about 2× between identical runs (an idle re-run of the exact scan below took 16 ms instead of 31.5 ms), and p95 moved even more. So the latency columns show medians only. Compare rows within a table, and measure p95 on your own hardware.

Two recalls: know which one you are measuring

Two different numbers are both called "recall", and mixing them up causes many of the bad decisions in this area.

• ANN recall@k = |ANN top-k ∩ exact top-k| / k. How faithfully the index reproduces brute force. It needs no human labels, only an exact search to compare with.
• IR (retrieval) recall@k = relevant items in the top k / all relevant items. Whether users find what they need. It needs labeled data. The Retrieval Metrics lesson covers it in depth.

On the test bench, over all 10,000 labeled test queries (the code that produces this table runs in Move 2, once the index exists):

Read it row by row. Brute force misses about 5% of the labeled duplicates, and almost all of that is the embedding model's fault (76 queries have more than ten labeled duplicates, so even a perfect top 10 would score 0.997). No index setting can fix it. At ef = 10, the approximation throws away a further 2.6 points of IR recall. At ef = 64, it keeps almost everything the model could find. So ANN recall tells you how much of the model's quality the index preserves. It never tells you whether the model was any good.

Predict: brute force returns ids [7, 3, 9, 1, 4] and the index returns [3, 7, 4, 8, 2]. What is ANN recall@5? Does the swapped order of 7 and 3 cost anything?

Ground truth and a stopwatch

Every experiment below compares against the exact top-k for 1,000 held-out test queries. Build that once:

import csv, json, time
import numpy as np
import faiss

texts = [json.loads(line)["text"] for line in open("quora/corpus.jsonl")]
row_of = {json.loads(line)["_id"]: i for i, line in enumerate(open("quora/corpus.jsonl"))}
queries = {q["_id"]: q["text"] for q in map(json.loads, open("quora/queries.jsonl"))}
qrels = {}                                   # query id -> rows of its labeled duplicates
for r in csv.DictReader(open("quora/qrels/test.tsv"), delimiter="\t"):
    qrels.setdefault(r["query-id"], set()).add(row_of[r["corpus-id"]])
test_ids = sorted(qrels)
X, Q = np.load("X.npy"), np.load("Q.npy")

rng = np.random.default_rng(0)
Qs = Q[rng.choice(len(Q), 1000, replace=False)]   # 1,000 held-out test queries
flat = faiss.IndexFlatIP(X.shape[1])     # exact search; inner product = cosine here
flat.add(X)
_, gt = flat.search(Qs, 100)             # ground truth: exact top-100 per query

def ann_recall(found, truth, k=10):
    """ANN recall@k: |approximate top-k ∩ exact top-k| / k, averaged over queries."""
    return np.mean([len(set(map(int, f[:k])) & set(map(int, t[:k]))) / k
                    for f, t in zip(found, truth)])

def latency_ms(search_one, n=200):
    """p50 and p95 single-query latency over the first n held-out queries."""
    times = []
    for q in Qs[:n]:
        t = time.perf_counter()
        search_one(q)
        times.append((time.perf_counter() - t) * 1000)
    return np.percentile(times, 50), np.percentile(times, 95)

faiss.omp_set_num_threads(1)             # one query, one core
p50, _ = latency_ms(lambda q: flat.search(q[None], 10))
print(f"exact, one query at a time: p50 {p50:.1f} ms")
t = time.perf_counter()
flat.search(Qs, 10)
print(f"exact, 1,000 queries as one batch: {time.perf_counter() - t:.2f} ms per query")
# exact, one query at a time: p50 31.5 ms
# exact, 1,000 queries as one batch: 1.20 ms per query

The queries are held out: none of them is an indexed record (13 of the 10,000 have exact-text twins in the corpus, because Quora contains duplicate questions). Move 6 measures how much holding out changes on this data, and why it matters more in RAG. The vectors are unit length, so inner product, cosine and L2 all rank the same way.

Move 1: Price the exact answer first

Symptom: p95 creeps up with every batch of new documents, and it scales with the corpus.

Exact k-NN computes one similarity per stored vector: n·dim multiply-adds, then a top-k selection. On the test bench that is 522,931 × 384 ≈ 201 million multiply-adds per query, and it streams all 803 MB of float32 vectors through the CPU.

The two measurements above tell different stories:

• Latency, one query at a time: a median of 31.5 ms on one core. This is what a user request sees.
• Throughput, 1,000 queries in one batch: 1.20 s for the batch, so about 830 queries per second on the same single core. A batch turns 1,000 vector-matrix products into one matrix-matrix product, so every vector loaded from memory serves 1,000 queries. That is throughput, not latency: every query in the batch waited the full 1.2 s for its answer.

So brute force is excellent for offline work: computing ground truth, deduplicating a corpus, or nightly jobs. It hurts in the online path, where requests arrive one at a time and the tail counts.

The cost is linear in n·dim. Ten million 768-d chunks is 10,000,000 × 768 / (522,931 × 384) ≈ 38× the work of the test bench: over a second per query on one core at the rate measured here. Whether your own corpus has crossed that line is a question for Vector Database Architecture, which computes the cut-off. This lesson starts where brute force has already lost.

Why not an exact index?

The classic exact structures, such as k-d trees, split space along one coordinate at a time and skip every region that provably cannot contain a closer point. In 2 or 3 dimensions that pruning removes almost everything. In hundreds of dimensions the ball around the query crosses so many splitting planes that the search ends up visiting most of the leaves anyway, and you pay tree overhead for a linear scan.

You can see the underlying problem in the similarity numbers. For 200 queries, compare the best match with the median match:

In random high-dimensional data every point is almost equally far from every other, so the "nearest" neighbor is barely nearer than a typical one. This is the concentration of distances behind the phrase "curse of dimensionality". Real embeddings are different: similar questions really do sit close together, far above the crowd. ANN indexes exploit that structure. They give up the guarantee and bet that neighbors of neighbors are likely to be neighbors. On real embeddings the bet pays off. On random vectors it fails, which is why you never benchmark on them (Move 6).

Your turn: a team has 4 million chunks at 1,024 dimensions, 20 queries per second at peak, and a 50 ms p95 budget for retrieval. Using the single-core scan rate measured above (803 MB in about 31.5 ms), is brute force viable?

Move 2: Walk a graph (HNSW)

Symptom: the vectors fit in RAM, but a full scan per query does not fit the latency budget.

A graph index links every vector to a few nearby vectors when it is built. A query then walks the links: start somewhere, move to whichever neighbor is closer to the query, and repeat. Each step computes only a handful of distances, so the walk touches a tiny fraction of the corpus. It works when "close to my neighbor" usually means "close to me", and on real embeddings it usually does.

A walk that gets stuck

Here is the walk on twelve points in 2-D, small enough to follow by hand. Each point is linked to its two nearest neighbors, and links work in both directions. The query sits at (8, 6), and its true nearest neighbor is J, one unit away. The walk starts at D in the bottom-left corner.

  y
  9  .  .  .  E  .  .  K  .  .  G
  8  .  .  .  .  .  .  .  .  .  C
  7  .  .  .  .  .  .  .  .  .  .
  6  .  .  .  .  .  .  .  .  Q  .      Q = query (8, 6)
  5  .  .  .  .  .  .  .  .  J  .
  4  .  .  .  H  .  .  .  .  .  .
  3  L  B  .  .  .  .  .  A  I  .
  2  D  .  .  .  F  .  .  .  .  .
     0  1  2  3  4  5  6  7  8  9   x

links: D-B D-L B-L B-H H-E H-F F-A A-I A-J I-J J-C C-G G-K K-E

The search keeps two lists: candidates (places it may still expand) and results (the best ef points seen so far). This is the layer search of HNSW, written out in plain Python:

import heapq, math

points = {"A": (7, 3), "B": (1, 3), "C": (9, 8), "D": (0, 2), "E": (3, 9), "F": (4, 2),
          "G": (9, 9), "H": (3, 4), "I": (8, 3), "J": (8, 5), "K": (6, 9), "L": (0, 3)}
graph = {"A": "FIJ", "B": "DHL", "C": "GJ", "D": "BL", "E": "HK", "F": "AH",
         "G": "CK", "H": "BEF", "I": "AJ", "J": "ACI", "K": "EG", "L": "BD"}

def search_layer(query, entry, ef):
    dist = lambda p: math.dist(points[p], query)
    visited = {entry}
    candidates = [(dist(entry), entry)]      # min-heap: nearest unexpanded first
    results = [(-dist(entry), entry)]        # max-heap: worst kept result on top
    while candidates:
        d, node = heapq.heappop(candidates)
        if d > -results[0][0]:               # nearest candidate is worse than the
            break                            # worst result we keep: stop
        for nb in graph[node]:
            if nb in visited:
                continue
            visited.add(nb)
            d_nb = dist(nb)
            if len(results) < ef or d_nb < -results[0][0]:
                heapq.heappush(candidates, (d_nb, nb))
                heapq.heappush(results, (-d_nb, nb))
                if len(results) > ef:
                    heapq.heappop(results)   # forget the worst
        print(f"  expanded {node} (d={d:.2f})  keep {sorted((round(-x, 2), p) for x, p in results)}")
    best = min((-x, p) for x, p in results)
    return best[1], round(best[0], 2), len(visited)

query = (8, 6)
for ef in (1, 3):
    print(f"ef={ef}")
    print("  result:", search_layer(query, entry="D", ef=ef))

Predict first: with ef = 1 the walk is purely greedy. Where does it stop?

ef=1
  expanded D (d=8.94)  keep [(7.62, 'B')]
  expanded B (d=7.62)  keep [(5.39, 'H')]
  expanded H (d=5.39)  keep [(5.39, 'H')]
  result: ('H', 5.39, 6)

Now give it a beam of three:

ef=3
  expanded D (d=8.94)  keep [(7.62, 'B'), (8.54, 'L'), (8.94, 'D')]
  expanded B (d=7.62)  keep [(5.39, 'H'), (7.62, 'B'), (8.54, 'L')]
  expanded H (d=5.39)  keep [(5.39, 'H'), (5.66, 'F'), (5.83, 'E')]
  expanded F (d=5.66)  keep [(3.16, 'A'), (5.39, 'H'), (5.66, 'F')]
  expanded A (d=3.16)  keep [(1.0, 'J'), (3.0, 'I'), (3.16, 'A')]
  expanded J (d=1.00)  keep [(1.0, 'J'), (2.24, 'C'), (3.0, 'I')]
  expanded C (d=2.24)  keep [(1.0, 'J'), (2.24, 'C'), (3.0, 'I')]
  expanded I (d=3.00)  keep [(1.0, 'J'), (2.24, 'C'), (3.0, 'I')]
  result: ('J', 1.0, 11)

Why it works. With three slots, F survives as a runner-up after H is expanded, so the search expands it next and finds the way down to A and J. The walk stops only when the closest unexpanded candidate is farther away than the worst of the ef results it keeps. From then on, nothing left in the queue can improve the answer. A bigger ef keeps more runner-up paths alive. It costs more distance computations: the last number in each result counts the visited points, 6 for ef = 1 and 11 for ef = 3.

On twelve points, visiting 11 is no better than a brute-force scan of 12. The payoff comes at scale: on the 522,931-vector test bench, an HNSW search with a beam of 64 computes about 895 distances per query, 0.17% of the corpus (FAISS counts them; see the M table below).

Layers: express lanes on top

A single-layer graph has a problem at scale: from a random starting point, the walk takes many short hops to cross the space. HNSW (Hierarchical Navigable Small World, Malkov & Yashunin, IEEE TPAMI 2020) stacks sparser graphs on top of the full one.

When a vector is inserted, it draws a random top layer. It reaches layer 1 with probability 1/M, layer 2 with probability 1/M², and so on. Here is what that produced in a FAISS HNSW index with M = 16 over the test bench:

layer 5        1 vector     <- the entry point
layer 4       10 vectors
layer 3      109
layer 2    2,020
layer 1   32,787             (about n / 16)
layer 0  522,931             every vector, up to 2·M = 32 links each

A query enters at the top and walks greedily (a beam of 1) on each sparse layer. Because those layers hold few vectors, each hop covers a long distance. The best point found on one layer becomes the entry to the layer below. On layer 0, which holds everything, the search runs the beam search above with a beam of efSearch. The upper layers get the walk to the right neighborhood; layer 0 does the careful local work.

Insertion uses the same search. The new vector looks for its neighbors with a beam of efConstruction, keeps a few of them (at most M on each upper layer), and the neighbors link back to it. Layer 0 allows up to 2·M links per node: FAISS picks up to 2·M at insertion, while hnswlib picks M and lets later nodes' back-links fill the rest. Both reserve memory for all 2·M slots. The chosen neighbors are not simply the closest ones. A selection heuristic skips a candidate that is closer to an already-chosen neighbor than to the new vector. That spreads a vector's links in different directions instead of spending them all inside one tight cluster. The paper reports that the heuristic matters most at high recall and on clustered data.

Back to the failed query. At ef = 10, all ten results for "How can I remove humidity in laptop?" were weight-loss questions ("How can I reduce 3 kgs in 7 days?"), with cosines between 0.224 and 0.257. Quora holds a big, tight family of them: 1,227 questions match a simple weight-loss pattern, and their average pairwise cosine is 0.43, against 0.04 for random pairs. The walk ended inside that family. With only ten slots, every candidate it held was a family member whose links led mostly to other family members, none closer to the query, so the stop rule fired: the same local minimum as H, in 384 dimensions. At ef = 16, the saved index already found the 0.996 duplicate.

The three knobs

Here is the query knob on the test bench, with hnswlib's default build (M = 16, ef_construction = 200):

import hnswlib

hnsw = hnswlib.Index(space="cosine", dim=X.shape[1])
hnsw.init_index(max_elements=len(X), M=16, ef_construction=200)   # hnswlib's defaults
t = time.perf_counter()
hnsw.add_items(X, np.arange(len(X)))     # uses all cores
print(f"build {time.perf_counter() - t:.0f} s; default ef = {hnsw.ef}")

for ef in (10, 16, 32, 64, 128, 256):
    hnsw.set_ef(ef)
    found, _ = hnsw.knn_query(Qs, k=10, num_threads=1)
    p50, _ = latency_ms(lambda q: hnsw.knn_query(q, k=10, num_threads=1))
    print(f"ef={ef:3d}  recall@10={ann_recall(found, gt):.3f}  p50={p50:.2f} ms")

hnsw.save_index("quora_hnsw.bin")
reloaded = hnswlib.Index(space="cosine", dim=X.shape[1])
reloaded.load_index("quora_hnsw.bin")
print(f"ef before save: {hnsw.ef}, after load: {reloaded.ef}")
# build 201 s; default ef = 10
# ef= 10  recall@10=0.944  p50=0.13 ms
# ef= 16  recall@10=0.968  p50=0.17 ms
# ef= 32  recall@10=0.988  p50=0.27 ms
# ef= 64  recall@10=0.994  p50=0.44 ms
# ef=128  recall@10=0.997  p50=0.78 ms
# ef=256  recall@10=0.998  p50=1.46 ms
# ef before save: 256, after load: 10

Every row is the same index. Going from ef = 10 to ef = 64 bought 5.0 points of recall for about 3.4× the latency, and it still ran about 70× faster than the exact scan. Past ef = 128, the extra time buys almost nothing.

The last line is the trap from the opening: the value you set is gone after a reload.

Reproduce the opening failure

Now run the same index over all 10,000 labeled test queries, and print the query whose ANN #1 fell furthest below the exact #1:

relevant = [qrels[q] for q in test_ids]

def hits(found, k=10):
    """How many labeled duplicates each query has in its top k."""
    return np.array([len(rel & set(map(int, f[:k]))) for rel, f in zip(relevant, found)])

def ir_recall(found, k=10):
    """IR recall@k: share of each query's labeled duplicates in its top k, averaged."""
    return np.mean(hits(found, k) / np.array([len(rel) for rel in relevant]))

faiss.omp_set_num_threads(12)
exact_scores, exact_top = flat.search(Q, 10)          # all 10,000 test queries
print(f"exact:  IR recall@10 = {ir_recall(exact_top):.3f}")
for ef in (10, 64):
    hnsw.set_ef(ef)
    found, dist = hnsw.knn_query(Q, k=10)
    lost = (hits(found) < hits(exact_top)).sum()      # queries that lost a duplicate
    print(f"ef={ef:2d}:  IR recall@10 = {ir_recall(found):.3f}   "
          f"ANN recall@10 = {ann_recall(found, exact_top):.3f}   lost a duplicate: {lost}")
    if ef == 10:
        i = np.argmax(exact_scores[:, 0] - (1 - dist[:, 0]))   # biggest shortfall
        print("  query:", queries[test_ids[i]])
        print(f"  ANN #1   ({1 - dist[i, 0]:.3f}):", texts[found[i, 0]])
        print(f"  exact #1 ({exact_scores[i, 0]:.3f}):", texts[exact_top[i, 0]])
# exact:  IR recall@10 = 0.950
# ef=10:  IR recall@10 = 0.924   ANN recall@10 = 0.946   lost a duplicate: 310
#   query: How can I remove humidity in laptop?
#   ANN #1   (0.257): How can I reduce my weight from 80 kg to 65 kg in 1 month?
#   exact #1 (0.996): How can I remove humidity in a laptop?
# ef=64:  IR recall@10 = 0.948   ANN recall@10 = 0.995   lost a duplicate: 30

These are the numbers in the "Two recalls" table, and the printed query is the one from the opening. Your rebuilt graph will differ, because multi-threaded builds are not deterministic, so a different handful of queries will fail for you. At ef = 10, 43 of the 10,000 queries had a best ANN result below cosine 0.5 while brute force had one above 0.8.

Now the build knobs. This table uses FAISS's IndexHNSWFlat with efConstruction = 100, because FAISS counts the distance computations each query performs. That count is the same on any machine, unlike milliseconds:

Three things to read off it:

• A small M is not a recall ceiling. The M = 8 graph still reaches 0.991 at efSearch = 256. It just needs a wider beam, and so more distance computations, to get there. Raise efSearch before you schedule a rebuild.
• A bigger M buys cheaper queries at high recall. It costs link memory, and every insert does more work. Build times on our busy machine were too noisy to separate M = 16 from M = 32.
• The build is the slow part. It runs once per index, but it runs again after every model change, and the graph needs RAM while it grows.

The hnswlib authors' parameter guide suggests M between 12 and 48 for most data, and gives a check for efConstruction: measure recall for the M nearest neighbors (k = M) with ef = ef_construction. If it is below 0.9, a better build is possible.

Four traps with the query knob

• ef is not stored in the index. The hnswlib README says so, and the reload above shows it. Call set_ef after every load_index, with the value read from configuration.
• Defaults differ by library. hnswlib searches with ef = 10. FAISS IndexHNSWFlat uses efSearch = 16 and efConstruction = 40. pgvector's HNSW uses m = 16, ef_construction = 64 and hnsw.ef_search = 40 (README). Qdrant builds with m = 16, ef_construct = 100. None of these defaults was tuned on your data.
• ef below k. hnswlib quietly searches with the larger of ef and k: on the test bench, ef = 5 and ef = 50 gave identical results for k = 50. FAISS uses efSearch as given. With efSearch = 5 and k = 50, recall@50 fell to 0.541, and 3 of the 1,000 queries came back with fewer than 50 real ids (FAISS pads the rest with −1).
• set_ef changes the whole index. In hnswlib it is shared state, so two request tiers cannot use different values at the same time. FAISS takes a per-call faiss.SearchParametersHNSW(efSearch=...), and Qdrant takes hnsw_ef per request.

Memory: next to float32 vectors, the links are the small part

The FAISS index above used 1,680 bytes per vector at M = 16: 1,536 for the float32 vector (384 × 4), 128 for the layer-0 links (2·M = 32 ids of 4 bytes), and the rest for upper layers and bookkeeping. A working estimate is n × (dim × 4 + 2·M × 4) bytes. For 10 million 768-d vectors at M = 16, that is 30.72 GB of vectors plus 1.28 GB of links, about 32 GB. The links only become a large share when vectors are short: at 128 dimensions they add 25%.

So while the vectors are float32, lowering M barely shrinks an index of modern embeddings. Compressing the vectors (Move 4) is what moves the total, and once they are compressed, the balance flips: the links become the big part.

Deletes: tombstones, not holes

Deleting a node from a graph would cut the paths that run through it. So hnswlib's mark_deleted keeps the node in the graph as a stepping stone and only hides it from results. Here is what that did on the test bench (hnswlib, ef = 32, recall measured against an exact search over the surviving vectors):

Recall held up, because the search simply walks further to fill its ten slots. The costs are memory that never comes back and latency that grows with the dead weight. hnswlib can reuse deleted slots (allow_replace_deleted=True at init, then add_items(..., replace_deleted=True)). FAISS's HNSW index has no remove_ids at all (guidelines); you rebuild. Vector databases rebuild in the background by rewriting segments, as Vector Database Architecture explains, and some graph designs target streaming updates directly, such as FreshDiskANN (Singh et al., 2021).

Your turn: a reranker now needs the top 100 candidates instead of the top 10, from the same hnswlib index running with ef = 64. What happens to the effective beam, what should you measure, and what will probably happen to latency?

Move 3: Search only a few neighborhoods (IVF)

Symptom: the graph takes too long to build or rebuild, or you want an index that pairs naturally with compression.

An inverted file index (IVF) sorts the corpus into buckets before any query arrives:

1. Train: run k-means on a sample of the vectors to find nlist centroids.
2. Add: file every vector in the list of its nearest centroid.
3. Search: compare the query with all nlist centroids, pick the nprobe nearest, and scan only those lists exhaustively.

      cell 1           cell 2          nprobe = 2: scan cells 2 and 4 only
   .  . .  .  |   .  .  .  .  .
    .  c1  .  |  .   c2  .  .       c = centroid, q = query, * = true neighbor
   .  .  .    |  .  .  q  . .
  ------------+------------------   the true neighbor sits just across the
   .  .   .   |  .  .  *  .         border, in cell 4, so nprobe = 1 misses it
    .  c3  .  |   .  c4  .  .
   .  .  .  . |  .  .  .  .  .
      cell 3           cell 4

The boundary is why nprobe = 1 is rarely enough: a query near the edge of its cell has neighbors in the next cell. Here is the sweep on the test bench, with FAISS and nlist = 1024:

dim = X.shape[1]
ivf = faiss.IndexIVFFlat(faiss.IndexFlatIP(dim), dim, 1024, faiss.METRIC_INNER_PRODUCT)
faiss.omp_set_num_threads(12)
t = time.perf_counter()
ivf.train(X)                             # k-means: learn 1,024 centroids
ivf.add(X)                               # file every vector under its nearest centroid
print(f"train + add {time.perf_counter() - t:.0f} s")

faiss.omp_set_num_threads(1)
for nprobe in (1, 4, 16, 64, 128):
    ivf.nprobe = nprobe
    faiss.cvar.indexIVF_stats.reset()
    _, found = ivf.search(Qs, 10)
    scanned = faiss.cvar.indexIVF_stats.ndis / len(Qs)
    p50, _ = latency_ms(lambda q: ivf.search(q[None], 10))
    print(f"nprobe={nprobe:3d}  recall@10={ann_recall(found, gt):.3f}  "
          f"scanned {scanned:6,.0f} vectors ({scanned / len(X):.2%})  p50={p50:.2f} ms")
# train + add 7 s
# nprobe=  1  recall@10=0.641  scanned    621 vectors (0.12%)  p50=0.12 ms
# nprobe=  4  recall@10=0.854  scanned  2,324 vectors (0.44%)  p50=0.13 ms
# nprobe= 16  recall@10=0.946  scanned  8,771 vectors (1.68%)  p50=0.40 ms
# nprobe= 64  recall@10=0.982  scanned 34,051 vectors (6.51%)  p50=1.41 ms
# nprobe=128  recall@10=0.990  scanned 67,501 vectors (12.91%)  p50=2.88 ms

On top of the vectors in the lists, every query also compares itself with the 1,024 centroids. Now compare with the graph. To reach recall@10 ≈ 0.98, IVF scanned about 34,000 vectors per query, while HNSW at M = 16 computed 557 distances (recall 0.986 at efSearch = 32). IVF's scans are sequential reads, which CPUs handle very efficiently, so the latency gap (1.41 ms against 0.27 ms for hnswlib at ef = 32) is much smaller than the 60× count gap. On this data the graph still wins per query. IVF's advantages lie elsewhere:

• Fast builds. Training and adding took 7 s, against 201 s for the hnswlib graph.
• Small overhead: one 8-byte id per vector in FAISS, plus the centroids.
• Easy updates: new vectors go into the list of their nearest centroid, and FAISS IVF indexes support remove_ids.
• A natural partner for compression. Each list can store compressed codes instead of vectors (Move 4).

Choosing nlist. FAISS's guidelines suggest 4·√n to 16·√n centroids below a million vectors, trained on 30 to 256 vectors per centroid; pgvector's README suggests rows / 1000 lists up to a million rows and √rows above. For the test bench that is about 2,900 to 11,600 centroids by FAISS's rule and 523 by pgvector's; the 1,024 used here sits between them. Treat both rules as starting points for a sweep. FAISS warns when the sample is too small: 4,096 centroids trained on 50,000 vectors printed please provide at least 159744 training points (39 per centroid).

When the centroids go stale

The centroids describe the data they were trained on. Add a new kind of content later and it all lands in whichever old cells happen to be nearest. To test that, the same index was trained twice, on 60,000 vectors each time, and then filled with the whole corpus:

FAISS's imbalance factor is 1.0 when all lists are equal. With skewed training, the centroids crowd into one topic while everything else shares a few oversized cells. Each probe then scans more vectors and still finds fewer of the true neighbors. nprobe can buy some of that back, but only retraining on a representative sample fixes it. Retraining means rebuilding the index.

Predict: what does IVF-Flat return with nprobe = nlist?

Move 4: Shrink the vectors, then rescore

Symptom: the index does not fit in RAM, or RAM is most of the bill.

In both structures above, the float32 vectors dominate memory. Here is the arithmetic for 10 million 768-d chunks:

n, dim, M = 10_000_000, 768, 16
sizes = {
    "float32 vectors": n * dim * 4,
    "HNSW links (2*M ids on layer 0)": n * 2 * M * 4,
    "int8 scalar codes": n * dim * 1,
    "binary codes (1 bit per dim)": n * dim // 8,
    "PQ codes, m=96 x 8 bits": n * 96,
}
for name, b in sizes.items():
    print(f"{name:33s} {b / 1e9:6.2f} GB")
# float32 vectors                    30.72 GB
# HNSW links (2*M ids on layer 0)     1.28 GB
# int8 scalar codes                   7.68 GB
# binary codes (1 bit per dim)        0.96 GB
# PQ codes, m=96 x 8 bits             0.96 GB

That is 30.72 GB (about 28.6 GiB) of float32 against under a gigabyte of binary or PQ codes. Now look at the links row again: a rounding error next to float32, but next to 0.96 GB of codes, the 1.28 GB of links are the largest part of the index. On the test bench it is 128 B of links against 48 B of codes per vector, 73% of the total. After compression, lowering M starts to matter, and the graph is what eventually outgrows RAM. Move 5 deals with that.

Three ways to compress:

• Scalar quantization (int8). Map each dimension's range onto 256 levels: one byte per dimension, 4× smaller.
• Binary quantization. Keep only the sign of each dimension: one bit, 32× smaller. Distances become Hamming distances (XOR and popcount), which are very fast.
• Product quantization (PQ). Cut each vector into m sub-vectors and replace each with the id of its nearest centroid from a 256-entry codebook for that slice: m bytes per vector (Jégou, Douze & Schmid, IEEE TPAMI 2011).

PQ from scratch, and the asymmetric trick

PQ is less mysterious once you build it yourself. This version splits the 384 dimensions into 48 slices of 8 and learns 256 centroids per slice:

m, dsub = 48, X.shape[1] // 48           # 48 sub-vectors of 8 dimensions
train = X[np.random.default_rng(1).choice(len(X), 50_000, replace=False)]
codebooks = []
codes = np.empty((len(X), m), dtype=np.uint8)
for j in range(m):
    part = slice(j * dsub, (j + 1) * dsub)
    km = faiss.Kmeans(dsub, 256, niter=20, seed=j)      # 256 centroids -> 1 byte
    km.train(np.ascontiguousarray(train[:, part]))
    codebooks.append(km.centroids)                     # shape (256, 8)
    codes[:, j] = km.index.search(np.ascontiguousarray(X[:, part]), 1)[1][:, 0]
print(f"{codes.nbytes / len(X):.0f} bytes per vector instead of {X[0].nbytes}")

def pq_search(q, k=10):
    # Asymmetric distance: the query stays float32. One (48 x 256) table of
    # partial inner products per query, then 48 lookups + adds per vector.
    table = np.stack([codebooks[j] @ q[j * dsub:(j + 1) * dsub] for j in range(m)])
    scores = table[np.arange(m), codes].sum(axis=1)
    return np.argpartition(-scores, k)[:k]

def pq_then_rescore(q, k=10, candidates=100):
    cand = pq_search(q, candidates)
    return cand[np.argsort(-(X[cand] @ q))[:k]]        # exact scores for the shortlist

sub = slice(0, 200)                                    # 200 queries keep this quick
print(f"PQ alone:                recall@10 = {ann_recall([pq_search(q) for q in Qs[sub]], gt[sub]):.3f}")
for c in (40, 100):
    found = [pq_then_rescore(q, candidates=c) for q in Qs[sub]]
    print(f"PQ top-{c:3d} + rescoring: recall@10 = {ann_recall(found, gt[sub]):.3f}")
# 48 bytes per vector instead of 1536
# PQ alone:                recall@10 = 0.783
# PQ top- 40 + rescoring: recall@10 = 0.989
# PQ top-100 + rescoring: recall@10 = 0.999

The query is never quantized, and that is the asymmetric part. For each query you compute 48 × 256 partial scores once, one per slice and centroid. After that, scoring a stored vector means looking up its 48 codes in the table and adding the results: no multiplications, and 48 bytes read instead of 1,536. Jégou et al. showed that keeping the query exact gives better estimates than quantizing both sides.

Look at the numbers. PQ alone lost a lot of recall. Rescoring a shortlist with the original vectors brought almost all of it back. That pattern, cheap codes to shortlist, exact vectors to decide, is how quantization is used in practice.

Binary: 32× smaller, and rescoring does the rest

faiss.omp_set_num_threads(12)
bits = np.packbits(X > 0, axis=1)        # sign of each dimension: 384 dims -> 48 bytes
binary = faiss.IndexBinaryFlat(X.shape[1])
binary.add(bits)
_, cand = binary.search(np.packbits(Qs > 0, axis=1), 100)   # Hamming distance
print(f"binary alone:                recall@10 = {ann_recall(cand, gt):.3f}")
for c in (40, 100):
    found = [ids[:c][np.argsort(-(X[ids[:c]] @ q))[:10]] for ids, q in zip(cand, Qs)]
    print(f"binary top-{c:3d} + rescoring: recall@10 = {ann_recall(found, gt):.3f}")
# binary alone:                recall@10 = 0.717
# binary top- 40 + rescoring: recall@10 = 0.954
# binary top-100 + rescoring: recall@10 = 0.986

The full comparison on the test bench. These are flat scans over the codes, and rescoring uses the float32 originals. The PQ rows come from FAISS's IndexPQ on all 1,000 queries, so they differ slightly from the 200-query run above:

Binary codes alone do poorly here, and at 384 dimensions that is expected: Qdrant's quantization guide says one-bit codes lost significant precision on vectors smaller than about a thousand dimensions. You have two levers. The first is the one above: shortlist more, then rescore. The second is a better code:

• More bits per dimension. Qdrant (v1.15+) offers 1.5-bit and 2-bit binary encodings.
• Asymmetric encoding. The stored vectors stay binary while the query is encoded with more bits (Qdrant v1.15+, 8 or 4 bits), the same idea as PQ's asymmetric distance above.
• Rotation first. RaBitQ (Gao & Long, SIGMOD 2024) rotates the vectors randomly before quantizing them. It is available in FAISS as IndexRaBitQ, and it scored 0.798 with 56-byte codes on the test bench, and 0.992 after rescoring the top 40. Qdrant v1.18 added TurboQuant, another rotation-based scheme, with 1 to 4 bits per dimension.

Configuring Qdrant's options is part of Advanced Qdrant. Shorter vectors from a Matryoshka-trained model are another lever, covered in Vector Embeddings.

IVF-PQ: the recall that nprobe cannot buy

IVF and PQ combine naturally: the lists hold PQ codes of each vector's offset from its centroid. Watch what nprobe can and cannot do:

dim = X.shape[1]                         # 384 again (the memory example set it to 768)
ivfpq = faiss.IndexIVFPQ(faiss.IndexFlatIP(dim), dim, 1024, 48, 8, faiss.METRIC_INNER_PRODUCT)
ivfpq.train(X)
refined = faiss.IndexRefineFlat(ivfpq)   # wrap BEFORE adding: it keeps a float32 copy
refined.add(X)
refined.k_factor = 10                    # rescore 10 x k candidates with exact scores
faiss.omp_set_num_threads(1)
for nprobe in (4, 16, 64, 256):
    ivfpq.nprobe = nprobe
    _, a = ivfpq.search(Qs, 10)
    _, b = refined.search(Qs, 10)
    print(f"nprobe={nprobe:3d}  IVF-PQ recall@10={ann_recall(a, gt):.3f}   with rescoring={ann_recall(b, gt):.3f}")
print(f"bytes per vector: IVF-PQ {faiss.serialize_index(ivfpq).nbytes / len(X):.0f}, "
      f"IVF-PQ + float32 copy {faiss.serialize_index(refined).nbytes / len(X):.0f}")
# nprobe=  4  IVF-PQ recall@10=0.696   with rescoring=0.853
# nprobe= 16  IVF-PQ recall@10=0.730   with rescoring=0.942
# nprobe= 64  IVF-PQ recall@10=0.735   with rescoring=0.973
# nprobe=256  IVF-PQ recall@10=0.737   with rescoring=0.982
# bytes per vector: IVF-PQ 60, IVF-PQ + float32 copy 1596

Two lessons in five lines of output:

1. IVF-PQ alone plateaus. Probing more cells cannot fix an error that lives in the codes. If recall stalls while you raise nprobe, you have hit the quantization floor. Add rescoring or use bigger codes.
2. Rescoring from RAM gives up the memory savings. IndexRefineFlat keeps every float32 vector in memory, so the index grows from 60 to 1,596 bytes per vector. That setup still saves compute, but it does not save RAM. To save RAM, the originals must live on disk and be read only for the shortlist.

⚠️ Build order trap: creating IndexRefineFlat around an index that already holds vectors raises 'base_index->ntotal == refine_index->ntotal' failed. Wrap the trained, empty index first, then add through the wrapper.

Where do the originals live?

query ──► quantized index in RAM ──► top k_candidates ids ──► read those originals ──► exact scores ──► top k
          (int8 / binary / PQ codes,     (e.g. 100)          (RAM, or SSD: 100 reads    (100 dot products)
           plus graph or IVF lists)                           of 1.5 to 4 KB each)

With originals on SSD, rescoring 100 candidates of 768-d float32 reads 100 × 3,072 B ≈ 307 KB per query, as 100 small random reads. That is cheap on local NVMe and slow on network-attached disks. Measure it on your hardware. Vector databases expose this pattern directly. Qdrant, for example, has quantization with oversampling and rescore settings, and its production tuning is covered in Advanced Qdrant.

Your turn: 50 million 1,024-d vectors on a machine with 64 GB of RAM and a local NVMe drive. You need recall@10 ≥ 0.95 against exact search. Which configuration fits?

Move 5: Past RAM, and the family tree

Symptom: even with compressed codes, a billion-vector index outgrows one machine's memory, or the RAM bill dominates.

Graphs on SSD: DiskANN

After Move 4, the graph is the biggest thing left in RAM. At a billion vectors, 128 B of links per vector (M = 16) is 128 GB before a single code is stored. DiskANN (Subramanya et al., NeurIPS 2019) puts the graph itself on disk:

RAM:   PQ codes for every vector ──► guide the walk (approximate distances)
                                          │ which nodes to expand next?
SSD:   for each node, one block: [ full float32 vector | its neighbor ids ]
                                          │ one read returns both
                                          ▼
       beam search reads a few blocks per round trip, then ranks the
       visited nodes by their full vectors (the rescoring is "free")

Its graph, Vamana, is a single layer built with a pruning rule that deliberately keeps some long-range edges, so a search needs fewer hops, and every hop costs an SSD read. Because each node's full vector sits in the same disk block as its neighbor list, the rescoring step reads nothing extra. The paper reports a billion-point index served from a workstation with 64 GB of RAM and an SSD, at 95%+ recall@1, more than 5,000 queries per second and under 3 ms mean latency on the SIFT1B benchmark, using a 16-core machine. That is one dataset on the authors' hardware; your numbers come from your own test.

As of 2026 you meet the idea as a DISKANN index type in Milvus (PQ codes in memory, graph on NVMe) and as StreamingDiskANN in the pgvectorscale extension for Postgres. Which product to choose is a question for Vector DB Selection.

ScaNN, from Google (Guo et al., ICML 2020), is the other name you will see. Its search runs in three phases: pick a few partitions, as IVF does, score their points with quantized codes, then recompute the scores of the best candidates more accurately. Its twist is anisotropic quantization: for inner-product search, it penalizes the part of a vector's quantization error that is parallel to the vector more than the part orthogonal to it. For the queries that match a vector best, error along the vector's own direction moves the score the most.

The family tree: trees and hashing

Two older families still show up in blog posts and older code:

• Trees. k-d trees are exact but degrade in high dimensions, as Move 1 showed. Spotify's Annoy builds a forest of random-projection trees instead: each split is the hyperplane halfway between two sampled points. Its index is a read-only file that many processes can memory-map and share, and you cannot add items once it is built. In October 2023 Spotify released Voyager, based on hnswlib, "intended to succeed Annoy" for production use. Spotify reports more than 10× Annoy's speed at the same recall.
• Locality-sensitive hashing (LSH). Hash functions chosen so that close vectors collide more often than distant ones (Indyk & Motwani, STOC 1998). For cosine similarity, one hash bit is the side of a random hyperplane a vector falls on (Charikar, STOC 2002). Binary quantization's sign bits are the same trick, with fixed hyperplanes (one perpendicular to each coordinate axis) instead of random ones. MinHash for set similarity (Broder, 1997) belongs to the same family. LSH comes with provable guarantees, and inserts are easy, but high recall needs many hash tables and so a lot of memory. On dense text embeddings, graph and quantization indexes have largely replaced it.

Filters change the picture

Real queries usually carry filters: tenant, language, date. A filter that removes 98% of the corpus interacts badly with an index that returns a fixed top k before filtering, and graph walks can lose connectivity when most nodes are off limits. Pre-, post- and in-graph filtering are the subject of Metadata & Filtering, including how Qdrant's planner chooses between an exact scan of the matching points and a filter-aware graph walk (it does not post-filter), and why its payload index must exist before the graph is built. Benchmark with the filters you will actually use.

Move 6: Benchmark it on your own data

Symptom: a benchmark chart promised 0.99 recall, and your system does not feel like 0.99.

What ann-benchmarks is, and is not

ann-benchmarks (Aumüller, Bernhardsson & Faithfull, Information Systems) runs many libraries on public datasets such as SIFT, GloVe and GIST. It plots recall against queries per second, one query at a time on one CPU. The current published results date from April 2025. Read it like this: pick your recall target on the x-axis and compare the throughput of the curves there. Use it to shortlist two or three candidates. It cannot tell you how those candidates behave on your embeddings, with your filters, your update rate and your hardware.

The same index, four data sets

Identical FAISS HNSW settings (M = 16, efConstruction = 100), 1,000 queries each:

The newsgroup rows come from all 18,846 posts in scikit-learn's fetch_20newsgroups, with headers, footers and quotes removed, split at blank lines, keeping paragraphs of 40 to 1,000 characters (74,053, not deduplicated), of which 1,000 random ones were held out as queries.

Four lessons:

• Real data differs. At the same low efSearch, the longer, more varied newsgroup paragraphs were harder than short Quora questions, even with seven times fewer vectors. By efSearch = 256 the gap nearly closes, and how big it looks depends on how you cut the paragraphs. A setting tuned on one dataset is a guess on another.
• Random vectors are useless for recall. With no neighbor structure, the same index scores close to zero. They are fine for timing memory bandwidth and useless for choosing efSearch.
• Queries copied from the index look a little better than real ones, but on this data only a little. Each copy's exact #1 is itself. On 5,000 queries of each kind at efSearch = 10, copies scored recall@1 0.983 and recall@10 0.954, against 0.970 and 0.944 for held-out queries; by efSearch = 32 the gap was gone. But Quora's documents are questions, just like its queries. In RAG, chunks are passages and queries are short questions, so recall measured with chunks as queries need not carry over to real questions. That, more than self-matching, is why you test with real queries.
• Averages hide tails. Report the share of queries below some recall (say 0.8), and read a sample of the worst ones. That is how you would find the trapped queries from the opening.

A measurement plan you can reuse

1. Queries: 500 to 1,000 real queries from logs, held out from the index. If you have no logs, write a few hundred questions of the kind your users will ask about your content, or have an LLM draft them and a person spot-check them. Chunks that were never indexed avoid self-matching, but they are still passages, not questions.
2. Ground truth: exact top-k by brute force, computed offline in batches. Inside a vector database, use its exact mode (Qdrant: SearchParams(exact=True)).
3. Sweep the query knob (efSearch, nprobe, the rescoring shortlist). For each setting, record ANN recall@k, p50/p95/p99 latency of single queries at your production concurrency, and memory.
4. Pick the cheapest setting that meets the recall target inside the latency budget. Write it into configuration, including after reloads.
5. Re-measure after anything changes: data volume, embedding model, filters, delete rate, library version. Track IR recall on a labeled set separately, because that one measures the model, not the index.

Final round: no label on the symptom

Real incidents do not say which move they need. Start from the measurement, name the symptom, then pick the move.

Challenge 1: the nightly purge

A news-search service uses hnswlib and removes expired articles every night with mark_deleted. After three months, 70% of the vectors in the index are expired. Recall against an exact search over the live articles is still fine, but p50 latency has roughly doubled, and the process has not given back any memory. Diagnose it, and fix it.

Challenge 2: recall that will not move

An IVF-PQ index (m = 32) gives recall@10 of 0.71 at nprobe = 16, 0.73 at 64 and 0.73 at 256. The team proposes nprobe = 1024. What do you tell them?

Challenge 3: two results instead of ten

One HNSW index holds 2 million chunks for many tenants. A small tenant owns 1% of them. The service asks the index for the top 100, drops chunks that belong to other tenants, and returns the best 10 that remain. Some of that tenant's queries return only one or two results, and not its best ones. What is going on, and where do you look next?

Challenge 4: minus ones in the candidate list

A reranker receives the top 100 candidates from a FAISS IndexHNSWFlat left at its default settings. The reranked results look worse than the team expected, and a few requests log candidate ids of −1. What is wrong?

Cheat sheet: symptom → move → cost

Before moving on, take one index you run or plan to run and answer out loud: which structure it uses and why, which knob you would turn first if recall dropped, what that knob costs, where the original vectors live if you quantize, and the exact query set and ground truth you would use to prove the new setting is better. If you can do that, you can read any vector database's index settings and know what they trade.

Next: Vector DB Selection turns these trade-offs into a product choice, Qdrant shows the HNSW and quantization settings in one real engine, and Metadata & Filtering handles the filters every real query carries.