What Is Approximate Nearest Neighbor Search? ANN Explained

Vector search at scale is a trade between exactness and speed, and most teams make that trade implicitly by accepting a database's defaults. Understanding what is being traded explains recall problems that otherwise look like embedding problems, and it prevents the common mistake of indexing a corpus small enough to search exactly. This explainer covers the trade. It complements what is hnsw and what is retrieval augmentation, and reflects FISTA Solutions' approach in AI agents delivery.

What is being approximated?

The set of nearest vectors. Exact search compares the query against every vector and returns the true closest. Approximate search examines a small fraction of the collection, chosen by a structure built in advance, and returns what it finds there.

Most of the time those are the same vectors. Occasionally a true nearest neighbour lies outside the region examined and is missed, which is what the approximation costs.

Family	Mechanism	Strength	Cost
Graph-based	Navigate proximity graph	Speed and recall	High memory
Inverted file	Partition into cells	Scales very large	Training step, tuning
Quantized variants	Compress vectors	Small footprint	Recall loss
Hashing	Bucket similar vectors	Simple, fast	Lower recall
Disk-based	Store off-memory	Very large corpora	Higher latency
Exact	Compare everything	Correctness	Linear scaling

Why is the trade acceptable?

Because retrieval feeds a downstream step. A system retrieving twenty candidates for a reranker or a model does not need all twenty to be the mathematically closest; it needs the relevant ones present. Missing the nineteenth-closest vector rarely changes the answer.

The speed difference is not marginal. At large scale it is the difference between a search taking milliseconds and one taking seconds, which is the difference between a usable system and an unusable one.

How is the trade controlled?

By parameters that determine how much of the space is examined. Searching harder raises recall and latency together; searching less does the reverse. Crucially, this is adjustable at query time in most implementations, so a system can search thoroughly for important queries and quickly for routine ones.

Treating recall as a fixed property of the index, rather than as a dial, gives up useful flexibility.

What usually decides the family?

Memory. Graph indexes deliver excellent speed and recall and consume substantial memory beyond the vectors themselves. Quantized inverted-file indexes fit far larger collections in the same footprint with a recall cost and a training step.

At modest scale the choice barely matters. At very large scale it is determined by what fits in the available memory budget, which makes it an infrastructure decision as much as a retrieval one. See what is hnsw.

When is exact search correct?

More often than assumed. Tens of thousands of vectors can be compared exhaustively in milliseconds on ordinary hardware. That gives exact results, no index memory, no parameters to tune, trivial updates and deletions, and no possibility of a silent recall problem.

Many production systems carry index complexity they never needed, having adopted it as the default path rather than in response to a measured constraint.

How should recall be measured?

By brute force on a sample. Take a few hundred real queries, compute the true nearest neighbours exhaustively, and compare with what the index returns at the configured parameters. That gives a number specific to your embeddings, your dimensionality, and your data distribution.

Vendor benchmarks describe standard datasets. They are useful for comparing implementations and useless for predicting behaviour on a particular corpus.

What causes recall to degrade over time?

Accumulated deletions in graph indexes, distribution shift as new content differs from what the index was built on, and parameter settings chosen for an earlier corpus size. None of these announces itself; retrieval simply gets quietly worse.

Periodic recall measurement, not just at launch, is what catches it.

How does this interact with filtering?

Awkwardly, and it is worth knowing. Applying a metadata filter to an approximate index can force it to examine far more of the space to find enough matching candidates, degrading latency badly when the filter is selective. Implementations differ in how well they handle this, and it is a common source of unexpected slowness.

What should you do first?

Measure your corpus size and your recall. If the corpus is small, use exact search and remove a whole category of problems. If it is large, measure recall at your current settings before tuning anything else, because retrieval quality problems attributed to embeddings are frequently index recall problems instead.

Does the choice matter as much as embeddings?

Rarely. Embedding model fit determines whether the right document is near the query at all, and no index recovers a document the embedding placed far away. Index recall determines whether a document that is near gets returned. Teams usually have more to gain from evaluating embedding models on their own corpus than from tuning index parameters, and the diagnostic order should reflect that.

How FISTA Solutions helps

FISTA Solutions sizes vector infrastructure from measured recall on client data, uses exact search where scale permits, tunes query-time parameters per workload, accounts for filtered-search behaviour, and re-measures recall periodically rather than only at launch, through AI agents, AI enablement, and forward deployed engineers. The record behind the approach is 150+ projects for 50+ companies with 99.9% uptime.

To find out whether your retrieval problem is really an index problem, message FISTA on WhatsApp, or read what is hnsw.