Despite their immense capabilities, Large Language Models are static artifacts: their parametric memory is frozen at training cutoff, and their stochastic generative nature induces Hallucinations—convincing fabrications presented with unflinching confidence. Retrieval-Augmented Generation (RAG) unites non-parametric external knowledge bases with parametric neural generation, dynamically retrieving verified factual context from petabyte-scale vector indices and grounding model outputs in verifiable evidence.
1. The Tripartite Architecture of RAG
Formulated by Patrick Lewis et al. (2020), modern enterprise RAG decouples knowledge retrieval from reasoning across three distinct stages:
- Document Chunking & Vectorization: Unstructured corpora are partitioned into semantic chunks $d in mathcal{D}$ and encoded into continuous vector spaces via a dense bi-encoder: $mathbf{e}_d = E_{text{doc}}(d) in mathbb{R}^D$.
- Approximate Nearest Neighbor (ANN) Retrieval: Given user query $q$, encode $mathbf{e}_q = E_{text{query}}(q)$ and retrieve the top-$k$ most similar documents maximizing cosine similarity: $text{sim}(q, d) = frac{mathbf{e}_q cdot mathbf{e}_d}{|mathbf{e}_q| |mathbf{e}_d|}$.
- Conditioned Generation: The retrieved documents are formatted into an augmented context prompt passed to the generator: $P(y mid q) = prod_t P(y_t mid q, d_1, dots, d_k, y_{<t})$.
2. Hierarchical Navigable Small World (HNSW) Indexing
Exact nearest neighbor search scales as $O(N cdot D)$, which is intractable for millions of documents. HNSW (Malkov & Yashunin, 2018) constructs a multi-layer geometric graph structure inspired by skip-lists:
- Layer Hierarchy: The top layers contain sparse, long-range connections between distant vector clusters, enabling rapid logarithmic geographic traversal across the vector space.
- Greedy Graph Traversal: At each layer, search begins at an entry point and greedily moves to the neighboring node that minimizes Euclidean distance to query vector $mathbf{e}_q$. Upon reaching a local minimum, search drops to the denser layer below.
- Bottom Layer $ell_0$: The base layer holds all vectors connected via Delaunay-like clustering graphs, achieving $O(log N)$ search latency with >98% recall accuracy.
3. Hybrid Search & Cross-Encoder Reranking
Dense semantic retrieval often fails when users search for exact product codes, legal IDs, or rare acronyms. Modern production systems employ Hybrid Retrieval, fusing dense vector similarity with sparse lexical keyword matching (BM25) via Reciprocal Rank Fusion (RRF):
text{RRF}(d) = sum_{m in {text{dense}, text{sparse}}} frac{1}{k + text{Rank}_m(d)}
Candidate pools from hybrid retrieval (e.g., top 100 candidates) are then passed through an intensive Cross-Encoder Reranker. Unlike bi-encoders that process queries and documents independently, cross-encoders concatenate the query and document into a single sequence $[q; d]$ and compute full all-to-all attention across all tokens, scoring relevance with precision that eliminates irrelevant noise before LLM ingestion.
