Looped Transformers as Programmable Computers

By Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason D. Lee, Dimitris Papailiopoulos. 2023

222 citations recorded by the source corpus.

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 embedding edit operations, non-linear functions, function calls, program counters, and conditional branches. Using these building blocks, we emulate a small instruction-set computer. This allows us to map iterative algorithms to programs that can be executed by a looped, 13-layer transformer. We show how this transformer, instructed by its input, can emulate a basic calculator, a basic linear algebra library, and in-context learning algorithms that employ backpropagation. Our work highlights the versatility of the attention mechanism, and demonstrates that even shallow transformers can execute full-fledged, general-purpose programs.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, Hardware and Architecture, Model Architectures

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Tengyu Ma
2. Zhiyuan Li
3. Di He
4. Suvrit Sra
5. Denny Zhou
6. Liwei Wang
7. Hadi Daneshmand
8. Liang Sun

In Electrical and Electronic Engineering

1. Tengyu Ma
2. Liang Sun
3. Xue Wang
4. Rong Jin
5. Suvrit Sra
6. Tian Zhou
7. Denny Zhou

In Hardware and Architecture

1. Tengyu Ma
2. Liwei Wang

In Model Architectures

1. Di He
2. Hadi Daneshmand
3. Tengyu Ma
4. Liang Sun
5. Xue Wang
6. Hong Liu
7. Rong Jin
8. Liwei Wang

Citations in the corpus

• Transformers learn to implement preconditioned gradient descent for in-context learning (2023, background): “This capability inspired a line of research that examines the algorithmic power of transformers (Pérez et al., 2021; Wei et al., 2022; Giannou et al., 2023; Akyürek et al., 2022; Olsson et al., 2022).”
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems (2024, background): “…ability of self-attention to create low-complexity circuits has been recognized (Edelman et al., 2022; Hahn, 2020; Merrill et al., 2021), as well as its capacity to form declarative programs (Weiss et al., 2021), and Turing machines (Dehghani et al., 2018; Giannou et al., 2023; Pérez et al., 2021).”
• Training Large Language Models to Reason in a Continuous Latent Space (2024, unknown): “Recently, looped transformers (Giannou et al., 2023; Fan et al., 2024) have been proposed to solve algorithmic tasks, which have some similarities to the computing process of continuous thoughts, but we focus on common reasoning tasks and aim at investigating latent reasoning in comparison to…”
• One Fits All: Power General Time Series Analysis by Pretrained LM (2023, methodology): “We believe it is this generic function performed by the self-attention module that allows trained transformer models to be so-called universal compute engine Lu et al. (2022) or general computation calculator Giannou et al. (2023).”
• Towards Revealing the Mystery behind Chain of Thought: a Theoretical Perspective (2023, background): “Recently, Giannou [22] demonstrated that a constant-depth looped Transformer encoder can simulate practical computer programs.”