Vector Similarity Search: Metrics & Approximate Methods › Exact Search: The Brute-Force Baseline

The simplest approach to finding the $k$ nearest neighbors of a query vector is exhaustive search: compute the distance between the query and every vector in the collection, then return the $k$ closest ones. Despite its simplicity, this approach serves a useful role in the vector search ecosystem. It provides a correctness baseline against which all approximate methods are measured, and it remains the practical choice for collections small enough that its linear cost is acceptable.

Given a query vector $\mathbf{q} \in \mathbb{R}^d$ and a collection of $n$ vectors $\{\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n\}$, each also in $\mathbb{R}^d$, exact search performs the following:

1. Compute $\text{distance}(\mathbf{q}, \mathbf{v}_i)$ for all $i = 1, \ldots, n$
2. Sort or partially sort the results to find the $k$ smallest distances
3. Return the corresponding $k$ vectors (and their identifiers)

The first step is where nearly all the computation happens. For each of the $n$ vectors in the collection, we must compute a distance or similarity score against the query. Each such computation involves $d$ multiplications and $d-1$ additions (for the dot product), plus any additional operations required by the specific metric (normalization for cosine similarity, subtraction and squaring for Euclidean distance). The computational cost is therefore $O(n \cdot d)$ for the distance computations, plus $O(n \log k)$ for maintaining a heap of the top $k$ results. For typical embedding dimensions ($d = 384$ to $1536$) and collection sizes ($n$ in the millions), the $O(n \cdot d)$ term dominates.

The second step, finding the top $k$ results, is handled efficiently by maintaining a max-heap (for distances, where we want the smallest) or min-heap (for similarities, where we want the largest) of size $k$. As each new distance is computed, it is compared against the worst element in the heap. If the new distance is better, it replaces the worst element. This avoids the $O(n \log n)$ cost of fully sorting all distances and instead requires only $O(n \log k)$ operations, which is significantly cheaper when $k$ is small relative to $n$.

Modern CPUs expose SIMD (Single Instruction Multiple Data) instruction sets like AVX2 and AVX-512 that process multiple floating-point values simultaneously. An AVX2 register holds 8 float32 values, so a single instruction can multiply or add 8 pairs of components at once. This means that the effective number of clock cycles per dot product is $d/8$ rather than $d$, an 8x theoretical speedup. In practice, combined with careful memory layout (storing vectors in row-major order for sequential access) and vectorized operations, libraries like FAISS achieve near-peak floating-point throughput on dot product computations.

The memory bandwidth story is equally important. For an exact search over 10 million 384-dimensional vectors, the total data that must be read from RAM is $10^7 \times 384 \times 4 \approx 15$ GB. Modern CPUs have memory bandwidth around 50-100 GB/s, so even if the computation were free, reading that much data takes 0.15-0.3 seconds per query. This memory bandwidth ceiling is often the dominant bottleneck for exact search on large collections, not the arithmetic.

GPUs change this calculus significantly. A modern GPU (like an NVIDIA A100) has 2 TB/s of memory bandwidth and 312 TFLOPS of tensor core throughput. Reformulating the distance computations as a matrix-matrix multiplication allows batching multiple queries together and saturating the GPU's capabilities. For batches of 100 queries over 10 million vectors at dimension 768, a GPU can sustain query rates that CPU-based exact search cannot match. FAISS's GPU backend exploits this by converting the batch search into a matrix multiplication $\mathbf{Q} \times \mathbf{D}^T$ where $\mathbf{Q}$ is the query matrix and $\mathbf{D}$ is the document matrix.

Exact search guarantees returning the true nearest neighbors. There are no missed relevant documents, no tuning parameters for recall, and no possibility that the correct answer was overlooked. Every vector in the collection is examined, so the algorithm has complete knowledge of the entire search space. This makes it the gold standard for evaluating approximate methods: when we report recall@k for an ANN algorithm, we are measuring how often it agrees with the results that exact search would have returned.

However, it scales linearly with collection size, which makes it inefficient for large datasets. Let's think through the numbers to develop a concrete sense of where the boundary lies. If you have 1 million vectors of dimension 768, a single query requires roughly 768 million multiply-add operations. On modern hardware with SIMD instructions, you can sustain around 10-50 billion floating-point operations per second on a single CPU core. That puts brute-force at roughly 15-75 milliseconds per query, which is potentially acceptable for some applications. But scale to 100 million vectors and you are looking at 1.5-7.5 seconds per query, which is far too slow for interactive use. The linear scaling with collection size means that every 10x increase in collection size produces a 10x increase in query time, with no way to mitigate this short of faster hardware.

The practical crossover point where you should switch from exact to approximate search depends on your latency budget and query volume. For a RAG system serving interactive users with a 100ms latency budget and a collection of a few hundred thousand documents, exact search on a single CPU may be fast enough. For a production system serving millions of queries per day over tens of millions of documents, approximate methods are needed.

Exact search requires storing all $n$ vectors in memory, since any vector could potentially be a nearest neighbor and must be accessible for the distance computation. For $n$ vectors of dimension $d$ stored as 32-bit floats, the memory requirement is:

$$\text{Memory} = n \times d \times 4 \text{ bytes}$$

where:

• $n$: the number of vectors in the collection
• $d$: the dimensionality of each vector
• $4$: the size in bytes of a standard 32-bit floating-point number

This formula reflects the fact that each vector is simply a flat array of $d$ floating-point values, and the full collection is $n$ such arrays stored contiguously. There is no overhead for index structures in exact search: the "index" is just the raw matrix of vectors.

For 10 million vectors at dimension 768, that is about 28.8 GB. This is feasible on a single large-memory machine but becomes challenging at larger scales. We will see in the chapter on Product Quantization how vector compression can dramatically reduce this memory footprint.