Why RAG Doesn't Compare Every Vector (And What It Does Instead)

Grounded / Real Inflated / Uruttu

65% real

35% uruttu

article Original Content

If semantic search compared every embedding, RAG wouldn't scale.
Here's what makes retrieval fast in vector-based RAG.

Your documents live as embeddings, so you can search by meaning instead of exact wording.

Answering a query means finding the vectors closest to it.

The obvious way: compare against every stored vector, return the closest.
That is exact nearest neighbour search.
↳ Cost: O(N) per query, N = number of stored vectors.

Imagine searching millions of documents to answer a single query.
It is too slow and does not scale.

So, what do you do?

𝗜𝗻𝗱𝗲𝘅𝗶𝗻𝗴

Indexing is organising high-dimensional vector embeddings into a data structure that enables fast similarity search.

That data structure is Approximate Nearest Neighbour (ANN).
↳ Cost: O(log N) per query

Since meaning is encoded into vectors, here similarity search = semantic search.

For example: Hierarchical Navigable Small World (HNSW)

→ It organises embeddings in a multi-layer graph.
→ Each layer contains vectors as nodes.
→ Every node is connected to its nearest neighbours via edges.

Traversing and descending through the layers routes the query to the right neighbourhood cheaply.

ANN algorithms trade a small amount of recall accuracy for massive speed gains.
Which is why retrieval rarely ends at the vector search: pipelines fetch more candidates, then re-rank.

𝗪𝗵𝗲𝗿𝗲 𝗶𝘁 𝗮𝗹𝗹 𝗹𝗶𝘃𝗲𝘀

A vector database.

It is the storage system that enables fast similarity search at scale and exposes a search API on top of it.

This is where indexing arranges embeddings into ANN structures.

It holds:

→ the embedding vectors
→ the original text
→ the metadata you filter on
→ the ANN index

Indexing is not a one-time build. The structure is maintained on every insert, update and delete.

This is what makes fast retrieval possible in vector-based RAG.

💾 Save this for your next build
➕ Follow for more practical GenAI insights
♻ Repost if this helps someone in your network

verified Validated Content

Here's a fact-check of the post's claims:

Solidly correct

Exact NN search is O(N) per query — correct, brute force compares the query against every stored vector.
HNSW is a multi-layer graph where nodes connect to nearby neighbors and search descends through layers to a target region — this is an accurate high-level description of the algorithm.
ANN trades recall for speed — correct and a well-known property of every ANN method (HNSW, IVF, LSH, etc.).
Retrieval pipelines often re-rank after ANN search — correct; this is standard practice (retrieve top-k candidates, then apply a more expensive/accurate re-ranker).
Vector databases store embeddings, original text/metadata, and the ANN index, and maintain the index on insert/update/delete — accurate description of how systems like Pinecone, Milvus, Weaviate, etc. work.

Correct but oversimplified

"ANN cost: O(log N) per query." This figure is widely repeated (including in vendor blogs like Zilliz/Milvus) and isn't wrong as a rough intuition, but it's not a rigorous guarantee. For graph-based methods like HNSW, it's difficult to provide a strict complexity analysis since no graph-based method currently offers such a guarantee — in practice the search path length is roughly O(log n), and the O(log N) result technically holds under an idealized assumption of a perfect Delaunay graph, not for real-world constructed graphs. So "O(log N)" is a reasonable practical shorthand, but stating it as a flat fact glosses over the fact that it's an empirical/approximate property, not a proven worst-case bound the way O(N) is for brute force.
"Since meaning is encoded into vectors, similarity search = semantic search." This is true in the sense that embedding-based similarity search is how semantic search is implemented — but it's worth noting semantic search isn't the only kind of vector search (vectors can also encode non-semantic similarity, e.g. image features), so the equivalence holds for RAG's use case but isn't a universal definition.

Minor nitpick

HNSW is one specific ANN method; the post presents it as "the" example correctly (says "for example"), so that's fine — but it's worth knowing other ANN structures exist too (IVF, LSH, product quantization, DiskANN, etc.), each with different complexity trade-offs, so the O(log N) figure specifically describes graph-based methods like HNSW, not ANN indexing in general.

Bottom line: the post's core narrative (brute force doesn't scale → ANN indexing trades exact accuracy for speed → HNSW as the mechanism → vector DB as the storage/orchestration layer) is accurate and a reasonable simplified explainer. The one place to flag if you want full rigor is the O(log N) claim — true as a practical rule of thumb for graph-based ANN, but not a proven worst-case bound like the O(N) brute-force figure it's being contrasted against.