Capsule 02: The core problem — RAG needs to find 5 docs among millions in milliseconds

Capsule overview

You're going to build an AI-powered tech support system. The idea sounds simple: when a user asks something, the system searches your documentation for the 5 most relevant articles and passes them to an LLM to write an answer. Total: 4 steps, what could go wrong?

Step 2 — "search for the 5 most relevant" — is where 90% of RAG projects sink in production. The question almost nobody asks before starting to code is: how fast can you find those 5 documents when your base has 1 million chunks?

If you take 50ms, your system is production-ready. If you take 5 seconds, it's unusable and nobody will explain the difference to you until it's too late — because the difference isn't in the code you're going to write, it's in the data structure you use to store the vectors. This capsule builds the mental model of why retrieval is the critical bottleneck of RAG and why conventional tools (numpy, pandas, SQL) collapse at the first sign of scale.

By the end of this capsule you'll be able to:

• ✅ Explain the four phases of the RAG pipeline and why retrieval is the bottleneck
• ✅ Calculate the expected total response time of a RAG (embedding + retrieval + generation)
• ✅ Predict when brute force with numpy is going to collapse (typical threshold: 100K vectors)
• ✅ Explain the accuracy vs speed trade-off of Approximate Nearest Neighbors (ANN)
• ✅ Justify with numbers why you need a specialized tool (vector database) over numpy/pandas
• ✅ Distinguish between exact nearest neighbor and approximate — and understand why for RAG the approximate is the right choice

Estimated time: 25-30 minutes

The RAG pipeline in four phases

Before talking about the bottleneck, let's make sure you're seeing the whole system. RAG (Retrieval-Augmented Generation) has four distinct phases, and only two of them affect the latency the user perceives:

PHASE 1 — INGESTION (runs once, or when new data arrives)
  Documents → Chunking → Embeddings → Storage
                                          │
                                          ▼
PHASE 2 — INDEXING (runs once, in the background)
  Vectors → Indexing Algorithm → Vector Database

═══════════════════════════════════════════════════════
  ↑ Offline phases. The user doesn't see them.
═══════════════════════════════════════════════════════
  ↓ Online phases. Every user query runs them.

PHASE 3 — RETRIEVAL (the bottleneck)
  User query → Query embedding → Search → Top-K chunks

PHASE 4 — GENERATION
  Top-K chunks → Prompt to the LLM → Generated answer

The critical insight: phases 1 and 2 can be as slow as you need — they run in the background. Phases 3 and 4 are the ones the user waits for, and together they define the perceived latency.

The user's time budget

UX studies consistently show that:

• <1 second total: smooth experience
• 1-3 seconds: acceptable, the user waits
• 3-5 seconds: starts to get frustrated

• 5 seconds: abandons or rephrases the question

If your goal is <3 seconds total, you have to distribute that budget between the two online phases:

Total budget:                3,000 ms
├─ Query embedding (OpenAI):    150 ms  (typical, varies 100-200ms)
├─ Retrieval:                    ??? ms  ← what we're analyzing
└─ Generation (GPT-4o-mini):  1,200 ms  (typical for a ~300-token answer)

Available for retrieval = 3,000 - 150 - 1,200 = 1,650 ms

That sounds roomy. Until you measure retrieval with real data.

Realistic scenario: the math that hurts

Case: a support chatbot for a SaaS company with technical documentation.

Data:

• 100,000 documentation articles
• Each article is chunked into ~5 pieces → 500,000 chunks
• Each chunk is embedded into a 1,536-dimension vector (OpenAI text-embedding-3-small)
• Total: 500,000 vectors of 1,536 dimensions each

Operational loads:

• 200 concurrent users at peak hour
• Each user makes 3-5 queries per session
• ~600 simultaneous queries per minute

Key question: how long does it take to find the 5 chunks most similar to a query?

And more importantly: how does that answer change depending on the tool you use?

Brute force with numpy — the obvious solution that fails

The first instinct of anyone who knows Python is:

import numpy as np

def naive_search(query_vector, all_vectors, k=5):
    """
    Computes cosine similarity against all vectors.
    Returns the k most similar.
    """
    # Normalize so that dot product = cosine similarity
    query_normalized = query_vector / np.linalg.norm(query_vector)
    all_normalized = all_vectors / np.linalg.norm(all_vectors, axis=1, keepdims=True)

    # Cosine similarity against ALL vectors
    similarities = np.dot(all_normalized, query_normalized)

    # Top-k indices
    top_k_indices = np.argsort(similarities)[-k:][::-1]
    return top_k_indices, similarities[top_k_indices]

Does it work? Yes. Does it scale? Let's measure it.

Real benchmark

import numpy as np
import time

DIMENSIONS = 1536  # OpenAI text-embedding-3-small

def benchmark_brute_force(n_vectors):
    # Generate random vectors (proxy for real embeddings)
    database = np.random.randn(n_vectors, DIMENSIONS).astype('float32')
    query = np.random.randn(DIMENSIONS).astype('float32')

    # Normalize
    db_norm = database / np.linalg.norm(database, axis=1, keepdims=True)
    q_norm = query / np.linalg.norm(query)

    # Measure 5 runs, take the median
    times = []
    for _ in range(5):
        start = time.perf_counter()
        sims = np.dot(db_norm, q_norm)
        top_5 = np.argsort(sims)[-5:][::-1]
        times.append((time.perf_counter() - start) * 1000)

    return np.median(times)


for n in [10_000, 100_000, 500_000, 1_000_000, 5_000_000]:
    latency_ms = benchmark_brute_force(n)
    print(f"n={n:>10,}: {latency_ms:>7.1f} ms")

Typical output (Macbook M2, 16 GB RAM):

n=    10,000:    12.5 ms     ✅ Excellent
n=   100,000:   125.3 ms     ⚠️  Acceptable, already starting to hurt
n=   500,000:   642.8 ms     ❌ Unusable
n= 1,000,000:  1,287.2 ms    ❌ Impossible for production
n= 5,000,000:  6,490.5 ms    ❌ Ridiculous

Unmistakable pattern: latency grows linearly with the number of vectors. It's what the theory predicts — the complexity of brute force is O(n), where n is the number of vectors.

Why your RAG system with numpy is going to fail

Go back to the SaaS chatbot scenario: 500,000 chunks. Brute force takes ~640ms.

Add it to the pipeline:

Query embedding:    150 ms  (OpenAI)
Retrieval (numpy):  640 ms  (brute force over 500K)
Generation:       1,200 ms  (GPT)
─────────────────────────
Total:            1,990 ms  ← close to the limit

That already exceeds 2 seconds in the happy case alone. If concurrency creates CPU contention, latency skyrockets. If your dataset grows to 1M chunks, you're already at 2.6 seconds of retrieval alone — completely out of budget.

And all of this before the memory problem shows up: 500K vectors × 1536 dim × 4 bytes (float32) = 3 GB in RAM. 5M vectors = 30 GB. Your application server can't handle that, and even if it could, you want that RAM for other things (cache, sessions, connections).

The key idea: Approximate Nearest Neighbors (ANN)

The real question isn't "how do I make brute force faster?" It's "do I really need the exact result?"

The counterintuitive insight

In RAG, you don't need the 5 absolutely closest vectors. You need 5 vectors close enough that the LLM can use them to answer well. Those two sets coincide 95-99% of the time, and the difference rarely matters.

Explicit trade-off:

You sacrifice 1-5% accuracy in exchange for 100-1000x less latency. For RAG, that trade-off is obvious.

Analogy: Google Maps

Imagine searching for "nearby Italian restaurant." You could:

• Exact approach: measure the GPS distance to EVERY Italian restaurant in Buenos Aires (8,000 restaurants), sort by distance, show you the nearest one. Result guaranteed correct, but it takes 30 seconds on your phone.

• Approximate approach: Google divides the city into zones. It identifies which zone you're in. It only searches restaurants in your zone and adjacent zones (200 restaurants). It shows you the nearest of those. 99% of the time it's the right one. It takes 100ms.

Which do you prefer? Obviously the second, because the 1% of the time it returns a restaurant that's 50 meters farther instead of the truly closest one, you don't care — the answer is "good enough." ANN works with exactly that logic for vectors.

How ANN algorithms pull it off (a bird's-eye view)

There are three main families you'll see in production:

HNSW (Hierarchical Navigable Small World):

• Builds a layered graph. The upper layers have few nodes with long jumps. The lower layers have many nodes with short jumps.
• To search, you start at the top and descend, "zooming in" toward the right cluster.
• Complexity: O(log n)
• Typical accuracy: 95-99%
• It's what ChromaDB, Weaviate, Qdrant, Pinecone use

IVF (Inverted File Index):

• Groups vectors into clusters (k-means). To search, you first find the cluster closest to your query, then search within that cluster.
• Complexity: O(√n) approximate
• Typical accuracy: 90-95%
• Used by Faiss (Meta), Milvus

PQ (Product Quantization):

• Compresses each vector into a short code. It loses precision in exchange for 4-8x less memory.
• Usually combined with IVF for extreme scale.
• Typical accuracy: 85-90%
• For datasets of hundreds of millions of vectors where memory is the constraint

The entire Module 2 is about how these algorithms work internally. For now, the insight that matters: they exist, they're fast, and they're the reason vector databases do what they do.

Numerical comparison: numpy vs ANN

Over the same 1M vectors of 1536 dimensions:

Takeaways:

1. HNSW is ~90x faster than brute force, with 98% accuracy. For almost any RAG, this is the right choice.
2. IVF is ~25x faster, ~5% less accuracy. A good balance when memory is tight.
3. PQ is 16x faster and uses 6x less memory. Appropriate when your dataset grows to 10M+ vectors.

Applied to the RAG pipeline:

Pipeline with HNSW:
Query embedding:    150 ms
Retrieval:           14 ms  ← ANN
Generation:       1,200 ms
─────────────────────────
Total:            1,364 ms  ✅ Excellent

Pipeline with brute force:
Query embedding:    150 ms
Retrieval:        1,287 ms  ← brute force
Generation:       1,200 ms
─────────────────────────
Total:            2,637 ms  ⚠️ Close to the 3s limit

And that's for a single query. With 200 concurrent queries, brute force collapses the server while HNSW responds without breaking a sweat.

Why conventional tools fail

Let's close the capsule with a summary table — you'll see details on each one in the following capsules:

Point: the "I already have X and I'll add vector search" options work, but they are consistently slower than dedicated vector DBs — because their architecture is optimized for something else (SQL queries, full-text search, etc.).

Capsules 03 and 04 cover why SQL/NoSQL fail in detail, and why numpy/pandas don't scale beyond the prototype.

Pitfalls and common mistakes

Pitfall 1: measuring only the optimistic case

The mistake: you measure brute force with 10K vectors, see 12ms, decide "this is fast, I'll stick with numpy."

Symptom: weeks later, when you put 200K documents into production, the system starts taking seconds. You don't understand why — "it used to work fine."

How to prevent it: from the start, measure with the dataset size expected in 6-12 months, not the current size. If you project 1M vectors, benchmark with 1M synthetic vectors before choosing the architecture.

Pitfall 2: confusing "exact NN" with "the LLM's correct answer"

The mistake: you assume that because ANN has 98% accuracy, your RAG will have 98% correct answers.

Reality: retrieval accuracy is just one of the components of the final quality. The LLM can give a perfect answer with "almost but not exactly correct" chunks, or a bad answer with the perfect chunks. Retrieval accuracy only matters if it affects the quality of the answer.

How to prevent it: measure accuracy end-to-end (does the system answer well?) in addition to retrieval accuracy. Guide #12 (Evaluation Frameworks) covers this.

Pitfall 3: optimizing latency without measuring generation

The mistake: you spend 3 weeks bringing retrieval down from 100ms to 20ms. The user doesn't notice the difference.

Symptom: retrieval is 100ms, generation is 2500ms. Total latency goes from 2750ms to 2670ms — a 3% invisible improvement.

How to prevent it: measure what percentage of the total time each component consumes. Optimize the most expensive one first. For typical RAG it's generation, not retrieval — and to optimize generation you use caching, smaller models, or streaming, not switching vector databases.

Pitfall 4: assuming more vectors = better RAG

The mistake: "let's put in all the documentation we have, more data = better." You start with 50K, end up with 5M.

Symptom: retrieval quality drops because there are too many irrelevant docs "diluting" the result. Queries return tangential chunks instead of the exact ones.

How to prevent it: curate the dataset. More data only helps if the new data is relevant to the expected queries. Old, duplicate, or irrelevant documents make the system worse, not better.

Applied exercise

Scenario: a colleague shows you their RAG prototype. They built it like this:

# rag_prototype.py
import numpy as np
import openai
import pandas as pd

# Load 80,000 pre-embedded chunks in pandas
df = pd.read_parquet("embeddings.parquet")  # columns: chunk_id, text, embedding

def search(query: str, k: int = 5):
    query_emb = openai.embeddings.create(
        input=query, model="text-embedding-3-small"
    ).data[0].embedding

    # Iterate row by row to compute similarity
    similarities = []
    for _, row in df.iterrows():
        sim = np.dot(query_emb, row['embedding']) / (
            np.linalg.norm(query_emb) * np.linalg.norm(row['embedding'])
        )
        similarities.append(sim)

    df['similarity'] = similarities
    return df.nlargest(k, 'similarity')[['chunk_id', 'text', 'similarity']]

They tell you: "It runs on my machine. I want to deploy to production next week. It's going to get ~30 queries per minute. Ready?"

Your job: identify the three critical problems with this code and propose a solution for each, with numerical justification.

# Stack the embeddings as a matrix (once, at load time)
embeddings_matrix = np.vstack(df['embedding'].values)
embeddings_norm = embeddings_matrix / np.linalg.norm(embeddings_matrix, axis=1, keepdims=True)

def search(query: str, k: int = 5):
    query_emb = get_query_embedding(query)
    query_norm = query_emb / np.linalg.norm(query_emb)
    similarities = np.dot(embeddings_norm, query_norm)
    top_k_idx = np.argsort(similarities)[-k:][::-1]
    return df.iloc[top_k_idx]

import chromadb
from chromadb.utils import embedding_functions

openai_ef = embedding_functions.OpenAIEmbeddingFunction(
    api_key=os.getenv("OPENAI_API_KEY"),
    model_name="text-embedding-3-small"
)
client = chromadb.PersistentClient(path="./chroma_db")
collection = client.get_or_create_collection(
    name="docs",
    embedding_function=openai_ef
)

def search(query: str, k: int = 5):
    return collection.query(query_texts=[query], n_results=k)

from functools import lru_cache
import hashlib

@lru_cache(maxsize=10_000)
def get_query_embedding_cached(query: str):
    # Cache hit: 0.1ms. Cache miss: 150ms (call to OpenAI)
    return openai.embeddings.create(
        input=query, model="text-embedding-3-small"
    ).data[0].embedding

Summary and next step

What you learned:

• RAG has four phases. The two online ones (retrieval + generation) define the latency the user perceives.
• The typical budget for retrieval is 200-500ms. The rest goes to query embedding and generation.
• Brute force with numpy is O(n) and collapses with 100K+ vectors. For 1M vectors it takes >1 second, unacceptable.
• ANN (Approximate Nearest Neighbors) sacrifices 1-5% accuracy for 100-1000x less latency. For RAG, the trade-off is clearly positive.
• HNSW, IVF, and PQ are the three main families of ANN algorithms. ChromaDB and most vector DBs use HNSW by default.
• Optimizing retrieval is useless if generation is the bottleneck. Measure before optimizing.

Checkpoint: before moving on, you should be able to:

• Calculate the retrieval budget for a system with a <2 second SLA.
• Predict when brute force with numpy is going to fail (typical threshold: 100K vectors).
• Explain why 98% ANN accuracy is enough for RAG in practice.

Next capsule: 03 — Why SQL/NoSQL don't work for semantic search.

You've just understood that RAG needs specialized tools. The next capsule explains why the tools you already have in your stack (Postgres, MongoDB, Elasticsearch) aren't the answer — even though they "almost" work. You'll see where they fail, when "almost" is enough, and when you definitely need a dedicated vector database.

Resources

1. Original RAG Paper (Lewis et al., 2020) — The paper that defined the pattern
2. Approximate Nearest Neighbors Explained (Simon Willison) — Accessible explanation without math
3. HNSW Algorithm (Malkov & Yashunin, 2018) — Technical paper, optional
4. ANN Benchmarks — Reproducible comparison of algorithms
5. Pinecone — Vector Database Fundamentals — Market overview
6. LangChain — RAG from Scratch — Practical application of the concept

Estimated time: 25-30 minutes Next: 03-why-sql-and-nosql-fall-short.md