Math Foundations — Lecture 12

Light on math: retrieval scoring (cosine similarity over embeddings), Chain-of-Thought formalism, and a comparison of dense vs sparse retrieval.

Chain-of-Thought as conditional generation

A plain LM directly samples an answer \(y\) given a prompt \(x\):

\[p(y \mid x) = \prod_{t=1}^{|y|} p(y_t \mid x, y_{

A Chain-of-Thought prompt introduces an intermediate reasoning trace \(z\):

\[p(y \mid x) = \sum_{z}\, p(z \mid x)\, p(y \mid x, z)\]

In practice we do not marginalise — we sample one trace \(\hat{z}\sim p(z\mid x)\) and read off \(\hat{y}=\arg\max p(y\mid x,\hat{z})\). The trace acts as scratch memory: extra tokens that condition the answer.

Self-consistency

Sample \(K\) reasoning traces, then majority-vote over the extracted answers:

\[\hat{y} \;=\; \arg\max_{y}\;\sum_{k=1}^{K} \mathbf{1}\!\left[\,\mathrm{extract}(z^{(k)},y^{(k)})=y\,\right],\quad (z^{(k)},y^{(k)})\sim p(\cdot\mid x)\]

This Monte-Carlo estimate of the marginal \(p(y\mid x)\) often beats greedy CoT.

Retrieval scoring for RAG

Given a query \(q\) and a corpus of documents \(\{d_1,\dots,d_N\}\), we return the top-\(k\) by some score \(s(q,d_i)\).

Dense retrieval (cosine similarity)

Encode query and documents with an embedding model \(E_q,E_d:\text{text}\to\mathbb{R}^{D}\):

\[\mathbf{q} = E_q(q),\quad \mathbf{d}_i = E_d(d_i)\]

\[s_{\text{dense}}(q,d_i) \;=\; \cos(\mathbf{q},\mathbf{d}_i) \;=\; \frac{\mathbf{q}^\top \mathbf{d}_i}{\lVert\mathbf{q}\rVert\,\lVert\mathbf{d}_i\rVert}\]

If the embeddings are L2-normalised (\(\lVert\mathbf{q}\rVert=\lVert\mathbf{d}_i\rVert=1\)) this reduces to the dot product. Top-\(k\) retrieval is then an approximate nearest-neighbour lookup in a vector store.

Sparse retrieval (BM25)

BM25 is a tf–idf variant over bag-of-words:

\[s_{\text{BM25}}(q,d) \;=\; \sum_{t \in q} \mathrm{IDF}(t)\,\cdot\,\frac{f(t,d)\,(k_1+1)}{f(t,d) + k_1\!\left(1-b+b\,\frac{|d|}{\bar{|d|}}\right)}\]

where \(f(t,d)\) is term frequency, \(|d|/\bar{|d|}\) the length normaliser, and \(k_1,b\) are hyperparameters. Pure lexical match — fast and strong baseline, but blind to paraphrase.

Dense vs sparse: when to use what?

Aspect	Sparse (BM25)	Dense (cosine)
Match type	exact lexical	semantic / paraphrase
Cold start	works out-of-the-box	needs an embedding model
Rare names / IDs	strong	can miss
Synonyms	misses	handles
Index	inverted index	ANN vector store

In practice, RAG systems often combine the two (hybrid retrieval) and re-rank the union with a cross-encoder.

Quick Check: If query and document embeddings are L2-normalised, cosine similarity reduces to:

The dot product \(\mathbf{q}^\top\mathbf{d}\)

The Euclidean distance \(\lVert\mathbf{q}-\mathbf{d}\rVert\)

A BM25 score

ReAct loop (pseudo-formal)

At step \(t\) the agent has a history \(h_t = (x, \tau_1, a_1, o_1, \dots, \tau_{t-1}, a_{t-1}, o_{t-1})\) of thoughts \(\tau\), actions \(a\), observations \(o\). It samples the next thought-action pair from a single LM:

\[(\tau_t, a_t) \;\sim\; p_{\mathrm{LM}}(\cdot \mid h_t)\]

\[o_t \;=\; \mathrm{Env}(a_t)\]

The loop terminates when \(a_t\) is a special Finish[y] action; the agent returns \(y\). No parameters are learned — the entire behaviour is induced from few-shot demonstrations of \((\tau, a, o)\) traces.