Lecture 10 — RAG: Dense Retrieval & Semantic Search¶

Estimated read time: 30–40 min · Difficulty: Core + Technical Depth

What this lecture is about¶

This lecture dives deep into the technical mechanics of modern RAG retrieval. Where Lecture 9 introduced the why and what of RAG, Lecture 10 focuses on the how. You will learn how embeddings actually work at a mechanical level, why cosine similarity and dot product give the same ranking for normalized vectors, how to process messy real-world documents (PDFs, tables, multi-column layouts), how to choose chunking parameters, why hybrid retrieval (BM25 + dense) beats either method alone, why reranking is non-negotiable in production systems, and how vector databases index billions of embeddings using approximate nearest neighbor (ANN) algorithms.

This is the lecture that separates "I used a vector database once" from "I can architect a production RAG system." You will also learn about advanced embedding techniques—instruction-tuned embedders, late-interaction models like ColBERT, Matryoshka embeddings, and GraphRAG. By the end, you should be able to make informed decisions about embedding models, chunking strategies, vector databases, and retrieval pipelines. Expect exam questions that test your understanding of hybrid retrieval, ANN indexes, and reranking.

Prerequisites¶

You should have read Lecture 9 or understand the basics of RAG (retrieve → augment → generate).
Basic understanding of vectors and dot products (high school math level).
Familiarity with embeddings (vectors representing text) is helpful.

Concept 1: Embeddings Deep Dive¶

The problem it solves¶

Embeddings are the foundation of dense retrieval. But what makes a good embedding? Why are they fixed-dimensional? Why do we normalize them?

The intuition¶

An embedding is a mapping from text (variable length) to a fixed-dimensional dense vector (e.g., 768 or 1536 dimensions). The key property: texts with similar meanings should have similar embeddings (measured by cosine similarity or dot product).

Example: - "The cat sat on the mat" → [0.2, 0.7, 0.1, ...] - "A feline rested on the rug" → [0.19, 0.71, 0.09, ...] (close) - "The stock market crashed" → [0.8, 0.1, 0.05, ...] (far)

Why fixed dimension? - Variable-length embeddings would require dynamic indexing, which is prohibitively expensive. - Fixed dimension allows us to use fast linear algebra (matrix multiplication, SIMD operations).

Why L2-normalize? - Most embedding models are trained to produce unit-length vectors (L2 norm = 1). - For unit vectors, cosine similarity = dot product, and dot product is the cheapest primitive (single SIMD instruction). - Normalization also prevents embeddings with large magnitudes from dominating the similarity computation.

The formula (with meaning)¶

L2 normalization:

v_normalized = v / ||v||

Where ||v|| = sqrt(v1² + v2² + ... + vn²) is the Euclidean length.

Cosine similarity:

cos(q, d) = (q · d) / (||q|| · ||d||)

If ||q|| = ||d|| = 1 (both normalized), then:

cos(q, d) = q · d (dot product)

Why this matters: Computing dot products is fast. Modern CPUs and GPUs have hardware-accelerated dot product instructions. Cosine similarity requires computing norms, which is slower.

Worked example¶

Suppose: - Query embedding: q = [3, 4] (unnormalized) - Doc embedding: d = [6, 8] (unnormalized)

Step 1: Normalize: - ||q|| = sqrt(3² + 4²) = 5 - q_norm = [⅗, ⅘] = [0.6, 0.8] - ||d|| = sqrt(6² + 8²) = 10 - d_norm = [6/10, 8/10] = [0.6, 0.8]

Step 2: Compute similarity: - Cosine similarity = (3·6 + 4·8) / (5 · 10) = 50 / 50 = 1.0 - Dot product of normalized vectors = 0.6·0.6 + 0.8·0.8 = 0.36 + 0.64 = 1.0

Result: Both methods give the same answer for normalized vectors.

Common misunderstandings¶

"Bigger embeddings (more dimensions) are always better." Not necessarily. A poorly trained 1536-dim embedding is worse than a well-trained 768-dim embedding. What matters is the training data and objective.
"Embeddings are unique." No. Many texts can map to similar embeddings (this is desirable for retrieval, but a problem for deduplication).
"I can compare embeddings from different models." No. Embeddings from different models live in different vector spaces and are not comparable.

Exam angle¶

Expect questions that test: - What an embedding is: Fixed-dimensional dense vector representing text. - Why normalize: To make cosine similarity = dot product (cheaper computation). - Why fixed dimension: Enables fast indexing and linear algebra. - Cosine vs dot product: For normalized vectors, they give the same ranking.

Concept 2: Document Processing — The Unsolved Problem¶

The problem it solves¶

Real-world documents are messy. PDFs have multi-column layouts, tables, headers, footers, and embedded images. OCR'd scans have errors. Web pages have ads and navigation. How do you extract clean, structured text for chunking and embedding?

The intuition¶

Document processing is the single largest source of RAG quality regression in production systems. You can have the best embedding model and the best retrieval algorithm, but if your PDF parser misses half the text or garbles tables, retrieval will fail.

Common problems: - PDFs with multi-column layouts (parser reads left-to-right across both columns, mixing unrelated text). - Tables (parsed as unstructured text, losing semantic structure). - Headers and footers (repeated on every page, polluting embeddings). - OCR errors (scanned documents with text recognition mistakes). - Embedded images, charts, and formulas (lost during text extraction).

Tools: - PyMuPDF (fitz): Fast, low-level PDF parser. Good for simple PDFs, poor for complex layouts. - unstructured.io: Open-source library that handles PDFs, Word docs, HTML, emails. Better layout detection. - Docling (IBM): Research-grade document parser with layout analysis and table extraction. - Document AI (Google Cloud): Managed API for OCR and layout analysis. Expensive but accurate.

Worked example¶

Problem: A PDF has a two-column layout:

[Column 1]               [Column 2]
Cats are mammals.        Dogs are also mammals.
They sleep all day.      They love long walks.

Naive parser (PyMuPDF):

Cats are mammals. Dogs are also mammals. They sleep all day. They love long walks.

Result: Sentences about cats and dogs are interleaved, breaking semantic coherence.

Better parser (unstructured):

[Chunk 1] Cats are mammals. They sleep all day.
[Chunk 2] Dogs are also mammals. They love long walks.

Result: Layout analysis detects columns and preserves semantic grouping.

Common misunderstandings¶

"PDF parsing is a solved problem." No. PDFs are a print-oriented format, not a data format. Layout recovery is hard.
"I can just use pdfplumber or PyPDF2." These are fine for simple PDFs, but fail on complex layouts and tables.
"Text extraction is the same as chunking." No. Text extraction gets you raw text. Chunking splits that text into semantically coherent pieces.

Exam angle¶

Expect questions that test: - Why document processing matters: Garbage in, garbage out. Bad parsing = bad retrieval. - Common problems: Multi-column layouts, tables, OCR errors. - Tools: PyMuPDF (fast, simple), unstructured (layout-aware), Document AI (managed, expensive).

Concept 3: Chunking Defaults Revisited¶

The problem it solves¶

Lecture 9 introduced chunking strategies. This section gives you production defaults and tuning guidance.

Production defaults¶

Parameter	Recommended value	Rationale
Chunk size	300–800 tokens	Large enough to capture context, small enough for precise retrieval
Overlap	10–20%	Prevents splitting mid-sentence, but avoids excessive redundancy
Splitting strategy	Recursive (paragraph → sentence → token)	Preserves semantic boundaries
Metadata	Document ID, section title, page number	Enables post-retrieval filtering and citation

When to deviate: - Small chunks (100–300 tokens): High-precision retrieval (e.g., legal citations, product IDs). Trade-off: higher fragmentation. - Large chunks (800–1500 tokens): Narrative text (e.g., news articles, blog posts). Trade-off: blurrier embeddings. - No overlap: When documents are already highly structured (e.g., FAQ Q&A pairs).

The intuition: why overlap?¶

Suppose you have a paragraph split exactly at 500 tokens. The answer to a query might span tokens 480–520 (straddling the boundary). With 10% overlap (50 tokens), both chunks will include tokens 450–500 and 500–550, ensuring the answer is fully contained in at least one chunk.

Worked example¶

Document: 1000-token passage. Chunk size: 400 tokens. Overlap: 10% (40 tokens).

Chunks: - Chunk 1: tokens 0–400 - Chunk 2: tokens 360–760 (overlaps with chunk 1 at tokens 360–400) - Chunk 3: tokens 720–1000 (overlaps with chunk 2 at tokens 720–760)

If the answer is at tokens 380–420, it appears in both chunk 1 (partial) and chunk 2 (complete).

Common misunderstandings¶

"Bigger chunks = better context = better answers." Not always. Larger chunks dilute the embedding signal. The embedding represents the AVERAGE meaning of all sentences in the chunk, which becomes blurrier as the chunk grows.
"I should always use 512 tokens because that's the BERT max length." BERT's 512-token limit is for the INPUT, not the chunk. You can chunk at any size. Modern embedding models support longer inputs (e.g., 8192 tokens for text-embedding-3-small).
"Overlap is free." No. Overlap increases index size and indexing time. Use the minimum overlap that prevents boundary splitting.

Exam angle¶

Expect questions that test: - Recommended defaults: 300–800 tokens, 10–20% overlap, recursive splitting. - Why overlap: Prevents splitting mid-sentence or mid-answer. - Trade-offs: Small chunks (high precision, fragmentation) vs large chunks (context, blurry embeddings).

Concept 4: Hybrid Retrieval — BM25 + Dense¶

The problem it solves¶

BM25 (lexical) is great for exact keyword matches. Dense retrieval (embeddings) is great for semantic similarity. Why choose one when you can use both?

The intuition¶

BM25 strengths: - Exact keyword matches (e.g., product names, IDs, rare terms). - Fast and cheap.

BM25 weaknesses: - Misses synonyms and paraphrases ("cat" vs "feline").

Dense retrieval strengths: - Captures semantic similarity. - Handles paraphrases and related concepts.

Dense retrieval weaknesses: - Can miss exact keyword matches (embeddings are approximate). - More expensive.

Hybrid retrieval: Combine both. Retrieve top-k with BM25, retrieve top-k with dense, merge the two ranked lists.

The formula (with meaning): Reciprocal Rank Fusion (RRF)¶

RRF is the standard way to merge two ranked lists:

score(doc) = 1 / (k + rank_BM25(doc)) + 1 / (k + rank_dense(doc))

Where: - k is a constant (typically 60). - rank_BM25(doc) is the rank of the document in the BM25 results (1 = top result). - rank_dense(doc) is the rank in the dense results.

Why RRF works: - Documents that rank high in BOTH systems get high scores. - Documents that rank high in ONE system get medium scores. - Documents that rank low in BOTH get low scores. - RRF is robust to score scale differences (BM25 scores are not comparable to cosine similarities).

Worked example¶

Suppose: - BM25 results: [doc1 (rank 1), doc2 (rank 2), doc3 (rank 3)] - Dense results: [doc2 (rank 1), doc4 (rank 2), doc1 (rank 3)]

RRF scores (k=60): - doc1: 1/(60+1) + 1/(60+3) = 0.0164 + 0.0159 = 0.0323 - doc2: 1/(60+2) + 1/(60+1) = 0.0161 + 0.0164 = 0.0325 - doc3: 1/(60+3) + 0 = 0.0159 - doc4: 0 + 1/(60+2) = 0.0161

Merged ranking: doc2 > doc1 > doc4 > doc3.

Interpretation: doc2 ranks high in BOTH systems, so it tops the merged list.

Common misunderstandings¶

"Hybrid retrieval is always better." Not always. On purely semantic queries (e.g., "What causes rain?"), dense-only may be sufficient. On keyword-heavy queries (e.g., "Find order #12345"), BM25-only may be sufficient. But for general-purpose systems, hybrid is the safe default.
"I can just average BM25 and dense scores." No. BM25 scores and cosine similarities are on different scales. RRF (or other rank-based fusion) is more robust.

Exam angle¶

Expect questions that test: - Why hybrid retrieval: Combines lexical (exact match) and semantic (meaning) retrieval. - How to merge: Reciprocal Rank Fusion (RRF). - When BM25 wins: Exact keyword matches, rare terms. - When dense wins: Semantic similarity, paraphrases.

Concept 5: Reranking with Cross-Encoders¶

The problem it solves¶

Bi-encoders retrieve top-100 quickly but coarsely. How do we improve the precision of the top-k?

The intuition¶

Recall from Lecture 9: - Bi-encoder: Encode query and doc INDEPENDENTLY. Fast, scalable, but coarse. - Cross-encoder: Encode [query; doc] JOINTLY. Slow, but accurate.

Standard production pattern: 1. Bi-encoder retrieves top-100. 2. Cross-encoder reranks top-100 to top-5.

Why this works: - Bi-encoder narrows from millions to 100 (fast). - Cross-encoder refines from 100 to 5 (accurate). - Total cost: 1 bi-encoder forward pass + 100 cross-encoder forward passes. Tractable.

Popular rerankers: - Cohere Rerank API: Managed service. Easy to use, expensive at scale. - bge-reranker-large: Open-source cross-encoder (FlagEmbedding). Free, self-hosted. - ms-marco-MiniLM-L-12-v2: Smaller, faster cross-encoder. Lower quality.

Worked example¶

Query: "How do I reset my password?"

Bi-encoder retrieves top-100: - doc1: "To reset your password, click 'Forgot Password'..." - doc2: "Password security best practices..." - doc3: "Account recovery options..." - ... - doc100: "User profile settings..."

Cross-encoder reranks: - Score([query; doc1]) = 0.92 - Score([query; doc2]) = 0.45 - Score([query; doc3]) = 0.68 - ... - Score([query; doc100]) = 0.12

Top-5 after reranking: [doc1, doc3, doc7, doc23, doc9]

Result: The top-5 is much more relevant than the top-5 from the bi-encoder alone.

Common misunderstandings¶

"Reranking is optional." It is optional for prototypes, but universal in production. Reranking typically improves top-5 precision by 10–30%.
"I can use a cross-encoder for initial retrieval." No. Cross-encoders require N forward passes for N documents. For millions of documents, this is too slow.
"Reranking fixes bad retrieval." No. If the bi-encoder misses the relevant documents (they are not in the top-100), reranking cannot recover them. Reranking REFINES, it does not REPLACE retrieval.

Exam angle¶

Expect questions that test: - What reranking is: Cross-encoder reranks bi-encoder results (top-100 → top-5). - Why it helps: Cross-encoder captures fine-grained query-document interactions. - Standard pattern: Bi-encoder (scalable, coarse) → cross-encoder (expensive, precise). - Popular tools: Cohere Rerank, bge-reranker-large.

Concept 6: Vector Databases and ANN Indexes¶

The problem it solves¶

You have 10 million document chunks. Each is a 768-dimensional vector. The user sends a query. How do you find the top-k most similar vectors in milliseconds?

The intuition¶

Naive approach (brute force): - Compute cosine similarity between the query and all 10 million vectors. - Sort and return the top-k. - Cost: 10M dot products. Too slow.

Approximate Nearest Neighbor (ANN) approach: - Build an index (data structure) that organizes vectors for fast search. - At query time, search only a subset of vectors (not all 10M). - Trade-off: Slight loss of accuracy (you might miss the true top-k), huge gain in speed.

Popular ANN algorithms: 1. IVF (Inverted File): Cluster vectors into buckets. At query time, search only the closest buckets. 2. HNSW (Hierarchical Navigable Small World): Build a graph where each node is a vector. Navigate the graph to find neighbors. 3. Flat (brute force): No index. Exact search. Only for small datasets (<100K vectors).

ANN algorithms explained¶

IVF (Inverted File): - Indexing: Cluster the 10M vectors into e.g., 1000 buckets using k-means. - Query: Find the closest bucket(s) to the query vector. Search only those buckets. - Example: If the query is closest to bucket 42, search only the ~10K vectors in bucket 42. - Trade-off: You might miss vectors that belong to a nearby bucket. Tune by searching multiple buckets (nprobe parameter).

HNSW (Hierarchical Navigable Small World): - Indexing: Build a multi-layer graph. Layer 0 has all vectors. Layer 1 has a subset (e.g., 10%). Layer 2 has a subset of layer 1, etc. - Query: Start at the top layer, navigate to the closest node. Drop to the next layer, navigate further. Repeat until layer 0. - Trade-off: High accuracy, high memory cost (stores the graph structure).

Flat: - Indexing: None. - Query: Brute-force search all vectors. - Trade-off: Exact (no approximation), but too slow for large datasets.

Worked example: IVF¶

Indexing: - 10M vectors, cluster into 1000 buckets. - Each bucket has ~10K vectors.

Query: - Compute query's distance to the 1000 bucket centroids. - Closest centroid is bucket 42. - Search all ~10K vectors in bucket 42. - Return top-10.

Cost: 1000 + 10K = ~11K dot products (vs 10M for brute force). 1000x speedup.

Accuracy: If the true top-10 includes a vector from bucket 43, we might miss it. Tune by searching multiple buckets (e.g., nprobe=5 → search 5 closest buckets).

Common misunderstandings¶

"ANN is always approximate." Not quite. HNSW with high ef_search can achieve near-exact results (99%+ recall), but at the cost of speed.
"Flat is always too slow." Not true. For <100K vectors, flat is often fast enough and avoids the complexity of ANN indexes.
"I should always use HNSW because it's the best." HNSW is great for read-heavy workloads, but expensive to build and update. For write-heavy workloads (frequent insertions), IVF may be better.

Exam angle¶

Expect questions that test: - What ANN is: Approximate nearest neighbor search. Trade accuracy for speed. - Why ANN is needed: Brute-force search is too slow for millions of vectors. - IVF: Cluster into buckets, search closest buckets. - HNSW: Graph-based navigation. - Flat: Brute force, exact, only for small datasets.

Concept 7: Vector Database Comparison¶

The problem it solves¶

Which vector database should you use? ChromaDB, FAISS, Qdrant, Pinecone, Milvus, pgvector?

The intuition¶

A vector database is more than just an ANN index. It typically includes: - ANN index (IVF, HNSW, etc.) - Metadata storage (document ID, title, date, access control) - Metadata filtering (e.g., "retrieve from documents where date > 2023") - Persistence (save index to disk, reload later) - API (insert, search, delete) - Hybrid search (combine BM25 + dense)

Database comparison¶

Database	Strengths	Weaknesses	Use case
ChromaDB	Developer-friendly API, batteries included, local-first	Limited scale (~10M vectors), slower than FAISS	Prototypes, small/medium projects
FAISS	Raw speed, battle-tested (Meta), low-level control	No metadata storage, no persistence out-of-the-box	High-performance research, custom pipelines
Qdrant	Metadata filtering, persistence, managed cloud	Smaller community than Pinecone	Production systems, self-hosted or managed
Milvus	Distributed, billion-scale, GPU support	Complex setup, heavier operational burden	Enterprise, billion-scale deployments
Pinecone	Managed service, zero ops, easy to start	Expensive at scale, vendor lock-in	Startups, fast prototyping
pgvector	Postgres extension, integrates with existing DB	Limited ANN performance vs purpose-built DBs	When you already use Postgres and want to add vectors

Practical recommendation¶

Project size	Recommended DB
Prototype, <100K vectors	ChromaDB or FAISS
Production, <10M vectors	ChromaDB, Qdrant, or pgvector
Production, 10M–1B vectors	Qdrant, Milvus, or Pinecone
Production, >1B vectors	Milvus (distributed) or Pinecone

Common misunderstandings¶

"Vector databases replace traditional databases." No. Vector DBs solve nearest-neighbor search. Relational DBs solve structured queries, transactions, joins, etc. You typically need both.
"Pinecone is the best because it's managed." Managed services are convenient but expensive. Self-hosted Qdrant or Milvus may be cheaper at scale.
"FAISS is outdated." No. FAISS is still the fastest ANN library and is widely used in research and production. But it requires you to build the metadata layer yourself.

Exam angle¶

Expect questions that test: - What a vector database provides: ANN index + metadata + filtering + persistence + API. - ChromaDB: Developer-friendly, prototypes. - FAISS: Raw speed, no batteries included. - Qdrant / Milvus / Pinecone: Production-grade, managed or self-hosted. - pgvector: Postgres extension, integrates with existing DB.

Concept 8: Quantization for Compression¶

The problem it solves¶

A 768-dimensional float32 vector is 768 * 4 bytes = 3KB. For 10M vectors, that is 30GB. How do we compress embeddings to save memory and speed up search?

The intuition¶

Quantization reduces precision. Instead of storing each dimension as a 32-bit float, store it as an 8-bit integer (or less).

int8 quantization: - Map the range [min, max] of each dimension to [0, 255]. - Store 8-bit integers instead of 32-bit floats. - Compression ratio: 4x (32 bits → 8 bits). - Accuracy loss: Minimal (typically <1% drop in recall).

Product Quantization (PQ): - Split the 768-dimensional vector into e.g., 96 sub-vectors of 8 dimensions each. - Cluster each sub-vector space into 256 centroids. - Store the centroid ID (1 byte) instead of the sub-vector. - Compression ratio: 96x (768 * 4 bytes → 96 bytes). - Accuracy loss: Higher (5–10% drop in recall), but acceptable for large-scale retrieval.

Worked example: int8 quantization¶

Original vector: [0.1, 0.5, 0.9] (float32, 12 bytes)

Quantize: - min = 0.1, max = 0.9, range = 0.8 - Map [0.1, 0.9] to [0, 255] - 0.1 → 0 - 0.5 → (0.5 - 0.1) / 0.8 * 255 ≈ 127 - 0.9 → 255

Quantized vector: [0, 127, 255] (int8, 3 bytes)

Compression ratio: 12 bytes → 3 bytes = 4x.

Common misunderstandings¶

"Quantization always hurts accuracy." True, but the drop is often negligible (1–5%) for int8. PQ has higher loss but is acceptable for large-scale systems.
"I should always use PQ for maximum compression." Not necessarily. int8 is a good middle ground (4x compression, minimal loss). PQ is for extreme scale (billions of vectors).

Exam angle¶

Expect questions that test: - What quantization is: Reduce precision to compress embeddings. - int8: 4x compression, minimal accuracy loss. - Product Quantization (PQ): 50–100x compression, higher accuracy loss. - Trade-off: Compression vs accuracy vs search speed.

Concept 9: Instruction-Tuned Embedders¶

The problem it solves¶

Generic embedding models are trained on web text. They may not work well on domain-specific tasks (e.g., legal documents, medical records). How do we adapt embedders to specific tasks?

The intuition¶

Instruction-tuned embedders allow you to prepend a task instruction to the text:

Example: - Query: "Represent this question for retrieving relevant documents: How do I reset my password?" - Document: "Represent this document for retrieval: To reset your password, click 'Forgot Password'..."

The embedder is trained to encode the instruction along with the text, producing task-specific embeddings.

Why this helps: - Generic embedders produce the same embedding for "How do I reset my password?" whether you are searching for documents, clustering similar questions, or computing semantic similarity. - Instruction-tuned embedders produce DIFFERENT embeddings for different tasks, improving task-specific performance.

Popular instruction-tuned models: - E5-instruct (Microsoft) - BGE-instruct (BAAI) - NV-Embed (NVIDIA)

Worked example¶

Query (generic embedder): "How do I reset my password?" Embedding: [0.2, 0.5, 0.7, ...]

Query (instruction-tuned embedder):

Represent this question for retrieving relevant documents:
How do I reset my password?

Embedding: [0.3, 0.6, 0.8, ...] (different from generic embedding)

Result: The instruction-tuned embedding is optimized for retrieval, not for other tasks (clustering, similarity, etc.).

Common misunderstandings¶

"Instruction-tuned embedders replace fine-tuning." Not quite. Fine-tuning trains a custom model on your domain data. Instruction-tuned embedders are off-the-shelf models that adapt to tasks via instructions. Fine-tuning is more powerful but requires labeled data.
"I should always use instruction-tuned embedders." Not always. If you have a narrow, well-defined task (e.g., FAQ retrieval), a fine-tuned model may be better. If you have a broad, multi-task use case, instruction-tuned embedders are easier.

Exam angle¶

Expect questions that test: - What instruction-tuned embedders are: Encode task instructions along with text. - Why they help: Produce task-specific embeddings. - Popular models: E5-instruct, BGE-instruct, NV-Embed. - When to use: Broad, multi-task use cases. For narrow tasks, fine-tuning may be better.

Concept 10: Late-Interaction Retrievers (ColBERT)¶

The problem it solves¶

Bi-encoders are fast but coarse (single vector per document). Cross-encoders are accurate but slow (N forward passes). Is there a middle ground?

The intuition¶

Late-interaction models (ColBERT) produce per-token embeddings instead of per-document embeddings.

Standard bi-encoder: - Doc: "The cat sat on the mat" → single vector [0.2, 0.5, 0.7]

ColBERT: - Doc: "The cat sat on the mat" → 6 vectors (one per token): - "The" → [0.1, 0.3, 0.2] - "cat" → [0.5, 0.7, 0.8] - "sat" → [0.2, 0.4, 0.3] - ...

Retrieval: For each query token, find the most similar document token (MaxSim). Sum over all query tokens.

Why this works: ColBERT captures fine-grained token-level interactions (like a cross-encoder), but the document embeddings can still be precomputed (like a bi-encoder).

Trade-off: Near cross-encoder quality at bi-encoder cost, BUT the index is much larger (6 vectors per document instead of 1).

Worked example¶

Query: "How do I reset my password?" Tokens: [How, do, I, reset, my, password]

Document: "To reset your password, click 'Forgot Password'." Tokens: [To, reset, your, password, click, Forgot, Password]

MaxSim scoring: - Query token "reset" → most similar doc token "reset" → similarity 0.95 - Query token "password" → most similar doc token "password" → similarity 0.92 - Query token "How" → most similar doc token "To" → similarity 0.40 - ...

Total score: Sum of MaxSim scores = 0.95 + 0.92 + 0.40 + ... = 3.2

Ranking: Documents with high total scores rank higher.

Common misunderstandings¶

"ColBERT replaces bi-encoders." Not yet. ColBERT is more accurate but more expensive (storage and compute). It is used in research and some production systems, but standard bi-encoders are still the default.
"ColBERT is a cross-encoder." No. ColBERT is a late-interaction model. Document embeddings are precomputed, so retrieval is fast. Cross-encoders require N forward passes at query time.

Exam angle¶

Expect questions that test: - What late-interaction is: Per-token embeddings, MaxSim scoring. - ColBERT: Near cross-encoder quality, bi-encoder speed, larger index. - Trade-off: Accuracy vs storage cost.

Concept 11: Matryoshka Embeddings¶

The problem it solves¶

Embedding models produce fixed-dimensional vectors (e.g., 768 dimensions). But what if you want a smaller embedding for cheaper storage and faster search, or a larger embedding for higher accuracy?

The intuition¶

Matryoshka embeddings are variable-dimensional embeddings. The first N dimensions of the embedding are a valid embedding for any N.

Example: - Full embedding: [0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8] (8-dim) - Truncate to 4-dim: [0.1, 0.2, 0.3, 0.4] (valid embedding) - Truncate to 2-dim: [0.1, 0.2] (valid embedding)

Why this helps: - You can store 2-dim embeddings for cheap, fast retrieval. - For queries that need higher accuracy, rerank with 8-dim embeddings. - This is called cost-controlled retrieval.

Training: The model is trained such that each prefix [0:N] is a valid embedding.

Worked example¶

Use case: Search over 100M documents.

Strategy: 1. Store 128-dim embeddings (cheap). 2. Initial retrieval: top-1000 by 128-dim similarity. 3. Rerank: Recompute similarity with 768-dim embeddings for top-1000. 4. Return top-10.

Savings: 768-dim embeddings for 100M docs = 300GB. 128-dim embeddings = 50GB. 85% storage savings.

Common misunderstandings¶

"Matryoshka embeddings are a new model architecture." No. They are a training technique. You can apply Matryoshka training to any embedding model.
"Smaller dimensions are always worse." Not necessarily. For simple queries, 128-dim may be sufficient. For complex queries, 768-dim helps.

Exam angle¶

Expect questions that test: - What Matryoshka embeddings are: Variable-dimensional embeddings where each prefix is valid. - Why they help: Cost-controlled retrieval (cheap initial retrieval, expensive rerank). - Use case: Store small embeddings for all docs, use large embeddings for top-k reranking.

Concept 12: GraphRAG¶

The problem it solves¶

Vector retrieval works well for single-hop queries. But what about multi-hop queries that require traversing relationships in the knowledge base?

The intuition¶

GraphRAG builds a knowledge graph from the corpus and uses graph traversal alongside vector search.

Example: - Query: "Who directed the movie that won Best Picture the year Obama was first elected?" - Knowledge graph: - Obama → elected → 2008 - 2008 → Best Picture → Slumdog Millionaire - Slumdog Millionaire → director → Danny Boyle

Retrieval: 1. Vector search: "Obama" → retrieve documents about Obama, 2008 election. 2. Graph traversal: 2008 → Best Picture → Slumdog Millionaire → Danny Boyle. 3. Final answer: "Danny Boyle."

Why this helps: Graph traversal captures explicit relationships (facts). Vector search captures implicit similarity (meaning). Combining both improves multi-hop retrieval.

Worked example¶

Traditional RAG: - Embed query: "Who directed the movie that won Best Picture the year Obama was first elected?" - Retrieve top-k documents. - Hope that one document contains all the information. - Likely fails because no single document chains Obama → 2008 → Best Picture → director.

GraphRAG: - Extract entities: Obama, Best Picture, director. - Traverse graph: Obama → 2008 → Slumdog Millionaire → Danny Boyle. - Retrieve documents about Danny Boyle for additional context. - Generate answer: "Danny Boyle."

Common misunderstandings¶

"GraphRAG replaces vector retrieval." No. GraphRAG COMBINES vector retrieval and graph traversal. You need both.
"Building a knowledge graph is easy." No. Knowledge graph construction (entity extraction, relation extraction, linking) is hard and error-prone. Microsoft's GraphRAG uses LLMs to extract entities and relations, but it is still expensive.

Exam angle¶

Expect questions that test: - What GraphRAG is: Combine vector search and graph traversal. - Why it helps: Multi-hop queries require traversing relationships. - Example: The "Obama → 2008 → Best Picture → director" example above. - Trade-off: Better for multi-hop queries, but requires building and maintaining a knowledge graph.

Concept 13: Self-RAG and FLARE¶

The problem it solves¶

Standard RAG retrieves once at the start. But what if the LLM realizes mid-generation that it needs more information?

The intuition¶

Self-RAG and FLARE are adaptive retrieval methods where the LLM decides WHEN to retrieve.

Self-RAG: - The LLM generates a token. - After each token, it predicts: "Do I need more information?" - If yes, retrieve and inject context. - If no, continue generating.

FLARE (Forward-Looking Active Retrieval): - The LLM generates a token. - If the token has low confidence (low probability), trigger retrieval. - Inject context and regenerate.

Why this helps: The LLM retrieves ONLY when needed, reducing retrieval cost and improving accuracy.

Worked example: FLARE¶

Query: "What is the capital of France and its population?"

Generation (without FLARE): - LLM: "The capital of France is Paris." (confident) - LLM: "Its population is..." (low confidence — the LLM does not know) - Trigger retrieval: search for "Paris population" → 2.1M. - Inject context and regenerate: "Its population is approximately 2.1 million."

Result: The LLM retrieves only when confidence is low, avoiding unnecessary retrievals.

Common misunderstandings¶

"Self-RAG replaces standard RAG." No. Self-RAG is more expensive (requires confidence prediction and multiple retrievals). Use it for complex, multi-hop queries. Use standard RAG for simple lookups.
"Self-RAG always retrieves more." Not necessarily. For simple queries, Self-RAG may retrieve zero times (the LLM is confident throughout). For complex queries, it may retrieve 3-5 times.

Exam angle¶

Expect questions that test: - What adaptive retrieval is: LLM decides when to retrieve. - Self-RAG: Retrieve when the LLM predicts it needs more information. - FLARE: Retrieve when generation confidence is low. - Trade-off: More accurate for complex queries, but more expensive.

Putting it together¶

Production RAG stack:

Document processing:
Use unstructured or Docling for layout-aware parsing.
Extract tables, headers, metadata.
Chunking:
300–800 tokens, 10–20% overlap, recursive splitting.
Store parent-child: small chunks for retrieval, large chunks for LLM.
Embedding:
text-embedding-3-small (prototype) or bge-large-en-v1.5 (production).
Consider instruction-tuned embedders (E5-instruct) for multi-task use cases.
Indexing:
ChromaDB (prototype, <10M vectors).
Qdrant, Milvus, or Pinecone (production, >10M vectors).
Use HNSW for read-heavy, IVF for write-heavy.
Apply int8 quantization for 4x compression.
Retrieval:
Hybrid (BM25 + dense) with RRF.
Retrieve top-100.
Reranking:
Cross-encoder (Cohere Rerank or bge-reranker-large).
Rerank top-100 to top-5.
Generation:
Augment prompt with top-5 chunks.
LLM generates grounded answer.
Evaluation:
RAGAS: context precision, context recall, answer relevancy, faithfulness.
Monitor in production: log retrieval scores, reranking changes, answer feedback.

Check yourself¶

Why do we normalize embeddings?
To make cosine similarity = dot product (cheaper computation).
What is the difference between IVF and HNSW?
IVF clusters vectors into buckets and searches closest buckets. HNSW builds a navigable graph and traverses it to find neighbors. HNSW is more accurate but uses more memory.
What is hybrid retrieval and how do you merge BM25 and dense results?
Hybrid retrieval combines BM25 (lexical) and dense (semantic) retrieval. Merge using Reciprocal Rank Fusion (RRF).
What is the production pattern for reranking?
Bi-encoder retrieves top-100 (fast, scalable). Cross-encoder reranks to top-5 (accurate, expensive).
What is GraphRAG and when is it useful?
GraphRAG combines vector search and graph traversal. Useful for multi-hop queries that require traversing relationships (e.g., "Who directed the movie that won Best Picture the year Obama was elected?").

Quick reference (for revision)¶

Concept	Key idea
Embeddings	Fixed-dimensional dense vectors. L2-normalize to make cosine = dot product
Document processing	The unsolved problem. PDFs, OCR, tables. Tools: PyMuPDF, unstructured, Docling
Chunking defaults	300–800 tokens, 10–20% overlap, recursive splitting
Hybrid retrieval	BM25 (lexical) + dense (semantic). Merge with RRF
Reranking	Cross-encoder reranks bi-encoder results (top-100 → top-5)
Vector databases	ChromaDB (dev), FAISS (speed), Qdrant/Milvus/Pinecone (production), pgvector (Postgres)
ANN indexes	IVF (cluster into buckets), HNSW (graph-based), Flat (brute force)
Quantization	int8 (4x compression, minimal loss), PQ (50–100x, higher loss)
Instruction-tuned embedders	E5-instruct, BGE-instruct, NV-Embed. Encode task instructions for task-specific embeddings
Late-interaction (ColBERT)	Per-token embeddings, MaxSim scoring. Near cross-encoder quality at bi-encoder cost
Matryoshka embeddings	Variable-dim embeddings. Store small for cheap retrieval, use large for reranking
GraphRAG	Combine vector search and graph traversal for multi-hop queries
Self-RAG / FLARE	Adaptive retrieval. LLM decides when to retrieve