03. Brute Force Search

Chapter 3 of 18 · 15 min

KEY INSIGHT

Brute force search on 1M vectors with 768 dimensions does ~768M FLOPs per query. At 100 QPS, that's 76.8 billion FLOPs—your CPU screams, and latency explodes. This is why indexes exist. ### Implementation ```python import numpy as np def brute_force_search(database, query, k=10): """ Find k nearest neighbors by exhaustive comparison. Args: database: (n_vectors, dim) array of vectors query: (dim,) query vector k: number of results Returns: distances, indices of k nearest neighbors """ # Compute L2 distance to all vectors diff = database - query distances = np.sqrt(np.sum(diff ** 2, axis=1)) # Get indices of k smallest distances indices = np.argsort(distances)[:k] return distances[indices], indices # Benchmark n = 100_000 dim = 768 k = 10 db = np.random.rand(n, dim).astype('float32') query = np.random.rand(dim).astype('float32') import time start = time.time() for _ in range(100): distances, indices = brute_force_search(db, query, k) elapsed = (time.time() - start) / 100 print(f"Average latency: {elapsed*1000:.2f}ms for {n:,} vectors, dim={dim}") ``` ### Complexity Analysis | Operation | Complexity | |-----------|------------| | Distance computation | O(n × dim) | | Sorting for top-k | O(n log k) | | Memory access | O(n × dim) bytes | For n=1M, dim=768: 768M distance computations, plus sorting 1M elements. This doesn't fit in L3 cache—the memory bandwidth bottleneck bites hard. ### Why Brute Force Sometimes Wins For small datasets (<10k vectors), the overhead of index construction and traversal often exceeds brute force cost. Many production systems fall back to brute force for small indexes. Additionally, when you need 100% recall (guaranteed exact results), brute force is your only option. ANN methods are a bet on "good enough recall."

Brute force is the baseline. Every advanced index is optimizing away comparisons, so understanding brute force's behavior tells you where the pain points are.

EXERCISE

Measure brute force latency as a function of dataset size. Plot the curve and identify where an index becomes worthwhile for your latency budget.

import numpy as np
import time

def benchmark_bruteforce(sizes, dim=128, n_queries=50):
    results = {}
    for n in sizes:
        db = np.random.rand(n, dim).astype('float32')
        queries = np.random.rand(n_queries, dim).astype('float32')
        
        start = time.time()
        for q in queries:
            diff = db - q
            dists = np.sqrt(np.sum(diff ** 2, axis=1))
            np.argsort(dists)[:10]
        elapsed = (time.time() - start) / n_queries
        results[n] = elapsed * 1000  # ms
        
    return results

sizes = [1000, 5000, 10000, 50000, 100000, 500000]
timings = benchmark_bruteforce(sizes)
for n, ms in timings.items():
    print(f"{n:>8,}: {ms:.2f}ms")