06. Approximate Nearest Neighbor (ANN) Algorithms: HNSW (Hierarchical Navigable Small World) & IVF-PQ Indexes • Generative AI, Large Language Models (LLMs) & Vector RAG • Rishabh Ki Kaksha

Generative AI, Large Language Models (LLMs) & Vector RAG › 06. Approximate Nearest Neighbor (ANN) Algorithms: HNSW (Hierarchical Navigable Small World) & IVF-PQ Indexes

50 mins

← Prev Next →

Course Syllabus

Module 1: Large Language Model (LLM) Fundamentals & Transformer Architecture

01. Transformer Architecture Deep Dive: Self-Attention Mechanism, Multi-Head Attention & Positional Encoding 02. Autoregressive Generation: Tokenization (BPE, WordPiece, SentencePiece), Sampling (Temperature, Top-K, Top-P) 03. Prompt Engineering Architecture: Few-Shot Prompting, Chain-of-Thought (CoT), ReAct & System Prompt Hardening

Part 1: LLM Internals & Vector RAG Pipelines

Module 2: Embeddings, Vector Spaces & Similarity Mathematics

04. Vector Embeddings: Dense vs Sparse Vectors (OpenAI text-embedding-3, BGE-Large, BM25) 05. Similarity Metrics: Cosine Similarity, Dot Product, Euclidean Distance & Manifold Geometry 06. Approximate Nearest Neighbor (ANN) Algorithms: HNSW (Hierarchical Navigable Small World) & IVF-PQ Indexes

Module 3: Vector Databases: Pinecone, Qdrant, Milvus, Chroma & pgvector

07. Vector Database Architecture: Comparing Pinecone, Qdrant, Weaviate, Milvus & PostgreSQL with pgvector 08. Metadata Filtering & Payload Indexing for High-Performance Multitenant Vector Search 09. Embedded Vector Stores: ChromaDB, DuckDB & In-Memory FAISS (Facebook AI Similarity Search)

Module 4: Advanced RAG Architecture: Chunking, Reranking & Hybrid Search

10. Document Chunking Strategies: Fixed Size, Recursive Character, Semantic Chunking & Parent Document Retrievers 11. Hybrid Search Architecture: Combining Keyword Search (BM25) + Dense Vector Search with Reciprocal Rank Fusion (RRF) 12. Cross-Encoder Reranking: Integrating Cohere Rerank / BGE-Reranker for Pinpoint Context Relevance

Module 5: Context Window Optimization, Multi-Query & Graph RAG

13. Multi-Query Generation, Sub-Question Decomposition & Step-Back Prompting for Complex Questions 14. Context Compression & Lost-in-the-Middle Mitigation Strategies 15. Graph RAG Architecture: Combining Knowledge Graphs (Neo4j / NetworkX) with Vector Search for Relational Insights

Module 6: RAG Evaluation (RAGAS), Guardrails & Production Deployment

16. RAG Evaluation Framework (RAGAS): Faithfulness, Answer Relevance, Context Precision & Context Recall 17. Guardrails & Safety: NeMo Guardrails, Llama Guard & Prompt Injection Defense Mechanisms 18. Streaming Output Architecture with Server-Sent Events (SSE) & WebSocket RAG Responses 19. Caching in GenAI: Semantic Caching with GPTCache & Redis to Slash API Costs by 70% 20. Production GenAI Deployment: Building an Enterprise PDF/Docs AI Assistant with LangChain & LlamaIndex

Interactive Lesson Studio

# 06. Approximate Nearest Neighbor (ANN) Algorithms: HNSW (Hierarchical Navigable Small World) & IVF-PQ Indexes

> Generative AI & Vector RAG Notes by Rishabh - Topic 06

---

### 1. The $O(N)$ Brute-Force Crisis ⚠️

100 Million vectors par exact cosine similarity calculate karna $O(N \cdot D)$ time leta hai (5 seconds per query!).  
**Approximate Nearest Neighbor (ANN):** 99% accuracy retain karte huye query time ko **< 2ms ($O(\log N)$)** par le aata hai!

---

### 2. HNSW (Hierarchical Navigable Small World - The Gold Standard 👑)

Skip-List data structure ka multi-layer geometric graph representation:

```
[ Layer 2 (Express Sparse Highway) ]  Node A ────────────────────────► Node Z
                                         │                              │
[ Layer 1 (Medium Density) ]          Node A ──────► Node M ─────────► Node Z
                                         │              │               │
[ Layer 0 (Full Dense Graph) ]        Node A ──► B ──► M ──► Q ──► R ──► Z
```
*Search starts at top sparse layer ➔ jumps to local maxima ➔ drops to Layer 0 for fine local exploration in $O(\log N)$!*

---

### 3. IVF-PQ (Inverted File with Product Quantization 📉)

*   **IVF:** Space ko Voronoi clusters ($K$-means centroids) me split karta hai.
*   **PQ (Product Quantization):** 1536-dim vector ko 8 sub-vectors me tod kar 8-byte integers me compress karta hai (**95% RAM compression!**).

---

### 4. Master Comparison Matrix

---

### 5. Interview Ke 3 Sawal Is Topic Se

1. **HNSW me `efSearch` aur `M` hyperparameters kya control karte hain?** -> `M` har node ke maximum graph neighbors control karta hai (Index memory size); `efSearch` search ke waqt dynamic priority queue size control karta hai (Latency vs Recall tradeoff).
2. **IVF me `nprobe` parameter kya karta hai?** -> Query search karte waqt kitne nearest Voronoi clusters ko scan karna hai.
3. **Filtered Vector Search (e.g. `userId == 123` + vector similarity) me Post-Filtering vs Pre-Filtering / Single-Stage HNSW me kya difference hai?** -> Post-filtering me vector search ke baad metadata filter hota hai (Recall collapse risk); Single-Stage HNSW search graph traversal ke dauran hi metadata constraints filter karta hai.

---
**Next Topic:** 07. Vector Database Architecture: Comparing Pinecone, Qdrant, Weaviate, Milvus & PostgreSQL with pgvector

Loading lesson content...

Python 3.12

Full IDE

Live Execution Terminal

Click "Execute Live" to run code.
                

Lesson Mastery AI Quiz

AI Doubt Solver

CERTIFICATE OF COMPLETION

Rishabh Gehlot

PHP 8+ & Laravel 11 Master Track