Module 1: Linear Algebra & Deep Learning Foundations for Sequence Models

Before examining the Transformer architecture, we must understand the mathematical substrate upon which all modern sequence modeling rests: high-dimensional vector spaces, affine transformations, numerical stability in probability distributions, and the empirical failures of recurrent neural networks.

---

1.1 Vector Spaces, Dot Products, and Inner Product as Semantic Similarity

In natural language processing, discrete textual symbols (tokens) are mapped into continuous dense representations:

$$\mathbf{x} \in \mathbb{R}^{d_{\text{model}}}$$

Where $d_{\text{model}}$ typically ranges from $768$ (GPT-2 Small) to $4096$ (LLaMA-3 8B) up to $12{,}288$ (GPT-4 / Gemma large).

From Text to Vectors: The Embedding Lookup Walk-through

How does a raw word like "cat" transform into an activation vector in $\mathbb{R}^{d_{\text{model}}}$?

1. Tokenization: The raw string is mapped to a discrete vocabulary index $i \in \{0, 1, \dots, |V|-1\}$ via a lookup dictionary (e.g., "cat" $\to$ ID $3797$).
2. One-Hot Encoding: The index is represented as a sparse one-hot vector $\mathbf{e}_i \in \{0, 1\}^{|V|}$, where position $i$ is $1$ and all other entries are $0$.
3. Linear Projection / Table Indexing: The model stores an embedding matrix $W_E \in \mathbb{R}^{|V| \times d_{\text{model}}}$. Multiplying $\mathbf{e}_i^\top W_E$ mathematically extracts the $i$-th row of $W_E$: $$\mathbf{x} = \mathbf{e}_i^\top W_E = W_E[i, :] \in \mathbb{R}^{d_{\text{model}}}$$

In practice, deep learning frameworks do not perform sparse matrix multiplication; they execute an $\mathcal{O}(1)$ array lookup into contiguous memory (nn.Embedding(vocab_size, d_model)).

Geometric Meaning of the Dot Product

Given two vectors $\mathbf{u}, \mathbf{v} \in \mathbb{R}^d$, the Euclidean inner product is defined algebraically and geometrically as:

$$\langle \mathbf{u}, \mathbf{v} \rangle = \mathbf{u}^\top \mathbf{v} = \sum_{i=1}^d u_i v_i = \|\mathbf{u}\|_2 \|\mathbf{v}\|_2 \cos(\theta)$$

Where $\theta$ is the angle between the two vectors in $d$-dimensional space.

Architecture Flowchart
 Full Diagram
Generating architectural diagram...

• When $\theta = 0^\circ \implies \cos(\theta) = 1$, the vectors are collinear and convey maximum directional alignment.
• When $\theta = 90^\circ \implies \cos(\theta) = 0$, the vectors are orthogonal; their dot product is zero, representing semantic independence.
• When $\theta = 180^\circ \implies \cos(\theta) = -1$, the vectors are diametrically opposed.

Cosine Similarity vs. Unnormalized Dot Product

While cosine similarity normalizes vectors:

$$\operatorname{CosineSim}(\mathbf{u}, \mathbf{v}) = \frac{\mathbf{u}^\top \mathbf{v}}{\|\mathbf{u}\|_2 \|\mathbf{v}\|_2}$$

Transformers deliberately use unnormalized dot products in self-attention because vector magnitude $\|\mathbf{u}\|_2$ carries vital information—such as token rarity, syntactic salience, and prediction confidence.

---

1.2 Linear Projections & Learned Transformations (Q, K, V Geometry)

A raw token embedding $\mathbf{x}_i \in \mathbb{R}^{d_{\text{model}}}$ cannot simultaneously serve as a search query, an index key, and an informative payload without representational interference.

Therefore, the Transformer applies three distinct linear transformations via learnable weight matrices:

$$\mathbf{q}_i = \mathbf{x}_i W^Q \quad (W^Q \in \mathbb{R}^{d_{\text{model}} \times d_k})$$ $$\mathbf{k}_i = \mathbf{x}_i W^K \quad (W^K \in \mathbb{R}^{d_{\text{model}} \times d_k})$$ $$\mathbf{v}_i = \mathbf{x}_i W^V \quad (W^V \in \mathbb{R}^{d_{\text{model}} \times d_v})$$

Architecture Flowchart
 Full Diagram
Generating architectural diagram...

Concrete Numerical Toy Example of Q, K, V Projections

To ground these matrices in concrete arithmetic, consider a toy setting with $d_{\text{model}} = 4$ and $d_k = d_v = 2$: Suppose token $\mathbf{x}_1 = [1.0, \, 0.0, \, 2.0, \, -1.0]$ and token $\mathbf{x}_2 = [0.0, \, 1.0, \, 1.0, \, 1.0]$. Given projection matrices:

$$W^Q = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 1 & -1 \\ 0 & 1 \end{bmatrix}, \quad W^K = \begin{bmatrix} 0 & 1 \\ 1 & 0 \\ -1 & 1 \\ 1 & 0 \end{bmatrix}$$

1. Calculate Query for Token 1: $$\mathbf{q}_1 = \mathbf{x}_1 W^Q = [1(1) + 0(0) + 2(1) - 1(0), \;\; 1(0) + 0(1) + 2(-1) - 1(1)] = [3.0, \, -3.0]$$
2. Calculate Key for Token 2: $$\mathbf{k}_2 = \mathbf{x}_2 W^K = [0(0) + 1(1) + 1(-1) + 1(1), \;\; 0(1) + 1(0) + 1(1) + 1(0)] = [1.0, \, 1.0]$$
3. Calculate Unscaled Dot Product: $$\mathbf{q}_1 \mathbf{k}_2^\top = (3.0 \times 1.0) + (-3.0 \times 1.0) = 3.0 - 3.0 = 0.0$$
4. Scale by $\sqrt{d_k} = \sqrt{2} \approx 1.414$: $$\operatorname{Score}(1, 2) = \frac{0.0}{1.414} = 0.0 \implies \exp(0.0) = 1.0$$

This demonstrates how learned projections transform raw token embeddings so that high alignment is learned dynamically rather than determined by arbitrary lexical coordinates.

Rank and Projection Subspaces

Because $W^Q, W^K, W^V$ have rank at most $\min(d_{\text{model}}, d_k)$, they project the high-dimensional representation into specialized lower-dimensional subspaces:

• $\mathbf{q}_i$ encodes the interrogative intention of token $i$.
• $\mathbf{k}_j$ encodes the addressable metadata of token $j$.
• The dot product $\mathbf{q}_i^\top \mathbf{k}_j$ evaluates how well token $j$'s features satisfy token $i$'s search demand.

---

1.3 Matrix Decomposition: SVD and Low-Rank Approximations

Any weight matrix $W \in \mathbb{R}^{m \times n}$ of rank $r$ can be factored via Singular Value Decomposition (SVD):

$$W = U \Sigma V^\top = \sum_{k=1}^r \sigma_k \mathbf{u}_k \mathbf{v}_k^\top$$

Where:

• $U \in \mathbb{R}^{m \times m}$ is an orthogonal matrix of left singular vectors.
• $\Sigma \in \mathbb{R}^{m \times n}$ is a diagonal matrix of non-negative singular values $\sigma_1 \ge \sigma_2 \ge \dots \ge \sigma_r > 0$.
• $V \in \mathbb{R}^{n \times n}$ is an orthogonal matrix of right singular vectors.

Architecture Flowchart
 Full Diagram
Generating architectural diagram...

The Eckart-Young-Mirsky Theorem

For any integer $k < r$, the optimal rank-$k$ approximation minimizing Frobenius error $\|W - W_k\|_F$ is obtained by truncating the sum at the top $k$ singular values:

$$W_k = \sum_{i=1}^k \sigma_i \mathbf{u}_i \mathbf{v}_i^\top, \quad \min_{\operatorname{rank}(B)=k} \|W - B\|_F = \sqrt{\sum_{i=k+1}^r \sigma_i^2}$$

This theorem directly justifies modern Low-Rank Adaptation (LoRA) and weight compression: overparameterized Transformer weight updates $\Delta W$ reside in an intrinsic subspace of remarkably low rank ($r \in \{4, 8, 16\}$).

Mathematical Mechanics of LoRA (Low-Rank Adaptation)

During fine-tuning, instead of updating all $d_{\text{in}} \times d_{\text{out}}$ parameters in $W_0$, LoRA freezes $W_0$ and injects a low-rank decomposition:

$$W = W_0 + \Delta W = W_0 + \frac{\alpha}{r} B A$$

Where:

• $B \in \mathbb{R}^{d_{\text{out}} \times r}$ and $A \in \mathbb{R}^{r \times d_{\text{in}}}$ with rank $r \ll \min(d_{\text{in}}, d_{\text{out}})$.
• $\alpha$ is a constant scaling hyperparameter (typically $\alpha = 2r$ or $16$).
• Initialization Proof: $A$ is initialized with random Gaussian noise $\mathcal{N}(0, \sigma^2)$, while $B$ is initialized strictly to zero ($B = 0$). Consequently: $$\Delta W = B A = 0 \cdot A = 0 \quad (\text{at step } t=0)$$ This guarantees that fine-tuning begins exactly at the pre-trained model's output without introducing sudden catastrophic disruption.

---

1.4 The Softmax Operator, Overflow Prevention, and Temperature Scaling

The Softmax function converts unnormalized logits $\mathbf{z} \in \mathbb{R}^N$ into a valid categorical probability distribution $\mathbf{p} \in \Delta^{N-1}$:

$$\operatorname{Softmax}(\mathbf{z})_i = \frac{e^{z_i}}{\sum_{j=1}^N e^{z_j}}$$

Numerical Catastrophe: Floating-Point Overflow

In IEEE 754 standard 32-bit float (fp32), the maximum representable value is $e^{88.7} \approx 3.4 \times 10^{38}$. For 16-bit half precision (fp16 or bf16), overflow occurs at $z_i > 11.0$ (fp16). If any $z_i > 88.7$, $e^{z_i} \to \infty$, leading to NaN during backward pass gradients.

Shift-Invariance & Safe Softmax

Softmax is strictly invariant to uniform scalar translation:

$$\operatorname{Softmax}(\mathbf{z} - c)_i = \frac{e^{z_i - c}}{\sum_j e^{z_j - c}} = \frac{e^{-c} e^{z_i}}{e^{-c} \sum_j e^{z_j}} = \operatorname{Softmax}(\mathbf{z})_i$$

In all production engines (PyTorch, FlashAttention, TensorRT-LLM), $c = \max_j (z_j)$ is subtracted before exponentiation:

$$\operatorname{SafeSoftmax}(\mathbf{z})_i = \frac{e^{z_i - \max_k(z_k)}}{\sum_{j=1}^N e^{z_j - \max_k(z_k)}}$$

Guaranteeing $z_i - \max_k(z_k) \le 0$ and strictly bounding the exponent between $(0, 1]$.

Temperature Scaling Regimes

When generating text or computing attention, we introduce temperature $T > 0$:

$$p_i = \frac{\exp(z_i / T)}{\sum_j \exp(z_j / T)}$$

• $T = 1.0$: Default calibrated model probabilities.
• $T \to 0$ (Argmax / Greedy): As temperature approaches zero, $\frac{z_{\max} - z_i}{T} \to \infty$ for all non-maximal logits. The probability distribution collapses into a Dirac delta (one-hot vector) centered on the single highest logit: $$\lim_{T \to 0^+} p_i = \begin{cases} 1, & \text{if } i = \arg\max_k z_k \\ 0, & \text{otherwise} \end{cases}$$
• $T \to \infty$ (Uniform Random): As temperature grows arbitrarily large, $z_i / T \to 0 \implies e^0 = 1$. All tokens become equally probable regardless of model knowledge: $$\lim_{T \to \infty} p_i = \frac{1}{N}$$

Architecture Flowchart
 Full Diagram
Generating architectural diagram...

Softmax Jacobian and Gradient Dynamics

The derivative of $\operatorname{Softmax}(\mathbf{z})_i$ with respect to logit $z_j$ is:

$$\frac{\partial p_i}{\partial z_j} = p_i (\delta_{ij} - p_j) = \begin{cases} p_i(1 - p_i), & \text{if } i = j \\ -p_i p_j, & \text{if } i \neq j \end{cases}$$

When one logit dominates ($p_i \to 1$), $1 - p_i \to 0$ and $p_j \to 0$, causing the gradient to vanish. This is why dot products in attention must be scaled by $\frac{1}{\sqrt{d_k}}$.

---

1.5 Sequential Bottlenecks: Why RNNs and LSTMs Failed at Scale

Prior to 2017, sequence learning relied on Recurrent Neural Networks (Elman RNNs, LSTMs, GRUs). The hidden state $\mathbf{h}_t$ was computed recursively:

$$\mathbf{h}_t = \tanh(W_{hh} \mathbf{h}_{t-1} + W_{xh} \mathbf{x}_t + \mathbf{b})$$

Architecture Flowchart
 Full Diagram
Generating architectural diagram...

1. Inability to Parallelize Across Sequences

Because $\mathbf{h}_t$ has a strict temporal dependency on $\mathbf{h}_{t-1}$, training an $N$-token sequence requires $N$ sequential matrix multiplications. On modern SIMD/GPU hardware with thousands of parallel tensor cores, this introduces catastrophic hardware under-utilization ($\mathcal{O}(N)$ sequential steps).

2. Vanishing and Exploding Gradients Across Long Paths

By the chain rule, backpropagating an error from step $T$ back to step $t$ involves repeated products of the recurrent transition Jacobian:

$$\frac{\partial \mathbf{h}_T}{\partial \mathbf{h}_t} = \prod_{k=t+1}^T \frac{\partial \mathbf{h}_k}{\partial \mathbf{h}_{k-1}} = \prod_{k=t+1}^T \operatorname{diag}(1 - \tanh^2(\cdot)) W_{hh}^\top$$

If the largest eigenvalue of $W_{hh}$, $\lambda_{\max} < 1$, the gradient magnitude decays exponentially with path length:

$$\left\|\frac{\partial \mathbf{h}_T}{\partial \mathbf{h}_t}\right\| \le c \cdot \lambda_{\max}^{T-t} \xrightarrow[T-t \to \infty]{} 0$$

If $\lambda_{\max} > 1$, the gradient explodes towards infinity. While LSTMs introduced additive cell memory paths to alleviate this, the computational graph length remained $\mathcal{O}(N)$.

3. The Transformer Breakthrough: Maximum Path Length $\mathcal{O}(1)$

The Transformer solves this fundamentally:

• Computational Path Length: Between any token $i$ and token $j$, the path length through Self-Attention is strictly $\mathcal{O}(1)$ (one matrix multiplication), eliminating exponential gradient decay.
• Parallelism: All tokens across the entire sequence are processed concurrently via batch matrix multiplication on GPU tensor cores.

---

Core Academic References

• Golub & Van Loan (2013): Matrix Computations (4th ed.). Johns Hopkins University Press.
• Bengio, Simard & Frasconi (1994): Learning long-term dependencies with gradient descent is difficult. IEEE Transactions on Neural Networks, 5(2): 157–166.
• Hochreiter & Schmidhuber (1997): Long Short-Term Memory. Neural Computation, 9(8): 1735–1780.
• Goodfellow, Bengio & Courville (2016): Deep Learning: Numerical Computation & Numerical Stability. MIT Press.