Sweeping the query-time knob traces the curve you will ship on

A vendor comparison sheet reports 0.99 recall at 0.42 ms per query and 2,400 QPS, benchmarked on SIFT1M. A team sizes their cluster from those numbers, deploys against 3M chunks of internal documentation at 1024 dimensions, and gets 0.88 recall at 6.8 ms with the same library and the same parameters. Nothing was misrepresented. SIFT1M is a million 128-dimensional local image descriptors with a low intrinsic dimensionality and tight cluster structure, which is close to the friendliest data an ANN index will ever see; 3M paragraphs of prose embedded by a modern text model occupy a much higher effective dimension with far weaker clustering, and every index behaves worse on it. The published number is a correct measurement of a different question.

There is no shortcut around this. A sweep, in the sense used here, holds the corpus, the query set, the ground truth and the machine fixed, moves one parameter through a range of values, and records the same measurements at every setting; what it traces out is a surface in three axes at once. That recall-latency-memory surface is a joint property of the index, the parameters and the data, and the only corpus whose surface predicts your production behaviour is your corpus. Running the sweep yourself is a day of work and it replaces every assumption in the stack.

The three numbers, and why each is in the list#

Recall is measured against exact search, per chapter 2, on queries drawn from production logs. It is the axis you are buying with everything else.

Latency is measured at percentiles, and the percentile matters more here than in most systems, because graph search has a naturally right-skewed cost distribution. Easy queries converge in a few dozen distance computations; queries into sparse regions — the population from chapter 5 — backtrack repeatedly and evaluate several times as many nodes before the beam settles. A representative HNSW run at ef_search = 200 on the 3M corpus measured 3.1 ms mean, 4.0 ms p50, 11.2 ms p95, and 28.6 ms p99. Reporting the mean would understate the p99 by a factor of nine. In a RAG pipeline that issues four retrievals in parallel and waits for all of them, the request's latency is the maximum of four draws, so the tail is what the user experiences roughly half the time rather than one time in a hundred.

That last step is worth doing rather than asserting, because it is the whole argument for keeping a percentile column. A request that fires four retrievals and cannot finish until all four return has the largest of the four as its latency. It comes in under some level only if every one of the four comes in under that level, and for draws treated as independent that probability is the single-query probability multiplied by itself four times. A level that one single query in six exceeds is therefore beaten by all four only about half the time, which puts the median request at roughly the point in the single-query distribution that only one query in six reaches. The four draws are not really independent, since they contend for the same memory bandwidth on the same box, and the concurrency measurement further down is what prices that; the arithmetic above is the floor rather than the estimate. A mean of 3.1 ms describes nothing anybody experiences either way.

Peak resident memory is measured rather than computed, because the arithmetic from chapters 1 and 4 covers the vectors and the graph and misses everything else. FAISS and hnswlib allocate per-thread scratch space proportional to ef_search and thread count; Python holds the ID arrays; the process keeps the file-backed pages it touched during load. On the 3M corpus, an HNSW index whose vectors and graph should total 11.0 GB reached 12.4 GB of resident set size — RSS, the memory the process is actually holding in RAM at that moment, which is the figure a container limit is enforced against — after loading and 13.1 GB after a thousand concurrent queries at ef_search = 800. The 2.1 GB gap is the difference between fitting on a 16 GB instance and not.

Those three figures close on each other exactly, and noticing that they do is what makes the gap worth naming rather than shrugging at. The arithmetic predicted 11.0 GB, the process peaked at 13.1 GB, and the 2.1 GB quoted is the distance between those two with nothing left over — it is quoted against the prediction, not against the 12.4 GB measured at load, which is why it looks larger than the step the paragraph above describes. Splitting the gap at the load figure separates two costs that behave differently. Everything from the prediction up to the figure at load is paid once, when the index is read in and the ID arrays and file-backed pages appear. Everything from there to the peak is paid per unit of concurrency, because the scratch space is allocated per thread and grows with ef_search. A container sized from the arithmetic is short by the whole gap; a container sized from the figure at load survives a quiet afternoon and dies under traffic.

Build time belongs in the table too, even though it is not a serving cost, because it sets how long a rebuild takes and therefore how quickly you can respond to any of the problems in the previous chapters.

The harness#

import faiss, hnswlib, numpy as np, time, psutil, os

def measure(search_fn, queries, gt_ids, warmup=50):
    for q in queries[:warmup]:
        search_fn(q[None, :])
    lat = np.empty(len(queries))
    ids = np.empty((len(queries), 10), dtype=np.int64)
    for i, q in enumerate(queries):
        t0 = time.perf_counter()
        ids[i] = search_fn(q[None, :])
        lat[i] = (time.perf_counter() - t0) * 1000
    rss = psutil.Process(os.getpid()).memory_info().rss / 1e9
    return {
        "recall": index_recall(ids, gt_ids).mean(),
        "p50": np.percentile(lat, 50),
        "p95": np.percentile(lat, 95),
        "p99": np.percentile(lat, 99),
        "rss_gb": rss,
    }

results = []

flat = faiss.IndexFlatIP(d)
flat.add(corpus)
results.append(("flat", None, measure(lambda q: flat.search(q, 10)[1][0], queries, gt_ids)))

ivf = faiss.IndexIVFFlat(faiss.IndexFlatIP(d), d, 2048, faiss.METRIC_INNER_PRODUCT)
ivf.train(train_sample); ivf.add(corpus)
for nprobe in (4, 16, 64, 256):
    ivf.nprobe = nprobe
    results.append(("ivf", nprobe, measure(lambda q: ivf.search(q, 10)[1][0], queries, gt_ids)))

hn = hnswlib.Index(space="ip", dim=d)
hn.init_index(max_elements=len(corpus), M=32, ef_construction=200)
hn.add_items(corpus, np.arange(len(corpus)), num_threads=16)
for ef in (40, 100, 200, 800):
    hn.set_ef(ef)
    results.append(("hnsw", ef, measure(lambda q: hn.knn_query(q, k=10)[0][0], queries, gt_ids)))

Exactly one knob moves at a time in that harness, and it is worth saying why, because it is what makes the resulting table readable rather than merely full. Every IVF row shares one build — the same 2048 cells, trained once — and differs from its neighbours only in nprobe. Every HNSW row shares one graph, built at M = 32 and ef_construction = 200, and differs only in ef_search. Any difference between two rows of the same index type therefore has exactly one candidate cause, which is what allows a recall change to be attributed to the knob rather than debated. Move M and ef_search together and the table still has rows in it, and no row can be compared with any other row.

Comparisons across index types are a different kind of claim resting on a different control. The IVF rows and the HNSW rows do not share a build and cannot, so what holds them comparable is that both ran over the same corpus, with the same query set, against the same ground truth, on the same machine. That is a property of the harness rather than of the indexes, and it is the reason the sweep has to be one script rather than two people's notebooks.

Measuring RSS inside one process that has built every index is wrong, and the snippet above is the shape rather than the finished job: each index needs its own process, or a fresh process per configuration, so that the memory reading belongs to one index. That is a requirement rather than a preference, because resident set size is a process-level counter and a process holding four indexes has no way to attribute its pages to any one of them. A shell loop over a script that takes the config as an argument and writes one JSON line is the least fiddly way to do it, and it also isolates crashes when a configuration turns out not to fit.

Two other details decide whether the latency numbers transfer. The warm-up loop exists because the first queries against a freshly loaded index fault pages in from disk and report 10 to 100 times the steady-state cost; without it, small query sets produce meaningless p99s, and since the percentiles are the entire point of the latency column that makes the warm-up a requirement too. And the measurement above is single-threaded by design, which gives a clean per-query cost but says nothing about throughput under load — that one is a preference rather than a requirement, which is exactly why it has to be followed by a pass that does not share its assumption. If the service will run eight concurrent workers on a machine with eight cores, the interesting numbers come from replaying the query log at the target QPS with a real concurrency model, because memory bandwidth contention between workers can double per-query latency without changing any parameter.

Throughput deserves its own pass because the single-threaded numbers overstate what the machine delivers. Replaying the query log at a target rate against eight worker threads on an eight-core box produced, for HNSW at ef_search = 200, a p95 of 11 ms at 20 QPS, 14 ms at 60 QPS, and 41 ms at 120 QPS, with the knee between 60 and 90 — well before the arithmetic suggests, because eight threads walking a 13.7 GB graph in random order contend for memory bandwidth and thrash the last-level cache against each other. The graph traversal has terrible locality by construction, since each hop jumps to an arbitrary vector, so the per-query cost rises with concurrency in a way that a single-threaded measurement cannot see. Sizing a fleet from the single-threaded p95 will under-provision it by roughly a factor of two.

Two features of those three points matter more than the points themselves. The first is that the p95 at 20 QPS matches, to the precision the table carries, the single-threaded p95 for the same configuration. Two measurement setups that share neither their load generator nor their concurrency model landing on one number is what licenses calling 20 QPS effectively uncontended, and it is what makes the rise above that rate a contention effect rather than a different index doing different work. The second feature lives in the gaps rather than the levels. Going from 20 QPS to 60 triples the offered load and costs three milliseconds of p95; going from 60 to 120 only doubles it and costs nine times that. A cost that grows faster than the load causing it is what a knee is, and naming it by that property is more useful than naming it by the QPS figure where it happened to appear on this hardware.

Keep the per-query recall arrays, not only the means. The frontier table below reports a single recall figure per row because that is what fits in a table, but the artefact you want on disk is one row per query per configuration, because that is what makes the chapter 5 diagnosis possible without rerunning anything, and what lets you check whether a configuration that improved the mean improved the tail or merely moved the middle. Five hundred queries across ten configurations is 5,000 rows and a few hundred kilobytes.

Reading the frontier#

Read the four IVF rows downwards as differences rather than as levels, because the differences are where the shape lives. Each step quadruples nprobe. The first step, from four cells to sixteen, adds a little under two tenths of recall. The second, to sixty-four, adds somewhat under half of what the first added. The third, to two hundred and fifty-six, adds well under half again. The p50 column meanwhile rises by a factor that starts short of four and climbs toward it, because a fixed cost sits underneath every query — the comparison of the query against all 2048 centroids happens whatever nprobe is — and that fixed cost is a large share of the cheapest row and a small share of the dearest. Work rising in proportion to the knob while recall gain halves at every step is the entire shape of the curve.

The shape follows from the order the cells are probed in, which is one causal chain with no gaps in it. IVF ranks the cells by how close their centroids are to the query and visits the closest first. The first cell probed is therefore the one most likely to hold true neighbours, and every cell after it is less likely to hold one than the cell before it. Cells are roughly equal in size, so each costs roughly the same to scan. Constant cost per cell and falling yield per cell together force the marginal recall bought by one more unit of work to decrease, and to decrease from the very first step. There is no knee in the sense of a sudden change of regime — the return is diminishing everywhere — and what gets called the knee is simply where the next quadrupling stops being worth its latency to whoever is paying for it.

The HNSW rows say the same thing in a form that is easier to hold, provided you look at what is still missing rather than at what is present. At ef = 40 recall falls short of one by a little under nine hundredths. The next row roughly halves that shortfall, the row after halves it again, and the last row halves it once more, leaving a little over one hundredth outstanding. The knob multiplies by between two and four at each of those steps and p50 rises in step with it. A shortfall that halves while cost multiplies is the signature of a search finding the cheapest misses first, and its consequence is that the price of each remaining point of recall grows without limit. An argument that ends "we may as well take the extra point" is an argument about the cheapest of the points still available, and the table has already priced the one after it.

A point is on the Pareto frontier when nothing else in the table is at least as good on every axis. IVF at nprobe = 4 survives because no other row in the table has a lower p99. HNSW at ef = 40 survives because nothing reaches 0.91 recall in 2.9 ms at p95. IVF at nprobe = 16 is dominated — HNSW at ef = 40 beats it on recall, p50, p95 and p99 simultaneously, paying only 0.9 GB of memory and 28 minutes of build time — and so is IVF at nprobe = 64, beaten by HNSW at ef = 200 on every latency column at higher recall. The dominated rows are the ones a single-index sweep would never reveal, because within IVF alone nprobe = 16 looks like a perfectly reasonable operating point.

The survival of IVF at nprobe = 4 is worth following, because it is the one row where the medians and the tails disagree about which index type is better. HNSW at ef = 40 beats it on recall, on p50 and on p95, and loses to it on p99. That inversion is not measurement noise, and the mechanism behind it is the one from chapter 5 seen from the cost side. IVF at a fixed nprobe does a fixed amount of work: it compares the query against every centroid, selects the same number of cells for every query, and scans them. A query pointing into a sparse region gets exactly the same treatment as a query pointing into a dense one, so the cost distribution is narrow by construction. HNSW's work is decided by the data it walks through, and the sparse-region queries backtrack and re-evaluate before the beam settles, so its cost distribution has a long right side by construction.

The table prices that difference four separate times. Divide p99 by p50 in each row: the four IVF rows all land near three, and the four HNSW rows all land at more than twice that, with the ratio between the two ratios coming out a little over two in every one of the four pairs. Four independent pairs of measurements landing on one factor is what licenses treating it as a property of the index type rather than of a particular parameter setting — whatever nprobe or ef_search is set to, an HNSW tail sits a bit more than twice as far from its own median as an IVF tail does. A service whose SLO is written on p99 should read that column before it reads the recall column.

The memory column is flatter than it looks and it still decides things. All the rows sit between 12.3 and 14.1 GB because the vectors dominate, so no configuration here is memory-constrained on a 32 GB box — but the 1.8 GB spread between the flat index and HNSW at ef = 800 is exactly the amount that would push a 16 GB instance over. That 1.8 GB is the full height of the column, top row to bottom, rather than a step between adjacent rows. Memory earns its column because it varies between index types, and because it is the axis that turns a latency decision into a hardware decision. Within one index type it barely moves at all.

The exact scan rows earn their place by anchoring the scale. At 112 ms they are not viable for an interactive search box, and they would be entirely viable for a nightly batch job or an internal tool at one query per second — which is the chapter 1 argument reappearing with real numbers attached, and a reminder that the same corpus can want different answers for different workloads.

What the frontier does not do is choose for you. Picking a point requires a latency budget and a recall requirement that come from outside the measurement: how much of the request budget retrieval is allowed to spend once the embedding call and generation are accounted for, and how much index loss the downstream pipeline tolerates before answers degrade. A reranker over the top 50 absorbs a lot of index loss; a system that passes the top 3 straight into a prompt absorbs almost none. Those thresholds turn a table into a decision, and they are a product question rather than an index question.

The shelf life of the measurement#

Everything above is valid for this corpus at this size with this embedding model. Growing from 3M to 9M chunks changes the graph's geometry, moves the plateau, and roughly triples the exact-scan row; the relative ordering of the index types usually survives, but the operating point does not. Changing the embedding model changes the intrinsic dimensionality of the space, which can move recall at a fixed ef_search by several points in either direction. A reasonable cadence is to rerun the sweep whenever the corpus triples or the model changes, and to run a single-configuration recall check on every rebuild, which costs a few minutes and catches regressions that would otherwise be invisible.

There is also a reason to keep your harness rather than adopting a published one. The ann-benchmarks suite and walkthroughs like Pinecone's Hierarchical Navigable Small Worlds (HNSW) article are excellent for learning the mechanics and for comparing libraries under controlled conditions, and neither can tell you where your corpus sits, because the datasets are the point of the comparison. The value of the local harness is that it takes your vectors, your query log, your hardware and your concurrency, and it can be rerun in an hour when someone proposes a change.

The frontier still has an axis missing. Every row above is a steady-state measurement over a corpus that does not change, and the 34-minute build time sits in a column without a rate next to it. A corpus where 8% of documents are edited daily makes that 34 minutes a recurring cost and makes IVF's centroids a decaying asset, and those pressures can eliminate an index type that looked best on every column of the table.

Three numbers on your own corpus, at several settings of one knob at a time, across more than one index type, is a day of work that replaces the whole stack of assumptions a vendor sheet installs. The table it produces does not contain the answer, and it does contain the set of answers that are not dominated, which is much smaller than the parameter space and is the only part of it worth arguing about. Each survivor arrives priced on the axes that turn a latency question into a hardware question and a hardware question into a fleet size. The next chapter puts corpus size, update rate and memory budget together and narrows the field before any benchmarking happens.