ResearchPod Summary
Large Language Models (LLMs) often struggle with multi-step planning, frequently failing to generalize to complex problem instances even when they can solve simpler ones. This paper investigates the gap between the theoretical Turing-completeness of transformer architectures and their empirical limitations in planning. The authors ask whether placing a transformer inside an iterative loop with an external, structured memory can enable it to learn robust planning policies that generalize across problem complexities.
Instead of generating an entire plan in a single pass, the authors propose the Chain of Computation (COC) architecture. This system treats the language model (LM) as a pattern-matching engine that operates within an iterative loop. The architecture uses a Structured Context Window (SCW)—an external memory similar to a Turing machine tape—that stores instructions and state information.
At each step, the LM reads a specific instruction from the SCW, generates the next action, writes new instructions to the tape, and outputs a pointer to the next instruction. This approach keeps the input context size constant, preventing the performance degradation typically associated with growing context windows in long-horizon planning. The model is trained to learn three core components: the planning policy, the world model, and the arithmetic operations required to manage the pointer.
By training on a small number of problem instances, the COC architecture achieves high success rates (exceeding 99.89%) on BlocksWorld and the Pancake puzzle. In the more challenging Tower of Hanoi (TOH) domain, the model successfully solved instances with up to 20 disks, requiring over 1 million actions. The authors found that failure cases in TOH were primarily linked to arithmetic errors or encountering novel tokens. They demonstrate that these failures can be mitigated by providing symbolic support for arithmetic or by reformulating the SCW as a deterministic pushdown automaton (PDA), which simplifies memory access and reduces the training data requirements.
This work suggests that the planning failures of LLMs are not necessarily due to a lack of inherent reasoning capacity, but rather due to the limitations of standard autoregressive, single-pass generation. By decoupling the reasoning process from the constraints of a fixed, growing context window, the COC architecture demonstrates that even relatively small models can perform complex, long-horizon planning tasks reliably.
AI-generated third-party summary by ResearchPod. Not official content or an endorsement by the paper authors or affiliated organizations.