Retrieval

Retrieval in RAG is the process of finding the most relevant document chunks for a query using techniques like BM25 (lexical), dense retrieval (embedding-based), and hybrid search (combining both), often followed by reranking and accelerated with approximate nearest neighbor (ANN) search methods such as HNSW and FAISS.

BM25: lexical (sparse) retrieval

BM25 (Best Matching 25) is a classic ranking function used in keyword search systems.

How BM25 works (conceptually)

It treats each document and query as a bag of tokens (words).
For each query term, it computes a score based on:
- Term frequency (TF): how often the term appears in the document.
- Inverse document frequency (IDF): how rare the term is across the corpus.
- Document length normalization: penalizes very long documents that might just repeat terms.

Simplified idea:

$score (d, q) = \sum_{t \in q} IDF (t) \cdot \frac{f ( t , d ) \cdot ( k _{1} + 1 )}{f ( t , d ) + k _{1} \cdot ( 1 - b + b \cdot \frac{∣ d ∣}{avglen} )}$

$f (t, d)$ : frequency of term $t$ in document $d$ .
$∣ d ∣$ : document length.
$k_{1}, b$ : tuning parameters.
$avglen$ : average document length.

Strengths of BM25

Fast and simple: very efficient to compute and index.
Excellent for exact matches: e.g., product codes, names, specific identifiers.

Weaknesses of BM25

No semantic understanding: cannot handle fuzzy queries or intent.
Struggles with ambiguous or short queries without context.

Use BM25 when:

Your domain has many exact identifiers (codes, IDs, product names).
You need fast, low-cost retrieval with high precision for exact matches.
You want a simple, interpretable baseline.

Dense retrieval: embedding-based search

Dense retrieval uses neural embeddings to represent queries and documents as vectors and finds similar vectors in a high-dimensional space.

How dense retrieval works

Encode query qqq into embedding q using a model (e.g., Sentence‑BERT, E5).
Encode each document chunk di into di
Compute similarity (often cosine similarity or dot product) between q and all di.
Return top‑k most similar chunks.

Strengths of dense retrieval

Semantic matching: finds related meanings even without exact word overlap (“pizza” ↔ “Italian flatbread with toppings”)
Handles synonyms, vocabulary mismatch, and fuzzy queries.
Can support multilingual search if trained on parallel corpora.

Weaknesses of dense retrieval

Higher cost: generating embeddings (50–200 ms per doc) + maintaining vector index.
Less precise on exact identifiers: embeddings for “XYZ-1234” are noisy; may match similar codes instead
Slower to update: new documents need embedding generation and vector index updates.

Use dense retrieval when:

Queries are semantic, fuzzy, or phrased differently from documents.
You need to capture meaning beyond exact words.
You can afford the extra compute and operational complexity.

Hybrid search: combining BM25 and dense retrieval

Hybrid search merges lexical (BM25) and dense (embedding) retrieval to exploit their complementary strengths.

Why hybrid?

BM25: great for exact matches, codes, rare terms.
Dense: great for semantics, synonyms, intent.
Together: they cover more query types and reduce failures of each approach.

Typical hybrid architecture

Parallel retrieval:
- Run BM25 query → get ranked list Lbm25L_{bm25}Lbm25.
- Run dense vector query → get ranked list LdenseL_{dense}Ldense.
Fusion:
- Combine $L_{bm 25}$ and $L_{d e n se}$ into a single ranked list.
- Common method: Reciprocal Rank Fusion (RRF): $score (d) = \frac{1}{k + rank _{bm 25} ( d )} + \frac{1}{k + rank _{d e n se} ( d )}$ where $k$ is typically around 60, and rank is position in each list (1 for top).
- Optionally, use weighted sums or learned fusion models.
Reranking (optional):
- Pass top candidates to a reranker model for more accurate final ordering.

Practical tips

Start with BM25 alone as a baseline; add dense retrieval when vocabulary mismatch becomes a problem.
Tune weights/fusion parameters based on evaluation metrics (recall, precision, NDCG).
Use metadata filters (e.g., document type, date, department) on both branches before fusion.

Hybrid search is now the default in many production RAG systems because it consistently outperforms pure BM25 or pure dense retrieval

Rerankers: improving final ordering

After retrieval (BM25, dense, or hybrid), you often have a candidate set (e.g., top 50–100 chunks). A reranker reorders these more precisely.

What rerankers do

They take a query–document pair and compute a more refined relevance score.
Unlike retrieval models (which are often bi-encoders: query and doc encoded separately), rerankers are usually cross-encoders that jointly process query and doc for better accuracy but higher cost.

Types of rerankers

Neural cross-encoders (e.g., BERT-based): high quality, more expensive.
Lighter models or rule-based reordering (e.g., boosting by metadata, recency).
Learned fusion methods that combine BM25 score, dense score, and metadata signals.

Placement in pipeline

Retrieval: BM25 + dense → top‑k candidates.
Rerank: cross-encoder or fusion model → final top‑k for LLM.
Generation: LLM uses reranked context.

Trade-off:

Rerankers improve accuracy but add latency.
Use them when retrieval quality is critical and you can afford the extra compute.

Approximate Nearest Neighbor (ANN) search

In dense retrieval, you need to find the nearest neighbors of a query vector among millions of document vectors. Exact search is too slow; ANN algorithms approximate this quickly.

ANN goal

Find vectors close to q\mathbf{q}q with high recall (most true neighbors) and low latency.
Trade-off: slightly approximate results, but much faster.

Common ANN algorithms:

1. HNSW (Hierarchical Navigable Small World)

Builds a multi-level graph where nodes are vectors.
Higher levels have fewer nodes and provide coarse navigation; lower levels are detailed.
Search starts at top, navigates down, finding neighbors efficiently.

Characteristics:

Very good recall–latency trade-off.
Works well for high-dimensional embeddings.
Used in many vector DBs (e.g., FAISS, Weaviate, Qdrant).

2. IVF (Inverted File Index)

Clusters vectors into clusters (via KMeans, etc.).
Each cluster has an “inverted file” of vectors belonging to it.
For a query:
1. Find closest clusters.
2. Search only vectors in those clusters.