j4flmao Advanced RAG Architecture: Algorithmic Foundations and Compilational Paradigms
1. Vector Database Indexing Mechanics
1.1 Hierarchical Navigable Small World (HNSW) Graphs
HNSW operates as a multi-layered proximity graph where each layer constitutes a skip-list-esque representation of the vector space. The construction involves stochastic insertion with an exponentially decaying probability of promotion to higher layers.
- Search Complexity: O(log N)
- Routing Paradigm: Search initiates at the topmost layer $L$, identifying the local minimum (nearest neighbor) using greedy search. This node serves as the entry point for layer $L-1$. The search progresses iteratively down to layer 0 (containing all elements).
- Edge Heuristics: To prevent exponential edge growth and maintain small-world properties, neighborhood pruning is employed based on distance heuristics rather than strict K-NN, ensuring diverse connectivity.
1.2 Inverted File Index with Product Quantization (IVF-PQ)
IVF-PQ relies on two distinct mechanisms: space partitioning (IVF) and vector compression (PQ).
- IVF (Coarse Quantization): The vector space is partitioned into $K$ Voronoi cells using k-means clustering. A query is first routed to the nearest $nprobe$ centroids, drastically reducing the search space from $N$ to $N \times (nprobe/K)$.
- PQ (Fine Quantization): Sub-vector decomposition. A $D$-dimensional vector is split into $M$ sub-vectors of dimension $D/M$. Each sub-space is independently clustered into $2^B$ sub-centroids (typically $B=8$). Distances are approximated using pre-computed lookup tables (Asymmetric Distance Computation), enabling exhaustive search within Voronoi cells at high throughput.
2. Dynamic Retrieval Paradigms: Self-RAG and DSPy
2.1 Self-RAG (Self-Reflective Retrieval-Augmented Generation)
An LM is explicitly trained (or prompted) to output reflection tokens alongside the generative sequence.
- [Retrieve] Token: Determines necessity of exogenous context (on-demand retrieval).
- [ISREL] Token: Evaluates the relevance of retrieved passages to the context.
- [ISSUP] Token: Verifies if the generated proposition is directly entailed by the retrieved passage, preventing hallucination.
- [ISUSE] Token: Assesses overall utility. Inference involves a critique-guided decoding strategy where trajectories with optimal reflection token probabilities are prioritized.
2.2 DSPy: Compiling Declarative Prompts
DSPy abstains from manual prompt engineering, treating LLM pipelines as differentiable computational graphs.
- Signatures: Declarative input/output specifications (e.g.,
question -> context, answer). - Teleprompters: Optimizers (e.g., BootstrapFewShot, MIPRO) that compile programs. They simulate the pipeline, aggregate successful traces, and backpropagate gradients (via language-based critique or scalar metrics) to update the parameters (prompts and few-shot examples) of each module.
3. Architecture Topology
%%{init: {"theme": "default", "flowchart": {"useMaxWidth": true}}}%%
flowchart TD
A[Query Formulation] -->|DSPy Optimizer| B{Self-RAG Routing}
B -->|Generate [Retrieve]=Yes| C[Vector Database]
B -->|Generate [Retrieve]=No| D[Direct Generation]
subgraph VectorRetrievalEngineVectorRetrievalEngine ["Vector Retrieval Engine<br><br><br>"]
C --> E{Index Selection}
E -->|High Recall| F[HNSW Multi-layer Graph]
E -->|Low Memory/High QPS| G[IVF-PQ]
F --> H[Greedy Routing L_n -> L_0]
G --> I[Voronoi Cell Routing]
I --> J[ADC Lookup Tables]
end
H --> K[Passage Retrieval]
J --> K
K --> L[Critic Module: Emit ISREL, ISSUP]
L -->|High Confidence| M[Final Response Generation]
L -->|Low Confidence| C