Planning with Transformers: Chain of Computation and Structured Context Windows

arXiv:2607.17710 · cs.LG · Submitted 2026-07-20 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Planning with Transformers".

Jane: The gist The Chain of Computation (COC) architecture investigates the gap between theoretical computational power and empirical performance of Large Language Models on planning tasks by placing an LM inside…

Tom: First, who's behind it and why it matters.

Title and authors: Tom: The paper is titled "Planning with Transformers: Chain of Computation and Structured Context Windows," and it's written by Ehsan Futuhi, Nathan R. Sturtevant, and others from the University of Alberta’s AImi.

Jane: It seems like they are directly tackling that question we discussed—the gap between what transformers are theoretically capable of doing as universal computers and what they can actually do when it comes to real-world planning problems.

Lu: The authors frame it by suggesting that transformers, because they are Turing-complete, can compute anything in principle, so the focus shifts to how we structure their interaction with the problem.

Meng: It’s about moving from a single pass where you dump everything into the context window to this iterative process where things are broken down into manageable chunks.

Lalam: The authors are essentially proposing a computational architecture that uses an external memory, which they call the Structured Context Window, to guide the model through these steps.

The paper's summary: Tom: So what’s the actual mechanism? They propose COC where each step involves reading from and generating outputs to this SCW, which acts like external memory for the planning process itself.

Jane: At each iteration, the model gets a single context window along with some local information, and it produces three things: new instructions for the SCW, the actions to take right now, and a pointer indicating where to look next.

Lu: That pointer is generated by the model itself; it’s what lets the AI decide which part of that external memory to access in its next step of computation.

Meng: The whole planning process starts at position zero of the SCW and keeps going until the model generates a specific pointer, which they call 'pt equals negative one'.

Lalam: So instead of just trying to write out a full plan at once, the model is essentially acting like an agent that reads its own instructions from this window repeatedly until it’s done.

The paper's improvements: Tom: One big improvement they highlight is how this iterative approach helps with generalization across different planning domains. They show good performance on BlocksWorld and the Pancake Puzzle, achieving average success rates exceeding ninety-nine point eight nine percent.

Jane: That’s impressive when you think about the complexity of those problems; they train on a relatively small number of instances at each difficulty level, and it still generalizes well to unseen problems.

Lu: The paper also looks at Tower of Hanoi, where they find that failures often come from arithmetic operations or seeing tokens they haven't seen before during training.

Meng: They suggest that separating the planning part from the arithmetic operations helps a lot; if you treat those things independently, you need much less extra training data to maintain good performance.

Lalam: This suggests that the errors we see in TOH aren't necessarily because the planning loop itself is flawed, but more about how the model handles those specific calculations or new symbols.

Conclusion: Tom: So, to wrap up, the main implication of "Planning with Transformers: Chain of Computation and Structured Context Windows" is that this iterative architecture can bridge the gap between theoretical power and practical planning performance.

Jane: They show that by structuring the context window as external memory controlled by a pointer, we can make LLMs much more reliable for complex sequential tasks like planning.

Lu: The paper demonstrates that this method works well because it allows the model to manage its own sequence of operations dynamically through that structured context.

Meng: From an engineering standpoint, the efficiency gain is also notable; because the input size at each step stays about constant, you don't have to deal with context windows growing exponentially with the solution length.

Lalam: And they showed that for problems like Tower of Hanoi up to twenty disks, they can achieve a perfect success rate by formulating it as a deterministic pushdown automaton that only uses push and pop operations on the SCW.

Tom: It’s a neat way to look at it, moving from just letting the model generate text to giving it an explicit memory structure for its planning logic. That sets up some interesting directions for how we approach reasoning with these models in the future.

Ehsan Futuhi, Nathan R. Sturtevant

Department of Computing Science, University of Alberta · Alberta Machine Intelligence Institute (Amii

cs.LG

Submitted: 2026-07-20

Updated: 2026-10-09

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 81/100

The gist: The gist The Chain of Computation (COC) architecture investigates the gap between theoretical computational power and empirical performance of Large Language Models on planning tasks by placing an LM

Key concepts

Chain of Computation (COC): This architecture places an LM inside a repeating loop to learn planning. In each step, the LM receives instructions, performs actions, and updates its knowledge base. This allows the model to build plans incrementally rather than trying to solve everything in one go.
Structured Context Window (SCW): The SCW is an external memory that holds the planning knowledge, including policies and arithmetic operations. The LM loads this memory at each step, allowing it to reference past learning and context while generating new instructions for the next action.
Deterministic Pushdown Automaton (PDA): The TOH planner can be modeled as a PDA, which is a formal computational model. This formulation shows that the planning process only requires push and pop operations on the SCW, eliminating complex pointer management and achieving perfect success rates for problems up to 20 disks.

Terminology

Transformer — 3× in this paper · explained in 2 episodes
Chain of Computation — 2× in this paper
Structured Context Window — 2× in this paper
Core — 1× in this paper · explained in 2 episodes
Large Language Models (LLMs) — 1× in this paper · explained in 8 episodes
Tower of Hanoi — 1× in this paper
World Model — 1× in this paper · explained in 7 episodes

Summary

The gist The Chain of Computation (COC) architecture investigates the gap between theoretical computational power and empirical performance of Large Language Models on planning tasks by placing an LM inside an iterative loop leveraging a Structured Context Window (SCW) to learn planning policies, world models, and arithmetic operations.

Chain of Computation Architecture

The COC architecture places a transformer-based LM inside an iterative loop, leveraging its strength as a pattern-matching system rather than requiring it to generate complete plans in a single pass The planning procedure is formulated as an iterative loop, where each iteration corresponds to a single prompt to the LM, following its standard autoregressive execution The LM’s context window is loaded from an external memory called the structured context window (SCW) At each iteration, the LM receives the current instruction and produces three outputs: (i) the new instructions to be written to the SCW, (ii) the actions to be executed at the current step, and (iii) a pointer indicating the next instruction to be processed. The process terminates when pt = −1.

Planning Domains and Performance

The work provides extensive evaluations on three planning domains: BlocksWorld, Tower of Hanoi (TOH), and the Pancake Puzzle In BlocksWorld and the Pancake Puzzle, training on a relatively small number of problem instances at each complexity level is sufficient for the model to generalize to unseen problem instances across all complexity levels, achieving average success rates exceeding 99.89%. For TOH, the model can generalize to unseen instructions held out during training, achieving an average success rate of 92% on problems ranging from 1 to 15 disks.

Failure Analysis in Tower of Hanoi

An analysis of failure cases in Tower of Hanoi (TOH) reveals that they arise from arithmetic operations or from encountering previously unseen tokens. The model 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. The analysis of failure cases in TOH reveals that they arise from arithmetic operations or from encountering previously unseen tokens.

Separating Planning from Arithmetic

The results in Figure 3 show that holding out the same percentage of training data can lead to different levels of generalization depending on which prompt–target pairs are excluded from training. In this experiment, we separate the planning and arithmetic operations so that they are handled independently. As shown in the figure, the solution length grows exponentially with the number of disks n, while the amount of additional training data required to maintain perfect performance grows only linearly. This stark contrast provides further evidence that the primary source of failures observed in the original TOH experiments is not the planning procedure itself, but rather inaccuracies in the arithmetic operations required to update the pointers.

Deterministic Pushdown Automaton Formulation

The formulation of the TOH planner as a PDA, together with a complete example of the corresponding prompt–target pairs, is provided in Appendix G. This PDA formulation eliminates the need for pointer operations and achieves a perfect success rate on all TOH problem instances up to 20 disks. The planner can be formulated as a deterministic pushdown transducer (Aho & Ullman, 1969).

Efficiency and Cost Reduction

The pointer mechanism not only provides concise inputs to the LM but also significantly reduces computational cost. Consider a planning task that requires generating noutput tokens. In a standard autoregressive setup (e.g. Lehnert et al. (2024)), the model processes an input whose size grows from nprompt to nprompt + noutput as more tokens are generated, eventually approaching the maximum context length. In contrast, the proposed pointer mechanism ensures that the model receives inputs of approximately constant size, determined only by the current instruction being processed. As a result, even for long planning horizons, the computational cost per iteration remains nearly constant.

Conclusion on Limitations

We later show that planning for TOH does not require pointers and that the only operations needed on the SCW are push and pop. Consequently, the planner can be formulated as a deterministic pushdown automaton (PDA). This PDA formulation eliminates the need for pointer operations and achieves a perfect success rate on all TOH problem instances up to 20 disks. The context-window curve measures the initial prompt plus all model-generated text up to that step, while the prompt-size curve measures the prompt at the current step. This demonstrates that the size of the prompt passed to the language model remains nearly constant throughout planning for TOH and the Pancake Puzzle, while the total context window grows linearly with the solution length. The context-window curve measures the initial prompt plus all model-generated text up to that step, while the prompt-size curve measures the prompt at each planning step. This demonstrates that the size of the prompt passed to the language model remains nearly constant throughout planning for TOH and the Pancake Puzzle, while the total context window grows linearly with the solution length. The context-window curve measures the initial prompt plus all model-generated text up to that step, while the prompt-size curve measures the prompt at each planning step. This demonstrates that the size of the prompt passed to the language model remains nearly constant throughout planning for TOH and the Pancake Puzzle, while the total context window grows linearly with the solution length. The context-window curve measures the initial prompt plus all model-generated text up to that step, while the prompt-size curve measures the prompt at each planning step. This demonstrates that the size of the prompt passed to the language model remains nearly constant throughout planning for TOH and the Pancake Puzzle, while the total context window grows linearly with the solution length. The context-window curve measures the initial prompt plus all model-generated text up to that step, while the prompt-size curve measures the prompt at each planning step. This demonstrates that the size of the prompt passed to the language model remains nearly constant throughout planning for TOH and the Pancake Puzzle, while the total context window grows linearly with the solution length. The context-window curve measures the initial prompt plus all model-generated text up to that step, while the prompt-size curve measures the prompt at each planning step. This demonstrates that the size of the prompt passed to the language model remains nearly constant throughout planning for TOH and the Pancake Puzzle, while the total context window grows linearly with the solution length. The context-window curve measures the initial prompt plus all model-generated text up to that step, while the prompt-size curve measures the prompt at each planning step. This demonstrates that the size of the prompt passed to the language model remains nearly constant throughout planning for TOH and the Pancake Puzzle, while the total context window grows linearly with the solution length. The context-window curve measures the initial prompt plus all model-generated text up to that step, while the prompt-size curve measures the prompt at each planning step. This demonstrates that the size of the prompt passed to the language model remains nearly constant throughout planning for TOH and the Pancake Puzzle, while the total context window grows linearly with the solution length.

Improvements for AI systems

Bold Header: Chain of Computation (COC) Architecture Implementation

The improved system will leverage COC to place a transformer-based LM inside an iterative loop using a Structured Context Window (SCW) with a pointer mechanism that allows the model to determine which part of the SCW to access in the next step, mitigating performance degradation as complexity increases.

Bold Header: Robust Generalization Across Problem Instances

The system can achieve high success rates on unseen instances by training on a relatively small number of problem instances at each complexity level, as shown in the results for BlocksWorld and the Pancake Puzzle, achieving average success rates exceeding 99.89% in those domains.

Bold Header: Symbolic Arithmetic Integration for TOH

For Tower of Hanoi (TOH) problems, the system can maintain 100% success rate on all TOH problem instances up to 20 disks by separating planning from arithmetic operations, as demonstrated when arithmetic operations on previously unseen numbers and unseen tokens are the primary sources of errors.

Bold Header: Deterministic Pushdown Automaton Formulation

The system can be formulated as a deterministic pushdown automaton (PDA) for TOH planning, eliminating the need for pointer operations entirely by using only push and pop operations to interact with the SCW, which achieves a perfect success rate on all TOH problem instances up to 20 disks.

Bold Header: Constant Computational Cost per Iteration

The system ensures efficient long-horizon planning because the amount of information processed by the language model at each planning step remains approximately constant, contrasting with previous methods where all tokens in the context participate in the attention computation, thus keeping computational cost per step nearly constant.

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, 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.