Approximate Nearest-Neighbor Search and Vector Indexes

Exact search computes the true nearest neighbors under the chosen score. On a large corpus it becomes costly. How costly is a measurable quantity, not a reason to skip it.

The FAISS GPU paper measured it in 2017. A k-selection kernel ran at up to 55% of theoretical peak. The nearest-neighbour implementation was 8.5x faster than the prior GPU state of the art. Its abstract states the consequence: “Our implementation enables the construction of a high accuracy k-NN graph on 95 million images from the Yfcc100M dataset in 35 minutes, and of a graph connecting 1 billion vectors in less than 12 hours on 4 Maxwell Titan X GPUs.”

At those numbers the reference is affordable. A team that cannot say whether a recall loss came from the model or from the index is usually choosing not to run it. It is not being prevented from running it.

Approximate indexes trade memory, latency, build time, update behavior, and recall. The effective candidate set also depends on filtering, sharding, replicas, vector normalization, and index freshness. All of those are system choices. Evaluate them separately from the embedding model.

The failure this section would otherwise describe in the abstract has been measured in public. The Big ANN Challenge at NeurIPS 2023 ran a dedicated filtered-search track. The corpus was a 10-million-image slice of YFCC100M encoded with CLIP. Each image carried tags drawn from a vocabulary of 200,386. The query set was 100,000 queries, each with one or two mandatory tags. Entries were scored on the highest throughput reached at recall@10 ≥ 0.9.

The organisers’ own baseline filtered after the search: “In vector-first mode, the search is performed with a Faiss IVF index and vector results that do not satisfy the word constraint are removed from the result list.”

That baseline reached 3,253 QPS on the private query set. The winning entry, ParlayANN, reached 37,671 QPS — more than 11x. Same vectors, same tags, same recall floor. Where the filter runs is not a detail of plumbing. On this track it was the whole result.

Exact search is not really a competitor in this row. It is the reference the other two are measured against. ANN-Benchmarks treats it that way, carrying bruteforce-blas and bf on the same recall-against-queries-per-second axes as the approximate implementations.

Graph-based ANN buys recall at a given latency by spending memory. The result behind that sentence is HNSW, from Malkov and Yashunin in 2016. In their own words: “Starting search from the upper layer together with utilizing the scale separation boosts the performance compared to NSW and allows a logarithmic complexity scaling.” Their gains are claimed at high recall. That is precisely the qualifier a single quoted throughput figure drops.

Partition and quantization methods buy scale by accepting approximation. The canonical account is the 2011 product-quantization paper. Its IVFADC index is a coarse partition over compressed codes, with the number of visited cells left exposed as a knob.

Read the three together and the row stops being a ranking. It is one reference and two families with different knobs.

An index is a build artifact with a version, not a lookup table. Canonical embeddings are generated, the index is constructed, filtering and sharding decide eligibility, queries are served inside a latency budget. The last stage, refresh and rollback, is what decides whether a bad rebuild can be undone.

That last stage is structural rather than a matter of diligence. Absorbing updates into a graph index normally means building the index again from scratch. FreshDiskANN, a 2021 system from Microsoft Research, was built to escape that default, and its abstract names it: “To overcome this drawback, the current industry practice for manifesting updates into such indices is to periodically re-build these indices, which can be prohibitively expensive.”

Its alternative sustained thousands of concurrent inserts, deletes and searches per second on a billion-point index. That was on a single SSD workstation, while holding above 95% 5-recall@5. The authors put it at a 5–10x reduction in the cost of maintaining freshness. Either way the stage exists and carries a cost. What it must not be is unowned.

Model-index mismatch and no exact reference compound each other. Serving drifts onto stale vectors, or onto a different normalization. Without an exact search to compare against, nobody can say whether the lost recall came from the model or from the index.

The filtering failure has a literature and a vocabulary of its own. A 2025 survey in PVLDB names three execution methods: pre-filtering, post-filtering and inline filtering. It sets the target as “Stable recall: achieve consistent recall across queries, regardless of filter conditions or the execution method.” Every bullet below is a way of losing that consistency without losing a request.

Ground truth for an approximate index is exact search on a sample. It has to exist before a parameter sweep can mean anything.

Here is what a sweep looks like when it is done and published. The 2011 product-quantization paper holds index, dataset and code size fixed — the GIST set, 500 queries, 64-bit codes (m=8, k*=256), IVFADC with k′=1024 — and moves one knob, the number of visited cells. At w=1 the search takes 1.5 ms and finds recall@100 of 0.308. At w=8 it takes 8.8 ms for 0.682. At w=64 it takes 65.9 ms for 0.744.

That is a 44x latency increase buying 0.436 recall. Most of the recall arrives in the first few steps. Exhaustive ADC over all 1,000,991 code comparisons sits off to the side at 17.2 ms for recall 0.652. The authors are explicit that this is the only fair way to compare such systems: “The IVFADC and FLANN methods are both evaluated at different operating points with respect to precision and search time.”

Filtering patterns, update behavior and index health carry the rest of the operating point. Exercise filters on sparse markets, rare attributes and policy exclusions. Measure insertion, deletion, rebuild and rollback. Monitor version, freshness, sampled recall, empty results and shard skew rather than the error rate.