Recall, latency and index size

The decision this chapter is written around is which retriever sits behind a 50 ms p95 budget for an agent-facing documentation API. Answering it means running both over one chunk set and reading three measurements, each of which answers a different question: how often the right chunk comes back, how long that takes at the percentiles you are held to, and how much memory the structure needs to be resident in.

Knowing which question each number answers is most of the value of benchmarking anything. The three are not a scoreboard to be summed, and the most common way to misread them is to quote one aggregate recall figure at a meeting — which, as the last section of this chapter shows, is a statement about the query mix in your sample rather than about either retriever.

Measuring the same thing twice#

The protocol matters more than the tooling. Both retrievers index the identical chunk set — same chunker, same boundaries, same 4.4 million chunks with a mean length of 380 tokens — so that no difference in the results can be attributed to preprocessing. Both are evaluated on the same 340 labelled queries, sampled from four weeks of production logs and stratified so that the query classes appear in their real proportions. Latency is measured after a warm-up pass, over 2,000 queries replayed at a fixed rate, and reported as p50 and p95 rather than a mean, because retrieval latency distributions have long right tails and a mean hides them.

import time, statistics

def bench(search_fn, queries, judgments, k=10, warmup=200):
    for q in queries[:warmup]:
        search_fn(q, k)                       # fill caches, JIT, page in

    lat, hits = [], 0
    for q in queries:
        t0 = time.perf_counter()
        ids = search_fn(q, k)
        lat.append((time.perf_counter() - t0) * 1000)
        if judgments.get(q) in ids:
            hits += 1

    lat.sort()
    return {
        "recall_at_10": hits / len(queries),
        "p50_ms": statistics.median(lat),
        "p95_ms": lat[int(0.95 * len(lat))],
        "p99_ms": lat[int(0.99 * len(lat))],
    }

Latency measured one query at a time is the wrong measurement if the service will be under load, and the two retrievers degrade differently under concurrency. An HNSW traversal is CPU-bound — a few thousand distance computations over resident memory — so throughput scales with cores until the memory bus saturates, and p95 rises steeply once concurrent queries exceed the core count. A lexical query is dominated by decoding compressed postings, which is also CPU work, but its working set is small and its cache behaviour is far friendlier, so it degrades more gently. Reporting single-threaded latency for both and then sizing the fleet from it will underestimate the vector side, and the fix is to replay at the concurrency you actually expect rather than at one.

Which recall to report is a choice worth making explicitly. recall@k — did the gold chunk appear anywhere in the top k — is the right metric when the consumer is a model that receives k chunks and reads all of them, because position within the k barely matters. nDCG and MRR are the right metrics when a human scans a list top-down and position is the whole point. A retrieval-augmented pipeline handing five chunks to a model is closer to the first case, so recall@10 is the number these tables carry; a search box for humans would report nDCG@10 instead, and the two can rank the same two systems differently. Topic 8.3, on retrieval evaluation, is where those metrics and the judgments behind them are defined properly.

Index size needs two numbers rather than one, because they behave differently. On-disk bytes determine what you pay for storage and how long a restore takes; resident set size determines what instance you have to buy. For the lexical index those diverge by an order of magnitude, and for the vector index they do not — which is the whole of the argument developed in the previous chapter, and the one thing here you can assert before running anything.

The three numbers#

Several things in that table pull against each other and each is worth naming.

Recall improves with ef_search, and latency degrades roughly linearly with it, because ef_search is very nearly a count of how many graph nodes the traversal visits. Going from 40 to 200 buys 7 points of recall for 3x the latency, and there is a ceiling: the exact column shows that even an exhaustive scan reaches only 0.83, so 0.02 of the gap at ef=200 is approximation error and 0.17 is the embedding model simply not placing the right chunk near the query. That split is worth checking rather than accepting, because it is the most decision-relevant arithmetic in the table. At ef=200 the run found 0.81 of the queries, so a little under a fifth went missing. The exact column says an exhaustive scan over the same vectors finds 0.83, so exhaustive search misses 0.17. The difference between the two misses is 0.02, and that 0.02 is everything the approximation costs — the queries where the graph walk failed to reach a neighbour the scan would have found. Everything else, the 0.17, is missing from the exact column too, so it cannot be an indexing failure. It is the embedding model not placing the right chunk among the query's ten nearest. Two named causes, 0.02 and 0.17, adding to exactly the shortfall from a perfect score, with no residual. Raising ef_search cannot cross that ceiling, and neither can a reranker, because both operate on what the geometry already put nearby.

The two latency multipliers agree with each other, which is the sign that ef_search really is behaving like a node count. Between ef=40 and ef=200, p50 goes from 3 ms to 9 ms and p95 from 7 ms to 21 ms — both exactly triple. A parameter that scaled the traversal by five would have tripled the variable part of the query and left the fixed part alone, and the same ratio appearing at two different percentiles says the fixed part is small and consistent. Had p50 tripled while p95 grew by six, something other than the traversal would be responsible for the tail.

Index size does not respond to any of these dials. It is d × 4 bytes per chunk plus the graph, fixed the moment you choose a model and an M, and the only levers on it are quantisation or a smaller-dimension model. Recall and latency are tunable at query time; memory is a procurement decision taken months earlier.

The two size rows read together are the whole argument of the previous chapter in four numbers. BM25 occupies 22 GB on disk and 2.6 GB in memory, so its working set is under an eighth of the structure. HNSW occupies 18.6 GB on disk and 18.9 GB in memory, so its working set is the structure plus a little runtime overhead. The lexical index is the larger of the two on disk and the cheaper of the two to run, which is the reverse of the intuition that a bigger file needs a bigger machine — and the reason is the access pattern rather than the size. Then the last two rows close it: the instance column doubles twice from 8 GB to 32 GB, and the monthly figure goes up by almost exactly the same factor of four. The bill is a direct read-off of the resident set, so the memory row is not one input to a costing exercise. It is the costing exercise.

Three of the build figures also agree with numbers computed elsewhere in this topic, which is worth noticing because build time is where estimates usually drift. Twenty-five minutes for the lexical index is 4.4 million documents at the few-thousand-a-second rate a reindex runs at. Forty minutes for the embedding pass is 4.4 million chunks at the rate a single GPU manages with batching. Six hours for the graph sits inside the four-to-nine-hour band the construction parameters imply. None of these was measured to make the table agree with the others, and they agree.

The latency comparison also inverts depending on which percentile you read. At p50 and p95 the vector index at ef=40 is faster than BM25, which surprises people who expect a graph traversal to be expensive. At p99 the order flips hard: 210 ms against 9 ms, because the lexical tail is driven by query shape — the multi-term, all-common-words queries whose postings walk we counted at the start of this topic — while the graph traversal visits about the same number of nodes for every query regardless of what was typed. Lexical latency has a long tail and a cheap floor; HNSW latency is flat, higher at the floor, and predictable. Against a 50 ms p95 budget both pass; against a 50 ms p99 budget only one does, and no amount of BM25 tuning fixes that without capping query term count or enabling block-max pruning.

Reading each column top to bottom rather than each row across makes the reason plain. BM25 runs 6, 14 and 210 ms across the three percentiles, a spread of a factor of thirty-five. The exact scan runs 690, 740 and 760, a spread of about a tenth. Those two shapes are two different kinds of system. A bandwidth-bound scan does the same work for every query — it reads every vector whatever was typed — so its percentiles can only differ by scheduling noise, and the near-flat column is the evidence that the scan really is bound by streaming rather than by anything about the query. The lexical column is the opposite: its work is the postings walk, the walk is set by the document frequencies of the terms typed, and document frequencies across a real query log span several orders of magnitude. The tail is not a defect in the implementation. It is the query mix arriving in the measurement.

The exact column also settles an argument the previous chapter could only make on paper. Eighteen gigabytes at a plausible memory bandwidth was computed there as a floor of roughly seven tenths of a second per query, and the measured p50 here is 690 ms. A computed floor and an independent measurement landing within a few percent of each other is as close as this kind of reasoning gets to proof: the exhaustive scan is doing nothing but moving bytes, and no optimisation of the arithmetic will help it.

The number that decides nothing on its own#

The aggregate recall row is the one most likely to be quoted and the least useful. BM25 at 0.61 against HNSW at 0.81 reads as a clear loss, and the two rows beneath it show that the aggregate is an average over two populations behaving in opposite directions: 0.97 versus 0.31 on identifiers, 0.34 versus 0.88 on paraphrases. The aggregate is a statement about the query mix in the sample, so it changes when the mix changes. Point the same service at coding agents rather than humans and the identifier share goes from 18 percent to 55 percent, at which point the aggregates become 0.79 for BM25 and 0.57 for HNSW without either index being touched.

The reweighting is not an estimate, and seeing why licenses a further question the table can answer for free. An aggregate is a weighted average of the per-class rates, with the weights being the query mix, so the aggregate is a straight-line function of the identifier share while the per-class rates stay fixed. Two points determine a straight line. At an 18 percent identifier share BM25 trails by twenty points; at 55 percent it leads by twenty-two. Those two figures pin the share at which the two aggregates are equal, and it is a little over a third. That is a usable number: it says the vector index is the right choice for this corpus below roughly a third identifier traffic and the wrong one above it, and it comes out of two runs already done rather than from a third one.

Reporting recall broken down by query class is therefore not extra rigour; it is the minimum required for the number to mean anything. The classes to break on are the ones from earlier in this topic — rare strings, order-bearing phrases, code-like tokens — plus whatever remainder your logs show.

Two ways this benchmark lies#

The judgment set is the first. If the 340 gold labels were produced by having someone look at what the current vector system returned and mark the good ones, then every query where the vector system retrieved nothing relevant has no gold label at all, and both retrievers are being scored on a set of queries pre-filtered to ones the vector system could answer. This is pooling bias, it is the reason TREC pooled across multiple systems rather than one, and it reliably inflates the incumbent by 5 to 15 points. The correction is to build labels from at least both retrievers' top-20, plus a sample of queries with no relevant result found, which is more annotation work and is the difference between a benchmark and a formality.

Building the labels honestly is the expensive part of this whole exercise, and it is worth budgeting for rather than discovering. Three hundred and forty queries, each needing an annotator to read the top 20 from both retrievers and mark which chunks actually answer the question, runs to roughly 15 to 20 hours of engineer time spread across two or three people, plus an adjudication pass on the disagreements. That is a real week of somebody's attention. The arithmetic behind the estimate is also where the one available saving hides. Three hundred and forty queries with twenty results from each retriever is a little under fourteen thousand chunk readings if the two lists are disjoint, and at even a few seconds each that is well past the stated twenty hours. The two lists are not disjoint, and the overlap is the discount — every chunk both retrievers returned is read once. Which means the budget for building the labels is set by how differently the two retrievers behave, and a pair of retrievers that agree closely is cheap to judge and, for the same reason, not worth comparing. It is also the only asset in this chapter that survives every subsequent change to the system, because a judgment set outlives the model, the index and the framework, whereas the benchmark numbers expire the moment anything is re-embedded.

The second is that these latency figures are steady-state on a warm process. A cold HNSW index is a different animal: the graph has to be read from disk into memory before the first query can complete predictably, which for 18.6 GB is 90 seconds to several minutes depending on the storage, and during that window p95 is in the hundreds of milliseconds. That turns into a deployment constraint — rolling restarts need a warm-up gate, autoscaling on this service is close to useless because a new replica is slow for minutes, and a node eviction is a latency incident. The lexical index reaches steady state in seconds because it only needs its hot terms paged in.

Dividing the size by the time in that sentence tells you which storage it assumes, and therefore whether it applies to you. Eighteen and a half gigabytes read in ninety seconds is around two hundred megabytes a second, which is network-attached-disk throughput rather than local NVMe. On a local drive the same load is several times faster and the warm-up window shrinks accordingly. So the ninety seconds is not a property of HNSW — it is a property of the storage class the graph is being read from, and it is the one number in this section a different instance type genuinely changes. Everything else about the cold-start constraint survives, because the graph still has to be entirely resident before the first query behaves predictably.

Read narrowly, a table like the one above answers "which one ships". Read as it is more usefully read, it produces a floor: BM25's 0.61 aggregate, and more importantly its 0.97 on identifiers, is a number the vector-first system must beat on the same queries, and its 0.34 on paraphrases says plainly where lexical retrieval cannot help. Both halves are needed, and the second is the part teams skip when they present the result.

Every measurement so far has treated the two retrievers as candidates competing for a slot. There is a use for the lexical index that does not require it to win any of these rows, or to be exposed to a single user, and it is the reason to build one even on a system that has already decided to be vector-first.