Where Linear Scan Breaks Down

Where we left off

Every retrieval lesson so far (Lesson 6 onward) has scored every record in the store against the query, one at a time, then sorted and sliced off the top k. That's a linear scan: exactly N similarity computations for a store of N records, no shortcuts. At 5 records, this is instant. This lesson asks: at what point does that stop being true?

Measuring it, not guessing it

Rather than reason abstractly about complexity, this lesson just times the same linear_scan function this course has been using all along, against stores of increasing size, using random vectors instead of real embeddings (a real embedding call for 100,000 records would be slow and expensive for a question this lesson doesn't need real meaning to answer).

The code, piece by piece

def random_vector() -> list[float]:
    return [random.random() for _ in range(EMBEDDING_DIMENSIONS)]

A random vector has the same shape (768 floats) as a real Gemini embedding, which is all this benchmark needs, cosine similarity doesn't know or care whether a vector came from a real model or random.random().

def linear_scan(query_vector: list[float], vectors: list[list[float]]) -> float:
    start = time.perf_counter()
    scored = [cosine_similarity(query_vector, v) for v in vectors]
    scored.sort(reverse=True)
    return time.perf_counter() - start

The exact same shape as every retrieve() function since Lesson 6: score every vector, then sort. time.perf_counter() before and after measures how long that took, in seconds.