Process vs outcome supervision
Two hand-written programs, one Transformer
Letter counting: we write the exact weights for a step-by-step solution and an all-at-once solution, in the same small network.
Running example on every slide: \(s_0 = 1,\ q = \mathtt{a},\ \text{word} = \mathtt{b\,a\,d\,a}\). Only basic linear algebra is needed. Every figure is computed live from the weights.
1 · Task
Count the query letter, mod \(m\)
Example \(m = 2\): start at \(s_0 = 1\) and add 1 at every a in b a d a, wrapping around at 2. The answer is \(s_4 = 1\).
| step \(t\) | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| letter \(w_t\) | b | a | d | a | |
| mark: is it a? | 0 | 1 | 0 | 1 | |
| state \(s_t\) | 1 | 1 | 0 | 0 | 1 |
In general \(s_t = (s_{t-1} + [w_t = q]) \bmod m\), where \([w_t = q]\) is 1 if the letter equals the query and 0 otherwise.
- Process supervision: the model is trained to write every state \(s_1, \dots, s_4\), then the answer.
- Outcome supervision: the model is trained to write only the answer \(s_4\).
2 · The two programs in words
Step by step vs all at once
- Process (top row): write \(1, 0, 0, 1\). Each new state needs only the previous state and one mark: \(s_4 = (0 + 1) \bmod 2 = 1\).
- Outcome (bottom row): write only the answer. It must count all the marks at once: \(c = 2\), so \((1 + 2) \bmod 2 = 1\).
- Both get the same prompt and the same network. We write the exact weights for each by hand.
3 · Toolkit
Three facts from linear algebra
Every weight in this deck is built from these three facts.
1. One-hot vectors. Letter c of a, b, c, d is \(e_{\mathtt c} = (0, 0, 1, 0)\). Dot products test equality: \(e_i \cdot e_j = [i = j]\), i.e. 1 if equal and 0 if not.
2. ReLU makes an AND gate. \(\mathrm{ReLU}(x) = \max(0, x)\). For bits \(x, y \in \{0, 1\}\):
\[ 2\,\mathrm{ReLU}(x + y - 1.5) = \begin{cases} 2 \cdot 0.5 = 1 & x = y = 1 \\ 0 & \text{otherwise (the sum is } \le -0.5) \end{cases} \]
3. Softmax with one big score picks one entry. \(\mathrm{softmax}(z)_j = e^{z_j} / \sum_k e^{z_k}\):
\[ \mathrm{softmax}(16, 0, 0, 0) \approx (0.9999997,\ 10^{-7},\ 10^{-7},\ 10^{-7}), \qquad \mathrm{softmax}(16, 16, 0, 0) \approx (\tfrac12, \tfrac12, 0, 0) \]
One winner gives a lookup of one row. Several tied winners give their average.
4 · Sizes
Symbols and sizes
| Symbol | Meaning | Example | Default run |
|---|---|---|---|
| \(A\) | number of letters (a, b, c, d) | 4 | 4 |
| \(n\) | word length = number of steps | 4 | 12 |
| \(m\) | modulus, states are \(0, \dots, m{-}1\) | 2 | 2 |
| \(q,\ s_0\) | query letter, start state | a, 1 | random |
| \(|\mathcal V| = A + m + 3\) | token types: letters, state values, SEP, :, EOS | 9 | 9 |
| \(P = 2n + 6\) | longest row of tokens | 14 | 30 |
| \(W = 2A + 4m + 2n + 9\) | length of each token's vector | 33 | 49 |
| \(F = \max\{A,\ 3m(n{+}1),\ 2n{+}1\}\) | number of ReLU units per MLP | 30 | 78 |
5 · The network
A table of vectors, updated twice
Example The process row has \(T = 14\) tokens, so the state of the network is a \(14 \times 33\) matrix \(X\). Row \(i\) is the vector for token \(i\).
\(X = E_{\mathrm{tok}}[\mathrm{ids}] + E_{\mathrm{pos}}[0{:}T]\)start: which token + where
\(S_h = (X W^{Q\top}_h)(X W^{K\top}_h)^{\top} / \sqrt{P}\)how much row \(i\) wants row \(j\)
\(X \mathrel{+}= \sum_{h} \mathrm{softmax}(S_h)\, X W^{V\top}_h\)attention: copy from other rows
\(X \mathrel{+}= \mathrm{ReLU}(X W_{\mathrm{in}}^{\top} + b)\, W_{\mathrm{out}}^{\top}\)MLP: same function on each row
\(\mathrm{logits} = X R^{\top}\)readout: score each next token
- Attention + MLP is one block. There are 2 blocks.
- Each block has 3 heads, i.e. 3 independent copy operations \(h\).
- A row may only read rows at or before it (causal mask).
| Matrix | Shape | Example |
|---|---|---|
| \(E_{\mathrm{tok}}, R\) | \(|\mathcal V| \times W\) | 9 × 33 |
| \(E_{\mathrm{pos}}\) | \(P \times W\) | 14 × 33 |
| \(W^Q_h, W^K_h\) | \(P \times W\) | 14 × 33 |
| \(W^V_h\) | \(W \times W\) | 33 × 33 |
| \(W_{\mathrm{in}}, W_{\mathrm{out}}^{\top}\) | \(F \times W\) | 30 × 33 |
| Parameters | 17,154 |
6 · Inside each row
Each vector is split into named slots
Example The row for the letter a at position 3 starts as \(e_{\mathtt a}\) in TL and \(e_3\) in POS. Block 0 then writes \(e_{\mathtt a}\) into QRY and 1 into MATCH.
| TL | the letter, one-hot | PREV | previous state \(s_{t-1}\) |
| TV | a state value, one-hot | MT | copy of the mark (process) |
| POS | the position, one-hot | CNT | the count \(c\) (outcome) |
| QRY | copy of the query \(q\) | S0 | start state \(s_0\) (outcome) |
| MATCH | the mark \([w_t = q]\) | OUT | the value to print |
In general Every slot has a single job. Attention weights are identity blocks that copy one slot into another; the MLPs hold the small AND gates.
7 · Who writes each slot
Given by the tokens vs written by the network
| Slot | Written by | Which rows |
|---|---|---|
| TL, TV, POS | input: \(E_{\mathrm{tok}}[\mathrm{ids}] + E_{\mathrm{pos}}\) | TL at letters, TV at state tokens, POS everywhere |
| QRY | block 0, head 0 | letters \(w_1..w_n\) |
| MATCH | block 0, MLP | letters equal to \(q\) |
| PREV, MT | process block 1, heads 0, 1 | rows that predict \(s_t\) |
| CNT, S0 | outcome block 1, heads 0, 1 | the row that predicts \(s_n\) |
| OUT | block 1 MLP (process head 2 for the copy) | rows that predict a state |
- TV is never computed. It is part of the input: the one-hot value of a state token.
- Row 0 holds \(s_0\), from the prompt.
- Process: rows \(s_1..s_n\) are tokens the model printed in earlier passes, fed back. Their TV is the model's own output, not a new slot.
- Outcome: no such rows. TV is set only at \(s_0\) and the final answer.
- Every other slot starts at 0 and is filled by one hand-written head or MLP.
- The map is free run: row \(i\) only sees rows \(\le i\), so one pass over the generated row gives the same rows as pass-by-pass generation. EOS is greyed out because no pass computes it.
8 · Inference
At inference: one token at a time
9 · Process program, every matrix
Producing row 8: every matrix
10 · Outcome program, every matrix
Producing row 8, outcome weights
11 · Playground
Run both programs
Change the query, start state or letters. Both programs should match the correct row for every input.
- The matrix \(X\): rows = tokens, columns = slots
- Blue \(\gt 0\), red \(\lt 0\); hover for values
12 · Summary
Same answer, very different programs
| Process | Outcome | |
|---|---|---|
| Embeddings + block 0 | identical weights (0 entries differ) | |
| Block 1 + readout | different weights (readout: just 4 entries, for ':' and EOS) | |
| Marks read per output | 1 | all \(n\) |
| Block-1 heads used | 3 | 2 |
| Block-1 ReLU units | \(2m\) (example: 4) | \(3m(n{+}1)\) (example: 30) |
| Grows with \(n\)? | no | yes |
| Supervised tokens | \(n + 3\) | 3 |
- Both programs are exact and live in the same network.
- Process: a small rule applied \(n\) times. Outcome: one large lookup over every possible count.
- Next: train one random starting point under each loss and compare it with these two programs.
Appendix
Each part as a picture
The same computations as slides 8–9, drawn as token diagrams instead of matrices.
A1 · Attention
Each head looks up one row
Example Head "Proc h1": row 9 (holding \(s_3 = 0\)) needs the mark of \(w_4\), stored at row 5. The heatmap shows a dark cell at (9, 5).
Key of row \(j\): \(k_j = e_j\), its position one-hot
Query of row 9: \(q_{9} \propto e_5\), the row it wants
Score \(q_{9} \cdot k_j = 16\) if \(j = 5\), else 0
- By fact 3, softmax puts weight \(\gt 0.99999\) on row 5
- The value matrix copies one slot, e.g. MATCH of row 5 into MT of row 9
- Click the buttons to see the other heads
A2 · Block 0 (same for both)
Mark each letter: is it \(q\)?
Example Every letter copies the query a from row 1, then compares: b a d a \(\to\) marks 0 1 0 1.
In general Attention copies \(e_q\) into QRY; the MLP computes \(\mathrm{MATCH} = e_{w_t} \cdot e_q = [w_t = q]\) using AND gates (fact 2).
A3 · Block 0 · inside the MLP
One AND gate per letter
Example At \(w_2 = \mathtt a\): gate a sees TL\(_{\mathtt a} = 1\), QRY\(_{\mathtt a} = 1\), so \(2\,\mathrm{ReLU}(1 + 1 - 1.5) = 1\). At \(w_1 = \mathtt b\): gate b sees \(1 + 0\), so 0.
\[
\mathrm{MATCH} \mathrel{+}= \sum_{a \in \{\mathtt{a,b,c,d}\}} 2\,\mathrm{ReLU}\big(\mathrm{TL}_a + \mathrm{QRY}_a - 1.5\big)
\]
| \(\mathrm{TL}_a\) | \(\mathrm{QRY}_a\) | inside ReLU | output |
|---|---|---|---|
| 1 | 1 | \(+0.5\) | 1 |
| 1 | 0 | \(-0.5\) | 0 |
| 0 | 1 | \(-0.5\) | 0 |
| 0 | 0 | \(-1.5\) | 0 |
- In general only gate \(a = w_t = q\) can fire
- Weights: \(W_{\mathrm{in}}\) has 1 on TL\(_a\) and QRY\(_a\), bias \(-1.5\), \(W_{\mathrm{out}} = 2\)
A4 · Process · block 1
Each step: last state + one mark
Example \(t = 4\): head 0 fetches \(s_3 = 0\), head 1 fetches the mark of \(w_4 = \mathtt a\) (= 1). The MLP outputs \(s_4 = (0 + 1) \bmod 2 = 1\). Step through \(t\) below.
In general Two lookups (\(s_{t-1}\) and one mark), then \(2m\) ReLU units compute \(s_t\). The work per step is the same for any word length \(n\).
A5 · Process · inside the MLP
Two AND gates per state value
Example PREV \(= e_0\), MT \(= 1\). The gate "was 0 and match" gives \(\mathrm{ReLU}(1 + 1 - 1.5) = 0.5\) and writes to OUT\(_1\). Every other gate is 0.
\[
\underbrace{\mathrm{ReLU}(\mathrm{PREV}_j - \mathrm{MT} - 0.5)}_{\text{was } j \text{ and no match}} \to \mathrm{OUT}_j,
\qquad
\underbrace{\mathrm{ReLU}(\mathrm{PREV}_j + \mathrm{MT} - 1.5)}_{\text{was } j \text{ and match}} \to \mathrm{OUT}_{(j+1) \bmod m}
\]
| \(\mathrm{PREV}_j\) | MT | no-match gate | match gate | writes |
|---|---|---|---|---|
| 1 | 0 | 0.5 | 0 | \(\mathrm{OUT}_j\) |
| 1 | 1 | 0 | 0.5 | \(\mathrm{OUT}_{j+1}\) |
| 0 | 0 or 1 | 0 | 0 | nothing |
- In general exactly one gate fires; \(W_{\mathrm{out}} = 2\) turns 0.5 into 1
- \(\Rightarrow \mathrm{OUT} = e_{s_t}\), and the readout prints \(s_t\)
A6 · Outcome · block 1
One row reads all \(n\) marks at once
Example At ':', head 0 gives all four letters equal weight \(\tfrac14\) (fact 3, tied scores). The average mark is \(\tfrac24\); times 4 gives \(c = 2\). Head 1 fetches \(s_0 = 1\).
In general The MLP must turn \((s_0, c)\) into \((s_0 + c) \bmod m\). It keeps one detector for every pair, \(c = 0, \dots, n\): \(3m(n{+}1)\) units, growing with \(n\).
A7 · Outcome · inside the MLP
A spike detector for each count
Example \(c = 2\). Detector \(c' = 2\): \(r(1) - 2r(0) + r(-1) = 1\). Detector \(c' = 1\): \(r(2) - 2r(1) + r(0) = 2 - 2 + 0 = 0\). Here \(r = \mathrm{ReLU}\).
\[
\beta_{c'}(x) = r(x{-}c'{+}1) - 2\,r(x{-}c') + r(x{-}c'{-}1) = \begin{cases} 1 & x = c' \\ 0 & \text{any other whole number } x \end{cases}
\]
| count \(x\) | \(r(x{-}c'{+}1)\) | \(r(x{-}c')\) | \(r(x{-}c'{-}1)\) | \(\beta_{c'}\) |
|---|---|---|---|---|
| below \(c'\) | 0 | 0 | 0 | 0 |
| \(c'\) | 1 | 0 | 0 | 1 |
| \(c'{+}d\), \(d \ge 1\) | \(d{+}1\) | \(d\) | \(d{-}1\) | 0 |
- In general 3 ReLUs make one spike, one spike per \((s_0, c')\)
- A large negative bias switches off every \(s_0\) group but the true one
- Spike \((s_0, c)\) writes OUT\(_{(s_0 + c) \bmod m} \Rightarrow\) prints \(s_n\)