Brute-Force Search

Brute-force search calculates the distance between the query vector and every single database vector without exception. This linear scan guarantees that the true nearest neighbors are always found, making it the gold standard for recall@K evaluation. For a dataset of n vectors, the algorithm performs exactly n distance calculations per query, resulting in O(n) time complexity. This exhaustive approach eliminates the possibility of missing a true neighbor due to partitioning errors or graph traversal shortcuts that plague approximate methods.

Unlike approximate nearest neighbor (ANN) algorithms that trade accuracy for speed, brute-force search achieves 100% recall@K by definition. This property makes it indispensable for:

• Ground truth generation when benchmarking ANN indices
• High-stakes applications where missing a single relevant result is unacceptable
• Small to medium datasets where latency remains tolerable
• Verification pipelines that audit the recall of production search systems

The absence of false negatives ensures that every relevant vector is retrieved, making brute-force the definitive reference implementation.

The primary drawback of brute-force search is its O(n) time complexity, which scales linearly with dataset size. For a database of 1 million 768-dimensional vectors using Euclidean distance, a single query requires 768 million floating-point operations. At billion-scale, latency becomes prohibitive even with hardware acceleration. This computational burden is compounded by the curse of dimensionality, where distance metrics lose discriminative power as dimensions increase, requiring even more precise calculations to distinguish true neighbors from the increasingly uniform distance distribution.

Brute-force search uses a flat index — the simplest possible vector index with no preprocessing, clustering, or graph construction. Vectors are stored sequentially in memory or on disk, and search involves a direct sequential scan. This simplicity offers key advantages:

• Zero index build time — vectors are immediately queryable upon insertion
• No memory overhead for auxiliary structures like graphs or codebooks
• Deterministic performance — query latency is predictable and consistent
• Trivial updates — adding or removing vectors requires no index restructuring

Libraries like FAISS implement flat indexes as IndexFlatL2 or IndexFlatIP for Euclidean and inner product searches respectively.

Despite its algorithmic simplicity, brute-force search benefits enormously from Single Instruction Multiple Data (SIMD) parallelism. Modern CPUs can pack multiple floating-point operations into a single instruction, processing 8 or 16 vector dimensions simultaneously with AVX-512 or ARM NEON intrinsics. GPU acceleration pushes this further, with thousands of cores computing distances in parallel. FAISS leverages CUDA kernels to achieve sub-millisecond latency on million-scale datasets by exploiting the embarrassingly parallel nature of exhaustive distance computation, making brute-force viable for surprisingly large datasets when hardware is abundant.

Brute-force search imposes no constraints on the distance function used. Any metric — cosine similarity, Euclidean distance, dot product, Manhattan distance, or custom domain-specific functions — can be applied without modifying the index structure. This flexibility contrasts with many ANN algorithms that are optimized for specific metrics. For example, Locality-Sensitive Hashing (LSH) requires hash functions tailored to a particular distance, while brute-force simply iterates and applies the chosen metric. This makes it ideal for prototyping and evaluating novel similarity functions before committing to an approximate index.