Autoregressive Large Language Models are Computationally Universal
<|reference_start|>Autoregressive Large Language Models are Computationally Universal: We show that autoregressive decoding of a transformer-based language model can realize universal computation, without external intervention or modification of the model's weights. Establishing this result requires understanding how a language model can process arbitrarily long inputs using a bounded context. For this purpose, we consider a generalization of autoregressive decoding where, given a long input, emitted tokens are appended to the end of the sequence as the context window advances. We first show that the resulting system corresponds to a classical model of computation, a Lag system, that has long been known to be computationally universal. By leveraging a new proof, we show that a universal Turing machine can be simulated by a Lag system with 2027 production rules. We then investigate whether an existing large language model can simulate the behaviour of such a universal Lag system. We give an affirmative answer by showing that a single system-prompt can be developed for gemini-1.5-pro-001 that drives the model, under deterministic (greedy) decoding, to correctly apply each of the 2027 production rules. We conclude that, by the Church-Turing thesis, prompted gemini-1.5-pro-001 with extended autoregressive (greedy) decoding is a general purpose computer.<|reference_end|>
@article{schuurmans2024autoregressive,
    title={Autoregressive Large Language Models are Computationally Universal},
    author={Dale Schuurmans, Hanjun Dai, Francesco Zanini},
    journal={arXiv preprint arXiv:2410.03170},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.03170},
    primaryClass={cs.CL}
}