What "approximate" is allowed to mean

Every practical vector index is approximate, and the word does a lot of quiet work. It could mean the result is provably within some factor of the best. It could mean the result is correct with some probability. It could mean nobody knows and you should measure. These are three different promises, all called the same thing, and the index you are most likely to be running makes the third one.

The naive assumption

“Approximate” sounds like a controlled inaccuracy — a tolerance, like a floating-point epsilon. The natural reading of “approximate nearest neighbour” is: you get a neighbour that is nearly the nearest, and by turning a knob you can decide how nearly.

How that fails: the knob on your index is not a tolerance. Search breadth and probe count are budgets — how much work you are willing to spend — and no amount of them entitles you to a statement about the answer’s quality. Raising the budget reliably improves results, but there is no function mapping a budget to a guaranteed accuracy, because the mapping depends on the data. The word “approximate” here is descriptive, not contractual. To see why that isn’t a scandal, it helps to look at what a real guarantee would have to say.

The three kinds of promise

1. A proven ratio: c-approximate nearest neighbour

The theoretical formulation. Fix a factor c > 1. A search is a valid c-approximate nearest neighbour search if it returns a point p with

d(query, p)  ≤  c · d(query, true_nearest)

The returned point is at most c times as far as the best one. Set c = 1.1 and you are promised a neighbour within 10% of optimal distance. This is a strong, checkable, honest statement — the kind of thing you can build a proof around, and the standard formulation in the theory literature.

Note what it constrains: distance, not identity. A c-approximate answer may be a completely different document from the true nearest neighbour, as long as it is nearly as close. Under distance concentration that gap is wide: if the 1st and 1,000th neighbours are within 4% of each other in distance, a c = 1.1 guarantee permits returning the thousandth. The guarantee is satisfied and the result may be useless.

This is the first reason the theoretical formulation doesn’t transfer cleanly to practice. What you care about is which documents came back — the identity — and a ratio bound on distance is a weak proxy for that precisely in the regime where search is hard.

2. A probability: what LSH offers

Locality-sensitive hashing makes a probabilistic promise, and it is the only mainstream family that makes a real one.

The construction gives a hash family where the probability of two points colliding is a decreasing function of their distance. Amplification — requiring agreement across several hashes, and repeating across several independent tables — lets you tune those probabilities. The result is a statement of this form:

With probability at least 1 − δ, the search returns a point within c times the distance of the true nearest neighbour, using space and time bounded by a stated function of n, c and δ.

That is a genuine contract, derived from the construction rather than measured. You choose δ, the construction tells you how many tables that costs, and the guarantee holds for any dataset, because the randomness is in the hash functions and not in the data.

The catch is the price. The bound is over the worst case, so the number of tables required for a convincing δ is large, and the memory follows. Which is why the family that offers the only real guarantee is not the family most people run: the guarantee is data-independent, and paying for worst-case behaviour on data that isn’t worst-case is expensive.

3. No guarantee at all: graph and cluster indexes

Here is the honest description of what HNSW and IVF give you.

A graph index explores a bounded number of nodes and returns the best it found. Its stopping rule is sound with respect to the graph — it halts when nothing unexplored can improve the current best along the edges it has. But the graph is an approximation of the proximity structure, built greedily and pruned heuristically, and there is no theorem saying the true nearest neighbour is reachable from your entry point within your budget. If the graph has no edge into the right region from anywhere you looked, the answer is simply not available to you, and the search cannot tell.

A cluster index exhaustively scans the vectors in the probed partitions. Within those partitions the answer is exact. Across the partition boundary there is no promise whatsoever: the true nearest neighbour may sit in the cell you didn’t probe, and in high dimensions that is the ordinary case rather than a rare accident.

Both are heuristics with excellent empirical behaviour and no bound. That is not a criticism. It is the trade that made the field practical: they exploit the structure real data has, instead of defending against structure it doesn’t have, and they beat the guaranteed methods by a wide margin on real collections. But it means the accuracy of your index is an empirical property of your data, your parameters and your build — not a property of the algorithm — and the only way to know it is to measure it.

What can be said without measuring

A short list of statements that are true by construction, and therefore free.

• Exact within the scanned set. Whatever candidates an index examines, it ranks them by true distance (unless quantization is in play, in which case it ranks them by an approximation and a rescoring stage restores exactness for the finalists). The approximation is always about which candidates were examined, never about arithmetic errors in comparing them.
• Monotone in budget, in expectation. More probes or more breadth examines a superset of what a smaller budget would examine, in the usual implementations, so results do not get worse as you spend more. Individual queries can still move around under a rebuild.
• Exact at maximum budget. Probe every cluster and you have scanned everything. Set search breadth large enough and a graph search degenerates towards visiting the whole reachable component. Both cost more than a flat scan, so this is a sanity check rather than a mode of operation — but it does mean the recall ceiling is 1.0 and the curve is continuous up to it.
• Recall is measurable, cheaply enough. A few hundred queries, exact ground truth computed once by brute force, and you have the number. This is the substitute for a proof and it is a good one, because it is measured on the data you actually have.

Why this matters operationally

Three practical consequences follow from “no guarantee”, and they are the reason to be clear about it.

Recall is not a property you set, it’s a property you observe. There is no configuration value that means “give me 95%”. You sweep a budget, measure, and choose. And since it’s a property of the data, it must be re-measured when the corpus or the model changes.

The same query can return different results after a rebuild. Graph construction depends on insertion order and randomness; cluster training depends on the sample. Neither is deterministic across builds, so a result set is not reproducible in the way a database query is. If something downstream assumes stability — a cached answer, a regression test asserting exact IDs — it will break for reasons that aren’t bugs.

Averages conceal the failures. Approximation error is not spread evenly. It concentrates on queries in sparse regions, short queries, and queries near partition boundaries. Mean recall of 0.95 is consistent with most queries perfect and a recognisable minority at 0.3. The distribution is where the information is, and the worst queries are usually one identifiable category.

The reason to insist on the distinction is that it tells you where to look when results disappoint. If your index makes no guarantee, then “recall is lower than I want” is a tuning question with a known procedure. But if recall is already high and the results are still poor, no amount of budget helps — you are asking a faithful index to fix a map that doesn’t separate your data.