Module 5.1

Fewer candidates, not faster math

Module 1.2 found the nearest neighbor by checking all 6 Nimbus documents — brute force. A real vector database almost never does that. It gets fast by being clever about which candidates it even bothers to compare.

QUERY: "Why did my Nimbus export fail?" — SEARCH STRATEGY

The math

The complexity gap, at real scale

Brute force

O(n) comparisons per query

n = corpus size

n = 1,000,000 → 1,000,000 comparisons

IVF (inverted file index)

O(n/k) comparisons per query

k = number of clusters

k = 1,000 → ~1,000 comparisons

HNSW (graph search)

O(log n) comparisons per query

navigable small-world graph

n = 1,000,000 → ~20 comparisons

Both IVF and HNSW are approximate — they can occasionally miss the true nearest neighbor to save that much work. At the toy scale below, the corpus is small enough that all three still land on the right answer.

The code

What each strategy actually runs

search_strategies.py

def brute_force(query, corpus):
    return max(corpus, key=lambda doc: cosine_sim(query, doc.vec))

def ivf_search(query, index, n_probe=1):
    nearest_clusters = index.nearest_centroids(query, n_probe)
    candidates = [doc for c in nearest_clusters for doc in c.members]
    return max(candidates, key=lambda doc: cosine_sim(query, doc.vec))

# HNSW isn't something you'd hand-roll — real code just calls a library:
import hnswlib
index = hnswlib.Index(space='cosine', dim=384)
index.add_items(corpus_vecs)
labels, distances = index.knn_query(query_vec, k=1)   # ~O(log n) internally

Chroma, Pinecone, Weaviate, FAISS, and pgvector all implement some version of IVF or HNSW under the hood — this is what "vector database" actually means at the algorithm level.

The Nimbus thread

When Nimbus's 6 docs become 6 million

At 6 documents, brute force is instant and this whole page is academic. The moment Nimbus's support corpus grows to real scale — years of tickets, every doc revision, every internal wiki page — brute force's O(n) starts costing real, measurable latency on every single query. That's the exact point where an index (IVF or HNSW) stops being an optimization and becomes a requirement.

So what

A vector database doesn't do the math faster — it's clever about which candidates it even looks at.