Step 01 — The Bottleneck: Recurrence, Tokens, Embeddings

2026/11/12

Contents: 0. Foundations from zero · 1. The paper and its people · 2. The lineage · 3. Why recurrence failed · 4. Tokens · 5. Embeddings · 6. Order-blindness · 7. Check yourself · 8. Sources

This is part one of a course on the Transformer. It assumes nothing — we start from what a computer actually stores when you type a letter, and end at the exact input a 2017 Transformer receives. Every concept used by the rest of the course is defined here, every claim is either derived in front of you or cited to its original paper. By the end of this part you should be able to answer, precisely: why did the Transformer need to exist, what does it see, and where do those numbers come from?

0. Foundations from absolute zero

0.1 What a computer stores when it stores text

A computer’s memory is bits: 0 or 1. Eight bits form a byte, which can express 2⁸ = 256 values. So the first problem of all of natural language processing is: how do you map text to numbers? The answer has layers, and each layer matters later.

Two facts from this that Step 1 will reuse. First: text was always numbers — every layer above, from characters to words to the vectors we will build, is just a re-encoding of these numbers. Second: the byte is the smallest meaningful alphabet — exactly 256 symbols — which is why the most modern tokenizers (Section 4.2) go all the way down to bytes and never meet a character they cannot encode.

flowchart LR
    A["a (a letter)"] --> B["97 (a number)"]
    B --> C["01100001 (bits)"]
    D["λ"] --> E["U+03BB"]
    E --> F["CE BB (two bytes)"]

0.2 Numbers, vectors, matrices, tensors

$$(\mathbf{A}\mathbf{x})_i = \sum_{j=1}^{n} A_{ij}\, x_j$$

— entry \(i\) of the result is the weighted sum of row \(i\) of the matrix with the vector. A matrix is a machine that transforms vectors, and a neural network is a stack of such machines whose entries are learned.

Vector operations used everywhere in this course:

$$\mathbf{u}\cdot\mathbf{v} = \sum_{i=1}^{d} u_i v_i \qquad \text{(dot product)} \qquad \|\mathbf{u}\| = \sqrt{\mathbf{u}\cdot\mathbf{u}} \qquad \text{(norm, i.e. length)}$$$$\cos(\mathbf{u},\mathbf{v}) = \frac{\mathbf{u}\cdot\mathbf{v}}{\|\mathbf{u}\|\,\|\mathbf{v}\|} \qquad \text{(cosine similarity, in } [-1,1])$$

The dot product is the single most important operation in this whole subject: it measures agreement. Two vectors pointing the same way have a large positive dot product; orthogonal vectors have zero; opposite vectors have a negative one. Attention (Step 03) is, literally, a table of normalized dot products.

0.3 Parameters, loss, gradients

A neural network is a function \(y = f_{\theta}(x)\) containing adjustable numbers, the parameters \(\theta\) (in 2017: 65 million of them). Training proceeds as follows. We measure how wrong the function is with a scalar loss \(L\). We compute the gradient \(\partial L/\partial \theta\) — for each parameter, how much the loss changes when that parameter is nudged. Then we move every parameter slightly against its gradient:

$$\theta \leftarrow \theta - \eta\, \frac{\partial L}{\partial \theta} \qquad \text{(gradient descent, } \eta \text{ = learning rate)}$$

One consequence to hold onto: if the gradient is (nearly) zero, learning stops. This single sentence is the entire explanation of the 1994 crisis in Section 3.2.

0.4 Probability and the softmax

A discrete probability distribution over \(V\) outcomes is a list of non-negative numbers \(p_1, \dots, p_V\) with \(\sum_i p_i = 1\). Language models output one such distribution per position (“how likely is each possible next token”). To turn arbitrary scores \(z_1,\dots,z_V\) into a distribution, the standard tool is the softmax:

$$\mathrm{softmax}(\mathbf{z})_i = \frac{e^{z_i}}{\sum_{j=1}^{V} e^{z_j}}$$

It is always positive, always sums to 1, and exaggerates the largest score. The final layer of the 2017 architecture (Step 07) is a softmax over the vocabulary \(V\).

0.5 Sequences and the two tasks

A sequence is an ordered list of items \(x_1, x_2, \dots, x_n\). The 2017 paper’s task is machine translation: sequence in (English), sequence out (German). Its architecture is two-sided: an encoder reads the input, a decoder writes the output. The other great task — predicting the next item from the previous ones — is language modeling; GPT (2018, Step 09) will keep only the decoder half of the 2017 design. Before any of this, the items themselves — tokens — must be invented. That is Section 4. First, why the machine that processed sequences in 2017 had to be replaced.

1. The paper and its people (2017)

“Attention Is All You Need” was written in the spring of 2017 by eight researchers at Google — Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Łukasz Kaiser, Illia Polosukhin — submitted to arXiv on 12 June 2017, and published at NeurIPS that December. As of 2026 it has been cited more than 150,000 times, placing it among the ten most-cited papers of the 21st century. Two trivia facts that are documented: the title is a nod to the Beatles’ All You Need Is Love, and the name “Transformer” was chosen because Jakob Uszkoreit liked the sound of the word.

The abstract’s second sentence is the declaration of the era that followed:

“We propose a new simple network architecture, the Transformer, based solely on attention mechanisms, dispensing with recurrence and convolutions entirely.”

The results were decisive. On WMT 2014 English→German, the big Transformer reached 28.4 BLEU, beating the best previous models — including ensembles of several networks — by more than 2 BLEU. On English→French it reached 41.0 BLEU (revised to 41.8 in later arXiv versions) after training for 3.5 days on eight NVIDIA P100 GPUs, “a small fraction of the training costs of the best models from the literature.” The base model trained in about 12 hours (100,000 steps at 0.4 s/step). The hyperparameters of the two sizes are the template for nearly every model since:

base big
layers N 6 6
d_model 512 1024
heads h 8 16
d_k = d_v 64 64
d_ff (feed-forward width) 2048 4096
dropout 0.1 0.3
label smoothing 0.1 0.1
parameters ~65 M ~213 M

The human story became part of the lore: within a few years all eight authors left Google — Shazeer co-founded Character.AI, Gomez co-founded Cohere, Polosukhin co-founded NEAR, Kaiser and Uszkoreit co-founded Inceptive, Vaswani and Parmar founded Adept (later Essential AI), Jones co-founded Sakana AI. The Wired retrospective “8 Google Employees Invented Modern AI” tells how the paper was written under time pressure that spring and shipped with eight names on it.

2. The world it replaced: the lineage 1986–2017

The Transformer is the endpoint of a thirty-year argument about sequences. Every design choice in the 2017 paper is an answer to a specific failure in this list.

timeline
    title The road to 2017
    1990 : Elman networks — simple RNNs
    1994 : Bengio, Simard & Frasconi — vanishing gradients
    1997 : Hochreiter & Schmidhuber — LSTM
    2013 : Mikolov et al. — word2vec
    2014 : Pennington et al. — GloVe
         : Sutskever et al. — seq2seq
         : Cho et al. — GRU
         : Bahdanau et al. — attention
    2015 : Luong et al. — attention variants
    2016 : Wu et al. — GNMT (Google Translate)
         : Sennrich et al. — BPE
         : Kalchbrenner et al. — ByteNet
    2017 : Gehring et al. — ConvS2S (May)
         : Vaswani et al. — THE TRANSFORMER (June)

The chain of ideas:

3. Why recurrence failed: the full math

3.1 The RNN, precisely

An (Elman-style) RNN keeps one hidden state and updates it per token:

$$h_t = \tanh\!\big(W_{hh}\, h_{t-1} + W_{xh}\, x_t + b_h\big)$$

with \(h_t \in \mathbb{R}^d\) the memory, \(x_t \in \mathbb{R}^{d_x}\) the current input, \(W_{hh} \in \mathbb{R}^{d\times d}\) the recurrent matrix, \(W_{xh} \in \mathbb{R}^{d \times d_x}\) the input matrix, and \(\tanh\) applied element-wise. Three numbers to memorize about this one line: it is serial (\(h_t\) needs \(h_{t-1}\)), its memory is fixed-width (everything known about the past must fit in \(d\) numbers), and its recurrent connection is nonlinear (the \(\tanh\) squeezes values into \([-1,1]\) at every single step).

3.2 Training it, and the 1994 catastrophe

To train, we unroll the recurrence through time and apply the chain rule (backpropagation through time, BPTT). Suppose the loss \(L\) depends on the final state \(h_T\). The gradient of \(L\) with respect to an earlier state \(h_t\) is a product of Jacobians:

$$\frac{\partial L}{\partial h_t} = \frac{\partial L}{\partial h_T} \prod_{k=t+1}^{T} J_k, \qquad J_k = \frac{\partial h_k}{\partial h_{k-1}} = \mathrm{diag}\big(\tanh'(z_k)\big)\, W_{hh}$$

where \(z_k = W_{hh}h_{k-1} + W_{xh}x_k + b_h\) and \(\tanh'(z) = 1 - \tanh^2(z) \le 1\). Now the problem appears. A product of matrices behaves, asymptotically, like its largest eigenvalue raised to the number of factors: \(\prod_{k} J_k\) scales roughly like \(\rho^{T-t}\) where \(\rho\) is the dominant eigenvalue of the typical \(J_k\). And \(J_k\) contains \(\mathrm{diag}(\tanh'(z_k))\), whose entries are strictly less than 1 (often much less, when \(z_k\) is far from 0).

This is the 1994 result of Bengio, Simard & Frasconi: gradient-based learning of long-range dependencies is fundamentally difficult in a recurrent architecture, not merely inconvenient. Gradient clipping (Pascanu et al., 2013) caps explosions. Nothing fixes vanishing — the information is already gone before the signal arrives. The hidden state’s contents after \(n\) steps are, mathematically, a function of everything, but the learning signal cannot reach the distant past.

flowchart LR
    subgraph A["RNN — O(n) serial steps, path length O(n)"]
        X1["x₁"] --> H1["h₁"]
        H1 --> H2["h₂"]
        H2 --> H3["h₃"]
        X2["x₂"] --> H2
        X3["x₃"] --> H3
    end
    subgraph B["Transformer — every pair at once, path length O(1)"]
        Y1["x₁"] --> AT["self-attention over all pairs"]
        Y2["x₂"] --> AT
        Y3["x₃"] --> AT
        AT --> Z["new representations in one pass"]
    end

3.3 The gate patches: LSTM and GRU

The LSTM (1997, with the forget gate from Gers et al., 2000) and the GRU (Cho et al., 2014) attack the vanishing gradient directly, by giving the state a linear highway through time:

$$i_t = \sigma\big(W_i[h_{t-1},x_t]+b_i\big), \quad f_t = \sigma\big(W_f[h_{t-1},x_t]+b_f\big), \quad o_t = \sigma\big(W_o[h_{t-1},x_t]+b_o\big)$$$$\tilde c_t = \tanh\big(W_c[h_{t-1},x_t]+b_c\big), \qquad c_t = f_t \odot c_{t-1} + i_t \odot \tilde c_t, \qquad h_t = o_t \odot \tanh(c_t)$$

The key line is \(c_t = f_t \odot c_{t-1} + i_t \odot \tilde c_t\). The cell state \(c_t\)’s connection to its past is linear:

$$\frac{\partial c_t}{\partial c_{t-1}} = \mathrm{diag}(f_t)$$

When the forget gate is open (\(f_t \approx 1\)), the gradient passes through unchanged — no \(\tanh'\) squeezing it toward zero at every step. This “constant error carousel” is why LSTMs genuinely learn longer dependencies than plain RNNs. The GRU gets the same effect with two gates and fewer parameters:

$$z_t = \sigma\big(W_z[h_{t-1},x_t]\big), \quad r_t = \sigma\big(W_r[h_{t-1},x_t]\big), \quad \tilde h_t = \tanh\big(W_h[r_t \odot h_{t-1},\, x_t]\big), \quad h_t = (1-z_t)\odot h_{t-1} + z_t \odot \tilde h_t$$

But notice what neither fix touches: the serial dependency. \(h_t\) still cannot exist before \(h_{t-1}\). That is Failure 1, and it is the one the 2017 paper kills.

3.4 The paper’s formal comparison — Table 1 with the arithmetic

Section 4 of the paper compares layer types on three axes. Let’s compute the numbers.

FLOP accounting. A matrix multiplication of shape \((m \times k) \cdot (k \times n)\) costs about \(2mnk\) floating-point operations (each output entry is a \(k\)-length dot product: \(k\) multiplications + \(k\) additions).

Recurrent layer. Each of the \(n\) steps multiplies \(h_{t-1}\) by \(W_{hh}\) \((d\times d)\) and \(x_t\) by \(W_{xh}\) \((d\times d_x)\): roughly \(2(d^2 + d\,d_x)\) FLOPs per step, so \(2n(d^2 + d\,d_x) = O(n\,d^2)\) per layer, executed in \(n\) sequential steps.

Self-attention layer (preview of Step 03). All \(n\) tokens are processed at once. Two big multiplications: scores \(QK^{\top}\), shape \((n\times d)\cdot(d\times n)\) costing \(2n^2 d\), and the value read-out, another \(2n^2 d\). Total \(O(n^2 d)\), executed in 1 sequential step.

The crossover. Comparing the two: \(n^2 d < n d^2 \iff n < d\). Attention is cheaper per layer whenever the sequence is shorter than the representation dimension — which held in 2017 (\(n=512 = d=512\), equal). Today the tables have turned: context lengths of 128k+ dwarf \(d\) of 4k–8k, and the quadratic term rules everything — which is precisely why Step 12 is a story about escaping \(n^2\).

Path length. The distance between any two tokens — the number of nonlinear layers a signal must cross, and hence the length of the gradient route — is \(O(n)\) in an RNN (token 1 must traverse \(n-1\) hidden states to influence token \(n\)), \(O(\log_k n)\) in a dilated convolution (each layer doubles the receptive field), and O(1) in self-attention: every pair is connected by a single operation.

layer type complexity per layer sequential ops max path length
self-attention O(n²·d) O(1) O(1)
recurrent O(n·d²) O(n) O(n)
convolutional O(k·n·d²) O(1) O(log_k n)
self-attention (restricted) O(r·n·d) O(1) O(n/r)

The bet. Pay \(O(n^2 d)\) per layer, get constant path length and total parallelism in return. Everything since 2017 — the KV cache, multi-query and grouped-query attention, flash attention, sparse and linear attention, state-space models — is the ongoing story of making that bet cheaper (Step 12).

4. Tokens: the vocabulary problem

A network reads integers, not text. The converter is a tokenizer: text → sequence of vocabulary ids.

4.1 Why subwords

Three candidate alphabets:

4.2 BPE — the algorithm and a complete worked example

Byte-pair encoding was invented by Philip Gage in 1994 as a data-compression algorithm. Sennrich et al. (2016) pointed it at NLP: treat the corpus as compressible data, merge frequent character pairs into subwords.

The algorithm, formally. Start with the character alphabet as vocabulary. Repeat until the vocabulary reaches the desired size \(V\): (1) count all adjacent symbol pairs in the corpus; (2) merge the most frequent pair \(a,b\) into a single new symbol \(ab\), everywhere in the corpus and in the vocabulary.

Worked example, complete. Corpus: low ×5, lower ×2, newest ×6, wider ×3. Initial vocabulary: d e i l n o r s t w </w> (11 symbols, </w> marking word end).

Merge 1 — count all pairs:

pair count pair count
w e 8 e r 5
l o 7 r 5
o w 7 w 5
n e 6 w i 3
e w 6 i d 3
e s 6 d e 3
s t 6
t 6

w e wins (8). Merge → new symbol we. Corpus becomes: low → l o w </w>, lower → l o we r </w>, newest → n e we s t </w>, wider → w i d e r </w>.

Merge 2 — recount. l o now stands at 7 (5 from low, 2 from lower); the old w e pairs are gone (absorbed into we). The top pair is l o (7). Merge → lo. Corpus: low → lo w </w>, lower → lo we r </w>, newest → n e we s t </w>.

Merge 3 — recount. Five pairs tie at 6 (n e, e we, we s, s t, t </w>); break the tie arbitrarily — merge s t → st. Corpus: newest → n e we st </w>.

Final vocabulary (14 symbols): d e i l n o r s t w we lo st </w>, and the corpus encodes as:

low → lo w </w> · lower → lo we r </w> · newest → n e we st </w> · wider → w i d e r </w>

flowchart TB
    T["Corpus: low(5), lower(2), newest(6), wider(3)"]
    V["Initial vocab: d,e,i,l,n,o,r,s,t,w,</w>"]
    M1["Merge 1: w+e → we (8 occurrences)"]
    M2["Merge 2: l+o → lo (7)"]
    M3["Merge 3: s+t → st (6)"]
    V2["Final vocab: d,e,i,l,n,o,r,s,t,w,we,lo,st,</w>"]
    EX["Encode: lowest → lo we st </w>"]
    DC["Decode: concatenate → lowest"]
    T --> V --> M1 --> M2 --> M3 --> V2
    V2 --> EX --> DC

Two properties make BPE the foundation of everything: generalization (the word lowest never appeared in the corpus, yet encodes as lo we st </w> — no unknown token needed) and perfect reversibility (decoding is concatenation, so the mapping is lossless).

Greedy is not optimal — and cannot be. BPE picks the locally best merge at each step. Is there a globally best tokenization? A 2025 ACL paper (“Tokenisation is NP-Complete”) proved the answer is no: finding a vocabulary that compresses the corpus to at most \(\delta\) symbols is NP-complete, by reduction from Max-2SAT. So BPE and its relatives are heuristics — and heuristics they will remain, until someone settles P vs. NP.

In the 2017 paper. BPE is run over the concatenated source and target corpora, producing one shared vocabulary of about 37,000 tokens for English–German and 32,000 for English–French. Sharing is what enables the weight-tying trick in Section 5.4.

4.3 The tokenizer family tree, through 2026

The implementations you would actually use are open source: Hugging Face’s tokenizers (Rust; trains BPE, WordPiece, Unigram) and OpenAI’s tiktoken.

4.4 Tokenization is not harmless

Because models think in tokens, their failures are famously un-human: early GPTs could not reliably count the letters in “strawberry” (a widely reported failure mode — tokens are not letters); arithmetic degrades because multi-digit numbers split unpredictably; spelling and reversal tasks break; and GPT-2’s tokenizer even contains anomalous tokens — byte sequences like SolidGoldMagikarp that got vocabulary ids but never appear in text, so the model has no coherent behavior for them. These are not quirks to laugh off: they are the price of the compression that subwords perform.

4.5 The token-free frontier (2021 → 2026)

The research program that questions the tokenizer entirely:

5. Embeddings: the lookup table

5.1 The lookup, as matrix math

Once text is ids, each id becomes a vector through one matrix: the embedding matrix \(E \in \mathbb{R}^{V \times d}\) — \(V\) rows (one per vocabulary token), \(d\) numbers each. In the 2017 paper \(d = 512\).

The operation is mathematically trivial and conceptually everything. Encode token \(i\) as a one-hot vector \(e_i \in \{0,1\}^V\) (a 1 in position \(i\), 0 elsewhere). Then:

$$e_i^{\top} E = \text{row } i \text{ of } E$$

A “lookup” is a one-hot matrix-vector product. There is no computation to learn inside this step — only the rows of \(E\) themselves are learned. That is what “the network learns embeddings” means.

A sentence of \(n\) tokens stacks into a matrix \(X \in \mathbb{R}^{n \times d}\); a batch of \(b\) sentences gives the tensor \((b, n, d)\). Sentences of different length are padded to a common \(n\), and a mask marks padding positions so attention ignores them.

flowchart LR
    TX["the cat sat"] --> TK["tokens: the | cat | sat"]
    TK --> ID["ids: 12 | 407 | 88"]
    ID --> E["E ∈ ℝ^(V×d) — look up rows 12, 407, 88"]
    E --> X["X ∈ ℝ^(n×d) — n row vectors of 512 numbers"]
    X --> NET["into the network"]

5.2 Where embeddings came from: word2vec and GloVe

The idea that meaning lives in vectors predates the Transformer by four years. word2vec (Mikolov et al., 2013) trains a shallow network on a game: predict a word from its context (CBOW) or the context from the word (skip-gram). For skip-gram, with input vector \(v_{w_I}\) and output vector \(v'_w\) for every word \(w\):

$$P(w_O \mid w_I) = \frac{\exp\big(v'_{w_O} \cdot v_{w_I}\big)}{\sum_{w \in V} \exp\big(v'_w \cdot v_{w_I}\big)}$$

— a softmax over the entire vocabulary, trained on enormous corpora (the paper reported billions of words per day on one machine, which is what made it famous as much as its quality). The sum over all \(V\) words is too expensive at scale, so practice uses hierarchical softmax or negative sampling (sample a few wrong words and train against only those). The representation learned is the input matrix’s rows.

flowchart LR
    subgraph SG["skip-gram"]
        W["target word"] --> C["predicts context words"]
    end
    subgraph CB["CBOW"]
        CC["context words"] --> TT["predicts the target"]
    end

Then the famous equation. Take the vector for king, subtract man, add woman — the nearest vector in the vocabulary is queen:

$$v_{\mathrm{king}} - v_{\mathrm{man}} + v_{\mathrm{woman}} \approx v_{\mathrm{queen}}$$

Formally: the difference vectors \(v_{\mathrm{king}} - v_{\mathrm{queen}}\) and \(v_{\mathrm{man}} - v_{\mathrm{woman}}\) are nearly parallel — the space has a direction that encodes gender, and more generally, relations are translations. The network was never told what gender is. GloVe (Pennington et al., 2014) produced the same phenomenon from a different source — factorizing word co-occurrence statistics — reaching 75% on analogy tests, proving the effect is a property of distributional statistics, not of one recipe. Meaning is geometry.

man woman king queen gender royalty
king − man + woman ≈ queen: both pairs differ by the same "royalty" vector. Relations are directions.

The critical difference in 2017. word2vec and GloVe embeddings were pre-trained separately, then frozen. The Transformer trains \(E\) from scratch, jointly with the whole network, so the vectors are shaped by and for the architecture that consumes them — and the rows of \(E\) end up capturing exactly the structure the rest of the network exploits. 2025 work (“Revisiting Word Embeddings in the LLM Era”) confirms the payoff: embeddings extracted from trained LLMs cluster semantically related words more tightly and score better on analogy tasks than classical word2vec/GloVe vectors.

5.3 Static, not contextual

One row per token means “bank” has exactly one vector, whether the sentence is about rivers or money. Everything upstream — the attention stack — is what disambiguates it. This static-then-contextual design still holds in every modern LLM: the embedding gives the token an identity; the layers give it a meaning in this sentence.

5.4 Two details of the 2017 paper, with the arithmetic

Weight tying (Section 3.4). The paper uses the same matrix for three jobs: input embeddings, output embeddings (decoder), and the pre-softmax linear layer. Untied, those are three \(V \times d\) matrices; tying saves \(2Vd\) parameters:

$$2 \cdot 37{,}000 \cdot 512 = 37{,}888{,}000 \approx 38\text{M} \text{ of the } 65\text{M total — about } 58\%.$$

It costs no accuracy, because a token’s meaning as input and as output should be the same object. GPT-2 and many successors keep the trick.

Scaling by √d (Section 3.4). Embedding rows are multiplied by \(\sqrt{d_{model}}\) on the way in. Here is the derivation of why that matters. Initialize embedding entries as independent zero-mean variables with variance \(\sigma^2\). The dot product of two embeddings has variance

$$\mathrm{Var}\big(u\cdot v\big) = \sum_{i=1}^{d} \mathrm{Var}(u_i v_i) = d\,\sigma^4 \qquad \Rightarrow \qquad \mathrm{std} = \sqrt{d}\,\sigma^2.$$

If embeddings were initialized at unit variance, their pairwise dot products would have standard deviation \(\sqrt{d}\) — growing without bound as models widen. The 2017 recipe initializes embeddings small and multiplies by \(\sqrt{d}\): e.g. entries uniform in \([-1/\sqrt{d},\, 1/\sqrt{d}]\) (variance \(1/(3d)\)) become, after scaling, variance \(1/3\) — order 1, the same scale as the sinusoidal positional encodings (whose values live in \([-1,1]\)) that get added to them in Step 02. Without the \(\sqrt{d}\) factor, the embeddings would be \(O(1/\sqrt{d})\) — so small that position information would swamp meaning entirely. A one-line fix that holds the whole input together.

5.5 Embeddings at modern scale (2026)

6. The input tensor and the order problem

A sentence of \(n\) tokens is the matrix \(X = [x_1; \dots; x_n] \in \mathbb{R}^{n \times d}\), each row one token’s embedding. The whole network is then one giant function: \((b,n,d)\) in, \((b,n,V)\)-shaped probability distributions out (Step 07).

Now the punchline that motivates Step 02, stated precisely. Let \(P\) be any permutation matrix. Attention computes pairwise dot products between rows and recombines them, so it is permutation equivariant:

$$\mathrm{Attention}(PX) = P \cdot \mathrm{Attention}(X)$$

— shuffle the rows in, and the outputs come out shuffled the same way. Without positional information, “dog bites man” and “man bites dog” are the same set of vectors fed to the network, and no stack of attention layers can tell them apart. The input is order-blind by construction. That gap — injecting position — is Step 02: the 2017 paper’s sinusoidal encodings and their modern replacement, RoPE.

flowchart TB
    subgraph ENC["Encoder × 6 (one block)"]
        direction TB
        SA["Multi-Head Self-Attention"] --> AN1["Add & Norm"]
        AN1 --> FF["Feed-Forward Network"]
        FF --> AN2["Add & Norm"]
    end
    IE["Input Embedding ×√d"] --> PE["+ Positional Encoding"]
    PE --> ENC
    OE["Output Embedding ×√d"] --> PE2["+ Positional Encoding"]
    PE2 --> DEC
    ENC -->|"K, V"| CROSS["Cross-Attention"]
    subgraph DEC["Decoder × 6 (one block)"]
        direction TB
        MA["Masked Self-Attention"] --> AN3["Add & Norm"]
        AN3 --> CROSS
        CROSS --> AN4["Add & Norm"]
        AN4 --> FF2["Feed-Forward Network"]
        FF2 --> AN5["Add & Norm"]
    end
    AN5 --> LIN["Linear"]
    LIN --> SM["Softmax"]
    SM --> OP["Output probabilities over V"]

7. Check yourself

  1. Why can a GPU not help an RNN the way it helps a Transformer? Which of the three failures is this?
  2. Write out the Jacobian \(\partial h_k / \partial h_{k-1}\) for an Elman RNN. Which factor in it is responsible for vanishing gradients?
  3. In the LSTM, which partial derivative has no \(\tanh'\) in it, and why does that matter?
  4. Clipping fixes exploding gradients. Why is there no equivalent fix for vanishing ones?
  5. Derive the crossover condition \(n < d\) between \(O(n^2 d)\) and \(O(n d^2)\). What does it imply about 2017 vs. 2026?
  6. Run one merge step of BPE on the corpus abab ×3, ab ×2. Which pair merges first, and what does the corpus look like after?
  7. Why is decoding BPE just concatenation — i.e., why is it lossless? And what did the 2025 NP-completeness result prove about “optimal” tokenization?
  8. Prove that \(e_i^{\top} E\) equals row \(i\) of \(E\).
  9. Compute the embedding-layer parameter count for GPT-2 (V = 50,257, d = 768) and its share of the 124M total.
  10. If embedding entries have variance \(\sigma^2\), what is the variance of a dot product between two embeddings? What does the \(\sqrt{d}\) scaling fix?
  11. Why does a byte-level tokenizer never need an UNK token?
  12. What does “permutation equivariant” mean, and why does it imply the Transformer cannot read word order without help?

8. Sources

Next: Step 02 — Positional encoding: the sinusoids, why they work, and why modern models replaced them with RoPE.