Memory Augmented Large Language Models are Computationally Universal

Understand

We show that transformer-based large language models are computationally universal when augmented with an external memory.

• Any deterministic language model that conditions on strings of bounded length is equivalent to a finite automaton, hence computationally limited.
• However, augmenting such models with a read-write memory creates the possibility of processing arbitrarily large inputs and, potentially, simulating any algorithm.
• We establish that an existing large language model, Flan-U-PaLM 540B, can be combined with an associative read-write memory to exactly simulate the execution of a universal Turing machine, $U_{15,2}$.