Looped Transformers as Programmable Computers

Motivation

• The paper targets a gap between general transformer computational constructions and practical methods for creating models that execute particular algorithms or compile higher-level programs.Prior work established Turing-machine simulation, while specialized languages and in-context optimization methods remained program- or iteration-dependent.Source: §1 · p. 2

Architecture

• Hardcoded weights and a single input-output loop let transformers emulate edit operations, nonlinear functions, function calls, program counters, and conditional branches without requiring deep models.The loop feeds the output sequence back as the next input, enabling iterative state updates and complex computations.Source: §1 · p. 2, Figure 1 · p. 3

Instruction set

• A looped transformer executes FLEQ, a flexible single-instruction language whose instruction functions can include matrix multiplication, nonlinear functions, and polynomials.Its depth depends on implementing one FLEQ instruction rather than on program length, because execution proceeds in CPU-like cycles.Source: §1 · p. 3

Demonstrated programs

• The framework demonstrates transformer programs for a basic calculator, matrix transpose, multiplication, inversion, power iteration, and backpropagation-based in-context learning.The prompt serves as a punchcard containing instructions, memory, and workspace for program variables.Source: §1 · p. 3

Scope

• All demonstrated transformers use at most thirteen layers, including a model that emulates a general-purpose computer, numerical linear algebra methods, and SGD on neural networks.The informal theorem summarizes these capabilities as achievable by a looped transformer with fewer than 13 layers.Source: §1 · p. 3

Implications

• The constructions show that attention and even one recursive loop can support complex iterative algorithms and general program execution, while remaining distinct from how real-world language models are trained.The authors present the framework as a tool for studying minimal network sizes and improving algorithmic capabilities in language models.Source: §1 · p. 4

Computational expressivity

• Transformers have been shown to be Turing complete or universal sequence-to-sequence approximators, although constructions commonly require high or infinite precision, recursion, or sufficient width and depth [Pérez et al., 2021, Pérez et al., 2019, Wei et al., 2022a; Yun et al., 2019].Wei et al. [2022a] is identified as an exception to the high/infinite-precision requirement.Source: §2 · p. 4

Programmable Transformers

• RASP and its Tracr compiler provide programmable Transformer-encoder abstractions, but prior work discusses limitations and unclear Turing completeness that this framework addresses [Weiss et al., 2021; Lindner et al., 2023; Merrill et al., 2022].The present approach demonstrates arbitrary nonlinear functions and iterative, non-linear algorithms while avoiding depth proportional to executed code length.Source: §2 · pp. 4–5

In-context learning

• Experimental studies show that Transformers can learn in-context linear and nonlinear models in embedding space, while related constructions connect in-context learning to SGD and gradient-based meta-learning [Garg et al., 2022; Akyürek et al., 2022; von Oswald et al., 2022].These works report performance matching or exceeding task-specific algorithms, predictors closely matching SGD, and similarities between gradient descent and linear-attention Transformers.Source: §2 · p. 5

Algorithmic reasoning

• Shallow Transformers can exploit shortcut solutions to replicate certain finite automata with fewer layers than reasoning steps, but general shortcut existence would imply an unlikely collapse of complexity classes [Liu et al., 2022].The shortcut solutions were shown to be learnable through standard training methods.Source: §2 · p. 5

Recursive architectures

• Related recursive Transformer architectures use recursion similarly, whereas this work uses only a single recursive link feeding the Transformer’s output back as input [Hutchins et al., 2022, Shen et al., 2022, Dehghani et al., 2018].This positions the framework among prior recursive constructions while distinguishing its specific recursion mechanism.Source: §2 · p. 5

The transformer architecture

• Inputs are sequences of n d-dimensional token embeddings, with tokens and matrix columns used interchangeably.An embedding layer can map discrete tokens into the required vector constructions.Source: §3 · pp. 5–6
• A transformer layer combines an attention operation with a ReLU layer, using key, query, and value matrices across attention heads.The attention softmax is applied over input columns, with λ ≥ 0 controlling temperature.Source: §3 · p. 6

Iterative computation through a simple loop

• Looped Transformers iteratively feed a multilayer transformer’s output back as its input for fixed-point-like computation.The input sequence contains instructions and memory, paralleling repeated read/write processing in conventional computers without requiring the CPU analogy to hold.Source: §3 · pp. 6–7

Input sequence format

• The input format separates a scratchpad, memory, and commands, with positional encodings serving as pointers to data and instructions.Data is copied from memory to the scratchpad for transformation and returned to memory, while commands specify locations and operations.Source: §3 · p. 7

4 Building Transformer Blocks towards General Computation

• Transformer blocks provide interoperable operations for assembling general-computation routines, including sequence edits, program-counter tracking, conditional jumps, and approximate function computation.Figure 2 summarizes three core blocks: input-sequence edits, program-counter maintenance, and condition-dependent jumps.Source: §4 · p. 8, Figure 2 · p. 8

4.1 Positional Encodings, Program Counter, and Data Pointers

• Binary positional encodings appended to tokens enable logarithmic-dimensional location tracking, program-counter increments, and data pointers for reading and writing.A one-hidden-layer ReLU network with 8d hidden activations and d outputs can add two d-dimensional binary integers when the sum is below 2d+1.Source: §4.1 · pp. 8–9

4.2 read / write: Copying Data/Instructions to/from the Scratchpad

• Single-layer, single-head transformers of width O(log n + d) can transfer pointed-to commands or data between input memory and a scratchpad.The scratchpad stores information for computation, while positional encodings designate source and destination locations for read and write operations.Source: §4.2 · pp. 9, 12, Figure 3 · p. 9, Figure 4 · p. 12

4.3 if ⟨condition⟩then goto ⟨instruction⟩: Conditional branching

• Conditional branching evaluates whether mem[a] ≤0 and either jumps the program counter to a specified instruction or increments it by one.The complete operation requires three feedforward layers of Eq. (1b), hence two transformer layers, with the attention value matrix set to zero.Source: §4.3 · pp. 13–14

5.1 A SUBLEQ Transformer

• SUBLEQ subtracts one memory value from another, stores the result, and branches to a specified instruction when the result is non-positive; with infinite memory, it is Turing complete.The construction uses a restricted variant that separates memory/registers from instructions and is also proved Turing complete.Source: §5.1 · p. 14
• The SUBLEQ transformer represents instructions and memory in the input, tracks a program counter, and uses scratchpad read/write and conditional-branch operations to execute instructions sequentially.The loop is crucial because it maintains execution state without requiring transformer depth to scale with program length.Source: §5.1 · pp. 14–15
• A nine-layer, two-head looped transformer can execute SUBLEQ programs with width O(log(n)+N), where n scales with program and memory length and N stores integer bits.The represented integers lie in the range [−2^N−1 + 1, 2^N−1 −1].Source: §5.1 · p. 15
• The construction reads an instruction and its operand data, computes mem[b]−mem[a] using bit operations and ReLU layers in three transformer layers, writes the result back in one layer, and corrects softmax read/write errors.With temperature high enough that read/write error is at most ϵ < 0.5, a noisy bit can be fixed by ReLU error correction.Source: §5.1 · pp. 16–19

5.2 FLEQ: A More Flexible Attention-based Computer

• FLEQ combines selectable transformer-based functions with conditional branching, enabling instructions of the form mem[c] = f_m(mem[a], mem[b]) and conditional jumps.The function set can include matrix multiplication, square roots, activation functions, and other nonlinear or iterative computations.Source: §5.2 · pp. 19–20
• The unified FLEQ computer has 9 + max{l_1, · · · , l_M} layers, Σ_i h_i heads, and dimensionality O(Md + log n), and recurrently executes arbitrary programs of FLEQ instructions.The design reserves separate blocks for each predefined function, which simplifies construction but may be inefficient; a single shared block is considered feasible but more complicated.Source: §5.2 · pp. 20–21
• FLEQ generalizes the OISC design by allocating function blocks in the scratchpad and executing one selected function per recurrent instruction over scalar, vector, or matrix inputs.Each instruction points to input locations, an output location, a function block, dimensions, a branch flag, and a jump target.Source: §5.2 · pp. 20–22
• FLEQ instructions can be decomposed into independent function-call and branch components, yielding a unified computer whose commands can separately execute a function or jump conditionally.Fixed memory locations encode unconditional function execution or conditional branching as simplified instruction forms.Source: §5.2 · p. 22
• FLEQ stores inputs A and B in separate column regions, places output C in a third region, and reserves remaining columns as scratchpad.Each input and output occupies the first d_h rows, while unused columns are zeroed.Source: §5.2 · p. 23
• The scratchpad provides s − 3d columns for intermediate calculations while the designated input and output regions preserve the function-block interface.The construction uses zero padding for inputs and leaves unused columns set to zero.Source: §5.2 · p. 23
• The final r − d_h rows are unrestricted and can store auxiliary information such as additional positional encodings.These rows are available to the transformer-based function block beyond the rows holding the matrix data.Source: §5.2 · p. 23
• The same layout supports matrix–vector multiplication, with A and b placed into their respective input regions and the product represented in the output region.The passage illustrates the layout for multiplying A ∈ R^(d×d) by b ∈ R^(d×1).Source: §5.2 · p. 23
• Only scratchpad columns require global attention in the construction, because most input embeddings need attend to only a few other embeddings.This sparsity motivates restricting attention rather than applying full attention across all columns.Source: §5.2 · p. 23
• Restricting attention to scratchpad columns reduces complexity from O(n^2d) to O(nd), making computation linear rather than quadratic in the number of input sequences.The stated reduction improves efficiency and enables scaling to larger input sequences.Source: §5.2 · p. 23

6 Functions in the Unified Template Form

• The unified template organizes transformer-based function blocks through shared input/output locations, with positional encodings supporting output transfer and read/write operations.These blocks provide components for iterative algorithms developed later.Source: §6 · p. 24

6.1 Encoding Non-linear Functions within the Attention Mechanism

• Attention encodes nonlinear functions by making softmax act as sigmoid and storing multiple coefficients in query and value matrices.An input indicator selects among linear combinations of sigmoids approximating different functions, building on Barron [1993].Source: §6.1 · pp. 24–25
• A 3-layer, m-head transformer block with dimensionality r = 2 log(d) + d + 1 = O(d) approximates arbitrary g ∈ΓC,B selected by an indicator vector.The construction uses no extra scratchpad space beyond s = 3d, with zero-padding available when later blocks require more space.Source: §6.1 · p. 25

6.2 Matrix Transposition and Multiplication by Linearizing the Softmax

• Matrix transposition vectorizes A and applies a fixed column permutation, producing A′ = A⊤ + ϵM with ∥M∥≤1.The approximation error depends on the softmax temperature λ through read/write operations.Source: §6.2 · pp. 25–26
• For any ϵ > 0, a 2-layer, 1-head transformer block with dimensionality r = O(d) computes A⊤B + ϵM for ∥M∥≤1.The construction linearizes softmax using a large constant C, which controls the error ϵ, and yields related products as corollaries.Source: §6.2 · p. 26

6.3 Advantage of attention over fully-connected networks

• Attention can implement x2 in essentially 2 layers, whereas ReLU networks require depth proportional to log(1/ϵ) for comparable approximation quality.The paper supplies hardcoded attention layers, turning these existence results into practical constructions.Source: §6.3 · p. 26

• A 12-layer, m-head transformer of dimensionality O(log n) implements addition, subtraction, multiplication, inversion, square root, and percentage.Inversion and square root require specified operand ranges and achieve errors O(1/√m) and O(1/m), respectively.Source: §7 · p. 27
• Addition and subtraction each require a 3-layer, 1-head, O(1)-dimensionality function block.These blocks implement f(a, b) = a + b and f(a, b) = a − b.Source: §7 · pp. 27–28
• A transformer-based function block can implement multiplication, f(a, b) = ab, using 2 layers, 1 head, and dimensionality O(d).Source: §7 · p. 28
• Inversion and square root each use 3-layer, m-head blocks, with errors ˜O(1/√m) and O(1/m) over their stated operand ranges.Division follows by combining multiplication with inversion.Source: §7 · p. 29
• Additional calculator functions can be implemented either by sigmoid approximation or iterative numerical updates y_k+1 = g(y_k) until a tolerance ϵ is reached.The proposed extensions include algebraic and trigonometric functions.Source: §7 · p. 29

Linear algebra using Transformers

• For transposing a 30 × 30 matrix, the construction uses 1 layer, 1 head, and width 168, versus Charton [2021]’s 1 layer, 8 heads, and width 256.The comparison assumes the matrix is provided in transposed form for the fixed-permutation implementation.Source: §8 · p. 30

Matrix Inversion

• Newton’s inversion program initializes X−T = ϵA and repeatedly updates Xi+1 = Xi(2I − AXi) until the loop counter terminates.The update is assembled from multiplication, subtraction, transpose, memory, and conditional-branch instructions.Source: §8 · pp. 30–31
• A 13-layer, 1-head transformer with dimensionality r = O(d) emulates Newton’s matrix-inversion algorithm for any ϵ > 0.The program uses multiplication, subtraction, and transpose blocks within the Unified Attention Based Computer.Source: §8 · p. 30

Power Iteration

• A 13-layer, 1-head transformer with dimensionality r = O(d) emulates Power Iteration for T = O(log 1/ϵ) iterations.The construction normalizes the iterated vector using Newton’s quadratically convergent inverse-square-root algorithm.Source: §8 · pp. 31–32

Scope

• The examples are proof of concept for small transformer-based linear-algebra libraries, whose looped transformer size remains constant with algorithmic depth.The architecture could incorporate additional functions for QR decomposition, Gauss-Seidel, Arnoldi iteration, or Lanczos, though these are not implemented here.Source: §8 · pp. 31–32

Contribution

• The work demonstrates in-context learning across a wider range of models than single-call approaches, while iterative programs such as SGD require looping or transformer size that grows with program depth.The authors state this is the first demonstration of transformer-based SGD beyond linear regression and more general loss functions and models.Source: §9 · p. 33

Stochastic Gradient Descent in linear models

• A 13-layer, 1-head transformer implements T iterations of SGD for linear models over D data points with error up to ϵ.The step size is supplied as a program parameter, and pointer-based instructions cycle through data points and epochs.Source: §9 · pp. 33–34

Backpropagation and SGD

• Arbitrary loss functions introduce approximation error and generally require poly(TD) heads, whereas derivatives expressed as sums of sigmoids need only one head per sigmoid and add no such error.Different activation functions can likewise be represented as sums of sigmoids, with poly(TD) heads needed to control approximation error.Source: §9 · pp. 33, 35
• The framework extends linear-model SGD to two-layer neural networks with sigmoid activation by repeatedly calling a backpropagation function to update weights and biases.The algorithm computes forward activations, output and hidden-layer errors, gradients, and parameter updates for each data point.Source: §9 · pp. 34–36
• A 13-layer, 1-head transformer implements T iterations of SGD for two-layer neural networks with error up to ϵ and input-provided step size.The construction uses dimensionality O(log(D) + d) and operates over D data points.Source: §9 · p. 35

Generalizing to arbitrary depth

• Generalizing backpropagation to networks of arbitrary depth makes transformer looping cost proportional to network depth, increasing computational cost as depth grows.The code length scales with the number of network layers because each algorithm line corresponds to one transformer cycle.Source: §9 · p. 37

Contributions

• Constant-depth looped transformers can emulate computing blocks, a one-instruction set computer, and programs for calculators, linear algebra, and full backpropagation-based in-context learning.The constructions use programmed weights and a single loop to execute iterative algorithms.Source: §10 · pp. 37–38

Implications

• Attention enables looped transformers to mimic complex iterative algorithms and execute general programs, suggesting natural-language commands could serve as a programming language for programmable computers.The paper relates this capability to possible internal subroutines in advanced models such as GPT-3 when given examples and instructions.Source: §10 · p. 38

Open Problems

• Open problems include fusing hardcoded models with larger pretrained transformers, tokenizing commands into natural language, distilling skills into larger networks, and validating smaller networks experimentally.The proposed validation would train on input-output pairs and internal representations.Source: §10 · p. 38
• Future work should also examine architectural changes that make these programmable-transformer designs easier to implement and train.The paper presents this as a route to further insights into programmable computers using transformer networks.Source: §10 · p. 38

A.1 Addition of pointers.

• A one-hidden-layer ReLU network with 8d hidden activations and d outputs computes the sum of two d-bit nonnegative integers when the sum is below 2^d.The construction also applies to the {±1}^d representation via affine bit conversion.Source: §A.1 · p. 42
• Each output bit depends only on the corresponding least-significant input prefixes, reducing addition to detecting two intervals of the prefix sum.The carry bit is expressed with a ReLU combination, and each bit requires six neurons before residual correction.Source: §A.1 · p. 42

A.2 Non-linear functions as sum of sigmoids

• A three-layer transformer with m heads and dimensionality O(d) can encode a selected family of nonlinear functions using an indicator vector and sigmoid terms.A ReLU feedforward layer relocates x according to the indicator, while attention heads produce the sigmoid evaluations and an extra layer formats the output.Source: §A.2 · pp. 42–44
• The nonlinear construction uses appended bias coordinates and embedding dimension to control attention inputs and accommodate correction terms in the sigmoid evaluations.The proof appends -log(3^d −1) to coefficient vectors and sets the final coordinate of x to one.Source: §A.2 · pp. 43–44
• A one-layer, one-head transformer can represent a function requiring m sigmoids from an input containing x and one-hot function indicators.Softmax attention is configured with sufficiently large scaling, and value projections place the resulting sigmoid terms in designated coordinates.Source: §A.2 · pp. 44–45
• The three-layer construction combines indicator-controlled embeddings, attention-generated sigmoid values, and feedforward routing to produce the desired nonlinear-function output.The final feedforward layers move the computed results back to the first row.Source: §A.2 · pp. 46–47

Matrix Transposition

• A 4-layer, 1-head transformer block with dimensionality r = 2d + 2 log d = O(d) outputs the transpose of an input matrix A ∈ R^d×d.This is stated as Lemma 19 for inputs of the specified form.Source: §A.3 · p. 48
• The construction vectorizes A into a d^2-dimensional representation, applies transposition as a fixed permutation of its columns, and matricizes the result back into Aᵀ.Attention performs the vectorization and matricization, while the fixed permutation implements the transpose in vector form.Source: §A.3 · pp. 48–49
• Attention and feed-forward layers use positional encodings to copy matrix data, select and rearrange rows, and produce the transposed matrix in the scratchpad.The first layer makes d copies of A, and subsequent layers vectorize and rearrange the copied rows before restoring the matrix representation.Source: §A.3 · pp. 48–49

• For any ϵ > 0, a 2-layer, 1-head transformer block of dimensionality r = O(d) outputs A^⊤B + ϵM with ∥M∥≤1.The construction applies to A ∈ R^{k×m} and B ∈ R^{k×n}.Source: §A.4 · p. 50
• The same 2-layer, 1-head construction outputs B^⊤A + ϵM for any ϵ > 0, with ∥M∥≤1 and r = O(d).This result is stated as a corollary of the A^⊤B construction.Source: §A.4 · p. 50
• The construction also outputs B^⊤B + ϵM for any ϵ > 0, using dimensionality r = O(d) and an error matrix satisfying ∥M∥≤1.Source: §A.4 · p. 50
• Likewise, it outputs A^⊤A + ϵM for any ϵ > 0, with two layers, one head, r = O(d), and ∥M∥≤1.Source: §A.4 · p. 50
• The proof pads matrices to dimension 2d, uses fixed identity and all-ones components in the input, and copies the computed product to its target location.The feedforward layers perform the final transform, while Lemma 2 copies A^⊤B to the desired place.Source: §A.4 · pp. 50, 52

Assumptions

• Input-matrix entries are assumed uniformly bounded by a constant G, with |v_i| ≤ G.Source: B Error Analysis · p. 52

The error in the read/write operation

• Read/write errors arise because softmax attention approximates a permutation, with each off-target entry bounded by e^(log n−λ).The targeted output has one intended position and small residual errors elsewhere.Source: B Error Analysis · pp. 52–53

The error in Matrix Multiplication

• Choosing ε_2 = ε/4 and ε_1 = C_1 log(nε) makes the combined matrix-multiplication error less than ε.Source: B Error Analysis · p. 54

Function approximation

• Function-approximation error is proportional to 1/√m, where m is the number of attention heads.Source: B Error Analysis · p. 54

Accumulation of error after T operations

• Across T operations, per-iteration error is bounded by (t + 1)ε/T under norm-bounded update matrices, while each operation contributes a controlled increment ε′.The stated conclusion follows when ε′ is below the corresponding ε/T threshold for matrix multiplication and read/write operations.Source: B Error Analysis · pp. 54–55

C subleq is Turing Complete

• The restricted SUBLEQ language is Turing complete because Minsky-machine increment and conditional-decrement instructions can be translated into equivalent SUBLEQ programs.The translation initializes fixed registers c−1, c0, c+1 and an extra register, with the conditional decrement represented by five SUBLEQ instructions whose correctness covers mem[a] ≥1, mem[a] ≤−1, and mem[a] = 0.Source: C subleq is Turing Complete · pp. 55–56

D Single Instruction Set

• The single-instruction computer encodes commands as (pa, pb, pc, pflag, pm, pp), computing mem[c] = fm(mem[a], mem[b]) and conditionally jumping to pp.Addresses use binary ±1 vectors, while pm selects one of M plug-and-play function blocks; operands may be scalars, d-dimensional vectors, or d×d matrices.Source: D Single Instruction Set · pp. 56–58

D.1–D.7

• Execution proceeds by reading the instruction, copying operands, routing them to the selected function block, computing fm, returning the result, writing pc, and choosing pp or pt+1.Separate subsections implement instruction selection, operand copying, function routing and parallel computation, result return, memory writing, and conditional program-counter update.Source: D Single Instruction Set · p. 56

D Single Instruction Set

• The execution layout partitions input X into Scratchpad, Memory, and Instructions blocks, with a program counter selecting the current instruction and scratchpad memory staging operands and results.The input has n columns and O(Md + log n) rows; scratchpad size ranges from O(1) for scalar/vector functions to O(d2) for functions such as matrix vectorization.Source: D Single Instruction Set · pp. 57–58

E Calculator

• The calculator construction uses a one-hidden-layer threshold network to partition inputs into multiplicative intervals [ai, ai(1 + ϵai)), supporting bounded relative-error output activations.The number of further partitions needed to reach C is O(log C).Source: E Calculator · p. 63
• The same activation-count approach approximates 1/x on [−C,−δ] using the stated number of output activations.The passage refers to an earlier bound of the form ϵδ + log C, but the supplied excerpt does not provide its complete context.Source: E Calculator · p. 63
• A one-hidden-layer threshold network with d hidden activations is asserted to approximate the calculator functions for any ϵ ∈ [0,1].The supplied lemma states the existence of such a network but does not include the omitted approximation expression or activation count.Source: E Calculator · p. 64
• Two output activations approximate √x on each interval [i^2ϵ^2, (i+1)^2ϵ^2) formed by partitioning [0,C].The construction uses intervals [i^2ϵ^2, (i+1)^2ϵ^2) and activations of the form iϵ·1_{x≥i^2ϵ^2}−iϵ·1_{x<(i+1)^2ϵ^2}.Source: E Calculator · p. 64