Approximate Nearest Neighbor(ANN) Algorithms: The Search Techniques Powering Every Vector Database

Introduction

Previous post introduced the vector database as a system built around an “ANN index,” and named a few algorithms in passing — HNSW, IVF, product quantization. This post opens the hood fully. Every vector database you’ll ever use is, underneath its API, a wrapper around one or more of the algorithms covered here. Understanding them at this level is what separates “my retrieval feels slow/inaccurate and I don’t know why” from being able to look at a config and know exactly which knob to turn.

Exact Search and Its Limits

The starting point for all of this is k-Nearest Neighbors (kNN), sometimes called exact nearest neighbor search: given a query vector, compute its distance to every vector in the collection, then return the k closest ones, guaranteed correct.

kNN is conceptually the simplest possible retrieval algorithm, and it’s exact — there’s no approximation, no risk of missing a true match. Its cost is equally simple to state: computing distance to every vector means search time grows linearly with collection size. Double the vectors, double the search time, every time, with no shortcuts. For a few thousand vectors this is unnoticeable. At tens of millions, it becomes a hard bottleneck no amount of better hardware fully escapes, since the problem is algorithmic, not just computational.

This is the exact ceiling that motivated the entire field of approximate search: if exact correctness is what’s making search slow, what happens if we accept results that are almost certainly correct in exchange for search times that don’t scale linearly?

Approximate Search: Trading a Little Accuracy for a Lot of Speed

Approximate Nearest Neighbor (ANN) search is the family of algorithms built around that trade-off. Rather than guaranteeing the exact true top-k results, ANN algorithms return results that are correct with very high probability — typically 95–99%+ of the true top-k, depending on configuration — in exchange for search times that scale sublinearly, often close to logarithmically, with collection size.

This isn’t a hack or a compromise born of laziness — it reflects a genuine insight about high-dimensional spaces: precomputing clever structure ahead of time (at indexing time, when you’re not in a hurry) lets you avoid most of the distance computations at query time (when you are). Every algorithm below is a different strategy for building that structure.

The practical framing worth internalizing: "accuracy in an ANN system is a dial, not a fixed property of the algorithm." Every ANN method exposes parameters that trade recall (how often you get the true nearest neighbors) against latency and memory — which is why benchmarking your specific configuration on your specific data matters more than trusting a vendor’s headline numbers.

Hierarchical Navigable Small World (HNSW) is the dominant ANN algorithm in modern vector databases, and it’s worth understanding at a real mechanical level, not just the map analogy from Vector DB.

HNSW builds a multi-layer graph where each vector is a node connected to a handful of its nearest neighbors. The key structural idea is the hierarchy: the top layer contains only a small fraction of the vectors, connected by long-range edges that span large regions of the space; each layer beneath adds more vectors and denser, shorter-range connections, until the bottom layer contains every vector in the collection.

A query starts at a single entry point in the sparse top layer and greedily moves toward whichever neighboring node is closest to the query vector — a fast, coarse jump across the space. Once no closer neighbor exists at that layer, the search drops down one level and repeats the same greedy process with finer-grained connections, progressively refining its position until it reaches the bottom layer and returns the closest nodes found there.

This is why HNSW achieves near-logarithmic search time: most of the “distance traveled” toward the answer happens in the cheap, sparse upper layers, with only fine-grained refinement happening in the expensive, dense bottom layer. The trade-off is memory: HNSW stores an entire graph structure — every node’s edges — in memory, which makes it fast but relatively memory-hungry compared to some alternatives below.

IVF: Cluster First, Search Second

Inverted File Index (IVF) takes a fundamentally different approach: instead of building a navigable graph, it partitions the vector space into clusters ahead of time, typically using an algorithm like k-means, and assigns every vector to its nearest cluster center.

At query time, IVF first identifies which cluster centers are closest to the query vector, then searches only within those clusters’ vectors — ignoring the rest of the collection entirely. This is the “inverted” part: instead of scanning every vector, you look up which clusters are relevant, the same conceptual move as the inverted index from Information Retrieval Fundamentals just applied to geometric neighborhoods instead of keyword occurrence.

The key tunable parameter is nprobe — how many clusters to search, not just the single nearest one. Searching more clusters improves recall (you’re less likely to miss a true neighbor that happened to land in a nearby-but-not-closest cluster) at the direct cost of speed. IVF’s big advantage over HNSW is memory efficiency — it doesn’t need to store a full graph — which is precisely why it’s frequently combined with product quantization (below) for very large collections where memory, not just speed, is the binding constraint.

Product Quantization: Compressing the Vectors Themselves

Product Quantization (PQ) attacks a different part of the problem entirely: instead of speeding up search, it shrinks the storage footprint of the vectors, which indirectly speeds up search too, since less data means less memory bandwidth spent moving it around during comparisons.

The mechanism: PQ splits each high-dimensional vector into several smaller sub-vectors, then, for each sub-vector segment, learns a small set of representative “codebook” centroids (typically 256 per segment) via clustering. Each sub-vector is then replaced by the ID of its nearest centroid — a single small integer instead of dozens of floating-point numbers. A 1,024-dimension vector, stored originally as 1,024 floats, might be compressed to just a few dozen bytes this way.

The cost is precision: PQ is inherently lossy — you’re approximating each original sub-vector by its nearest learned centroid, so some distance-computation accuracy is sacrificed for a large reduction in memory footprint. This is almost never used as a standalone search method; it’s typically layered on top of IVF (searching within the relevant clusters using compressed, quantized vectors) to handle collections at a scale — hundreds of millions to billions of vectors — where storing full-precision vectors in memory simply isn’t feasible.

ScaNN and DiskANN: Purpose-Built Variants

Two more names worth recognizing, each optimized for a specific constraint the algorithms above don’t fully address.

ScaNN (Scalable Nearest Neighbors, Google Research) introduced a quantization technique specifically designed to preserve the accuracy of similarity ordering — not just approximate the vectors well in isolation, but specifically minimize errors in which vector ends up ranked closer to the query. This distinction matters because standard quantization methods (like plain PQ) optimize for reconstruction accuracy, which isn’t quite the same objective as ranking accuracy — ScaNN’s refinement consistently gives it strong recall-versus-speed benchmarks as a result.

DiskANN (Microsoft Research) targets a different constraint entirely: what happens when your vector collection is too large to fit in memory at all? Rather than requiring the full index to live in RAM (as HNSW typically does), DiskANN is engineered to keep most of its graph structure on fast SSD storage, using a carefully designed layout that minimizes slow disk reads during a query. This unlocks billion-scale vector search on a single machine with modest RAM, at some added query latency compared to a fully in-memory HNSW index — a trade-off that’s often worthwhile when the alternative is an expensive multi-machine memory-scaling problem.

Both are less commonly the default choice than HNSW, but knowing when they exist matters: ScaNN when ranking accuracy at high compression is the priority, DiskANN when your collection has simply outgrown what memory can hold.

Performance Trade-offs

Every algorithm above sits somewhere on the same three-way trade-off, and understanding this triangle is more useful long-term than memorizing any single algorithm’s internals.

Recall — how often the algorithm actually returns the true nearest neighbors, versus a plausible-but-wrong approximation. This is the accuracy axis, and it’s always the thing being traded away for the other two.
Latency — how fast a single query returns. This is usually the axis end users feel most directly.
Memory — how much RAM (or disk, for DiskANN-style approaches) the index requires. This is usually the axis that determines whether a given scale is even feasible to run at all, regardless of how fast or accurate it could theoretically be.

Concretely: HNSW favors low latency and high recall at the cost of high memory use. IVF trades some recall and latency for meaningfully better memory efficiency. Product quantization pushes memory efficiency further still, at a real recall cost, and is usually paired with IVF rather than used alone. DiskANN accepts higher latency in exchange for supporting collections that wouldn’t fit in memory under any of the other approaches.

There’s no universally “best” algorithm here — the right choice depends entirely on your collection size, latency requirements, and available infrastructure, which is exactly why most production vector databases (the ones covered in Vector DB post) let you choose or tune between several of these under the hood, rather than locking you into one.

Closing Thoughts

Every millisecond your RAG system spends retrieving a chunk is being spent inside one of the algorithms covered in this post. Knowing the actual trade-off each one is making — graph traversal versus clustering, full precision versus compression, memory-resident versus disk-resident — turns retrieval performance from a black box into something you can reason about and deliberately tune.

With retrieval mechanics now fully covered — from IR fundamentals through embeddings, vector databases, and the ANN algorithms underneath them — the series turns next to the other half of the pipeline: how raw source documents actually get prepared for retrieval in the first place.