Systematically wrong neighbours are an index bug, not approximation noise

An incident report reads: since roughly the start of the month, about one query in seven returns documents with no apparent relationship to the question. No errors in the logs. p50 and p95 latency unchanged from the previous quarter. The embedding model version is pinned and confirmed identical between indexing and query time, and the distance function configured on the index matches what the model was trained for. The first suggestion in the thread is to raise ef_search, because it is the only thing anyone can change without a rebuild.

Four terms carry the argument below. Index recall, written R@10 when it is measured over ten results, is the overlap between what an approximate index returns and what an exhaustive scan of the same stored vectors would have returned for the same query — a property of the index alone, not of whether the documents answer the question. ef_search and nprobe are the query-time knobs of the two index families, controlling how wide a beam an HNSW graph walk keeps and how many cells an inverted-file index scans. A tombstone is a flag marking a stored entry dead while leaving it physically in place. And a corpus here is the set of documents that were embedded and stored, which may differ from the set of documents the application believes it has.

Reading the shape of the number#

Before touching the knob, the number itself is worth reading. Chapter 5 established that approximation loss concentrates on a characterisable population rather than spreading evenly — the queries pointing into sparse regions, the queries with many near-ties, the queries far from the distribution the index was built on, and the documents inserted after the build. So a concentrated failure is not by itself surprising.

What does not fit is the character of the failure. Every mechanism in that chapter degrades a result set toward semantically adjacent material — the seventh-nearest chunk instead of the second, a different member of a near-tied group, a document from a thinly populated neighbourhood. None of them produce documents with no apparent relationship to the question. The reason is structural: each of those mechanisms is a failure to search far enough in the right region, and the results it returns are still the nearest things the search did reach. A search that reaches too little of the right region returns worse neighbours; it has no way to return non-neighbours. That symptom means the index is ranking by something other than proximity in the space you think it is in, or is returning results from a version of the corpus that no longer exists, and both are fixable bugs rather than a curve you are sitting too low on.

The stability of the number is the second clue. Approximation loss moves when traffic mix moves, because the population that loses is defined by query geometry. A figure that sits at 15% week after week points at a fixed fraction of something: a batch of documents, a shard, a subset of the corpus with a property the rest does not have.

Fifteen per cent is also a large number in the wrong way, and the arithmetic showing why is worth doing. An index at a mean R@10 of 0.86 is losing an average of 1.4 documents out of every 10, since ten results at eighty-six per cent recall means about eight and a half correct ones. That average is spread over a tail of queries that lose most of theirs — but those queries still get some correct results, because the beam is still searching the right region. A query returning ten unrelated documents has zero correct results, and zero is a different kind of number from 1.4. There are only three ways to reach it. The search can be looking in a different region of the space from the one the answer is in. It can be ranking by a quantity that is not proximity, so that the ordering it produces is a ranking of something else. Or something can be filtering out everything that was found, after the search has found it. All three of those are the sort of defect that has a single root cause and a single fix, which is why the investigation is short if it is done in the right order.

That three-way split is worth holding onto, because everything in the rest of this chapter is a branch of it. Under-provisioned search and tombstoned deletes are both ways of looking in the wrong region. Unnormalised vectors and mixed model versions are both ways of ranking by the wrong quantity. A permission filter applied after retrieval is the third. A mechanism that is not on the list still has to be an instance of one of the three, so the way to extend the list is to ask which of the three a candidate belongs to rather than to collect symptoms.

There is one more thing to read in the report, and it is the part that reads as reassurance. Four facts are offered as having been checked: no errors in the logs, latency unchanged, the model version pinned, the distance function matching. Every one of those is unchanged under all three causes below. A wrong neighbour is a valid answer, so nothing raises an exception. Tombstones keep work constant by construction, so latency is exactly what they predict. And the model version and distance function are configuration values, one setting each for the whole index, while the dangerous property — which model produced this vector, what magnitude this vector has — varies from vector to vector. A single configuration value cannot vary per vector, so it cannot discriminate between corpora whose vectors differ. A quantity that stays put while the dangerous property moves cannot be used to rule anything out, however carefully it was verified.

Three causes and the check that separates them#

An under-provisioned search is the benign cause and the one worth ruling out first, because ruling it out is a fifteen-minute sweep against a copy of the index. A corpus that has grown from 1M to 4M vectors while nprobe stayed at 8 is scanning a quarter of the fraction it used to; an HNSW index whose ef_search was tuned when the corpus was half the size sits lower on its curve than it did. The signature is that recall rises monotonically toward exact as the knob rises, and that the queries which recover are the sparse-region ones from chapter 5. If the curve plateaus below what you need, the ceiling is the build parameters and the fix is a rebuild at larger M, per chapter 4.

The quarter in that first sentence carries an assumption worth making visible, because it decides which symptom growth produces. It reads the corpus as having been reindexed with nlist — the number of cells an inverted-file index divides the space into — scaled up to keep the cells the same size, which is the usual reason to change nlist at all. A fourfold corpus then has four times as many cells, so the same eight cells are a quarter of the share they once were, and recall falls while the work per query stays flat. If nlist was instead left where it was, eight cells are still the same share of the space and each holds four times as many vectors, so the work per query quadruples and growth shows up as latency rather than as lost recall. Which of the two you are in is readable off which number moved, and an incident whose p50 and p95 are unchanged is in the first.

Tombstoned deletes are the cause that most closely matches the incident above. When 30% of documents have been deleted from a live HNSW index over several months with no rebuild, what happens is not that the index gets smaller or faster. The deleted nodes are marked and kept, because the graph's connectivity depends on them as routing elements, so every search still traverses them, still computes distances against them, and then discards them at the end — which means search work and memory stay near their old levels while the number of live results the beam can actually collect shrinks. A search at ef_search = 100 that spends 30 of its candidate slots on tombstones is effectively running at ef_search = 70 for result-collection purposes, and the queries whose true neighbours sit behind a wall of dead nodes lose them entirely.

The step from a thirty per cent dead index to thirty dead slots in a hundred-wide beam is the one to check rather than assume. The beam is filled by proximity, and tombstones were live nodes once, distributed through the space the same way the live ones are — so a query landing anywhere in particular meets dead nodes at roughly the rate they occur in the index overall. That reasoning holds while the deletions are spread across the space. When a whole subject area is deleted at once, queries pointing at that area meet a dead fraction far above the index average while queries elsewhere meet almost none, and the loss concentrates on a subset of traffic instead of thinning every query a little. A stable fraction of queries failing badly, which is what the report describes, is the concentrated case rather than the uniform one.

# Check 2a: does the index hold more elements than the application has documents?
print(hn.get_current_count(), db.execute("select count(*) from chunks").scalar())
# 4_180_339   2_930_112     -> 1.25M tombstoned, 30% of the index

# Check 2b: is the work per query flat while quality falls?
faiss.cvar.indexIVF_stats.reset()
ivf.search(queries, 10)
print(faiss.cvar.indexIVF_stats.ndis / len(queries))   # distance computations/query
# 37_412 today vs 36_980 recorded six months ago, on a corpus 30% smaller

The two checks come from two different libraries because that is where each counter lives: get_current_count is hnswlib reporting how many elements the graph holds, and indexIVF_stats.ndis is FAISS reporting how many distance computations a search performed. Reading the first, the gap between the element count and the live document count is the 1.25M tombstones, and the 30% in the comment is thirty per cent of the index rather than of the live document count — against the live count the same 1.25M would read as more than forty per cent. Getting that denominator right is the whole check, since the quantity that matters is the dead share of what a search traverses, and what a search traverses is the index.

The second reading is the same fact taken with a different instrument. If the dead nodes had genuinely been removed, work per query would have fallen roughly in proportion to the live corpus, because an inverted-file search computes distances against the contents of the cells it probes and those cells would be smaller. Instead 37_412 today against 36_980 six months ago is essentially unchanged, on a corpus 30% smaller. Two independent measurements — a count of elements and a count of arithmetic — land on the same conclusion, and neither could be explained by the other being miscalibrated.

The two readings together are conclusive: the application knows about 2.93M documents, the index is holding 4.18M elements, and per-query work has not fallen even though the live corpus shrank. What they are conclusive about is that tombstones are present. They are not yet a statement about how much of the 15% tombstones explain, which is a separate question needing a separate instrument. Rebuilding on a copy and re-measuring recall against the same ground truth confirms the mechanism — recall returns to its old value and per-query distance computations drop by roughly the tombstone fraction. Raising ef_search in this state makes things slightly better and mostly worse, because the wider beam traverses more dead nodes and buys latency for a fractional recovery.

Vectors that went in unnormalised under an inner-product distance is the cause that produces the most alarming results and is the easiest to check. The metric question itself belongs to 8.5; what matters here is the index-side manifestation. Under inner product, a vector's magnitude scales its score against every query, so a batch that skipped the normalisation step — a re-embedding job that wrote raw model output, or a migration that bypassed the ingestion path — produces documents that outscore genuinely closer neighbours for no reason connected to meaning. If that batch is 6% of the corpus with norms in the 4 to 18 range while everything else sits at 1.0, it will hijack the top-10 for every query whose true neighbours score below the inflated ones, and that is a fixed fraction of queries determined by score distributions rather than by anything about the query.

norms = np.linalg.norm(corpus, axis=1)
print(np.percentile(norms, [1, 50, 90, 95, 99]))
# [0.9999 1.0000 1.0001 3.8721 17.442]   -> a tail, not a metric mismatch

# Do the hijackers show up everywhere?
_, ids = hn.knn_query(queries, k=10)
hits = norms[ids.ravel()]
print((hits > 1.01).mean())          # 0.31 of all returned results
print((norms > 1.01).mean())         # 0.061 of the corpus

That percentile array is read by its gaps rather than its levels. From the 1st percentile to the 90th the norms move from 0.9999 to 1.0001, a span of two ten-thousandths, which is flat to the precision printed. From the 90th to the 95th they jump to 3.8721, close to four times higher. From the 95th to the 99th they jump again to 17.442. A quantity that is flat across ninety percentiles and then steps twice is two populations sitting in one array, and a single spread of values — which is what a metric mismatch would produce, everything shifted together — cannot look like that. The two step values also bracket the stated inflation: 3.8721 sits just under the bottom of the 4 to 18 range and 17.442 just under the top, so the percentiles reproduce the range rather than merely being consistent with it.

The array also locates the boundary. The 90th percentile is clean and the 95th is not, so the contaminated share lies somewhere between five and ten per cent — and the mask on the following line puts it at 0.061 of the corpus. Two instruments computed from the same vectors, one a set of percentiles and one a fraction, agreeing on the size of the batch.

Six per cent of the corpus supplying thirty-one per cent of all returned results is not a ranking a distance function produced; it is magnitude leaking into the score. What makes that comparison a proof rather than an impression is that the expected value is computable without knowing anything about the queries. A subset picked out by a processing accident has no reason to sit closer to incoming questions than the rest of the corpus does, so under a correct ranking a 6% slice should supply about 6% of returned slots. It supplies about five times that. The excess is the whole signal, and it is available before any judgment about whether a returned document is relevant.

One comparison that should not be made is between that 0.31 and the report's 15%, because they count different things: 0.31 is the share of returned slots occupied by inflated documents across a set of queries, while 15% is the share of queries whose results are plainly wrong. A query can absorb an inflated document or two and still return useful ones. There is also a second, quieter consequence: an HNSW graph built over those vectors chose its links using the same broken comparison, so renormalising in place does not repair it and the index has to be rebuilt from corrected vectors.

Two things fall out of that table that are not obvious from the flowchart. The first is that each check moves under exactly one cause and stays put under the other two — a knob sweep tells you nothing about tombstones, an element count tells you nothing about magnitudes. Three checks are enough for three causes because of that one-to-one property, and it is the exact complement of the four reassurances in the report, which stay put under all three. The second is that the last column has a single "Yes", and it sits on the one row whose check is the ef_search sweep. That row's diagnostic and its remedy are the same action, so running the sweep either fixes the problem or eliminates the cause, and no other check has that property. That is why the sweep goes first even though the norm histogram is cheaper by minutes.

Reproducing it before fixing it#

The temptation to skip straight to the fix is strongest with the third cause, because the norm histogram is so conclusive that reindexing feels obviously correct. Reproducing first is still worth the hour, because it is the only way to know that the cause you found accounts for all 15% rather than 4% of it. A check establishes that a cause is present; it never establishes that the cause is sufficient, and those are different claims needing different instruments. Presence is a property of the corpus and a count settles it. Sufficiency is a claim about how much of the observed failure rate the mechanism generates, and only rebuilding the mechanism and measuring its output settles that.

The reproduction is small: take 200 vectors from a healthy corpus, scale 6% of them by a factor drawn from 4 to 18, build an index over the result, and check that the fraction of queries whose top-10 is contaminated lands near the observed number. If it lands at 3%, there is a second cause still in the system.

def reproduce_magnitude_bug(clean, queries, frac=0.06, lo=4.0, hi=18.0, seed=0):
    rng = np.random.default_rng(seed)
    dirty = clean.copy()
    victims = rng.choice(len(clean), int(frac * len(clean)), replace=False)
    dirty[victims] *= rng.uniform(lo, hi, size=(len(victims), 1)).astype(np.float32)

    idx = hnswlib.Index(space="ip", dim=clean.shape[1])
    idx.init_index(max_elements=len(dirty), M=32, ef_construction=200)
    idx.add_items(dirty, np.arange(len(dirty)), num_threads=16)
    idx.set_ef(200)
    ids, _ = idx.knn_query(queries, k=10)

    victim_set = set(victims.tolist())
    contaminated = [any(i in victim_set for i in row) for row in ids]
    return np.mean(contaminated)

print(reproduce_magnitude_bug(clean_corpus, queries))   # 0.148

The function is constructed so that the only difference between it and a healthy system is the defect under test. It starts from clean vectors, applies exactly the corruption the norm histogram described — the same 6% fraction, the same 4 to 18 range — builds the same kind of index over the result, and then counts queries rather than documents, because queries are what the report counts. That last correspondence is what makes the comparison legal: a reproduction that measured the share of contaminated result slots would produce a number that cannot be set against the report's fifteen per cent at all.

Fourteen point eight per cent against an observed fifteen is a match, and it is a match that took twenty minutes of compute to obtain. Had it returned 0.04, the correct conclusion would have been that the norm anomaly is real and explains a quarter of the problem, and that the investigation continues.

The same applies to the patch. Fixing the norms and rebuilding is not verified by the absence of complaints; it is verified by running the chapter 2 harness against fresh ground truth computed from the corrected vectors, and confirming that mean R@10 and the per-query distribution both return to where they were before the incident. A patch that restores the mean while leaving a bimodal tail has fixed one thing and left another.

Mixed model versions and the filter around the index#

The confirmation in the incident report was that the model version is pinned and the distance function matches. Neither statement rules out a mixed index. If a re-embedding to a new model version was run as a background job over three weeks and stalled, the index now holds vectors from two models in one space, and the two populations are mutually incomparable no matter how correct each is on its own. The mechanism is worth spelling out, because "incomparable" sounds like a matter of degree and is not. A distance function combines the two vectors coordinate by coordinate, and a coordinate only carries meaning relative to what the model that produced it put on that axis. Two models put different things there. So a score computed across the two is arithmetic performed on axes that do not correspond, and it returns a number of the usual size and shape while meaning nothing. The check is a stored model version per vector and a count by version, and it belongs on the list precisely because it survives the confirmation everyone reaches for — a pinned version is one value for the whole deployment, and what is at issue is a value that varies per vector. The same is true of dimension truncation applied inconsistently, where half the corpus was embedded at 1024 dimensions and half at a truncated 512 and padded.

There is also a category the three checks cannot see at all, which is the filter path around the index. A tenant or permission filter applied after retrieval will silently empty a result set when the top-k happens to contain nothing the user may see, and the service then returns whatever the fallback path produces — often a second query with the filter relaxed, or the tail of the candidate list. That produces exactly the incident's symptoms and none of the three signatures, because the index is behaving perfectly. Checking it means logging the pre-filter and post-filter result counts and looking at the distribution of the difference; a spike of queries where post-filter count is zero is conclusive and is not something recall measurement will ever surface, since the ground truth was computed without the filter.

That last exclusion is worth stating as a general property rather than as one more item. Index recall is measured by comparing the index against an exhaustive scan of the same stored vectors, so it can only ever see defects that live between the query and the stored vectors. A defect upstream of storage, such as the wrong vectors having been written, moves the ground truth along with the results and cancels out. A defect downstream of retrieval, such as a filter, happens after the measurement ends. Both are invisible to a perfect recall number, which is why a recall check is a necessary instrument and never a sufficient one.

None of this is an argument that approximation loss is unimportant. The four populations from chapter 5 — sparse regions, near-ties, out-of-distribution queries and late inserts — are real and they are the reason index recall needs measuring on a schedule. The argument is about ordering: a symptom of plainly wrong neighbours at stable latency is evidence against ordinary approximation, and the three checks above take under an hour between them, while a ef_search increase applied without them costs latency on every query in the system and, for two of the three causes, changes nothing.

What carries forward from this topic is a small number of things that live in the operational surface rather than in a design document. Ground truth for a fixed query set, versioned with the corpus snapshot, regenerated on every rebuild. A recall check that runs after every reindex and fails the deploy if mean R@10 drops more than a couple of points, with the per-query distribution recorded alongside the mean so a bimodal tail is visible. Element count against live document count as a monitored ratio, which is the cheapest possible tombstone alarm. A rebuild cadence chosen from the churn rate rather than from when somebody notices. And the sweep from chapter 6 rerun when the corpus triples or the embedding model changes, because the operating point you chose was a measurement of a corpus that no longer exists.