RAG Search Algorithms - How Retrieval Actually Works Under the Hood

Every agentic AI system that "looks things up" before answering — a support bot searching a knowledge base, a coding agent searching a codebase, a research assistant searching PDFs — is running a Retrieval-Augmented Generation (RAG) pipeline underneath. The retrieval step is the part that decides what the model even gets to see before it writes an answer. If retrieval pulls the wrong chunks, no amount of prompt engineering on the generation side will save the output.

Most tutorials treat "search" as a black box: throw text at a vector database, get chunks back. But there are five distinct families of search algorithms in production RAG systems today, each solving a different retrieval failure mode. Picking the right one — or the right combination — is the single highest-leverage decision in a RAG pipeline.

This post walks through each family: how it works, a diagram of the mechanism, the best use case, and a worked example.

1. Keyword (Lexical) Search — Matching Characters, Not Meaning

Lexical search treats text as strings. It doesn't understand that "car" and "automobile" mean the same thing — it only knows whether the same tokens appear in the query and the document.

TF-IDF — The Starting Point

TF-IDF is the original mathematical approach to lexical relevance. It scores a term in a document using two factors:

term frequency (how often the word appears in that document) and

inverse document frequency (how rare the word is across the whole corpus — common words like "the" get down-weighted, rare words get boosted).

The drawback: TF-IDF has no length normalization. A term appearing 5 times in a 50-word document and 5 times in a 5,000-word document gets scored the same way, even though the first is clearly far more "about" that term. This means very long documents can be unfairly penalized or short documents unfairly boosted, purely as an artifact of length rather than actual relevance.

Best for: simple keyword scoring where all documents are roughly the same length, or as a teaching baseline. In practice, most production systems have moved past it for the reason above.

BM25 (Best Matching 25) — Fixing TF-IDF's Length Problem

BM25 keeps the same core idea as TF-IDF — term frequency weighted by inverse document frequency — but adds length normalization, so a document doesn't score higher just because it's longer, and diminishing returns on term frequency, so a word appearing 50 times doesn't score 10x higher than one appearing 5 times. This is why BM25 replaced TF-IDF as the industry-standard lexical algorithm.

Best for: exact identifiers — part numbers, error codes, SKUs, legal citations, API method names — anything where a semantic model might "helpfully" match a conceptually similar but factually wrong result.

Example: A support agent searches "error code E4021." A vector search might return docs about "connection timeout errors" in general (semantically close but wrong). BM25 returns only the doc that literally contains "E4021," because it's matching the exact token.

2. Dense Vector (Semantic) Search — Matching Meaning, Not Characters

Instead of comparing strings, dense retrieval converts text into embeddings — high-dimensional vectors where semantically similar text ends up numerically close together. The retrieval problem then becomes "find the nearest vectors," which is where the index algorithms below come in.

Exhaustive k-NN — The Naive Baseline

The simplest possible approach: compare the query vector against every single vector in the database and return the closest matches. This is brute-force search.

The drawback: it's 100% accurate — there's no approximation, so you always get the true nearest neighbors — but the cost scales linearly with the number of vectors. Past roughly hundreds of thousands of vectors, comparing against everything on every query becomes too slow for production latency budgets.

Best for: small corpora (a few thousand chunks) or as a correctness baseline when validating that a faster, approximate index isn't silently losing relevant results.

IVF (Inverted File Indexing) — Trading Some Accuracy for Speed

IVF's fix for exhaustive search's scaling problem is to pre-cluster the vector space (e.g., via k-means) into buckets ahead of time. At query time, instead of scanning every vector, it only searches the nearest cluster(s) to the query — a much smaller subset of the total data.

The drawback: because it only checks the nearest cluster(s), a true nearest neighbor that happens to sit just across a cluster boundary can be missed. It's faster than exhaustive search, but the accuracy/speed trade-off still isn't ideal for very high-dimensional, high-recall production workloads — which is what pushed the field toward graph-based indexes.

Best for: very large datasets where memory footprint matters more than squeezing out the last few percentage points of recall — common in on-disk vector indexes.

HNSW (Hierarchical Navigable Small World)

HNSW addresses the weaknesses of both approaches above with a different data structure entirely: a multi-layer graph, similar in spirit to a skip list. The top layers are sparse and let the search jump across large distances quickly to find the right neighborhood; lower layers are dense and let it drill down to precise matches — without needing to touch every vector (like exhaustive k-NN) or accept a rigid cluster boundary (like IVF).

The search starts at node A on the sparsest top layer, where only a couple of nodes exist — enough to tell it should head toward the "D" side of the graph rather than search everywhere. It drops down a layer (more nodes now, layer 1), refines its position, and drops down again to the bottom layer where every node lives. By this point it's already standing right next to the true answer, so it only has to check a few close neighbors (C and D) instead of all seven nodes shown here — and in a real index, instead of all vectors in the entire database.

This is why HNSW has become the most widely used ANN algorithm in production vector databases — it gets close to exhaustive-search recall at a small fraction of the latency, and scales to millions of vectors without the boundary-miss problem IVF has.

Best for: production semantic search at scale — millions of chunks where you need sub-100ms latency and can tolerate "approximate" (not guaranteed 100% exact) nearest neighbors.

Example: A user asks "how do I get a refund," and the knowledge base document is phrased "requesting reimbursement for a purchase." No shared keywords, but HNSW retrieves it because the embeddings land close together in vector space — at a latency exhaustive k-NN couldn't match at that corpus size.

Distance Metrics

The three algorithms above all need a way to define "closeness":

• Cosine similarity — compares the angle between vectors, ignoring magnitude. Most common default for text embeddings.

• Dot product — factors in magnitude as well as direction; used when embedding magnitude is meaningful (e.g., some recommendation embeddings).

• Euclidean distance — straight-line distance; common in image or spatial embeddings.

3. Hybrid Search & Fusion — Getting the Best of Both Worlds

Lexical search misses paraphrases. Vector search misses exact identifiers. Production RAG systems increasingly run both in parallel and fuse the results.

The big picture: hybrid search isn't one algorithm — it's a pattern. The same query is sent to two independent search systems at once (BM25 and vector search), and the two result lists are then merged into one by a fusion method. The fusion method is the only part that varies — the two most common ones are RRF and weighted scoring, covered below.

With that overview in mind, here's how each fusion method actually works.

RRF (Reciprocal Rank Fusion)

Vector search returns a decimal similarity score (e.g., 0.82) and BM25 returns an unbounded score (e.g., 14.5) — you can't just add them together, the scales aren't comparable. RRF sidesteps this entirely: it only looks at rank position in each result list. A document ranked #1 in either list gets a high reciprocal score (1/1); one ranked #100 gets a tiny score (1/100). Scores from both lists are summed to produce one merged ranking.

Best for: general-purpose RAG where queries are unpredictable — sometimes users type exact terms, sometimes they paraphrase. RRF requires no score calibration or tuning, which makes it a safe default.

Example: A query for "PGVector connection pooling" gets exact-match boost from BM25 on "PGVector," while the vector search separately surfaces a doc titled "managing database connections at scale" that never says "PGVector." RRF merges both into one ranked list instead of picking one method and losing the other's catch.

Weighted Scoring

Assigns a tunable ratio (e.g., 70% vector, 30% keyword) and computes a blended score directly.

Easy way to think about it: instead of only caring about rank position like RRF does, weighted scoring uses the actual similarity numbers — but first it decides in advance how much to trust each search method, like a recipe with fixed proportions, and mixes them in that ratio every time.

Unlike RRF, the raw scores from each method have to be normalized onto the same 0–1 scale first (since 0.82 and 14.5 aren't comparable as-is), then each normalized score is multiplied by its fixed weight (0.7 and 0.3 here) and added together. That 70/30 split isn't automatic — someone has to decide it, usually by testing which ratio produces the best results on real queries for that specific domain.

Best for: domains where you've empirically validated that one signal should dominate — e.g., an e-commerce catalog where exact SKU matches (keyword) should almost always outrank semantic similarity.

4. Post-Retrieval Algorithms — Filtering the Noise After Retrieval

Once candidates are retrieved, a second algorithmic pass improves precision before anything reaches the LLM.

Cross-Encoder Reranking

Standard vector search (a "bi-encoder") embeds the query and each document independently, then compares vectors — fast, but blind to interactions between query and document. A cross-encoder reranker instead feeds the query and each candidate document together into a model that scores relevance directly. It's computationally heavier (can't be pre-computed or indexed), so it's only run on the top candidates from the first retrieval pass, not the whole corpus.

Best for: any pipeline where context window budget is tight and precision at the top of the list matters more than recall — which is nearly every production RAG system, since LLMs weight earlier context more heavily and irrelevant chunks dilute the answer.

Example: Initial retrieval returns 50 loosely-related chunks about "database indexing." The reranker re-scores all 50 against the actual query "why is my B-tree index not being used in this query plan" and pushes the 3 genuinely relevant chunks to the top, discarding the rest before they ever hit the LLM.

Metadata Filtering

Hard constraints applied before or after the similarity search — e.g., "only search documents where department = engineering" or "only chunks published after 2024." This isn't a ranking algorithm; it's a boundary that the ranking algorithms operate within.

Best for: multi-tenant systems, access control, or time-sensitive corpora where irrelevant-but-similar content from the wrong tenant or an outdated version must never surface, regardless of similarity score.

5. Multi-Hop and Graph-Based Search — Answering Across Documents

Vector and keyword search both operate on isolated chunks. Some questions need information stitched together across multiple documents — that's where graph-based and hypothetical-document approaches come in.

GraphRAG

GraphRAG parses unstructured text into a knowledge graph of entities and relationships, then uses graph traversal and community-detection algorithms to answer questions that span multiple disconnected source documents — something flat chunk retrieval structurally can't do well, since no single chunk contains the full answer.

Best for: questions requiring reasoning across many documents — "how are Team A's incidents connected to the vendor outage last quarter" — where the answer doesn't live in any single chunk.

Example: Asking "which customers were affected by the same root cause as the March outage" requires connecting an incident report, a customer ticket log, and a vendor postmortem — three separate documents. GraphRAG traverses the entity graph (incident → root cause → affected services → customers) to compile the answer; a single vector search over chunks would never connect all three.

6. Query Transformation — Rewriting the Question Before Searching

Every algorithm so far changes how documents are searched. This category is different: it changes what gets searched for — the query itself is rewritten before it ever reaches a retrieval algorithm. This runs at query time only; it doesn't touch or restructure the document corpus at all, which is what separates it from GraphRAG above.

HyDE (Hypothetical Document Embeddings)

An LLM first generates a hypothetical, idealized answer to the query. That hypothetical answer — not the raw question — is embedded and used to search the database. The intuition: an answer-shaped piece of text is often closer in vector space to real answer documents than a short, terse question is.

Best for: queries that are short, vague, or phrased very differently from how the source documents are written — where a literal embedding of the question undershoots the semantic target.

Choosing the Right Algorithm: Decision Guide

Trade-off Summary Table

Where This Fits in the Agentic AI Stack

Retrieval is the layer beneath everything else in an agentic RAG system — before tool selection, before reasoning chains, before final generation. Getting it wrong silently degrades every downstream step, because the agent reasons confidently over whatever context it was given, right or wrong.