Exact nearest neighbor search

Also known as: brute-force vector search

On this page 7

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.

  1. Encode the query with the same embedding model used at ingestion.
  2. Compute a similarity or distance score between the query and every stored vector.
  3. Keep a bounded heap of size k while scanning, so memory stays small.
  4. Apply metadata filters, either before scoring or as a mask on the scan.
  5. 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.

MetricWhat it measuresPractical note
Cosine similarityAngle between vectorsEquals inner product on unit-normalized vectors
Inner productProjection of one vector on anotherRewards vector magnitude unless normalized
Euclidean (L2) distanceStraight-line distanceRanking matches cosine when vectors are normalized
Hamming distanceDiffering bitsUsed with binary embeddings, very fast with popcount
Distance metrics used in exact search

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 sizeTypical latency per queryUsual verdict
Up to 100,000 vectorsAbout 1 ms or lessExact search is the simplest correct choice
1 to 10 million vectorsTens to hundreds of ms on CPUViable with batching, GPUs or quantization
100 million vectors and moreSeconds per query on CPUApproximate indexes are normally required
Indicative behavior by collection size

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 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.

PropertyExact searchApproximate search
RecallAlways 100 percentTypically 90 to 99 percent, tunable
Query timeLinear in collection sizeRoughly logarithmic or sublinear
Index buildNone beyond storing vectorsMinutes to hours for large sets
Updates and deletesImmediate and trivialCan degrade graphs or need rebuilds
Filtered queriesAlways correctRestrictive filters can sharply reduce recall
Memory overheadRaw vectors onlyExtra graph links or codebooks
Exact and approximate search compared

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.

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.

SituationRecommended approachReason
Per-user or per-tenant corpusExact scan per partitionEach partition is small and fully isolated
Strict metadata filter leaves few candidatesFilter first, then exact scanANN graphs lose recall under heavy filtering
Benchmarking an ANN indexExact ground truthRecall cannot be measured otherwise
Compliance or legal discoveryExact searchA missed document carries real cost
Hundreds of millions of vectors with tight latencyANN with exact rerankingA full scan is too slow per query
Decision guide for exact search

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.