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 separates a system that works from one that mysteriously misses things is whether you know, in numbers, how often the second one is wrong.

1Exact 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. That linear cost is more forgiving than people expect, because a modern CPU does this kind of arithmetic extremely well:

Even after you index, keep exact search available on a sample. It is your ground truth, and section 3 is built on it.

2HNSW 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. Think of it as travelling by motorway, then A-road, then street.

It is the default in most vector stores because it is fast and its recall is high. Its costs are memory — the graph edges are stored alongside the vectors — and build time.

ef_search is the one to know. It is per query, so you can tune it live, expose it per endpoint, and raise it for a slow accurate path while keeping it low for a fast one. ef_search must be at least your k, and raising it well above k is the standard fix for disappointing recall. Note that M and ef_construction are baked in at build time — changing them means rebuilding the index.

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, 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. Scalar quantisation stores each dimension as an 8-bit integer instead of a 32-bit float — roughly a quarter of the memory, a small recall cost, and it is usually a good trade. Binary quantisation goes to one bit per dimension, which is a huge saving and a large accuracy cost on its own; it is used as a first pass, retrieving a wide candidate set cheaply and rescoring those candidates with the full-precision vectors. Product quantisation splits the vector into sub-vectors and codes each against a learned codebook, achieving strong compression at more accuracy cost and more 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.

3Measure recall, then tune

Here is the measurement that makes the rest of this lesson actionable. 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. That fraction is your recall@k, and it is the number you tune against.

# 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."""
    recalls, t0 = [], time.perf_counter()
    for q in queries:
        got = set(ann_search(q, k))
        recalls.append(len(got & true_top_k(index, q, k)) / k)
    ms = (time.perf_counter() - t0) * 1000 / len(queries)
    return float(np.mean(recalls)), ms

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} recall@10={r:.3f}  {ms:.1f} ms/query")

Run that once and the shape of the curve tells you everything. Recall climbs steeply at first, then flattens; latency climbs steadily and does not flatten. You want the elbow — the point past which you are paying real milliseconds for a fraction of a percent.

A few things the numbers will teach you:

• Defaults are frequently too low for ef_search or nprobe when k is large. If you retrieve 50 candidates for a reranker, ef_search of 40 cannot serve you well.
• Recall against exact search 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.
• Rebuild-time knobs and query-time knobs are different kinds of decision. Get M and ef_construction roughly right once, then live on ef_search.

And re-measure after your corpus changes substantially. Index quality is a function of the data in it, so the settings that gave you 0.98 recall at 100,000 vectors are a claim about a corpus you no longer have.