Home / How it works / Approximate Nearest Neighbor (ANN) Search for Semantic Search

Approximate Nearest Neighbor (ANN) Search for Semantic Search

Approximate nearest neighbor (ANN) search finds vectors that are close to a query without guaranteeing they are the exact closest, trading a small loss of accuracy for a very large gain in speed. Exact search compares the query with every stored vector, which becomes too slow as a collection grows into the millions. ANN algorithms organize vectors in advance, into graphs, clusters, hash buckets, or trees, so a query only visits a small part of the collection. Their accuracy is measured as recall: the share of true nearest neighbors the search actually returns. Weaviate’s published benchmark, for example, reached 98.35 percent recall at 10 on one million SIFT vectors while serving 10,940 queries per second. Semantic search depends on ANN, because it must search embeddings of large collections within the time a user will wait.

What is approximate nearest neighbor search?

Approximate nearest neighbor search is a method for finding vectors close to a query vector while allowing the result to be slightly farther than the true nearest one. It relaxes the exact problem in return for speed.

Researchers state the relaxation precisely. Andoni, Indyk, and Razenshteyn give the formal version in their 2018 survey of the field. A valid answer is any point within c times the distance of the true nearest point, for some c of at least 1. With c equal to 1, the problem is exact. Larger values allow more slack and faster answers.

Practitioners usually measure the approximation differently. Instead of a distance factor, they count how many of the true top results the search returns. Weaviate’s documentation explains that a recall of 98 percent means 2 percent of returned results are not among the true nearest neighbors. That count is easier to relate to search quality.

ANN is the engine behind vector search and similarity search. It works on the embeddings described in dense vectors, using a distance metric to define closeness. Its meaning is clearest beside the exact method it replaces.

How does ANN search differ from exact k-nearest neighbor search?

ANN search differs from exact k-nearest neighbor search by skipping most of the collection, so it returns results much faster but may miss some of the true closest vectors. Exact search, often called kNN, guarantees the right answer by checking everything.

The k-nearest neighbors idea is simple: given a query, return the k stored items closest to it. The exact way to do that is a linear scan. Compute the distance from the query to every vector, sort, and keep the top k. Microsoft’s SQL documentation describes this exact search as precise but resource-intensive.

The table shows that the trade is speed for certainty. The exact versus approximate search guide covers the decision in depth. The term kNN also names a machine learning classifier that labels a point by its neighbors, but in search it means retrieval only. Semantic search accepts the trade for a clear reason.

Why does semantic search need approximate nearest neighbor search?

Semantic search needs ANN search because exact comparison against millions of high-dimensional embeddings takes too long for interactive queries. Each embedding may hold hundreds or thousands of numbers, and each comparison touches all of them.

The cost grows in two directions. More items mean more comparisons. More dimensions make each comparison slower. A collection of one million 1536-dimensional vectors needs over 1.5 billion multiply-and-add steps per query for a full scan. Weaviate’s blog on ANN algorithms makes the point that a brute-force approach becomes far too slow at this scale, and that Weaviate instead looks for close-enough results.

The approximation rarely hurts semantic search much. Embeddings themselves are approximations of meaning, so a result that is the second-closest rather than the closest is often equally relevant. Microsoft’s documentation makes the same argument: with recall close to 1, ANN results closely match exact ones at far lower cost.

That does not make recall irrelevant. A missed neighbor can be the one relevant document. ANN settings therefore belong in the evaluation plan, as ANN recall explains. How much recall is lost depends on the algorithm.

How do approximate nearest neighbor algorithms work?

Approximate nearest neighbor algorithms work by organizing vectors so a query can reach its neighborhood quickly, using graphs, clusters, hashing, or trees. Each family narrows the search in a different way.

The main families are these:

• Graph methods link each vector to its neighbors and walk the links toward the query; HNSW and DiskANN are examples.
• Cluster methods group vectors around centroids and search only the nearest groups; IVF is the standard example.
• Hashing methods map similar vectors to the same bucket; locality-sensitive hashing, from Indyk and Motwani’s 1998 work, is the classic case.
• Tree methods split space recursively; KD-trees and Spotify’s Annoy library use forms of this.
• Quantization compresses vectors so more comparisons fit in memory, often combined with one of the families.

The list shows that families can mix. Malkov and Yashunin’s HNSW, from 2016, builds a multilayer graph and descends from coarse to fine layers. Subramanya and colleagues’ DiskANN, from NeurIPS 2019, keeps a graph on SSD and searched one billion points on a single workstation with 64 GB of RAM.

No family dominates everywhere. Aumüller, Bernhardsson, and Faithfull’s ANN-Benchmarks study found that very different approaches can reach comparable quality-performance trade-offs. Graph methods are the most common default in vector databases. Cluster methods matter too, and they answer one of the most common questions about ANN.

How does a cluster index support semantic search?

A cluster index supports semantic search by grouping embeddings around learned centroids, so each query searches only the clusters nearest to it instead of the whole collection. This is the inverted file, or IVF, approach.

FAISS documents the mechanism. A clustering step, usually k-means, splits the vectors into nlist cells. At query time, the index finds the centroids closest to the query embedding and scans only the vectors in the nprobe nearest cells. The work drops to roughly nprobe divided by nlist of the collection.

The settings decide recall. A relevant document assigned to a cluster the query does not probe is missed. Probing more clusters raises recall and costs time. pgvector suggests starting with lists equal to the row count divided by 1,000 for up to one million rows, and probes equal to the square root of lists.

Weaviate’s HFresh index applies a cluster design to reduce memory: it keeps an HNSW index of centroids in memory and stores the vectors of each cluster on disk. Cluster indexes are lighter than graphs but need representative data before they are built. Semantic indexing and vector indexes compares IVF and HNSW in detail. Whatever the index, its accuracy has to be measured.

How is the accuracy of ANN search measured?

The accuracy of ANN search is measured as recall at k: the share of the true k nearest neighbors, found by exact search, that the approximate search returns. It is always reported together with speed, because each can be traded for the other.

Weaviate’s ANN benchmark shows the method. It runs 10,000 queries per configuration and measures recall at 10 and at 100 against each dataset’s ground truth, alongside queries per second, mean latency, 99th-percentile latency, and import time. Its timings include network transfer and object retrieval, which libraries benchmarked by ann-benchmarks do not include. The tests ran on a 30-core machine.

The table shows the size of the trade in practice: recall near 98 percent at thousands of queries per second. Higher-dimensional vectors cost more per query. Results depend on hardware and data, so these figures are reference points, not promises.

ANN recall is not the same as search relevance. It only says whether the index found the true nearest vectors. Whether those vectors are relevant depends on the embedding model. Settings move recall up or down.

How do you tune the speed and recall of an ANN index?

The speed and recall of an ANN index are tuned through build settings that shape the index and query settings that control how much of it each search explores. In HNSW, those are maxConnections and efConstruction at build time and ef at query time.

Weaviate’s configuration reference describes each. ef is the size of the candidate list during a search: higher is more accurate and slower, and values above 512 show diminishing recall gains. efConstruction trades build speed for index quality, and a higher value lets queries use a lower ef. maxConnections sets the edges per node, 32 by default. Weaviate suggests ef 64, efConstruction 128, and maxConnections 32 as a starting point.

Weaviate’s default is a dynamic ef, which scales with the number of results requested. Its formula multiplies the query limit by 8, then clamps the result between 100 and 500. A limit of 20 gives an ef of 160, and a limit of 100 is capped at 500. That is why result quality can change with the requested limit.

For IVF indexes, the equivalent levers are the number of clusters and the number probed. In every case, tune with measured recall on a sample of real queries, and change one setting at a time. Top-k retrieval covers how the limit interacts with ranking. Sometimes the right setting is no approximation at all.

When should you use exact search instead of ANN?

Exact search should be used instead of ANN when the collection or the filtered subset is small enough to scan quickly, or when recall must be perfect. In those cases an index adds cost without adding speed.

Size thresholds give a starting point. Weaviate suggests a flat index for collections expected to stay under about 100,000 vectors, and its dynamic index switches from flat to HNSW at 10,000 objects by default. Microsoft’s SQL documentation recommends exact search under about 50,000 vectors, including when filters narrow a larger table to that size.

Filters matter because they shrink the candidate set. Weaviate’s HNSW index has a flatSearchCutoff setting, 40,000 by default, under which a filtered search switches to a flat scan of the allowed objects. A query restricted to one customer’s documents may scan exactly and quickly, even inside a huge collection. Metadata filtering explains how filters and indexes interact.

Exact search also serves as the measuring stick. Run it on a sample of queries to compute ANN recall, then decide whether the approximation is acceptable. The broader pipeline is in how semantic search works and semantic search architecture. Related topics include relevance scores, sparse vectors, dense versus sparse vectors, semantic matching, synonyms and related terms, multilingual search, and chunking.

Approximate nearest neighbor search finds close vectors fast by searching only part of a collection, through graphs, clusters, hashing, or trees. It trades a little recall, measured against exact search, for large gains in speed, and Weaviate’s benchmark shows recall near 98 percent at thousands of queries per second. Settings such as ef, efConstruction, and the number of probed clusters move the balance. The decision is to use ANN for large collections, exact search for small or tightly filtered ones, and to measure recall on real queries before trusting any configuration.