# Universal Length Generalization with Turing Programs

arXiv: https://arxiv.org/abs/2407.03310 · HTML: https://mlsanity.com/paper/2407.03310/

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 48 of its 59 references that are in the map.
- First posted on arXiv 3 Jul 2024.

## Builds on (most cited first, 30 of 48)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context](https://mlsanity.com/paper/1901.02860/) (2019)
- [Solving Quantitative Reasoning Problems with Language Models](https://mlsanity.com/paper/2206.14858/) (2022)
- [Self-Attention with Relative Position Representations](https://mlsanity.com/paper/1803.02155/) (2018)
- [Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation](https://mlsanity.com/paper/2108.12409/) (2021)
- [In-context Learning and Induction Heads](https://mlsanity.com/paper/2209.11895/) (2022)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [GPT-NeoX-20B: An Open-Source Autoregressive Language Model](https://mlsanity.com/paper/2204.06745/) (2022)
- [Neural Turing Machines](https://mlsanity.com/paper/1410.5401/) (2014)
- [Textbooks Are All You Need](https://mlsanity.com/paper/2306.11644/) (2023)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [The Impact of Positional Encoding on Length Generalization in Transformers](https://mlsanity.com/paper/2305.19466/) (2023)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Compositionality decomposed: how do neural networks generalise?](https://mlsanity.com/paper/1908.08351/) (2019)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Repeat After Me: Transformers are Better than State Space Models at Copying](https://mlsanity.com/paper/2402.01032/) (2024)
- [Exploring Length Generalization in Large Language Models](https://mlsanity.com/paper/2207.04901/) (2022)
- [What Algorithms can Transformers Learn? A Study in Length Generalization](https://mlsanity.com/paper/2310.16028/) (2023)
- [Thinking Like Transformers](https://mlsanity.com/paper/2106.06981/) (2021)
- [Transformer Language Models without Positional Encodings Still Learn Positional Information](https://mlsanity.com/paper/2203.16634/) (2022)
- [On the Turing Completeness of Modern Neural Network Architectures](https://mlsanity.com/paper/1901.03429/) (2019)

## Built on by (most cited first, 25 of 25)

- [Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers](https://mlsanity.com/paper/2502.02393/) (2025)
- [Mixture of Parrots: Experts improve memorization more than reasoning](https://mlsanity.com/paper/2410.19034/) (2024)
- [Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization](https://mlsanity.com/paper/2511.07378/) (2025)
- [Ask, and it shall be given: On the Turing completeness of prompting](https://mlsanity.com/paper/2411.01992/) (2024)
- [Softmax Transformers are Turing-Complete](https://mlsanity.com/paper/2511.20038/) (2025)
- [The Role of Sparsity for Length Generalization in Transformers](https://mlsanity.com/paper/2502.16792/) (2025)
- [Beyond Single-Task: Robust Multi-Task Length Generalization for LLMs](https://mlsanity.com/paper/2502.11525/) (2025)
- [Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilities](https://mlsanity.com/paper/2505.21785/) (2025)
- [Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence](https://mlsanity.com/paper/2506.23908/) (2025)
- [Self-Verifying Reflection Helps Transformers with CoT Reasoning](https://mlsanity.com/paper/2510.12157/) (2025)
- [To Infinity and Beyond: Tool-Use Unlocks Length Generalization in State Space Models](https://mlsanity.com/paper/2510.14826/) (2025)
- [Provable Length Generalization in Sequence Prediction via Spectral Filtering](https://mlsanity.com/paper/2411.01035/) (2024)
- [The Imitation Game: Turing Machine Imitator is Length Generalizable Reasoner](https://mlsanity.com/paper/2507.13332/) (2025)
- [Probability Distributions Computed by Autoregressive Transformers](https://mlsanity.com/paper/2510.27118/) (2025)
- [On the Ability of Transformers to Verify Plans](https://mlsanity.com/paper/2603.19954/) (2026)
- [Representing Rule-based Chatbots with Transformers](https://mlsanity.com/paper/2407.10949/) (2024)
- [Exact Learning of Arithmetic with Differentiable Agents](https://mlsanity.com/paper/2511.22751/) (2025)
- [Universal computation is intrinsic to language model decoding](https://mlsanity.com/paper/2601.08061/) (2026)
- [Barriers to Universal Reasoning With Transformers (And How to Overcome Them)](https://mlsanity.com/paper/2604.25800/) (2026)
- [Learning Model Successors](https://mlsanity.com/paper/2502.00197/) (2025)
- [Position as Probability: Self-Supervised Transformers that Think Past Their Training for Length Extrapolation](https://mlsanity.com/paper/2506.00920/) (2025)
- [Loom: A Scalable Analytical Neural Computer Architecture](https://mlsanity.com/paper/2604.08816/) (2026)
- [Position: The Turing-Completeness of Autoregressive Transformers Relies Heavily on Context Management](https://mlsanity.com/paper/2605.19514/) (2026)
- [Planning with Transformers: Chain of Computation and Structured Context Windows](https://mlsanity.com/paper/2607.17710/) (2026)
- [Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers](https://mlsanity.com/paper/2608.31067/) (2026)

## Abstract (arXiv)

Length generalization refers to the ability to extrapolate from short training sequences to long test sequences and is a challenge for current large language models. While prior work has proposed some architecture or data format changes to achieve length generalization, these proposals typically apply to a limited set of tasks. Building on prior scratchpad and Chain-of-Thought (CoT) techniques, we propose Turing Programs, a novel CoT strategy that decomposes an algorithmic task into steps mimicking the computation of a Turing Machine. This framework is both universal, as it can accommodate any algorithmic task, and simple, requiring only copying text from the context with small modifications. We show that by using Turing Programs, we obtain robust length generalization on a range of algorithmic tasks: addition, multiplication and in-context SGD. We then demonstrate that transformers achieve length generalization on random Turing Programs, suggesting that length generalization is possible for any algorithmic task. Finally, we theoretically prove that transformers can implement Turing Programs, constructing a simple RASP (Weiss et al.) program that simulates an arbitrary Turing machine.