Approximation loss lands on a predictable population of queries

Take the 3M-vector HNSW index from the previous chapter — three million embedded chunks held in a Hierarchical Navigable Small World graph, built at M = 16 and queried at ef_search = 40, with a mean R@10 of 0.86 — and print the per-query values instead of the mean. R@10 is index recall in the sense of chapter 2: for one query, the fraction of the ten documents an exact scan over every stored vector would have returned that the approximate index actually returned. With ten true neighbours in play that fraction can take only eleven values, from zero up to one in steps of a tenth, so a histogram of it is an exact tally rather than a binning of something continuous. Over 500 logged queries the tally has almost nothing in the middle:

R@10   queries
1.0    ███████████████████████████████████  372
0.9    ████████                              41
0.8    ███                                   14
0.7    ██                                     9
0.6    █                                      6
0.5    █                                      5
0.4    █                                      4
0.3    ██                                     8
0.2    ████                                  17
0.1    ██████                                 24
0.0    ..                                     0

Two things about that block are worth checking rather than assuming, because everything below rests on them. It has exactly as many rows as R@10 has possible values, so no attainable score has been left out. And adding the counts downwards from the top reaches five hundred with nothing left over, so each of the 500 queries sits in exactly one bucket and there is no residual group outside the picture. Together those two facts license reading each row as a population count and comparing one row against another directly.

Three quarters of the queries are exactly right. Forty-one of them — the twenty-four scoring a tenth and the seventeen scoring two tenths — return one or two correct documents out of ten, which for a RAG pipeline, where the retrieved passages are placed in a language model's prompt and the answer is written from them, means the model is answering from material that is topically adjacent and factually irrelevant. The mean of 0.86 describes neither group. This is the same shape as a latency distribution where a mean of 3 ms and a p99 of 200 ms coexist, and it deserves the same response: the average is the wrong summary, and the interesting engineering question is who is in the tail. The shapes match and the remedies do not, because a slow query eventually returns the right answer while a query in this tail returns the wrong documents and stops.

Why the middle is empty#

The shape is not a quirk of this index, and the reason it is not is the most useful thing in the chapter. An approximate index does not compute a slightly wrong score for every stored document. It computes an exact score for the documents it visits, computes nothing at all for the documents it does not visit, and returns the best of what it visited. Approximation here is not noise added to a ranking. It is a set of documents that were never in the ranking to be ranked.

That distinction fixes the shape of the histogram, in two steps. A true neighbour is lost when the search never reaches it, which is a yes-or-no event rather than a small perturbation, so per-query recall is a count of how many of ten true neighbours the search happened to reach. And those ten are not ten independent draws. They are the ten vectors closest to the query, which puts them close to one another as well, so they usually occupy a single neighbourhood of the space. A search that arrives in that neighbourhood reaches most of them; a search that arrives somewhere else reaches almost none.

Both of those outcomes are common and the state between them is not, because landing half inside and half outside one tight neighbourhood is a narrower coincidence than either landing in it or missing it. That is why the bucket at nine tenths and the buckets at one and two tenths are populated while the buckets between them are nearly empty. The middle is not quite empty, and the queries sitting in it are the exception to the claim that a query's true ten occupy one neighbourhood: a query whose true top ten straddles two separated regions can have one region reached and the other missed, and it scores in the middle for exactly that reason.

The last step is what makes the loss predictable rather than merely lumpy. Whether a search reaches a neighbourhood is decided by the index's routing structure — which edges exist in an HNSW graph, which cell a vector was assigned to in an inverted-file index, the IVF family this topic works through alongside HNSW — and that structure is fixed at build time and is a property of the stored documents rather than of the query that arrives later. The same query therefore loses the same documents on every request, and two different queries pointing into the same badly-connected neighbourhood both lose. Loss decided by a fixed property of the data is loss with a population attached to it, and a population can be named, detected and fixed.

The tempting belief at this point is that the mean is a safety net: watch it, hold it above a threshold, and the index is under control. It is not, and the reason is exact. Take the 500 queries above and redistribute the same total loss evenly, so that every query returns roughly a seventh fewer true neighbours than it should. The mean is unchanged at 0.86 by construction, and nobody notices anything, because every answer set still holds most of its correct documents. Now concentrate the same total as the histogram actually does, and forty-one users get answers assembled from documents that are about the right subject and do not contain the answer. The mean does not move between those two worlds. A quantity that does not move when the dangerous property moves cannot be used to order two indexes by, and a threshold on it cannot tell the two worlds apart.

Four populations, four mechanisms#

The queries in the tail are not random and they are not the same as the queries a human would call hard. Four mechanisms account for most of them, and they can be told apart.

Queries whose neighbours live in sparse regions. High-dimensional embedding spaces have a well-documented asymmetry: some vectors appear in very many other vectors' nearest-neighbour lists, and some appear in almost none. The first group are hubs, the second antihubs, and the effect strengthens with dimension. In a graph index this asymmetry becomes connectivity. An antihub is rarely selected as anybody's link during insertion, so it accumulates few in-edges, and a search only finds it if it happens to enter its immediate vicinity. In an IVF index, where the space is carved into cells around a set of centroids and a query scans only the cells whose centroids are nearest it, the same vectors sit in thinly-populated cells whose centroids poorly summarise them. Documents about a niche subject that nothing else in the corpus resembles — a single compliance memo among 3M product descriptions — are systematically the hardest for the index to return, and they are often exactly what a specific query is looking for.

The difference between in-edges and out-edges is the part worth slowing down for, because it is easy to assume that a node with plenty of links is a node that is easy to reach. A greedy graph search moves by following edges away from wherever it currently stands, so the only edges that can ever deliver it to a given node are the edges pointing at that node; the node's own out-edges lead away from it and are no help in arriving. That much is a requirement of how traversal works. The design decision sits one level up: HNSW picks a new node's out-edges by finding that node's own nearest neighbours, which means a vector acquires in-edges only when some other vector's insertion picks it as one of that vector's nearest neighbours. A vector nothing in the corpus considers close is therefore chosen by nobody, ends up with in-edges only from whatever happened to be inserted beside it, and is reachable only from within its immediate vicinity. Sparse region, few in-edges, unreachable unless the search lands almost on top of it — each link in that chain is checkable on its own.

The asymmetry is easy to measure directly and is usually more extreme than people expect. Computing the exact 10-nearest-neighbour lists for all 3M vectors and counting how often each vector appears in someone else's list gives an in-degree distribution: on the product corpus, the median vector appears in 7 lists, the 99th percentile appears in 143, and 11% of vectors appear in zero. Those 11% are unreachable by any path that a graph index would naturally build toward them, because nothing considers them a close neighbour, and they are the documents that a query has to land almost exactly on top of to retrieve.

Queries with many near-ties. When the twentieth-best chunk is within 0.004 cosine of the tenth-best, the exact top-10 is one of many nearly-equivalent answers, and a beam of width 40 that explores a slightly different part of the neighbourhood returns a different valid subset. These queries score badly on R@10 and the user notices nothing, because the substituted documents are as good as the ones they replaced. Corpora with heavy boilerplate produce a lot of this: shared headers, repeated legal footers, and near-duplicate versions of the same page. This is the one population in the chapter where the metric moves and the experience does not, which is why it gets treated differently from the other three at every step below.

Queries far from what the index was built or trained on. Out of distribution is the usual phrase for it, and it means material whose position in the space the index's structure was never fitted to, so the structure describes it badly even though it is stored correctly. IVF makes this explicit, since the centroids were fitted to whatever was in the training sample, and a query about a product line launched after training probes cells whose centroids are a poor description of their contents. HNSW is less exposed but not immune, because the graph's link structure was chosen by a heuristic evaluated against the corpus as it stood. A concrete version: a support corpus in English gets 40,000 Spanish articles added, the multilingual embedding model places them in their own region, and queries in Spanish route through an entry point and upper layers that were laid down when no Spanish existed.

Documents that entered late. Incremental insertion into either index type gives new vectors worse treatment than the ones present at build. In HNSW, a node inserted into a saturated neighbourhood gets out-edges but few in-edges, which is the pocket from chapter 4. In IVF, it is assigned to the nearest existing centroid whether or not that centroid represents it. Both produce a recall that varies with a document's age in the index, which is the property that makes this population easy to detect and easy to misattribute — the symptom is "recently published articles never come up", and the first suspect is usually the ingestion pipeline.

Measuring which one you have#

The ground truth from chapter 2 already contains everything needed for the first two detectors, provided you kept the exact scores alongside the IDs and computed them for more than k results.

import numpy as np

def diagnose(per_query_recall, gt_scores, gt_ids, doc_added_at, k=10):
    """gt_scores: (nq, 100) exact scores, descending. doc_added_at: unix ts per doc."""
    # Local sparsity: how far away the 100th true neighbour is.
    sparsity = 1.0 - gt_scores[:, 99]

    # Tie density: how flat the score curve is just past the cutoff.
    tie_gap = gt_scores[:, k - 1] - gt_scores[:, 25]

    # Recency of the answer set: median insert time of the true top-k.
    answer_age = np.median(doc_added_at[gt_ids[:, :k]], axis=1)

    for name, signal in [("sparsity", sparsity), ("tie_gap", tie_gap),
                         ("answer_age", answer_age)]:
        r = np.corrcoef(signal, per_query_recall)[0, 1]
        lo = per_query_recall[signal >= np.quantile(signal, 0.90)].mean()
        hi = per_query_recall[signal <= np.quantile(signal, 0.10)].mean()
        print(f"{name:<12} corr={r:+.2f}  top-decile R={lo:.3f}  bottom-decile R={hi:.3f}")

# sparsity     corr=-0.61  top-decile R=0.412  bottom-decile R=0.981
# tie_gap      corr=+0.44  top-decile R=0.945  bottom-decile R=0.588
# answer_age   corr=-0.09  top-decile R=0.851  bottom-decile R=0.874

The sign of each correlation is fixed by how its signal was defined and carries no information at all. sparsity is one minus the score of the hundredth true neighbour, so it rises as the neighbourhood around the query thins out, and it must therefore correlate negatively with recall if it correlates with anything. tie_gap is the score at the cutoff minus a score some way below it, so it rises as the answer set becomes better separated, and it must correlate positively. A sign that came out the other way would be a bug in the signal rather than a discovery about the index, and that is worth knowing before reading anything into the two minus signs and the one plus.

The printed numbers say something specific about this index. Sparsity dominates: queries whose hundredth true neighbour is far away — that is, queries pointing into thinly populated regions — average R@10 of 0.41, against 0.98 for queries pointing into dense regions. Tie density is the second effect and it is the benign one, so a portion of the measured loss is not costing anybody anything. Insertion age shows no signal at all, which rules out the late-insert population and means a rebuild would not help. Faced with this profile, the correct move is a larger M, because sparse-region recall is a connectivity problem, and the correct move is not a rebuild and not a higher ef_search.

Of the two instruments printed per row, the decile means are the strong one and the correlation coefficient is the weak one. A correlation coefficient measures how well a straight line fits, and the variable being fitted here spends three quarters of its mass at exactly 1.0. No straight line fits that well, so the coefficient is pushed toward zero by the shape of the target rather than by the absence of an effect, and −0.61 understates a split that the deciles state plainly: 0.41 against 0.98 is not a tendency, it is two different systems sharing a hostname. Read the coefficients to rank the three signals against each other, and read the deciles to decide whether the leading one is worth acting on.

A different profile calls for a different move, and that is the point of running the correlation rather than reaching for the knob. An index showing answer_age correlation of −0.55 and flat sparsity has an incremental-insertion problem and wants a rebuild cadence. An index showing strong out-of-distribution segmentation — recall of 0.94 on English queries and 0.31 on Spanish — wants retraining on a representative sample, or a separate index per language.

What each population costs to fix#

The four mechanisms respond to different interventions, and the interventions differ by two orders of magnitude in cost, which is the practical reason to run the diagnosis rather than reach for whatever is nearest to hand.

The two tables agree on one row, and the agreement is worth stating because it is the only place here where three independently written columns pick out the same population. Near-ties is the single row whose relevance column reads "Rarely". It is the single row whose expected gain reads "None to recall". And it is the single row whose intervention leaves the index untouched. Those three columns were filled in from three different considerations — what a user experiences, what the recall number would do, and what an engineer would change — and they close on one row with no residual and no second candidate. What that licenses is treating tie loss as an error in the measurement rather than a defect in the index. It is the one component of the gap between 1.0 and 0.86 that should be subtracted before two indexes are compared, because leaving it in penalises an index for making an arbitrary choice among documents that were equivalent.

The intervention that is missing from that table is raising ef_search, and its absence is deliberate. Widening the beam recovers some of every population — a large enough frontier eventually stumbles into a sparse region — but it does so at a cost that scales with every query in the system, including the 372 that were already perfect. On the index above, going from ef_search = 40 to 400 raised the mean from 0.86 to 0.91 while raising p95 latency from 2.9 ms to 17 ms, and almost all of the recovered recall came from the tie population, which was not costing anybody anything. Paying six times the latency on all traffic to improve a metric on queries whose users were satisfied is a bad trade that looks like progress on a dashboard.

How the tail shows up in complaints#

The connection worth making explicit is that these populations have recognisable descriptions in the language product people use. "The search never finds the compliance docs" is the sparse-region population, because a handful of documents about a subject nothing else resembles are precisely the antihubs. "Results are fine but a bit random for common questions" is the tie population, and it is usually not worth acting on. "It works in English but not in German" is the out-of-distribution population. "New articles take a week to become findable" is the late-insert population, and it is the one most often misdiagnosed as an ingestion lag, because the documents demonstrably are in the index and can be retrieved by ID.

Running the correlation is what converts those reports into a decision. A complaint about compliance documents plus a sparsity correlation of −0.61 is a rebuild at larger M. The same complaint with a flat sparsity correlation and a strong recency correlation is a rebuild cadence, which is cheaper and faster to deploy. Without the measurement the two are indistinguishable from the outside, and the usual outcome is that both get tried in sequence over a month.

What the diagnosis needs before it can run#

Every detector in this chapter is computed from per-query recall, and per-query recall requires the exact ground truth and the approximate results side by side, which requires an index to exist and a query log to run through it. There is no way to look at a corpus and predict its recall profile from the corpus alone. What the population analysis buys is interpretation rather than prediction: once the per-query numbers exist, you can tell which of four quite different problems you have, and each has a different fix and a different cost.

One measurement is the exception to that and it is worth knowing about, because it costs nothing but compute: the in-degree census — the count, for every vector, of how many other vectors' exact 10-nearest-neighbour lists it appears in — needs no index at all. It cannot tell you what recall will be, and it does tell you which documents are at risk before a single graph edge has been written, which is enough to decide whether the sparse-region problem is worth planning for.

The tie-density result is also a warning about the metric itself. If a meaningful fraction of your measured loss is queries with dense near-ties, then R@10 is understating the index and the tie-tolerant variant from chapter 2 is the more honest figure. Chasing the last four points of a recall number that is partly measuring an arbitrary choice among equivalent documents is a way to spend a week of build time on nothing.

Results that are unrelated rather than merely worse#

The analysis is silent on the causes that are not approximation at all. A query returning plainly unrelated documents — not a worse neighbour, an unrelated one — does not belong to any of these four populations, because every mechanism here degrades the result set toward semantically adjacent material. Each of the four returns documents the search did reach, drawn from the query's own region of the space; none of them can produce a document from a region the search never entered. When the results are not adjacent, something structural is wrong with the index or the vectors in it, and chapter 8 is about telling that apart from ordinary loss.

The practical form of that distinction is the one to carry out of here. Loss that is approximation looks like a worse answer to the right question. Loss that is a bug looks like an answer to a different question, and no amount of ef_search, nprobe or rebuilding will move it, because none of those change what the vectors mean.

A mean recall figure describes a population that may not exist. The distribution behind it is what a user experiences, and in every index measured this way it separates into queries that are exactly right and queries that are almost entirely wrong, with membership decided by properties of the stored documents that were fixed when the index was built. Four mechanisms cover most of it, three correlations tell them apart in an afternoon, and each one points at a different intervention costing anywhere from minutes to a full rebuild. The wrong move, and the tempting one, is to widen the beam on all traffic to move a number that was never measuring the thing being complained about.

Before any of that, the tail has to become visible in the first place, which means measuring more than one index and more than one knob setting on your own data, with the memory and tail-latency numbers alongside the recall. That sweep is the next chapter, and it is what turns four separate curves into one decision.