Approximate Nearest Neighbor (ANN)

Approximate Nearest Neighbor (ANN) search is the class of algorithms that powers fast similarity lookup in a vector database. Exact nearest-neighbour search must compare a query vector against every stored vector — a linear scan that becomes hopeless at millions or billions of high-dimensional embeddings. ANN algorithms instead examine only a carefully chosen fraction of the space, accepting a small, measurable loss in accuracy in exchange for latency reductions of several orders of magnitude. Practically all production similarity search — including every self-hosted retrieval-augmented-generation stack — runs on ANN.

Why exact search fails at scale

The obstacle has a name: the curse of dimensionality. In the hundreds-of-dimensions spaces where text embeddings live, the space-partitioning tricks that make low-dimensional lookups fast (the k-d trees of classic computational geometry) degrade toward brute force, and distances between random points concentrate so that clever pruning saves little. ANN research is essentially a catalogue of ways to spend preprocessing time and memory on an index whose structure lets queries skip the vast majority of comparisons while still landing on (almost all of) the true neighbours.

The two dominant index families

HNSW (Hierarchical Navigable Small World) builds a multi-layer proximity graph: sparse upper layers provide long-range hops, dense lower layers provide precision, and a query greedily walks downward from a random-ish entry point toward its neighbourhood. It delivers high recall at low latency and handles incremental inserts well, at the cost of substantial memory (the graph lives alongside the vectors) and slower index builds. IVF (Inverted File) takes the clustering route: vectors are partitioned with k-means into cells, and a query searches only the handful of cells nearest to it. IVF is often paired with Product Quantization (PQ), which compresses each vector into compact codes, shrinking memory dramatically and enabling billion-scale indexes on modest hardware — with some recall sacrificed to the compression. Most self-hosted vector stores default to HNSW; IVF-PQ appears where memory is the binding constraint.

The recall/latency dial

Every ANN index exposes parameters that move you along a curve between speed and accuracy — recall being the fraction of true nearest neighbours actually returned. Searching more graph neighbours (HNSW's search breadth) or probing more clusters (IVF) raises recall and costs latency; index-build parameters trade construction time and memory for a better ceiling. The sovereign-stack framing is refreshingly concrete: you are tuning software to fit hardware you own, not renting headroom. For a personal or small-team corpus — thousands to a few million chunks — even conservative settings give effectively perfect recall in single-digit milliseconds on a desktop, and below roughly a hundred thousand vectors a brute-force scan is often fast enough that no index is needed at all. Measure before optimizing.

Real deployments also contend with filtered search — "nearest neighbours where the document is tagged 'firmware' and dated this year." Metadata filters interact awkwardly with ANN indexes: pre-filtering shrinks the candidate set in ways a graph index was not built for, while post-filtering can starve the result list when the filter is selective. Vector databases differ meaningfully in how well they handle this, which makes filtered-query behaviour — not headline recall benchmarks — the most useful thing to test when choosing a store for a corpus that will be sliced by product, language, or date. The same advice applies to hybrid search, where ANN results are fused with classic keyword scores — the fusion quality varies more between implementations than the raw vector search does.

ANN is what makes private, on-premise semantic search feasible on a single workstation: it lets a self-custody compute setup query a large corpus in milliseconds without shipping documents to a third party — the retrieval half of a fully local AI stack, feeding context to on-device inference.