Dense Retrieval & Vector Search

The Big Picture: From Sparse to Dense Retrieval

Sparse retrieval (BM25) excels at exact keyword matching but struggles with semantic gaps. The word "automobile" is very different from "car" to BM25, even though humans recognize they are synonymous. Dense retrieval solves this by encoding queries and passages as continuous vectors in a shared embedding space, where semantic similarity translates to geometric proximity.

Bi-Encoder Architecture

The dominant approach in dense retrieval uses a bi-encoder architecture:

1. Encode query: q_embed = Q_encoder(query)
2. Encode passage: p_embed = P_encoder(passage)
3. Rank by similarity: score = q_embed · p_embed (cosine or dot product)

Both encoders are typically BERT-based or based on modern transformer architectures. This design is efficient because you can pre-compute all passage embeddings, then at query time, encode only the query and perform fast similarity search.

Use Cases

Diagram: BM25 vs Dense Semantic Match

Dense Passage Retrieval (DPR)

Dense Passage Retrieval, introduced by Facebook AI, is a foundational bi-encoder approach for retrieval-augmented question answering. The key innovation is using in-batch negatives and hard negative mining during training to learn discriminative embeddings.

Architecture Overview

Query Encoder (BERT-based):
  query → [CLS] token → dense vector q_embed (768-dim)

Passage Encoder (BERT-based):
  passage → [CLS] token → dense vector p_embed (768-dim)

Similarity Score:
  score(q, p) = q_embed · p_embed  (dot product)

Training: Contrastive Learning

DPR uses contrastive learning to minimize InfoNCE loss. For each query, one passage is relevant (positive), and the rest are irrelevant (negatives).

Hard Negative Mining

A critical ingredient for DPR training is using hard negatives — passages that are not relevant but are semantically similar or ranked highly by BM25. This prevents the model from learning trivial distinctions.

Training process:

1. Batch of N queries, each with 1 positive and ~N-1 negatives (in-batch negatives)
2. Pre-compute hard negatives via BM25 for more challenging training
3. Minimize InfoNCE loss: push positive score up, negative scores down
4. Larger batch sizes help because they provide more diverse negatives

Reference: See bert_guide.html for BERT architecture details.

Training Dense Retrievers

Training an effective dense retriever requires careful data preparation, negative sampling strategies, and hyperparameter tuning. Most successful models use publicly available QA datasets and augment negatives with hard samples.

Standard Datasets

Negative Sampling Strategies

1. In-Batch Negatives

In a batch of N queries, the N-1 other passages serve as negatives. Simple, but works well. Requires batch size ≥ 32 for reasonable diversity.

2. BM25 Hard Negatives

Run BM25 retrieval on the corpus. For each query, take top-K BM25 results that are not the gold passage. These are challenging negatives that fool keyword matching.

3. ANCE: Approximate Nearest Neighbor Negative Contrastive Learning

Dynamically refresh negatives using the current model. Every K training steps, retrieve hard negatives using ANN search on the current model's embeddings. This adapts to the model's progress.

ANCE Algorithm:
1. Initialize encoder
2. For each training step:
   a. If step % K == 0:
      - Encode all passages with current encoder
      - Build ANN index (e.g., HNSW)
      - For each query, retrieve top-n candidates via ANN
      - Use non-relevant candidates as hard negatives
   b. Train on query + positive + hard negatives
3. Repeat until convergence

Knowledge Distillation

Use a stronger re-ranker (cross-encoder) to assign soft labels or scores to passages, then train the bi-encoder to match those scores. This transfers knowledge from expensive cross-encoder to efficient bi-encoder.

Hyperparameter Impact

Sentence Transformers & Modern Embedding Models

Sentence BERT (SBERT) revolutionized dense retrieval by adding a pooling layer to BERT, enabling efficient generation of fixed-size embeddings. Modern alternatives like E5, BGE, and GTE further improve performance across diverse retrieval tasks.

SBERT Architecture

Sentence BERT adds simple mean pooling on top of BERT's [CLS] token, combined with fine-tuning on semantic similarity tasks:

Modern Embedding Models

Matryoshka Representation Learning (MRL)

Recent work allows a single model to generate embeddings of multiple dimensions efficiently. A 768-dim model trained with MRL can output 256-dim, 512-dim, or 768-dim embeddings by truncating the vector. This trades a small accuracy loss for faster search.

Evaluation: BEIR Benchmark

BEIR (Benchmark for Information Retrieval) is a standard suite of 15 diverse retrieval tasks:

Typical evaluation: compute NDCG@10, recall@100, and mean reciprocal rank (MRR) across tasks. Top models achieve NDCG@10 ≈ 0.55-0.60 on BEIR.

Reference: See bert_guide.html for BERT internals and fine-tuning.

Approximate Nearest Neighbor (ANN) Algorithms

With millions or billions of embeddings, exact nearest neighbor search (brute-force L2 or cosine similarity) becomes prohibitively slow: O(N·d) complexity. ANN algorithms sacrifice small amounts of accuracy for massive speedup, enabling real-time search.

The ANN Accuracy-Speed Tradeoff

Four Families of ANN Methods

1. Tree-Based (KD-tree, Ball Tree)

Recursively partition the space into regions. Query: traverse tree to find relevant regions.

• Pros: Simple, interpretable, works for low-dimensional data (d ≤ 20)
• Cons: "Curse of dimensionality" — performance degrades in high dimensions
• Example: scikit-learn's KDTree for small datasets

2. Graph-Based (HNSW, NSG)

Build a proximity graph where edges connect similar vectors. Query: navigate graph to nearest neighbor.

• Pros: Excellent recall/QPS tradeoff, scales to billions, no training
• Cons: Index building is sequential, O(N log N) or O(N) time
• Example: HNSW (Hierarchical Navigable Small World) — dominant in practice

3. Quantization-Based (IVF-PQ, Product Quantization)

Reduce dimensionality and precision. IVF: partition into clusters. PQ: compress sub-vectors to bytes.

• Pros: Extreme memory savings (32-100× smaller), very fast on GPU
• Cons: Training required, recall ~95% with aggressive compression
• Example: FAISS library (Facebook), industry standard

4. Hashing-Based (LSH, Learned Hashing)

Hash vectors into buckets. Query: hash and search nearby buckets.

• Pros: Fast hashing, very memory-efficient
• Cons: Recall is harder to tune, collisions affect quality
• Example: Locality Sensitive Hashing (LSH), used mainly in research

HNSW: Hierarchical Navigable Small World

HNSW is a graph-based ANN algorithm that combines small-world networks with hierarchical organization. It achieves excellent recall and query speed while being practical to implement and use in production.

Core Idea: Small-World Networks

A small-world network is a graph where most nodes are not neighbors, but any node can be reached from any other in a small number of steps. Think of social networks: you are connected to direct friends, but can reach most people through "degrees of separation."

Hierarchical Organization

HNSW extends this by creating multiple layers:

• Top Layer: Few nodes, sparse connections, large jumps in space
• Middle Layers: More nodes, medium density
• Bottom Layer (L0): All nodes, dense connections, fine-grained search

Construction Algorithm

HNSW Construction:
1. For each vector v to insert:
   a. Assign level l randomly (exponentially decreasing probability)
   b. If l > max_level: update entry point
   c. For each layer from max_level down to 0:
      - Find nearest neighbors in that layer
      - Connect v to M nearest neighbors (M = degree parameter)
      - Update neighbors to point back to v
   d. Prune: keep only M nearest per layer (M = edge parameter)

Key Parameters

Query Algorithm

HNSW Search (query q, ef):
1. Start from entry point (top layer)
2. For each layer from max_level down to 0:
   - Find nearest neighbor to q using greedy search
   - If not at bottom: use found neighbor as entry point for next layer
   - If at bottom: expand search beam to ef neighbors
3. Return top-K neighbors

Why HNSW Wins

Typical HNSW Settings

FAISS: IVF-PQ (Inverted File + Product Quantization)

FAISS (Facebook AI Similarity Search) is an industry-standard library for similarity search. IVF-PQ combines inverted file indexing with product quantization to achieve extreme memory efficiency and GPU acceleration while maintaining good recall.

Part 1: Inverted File (IVF)

IVF partitions the vector space using k-means clustering:

1. Run k-means on embeddings → K cluster centers (Voronoi cells)
2. Assign each vector to its nearest cluster center
3. Store inverted lists: for each cluster, list of vector IDs in that cluster
4. Query: compute query distance to K cluster centers, search only nearest nprobe clusters

Part 2: Product Quantization (PQ)

Instead of storing full 768-dimensional vectors (768 × 4 bytes = 3072 bytes per vector), PQ compresses them dramatically:

Product Quantization:
1. Split each 768-dim vector into M sub-vectors (M=96, each 8-dim)
2. For each sub-vector, learn codebook of 256 codewords (8-bit)
3. Replace each sub-vector with its nearest codeword index
4. Store only M bytes per vector (instead of 3072 bytes)
   Compression: 3072 → 96 bytes = 32× reduction!

Asymmetric Distance Computation (ADC)

At query time, compute distances without decompressing vectors:

• Query: 768-dim (full precision)
• Corpus: PQ-compressed to bytes
• Distance: compute distance from query sub-vectors to PQ codebook, then sum
• Result: approximate distance, but very fast (no decompression needed)

FAISS Index Types

Modern Vector Search Solutions

Beyond research implementations, production vector search requires features like metadata filtering, incremental updates, and easy deployment. Modern solutions provide these while leveraging state-of-the-art ANN algorithms.

ScaNN (Google)

ScaNN (Scalable Nearest Neighbors) introduces anisotropic vector quantization, achieving better recall than standard PQ at the same compression level.

• Key Innovation: Quantization is optimized for the specific query distribution, not uniform
• Recall: ~97% with 4× compression (vs ~90% for standard PQ)
• Use: Google uses ScaNN for YouTube and Search recommendations

NSG (Navigating Spreading-out Graph)

A graph-based approach similar to HNSW but with additional optimizations:

• Construction: Greedily builds graph to minimize "neighborhood expansion"
• Recall: Comparable to HNSW, ~98%+
• Industry: Used in Alibaba, Tencent production systems

DiskANN (Microsoft)

Enables billion-scale search on a single machine with SSD storage, not requiring GPU or distributed setup.

• Storage: Vectors on disk, index in RAM (100× smaller than vectors)
• Scalability: Supports 100M+ vectors on single machine
• Speed: Millisecond latency with SSD I/O optimization

Managed Vector Databases

When to Use Each

Practical Considerations

Moving from research to production requires addressing indexing overhead, incremental updates, filtering, and monitoring. This section covers real-world challenges and solutions.

Index Building and Memory

HNSW Construction Time: O(N log N) with typical parameters. For 100M embeddings (768-dim, 768×4 = 3KB each = 230GB raw), building takes hours on a single machine.

Incremental Indexing

For real-time systems (e-commerce, news, social media), new items arrive continuously.

• HNSW: Supports incremental insert() — add new vectors one-by-one. Index remains online.
• IVF-PQ: Requires retraining k-means periodically (offline). Can add vectors to existing clusters until retraining.
• Buffer approach: New items go into a fast (small) index, periodically merge with main index

Filtered Search (Metadata Filtering)

Often need to filter by metadata: brand='Nike' AND price<$200 before or during ANN search.

Pre-Filter

Filter metadata first, then run ANN on the remaining vectors. Fast filtering but may discard relevant vectors.

Post-Filter

Retrieve top-K from ANN, then apply metadata filter. Simpler but may return few results if filter is strict.

Native Filtering

Integrate filtering into ANN search (e.g., HNSW with metadata tags). Qdrant, Weaviate, Pinecone support this. Best quality.

Multi-Vector Retrieval (Late Interaction)

ColBERT (Context-Aware BERT Representations for Learning-To-Rank) represents queries and documents as sets of vectors (one per token), then compute similarities at token level. More expressive than single-vector dense retrieval but more expensive.

Quantization and Accuracy Trade-offs

Embedding Model Updates

When you retrain your embedding model, all stored embeddings become stale. Three approaches:

1. Batch Re-encode: Re-encode all passages with new model, rebuild index (offline, several hours)
2. A/B Testing: Run new model alongside old. Gradual migration.
3. Adapter Module: Keep embeddings fixed, train lightweight adapter to map old embeddings to new space

Monitoring Dense Retrieval

• Recall Drift: Monitor recall@K on a held-out test set. Alert if drops below threshold.
• Latency Percentiles: Track p50, p95, p99 query latencies. Watch for ANN timeout/degradation.
• Index Freshness: How old is the oldest vector in the index? Freshness SLA for new items.
• Query Distribution: Monitor query embedding distribution. Large shifts may indicate query-doc mismatch.
• Embedding Drift: Sample embeddings over time. If they shift, may need model retraining.

Dense vs Sparse vs Hybrid Retrieval

Each retrieval approach has strengths and weaknesses. Understanding the tradeoffs helps choose the right method for your task.

Comprehensive Comparison

When to Use Each

BM25 Wins On:

• Entity search: "Barack Obama", "COVID-19 vaccine"
• Product catalogs with product IDs, SKUs
• Legal/financial documents with specific terms and regulations
• Systems with no training data and strict interpretability requirements

Dense Retrieval Wins On:

• Open-domain QA: "Who won the Nobel Prize in 2023?"
• Semantic search: "flights to Paris in the spring"
• Paraphrase matching: "autonomous vehicles" ≈ "self-driving cars"
• Typo tolerance: "rekursion" → "recursion"
• Cross-lingual search with multilingual embeddings

Hybrid Retrieval Wins On:

• E-commerce: combine semantic search with brand/category filters and entity matching
• Enterprise search: blend semantic understanding with policy keyword compliance
• Medical search: find semantically similar papers AND articles with specific drug names

When to Upgrade from BM25 to Dense

Consider dense retrieval if:

• BM25 baseline has low recall on a held-out test set (<50% recall@100)
• You have semantic failures: synonyms, paraphrases not retrieved
• You have training data (query-passage pairs) or can leverage pre-trained models like E5
• Index size is not a constraint (embedding storage is manageable)
• You can afford ANN index building time (hours, not seconds)

References: See bm25_inverted_index_guide.html and hybrid_search_reranking_guide.html for detailed comparisons and hybrid approaches.

Python Implementation: Complete Dense Retrieval System

Build a practical dense retrieval system from scratch using only numpy and pandas. This demonstrates key concepts: embedding computation, similarity search, and evaluation.

Full Implementation

import numpy as np
import pandas as pd
from typing import List, Tuple
import math

class SimpleEmbedder:
    """TF-IDF proxy for embeddings (no dependencies)."""

    def __init__(self, vocab_size=100, dim=64):
        self.vocab_size = vocab_size
        self.dim = dim
        self.word_to_id = {}
        self.id_matrix = None
        self.idf = None

    def fit(self, texts: List[str]):
        """Learn vocabulary and IDF weights."""
        words = set()
        doc_freq = {}

        for text in texts:
            tokens = text.lower().split()
            words.update(tokens)
            for token in set(tokens):
                doc_freq[token] = doc_freq.get(token, 0) + 1

        # Build vocabulary (top vocab_size words)
        sorted_words = sorted(words,
            key=lambda w: doc_freq.get(w, 0), reverse=True)
        self.word_to_id = {w: i for i, w in
            enumerate(sorted_words[:self.vocab_size])}

        # Compute IDF
        N = len(texts)
        self.idf = {}
        for word in self.word_to_id:
            count = doc_freq.get(word, 0)
            self.idf[word] = math.log(N / max(1, count))

        # Initialize random projection matrix
        np.random.seed(42)
        self.id_matrix = np.random.randn(self.vocab_size,
            self.dim) / math.sqrt(self.dim)

    def embed(self, text: str) -> np.ndarray:
        """Convert text to dense vector."""
        tokens = text.lower().split()
        tfidf_vec = np.zeros(self.vocab_size)

        # Compute TF-IDF
        for token in tokens:
            if token in self.word_to_id:
                wid = self.word_to_id[token]
                idf = self.idf.get(token, 0)
                tfidf_vec[wid] += idf

        # L2 normalize
        norm = np.linalg.norm(tfidf_vec)
        if norm > 0:
            tfidf_vec /= norm

        # Project to embedding space
        embedding = tfidf_vec @ self.id_matrix
        embedding /= (np.linalg.norm(embedding) + 1e-8)
        return embedding


class DenseRetriever:
    """Bi-encoder style dense retriever."""

    def __init__(self, embedder: SimpleEmbedder):
        self.embedder = embedder
        self.passages = []
        self.embeddings = None

    def build_index(self, passages: List[str]):
        """Build index from passages."""
        self.passages = passages
        self.embeddings = np.array([
            self.embedder.embed(p) for p in passages
        ])

    def retrieve(self, query: str, top_k: int = 5
        ) -> List[Tuple[str, float]]:
        """Retrieve top-K passages for query."""
        q_embedding = self.embedder.embed(query)

        # Compute cosine similarity
        scores = self.embeddings @ q_embedding

        # Get top-K indices
        top_indices = np.argsort(scores)[::-1][:top_k]

        results = []
        for idx in top_indices:
            passage = self.passages[idx]
            score = float(scores[idx])
            results.append((passage, score))

        return results


class ANNIndex:
    """Brute-force ANN (top-K with batch processing)."""

    def __init__(self, embeddings: np.ndarray):
        self.embeddings = embeddings

    def search(self, query_embedding: np.ndarray, k: int = 10
        ) -> List[int]:
        """Return top-K indices."""
        scores = self.embeddings @ query_embedding
        return np.argsort(scores)[::-1][:k].tolist()


class DenseVsBM25Eval:
    """Evaluate dense retrieval vs BM25."""

    @staticmethod
    def bm25_score(query: str, passage: str) -> float:
        """Simple BM25-like scoring."""
        q_tokens = set(query.lower().split())
        p_tokens = passage.lower().split()
        matches = sum(1 for t in p_tokens if t in q_tokens)
        return matches / (len(p_tokens) + 1)

    @staticmethod
    def evaluate(retriever: DenseRetriever, passages: List[str],
        query: str, relevant_passages: List[str]):
        """Compare dense and BM25 retrieval."""

        # Dense retrieval
        dense_results = retriever.retrieve(query, top_k=5)
        dense_matches = sum(1 for p, _ in dense_results
            if p in relevant_passages)

        # BM25 retrieval
        bm25_scores = [(p, DenseVsBM25Eval.bm25_score(query, p))
            for p in passages]
        bm25_results = sorted(bm25_scores,
            key=lambda x: x[1], reverse=True)[:5]
        bm25_matches = sum(1 for p, _ in bm25_results
            if p in relevant_passages)

        return {
            'dense_precision@5': dense_matches / 5,
            'bm25_precision@5': bm25_matches / 5,
            'dense_results': dense_results,
            'bm25_results': bm25_results
        }


# Example usage
if __name__ == '__main__':
    # Sample corpus
    passages = [
        "Machine learning is a subset of artificial intelligence",
        "Deep learning uses neural networks with many layers",
        "Python is a popular programming language for data science",
        "Transfer learning improves model performance with limited data",
        "Convolutional neural networks excel at image recognition",
        "NLP focuses on processing human language",
        "Transformers use attention mechanisms for sequence modeling",
        "GPU acceleration speeds up neural network training",
        "Regularization prevents overfitting in machine learning",
        "Gradient descent optimizes neural network weights",
        "Embeddings represent words as dense vectors",
        "BERT is a pre-trained language model from Google",
        "Information retrieval finds relevant documents quickly",
        "Semantic search understands meaning beyond keywords",
        "Vector databases store and search embeddings efficiently",
        "Attention mechanisms allow models to focus on relevant parts",
        "Fine-tuning adapts pre-trained models to new tasks",
        "Batch normalization stabilizes deep network training",
        "Dropout regularization randomly deactivates neurons",
        "Cross-entropy loss measures classification error"
    ]

    # Build retriever
    embedder = SimpleEmbedder(vocab_size=50, dim=32)
    embedder.fit(passages)

    retriever = DenseRetriever(embedder)
    retriever.build_index(passages)

    # Test queries
    test_cases = [
        ("vector embeddings for search",
         ["Embeddings represent words as dense vectors",
          "Vector databases store and search embeddings efficiently"]),
        ("deep learning models",
         ["Deep learning uses neural networks with many layers",
          "Convolutional neural networks excel at image recognition"]),
        ("language processing techniques",
         ["NLP focuses on processing human language",
          "Transformers use attention mechanisms for sequence modeling"])
    ]

    print("=" * 70)
    print("DENSE RETRIEVAL vs BM25 EVALUATION")
    print("=" * 70)

    evaluator = DenseVsBM25Eval()

    for query, relevant in test_cases:
        print(f"\nQuery: '{query}'")
        print(f"Relevant passages: {len(relevant)}")

        results = evaluator.evaluate(retriever, passages,
            query, relevant)

        print(f"\nDense Precision@5: {results['dense_precision@5']:.2f}")
        print(f"BM25 Precision@5: {results['bm25_precision@5']:.2f}")

        print("\nTop-5 Dense Results:")
        for i, (p, score) in enumerate(results['dense_results'], 1):
            marker = "✓" if p in relevant else " "
            print(f"  {i}. [{marker}] {p[:60]}... (score: {score:.3f})")

        print("\nTop-5 BM25 Results:")
        for i, (p, score) in enumerate(results['bm25_results'], 1):
            marker = "✓" if p in relevant else " "
            print(f"  {i}. [{marker}] {p[:60]}... (score: {score:.3f})")

        print("-" * 70)

Key Output Example

Query: "vector embeddings for search"
Relevant passages: 2

Dense Precision@5: 0.40
BM25 Precision@5: 0.20

Top-5 Dense Results:
  1. [✓] Embeddings represent words as dense vectors... (score: 0.654)
  2. [✓] Vector databases store and search embeddings effi... (score: 0.612)
  3. [ ] Semantic search understands meaning beyond keywor... (score: 0.589)
  4. [ ] Information retrieval finds relevant documents qu... (score: 0.556)
  5. [ ] Transformers use attention mechanisms for sequence... (score: 0.478)

Top-5 BM25 Results:
  1. [✓] Vector databases store and search embeddings effi... (score: 0.400)
  2. [ ] Machine learning is a subset of artificial intell... (score: 0.200)
  3. [ ] Deep learning uses neural networks with many layers (score: 0.167)
  4. [ ] NLP focuses on processing human language (score: 0.167)
  5. [ ] Transformers use attention mechanisms for sequence... (score: 0.167)

Extending to Production

To scale to millions of embeddings:

• Replace embedder: Use SBERT, E5, or OpenAI embeddings instead of TF-IDF
• Add ANN index: Use FAISS or HNSW instead of brute-force
• Metadata filtering: Add filtering by tags, categories, dates
• Re-ranker: Use a cross-encoder to rerank top-100 for final ranking
• Monitoring: Track recall@K, latency, index freshness

Reference: See rag_patterns_guide.html for integrating dense retrieval into RAG pipelines.