Deep NLP

4 episodes · follows chapter 11 of the textbook

Retrieval-based Models

How a language model finds things. We build lexical search from the inverted index up (tf-idf, BM25 derived from probability, top-k heaps), then dense retrieval (bi-encoders trained with InfoNCE) and approximate nearest-neighbour search (IVF, HNSW), then retrieval-augmented generation with every stage inspectable, and finally the metrics and datasets that tell you whether retrieval or reading is the bottleneck.

Progress — loading…

Objectives

Language

  • Explain the vocabulary-mismatch problem and why lexical and dense retrieval fail in complementary ways
  • Describe the RAG pipeline (retrieve, assemble, read) and attribute failures to the right stage
  • Know what SQuAD, Natural Questions, MS MARCO and BEIR measure, and the pitfalls of each kind of benchmark

Math & data structures

  • Derive idf from the log-odds of term occurrence in relevant vs non-relevant documents
  • Derive BM25's saturation and length-normalization terms from required properties
  • Derive InfoNCE as softmax cross-entropy over in-batch passages, with its gradient
  • Derive P@k, R@k, MRR, AP and nDCG, including why log2(i+1) and why normalize by IDCG
  • Posting lists and two-pointer intersection; size-k min-heaps; skip lists; navigable small-world graphs

Code

  • Build a BM25 search engine with an inverted index and a top-k heap
  • Train a NumPy bi-encoder with analytic InfoNCE gradients; port it to PyTorch
  • Implement HNSW-lite and plot recall vs ef against brute force
  • Build an inspectable RAG pipeline and break it at its seams
  • Implement retrieval and QA metrics and a retrieval-vs-reader error analysis

Episodes

  1. Information Retrieval: Inverted Indexes, tf-idf, and BM2518 min · 31 cues

    Inverted index, posting lists, tf-idf derivation, BM25 saturation intuition, top-k with heaps.

  2. Dense Retrieval and Approximate Nearest Neighbors19 min · 32 cues

    Bi-encoders, contrastive training (InfoNCE), ANN (IVF, HNSW graphs), recall vs speed.

  3. Retrieval-Augmented Generation, Stage by Stage16 min · 30 cues

    RAG pipeline, chunking, prompt assembly, failure modes, evaluation of retrieval separately.

  4. QA Datasets and Evaluation: What the Numbers Actually Measure17 min · 31 cues

    EM/F1 for QA, P@k, MRR, nDCG, datasets (SQuAD, NQ, MS MARCO, BEIR).

Exercises

ExerciseTierLadderTime
A BM25 search engine from scratch: posting lists, saturation, and a top-k heap browserPredict · Scratch · Compose60 min
HNSW-lite: skip-list levels, beam search on a graph, and the diversity heuristic browserScratch · Harden · Probe a claim75 min
Port the InfoNCE bi-encoder to PyTorch and match the NumPy reference gpuPort45 min
Break RAG at its seams: chunk overlap, prompt budgets, and the truncated question browserPredict · Harden · Break it60 min
Retrieval and QA metrics from scratch: P@k, R@k, MRR, AP, nDCG, EM and F1 browserScratch · Harden · Compose50 min

Labs

Library contributions

Files in nlpcore this module teaches you to write.

Sources

  1. Thakur et al., BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models, 2021 · arXiv:2104.08663
  2. Graham, Knuth, Patashnik, Concrete Mathematics (2nd ed.) · §Ch. 9 Asymptotics (O-notation, for the complexity claims)
  3. Zhang, Lipton, Li, Smola. Dive into Deep Learning (softmax regression and cross-entropy loss) · link · §4.1 Softmax Regression
  4. Järvelin & Kekäläinen, Cumulated gain-based evaluation of IR techniques, ACM TOIS 20(4), 422-446, 2002
  5. Karpukhin, Oğuz, Min, Lewis, Wu, Edunov, Chen, Yih. Dense Passage Retrieval for Open-Domain Question Answering, 2020 · arXiv:2004.04906
  6. Khattab & Zaharia, ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT, SIGIR 2020 · arXiv:2004.12832unverified
  7. Jeremy Kun, A Programmer's Introduction to Mathematics · §Ch. 6 Graphs (6.1 The Definition of a Graph), 12.3 Inner Products, 4.2 Clever Bijections and Counting
  8. Lewis et al. (12 authors), Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks, 2020 · arXiv:2005.11401
  9. Apache Lucene, BM25Similarity (defaults k1 = 1.2, b = 0.75; idf = log(1 + (docCount - docFreq + 0.5) / (docFreq + 0.5))) · link
  10. Yu. A. Malkov & D. A. Yashunin, Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs, 2016 · arXiv:1603.09320
  11. MS MARCO: A Human Generated MAchine Reading COmprehension Dataset (Bajaj et al., arXiv 1611.09268, 2016)
  12. Kwiatkowski et al., Natural Questions: A Benchmark for Question Answering Research, TACL 7, 452-466, 2019
  13. Rajpurkar, Zhang, Lopyrev, Liang. SQuAD: 100,000+ Questions for Machine Comprehension of Text, 2016 · arXiv:1606.05250
  14. Stephen Robertson & Hugo Zaragoza, The Probabilistic Relevance Framework: BM25 and Beyond, Foundations and Trends in Information Retrieval 3(4), 2009 · link
  15. Gerard Salton and the SMART information retrieval system (begun at Harvard, developed at Cornell after Salton moved there in 1965)
  16. Jurafsky & Martin, Speech and Language Processing, 3rd ed. draft (Aug 19, 2026), Ch. 11 Information Retrieval and Retrieval-Augmented Generation (running header: Retrieval-based Models) · link · §11.1, 11.1.1, 11.1.2, 11.1.3, 11.1.4, 11.1.5, 11.2, 11.3, 11.4, 11.5, 11.6, 11.7, Historical Notes
  17. Karen Spärck Jones, A statistical interpretation of term specificity and its application in retrieval, Journal of Documentation 28(1), 1972
  18. trec_eval (NIST), map measure: sum of precisions at relevant retrieved ranks divided by the total number of relevant documents for the topic · linkunverified
  19. van den Oord, Li, Vinyals. Representation Learning with Contrastive Predictive Coding (introduces the name InfoNCE) · arXiv:1807.03748