An approximate index returns the neighbours its search effort happened to find

"Nearest neighbour search" names two quite different operations. One compares a query against every stored vector and sorts, which is correct by construction and expensive. The other visits a small, well-chosen fraction of the stored vectors and returns the best of those, which is fast and correct most of the time. A vector database usually does the second, a library index often does the first, and nothing in an application's code says which one it is getting.

That matters because of a specific failure report: recall drops after a migration, with the embedding model unchanged, a corpus whose documents nobody edited, and the same query set as before. Approximate search is one of three candidate causes and it is the one with a knob attached, so it is the one teams reach for. Turning that knob does move the number, which is exactly the problem — a knob that improves any recall figure regardless of what caused the drop is a knob that cannot tell you anything, and using it first buys latency-funded cover for a defect that stays in place and keeps growing. What follows is what the index is actually doing, how much approximation genuinely costs, and the one check that convicts or exonerates it outright.

What the index is actually searching#

An exact search compares the query against every stored vector and sorts. For a million 768-dimensional float32 vectors that means reading 3.07 GB from memory per query — a million vectors times 768 components times four bytes each — which at a realistic 20 GB/s of effective bandwidth is around 150 ms, since three gigabytes at twenty gigabytes a second is about a seventh of a second. Correct by construction, and far too slow to sit in front of a user-facing endpoint at any meaningful query rate.

This is the part of a migration that changes silently, because the local baseline frequently was not approximate at all. FAISS is a library of index types rather than a single index, and the two that appear in every tutorial — IndexFlatIP and IndexFlatL2 — are exhaustive scans with no graph, no clustering and no tuning parameters. A team that prototyped with IndexFlatIP over fifty thousand vectors got exact nearest neighbours for two years and never knew approximation was a category, because at that corpus size the exhaustive scan was fast enough that nobody had a reason to move off it. Migrating to a managed service is then the first moment an approximate index enters the system, and it enters at whatever defaults the vendor chose, which is a real change even though nothing in the application code mentions it.

Approximate nearest neighbour indexes, ANN for short, buy speed by not looking at most of the corpus. HNSW — hierarchical navigable small world, the structure behind most current implementations — builds a navigable graph in which each vector is linked to a few dozen neighbours across several layers, and answers a query by walking downhill through the graph from an entry point, maintaining a candidate list of size ef_search and stopping when no unvisited neighbour improves on the worst entry in that list. IVF, the inverted file index, partitions the space into nlist clusters and scans only the nprobe clusters whose centroids are closest to the query. Both are heuristics over the same idea: visit a small, well-chosen fraction of the vectors and hope the true nearest neighbours were in it.

The stopping rule is where the approximation lives, and it is worth reading as a mechanism rather than as a parameter. The walk keeps a list of the best candidates found so far. It expands the most promising unvisited one, adds its graph neighbours, and stops when nothing new improves on the worst entry already held. A larger list means a worse "worst entry", which means more candidates qualify as improvements, which means the walk keeps going and covers more of the graph. So ef_search is not a quality dial with an arbitrary scale — it is the width of the frontier the search is willing to hold open, and everything else follows from that.

They usually were. The parameter that decides how hard to look is also the parameter that decides how often the hope is disappointed:

Two of those columns are locked to each other and one is not, which is the whole shape of the trade. Latency tracks the fraction of the corpus visited almost exactly — the visited share doubles each row and so does the millisecond figure — because the cost of a query is the cost of reading vectors, the same bandwidth argument that produced the 150 ms for a full scan. The recall column does not track either of them. It climbs steeply at first and then flattens while latency keeps doubling, which is the characteristic trade of every approximate index. Getting from 0.93 to 0.985 costs 2.5 ms; getting from 0.985 to 0.998 costs another 10 ms for a thirteenth of the improvement.

The reason the two columns come apart is the structure of a graph walk rather than anything statistical. Doubling the frontier doubles the work because the walk visits twice as many nodes. It does not double the payoff, because the neighbours still missing after a wide search are the ones sitting behind the worst-connected parts of the graph, and reaching them requires the walk to pass through regions that look unpromising at every step. Effort spent late is spent on progressively harder targets, and the last few tenths of a percent of neighbours may not be reachable at any setting at all — a point the harder cases below return to.

Two different quantities both called recall#

The word "recall" in that table means something different from the word "recall" in an incident report, and conflating them is how this hypothesis gets over-weighted. ANN recall@10 measures agreement between the approximate index and an exact scan over the same vectors with the same metric — it asks whether the index found the neighbours that are actually nearest. Retrieval recall@10 measures agreement between the index and human relevance labels — it asks whether the neighbours that are nearest are the ones a person would have wanted.

The two are independent in both directions, which is what makes the distinction load-bearing rather than pedantic. An index can have ANN recall of 1.000 and retrieval recall of 0.2, because a perfect search over vectors that were embedded wrongly, normalised inconsistently, or scored with the wrong metric returns exactly the wrong documents with complete fidelity. And an index can have ANN recall of 0.93 and retrieval recall barely below its ceiling, because the neighbours it dropped were the ninth and tenth rather than the first. The two numbers are produced by entirely different failures, and only one of them is fixed by a parameter.

The one-line check, and what it rules out#

Separating them is a matter of running the same queries against an exact scan over the same vectors and measuring the overlap:

import numpy as np

V = np.array(index.fetch_all())          # every stored vector, as stored
ids = np.array(index.all_ids())
Q = np.load("queries.npy")               # 400 query vectors, same preprocessing

# exact top-10 under the index's own metric (dot product here)
exact = ids[np.argsort(-(Q @ V.T), axis=1)[:, :10]]
approx = np.array([index.query(q, top_k=10).ids for q in Q])

overlap = np.mean([len(set(a) & set(e)) / 10 for a, e in zip(approx, exact)])
print(f"ANN recall@10 vs exact: {overlap:.3f}")   # ANN recall@10 vs exact: 0.991

An overlap of 0.991 says the index is finding almost exactly what a brute-force scan would find, so approximation is responsible for at most a fraction of a point of the eighteen that went missing, and the problem is somewhere in the metric or the vectors. An overlap of 0.74 would say the opposite. Either way the check costs one pass over the corpus and answers the question outright, which is a better position than tuning a parameter until a number improves and never learning why.

The exact scan has to use the index's own metric and the vectors exactly as stored, unnormalised warts included. Scoring against freshly normalised vectors and comparing to what a dot-product index returned mixes two hypotheses together and produces a low overlap that proves nothing about the graph. The check is a comparison of two search strategies over one set of vectors, so anything that changes the vectors between the two sides changes what is being compared, and the resulting disagreement gets attributed to the graph.

On a 52,000-document corpus this check is decisive for a second reason, and the arithmetic says so before any code runs. Fifty-two thousand vectors at 768 components and four bytes each is 160 MB, and 160 MB at the same 20 GB/s that produced the 150 ms figure above finishes in about 8 ms — the same constant, applied to a corpus a twentieth the size, giving a time a twentieth as long. An exact scan at that size is not a research exercise; it is a routine query. A default HNSW configuration over a corpus that size also typically returns ANN recall above 0.99, because the graph has few enough nodes that even a modest candidate list covers the relevant neighbourhood. Approximation was never plausible as the cause of an eighteen-point drop there.

Why it goes last in the triage order#

Approximation erodes results from the bottom. When the graph walk terminates early, the entries it misses are the ones that were marginal — the ninth and tenth neighbours, whose scores sit a hair above the eleventh and twelfth. The true first neighbour is missed rarely, because it is the strongest attractor in the graph and almost every reasonable path leads toward it: the walk moves toward whatever improves its worst candidate, and the nearest vector improves on more candidates than anything else does, from more starting points. That is why an index at ANN recall@10 of 0.962 loses only about one to two points of retrieval recall@10 — most of the 3.8 percent of missing neighbours are positions the gold document was not occupying anyway.

To lose eighteen points of retrieval recall from approximation alone, an index would need ANN recall somewhere in the 0.70 to 0.80 range, which corresponds to search effort far below any shipped default — ef_search in the low teens, or nprobe=1 over a few thousand IVF clusters. Those are values you have to type. A managed service that shipped them would fail its own benchmarks. So the size of the drop is itself evidence: a large uniform move in an aggregate points at a rule applied to every document, and a small ragged move concentrated in the hardest queries points at the search effort.

The order is by cost of the check and by cost of being wrong. Checks 1 and 2 are single API calls that either exonerate a hypothesis or convict it, and if either convicts, the fix restores the missing recall without spending anything. Check 3 costs a full pass over the corpus, and its remedy — more search effort — buys quality with latency permanently, on every query, for the life of the index. Raising ef_search from 64 to 512 on the million-vector table above turns a 2.1 ms lookup into a 14 ms one, and at 40 queries per second that is the difference between one replica and something closer to five, which is a recurring infrastructure bill accepted in exchange for hiding a configuration bug that will keep growing.

The knob also has a ceiling that is not visible from the query side. ef_search decides how much of the graph is explored, but what there is to explore was fixed when the graph was built: M, the number of links each node keeps, and ef_construction, the candidate list used while inserting. A graph built with M=8 over a corpus with strong clustering can leave regions weakly connected, and no amount of search effort at query time reaches a node that has no path to it — recall climbs and then stops, at 0.97 or 0.94, with latency continuing to rise. Diagnosing that from the query side looks like diminishing returns on a parameter, and the remedy is a rebuild rather than a setting, which is another reason the tuning path is a worse first move than it appears. Graphs also degrade under heavy deletion, since most implementations tombstone a removed vector, marking it dead in place without rewiring the neighbours that still point at it, rather than repairing the links, so an index that has churned through several times its own size in updates can lose recall while every parameter still reads the same as the day it was created.

There is a further approximation worth knowing about even though it does not usually explain a migration regression, because it interacts with everything in this topic. Managed services frequently store vectors compressed by quantisation, which means holding each number at reduced precision rather than as a full float — scalar quantisation to int8, or product quantisation into a few dozen bytes per vector — which cuts memory by 4× to 32× and introduces a reconstruction error independent of the graph traversal. Quantisation error is relative to vector magnitude, so a corpus with a wide spread of norms quantises less evenly than a normalised one, and the same normalisation drift from the previous chapter degrades a quantised index a second time through a completely separate mechanism. That is a case worth holding onto, because it is the one place where the three hypotheses stop being independent: a normalisation defect can produce a genuine ANN recall loss, so the overlap check can convict the graph while the cause is upstream of it. The order of the checks is what keeps that from misleading anyone, since hypothesis 2 is settled before hypothesis 3 is asked. Systems that keep the compressed vectors for the graph walk and then re-score the shortlist against full-precision vectors, which is what most rescoring or refine options do, recover most of the loss for a small fixed cost; that pattern, along with disk-resident graph structures in the DiskANN family, is where the current work on this trade-off sits.

None of this is an argument against approximate search, which is the reason vector retrieval is affordable at all and which is delivering 0.99 agreement with brute force for a thousandth of the work in the table above. It is an argument about ordering. The index returns what its search effort reached, that effort is a number somebody chose, and the honest way to find out what it cost you is to compare against the answer effort-free search would have given — which on any corpus small enough to have this problem is a few milliseconds away. What the knob offers instead is a way to make a metric move without learning anything, and a knob will move any number far enough to close a ticket.

Suppose all three come back clean and the ranking is correct — the metric matches the model, the norms are uniform, the index agrees with a brute-force scan. There is still a decision left that none of it settles, which is where in the returned list to stop. A retrieval system that hands its top ten to a language model regardless of quality will feed it three good passages and seven irrelevant ones, and the usual instrument for cutting that list is a fixed score threshold that somebody chose once.