Indexes and the trade you are making

There are two ways to find the nearest vectors to a query. Compare against all of them, which is always right and gets slower as you grow. Or compare against a clever subset, which is fast and sometimes wrong.

Everyone ends up on the second one eventually. What matters is whether you know, in numbers, how often it is wrong.

1.Exact search, and why you keep it around

Exact search - sometimes called flat or brute-force - scores the query against every stored vector and sorts. It is one matrix multiply. It is not an approximation of anything; it is the definition of the correct answer.

Its cost is linear in corpus size and in dimensions. A million vectors of 1,024 dimensions is about a billion multiply-adds per query, and ten million is ten billion. The rows are rules of thumb, not measurements, so time your own:

Even after you index, keep exact search available on a sample. It is your ground truth, and section 3 is built on it. If a store keeps a vector per token, multiply every size here by the tokens per chunk; Late interaction: one vector per token does that sum.

2.HNSW and IVF, and their knobs

HNSW - hierarchical navigable small world - builds a graph. Each vector becomes a node connected to some of its near neighbours, in layers: a sparse top layer for long jumps across the space, denser layers below for local refinement. A search enters at the top, greedily walks towards the query, drops a layer, walks again, and finishes with a careful local search at the bottom.

It is the default in most vector stores because it is fast and its recall is high. Its costs are memory, because the whole index is expected to sit in RAM, and build time.

ef_search is the one to know. It is per query, so you can tune it live, and raise it for a slow accurate path while keeping it low for a fast one. M and ef_construction are baked in at build time, and changing them means rebuilding the index.

The failure case: a reranker that only ever sees 40. As of October 2026, pgvector (version 0.8.7) sets hnsw.ef_search to 40, and its README says results are limited by that candidate list. A team asks for LIMIT 50 to feed the candidate list from Reranking, but an index scan can return no more than 40 rows, so the reranker may never see ten candidates, and the best chunk may be one of them (the README gives no exact row count). For filtered queries, the same README describes hnsw.iterative_scan, which keeps scanning the index when a filter leaves too few rows. The fix is SET hnsw.ef_search = 100, then measure it in section 3.

IVF - inverted file - partitions instead. Cluster all the vectors into nlist buckets, remember each bucket's centre, and at query time compare the query to the centres, pick the closest nprobe buckets and search only inside those.

IVF's characteristic failure is a query that lands near a bucket boundary: its true nearest neighbour sits in the bucket next door, which you did not search. Raising nprobe fixes it at the cost of speed. IVF also has to be trained - the clusters are learned from a sample of your vectors (the FAISS guide asks for roughly 30 to 256 training vectors per cluster), so an index built on an empty or unrepresentative table will have bad buckets, and heavy inserts after training degrade it until you rebuild.

Default to HNSW. Reach for IVF when memory is the binding constraint, usually combined with quantisation.

Quantisation shrinks the vectors themselves. Take 10 million chunks at 1,024 dimensions. As 32-bit floats that is 10,000,000 x 1,024 x 4 bytes, about 41 GB, plus about 1.3 GB of HNSW edges at M of 16 (FAISS's memory formula). Scalar quantisation stores one byte per dimension instead of four: about 10 GB of vectors, for a small recall cost. Qdrant's guide (vendor-reported) puts that error usually under 1 percent in its tests. Binary quantisation keeps one bit per dimension, about 1.3 GB of vectors, but the same guide warns of large precision loss below roughly 1,000 dimensions, so it works as a first pass: fetch a wide candidate set, then rescore it with full-precision vectors. Product quantisation codes sub-vectors against a learned codebook, compressing hardest at the most accuracy cost and tuning.

Approximate search is not a worse kind of search. It is the same search with a dial on it, and the dial is only dangerous when you do not know where it is set.

3.Measure index recall, then tune

Take a sample of real queries. Run each one through exact search to get the true top k. Run it through your index. Compare the overlap. Say the true top 10 for one query are ten rows, and the index returns eight of them plus two strangers: recall@10 for that query is 8 / 10 = 0.8. Average that over a few hundred queries and you have your index recall@k, the number you tune against. It scores the index against exact search, not the system against the right answer. That is a different measure from the recall@k of Measuring retrieval, which counts the queries whose right chunk lands in the top k.

# pip install numpy
import time
import numpy as np

def true_top_k(index: np.ndarray, q: np.ndarray, k=10):
    """Ground truth: score against every vector. Unit-length vectors assumed."""
    return set(np.argsort(index @ q)[::-1][:k].tolist())

def measure(index, queries, ann_search, k=10):
    """ann_search(q, k) -> list of row ids from your real store."""
    truths = [true_top_k(index, q, k) for q in queries]  # outside the timer
    t0 = time.perf_counter()
    got = [set(ann_search(q, k)) for q in queries]  # time only the index
    ms = (time.perf_counter() - t0) * 1000 / len(queries)
    recall = np.mean([len(g & t) / k for g, t in zip(got, truths)])
    return float(recall), ms

# index: (n, d) unit-length array; sample_queries: your real query vectors;
# search(q, k, ef_search=...): your store's own call
for ef in (10, 40, 100, 200, 400):
    r, ms = measure(index, sample_queries, lambda q, k: search(q, k, ef_search=ef))
    print(f"ef_search={ef:<4} index recall@10={r:.3f}  {ms:.1f} ms/query")

Recall typically climbs steeply, then flattens, while latency keeps climbing. You want the elbow - the point past which you pay real milliseconds for a fraction of a percent.

Two things the sweep teaches:

• Measure at the k you actually use. Index recall@10 and index recall@50 are different numbers, and the sweep should use the k your reranker consumes.
• Index recall is not the same as your system being good. It only measures whether the index found what brute force would have found. If exact search itself misses the right chunk, the problem is upstream in embeddings or chunking, and no index setting will help.

When not to tune at all. If exact search fits your latency budget, skip the index and this section. If a filter leaves only a few thousand rows, an exact scan over them often beats the graph, as Metadata and filtering explains. And once index recall at your k is high enough that misses are rare, stop: the remaining errors are more likely in chunking or embeddings than in the index.

Re-measure after your corpus changes substantially. Index quality is a function of the data in it, so settings that gave 0.98 index recall at 100,000 vectors are a claim about a corpus you no longer have. Measuring retrieval applies the same habit to the whole retriever, not only the index.