Planning with Transformers: Chain of Computation and Structured Context Windows

• URL: http://arxiv.org/abs/2607.17710v1
• Date: Mon, 20 Jul 2026 09:06:15 GMT
• Title: Planning with Transformers: Chain of Computation and Structured Context Windows
• Abstract summary: Large Language Models (LLMs) have had a remarkable impact across many areas of machine learning.<n>Recent studies have shown that they struggle to reliably solve planning problems.<n> theoretical results have shown that transformers, the core architecture underlying modern LLMs, are Turing-complete.
• Score: 8.408138419383747
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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. 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, leveraging its strength as a pattern-matching system. The COC uses a Structured Context Window (SCW) which provides a constant-sized context window with support for choosing which window is used at each planning step. Within this architecture, the LM is able to learn a planning policy, predicts the world model, and performs the arithmetic operations required during planning. We show that, when given an append-only SCW (resembling a Turing Machine tape), even relatively small LMs trained from scratch can learn planning policies and generalize from a small number of training instances within each planning domain, achieving success rates above 99.89\% on BlocksWorld and the Pancake puzzle. Our analysis of failure cases in Tower of Hanoi (TOH) reveals that they arise from arithmetic operations or from encountering previously unseen tokens. We show that COC can solve TOH problem instances with up to 20 disks, requiring over 1 million actions, while requiring substantially less training data by either (1) planning with symbolical support for arithmetic or by (2) using a deterministic pushdown automaton (PDA) formulation for the SCW.

Related papers

• Model-Native Computing Architecture: Envisioning Future System Architecture Through the Lens of Computer Architecture [3.6606890511372705]
  Large language models are undergoing a transition from model technology to system technology.<n> recurring engineering problems increasingly resemble classical computer systems problems.<n>We map concepts from computer architecture to the emerging model-native stack.
  arXiv  Detail & Related papers  (2026-05-29T19:20:16Z)
• Beyond Test-Time Training: Learning to Reason via Hardware-Efficient Optimal Control [86.63490309209378]
  We formulate reasoning as optimal control and introduce the Test-Time Control layer, which performs finite-horizon LQR planning over latent states at inference time.<n>We demonstrate that embedding optimal control as an architectural layer provides an effective and scalable mechanism for reasoning beyond test-time training.
  arXiv  Detail & Related papers  (2026-03-10T05:42:13Z)
• A Small-Scale System for Autoregressive Program Synthesis Enabling Controlled Experimentation [4.499832265081113]
  We present a system called Cadmus which includes an integer virtual machine (VM), a dataset composed of true programs of diverse tasks, and an autoregressive transformer model that is trained for under $200 of compute cost.<n>The system can be used to study program completion, out-of-distribution representations, inductive reasoning, and instruction following in a setting where researchers have effective and affordable fine-grained control of the training distribution.
  arXiv  Detail & Related papers  (2026-02-09T19:03:04Z)
• Language Model Planning from an Information Theoretic Perspective [31.323156960716826]
  decoder-only language models (LMs) organize intermediate computations to support coherent long-range generation.<n>Planning involves structuring computations over long horizons, considering multiple possible continuations, and selectively reusing past information.<n>We study planning in LMs across synthetic grammar, path-finding tasks, and natural language datasets.
  arXiv  Detail & Related papers  (2025-09-28T01:58:15Z)
• Computational Thinking Reasoning in Large Language Models [69.28428524878885]
  Computational Thinking Model (CTM) is a novel framework that incorporates computational thinking paradigms into large language models (LLMs)<n>Live code execution is seamlessly integrated into the reasoning process, allowing CTM to think by computing.<n>CTM outperforms conventional reasoning models and tool-augmented baselines in terms of accuracy, interpretability, and generalizability.
  arXiv  Detail & Related papers  (2025-06-03T09:11:15Z)
• Self-Steering Language Models [113.96916935955842]
  DisCIPL is a method for "self-steering" language models (LMs)<n>DisCIPL generates a task-specific inference program that is executed by a population of Follower models.<n>Our work opens up a design space of highly-parallelized Monte Carlo inference strategies.
  arXiv  Detail & Related papers  (2025-04-09T17:54:22Z)
• Plan-over-Graph: Towards Parallelable LLM Agent Schedule [53.834646147919436]
  Large Language Models (LLMs) have demonstrated exceptional abilities in reasoning for task planning.<n>This paper introduces a novel paradigm, plan-over-graph, in which the model first decomposes a real-life textual task into executable subtasks and constructs an abstract task graph.<n>The model then understands this task graph as input and generates a plan for parallel execution.
  arXiv  Detail & Related papers  (2025-02-20T13:47:51Z)
• Interactive and Expressive Code-Augmented Planning with Large Language Models [62.799579304821826]
  Large Language Models (LLMs) demonstrate strong abilities in common-sense reasoning and interactive decision-making. Recent techniques have sought to structure LLM outputs using control flow and other code-adjacent techniques to improve planning performance. We propose REPL-Plan, an LLM planning approach that is fully code-expressive and dynamic.
  arXiv  Detail & Related papers  (2024-11-21T04:23:17Z)
• Supervised Chain of Thought [5.389461633686935]
  Chain of Thought (CoT) prompting offers a promising approach to solving complex reasoning tasks. One-prompt-for-all approach poses significant challenges for models to generate the correct reasoning steps. We show how task-specific supervision is essential for navigating the prompt space accurately and achieving optimal performance.
  arXiv  Detail & Related papers  (2024-10-18T06:25:27Z)
• Executing Arithmetic: Fine-Tuning Large Language Models as Turing Machines [7.695524275630717]
  Large Language Models (LLMs) have demonstrated remarkable capabilities across a wide range of natural language processing and reasoning tasks. We propose a Composable Arithmetic Execution Framework (CAEF) that enables LLMs to learn to execute step-by-step computations by emulating Turing Machines. In our evaluation, CAEF achieves nearly 100% accuracy across seven common mathematical operations on the LLaMA 3.1-8B model.
  arXiv  Detail & Related papers  (2024-10-10T13:23:49Z)
• Unlocking Reasoning Potential in Large Langauge Models by Scaling Code-form Planning [94.76546523689113]
  We introduce CodePlan, a framework that generates and follows textcode-form plans -- pseudocode that outlines high-level, structured reasoning processes. CodePlan effectively captures the rich semantics and control flows inherent to sophisticated reasoning tasks. It achieves a 25.1% relative improvement compared with directly generating responses.
  arXiv  Detail & Related papers  (2024-09-19T04:13:58Z)
• Nl2Hltl2Plan: Scaling Up Natural Language Understanding for Multi-Robots Through Hierarchical Temporal Logic Task Representation [8.180994118420053]
  Nl2Hltl2Plan is a framework that translates natural language commands into hierarchical Linear Temporal Logic (LTL)<n>First, an LLM transforms instructions into a Hierarchical Task Tree, capturing logical and temporal relations.<n>Next, a fine-tuned LLM converts sub-tasks into flat formulas, which are aggregated into hierarchical specifications.
  arXiv  Detail & Related papers  (2024-08-15T14:46:13Z)
• A General Framework for Learning from Weak Supervision [93.89870459388185]
  This paper introduces a general framework for learning from weak supervision (GLWS) with a novel algorithm. Central to GLWS is an Expectation-Maximization (EM) formulation, adeptly accommodating various weak supervision sources. We also present an advanced algorithm that significantly simplifies the EM computational demands.
  arXiv  Detail & Related papers  (2024-02-02T21:48:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.