Approximate-nearest-neighbour recall is a product SLO

Approximate-nearest-neighbour recall is a product SLO. When an ANN index misses the relevant item that exact search would have returned, the consequence appears in the product: an agent forgets a prior constraint, a RAG answer lacks the decisive policy passage, or a recommendation excludes the right candidate. The service can remain fast and fully available while failing its actual purpose.

Approximation is a deliberate trade. HNSW searches a navigable graph; IVF searches selected clusters; product quantization compresses vectors; ANNOY and LSH narrow candidates through trees or hashes. Each saves latency, memory, or compute by accepting some probability of missing true neighbours. That probability is not an implementation footnote. It is the error budget of the retrieval product.

I define recall against an exact or higher-fidelity reference on a representative query set. Recall@k asks how many true top-k neighbours survive approximation, but the aggregate is only the start. The product SLO should be sliced by tenant, corpus size, metadata-filter selectivity, query class, language, freshness, and consequence. A 97% average can conceal severe loss on a small regulated tenant or on the exact filter pattern used for incident response.

Metadata filters deserve special treatment. Pre-filtering can shrink the candidate space safely but may reduce index efficiency; post-filtering can return too few results after the ANN search; in-graph filtering changes traversal behaviour. A relevant vector from the wrong tenant is not useful recall—it is a security failure. Tenant identity must remain an enforced index contract while recall is measured inside the authorized partition.

The SLO must travel with index operations. Insert patterns, deletions, graph connectivity, cluster training, quantization, compaction, and corpus growth can all change recall without an outage. I want canary queries after rebuilds, scheduled exact comparisons on sampled partitions, and release gates for parameter changes. Tail latency belongs beside recall because increasing search depth or probes can recover neighbours by spending time and compute. The acceptable point is a product decision, not a benchmark maximum.

Downstream evaluation then distinguishes a missed neighbour from a generation error. Retrieval failure and answer failure need separate evidence. I preserve candidate lists and compare them with judged relevance so a poor answer cannot be blamed vaguely on “the model.” Error budgets can then drive action: rebuild an index, raise search effort, change quantization, route a high-consequence query to exact search, or degrade honestly when the SLO cannot be met.

Capacity planning follows from the same contract. Corpus growth can force a team to add shards, compress vectors, or lower search effort, and every choice moves the recall-latency frontier. Forecasts should therefore include quality headroom, not just QPS and memory. An index at its recall limit has already exhausted capacity even if CPU remains available.

There is one precise concession: nearest-neighbour recall is not the same as task relevance. The mathematically closest vectors can still be useless because the embedding model, chunking, or query representation is wrong. ANN recall only measures loss introduced by approximation relative to that representation. It cannot certify the retrieval system as a whole.

That boundary makes the metric more useful, not less. Vector search is an indexing decision; ANN recall isolates whether the chosen index keeps its side of the contract. I would rather operate an explicit 95% recall SLO with exact fallback for critical paths than advertise millisecond latency over an unmeasured miss rate. Product reliability includes the evidence the system silently failed to retrieve.