mlsanityData to 14 Oct 2026

Universal computation is intrinsic to language model decoding

arXiv 2601.08061 ↗First posted 12 Jan 2026cs.CLcited by 1

Not on the map. Why?

Abstract (arXiv)

Language models now provide an interface to express and often solve general problems in natural language, yet their ultimate computational capabilities remain a major topic of scientific debate. Unlike a formal computer, a language model is trained to autoregressively predict successive elements in human-generated text. We prove that chaining a language model's autoregressive output is sufficient to perform universal computation. That is, a language model can simulate the execution of any algorithm on any input. The challenge of eliciting desired computational behaviour can thus be reframed in terms of programmability: the ease of finding a suitable prompt. Strikingly, we demonstrate that even randomly initialized language models are capable of universal computation before training. This implies that training does not give rise to computational expressiveness -- rather, it improves programmability, enabling a natural language interface for accessing these intrinsic capabilities.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 56 of its 87 references that are in the map. First posted on arXiv 12 Jan 2026.

Builds on

56 of 87 references.

References · 56

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  4. 2020Language Models are Few-Shot Learnerscited by 32,419
  5. 2022Training language models to follow instructions with human feedbackcited by 15,971
  6. 2024The Llama 3 Herd of Modelscited by 14,715
  7. 2022Chain-of-Thought Prompting Elicits Reasoning in Large Language Modelscited by 12,459
  8. 2025DeepSeek-R1: Incentivizing Reasoning Capability in LLMs via Reinforcement Learningcited by 6,330
  9. 2016Layer Normalizationcited by 5,669
  10. 2017Model-Agnostic Meta-Learning for Fast Adaptation of Deep Networkscited by 4,897
  11. 2022Large Language Models are Zero-Shot Reasonerscited by 4,374
  12. 2021Prefix-Tuning: Optimizing Continuous Prompts for Generationcited by 3,915
38 more
  1. 2017Deep reinforcement learning from human preferencescited by 3,912
  2. 2021Finetuned Language Models Are Zero-Shot Learnerscited by 3,780
  3. 2022Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedbackcited by 3,720
  4. 2024Gemini 1.5: Unlocking multimodal understanding across millions of tokens of contextcited by 3,224
  5. 2022Constitutional AI: Harmlessness from AI Feedbackcited by 3,050
  6. 2022Scaling Instruction-Finetuned Language Modelscited by 3,024
  7. 2020Learning to summarize from human feedbackcited by 2,588
  8. 2023Efficient Streaming Language Models with Attention Sinkscited by 2,186
  9. 2021What Makes Good In-Context Examples for GPT-3?cited by 1,195
  10. 2022Large Language Models Are Human-Level Prompt Engineerscited by 1,045
  11. 2023Large Language Models Cannot Self-Correct Reasoning Yetcited by 1,017
  12. 2022STaR: Bootstrapping Reasoning With Reasoningcited by 940
  13. 2021Show Your Work: Scratchpads for Intermediate Computation with Language Modelscited by 886
  14. 2018Universal Transformerscited by 647
  15. 2024GSM-Symbolic: Understanding the Limitations of Mathematical Reasoning in Large Language Modelscited by 550
  16. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  17. 2023Think before you speak: Training Language Models With Pause Tokenscited by 264
  18. 2024Chain of Thought Empowers Transformers to Solve Inherently Serial Problemscited by 260
  19. 2023Looped Transformers as Programmable Computerscited by 237
  20. 2024The Illusion of State in State-Space Modelscited by 187
  21. 2021Thinking Like Transformerscited by 184
  22. 2021Cutting Down on Prompts and Parameters: Simple Few-Shot Learning with Language Modelscited by 139
  23. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  24. 2019On the Turing Completeness of Modern Neural Network Architecturescited by 129
  25. 2015Neural GPUs Learn Algorithmscited by 121
  26. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  27. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  28. 2020On the Computational Power of Transformers and its Implications in Sequence Modelingcited by 85
  29. 2024A Peek into Token Bias: Large Language Models Are Not Yet Genuine Reasonerscited by 73
  30. 2023Unleashing the potential of prompt engineering for large language modelscited by 72
  31. 2023Auto-Regressive Next-Token Predictors are Universal Learnerscited by 67
  32. 2017Meta-Learning and Universality: Deep Representations and Gradient Descent can Approximate any Learning Algorithmcited by 65
  33. 2025Artificial Intelligence Index Report 2025cited by 64
  34. 2020A Formal Hierarchy of RNN Architecturescited by 62
  35. 2015Learning to Transduce with Unbounded Memorycited by 54
  36. 2023Memory Augmented Large Language Models are Computationally Universalcited by 47
  37. 2023Learning to Decode the Surface Code with a Recurrent, Transformer-Based Neural Networkcited by 42
  38. 2019On the Computational Power of RNNscited by 35

50 most cited of 56 All 56 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Planning with Transformers: Chain of Computation and Structured Context Windowscited by 0