Elamur Research⌕
☰
home / papers / 2023 / Memory Augmented Large Language Models are Computationally Universal

Memory Augmented Large Language Models are Computationally Universal

Paper · 2023 · Dale Schuurmans

Summary

Transformer language models can only attend to an input of bounded length, so a deterministic model of this kind is formally no more powerful than a finite automaton. Schuurmans asks whether adding an external feedback loop fundamentally expands what such models can compute. He pairs a frozen Flan-U-PaLM 540B with an associative read-write memory, a key-value dictionary, in the style of a von Neumann stored-instruction computer. The language model acts as the CPU and the dictionary acts as RAM. Python regular expressions shuttle prompts and variable assignments between the two, and these parsers are restricted to finite-state operations so that the universality cannot come from the glue code. A dedicated "prompt program" then makes the system emulate the universal Turing machine U 15,2. Correctness reduces to confirming that the model answers each of a finite set of possible prompts correctly. No weights are changed and no training is involved. The work shows that existing LLMs are already Turing-universal when given unbounded external memory, which sets it apart from earlier proofs that relied on specially constructed network weights.

Key points

  • Setup: The model is Flan-U-PaLM 540B with frozen weights. The memory is a Python dictionary, and memory location op serves as the instruction register. The loop repeats until op contains halt.

  • Glue code: All pre- and post-processing uses the Python re library and covers:

    • parsing assignments,
    • splicing in values with @[...] and %[...],
    • integer += and -= updates.

    Nested substitution is capped at depth 2 so that every step stays finite-state.

  • Target machine: The system simulates U 15,2 (Neary & Woods), using one terse prompt for each machine state, labelled A through O. The proof is a finite series of verification tests, one for each combination of state and symbol read.

  • Brittleness: Prompts had to be compact and carefully engineered, and not every LLM tried succeeded. The model handled if-then conditionals reliably but not if-then-else, which made the smaller U 6,4 impractical to simulate.

  • Alternatives and analogies: An earlier version used Rule 110. It was dropped because it needs an unbounded periodic initialization, while U 15,2 needs only a bounded one. The author compares the prompt language to early assembly languages.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of AlbertaEdmonton · Canada44 works · 3,236 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,320 works

Cite

Cite as Dale Schuurmans. 2023. Memory Augmented Large Language Models are Computationally Universal. arXiv:2301.04589.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.2301.04589 · arXiv 2301.04589

@misc{schuurmans2023memory,
  title = {{Memory Augmented Large Language Models are Computationally Universal}},
  author = {Dale Schuurmans},
  year = {2023},
  doi = {10.48550/arxiv.2301.04589},
  eprint = {2301.04589},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.2301.04589}
}

References

23 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Bhattamishra, S., Patel, A., and Goyal, N. (2020). On the computational power of Transformers and its implications in sequence modeling. In Conference on Computational Natural Language Learning (CONLL). find
  2. Böhm, C. (1954). Calculatrices digitales du déchiffrage de formules logico-mathématiques par la machine même dans la conception du programme. PhD thesis, ETH Zürich. find
  3. Booth, A. and Britten, K. (1947). General considerations in the deisgn of an all purpose electronic digital computer. Technical report, Institute for Advanced Study, Princeton. 2nd ed. find
  4. Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B… — Language Models are Few-Shot Learners
  5. Chung, H. W., Hou, L., Longpre, S., Zoph, B., Tay, Y., Fedus, W., Li, Y., Wang, X., Dehghani, M., Brahma, S., Webson, A., Gu, S. S., Dai, Z., Suzgun, M., Chen, X., Chowdhery, A., Castro-Ros, A., Pellat, M., Robinson, K., Valter, D., Narang, S., Mishra, G., Yu, A., Zhao, V., Huang, Y., Dai, A., Yu, H… find
  6. Cook, M. (2004). Universality in elementary cellular automata. Complex Systems, 15:1–40. find
  7. Dohan, D., Xu, W., Lewkowycz, A., Austin, J., Bieber, D., Lopes, R. G., Wu, Y., Michalewski, H., Saurous, R. A., Sohl-dickstein, J., Murphy, K., and Sutton, C. (2022). Language model cascades. arXiv 2207.10342. find
  8. Neary, T. (2008). Small universal Turing machines. PhD thesis, National University of Ireland, Maynooth. find
  9. Neary, T. and Woods, D. (2009). Four small universal Turing machines. Fundamenta Informaticae, 91:105–126. find
  10. Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Gray, A., Schulman, J., Hilton, J., Kelton, F., Miller, L., Simens, M., Askell, A., Welinder, P., Christiano, P., Leike, J., and Lowe, R. (2022). Training language models to follow instruction…
  11. Pérez, J., Marinković, J., and Parceló, P. (2019). On the Turing completeness of modern neural network architectures. In International Conference on Learning Representations (ICLR). find
  12. Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. (2019). Language models are unsupervised multitask learners. find
  13. Schulman, J., Zoph, B., Kim, C., Hilton, J., Menick, J., Weng, J., Uribe, J. F. C., Fedus, L., Metz, L., Pokorny, M., Lopes, R. G., Zhao, S., Vijayvergiya, A., Sigler, E., Perelman, A., Voss, C., Heaton, M., Parish, J., Cummings, D., Nayak, R., Balcom, V., Schnurr, D., Kaftan, T., Hallacy, C., Turle… find
  14. Shannon, C. (1956). A universal Turing machine with two internal states. Automata Studies, Annals of Mathematics Studies, 34:157–165. find
  15. Siegelmann, H. and Sontag, E. (2019). On the computational power of neural nets. In Conference on Learning Theory (COLT). find
  16. Sipser, M. (2013). Introduction to the Theory of Computation. Cengage Learning, 3rd edition. find
  17. Turing, A. (1937). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 2, 42:230–265. find
  18. von Neumann, J. (1945). First draft of a report on the EDVAC. find
  19. Wei, C., Chen, Y., and Ma, T. (2022a). Statistically meaningful approximation: a case study on approximating Turing machines with Transformers. In Advances in Neural Information Processing Systems (NeurIPS). find
  20. Wei, J., Wang, X., Schuurmans, D., Bosma, M., Ichter, B., Xia, F., Chi, E., Le, Q., and Zhou, D. (2022b). Chain of thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems (NeurIPS).
  21. Weiss, G., Goldberg, Y., and Yahav, E. (2018). On the practical computational power of finite precision RNNs for language recognition. In Conference of the Association for Computational Linguistics (ACL).
  22. Wolfram, S. (2002). A New Kind of Science. Wolfram Media. find
  23. Zhou, D., Schärli, N., How, L., Wei, J., Scales, N., Wang, X., Schuurmans, D., Cui, C., Bousquet, O., Le, Q., and Chi, E. (2022). Least-to-most prompting enables complex reasoning in large language models. arXiv 2205.10625.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/schuurmans-2023-memory-augmented-large-language-models/