RAG at scale

1 · The scaling wall

Every retriever so far scored the query against every stored vector and kept the best. That is brute-force (or “flat”) search, and it is exactly right at small scale: it is simple, it is exact (it truly finds the nearest neighbours), and for a few thousand chunks it is instant. The problem is the cost curve. Comparing the query against N vectors of dimension d costs O(N·d) per query: double the corpus, double the work, on every single query. Fine at thousands; a wall at millions.

Rather than time it (clocks are noisy and non-deterministic), we count operations. Each full vector comparison bumps a counter, so the growth is exact and reproducible. Watch comparisons track N one-for-one:

scaling_wall.py# Brute-force search cost, measured with an OPERATION COUNTER (not a clock).
# Every vector comparison bumps the counter, so cost is deterministic and reproducible.

def make_index(n, dims=8):
    """Deterministic fake vectors: value depends only on (row, col)."""
    return [[((r * 7 + c * 13) % 17) / 17.0 for c in range(dims)] for r in range(n)]

comparisons = 0
def cosine(a, b):
    global comparisons
    comparisons += 1                      # one full vector compared = one op
    dot = sum(x * y for x, y in zip(a, b))
    na = sum(x * x for x in a) ** 0.5
    nb = sum(x * x for x in b) ** 0.5
    return dot / (na * nb + 1e-9)

def brute_force(query, index):
    return max(range(len(index)), key=lambda i: cosine(query, index[i]))

query = [0.5] * 8
for n in (1000, 2000, 4000, 8000):
    index = make_index(n)
    comparisons = 0
    brute_force(query, index)
    print(f'N={n:>5}  comparisons={comparisons:>5}  (== N, grows linearly)')

N= 1000  comparisons= 1000  (== N, grows linearly)
N= 2000  comparisons= 2000  (== N, grows linearly)
N= 4000  comparisons= 4000  (== N, grows linearly)
N= 8000  comparisons= 8000  (== N, grows linearly)

The comparison count equals N every time — that is the O(N) part, and each comparison itself costs O(d). At 10k vectors nobody notices; at 10 million, a single query touches 10 million vectors, and if you serve hundreds of queries per second the machine melts. You cannot brute-force your way to scale — you need a data structure that finds near vectors without scanning them all.

2 · Approximate nearest neighbours (ANN)

The escape is to stop insisting on the exact nearest neighbours. Approximate nearest neighbour search accepts that it will occasionally miss a true top result, in exchange for touching a tiny fraction of the vectors. The knob is recall — the fraction of true neighbours the approximate search still finds — and in practice you can hold recall very high (say 0.95–0.99, illustrative) while inspecting orders of magnitude fewer vectors. That trade is the entire reason production RAG can exist at scale. Two families dominate, and it is worth holding both as mental pictures:

We will not build a real HNSW graph — that is a substantial system and the whole point of using a library is that someone already did it correctly. But the IVF idea is small enough to simulate, and it makes the recall trade concrete. Below we cluster 600 vectors into 4 buckets, then search only the nprobe nearest buckets, counting how many vectors we inspect versus brute force:

ivf_sim.py# IVF idea: cluster vectors, then search ONLY the nearest cluster(s).
# We count how many vectors each strategy inspects. Fully deterministic.

def make_vectors(n, dims=4):
    # spread points across the space so all clusters get populated
    return [[((r * 2 + c * 7) % 13) / 13.0 for c in range(dims)] for r in range(n)]

def dist2(a, b):
    return sum((x - y) ** 2 for x, y in zip(a, b))

def cosine(a, b):
    dot = sum(x * y for x, y in zip(a, b))
    na = sum(x * x for x in a) ** 0.5
    nb = sum(x * x for x in b) ** 0.5
    return dot / (na * nb + 1e-9)

# ---- build: assign each vector to its nearest of C fixed centroids (IVF 'inverted lists') ----
vectors = make_vectors(600, dims=4)
centroids = [[0.15, 0.25, 0.75, 0.35], [0.75, 0.65, 0.2, 0.25],
             [0.25, 0.85, 0.35, 0.7], [0.85, 0.2, 0.55, 0.8]]
lists = {c: [] for c in range(len(centroids))}
for i, v in enumerate(vectors):
    nearest_c = min(range(len(centroids)), key=lambda c: dist2(v, centroids[c]))
    lists[nearest_c].append(i)

query = [0.2, 0.3, 0.7, 0.4]

# ---- brute force: inspect every vector, exact answer ----
bf_inspected = len(vectors)
bf_best = max(range(len(vectors)), key=lambda i: cosine(query, vectors[i]))

# ---- IVF: probe only the nprobe nearest clusters ----
def ivf_search(query, nprobe):
    order = sorted(range(len(centroids)), key=lambda c: dist2(query, centroids[c]))
    probed = order[:nprobe]
    candidates = [i for c in probed for i in lists[c]]
    inspected = len(candidates)
    best = max(candidates, key=lambda i: cosine(query, vectors[i]))
    return best, inspected

for c in range(len(centroids)):
    print(f'cluster {c}: {len(lists[c])} vectors')
print(f'\nbrute force : inspected {bf_inspected}, best index {bf_best}')
for nprobe in (1, 2, 3):
    best, inspected = ivf_search(query, nprobe)
    hit = 'HIT ' if best == bf_best else 'MISS'
    print(f'IVF nprobe={nprobe}: inspected {inspected:>3}, best index {best}  ({hit} vs brute force)')

cluster 0: 184 vectors
cluster 1: 92 vectors
cluster 2: 232 vectors
cluster 3: 92 vectors

brute force : inspected 600, best index 12
IVF nprobe=1: inspected 184, best index 11  (MISS vs brute force)
IVF nprobe=2: inspected 416, best index 11  (MISS vs brute force)
IVF nprobe=3: inspected 508, best index 12  (HIT  vs brute force)

This is the recall trade in one run. At nprobe=1 we inspected only 184 of 600 vectors — a big saving — but the true best (index 12) sat in a cluster we didn't probe, so we returned a near-but-wrong neighbour (index 11): a recall miss. Probing more clusters inspects more vectors and, by nprobe=3, recovers the exact answer. That is the entire ANN dial: more probing → higher recall → more work. A real IVF over millions of vectors would use many more clusters so even a small nprobe skips the vast majority of the corpus, and HNSW reaches similar recall by graph-walking instead of clustering.

3 · Vector databases — library vs managed

An ANN index is just the search structure. A real system needs much more around it, and that is what a vector database provides. You have two broad ways to get there, and the honest framing is a trade-off, not a winner — the right choice depends on your team, scale, and constraints:

Whichever you pick, the query interface is the one you already know from 3.1–3.3: embed the query, ask the index for the top-k, optionally with a metadata where filter and hybrid keyword fusion. The database changes where the vectors live and who operates it, not the retrieve → augment → generate shape.

4 · Sharding & distribution

A single node holds only so many vectors in memory and serves only so many QPS. When one machine isn't enough, you shard: split the index across several nodes so each holds a slice of the corpus. A query then fans out to all shards, each returns its local top-k, and a coordinator merges them — the classic scatter-gather pattern.

5 · Ingestion at scale & freshness

The index isn't built once and frozen — documents are added, changed, and deleted continuously, and every change means embedding text and updating the index. How you feed that pipeline decides how fresh your answers are:

Three ingestion realities bite specifically at scale:

6 · Caching — embeddings & query results

Real traffic is skewed: a small set of popular queries and documents accounts for a large share of requests. Caching exploits that. Two layers pay off, and both cut the expensive embedding calls:

Here is both ideas in one runnable simulation. We count how many times the pretend-expensive embed() actually runs, and how many requests are served straight from the result cache:

caching.py# Caching: skip re-embedding text we've seen, and skip re-retrieving repeated queries.
# We count how many times the (expensive) embed function actually runs. Deterministic.

embed_calls = 0
_embed_cache = {}

def embed(text):
    """Pretend-expensive embedder. The cache makes repeats free."""
    global embed_calls
    if text in _embed_cache:
        return _embed_cache[text]          # cache HIT: no work
    embed_calls += 1                       # cache MISS: pay the cost once
    vec = [(sum(ord(ch) for ch in text) + i) % 97 / 97.0 for i in range(4)]
    _embed_cache[text] = vec
    return vec

# A stream of queries where some repeat (real traffic is very skewed toward popular ones).
queries = ['reset password', 'refund policy', 'reset password',
           'reset password', 'refund policy', 'shipping time']

query_cache = {}
query_cache_hits = 0
for q in queries:
    if q in query_cache:
        query_cache_hits += 1              # served straight from the result cache
        continue
    query_cache[q] = embed(q)              # miss: embed + (would retrieve) once

print(f'requests            : {len(queries)}')
print(f'distinct queries    : {len(set(queries))}')
print(f'embed() calls made  : {embed_calls}   (== distinct queries, repeats were free)')
print(f'query-cache hits     : {query_cache_hits}')
print(f'work avoided         : {query_cache_hits}/{len(queries)} requests served from cache')

requests            : 6
distinct queries    : 3
embed() calls made  : 3   (== distinct queries, repeats were free)
query-cache hits     : 3
work avoided         : 3/6 requests served from cache

Six requests, but only three distinct queries — so embed() ran three times and half the requests were served from the result cache with zero retrieval work. On skewed real traffic the hit rate is often far higher. The catch is invalidation: a cached result is only correct until the underlying documents change.

7 · Thinking in a cost & latency budget

At scale, every design choice is a spend. It helps to think of a per-query budget — a latency budget (how long a user waits) and a cost budget (money per query) — and to know which stage spends what. The numbers below are illustrative placeholders to show the shape of the reasoning, not measurements — your real figures depend on your models, data, and infrastructure, so measure them: