Back

Looped Transformers as Programmable Computers

Angeliki GiannouShashank RajputJy-yong SohnKangwook LeeJason D. LeeDimitris Papailiopoulos

article2023ICML167 citations

Demonstrates how constant-depth looped transformers can function as universal computers by executing instruction sets directly from input prompts to run iterative algorithms, linear algebra operations, and in-context backpropagation.

Listen

Modern artificial intelligence heavily relies on transformer networks, yet existing theoretical understanding often views them as fixed sequence-to-sequence mappers or requires network depth to grow linearly with the number of computation steps. This scaling creates substantial computational overhead when executing complex, multi-step algorithms. The article demonstrates that a transformer network with fixed weights can operate as a general-purpose, programmable computer by wrapping it in a single recurrent loop. By treating the input sequence as both program instructions and working memory—analogous to punchcards and central processing units—the architecture can execute arbitrary iterative procedures without requiring deep or dynamically trained networks.

The authors develop a mathematical framework that reverse-engineers self-attention and feed-forward layers to emulate core computational primitives, such as reading and writing data, evaluating non-linear functions, maintaining program counters, and performing conditional branching. Rather than relying on infinite precision, the approach implements an instruction-set computer based on universal single instructions and a generalized framework named FLEQ. This architecture executes instructions of the form mem[c] = fm(mem[a], mem[b]) alongside conditional jumps, where fm represents pre-compiled functional blocks. The authors evaluate this setup through constructive proofs and theoretical algorithmic simulations, mapping diverse multi-step workloads to the looped transformer framework.

The primary finding is that a shallow looped transformer of constant depth (13 layers or fewer) can execute general, iterative programs regardless of program length or iteration count. Key capabilities established include building a four-function calculator with square roots and inverses within 12 layers, running matrix inversion and power iteration in 13 layers with bounded error, and executing full stochastic gradient descent with backpropagation on a two-layer neural network across T training iterations in 13 layers. Furthermore, by restricting global attention to scratchpad columns, the attention mechanism's computational complexity per step drops from quadratic to linear with respect to sequence length, while approximation errors induced by the softmax operation can be driven arbitrarily close to zero by increasing the softmax temperature.

These findings indicate that transformer models possess intrinsic capabilities to serve as compact, universal compute units. This provides a theoretical explanation for how large models perform in-context reasoning and algorithmic execution at inference time without modifying their internal parameters. For engineering and system design, this opens pathways toward using small, fixed-depth recurrent transformers to run iterative tasks, potentially lowering hardware and inference costs compared to deploying massive, deep models for algorithmic reasoning.

Organizations exploring algorithmic distillation or embedded neural compute should consider prototyping compact, looped transformer architectures for deterministic or iterative routines. Further analysis should explore practical software tooling that compiles high-level code directly into transformer weights, as well as empirical benchmarking to determine real-world execution speed and memory tradeoffs against standard central processing units. While theoretical proofs provide high confidence in the framework's mathematical validity, key limitations remain: the article relies on constructive theoretical proofs rather than empirical hardware benchmarks, assumes a separated memory-and-instruction input structure, and has not yet established a method for merging these hard-coded architectures with standard pre-trained language models.

Princeton UniversityUniversity of Wisconsin MadisonYonsei Universitybackpropagation algorithmencoder-decoderlibrarieslooped transformersprogrammable computersiterative computation
arXiv: 2301.13196jysohn1108/Looped_TF
  • Paper: Neural Turing Machines, Alex Graves et al. (2014). Introduces the foundational paradigm of pairing neural controllers with addressable memory for algorithmic computation, setting the stage for transformer-based computer emulation.
  • Paper: Attention Is All You Need, Ashish Vaswani et al. (2017). Introduces the core Transformer architecture and self-attention mechanism whose programmable computational capabilities are systematically mapped in the looped setting.
  • Paper: Transformers Learn In-Context by Gradient Descent, Johannes von Oswald et al. (2023). Demonstrates that attention layers can implement optimization steps like gradient descent in-context, providing the conceptual foundation for looped transformers to execute backpropagation algorithms.
  • Paper: Tighter Bounds on the Expressivity of Transformer Encoders, David Chiang et al. (2023). Establishes formal theoretical expressivity bounds for fixed-precision transformer encoders, directly informing the functional limits of constant-depth transformer components.
  • Paper: Your Transformer May Not be as Powerful as You Expect, Shengjie Luo et al. (2022). Examines the conditions necessary for transformers to maintain universal approximation and position tracking capabilities.
Cover for Looped Transformers as Programmable Computers

Abstract

We present a framework for using transformer networks as universal computers by programming them with specific weights and placing them in a loop. Our input sequence acts as a punch-card, consisting of instructions and memory for data read/writes. We demonstrate that a constant number of encoder layers can emulate basic computing blocks, including lexicographic operations, non-linear functions, function calls, program counters, and conditional branches. Using this framework, we emulate a computer using a simple instruction-set architecture, which allows us to map iterative algorithms to programs that can be executed by a constant depth looped transformer network. We show how a single frozen transformer, instructed by its input, can emulate a basic calculator, a basic linear algebra library, and even a full backpropagation, in-context learning algorithm. Our findings reveal the potential of transformer networks as programmable compute units and offer insight into the mechanics of attention. 3

Topics

backpropagation algorithmencoder-decoderlibrariesnetwork architecture

Keywords

looped transformersprogrammable computersiterative computationprogram countersmemory cellsdata pointerspositional encodingspower iterationmatrix multiplication

Table of Contents

  • 1 Introduction
  • 2 Prior Work
  • 3 Preliminaries
  • 4 Building Transformer Blocks towards General Computation
  • 4.1 Positional Encodings, Program Counter, and Data Pointers
  • 4.2 read / write: Copying Data/Instructions to/from the Scratchpad
  • 4.3 if ⟨condition⟩ then goto ⟨instruction⟩
  • 5 Emulating a Single Instruction Computer
  • 5.1 A SUBLEQ Transformer
  • 5.2 FLEQ: A More Flexible Attention-based Computer
  • 6 Applications
  • 7 Conclusion
  • Acknowledgements
  • References
  • A Limitations
  • B Omitted Proofs
  • B.1 Addition of pointers.
  • B.2 Read/Write operations.
  • B.3 if ⟨condition⟩ then goto ⟨instruction⟩: Conditional branching
  • C subleq is Turing Complete
  • D FLEQ Overview
  • E Functions in the Unified Template Form
  • E.1 Encoding Non-linear Functions within the Attention Mechanism
  • E.2 Matrix Transposition
  • E.3 Matrix Multiplication by Linearizing the Softmax
  • E.4 Advantage of attention over fully-connected networks
  • F FLEQ: Proof of Theorem 1
  • F.1 Step 1
  • F.2 Step 2
  • F.3 Step 3
  • F.4 Step 4
  • F.5 Step 5
  • F.6 Step 6
  • F.7 Step 7
  • G Error Analysis
  • H A Basic Calculator
  • I Linear Algebra
  • J Emulating Learning Algorithms at Inference Time

Knowls

  1. Knowl 1 — FLEQ compiles programs into a fixed-depth looped transformer

    theoretical result

    Let f1,…,fMf_1,\ldots,f_M be functions implemented by transformer-based function blocks, where block ii has lil_i layers and hih_i attention heads. Each block takes two padded inputs and writes its output to a designated part of a scratchpad. There is a transformer with 9+max⁡ili9+\max_i l_i layers, ∑ihi\sum_i h_i heads, and embedding dimension O(Md+log⁡n)O(Md+\log n) that executes programs with instructions of the form

    FLEQ⁡(a,b,c,m,flag,p,dh,dw):mem[c]=fm(mem[a],mem[b]);if mem[flag]≤0, jump to p.\operatorname{FLEQ}(a,b,c,m,\mathrm{flag},p,d_h,d_w):\quad \mathrm{mem}[c]=f_m(\mathrm{mem}[a],\mathrm{mem}[b]);\quad \text{if }\mathrm{mem}[\mathrm{flag}]\le 0\text{, jump to }p.

    Here nn is the input sequence length, dd is the maximum padded size of a function-block input, mm selects one of the MM functions, and dh,dw≤dd_h,d_w\le d specify the active matrix dimensions for that instruction. The memory locations a,b,c,flaga,b,c,\mathrm{flag} and instruction address pp are encoded as pointers. Reapplying the same transformer for KK loop iterations executes KK instructions; its depth does not grow with the number of program instructions. Softmax-based read, write, and function operations incur approximation error that can be made arbitrarily small by increasing the softmax temperature.

  2. Knowl 2 — Program, memory, and function blocks share one input sequence

    model/method

    The input to the looped-transformer computer is a sequence of nn columns partitioned into a scratchpad, a memory region, and an instruction region. The scratchpad holds the program counter, the current instruction, temporary data, and separate workspaces for the implemented functions. Memory stores scalars, vectors, or matrices; a matrix can occupy consecutive columns. Instructions contain pointers to operand locations, the result destination, the selected function block, the branch flag and target, and the active input dimensions. For a function block with maximum padded dimension dd, the first input occupies the first dd columns of its workspace, the second input the next dd, and the output the following dd; unused entries are zero-padded, and additional columns may serve as workspace. Each loop iteration fetches the instruction at the program counter, reads its operands, routes them to the selected function block, writes the result to memory, and updates the program counter according to the branch condition.

  3. Knowl 3 — Binary positional encodings implement pointer operations and control flow

    model/method

    For a sequence of length nn, column index ii is encoded by a log⁡n\log n-dimensional vector pi∈{−1,+1}log⁡np_i\in\{-1,+1\}^{\log n}: a zero bit in the binary index is encoded as −1-1 and a one bit as +1+1. Thus pi⊤pi=log⁡np_i^\top p_i=\log n, while distinct indices have inner product at most log⁡n−1\log n-1. The paper uses these encodings as data pointers and program counters; a one-hidden-layer ReLU network can increment or add represented nonnegative indices, subject to the stated no-overflow condition.

    A one-layer, one-head transformer of width O(log⁡n+d)O(\log n+d) can copy a data or command vector from the column selected by a scratchpad pointer, or write scratchpad data to the selected destination. These operations use softmax attention to approximate a positional match, and their error can be reduced by raising the softmax temperature. Conditional control evaluates whether the selected memory value is nonpositive and sets the program counter either to the branch target or to the next instruction; the pointer selection uses two transformer layers.

  4. Knowl 4 — A constant-depth looped transformer executes a Turing-complete SUBLEQ computer

    theoretical result

    SUBLEQ has one instruction: mem[b]←mem[b]−mem[a]\mathrm{mem}[b]\leftarrow\mathrm{mem}[b]-\mathrm{mem}[a]; if the result is nonpositive, jump to instruction cc, otherwise continue to the next instruction. A looped transformer can execute this instruction set using a ten-layer, two-head transformer of width O(log⁡n+log⁡N)O(\log n+\log N), where nn is the input length proportional to the program and memory size and each integer is stored in NN bits using two's-complement representation. The supported integer range is [−2N−1+1,2N−1−1][-2^{N-1}+1,2^{N-1}-1]. The construction fetches the instruction, reads both operands, performs subtraction, writes the result, and branches; softmax read/write error can be reduced by increasing temperature. The paper shows that its restricted version of SUBLEQ is Turing complete given infinite memory. The transformer depth is fixed as program length grows, although the number of loop executions still grows with the number of instructions executed.

  5. Knowl 5 — Attention can encode sigmoid sums for nonlinear function blocks

    theoretical result

    The paper constructs attention heads whose softmax response implements a sigmoid of an input-dependent linear score. Consequently, a transformer-based function block can select one of NN pre-encoded functions using an indicator input and compute an approximation of the form

    fj(x)=∑i=1mcji ϕ(x⊤aji),ϕ(u)=11+e−u,f_j(x)=\sum_{i=1}^{m}c_{ji}\,\phi(x^\top a_{ji}),\qquad \phi(u)=\frac{1}{1+e^{-u}},

    where xx is the input vector, jj is the selected function, and aji,cjia_{ji},c_{ji} are fixed coefficients encoded in the block's weights. The block uses three layers, mm heads, and dimension O(d)O(d) for input dimension dd. For targets in the paper's bounded-domain class with bounded Fourier integral, the cited sigmoid approximation result gives error O(m−1/2)O(m^{-1/2}) under its stated scaling condition on the sigmoid parameter. This supplies nonlinear function blocks that can be called by FLEQ programs.

  6. Knowl 6 — A 12-layer FLEQ transformer implements a basic calculator

    theoretical result

    The unified attention-based computer can implement addition, subtraction, multiplication, percentage, inversion, and square root using a 12-layer transformer with mm heads and dimension O(log⁡n)O(\log n), where nn is the number of calculator operations in the program. The inversion approximation is stated for operands in [−eO(m),−Ω~(1/m)]∪[Ω~(1/m),eO(m)][-e^{O(m)},-\widetilde{\Omega}(1/\sqrt m)]\cup[\widetilde{\Omega}(1/\sqrt m),e^{O(m)}] and has error O(1/m)O(1/\sqrt m). The square-root approximation is stated for operands in [0,O(m2)][0,O(m^2)] and has error O(1/m)O(1/m). The arithmetic and percentage blocks are also subject to softmax approximation error, which the paper says can be reduced by increasing temperature. The calculator is a program over memory locations and function calls, not a separately trained model.

  7. Knowl 7 — Transformer blocks implement matrix transposition and multiplication

    theoretical result

    For a matrix A∈Rd×dA\in\mathbb{R}^{d\times d}, a transformer-based function block with four layers, one head, and dimension 2d+2log⁡d=O(d)2d+2\log d=O(d) outputs a representation of A⊤A^\top with additive error ϵM\epsilon M, where ∥M∥≤1\|M\|\le 1 and ϵ>0\epsilon>0 can be chosen arbitrarily small. The construction vectorizes the matrix, permutes the entries using positional encodings, and restores the matrix representation. For A∈Rk×mA\in\mathbb{R}^{k\times m} and B∈Rk×nB\in\mathbb{R}^{k\times n}, a two-layer, one-head block of dimension O(d)O(d) implements A⊤BA^\top B with additive error ϵM\epsilon M, again with ∥M∥≤1\|M\|\le 1; the softmax parameters control this error. These blocks provide the linear-algebra operations used by the paper's iterative programs.

  8. Knowl 8 — Fixed-depth transformers emulate iterative matrix algorithms

    theoretical result

    Using matrix-operation function blocks inside the looped computer, a 13-layer, one-head transformer of dimension O(d)O(d) can emulate iterative linear-algebra procedures on d×dd\times d matrices. For matrix inversion, the program uses the Newton iteration Xi+1=Xi(2I−AXi)X_{i+1}=X_i(2I-AX_i), initialized as X−T=ϵAX_{-T}=\epsilon A in the paper's construction; for every requested output tolerance, the transformer can produce an output within that tolerance, with softmax temperature controlling the read/write and arithmetic approximation errors. For power iteration, the program starts with b0=1b_0=\mathbf{1}, repeatedly computes bk+1=Abkb_{k+1}=Ab_k, and normalizes the final vector. The paper states that the transformer emulates T=O(log⁡(1/ϵ))T=O(\log(1/\epsilon)) power-iteration steps with output error at most ϵ\epsilon. In both cases the transformer depth remains fixed while the algorithm's iterations are performed by repeated calls.

  9. Knowl 9 — Looped transformers emulate SGD and two-layer-network backpropagation

    theoretical result

    A 13-layer, one-head looped transformer of dimension O(log⁡∣D∣+d)O(\log |D|+d) can simulate TT iterations of SGD over a dataset DD of ∣D∣|D| examples in dimension dd, with the step size supplied to the program. For a linear model, the paper gives the update wt+1=wt−η∑i=1∣D∣(wt⊤xi−yi)xiw_{t+1}=w_t-\eta\sum_{i=1}^{|D|}(w_t^\top x_i-y_i)x_i and implements successive data-point processing with pointers that advance through the examples and reset for another pass. The same framework implements SGD for a two-layer sigmoid-activated neural network by computing forward activations, backpropagated gradients, and weight and bias updates. Each simulated step is approximate; the paper says its error can be reduced arbitrarily by increasing softmax temperature and adjusting an additional free parameter without increasing transformer size. The construction also applies to other losses when their derivatives can be approximated by an available function block.

  10. Knowl 10 — The constructions have unresolved efficiency and precision limitations

    limitation

    The paper does not experimentally validate the computational efficiency of its constructions and notes that executing an algorithm with a transformer may be less efficient than running the algorithm directly. The required input organization separates instructions from memory and reserves workspace for computations, which may introduce inefficiency. The authors leave open how hard-coded transformer weights could be combined with pretrained models, and they do not provide a thorough finite-precision analysis. The approximation guarantees therefore establish expressivity and controllable idealized errors, not practical runtime or robustness under finite-precision implementation.

Coverage note — Detailed proofs and weight-matrix constructions for the read/write, arithmetic, matrix-operation, and function-approximation blocks, along with full example program listings, are omitted because their implementation details are not independently load-bearing beyond the stated mechanisms and guarantees.

References

  1. 1.Akyurek, E., Schuurmans, D., Andreas, J., Ma, T., and Zhou, D. What learning algorithm is in-context learning? investigations with linear models. arXiv preprint arXiv:2211.15661, 2022.
  2. 2.Barron, A. Universal approximation bounds for superpositions of a sigmoidal function. IEEE Transactions on Information Theory, 39(3):930–945, 1993. doi: 10.1109/18.256500.
  3. 3.Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901, 2020.
  4. 4.Charton, F. Linear algebra with transformers. arXiv preprint arXiv:2112.01898, 2021.
  5. 5.Chowdhery, A., Narang, S., Devlin, J., Bosma, M., Mishra, G., Roberts, A., Barham, P., Chung, H. W., Sutton, C., Gehrmann, S., et al. Palm: Scaling language modeling with pathways. 2022.
  6. 6.Chung, H. W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fedus, W., Li, E., Wang, X., Dehghani, M., Brahma, S., et al. Scaling instruction-finetuned language models. arXiv preprint arXiv:2210.11416, 2022.
  7. 7.Dasgupta, I., Lampinen, A. K., Chan, S. C., Creswell, A., Kumaran, D., McClelland, J. L., and Hill, F. Language models show human-like content effects on reasoning. arXiv preprint arXiv:2207.07051, 2022.
  8. 8.Dehghani, M., Gouws, S., Vinyals, O., Uszkoreit, J., and Kaiser, Ł. Universal transformers. arXiv preprint arXiv:1807.03819, 2018.
  9. 9.Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., et al. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations, 2020.
  10. 10.Garg, S., Tsipras, D., Liang, P., and Valiant, G. What can transformers learn in-context? a case study of simple function classes. In Advances in Neural Information Processing Systems, 2022.
  11. 11.Hutchins, D., Schlag, I., Wu, Y., Dyer, E., and Neyshabur, B. Block-recurrent transformers. arXiv preprint arXiv:2203.07852, 2022.
  12. 12.Kenton, J. D. M.-W. C. and Toutanova, L. K. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT, pp. 4171–4186, 2019.
  13. 13.Khan, S., Naseer, M., Hayat, M., Zamir, S. W., Khan, F. S., and Shah, M. Transformers in vision: A survey. ACM computing surveys (CSUR), 54(10s):1–41, 2022.
  14. 14.Lewkowycz, A., Andreassen, A., Dohan, D., Dyer, E., Michalewski, H., Ramasesh, V., Slone, A., Anil, C., Schlag, I., Gutman-Solo, T., et al. Solving quantitative reasoning problems with language models. arXiv preprint arXiv:2206.14858, 2022.
  15. 15.Lindner, D., Kramar, J., Rahtz, M., McGrath, T., and Mikulik, V. Tracr: Compiled transformers as a laboratory for interpretability. arXiv preprint arXiv:2301.05062, 2023.
  16. 16.Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers learn shortcuts to automata. arXiv preprint arXiv:2210.10749, 2022.
  17. 17.Mavaddat, F. and Parhami, B. Urisc: the ultimate reduced instruction set computer. International Journal of Electrical Engineering Education, 25(4):327–334, 1988.
  18. 18.Merrill, W., Sabharwal, A., and Smith, N. A. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10:843–856, 2022.
  19. 19.Nye, M., Andreassen, A. J., Gur-Ari, G., Michalewski, H., Austin, J., Bieber, D., Dohan, D., Lewkowycz, A., Bosma, M., Luan, D., et al. Show your work: Scratchpads for intermediate computation with language models. 2021.
  20. 20.Perekrestenko, D., Grohs, P., Elbrachter, D., and Bölcskei, H. The universal approximation power of finite-width deep relu networks. arXiv preprint arXiv:1806.01528, 2018.
  21. 21.Perez, J., Barceló, P., and Marinkovic, J. Attention is turing-complete. Journal of Machine Learning Research, 22(75):1–35, 2021. URL http://jmlr.org/papers/v22/20-302.html.
  22. 22.Perez, J., Marinkovic, J., and Barceló, P. On the turing completeness of modern neural network architectures, 2019. URL https://arxiv.org/abs/1901.03429.
  23. 23.Shen, Z., Liu, Z., and Xing, E. Sliced recursive transformer. In European Conference on Computer Vision, pp. 727–744. Springer, 2022.
  24. 24.Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. Advances in neural information processing systems, 30, 2017.
  25. 25.von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M. Transformers learn in-context by gradient descent. arXiv preprint arXiv:2212.07677, 2022.
  26. 26.Wei, C., Chen, Y., and Ma, T. Statistically meaningful approximation: a case study on approximating turing machines with transformers. Advances on Neural Information Processing Systems (NeurIPS), 2022a.
  27. 27.Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D., et al. Emergent abilities of large language models. arXiv preprint arXiv:2206.07682, 2022b.
  28. 28.Wei, J., Wang, X., Schuurmans, D., Bosma, M., Chi, E., Le, Q., and Zhou, D. Chain of thought prompting elicits reasoning in large language models. arXiv preprint arXiv:2201.11903, 2022c.
  29. 29.Weiss, G., Goldberg, Y., and Yahav, E. Thinking like transformers. In International Conference on Machine Learning, pp. 11080–11090. PMLR, 2021.
  30. 30.Yuan, L., Chen, Y., Wang, T., Yu, W., Shi, Y., Jiang, Z.-H., Tay, F. E., Feng, J., and Yan, S. Tokens-to-token vit: Training vision transformers from scratch on imagenet. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 558–567, 2021.
  31. 31.Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S., and Kumar, S. Are transformers universal approximators of sequence-to-sequence functions? In International Conference on Learning Representations, 2019.
  32. 32.Zhou, H., Nova, A., Larochelle, H., Courville, A., Neyshabur, B., and Sedghi, H. Teaching algorithmic reasoning via in-context learning. arXiv preprint arXiv:2211.09066, 2022.

Citation

MLA
Giannou, A., et al. “Looped Transformers as Programmable Computers”. International Conference on Machine Learning, vol. 202, 2023, pp. 11398–442, https://proceedings.mlr.press/v202/giannou23a.html.
APA
Giannou, A., Rajput, S., Sohn, J.-Y., Lee, K., Lee, J. D., & Papailiopoulos, D. (2023). Looped Transformers as Programmable Computers. International Conference on Machine Learning, 202, 11398–11442. https://proceedings.mlr.press/v202/giannou23a.html
Chicago
Giannou, A., S. Rajput, J.-Y. Sohn, K. Lee, J. D. Lee, and D. Papailiopoulos. 2023. “Looped Transformers as Programmable Computers”. International Conference on Machine Learning 202: 11398–442. https://proceedings.mlr.press/v202/giannou23a.html.
Harvard
Giannou, A. et al. (2023) “Looped Transformers as Programmable Computers”, International Conference on Machine Learning. PMLR, pp. 11398–11442. Available at: https://proceedings.mlr.press/v202/giannou23a.html.
Vancouver
1. Giannou A, Rajput S, Sohn J-Y, Lee K, Lee JD, Papailiopoulos D (2023) Looped Transformers as Programmable Computers. In: International Conference on Machine Learning. PMLR, pp 11398–11442

BibTeX

@InProceedings{pmlr-v202-giannou23a,
  title = 	 {Looped Transformers as Programmable Computers},
  author =       {Giannou, Angeliki and Rajput, Shashank and Sohn, Jy-Yong and Lee, Kangwook and Lee, Jason D. and Papailiopoulos, Dimitris},
  booktitle = 	 {Proceedings of the 40th International Conference on Machine Learning},
  pages = 	 {11398--11442},
  year = 	 {2023},
  editor = 	 {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan},
  volume = 	 {202},
  series = 	 {Proceedings of Machine Learning Research},
  month = 	 {23--29 Jul},
  publisher =    {PMLR},
  pdf = 	 {https://proceedings.mlr.press/v202/giannou23a/giannou23a.pdf},
  url = 	 {https://proceedings.mlr.press/v202/giannou23a.html},
  abstract = 	 {We present a framework for using transformer networks as universal computers by programming them with specific weights and placing them in a loop. Our input sequence acts as a punchcard, consisting of instructions and memory for data read/writes. We demonstrate that a constant number of encoder layers can emulate basic computing blocks, including lexicographic operations, non-linear functions, function calls, program counters, and conditional branches. Using this framework, we emulate a computer using a simple instruction-set architecture, which allows us to map iterative algorithms to programs that can be executed by a constant depth looped transformer network. We show how a single frozen transformer, instructed by its input, can emulate a basic calculator, a basic linear algebra library, and even a full backpropagation, in-context learning algorithm. Our findings reveal the potential of transformer networks as programmable compute units and offer insight into the mechanics of attention.}
}
Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: https://creativecommons.org/licenses/by/4.0/