Exact nearest neighbor search is the retrieval method that finds the k vectors closest to a query by computing the distance to every vector in the collection and returning the true top results, with no approximation. Within Retrieval & knowledge, a core area of artificial intelligence, it is also called brute-force vector search or flat search, and it serves as the ground truth against which every approximate method is measured.
The method guarantees perfect recall: if a vector is among the k nearest under the chosen metric, it will be returned. The price is linear query cost, because the work grows in direct proportion to the number of stored vectors and their dimensionality. For collections up to a few million embeddings, or wherever a missed result is unacceptable, that price is often worth paying.
How exact nearest neighbor search computes results
Exact search answers a query by scoring the query against all N stored vectors, then selecting the k best scores. In a retrieval-augmented generation (RAG) system, the query is an embedding of the user question, and the stored vectors are embeddings of document chunks produced by the same embedding model.
- Encode the query with the same embedding model used at ingestion.
- Compute a similarity or distance score between the query and every stored vector.
- Keep a bounded heap of size k while scanning, so memory stays small.
- Apply metadata filters, either before scoring or as a mask on the scan.
- Return the k identifiers with their scores, sorted from best to worst.
The scan is usually expressed as a dense matrix multiplication: a batch of queries multiplied by the transposed matrix of stored vectors. This form maps well onto SIMD instructions on CPUs and onto GPU tensor cores, which is why a well-implemented flat scan is far faster than a naive loop, even though the number of operations is identical.
The choice of metric shapes the result. The following table lists the common metrics and how they behave in an exact scan.
| Metric | What it measures | Practical note |
|---|---|---|
| Cosine similarity | Angle between vectors | Equals inner product on unit-normalized vectors |
| Inner product | Projection of one vector on another | Rewards vector magnitude unless normalized |
| Euclidean (L2) distance | Straight-line distance | Ranking matches cosine when vectors are normalized |
| Hamming distance | Differing bits | Used with binary embeddings, very fast with popcount |
Cost, scale and hardware limits
The cost of one query is roughly N multiplied by d operations, where N is the number of vectors and d is the dimensionality. A collection of 1 million vectors with 768 dimensions needs about 768 million multiply-add operations per query, and with 32-bit floats the vectors occupy about 3 GB of memory.
Because every query reads the whole collection, exact search is often limited by memory bandwidth rather than arithmetic. Batching many queries together lets the hardware reuse each loaded vector, which raises throughput substantially. The table below gives indicative orders of magnitude; real figures depend on hardware, dimensionality and implementation quality.
| Collection size | Typical latency per query | Usual verdict |
|---|---|---|
| Up to 100,000 vectors | About 1 ms or less | Exact search is the simplest correct choice |
| 1 to 10 million vectors | Tens to hundreds of ms on CPU | Viable with batching, GPUs or quantization |
| 100 million vectors and more | Seconds per query on CPU | Approximate indexes are normally required |
Compression changes the arithmetic. Storing vectors as 8-bit integers cuts memory about fourfold, and binary embeddings cut it about 32-fold, but both introduce quantization error. A scan over compressed vectors is exact with respect to the compressed values, not the original embeddings, so a full-precision rescoring step is common.
Exact versus approximate nearest neighbor search
Exact search trades speed for certainty, while approximate nearest neighbor (ANN) search trades a small loss of recall for sublinear query time. Indexes such as HNSW, IVF and DiskANN avoid scanning every vector by navigating a graph or probing a subset of clusters.
| Property | Exact search | Approximate search |
|---|---|---|
| Recall | Always 100 percent | Typically 90 to 99 percent, tunable |
| Query time | Linear in collection size | Roughly logarithmic or sublinear |
| Index build | None beyond storing vectors | Minutes to hours for large sets |
| Updates and deletes | Immediate and trivial | Can degrade graphs or need rebuilds |
| Filtered queries | Always correct | Restrictive filters can sharply reduce recall |
| Memory overhead | Raw vectors only | Extra graph links or codebooks |
Exact search is also the reference for evaluating ANN indexes. Recall at k is measured by running the same queries through a flat scan and checking how many of the true neighbors the approximate index found. Without that baseline, a tuning claim such as 98 percent recall cannot be verified.
When to choose exact search
Exact search is the right default when the collection is small, highly filtered or frequently changing, and when correctness matters more than the last few milliseconds. The decision table below summarizes common situations.
| Situation | Recommended approach | Reason |
|---|---|---|
| Per-user or per-tenant corpus | Exact scan per partition | Each partition is small and fully isolated |
| Strict metadata filter leaves few candidates | Filter first, then exact scan | ANN graphs lose recall under heavy filtering |
| Benchmarking an ANN index | Exact ground truth | Recall cannot be measured otherwise |
| Compliance or legal discovery | Exact search | A missed document carries real cost |
| Hundreds of millions of vectors with tight latency | ANN with exact reranking | A full scan is too slow per query |
A widely used hybrid is two-stage retrieval: an approximate index or a compressed scan returns a few hundred candidates, and an exact computation on full-precision vectors reorders them. This keeps most of the speed of ANN while restoring precision at the top of the list, before a cross-encoder or other reranking step.
Limitations and common misconceptions
The most frequent misunderstanding is that exact search guarantees relevant results. It guarantees only the true nearest vectors under the chosen metric; if the embedding model represents the domain poorly, the exact answer is exactly wrong.
- Exact does not mean relevant: retrieval quality is bounded by the embedding model and chunking strategy.
- Ties and floating-point order can make results differ slightly between CPU and GPU runs.
- Metric mismatch with the embedding model, such as L2 on unnormalized vectors trained for cosine, silently degrades ranking.
- High dimensionality compresses distance differences, so scores can look similar even when ranking is correct.
- Cost grows with every new document, so a design that works at launch may fail a year later.
Teams should plan a scaling threshold in advance: a collection size or latency target at which the system moves from a flat index to an approximate one, keeping the flat scan available for evaluation.
Explained without jargon
Imagine looking for the books most similar to one you like by checking every single book in the library, one by one. It takes longer than using a shortcut, but you are certain that nothing was missed.
Exact nearest neighbor search works the same way with numbers that describe meaning. A computer compares a question with every stored item and returns the closest ones. It is completely reliable but slows down as the collection grows, so very large systems use faster shortcuts and keep the full check for testing and for small collections.
A typical use case
A law firm builds an internal assistant that answers questions about its own contracts. The archive holds about 400,000 text chunks, each stored as a 1,024-dimensional embedding, and every query is filtered to a single client, which typically leaves fewer than 20,000 chunks.
The engineering team chooses a filtered exact scan instead of an HNSW index. Filtering first and scoring the remaining vectors takes under 10 ms on a standard CPU, new contracts become searchable the moment they are embedded, and no relevant clause is skipped because of approximation. The team also uses the flat scan to confirm that a planned ANN index for the full archive reaches 97 percent recall at 10 before any migration.