# Planning with Transformers: Chain of Computation and Structured Context Windows

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 61 of its 74 references that are in the map.
- First posted on arXiv 20 Jul 2026.

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

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Evaluating Large Language Models Trained on Code](https://mlsanity.com/paper/2107.03374/) (2021)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [Neural Machine Translation of Rare Words with Subword Units](https://mlsanity.com/paper/1508.07909/) (2015)
- [Efficiently Modeling Long Sequences with Structured State Spaces](https://mlsanity.com/paper/2111.00396/) (2021)
- [Shortcut Learning in Deep Neural Networks](https://mlsanity.com/paper/2004.07780/) (2020)
- [Challenging BIG-Bench Tasks and Whether Chain-of-Thought Can Solve Them](https://mlsanity.com/paper/2210.09261/) (2022)
- [SWE-agent: Agent-Computer Interfaces Enable Automated Software Engineering](https://mlsanity.com/paper/2405.15793/) (2024)
- [Qwen2.5-Coder Technical Report](https://mlsanity.com/paper/2409.12186/) (2024)
- [BloombergGPT: A Large Language Model for Finance](https://mlsanity.com/paper/2303.17564/) (2023)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Reasoning with Language Model is Planning with World Model](https://mlsanity.com/paper/2305.14992/) (2023)
- [Faith and Fate: Limits of Transformers on Compositionality](https://mlsanity.com/paper/2305.18654/) (2023)
- [On the Planning Abilities of Large Language Models : A Critical Investigation](https://mlsanity.com/paper/2305.15771/) (2023)
- [The Illusion of Thinking: Understanding the Strengths and Limitations of Reasoning Models via the Lens of Problem Complexity](https://mlsanity.com/paper/2506.06941/) (2025)
- [Chain of Thought Empowers Transformers to Solve Inherently Serial Problems](https://mlsanity.com/paper/2402.12875/) (2024)
- [Looped Transformers as Programmable Computers](https://mlsanity.com/paper/2301.13196/) (2023)
- [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)
- [Stream of Search (SoS): Learning to Search in Language](https://mlsanity.com/paper/2404.03683/) (2024)
- [Training Language Models with Memory Augmentation](https://mlsanity.com/paper/2205.12674/) (2022)
- [Looped Transformers for Length Generalization](https://mlsanity.com/paper/2409.15647/) (2024)
- [Algorithm of Thoughts: Enhancing Exploration of Ideas in Large Language Models](https://mlsanity.com/paper/2308.10379/) (2023)
- [Navigation with Large Language Models: Semantic Guesswork as a Heuristic for Planning](https://mlsanity.com/paper/2310.10103/) (2023)

## Abstract (arXiv)

Large Language Models (LLMs) have had a remarkable impact across many areas of machine learning. However, recent studies have shown that they struggle to reliably solve planning problems, particularly when compared with classical planners. Even with recent advances in reasoning-oriented models, the extent to which LLMs can genuinely perform planning remains an open question. At the same time, theoretical results have shown that transformers, the core architecture underlying modern LLMs, are Turing-complete. In this work, we investigate this apparent gap between the theoretical computational power of LLMs and their empirical planning performance. We propose Chain of Computation (COC), a computational architecture that places a transformer-based LM inside an iterative loop and leverages its strength as a pattern-matching system. COC uses a Structured Context Window (SCW) as external memory, allowing the model to access only the portion of the accumulated context required at each planning step and thereby maintain an approximately constant input size. Within this architecture, the LM learns the planning policy and world model and performs the arithmetic operations required during planning. We show that relatively small LMs trained from scratch can learn planning procedures from a small number of training instances and generalize to unseen problems, achieving success rates above 99% on BlocksWorld and the Pancake puzzle. We further show that COC can be formulated as a pushdown automaton (PDA). This formulation can solve Tower of Hanoi (TOH) instances with up to 20 disks and enables the planner to execute the depth-first search (DFS) algorithm. Theoretically, we characterize how the accumulation of irrelevant context increases planning failure probability under the standard full-context setup and how the SCW mitigates this effect.