Implicit Memory — RNN, LSTM, GRU

Fixed-size Hidden State · No External Access · O(1) per step

Overview

The Bottleneck. Standard RNNs compress all past history into a single fixed-dimension vector ht. This is "implicit" memory — the model has no way to address specific past events except by what survives the compression.

LSTMs. Use a dedicated cell state ct and gating mechanisms (Input, Forget, Output) to control the flow of information. While better at long-range dependencies than vanilla RNNs, they still fail at tasks requiring structured retrieval (like copying long strings).

Chomsky Hierarchy. RNNs are theoretically equivalent to Finite State Automata (Regular Languages). LSTMs can emulate counters (anbn), but struggle with full Context-Free or Context-Sensitive tasks because their memory cannot grow with input size.

One Forward Pass — LSTM

d_h=2 · forget / input / candidate / output gates
①
State at timestep t — three tensors entering the cell
Input xt
[0.3, −0.5]
Prev hidden ht−1
[0.2, 0.4]
Prev cell ct−1
[0.1, 0.6]
z = concat([ht−1, xt]) = [0.2, 0.4, 0.3, −0.5]  ← fed to all 4 gate networks
②
Four gate activations — three Sigmoid, one Tanh
Forget ft
σ(Wf·z) = σ([0.7, 0.8])
ft[0] = 0.67
ft[1] = 0.69
how much of ct−1 to keep
Input it
σ(Wi·z) = σ([0.4, 0.6])
it[0] = 0.60
it[1] = 0.65
how much new info to write
Candidate c̃t
tanh(Wc·z) = tanh([0.5, −0.3])
c̃t[0] = +0.46
c̃t[1] = −0.29
candidate new content, ∈ (−1, 1)
Output ot
σ(Wo·z) = σ([0.3, 0.5])
ot[0] = 0.57
ot[1] = 0.62
what fraction of ct to expose
③
Cell state update — the "conveyor belt" carrying long-range memory
ct = ft ⊙ ct−1 + it ⊙ c̃t
ct[0] = 0.67·0.1 + 0.60·(+0.46) = 0.067 + 0.276 = 0.343
ct[1] = 0.69·0.6 + 0.65·(−0.29) = 0.414 − 0.189 = 0.225
ct−1 [0.1, 0.6]
→
ct [0.343, 0.225]
If ft≈1 and it≈0, c passes through unchanged — the LSTM can preserve information over many steps. If ft≈0, old memory is erased and replaced by the new candidate.
④
Hidden state — gated cell readout exposed to the outside world
ht = ot ⊙ tanh(ct)
ht[0] = 0.57 · tanh(0.343) = 0.57 · 0.329 = 0.188
ht[1] = 0.62 · tanh(0.225) = 0.62 · 0.221 = 0.137
ht−1 [0.2, 0.4]
→
ht [0.188, 0.137]
ht feeds the prediction head AND recurs as input to the next step. ct is the internal highway; ht is the summary exposed to the outside.
⑤
Prediction head — linear readout from ht to next-token distribution
logits = Wout · ht + bout   Wout ∈ ℝ|Σ|×dh
logits = [0.24, 0.09, 0.16]   (|Σ|=3: a, b, c)
ŷt = softmax(logits) = [0.359, 0.309, 0.332]
loss = −log ŷt[y*]   y*=b → L = −log(0.309) = 1.174
a0.359
b  (true next)0.309
c0.332
sum = 1.000 · same Wout used at every timestep
Bottleneck: ht ∈ ℝ2 is the only information Wout sees — regardless of whether the sequence has 10 or 10,000 tokens. Long sequences compete for the same dh slots, which is why LSTMs fail at tasks requiring exact recall of distant tokens. External memory (stack, tape, matrix) breaks this ceiling.

Transformers — Attention as Memory

Fixed Context Window · Key-Value Retrieval · O(N²) Training

Overview

Soft Memory. Transformers treat the entire context window as a memory. Each token is a memory slot. Attention is the addressing mechanism.

Static vs Dynamic. Unlike NTM/DNC, Transformers do not write to their memory during a forward pass. The "memory" (KV cache) is just the representations of previous tokens. New information cannot be stored in old slots.

Computational Limits. While Transformers excel at Regular and some DCF tasks within their window, they cannot generalize to sequence lengths beyond what they were trained on (Position Encoding limit), unlike Stack-RNNs or Tapes which can theoretically grow.

One Forward Pass — Self-Attention

3-token sequence · d_k=d_v=4 · query token: "cat" (pos 1) attending to all
①
Context window as read-only memory — every token is a slot
pos token embedding x (d=4) role
0 the [0.1, 0.9, 0.2, 0.5] provides K[0], V[0]
1 cat [0.7, 0.3, 0.8, 0.4] ← query token this step
2 sat [0.5, 0.6, 0.1, 0.9] provides K[2], V[2]
Unlike NTM/DNC, this memory is read-only during a forward pass — no token can write into another's slot. The "memory" is the frozen set of input representations.
②
Project Q · K · V — three learned linear maps, d_k = d_v = 4
Query q (from "cat")
q = xcat WQ
[1.0, 0.0, 1.0, 0.0]
what "cat" is looking for
Keys K (all tokens)
kj = xj WK
kthe: [−0.8, 0.3, −0.8, 0.5]
kcat: [1.4, 0.2, 1.4, −0.3]
ksat: [0.6, 0.4, 0.6, 0.7]
what each token offers to match
Values V (all tokens)
vj = xj WV
vthe: [0.2, 0.4, 0.1, 0.5]
vcat: [0.9, 0.3, 0.7, 0.1]
vsat: [0.5, 0.8, 0.2, 0.6]
what each token contributes if selected
③
Attention scores — q · kj / √dk, scaled to prevent softmax saturation
score(cat→the) = q·kthe / √4 = −1.60 / 2.0 = −0.80
score(cat→cat) = q·kcat / √4 = +2.80 / 2.0 = +1.40  ← self-attention, highest
score(cat→sat) = q·ksat / √4 = +1.20 / 2.0 = +0.60
Division by √dk prevents dot products from growing large and pushing softmax into near-zero gradient (saturated) regions as d increases.
④
Softmax attention weights α — form a probability distribution over all tokens
α(cat→the): exp(−0.80)/Z = 0.449/6.33 = 0.071
α(cat→cat): exp(+1.40)/Z = 4.055/6.33 = 0.641 ← dominant
α(cat→sat): exp(+0.60)/Z = 1.822/6.33 = 0.288
Z = 0.449 + 4.055 + 1.822 = 6.326  ·  α sums to 1.0 by construction
⑤
Output — weighted value sum, then linear readout to next-token logits
ocat = Σ αj · vj
    = 0.071·vthe + 0.641·vcat + 0.288·vsat
o[0] = 0.071·0.2 + 0.641·0.9 + 0.288·0.5 = 0.735
o[1] = 0.071·0.4 + 0.641·0.3 + 0.288·0.8 = 0.451
o[2] = 0.071·0.1 + 0.641·0.7 + 0.288·0.2 = 0.513
o[3] = 0.071·0.5 + 0.641·0.1 + 0.288·0.6 = 0.272
Prediction head — W · o + b → softmax → next-token probability
ŷt = softmax(W · ocat + b)   W ∈ ℝ|Σ|×dv
logits = [0.82, 0.31, 0.55]   (|Σ|=3: the, cat, sat)
ŷt = [0.423, 0.254, 0.323]  ← prob over next token
loss = −log ŷt[y*]   y*=sat → L = −log(0.323) = 1.130
the0.423
cat0.254
sat  (true next)0.323
sum = 1.000 · causal mask prevents future leakage
Static memory: no token writes into another's V slot. Each position predicts the next token using only attended-to context — memory cannot grow with the task unlike stack/tape/NTM models.

Neural Execution Engine — Yan et al. (2020)

Algorithmic Primitives · Engine Selection · Soft Modular Execution

Overview

Yan 2020

Core idea. Learning to execute algorithms by factoring execution into a small set of primitive engines. Instead of learning a monolithic function, NEE trains a controller that selects and blends pre-specified operations — analogous to a CPU dispatching micro-ops from a fixed instruction set.

Engines. Each engine is a lightweight feedforward net (or learned linear map) that maps the current state to a new state for its specific operation — ADD, SWAP, INC-POINTER, COPY, etc. The engine set is designed by the researcher to match the algorithm family. The networks learn how to execute each primitive; the controller learns which primitive to apply when.

Controller. An LSTM reads the current state and emits a probability distribution over engines at each execution step. During the forward pass, all engines run in parallel and their outputs are blended by these probabilities. Gradient flows through every engine every step — even low-weight engines receive signal — which stabilises early training.

Sharpening toward discrete. The soft blend during training makes controller gradients dense. At test time the distribution can be sharpened (or converted to argmax) to recover an exactly discrete, interpretable program trace. This soft-to-hard curriculum is what allows NEE to generalise to longer sequences than seen during training.

Task fit. Best suited to tasks where the algorithm decomposes into a known fixed primitive set: multi-digit addition and multiplication, pointer-based sorting, and register-machine computation (Yan 2020). The number of execution steps T is fixed; algorithms that need more steps require either increasing T or hierarchically nesting engines within engines.

One Execution Step: Pointer-Based Arithmetic

State S = [A, B, P] · A,B=Registers, P=Pointer
①
Initial state — registers and pointer fed to controller
A = 10.0
B = 5.0
P = 0.0
# Goal: Accumulate & Move
②
All engines run in parallel — controller weights each output
Engine 1: ADD p=0.7
A' = A + B = 15.0
[15.0, 5.0, 0.0]
Engine 2: SWAP p=0.2
A',B' = B,A
[5.0, 10.0, 0.0]
Engine 3: INCP p=0.1
P' = P + 1.0
[10.0, 5.0, 1.0]
③
Soft modular blend — weighted sum of all engine outputs
Snew = 0.7·[15, 5, 0] + 0.2·[5, 10, 0] + 0.1·[10, 5, 1]
Snew = [10.5, 3.5, 0] + [1.0, 2.0, 0] + [1.0, 0.5, 0.1]
Next State St+1
[12.5, 6.0, 0.1]
Why this works: Even if the model isn't 100% sure between ADD and SWAP, the 12.5 result contains "mostly added" information. As training progresses, the distribution sharpens toward 1.0 for the correct operation, recovering the exact discrete algorithm.