The weights are programmed
Query, key, value, and feed-forward matrices are set analytically to perform reads, writes, arithmetic, and branches. The central existence result does not train these weights from data.
The short version
The paper gives an explicit recipe for turning a small, frozen encoder Transformer into the equivalent of a programmable processor. The same Transformer block is applied repeatedly. Its input sequence is not prose: it is a carefully formatted array containing a scratchpad, mutable memory, machine instructions, and a program counter. One pass through the block executes one instruction; feeding the output back as the next input executes the next instruction.
The state is in the sequence
Instructions select operations; memory tokens hold variables; a scratchpad holds intermediate values. The model’s parameters stay fixed while the sequence changes.
The loop supplies time
A fixed set of layers is reused for as many machine cycles as needed. Unique network depth is constant, but sequential work still grows with the number of executed instructions.
Best one-sentence interpretation: this is a constructive proof that attention plus a feed-forward network, when given external recurrence and a rigid numerical encoding, can implement a stored-program computer.
What problem is the paper addressing?
Earlier theory had already shown that Transformers can be Turing complete or universal sequence-to-sequence approximators. Those results answer an expressivity question: can some Transformer represent arbitrary computation? They do not necessarily give an engineer a compact instruction set, a memory convention, or a way to compile an ordinary iterative algorithm into a shallow reusable network.
At the same time, work on in-context learning had shown both empirically and constructively that Transformers can behave like learning algorithms. Existing constructions often used a new layer for each optimization step. If ten gradient steps require ten copies of a block, architecture depth is tied to computation length.
Giannou and colleagues ask a more operational question: Can one fixed Transformer be designed as a reusable compute unit, with the program supplied in its input and repeated application supplying arbitrary computation time? Their answer is yes, under the paper’s formal model.
The proposed machine
The model is an encoder-style Transformer over a matrix X ∈ ℝ^(d×n). Columns are tokens; rows are features. It uses residual self-attention, a ReLU feed-forward block, and softmax attention. Unlike a production language model, it consumes structured numerical embeddings rather than natural-language tokens, uses full rather than causal attention, and is placed inside an explicit outer loop.
Xₜ₊₁ = TF(W; Xₜ), t = 0, …, T−1, with the same frozen W at every step.
The “punch card” layout
The sequence is partitioned into three column regions:
- Scratchpad (S): temporary workspace, including the current instruction, operands, intermediate results, and program counter.
- Memory (M): persistent variables that can be read and overwritten. Consecutive columns can encode vectors and matrices.
- Commands (C): the program. Each instruction stores addresses, a function selector, dimensions, a branch flag address, and a branch target.
Every location has a binary ±1 positional code. These codes are not merely descriptive position metadata: they act as machine addresses.
How attention becomes a read/write mechanism
1. Address matching by dot product
If location i has a ±1 binary address vector pᵢ of length log n, then pᵢᵀpᵢ = log n. Any different address pⱼ disagrees in at least one bit, so pᵢᵀpⱼ < log n. The authors choose query and key matrices so the intended address gets the largest attention score.
High-temperature softmax makes that score nearly one-hot. A value matrix then copies the chosen column into the scratchpad. Reversing the addressing pattern writes a scratchpad value to one selected memory column.
selector error ≲ exp(log n − λ), where λ is the softmax temperature
This is content-addressable memory built from attention. It is approximate because softmax never becomes an exact argmax at finite temperature. The paper bounds the error and, for the binary SUBLEQ construction, adds a ReLU error-correction step that snaps sufficiently small perturbations back to −1, 0, or +1.
2. The feed-forward network supplies logic
The ReLU block is wired to implement binary addition, two’s-complement negation, sign tests, masking, and selection. A one-hidden-layer ReLU network increments the binary program counter. Another block creates a branch flag and chooses between the branch target and the next sequential address.
3. Attention supplies more than lookup
Two technical constructions are especially useful later:
- Nonlinear functions: a softmax over a specially arranged pair of scores acts as a logistic sigmoid. Multiple heads encode different sigmoids, and their values form a weighted sum. Barron’s approximation theorem then covers a broad class of functions on bounded domains.
- Matrix multiplication: the authors choose a small scaling constant so
exp(cz) ≈ 1 + cz. After subtracting the constant component, attention scores expose dot products. A two-layer function block thereby approximates matrix products.
The division of labor: attention routes data and creates multiplicative interactions; the ReLU network performs discrete logic, masking, and local transformations; recurrence turns these spatial operations into a sequence of machine steps.
SUBLEQ: one instruction is enough
The first complete computer executes a restricted form of SUBLEQ, “subtract and branch if less than or equal to zero.” An instruction has three addresses:
SUBLEQ(a, b, c): mem[b] ← mem[b] − mem[a]; if mem[b] ≤ 0, jump to c; otherwise continue.
A tiny example
| Before | Subtraction | Control flow |
|---|---|---|
mem[a]=3, mem[b]=7, target c=42 | mem[b] ← 7−3 = 4 | 4 > 0, so advance to the next instruction. |
mem[a]=3, mem[b]=2, target c=42 | mem[b] ← 2−3 = −1 | −1 ≤ 0, so set the program counter to instruction 42. |
Subtraction plus conditional branching can synthesize ordinary arithmetic, loops, and control flow. The paper’s restricted variant keeps commands separate from memory. Appendix C argues that it remains Turing complete by compiling a Minsky register machine, itself a universal model, into sequences of these instructions.
One Transformer cycle
- Fetch: use the program-counter address to copy the current three-address instruction into the scratchpad.
- Read: two attention heads fetch
mem[a]andmem[b]. - Subtract: ReLU layers form two’s-complement negation and binary addition.
- Write: attention copies the result back to memory location
b. - Branch: test whether the result is nonpositive; select
cor increment the program counter. - Correct: remove small softmax-induced noise from the discrete representation.
- Halt: a special EOF instruction points back to itself and leaves memory unchanged.
Lemma 4: a looped Transformer with 10 layers, 2 heads, and width O(log n + log N) can run these programs, where n scales with program plus memory length and N is integer bit width.
A useful correction to some online summaries: the final ICML/PMLR paper says 10 layers for this SUBLEQ construction.
FLEQ: turning the minimal computer into a useful one
SUBLEQ proves universality, but expressing matrix multiplication as a long subtraction program would be unwieldy. The authors therefore introduce FLEQ, a flexible instruction that can call one of M built-in Transformer function blocks:
mem[c] ← fₘ(mem[a], mem[b]); if mem[flag] ≤ 0, jump to instruction p.
An instruction carries pointers to a, b, c, the selected block m, the branch flag, the target p, and dimensions for the operands. Function blocks share a standardized interface: inputs A and B occupy reserved scratchpad columns and output C=f(A,B) is written to another reserved region.
Main theorem: if the built-in blocks have depths
l₁,…,lₘ and head counts h₁,…,hₘ, one FLEQ executor uses 9 + max lᵢ layers, Σhᵢ heads, and width O(Md + log n). Applying it recurrently T times executes T instructions.
The constant-depth claim concerns the executor after its function library is fixed. Width grows with the number of functions and operand size; accuracy can require more heads or larger numerical parameters.
What the paper constructs
| Construction | Result | Important qualification |
|---|---|---|
| SUBLEQ computer | 10 layers, 2 heads | Integer bit width and program/memory length are explicit resources; universality assumes unbounded memory and cycles. |
| Calculator | 12 layers; addition, subtraction, multiplication, inverse, square root, percentage | Inverse and square-root are approximations on stated bounded domains; accuracy depends on head count. |
| Matrix inverse | 13 layers executing Newton–Raphson iterations | Approximation error can be reduced through softmax scaling; convergence still depends on the numerical algorithm’s assumptions. |
| Dominant eigenvector | 13 layers executing power iteration | The paper states T = O(log(1/ε)) iterations for its guarantee; ordinary power-iteration conditions still matter. |
| Linear-model SGD | 13 layers, 1 head | Runs repeated gradient updates over in-context data; each simulated step is approximate. |
| Two-layer-network training | 13 layers, 1 head | Implements forward computation, backpropagation, and SGD for a sigmoid-activated network. |
These are analytic constructions. The paper gives pseudocode, parameter recipes, and error arguments; it does not compare throughput, energy, or wall-clock speed with conventional numerical software.
Why the backpropagation result matters for in-context learning
In ordinary training, an optimizer changes the model’s parameters. Here, the Transformer’s own weights W remain frozen. The sequence contains a second model’s weights, biases, examples, labels, and learning rate as mutable data. The looped Transformer reads one example, computes gradients, and overwrites those stored weights. In that precise sense, learning occurs inside the forward execution.
Outer model
- 13-layer looped Transformer
- Hard-coded, frozen parameters
- Acts as interpreter/optimizer
Inner model
- Linear or two-layer sigmoid network
- Parameters stored in sequence memory
- Updated by simulated SGD
For the two-layer network, FLEQ instructions perform matrix transposes and products, sigmoid activations, output errors, hidden-layer errors, outer products, and parameter updates. A program loop moves through data points and epochs. The result generalizes earlier constructions that implemented one or a few steps of linear regression.
Do not overread this result. It proves that a specially programmed Transformer can execute backpropagation. It does not prove that GPT-style models learned this exact mechanism, that natural-language prompts compile to FLEQ, or that the construction explains all observed in-context learning.
What the result actually means
What is established
- A fixed set of Transformer layers can implement an instruction interpreter.
- Attention can perform address-based reads and writes, nonlinear approximation, and matrix products.
- External recurrence permits arbitrary-length programs without adding distinct layers for every step.
- The structured input can choose among programs while the executor weights remain unchanged.
- A learning algorithm, including backpropagation for a small neural net, can be represented as an in-context program.
What is not established
- That trained language models naturally discover these exact circuits.
- That this is an efficient replacement for a CPU, GPU, or numerical library.
- That computation takes constant time.
- That arbitrary natural-language code can be executed by the construction.
- That a finite Transformer literally has infinite memory or is an unrestricted physical Turing machine.
“Constant depth” unpacked
Suppose the executor has L layers and the program runs for T cycles. There are only L distinct parameterized layers, reused each time, but the unfolded computation has roughly L×T sequential layer applications. The paper itself says total complexity scales with the number of executed instructions, as standard complexity assumptions require.
unique parameter depth = L (constant); unfolded sequential depth ≈ L·T (grows with runtime)
The conceptual advance is weight sharing across computational time, not free computation. This is closer to a recurrent neural network, cellular automaton, or CPU clock cycle than to a fixed feed-forward circuit that answers in one pass.
“Programmable” unpacked
The same executor can run different instruction sequences placed in its input. That is genuine program/data separation at the level of the construction. FLEQ’s primitive operation library, however, is baked into the weights. A program may combine those primitives in new sequences, but adding a genuinely new primitive requires adding or changing a function block.
“Universal” unpacked
The universality route is conventional: SUBLEQ can simulate a universal register machine, and the looped Transformer can simulate SUBLEQ. Like other universality arguments, it is asymptotic. Unbounded computation requires unbounded cycles, sufficient address space and memory, and adequate numerical fidelity. Any fixed physical instantiation has finite resources.
Limitations and technical caveats
The paper’s Appendix A is unusually direct: efficiency was not experimentally validated; the Transformer implementation may be less efficient than running the algorithm directly; the separated command/memory layout can waste space; integration with pretrained models is unclear; and the finite-precision analysis is incomplete. Several additional qualifications follow from the theorems.
| Issue | Why it matters |
|---|---|
| Hand-coded weights | This is an existence and design result, not evidence that gradient descent will find the construction or that it is robust after training. |
| Nonstandard input | The model receives numerical columns with dedicated address, mask, and control fields. Ordinary text tokenization does not supply this representation. |
| Architecture mismatch | The construction uses an encoder-style, full-attention block with a specific residual/ReLU formulation and an explicit outer loop, not an off-the-shelf autoregressive decoder. |
| Softmax temperature | Near-discrete reads and writes rely on large score scales. The copy error decreases approximately like e^(log n−λ), so larger sequences or tighter tolerances demand larger numerical separation. |
| Approximation error | Nonlinear functions and matrix products are approximate. To keep total error below ε over T operations, the proof budgets about ε/T local error per operation. |
| Accuracy costs resources | Sigmoid-sum approximation improves with more heads; for broader activations or losses in the learning construction, the authors note that head count or dimension may need to grow polynomially, unless extra iterative computation is used. |
| Memory and program size still count | Sequence length grows with stored memory and instructions. Full attention would be quadratic in that length, although the authors note that their access pattern can be sparsified to O(nd) because only scratchpad columns need global attention. |
| Simplified SUBLEQ | The released implementation separates code and data and lacks convenient indirect addressing. Its README notes that list programs may grow linearly with list size even where self-modifying original SUBLEQ could keep code size constant. |
Practical bottom line: the construction is valuable as a microscope for Transformer expressivity and as a blueprint for neural interpreters. The paper does not make a case for replacing conventional computers with this implementation.
A useful way to read the paper
- Pages 1–3: read the motivation and the exact Transformer definition. Notice the outer recurrence and the use of vector embeddings rather than language tokens.
- Pages 3–5: understand the sequence layout and Lemmas 1–3. Binary addresses plus high-temperature attention are the central trick.
- Pages 5–7: follow one SUBLEQ cycle. This is the cleanest end-to-end example of the machine.
- Pages 7–9: read Theorem 1 and the application statements. Keep function-block depth separate from the fixed nine-layer control overhead.
- Appendices D–F: use these only if you want the exact FLEQ data layout and weight constructions.
- Appendix G: read this before making claims about exactness or long computations.
- Appendices H–J: trace the calculator, linear-algebra, and learning programs after the execution model is clear.
Three questions to keep in mind
- Which resources are fixed, and which scale with program length, data dimension, accuracy, or runtime?
- Is a claimed operation exact, error-corrected discrete computation, or a continuous approximation?
- Is the paper describing what a trained LLM does, or only what a purpose-built Transformer can represent?
Sources and further reading
Technical claims in this report were checked against the final PMLR paper. Secondary indexes were used for bibliographic context and to locate the current code repository.
- Giannou et al., “Looped Transformers as Programmable Computers”, final ICML 2023 paper (primary source).
- PMLR publication record, including abstract and citation metadata.
- arXiv record 2301.13196, submitted 30 January 2023.
- Official implementation repository, including SUBLEQ, factorial, list reversal, and linear search demonstrations.
- Official ICML presentation, 24 July 2023.
- Semantic Scholar record, for references and later citation context.
- Princeton institutional publication record.
The paper’s linked OpenReview forum was behind browser verification during research, so this report does not attribute any claim to reviewer comments. Citation counts were deliberately omitted from the analysis because they change over time.
Final assessment
The paper’s enduring idea is not that Transformers are secretly efficient CPUs. It is that the mechanics of attention can be reverse-engineered into an explicit instruction interpreter, and that recurrence lets a shallow, weight-tied network express long, stateful algorithms. That gives a concrete bridge between abstract Turing-completeness results and executable constructions, while leaving open the harder empirical question of whether trained language models learn comparable machinery.