Chapter 5: Retrieval Strategies

Retrieval Strategies: Dense, Sparse, and Hybrid Approaches

Retrieval is the heart of RAG systems—it's the process of finding the most relevant documents for a user's query. There are three main approaches, each with distinct characteristics and use cases.

1. Dense Retrieval (Semantic Search)

What it is: Dense retrieval uses vector embeddings to represent both queries and documents in a high-dimensional space, then finds documents whose embeddings are "close" to the query embedding using similarity metrics like cosine similarity.

How it works:

1. Convert the query into a dense vector using an embedding model (e.g., SentenceTransformer, OpenAI embeddings)
2. Compare this query vector with all document vectors in the vector database
3. Calculate similarity scores (cosine similarity, dot product, or Euclidean distance)
4. Return the top-k documents with highest similarity scores

Key Advantages:

• ✅ Semantic understanding: Understands meaning, not just keywords. A query about "automobile" will find documents about "car," "vehicle," or "auto" even if those exact words aren't present.
• ✅ Handles synonyms and paraphrasing: "Machine learning" and "ML" are treated as similar concepts. "How do I train a model?" finds documents about "model training" even if they use different wording.
• ✅ Context-aware: Understands that "Python programming" is different from "python snake" based on context.
• ✅ Language-agnostic: Works across languages if using multilingual embeddings (e.g., multilingual-MiniLM)
• ✅ Most common in modern RAG: This is the default approach for most production RAG systems

Limitations:

• ❌ More computationally expensive: Requires embedding models and vector similarity calculations
• ❌ May miss exact keyword matches: If a document uses very specific terminology not well-represented in the embedding model's training data, it might be missed
• ❌ Requires good embeddings: Quality depends heavily on the embedding model used
• ❌ Storage overhead: Need to store vector embeddings for all documents

2. Sparse Retrieval (Keyword Search)

What it is: Sparse retrieval uses keyword matching based on term frequency and document frequency. The most common algorithms are BM25 (Best Matching 25) and TF-IDF (Term Frequency-Inverse Document Frequency).

How it works:

1. Extract keywords from the query (tokenization, stemming, stop word removal)
2. Count how often each keyword appears in each document (term frequency)
3. Weight keywords by their rarity across all documents (inverse document frequency - rare words are more important)
4. Calculate a relevance score for each document based on keyword matches
5. Return the top-k documents with highest scores

Key Advantages:

• ✅ Fast: Very efficient, especially with inverted indexes (traditional search engine technology used by Google, Elasticsearch)
• ✅ Good for exact matches: Excellent when you need to find documents containing specific terms or phrases
• ✅ Interpretable: You can see exactly which keywords matched and why a document was retrieved
• ✅ No embedding model needed: Works with raw text, no neural networks required
• ✅ Low storage: Only stores keyword indexes, not full vectors

Limitations:

• ❌ No semantic understanding: "automobile" won't find "car" unless both terms are present in the document
• ❌ Requires exact term matches: Misses synonyms, paraphrases, and related concepts
• ❌ Language-specific: Needs language-specific tokenization and stemming
• ❌ Poor for conceptual queries: Struggles with queries like "things that help you learn" (no specific keywords)

3. Hybrid Retrieval: Best of Both Worlds

What it is: Hybrid retrieval combines dense and sparse retrieval, taking advantage of both approaches' strengths. This is often the best approach for production RAG systems.

How it works:

1. Run both dense retrieval and sparse retrieval separately
2. Get top-k results from each method (e.g., top 50 from each)
3. Combine the results (union or intersection of result sets)
4. Rerank the combined results using a weighted score: final_score = α × dense_score + (1-α) × sparse_score where α is typically 0.3-0.7
5. Return the top-k documents from the reranked list

Why Hybrid Works Better:

• ✅ Catches both semantic and exact matches: Dense finds semantically similar docs, sparse finds exact keyword matches
• ✅ More comprehensive: Less likely to miss relevant documents
• ✅ Better for diverse queries: Some queries benefit from semantic search (conceptual questions), others from keyword search (specific term lookups)
• ✅ Production-proven: Used by many production systems (e.g., Google Search uses hybrid approaches)

When to use:

• ✅ When you have diverse query types (some need semantic understanding, others need exact matches)
• ✅ When retrieval quality is critical and you can afford the computational cost
• ✅ For production systems where you want maximum coverage and accuracy

Reranking: Refining Initial Retrieval Results

Why Reranking is Necessary

Initial retrieval (whether dense, sparse, or hybrid) is fast but not perfect. It uses relatively simple similarity calculations that may not capture the nuanced relationship between a query and a document. Reranking is a second-stage refinement that improves relevance by using more sophisticated (but slower) models.

The Problem with Initial Retrieval:

• ❌ Embedding similarity is approximate: Two documents might have similar embeddings but different relevance to a specific query. For example, two documents about "Python" might be similar (both about programming), but one might be about "Python for data science" and the other about "Python web development" - only one is relevant to a query about "data science."
• ❌ Keyword matching is surface-level: A document might contain all query keywords but not actually answer the question. For example, a document might mention "machine learning" and "tutorial" but be about a different topic entirely.
• ❌ Context matters: The same words in different contexts have different meanings. "Bank" could mean financial institution or river bank.
• ❌ Query intent: Initial retrieval doesn't deeply understand what the user is really asking. A query "how to install" might retrieve documents about installation in general, but the user might specifically want installation on Windows.

The Solution: Reranking

Reranking takes the top-k candidates from initial retrieval (e.g., top 100) and uses a more sophisticated model to re-score and reorder them, producing a final top-k list (e.g., top 5-10) that better matches query intent.

Reranking Methods

1. Cross-Encoder Reranking

What it is: A neural network model (typically BERT-based) that processes the query and document together in a single forward pass, allowing the model to see the full interaction between query and document through attention mechanisms.

How it works:

• Input: [CLS] query [SEP] document [SEP] (concatenated query and document)
• The model processes both simultaneously, allowing attention mechanisms to identify which parts of the document are most relevant to the query
• Output: A relevance score (typically 0-1 or a similarity score)
• Documents are reranked by these scores

Advantages:

• ✅ More accurate: Significantly better than embedding-based similarity because it sees the full query-document interaction
• ✅ Context-aware: Understands how query and document relate in context
• ✅ Better for nuanced queries: Handles complex questions that require deep understanding
• ✅ Production-ready models: Pre-trained models available (e.g., ms-marco-MiniLM, cross-encoder models from SentenceTransformers)

Disadvantages:

• ❌ Slower: Must process each query-document pair separately (can't batch efficiently for different queries)
• ❌ More expensive: Requires running a neural network for each candidate
• ❌ Limited to top-k: Too slow to use on entire document collection (typically used on top 50-200 candidates)

When to use: When you have a small candidate set (50-200 documents) from initial retrieval and want maximum accuracy. This is the most common reranking approach in production RAG systems.

2. LLM-Based Reranking

What it is: Uses a large language model (like GPT-4, Claude) to score or rank documents based on their relevance to the query.

How it works:

• For each candidate document, create a prompt asking the LLM to score relevance
• Example prompt: "Rate how relevant this document is to the query 'X' on a scale of 1-10. Document: [document text]"
• Use LLM's output to rerank documents
• Alternatively, ask LLM to directly rank documents in order of relevance

Advantages:

• ✅ Most accurate: LLMs have deep understanding of language and context
• ✅ Handles complex queries: Can understand nuanced questions and multi-part queries
• ✅ Flexible: Can be prompted to consider specific factors (relevance, completeness, accuracy)

Disadvantages:

• ❌ Very slow: LLM inference is much slower than specialized reranking models
• ❌ Expensive: API costs can be high if reranking many documents
• ❌ Inconsistent: LLM outputs can be non-deterministic
• ❌ Limited scalability: Not practical for high-volume systems

When to use: For high-value queries where accuracy is critical and you can afford the latency and cost. Often used in research or low-volume production systems.

Reranking Best Practices

• Use two-stage retrieval: Fast initial retrieval (dense/sparse) → slower reranking on top-k candidates
• Typical pipeline: Retrieve top 100-200 → Rerank to top 5-10
• Balance accuracy vs speed: More accurate reranking is slower; choose based on your latency requirements
• Cache reranking results: For common queries, cache reranked results to avoid recomputation
• Monitor performance: Track reranking accuracy, latency, and cost

Retrieval Scoring Formulas Overview

Retrieval strategies use mathematical formulas to score and rank documents. Understanding these formulas helps you choose the right retrieval method, tune parameters, and optimize performance. This section covers the key formulas used in dense, sparse, hybrid, and reranking approaches.

Implementation Overview

This section provides practical Python code examples for implementing retrieval strategies in RAG systems. The examples demonstrate dense retrieval, sparse retrieval (BM25), hybrid retrieval, and reranking with cross-encoders. These implementations form the core of production RAG systems.

from sentence_transformers import SentenceTransformer
from rank_bm25 import BM25Okapi
import numpy as np
from typing import List, Dict, Optional

class HybridRetriever:
    """
    Production-ready hybrid retrieval system.
    
    Combines dense (semantic) and sparse (keyword) retrieval
    for optimal results in RAG systems.
    """
    
    def __init__(self, documents: List[str], alpha: float = 0.7):
        """
        Initialize hybrid retriever.
        
        Args:
            documents: List of document strings to index
            alpha: Weight for sparse retrieval (1-alpha for dense)
                  alpha=0.7 means 70% sparse, 30% dense
        """
        if not documents:
            raise ValueError("Documents list cannot be empty")
        
        self.documents = documents
        self.alpha = alpha
        
        # Initialize dense retriever (embedding-based)
        print("Initializing embedding model...")
        self.embedder = SentenceTransformer('all-MiniLM-L6-v2')
        self.embeddings = self.embedder.encode(documents, show_progress_bar=True)
        print(f"Generated {len(self.embeddings)} embeddings (dimension: {self.embeddings.shape[1]})")
        
        # Initialize sparse retriever (BM25)
        print("Building BM25 index...")
        tokenized_docs = [self._tokenize(doc) for doc in documents]
        self.bm25 = BM25Okapi(tokenized_docs)
        print("BM25 index built")
    
    def _tokenize(self, text: str) -> List[str]:
        """Tokenize text for BM25 (simple word splitting)."""
        # In production, use proper tokenization (NLTK, spaCy)
        return text.lower().split()
    
    def retrieve(self, query: str, top_k: int = 5, normalize: bool = True) -> List[Dict]:
        """
        Retrieve documents using hybrid approach.
        
        Args:
            query: User query string
            top_k: Number of documents to retrieve
            normalize: Whether to normalize scores before combining
            
        Returns:
            List of dicts with 'document', 'dense_score', 'sparse_score', 'hybrid_score'
        """
        # Step 1: Dense retrieval (semantic search)
        query_embedding = self.embedder.encode([query])
        dense_scores = np.dot(self.embeddings, query_embedding.T).flatten()
        
        # Step 2: Sparse retrieval (BM25 keyword search)
        tokenized_query = self._tokenize(query)
        sparse_scores = self.bm25.get_scores(tokenized_query)
        
        # Step 3: Normalize scores to [0, 1] range for fair combination
        if normalize:
            dense_scores = self._normalize(dense_scores)
            sparse_scores = self._normalize(sparse_scores)
        
        # Step 4: Combine scores
        # alpha * sparse + (1-alpha) * dense
        hybrid_scores = self.alpha * sparse_scores + (1 - self.alpha) * dense_scores
        
        # Step 5: Get top-k
        top_indices = np.argsort(hybrid_scores)[-top_k:][::-1]
        
        # Format results
        results = []
        for idx in top_indices:
            results.append({
                'document': self.documents[idx],
                'dense_score': float(dense_scores[idx]),
                'sparse_score': float(sparse_scores[idx]),
                'hybrid_score': float(hybrid_scores[idx]),
                'rank': len(results) + 1
            })
        
        return results
    
    def _normalize(self, scores: np.ndarray) -> np.ndarray:
        """Normalize scores to [0, 1] range using min-max normalization."""
        min_score = scores.min()
        max_score = scores.max()
        if max_score - min_score < 1e-8:  # Avoid division by zero
            return np.ones_like(scores)
        return (scores - min_score) / (max_score - min_score)

# Example usage
documents = [
    "Python machine learning library scikit-learn provides tools for data analysis",
    "TensorFlow is a deep learning framework for neural networks",
    "Machine learning algorithms learn patterns from data automatically",
    "Natural language processing helps computers understand human language",
    "Python programming language is popular for data science"
]

retriever = HybridRetriever(documents, alpha=0.6)  # 60% sparse, 40% dense

# Query
query = "Python machine learning"
results = retriever.retrieve(query, top_k=3)

print(f"\nQuery: '{query}'")
print(f"\nTop-3 Results:")
for result in results:
    print(f"\nRank {result['rank']}:")
    print(f"  Document: {result['document']}")
    print(f"  Dense score: {result['dense_score']:.3f}")
    print(f"  Sparse score: {result['sparse_score']:.3f}")
    print(f"  Hybrid score: {result['hybrid_score']:.3f}")

import math
from collections import Counter
from typing import List, Dict

class BM25:
    """
    BM25 (Best Matching 25) ranking function implementation.
    
    BM25 is a probabilistic ranking function that scores documents
    based on term frequency, inverse document frequency, and document length.
    """
    
    def __init__(self, documents: List[str], k1: float = 1.2, b: float = 0.75):
        """
        Initialize BM25 index.
        
        Args:
            documents: List of document strings
            k1: Term frequency saturation parameter (typically 1.2)
            b: Length normalization parameter (typically 0.75)
        """
        self.k1 = k1
        self.b = b
        self.documents = documents
        
        # Tokenize all documents
        self.tokenized_docs = [self._tokenize(doc) for doc in documents]
        
        # Calculate document frequencies and average document length
        self.doc_freqs = self._calculate_document_frequencies()
        self.avg_doc_length = sum(len(doc) for doc in self.tokenized_docs) / len(documents)
        self.total_docs = len(documents)
    
    def _tokenize(self, text: str) -> List[str]:
        """Simple tokenization (in production, use proper tokenizer)."""
        return text.lower().split()
    
    def _calculate_document_frequencies(self) -> Dict[str, int]:
        """Calculate how many documents contain each term."""
        doc_freqs = Counter()
        for doc_tokens in self.tokenized_docs:
            unique_terms = set(doc_tokens)
            for term in unique_terms:
                doc_freqs[term] += 1
        return doc_freqs
    
    def _idf(self, term: str) -> float:
        """
        Calculate Inverse Document Frequency (IDF) for a term.
        
        Formula: log((N - n(t) + 0.5) / (n(t) + 0.5))
        where N = total docs, n(t) = docs containing term
        """
        if term not in self.doc_freqs:
            return 0.0
        
        n_t = self.doc_freqs[term]  # Number of documents containing term
        # BM25 IDF formula
        idf = math.log((self.total_docs - n_t + 0.5) / (n_t + 0.5))
        return max(0.0, idf)  # Ensure non-negative
    
    def score(self, query: str, doc_index: int) -> float:
        """
        Calculate BM25 score for a query-document pair.
        
        Args:
            query: Query string
            doc_index: Index of document in documents list
            
        Returns:
            BM25 score
        """
        query_terms = self._tokenize(query)
        doc_tokens = self.tokenized_docs[doc_index]
        doc_length = len(doc_tokens)
        
        score = 0.0
        
        for term in query_terms:
            # Term frequency in document
            tf = doc_tokens.count(term)
            
            if tf == 0:
                continue  # Term not in document, skip
            
            # IDF component
            idf = self._idf(term)
            
            # Term frequency saturation component
            numerator = tf * (self.k1 + 1)
            denominator = tf + self.k1 * (1 - self.b + self.b * (doc_length / self.avg_doc_length))
            
            # BM25 score for this term
            term_score = idf * (numerator / denominator)
            score += term_score
        
        return score
    
    def get_scores(self, query: str) -> List[float]:
        """Get BM25 scores for query against all documents."""
        return [self.score(query, i) for i in range(len(self.documents))]
    
    def get_top_k(self, query: str, k: int = 5) -> List[tuple]:
        """
        Get top-k documents for query.
        
        Returns:
            List of (document_index, score) tuples, sorted by score descending
        """
        scores = self.get_scores(query)
        # Get indices sorted by score (descending)
        top_indices = sorted(range(len(scores)), key=lambda i: scores[i], reverse=True)[:k]
        return [(i, scores[i]) for i in top_indices]

# Example usage
documents = [
    "machine learning algorithms learn from data",
    "deep learning uses neural networks",
    "machine learning is a subset of artificial intelligence",
    "neural networks are used in deep learning"
]

bm25 = BM25(documents)

query = "machine learning"
scores = bm25.get_scores(query)
print(f"BM25 scores for query '{query}':")
for i, (doc, score) in enumerate(zip(documents, scores)):
    print(f"  Doc {i+1}: {score:.3f} - {doc}")

top_k = bm25.get_top_k(query, k=2)
print(f"\nTop-2 documents:")
for doc_idx, score in top_k:
    print(f"  Score: {score:.3f}")
    print(f"  Document: {documents[doc_idx]}\n")

from sentence_transformers import CrossEncoder
import numpy as np
from typing import List, Dict

class Reranker:
    """
    Cross-encoder based reranker for improving retrieval accuracy.
    
    Takes top-k candidates from initial retrieval and reranks them
    using a more sophisticated model that sees query-document interaction.
    """
    
    def __init__(self, model_name: str = 'cross-encoder/ms-marco-MiniLM-L-6-v2'):
        """
        Initialize reranker with cross-encoder model.
        
        Args:
            model_name: Pre-trained cross-encoder model name
        """
        print(f"Loading cross-encoder model: {model_name}...")
        self.model = CrossEncoder(model_name)
        print("Model loaded")
    
    def rerank(self, query: str, documents: List[str], top_k: int = 3) -> List[Dict]:
        """
        Rerank documents for a query.
        
        Args:
            query: User query
            documents: List of candidate documents to rerank
            top_k: Number of top documents to return
            
        Returns:
            List of dicts with 'document', 'score', 'rank'
        """
        if not documents:
            return []
        
        # Create query-document pairs
        # Format: [query, document] for each document
        pairs = [[query, doc] for doc in documents]
        
        # Get relevance scores from cross-encoder
        # Higher score = more relevant
        scores = self.model.predict(pairs)
        
        # Sort by score (descending) and get top-k
        ranked_indices = np.argsort(scores)[::-1][:top_k]
        
        # Format results
        results = []
        for rank, idx in enumerate(ranked_indices, 1):
            results.append({
                'document': documents[idx],
                'score': float(scores[idx]),
                'rank': rank
            })
        
        return results
    
    def rerank_batch(self, queries: List[str], documents: List[str], top_k: int = 3) -> List[List[Dict]]:
        """
        Rerank documents for multiple queries (batch processing).
        
        Args:
            queries: List of queries
            documents: List of candidate documents (same for all queries)
            top_k: Number of top documents per query
            
        Returns:
            List of results (one list per query)
        """
        all_results = []
        for query in queries:
            results = self.rerank(query, documents, top_k)
            all_results.append(results)
        return all_results

# Example: Two-stage retrieval pipeline
class TwoStageRetriever:
    """
    Complete two-stage retrieval: fast initial retrieval + accurate reranking.
    
    This is the standard production approach:
    1. Fast initial retrieval (dense/sparse/hybrid) gets top-100 candidates
    2. Reranker refines to top-5 most relevant
    """
    
    def __init__(self, initial_retriever, reranker):
        self.initial_retriever = initial_retriever  # HybridRetriever or similar
        self.reranker = reranker
    
    def retrieve(self, query: str, initial_k: int = 100, final_k: int = 5):
        """
        Two-stage retrieval pipeline.
        
        Args:
            query: User query
            initial_k: Number of candidates from initial retrieval
            final_k: Number of final results after reranking
        """
        # Stage 1: Fast initial retrieval
        print(f"Stage 1: Initial retrieval (top-{initial_k})...")
        initial_results = self.initial_retriever.retrieve(query, top_k=initial_k)
        initial_docs = [r['document'] for r in initial_results]
        
        # Stage 2: Rerank top candidates
        print(f"Stage 2: Reranking top-{initial_k} to get top-{final_k}...")
        reranked = self.reranker.rerank(query, initial_docs, top_k=final_k)
        
        return reranked

# Example usage
from sentence_transformers import SentenceTransformer

# Initialize components
embedder = SentenceTransformer('all-MiniLM-L6-v2')
initial_retriever = HybridRetriever(documents, alpha=0.6)
reranker = Reranker()

# Two-stage retrieval
two_stage = TwoStageRetriever(initial_retriever, reranker)

query = "Python machine learning"
final_results = two_stage.retrieve(query, initial_k=10, final_k=3)

print(f"\nFinal top-3 after reranking:")
for result in final_results:
    print(f"Rank {result['rank']}: {result['document']} (score: {result['score']:.3f})")

Installation Requirements

Install the required packages:

pip install sentence-transformers rank-bm25 numpy

Note: For production, consider using vector databases (Pinecone, Chroma) for initial retrieval instead of in-memory implementations shown here.

Where This Is Used

Retrieval Strategies in Practice

When to use vector search: Semantic similarity is important, synonyms matter, multilingual content

When to use keyword search: Exact term matching needed, domain-specific terminology

When to use hybrid: Best of both worlds, production systems often use this

When to use reranking: Need highest accuracy, can afford extra latency

Performance Trade-offs

Vector search: Fast, good semantic understanding, but may miss exact matches

Keyword search: Very fast, exact matches, but misses synonyms

Hybrid: Balanced, combines strengths, slightly slower

Reranking: Most accurate, but slowest (processes each candidate)