🤖 machine learning

Planning with Transformers: Chain of Computation and Structured Context Windows

This paper introduces Chain of Computation (COC), a framework that integrates a transformer-based language model into an iterative loop with a Structured Context Window (SCW) to bridge the gap between theoretical Turing-completeness and empirical planning performance, enabling small models to achieve near-perfect success on complex planning tasks like BlocksWorld and Tower of Hanoi through specialized context management and arithmetic support.

Original authors: Ehsan Futuhi, Nathan R. Sturtevant

Published 2026-07-21

📖 12 min read🧠 Deep dive

CC BY 4.0

Original authors: Ehsan Futuhi, Nathan R. Sturtevant

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a brilliant but slightly forgetful robot how to solve a complex puzzle. You might think that if you give the robot a super-smart brain (a Large Language Model, or LLM) and ask it to "just figure it out," it would succeed. But in the world of artificial intelligence, these models are like incredible pattern-matchers that sometimes struggle when asked to plan a long, multi-step journey. They are great at writing stories or chatting, but when it comes to strict logic puzzles—like moving blocks around or solving the Tower of Hanoi—they often get lost, forgetting the rules or the steps they just took. This is a big deal because if we want AI to help us with real-world tasks like organizing warehouses or navigating robots, it needs to be able to plan ahead without making silly mistakes. The big question researchers have been asking is: Is the AI actually too dumb to plan, or is it just using the wrong tool for the job?

This paper suggests that the AI isn't necessarily dumb; it's just trying to do too much at once. The authors, Ehsan Futuhi and Nathan R. Sturtevant, propose a new way of thinking called "Chain of Computation" (COC). Instead of asking the AI to write down the entire solution in one giant breath (which is like asking a human to memorize a whole book in one go), they put the AI inside a loop with a special "scratchpad" called a Structured Context Window (SCW). Think of this like a robot with a sticky note pad. Instead of trying to remember the whole plan, the robot looks at one instruction on the pad, does that one small step, writes the next instruction on the pad, and then points to where the next instruction is. It's like a game of "follow the leader" where the robot is both the leader and the follower, constantly updating its own map.

The researchers tested this idea on three classic puzzles: the Tower of Hanoi (moving disks between pegs), BlocksWorld (stacking blocks), and the Pancake Puzzle (sorting pancakes by flipping them). They found that when they gave the AI this "scratchpad" system, even relatively small AI models trained from scratch could solve these puzzles with amazing accuracy—over 99.89% success on the block and pancake puzzles. The magic trick was that the AI didn't have to remember the whole history; it just had to read the current instruction, do the math to figure out the next step, and write down where to look next.

However, the paper also discovered a specific weak spot. When the puzzles got really big (like the Tower of Hanoi with many disks), the AI started to make mistakes, but not because it forgot the plan. It turned out the AI was getting tripped up by simple math. When the robot had to calculate "disk number 7 minus 1" to figure out the next step, it sometimes got the number wrong, especially if it had never seen that specific number before. The authors showed that if they helped the AI by doing the math for it (or using a special "stack" system that doesn't require complex math), the AI could solve even the hardest versions of the Tower of Hanoi (up to 20 disks) perfectly. This suggests that the AI's planning brain is actually quite strong, but it needs a little help with the arithmetic and memory management to reach its full potential.

The Big Picture: Why AI Struggles with Planning

To understand why this paper matters, we first need to understand the two main characters in this story: Large Language Models (LLMs) and Planning.

LLMs are the super-smart AI brains you might have heard of, like the ones that write essays or code. They are trained on massive amounts of text, learning to predict the next word in a sentence. Because they've read so much, they are great at recognizing patterns. If you ask them to write a story about a dragon, they can do it because they've seen thousands of dragon stories. However, "planning" is different. Planning is like solving a maze or organizing a trip: you have to think several steps ahead, remember what you did, and make sure you don't break the rules.

For a long time, scientists noticed that while LLMs are great at chatting, they are terrible at planning. If you ask an LLM to move a stack of blocks from one place to another without dropping any, it often gives a plan that breaks the rules or forgets a step. This is frustrating because we want AI to be useful in the real world, where things need to be done in the right order.

There is a theory that LLMs are actually "Turing-complete," which is a fancy math way of saying they should be able to do any calculation a computer can do, including complex planning. But in practice, they seem to fail. The big question this paper tackles is: Why? Is the AI's brain fundamentally broken for planning, or is it just that we are asking it to do the task in the wrong way?

The Problem: The "One-Shot" Trap

Imagine you are trying to solve a Rubik's Cube. If someone asked you to write down the entire solution (the sequence of 20 or 30 moves) in one single sentence without stopping to think, you might get it wrong. You might forget the middle steps or mix up the colors.

This is what happens when we ask a standard LLM to plan. We usually give it a prompt like "Solve this puzzle," and it tries to generate the entire list of moves in one go. The paper calls this "Single-Pass, Full Context." The problem is that as the puzzle gets bigger, the list of moves gets longer. The AI has to keep all those moves in its "head" (its context window) at the same time. As the list grows, the AI starts to lose track. It's like trying to hold a conversation with a friend while also remembering a grocery list, a phone number, and a math problem all at once. Eventually, the AI gets confused, makes a mistake early on, and then the whole plan falls apart.

The authors argue that the AI isn't bad at planning; it's just bad at holding a giant, unorganized list of instructions in its head.

The Solution: The "Chain of Computation" (COC)

To fix this, the authors built a new system called Chain of Computation (COC). Instead of asking the AI to write the whole plan at once, they put the AI inside a loop.

Imagine the AI is a robot working in a factory. Instead of giving the robot a giant blueprint of the whole factory, you give it a Structured Context Window (SCW). Think of the SCW as a long roll of paper tape, like the old paper tapes used in old computers or a very long sticky note.

Here is how the robot works with this new system:

Read: The robot looks at the very first instruction on the tape.
Think: It figures out what to do next based on that one instruction.
Write: It writes a new instruction on the end of the tape.
Point: It writes down a "pointer" (like an arrow) that says, "Go look at the instruction right after this one."
Repeat: The robot moves its "eye" to the new instruction and does it again.

The robot never has to remember the whole plan. It only has to focus on the current instruction and decide what to do next. It's like a game of "Follow the Leader" where the robot is constantly updating the map for itself.

The paper introduces a special tool called a pointer. This pointer tells the robot exactly which part of the tape to look at next. This is crucial because it keeps the robot's "attention" focused on a small, manageable piece of information, rather than drowning it in a sea of text.

The Experiments: Testing the Robot

The authors tested this new robot on three famous puzzles to see if it could learn to plan better.

1. BlocksWorld
This is a puzzle where you have a bunch of blocks stacked on a table, and you need to rearrange them into a specific shape. You can only move the top block of a stack.

The Result: The robot was incredibly good at this. Even when the puzzle got very complex (with 40 blocks), the robot solved it perfectly 100% of the time. It learned the strategy of "unstack everything, then restack it" and could apply it to any new arrangement of blocks it had never seen before.

2. The Pancake Puzzle
In this puzzle, you have a stack of pancakes of different sizes. You can only flip the top part of the stack (like flipping a pancake in a pan) to rearrange them. The goal is to get them sorted by size.

The Result: Similar to BlocksWorld, the robot did amazingly well. It solved almost every puzzle, even with 40 pancakes. The only time it "failed" was when the pancakes were already sorted, and it tried to flip them anyway. But since flipping them and flipping them back didn't hurt the final result, it still reached the goal. This showed the robot had learned the core logic of the puzzle.

3. Tower of Hanoi (TOH)
This is the hardest puzzle. You have three pegs and a stack of disks of different sizes. You have to move the whole stack from one peg to another, but you can never put a big disk on top of a small one. The number of moves needed grows exponentially (it gets huge very fast).

The Result: Here, the robot was good, but not perfect. It solved about 92% of the puzzles when the disks were small (up to 15 disks). But as the puzzles got harder, it started to make mistakes.

The Mystery: Why Did the Robot Fail?

The authors didn't just stop at "it worked." They wanted to know why it failed on the hardest puzzles. They looked closely at the mistakes the robot made on the Tower of Hanoi.

They found that the robot wasn't failing because it didn't understand the plan. It knew exactly which disk to move and where to put it. The problem was math.

To keep track of the plan, the robot had to do simple arithmetic, like "If I have 7 disks, I need to move the top 6 first." It had to calculate "7 minus 1" to get "6." The paper found that when the robot encountered a number it had never seen before (like a very large disk number), it would get the math wrong. It might calculate "7 minus 1" as "5" or "8," and then the whole plan would go off the rails.

This was a huge discovery. It meant the robot's "planning brain" was actually working perfectly. The failure wasn't in the logic; it was in the calculator.

The Fix: Helping with Math and Memory

To prove this, the authors tried two different fixes:

Fix 1: Symbolic Math
They told the robot to stop trying to do the math itself. Instead, they gave it "symbolic" instructions. For example, instead of saying "Move disk 6," the robot would say "Move disk (n-1)." Then, a separate, simple computer program (an arithmetic module) would do the actual math and tell the robot the real number.

The Result: When they did this, the robot's success rate went up. It could solve the puzzles perfectly because it didn't have to worry about getting the numbers wrong. This proved that the planning part was fine; the math was the bottleneck.

Fix 2: The Stack (PDA)
The authors realized that for the Tower of Hanoi, the robot didn't even need to jump around the tape looking for different instructions. It only needed to look at the top of the stack and add new instructions to the top. This is exactly how a "Stack" works in computer science (Last-In, First-Out).
They reformulated the robot's job to act like a Deterministic Pushdown Automaton (PDA). This is a fancy term for a machine that only uses a stack.

The Result: With this new setup, the robot solved 100% of the Tower of Hanoi puzzles, even with 20 disks (which requires over 1 million moves!). It didn't need to do complex math to find the next instruction because the stack handled it automatically.

What This Means

This paper suggests that Large Language Models are not inherently bad at planning. The problem was that we were asking them to do everything at once: remember the whole plan, do the math, and figure out the next step, all while staring at a giant wall of text.

By breaking the task down into small, iterative steps and giving the AI a "scratchpad" (the SCW) to manage its memory, the AI can learn to plan very effectively. The paper shows that even small AI models, trained from scratch, can learn complex planning strategies if they are given the right tools.

The key takeaway is that the AI's "reasoning" is strong, but its "arithmetic" and "memory management" need help. If we separate the planning logic from the math and give the AI a structured way to manage its steps, it can solve problems that were previously thought to be too hard.

The authors conclude that while they have made a big step forward, there is still more to learn. They want to investigate exactly how the "pointer" system helps the AI and whether this method can be used for even more complex, real-world planning tasks in the future. But for now, they have shown that with a little bit of structure, AI can be a very good planner indeed.

Technical Summary: Planning with Transformers: Chain of Computation and Structured Context Windows

Problem Statement

Despite the theoretical finding that Transformer-based Large Language Models (LLMs) are Turing-complete and capable of universal computation, empirical studies demonstrate that they struggle to reliably solve planning problems, particularly when compared to classical planners. While LLMs excel in conversational agents, code generation, and reasoning benchmarks, they often fail on multi-step decision-making tasks (e.g., BlocksWorld, Tower of Hanoi) that humans find trivial. Existing approaches, such as Chain-of-Thought (CoT) prompting or integrating LLMs with search algorithms (e.g., MCTS), often suffer from error accumulation, inefficient context usage, and an inability to generalize to unseen problem complexities. A critical gap exists between the theoretical computational power of the Transformer architecture and its practical performance in planning domains.

Methodology: Chain of Computation (COC)

The authors propose the Chain of Computation (COC) architecture to bridge this gap. Unlike standard planning where an LLM generates a full plan in a single pass, COC places the LLM inside an iterative loop, leveraging its strength as a pattern-matching system rather than a global planner.

Core Components

Structured Context Window (SCW): An external memory mechanism that acts as a constant-sized context window for the model. Initially implemented as an append-only tape, it stores instructions and outputs.
Pointer Mechanism: At each iteration, the LLM receives only the specific instruction pointed to by a pointer ( $p$ ) within the SCW, rather than the entire accumulated history. This ensures the input size remains constant regardless of the planning horizon.
Iterative Execution:
- The process begins with an initial instruction (e.g., SOLVE(start, goal)) at position 0.
- The LLM reads the instruction at pointer $p$ $p$ and generates three outputs:
  1. New Instructions: To be written to the SCW.
  2. Actions: The specific move to be executed.
  3. Next Pointer ( $p_{next}$ ): The index of the next instruction to process.
- The process terminates when the model generates a pointer value of $-1$.
- The final solution is the sequence of actions extracted from the SCW.

Learning Objectives

Within this architecture, the LLM is trained to learn three distinct modules:

Planning Policy ( $\pi$ ): Generating the next action given the current state.
World Model ( $T$ ): Predicting the next state (or state transitions).
Arithmetic Operations: Updating pointers and managing indices.

The training objective involves optimizing instruction-output pairs to generalize these modules to unseen variables and problem instances.

Experimental Setup

The authors evaluated COC on three planning domains:

Tower of Hanoi (TOH): A recursive problem with exponential solution length ( $2^n - 1$ ).
BlocksWorld: A linear complexity problem involving stacking and unstacking blocks.
Pancake Puzzle: A combinatorial problem involving prefix flips to sort pancakes.

Models were decoder-only Transformers trained from scratch using standard next-token prediction. Experiments varied the number of training instances and the complexity (number of disks/blocks/pancakes) to test generalization.

Key Results

1. High Success Rates and Generalization

BlocksWorld & Pancake Puzzle: Models trained on a small number of instances (e.g., 500 random configurations) achieved success rates exceeding 99.89% on unseen test instances across all complexity levels (up to $n=40$ ). Even with only 30 training instances, performance remained high, significantly outperforming larger pretrained reasoning models in prior literature.
Extended BlocksWorld: The model generalized to initial states with multiple stacks (a more complex combinatorial space), maintaining a 99.89% success rate.
Tower of Hanoi: The model achieved an average success rate of 92% on instances with 1 to 15 disks, even when a significant portion of training data (up to 35%) was held out.

2. Failure Analysis

Analysis of failure cases in TOH revealed that errors were rarely due to a failure in the planning policy itself. Instead, failures stemmed from:

Arithmetic Errors: Incorrect calculation of pointer updates or disk indices.
Unseen Tokens: Encountering numbers or instruction indices not present in the training distribution.

3. Mitigation Strategies

Symbolic Arithmetic: By separating the planning logic from arithmetic operations (using symbolic placeholders for the LLM and an external module for calculation), the model maintained 100% success on TOH instances up to 20 disks. Crucially, while the solution length grows exponentially with $n$ , the required additional training data grew only linearly.
Pushdown Automaton (PDA) Formulation: The authors observed that TOH only requires stack-like operations (push/pop) rather than random access via pointers. Reformulating the SCW as a deterministic PDA (where the pointer always points to the top of the stack) eliminated the need for complex pointer arithmetic. This formulation achieved 100% success on all TOH instances up to 20 disks (requiring over 1 million actions) with minimal training data.

Significance and Claims

The paper claims that the primary limitation of LLMs in planning is not an inherent inability to learn planning algorithms, but rather the difficulty in managing long-horizon state updates and arithmetic operations within a standard autoregressive context window.

Architectural Insight: The COC architecture demonstrates that by restricting the context to a constant size and using an external pointer mechanism, small models trained from scratch can learn complex iterative algorithms and generalize to unseen problem sizes.
Theoretical vs. Empirical: The work provides empirical evidence supporting the theoretical claim that Transformers are Turing-complete, showing that with the right inductive bias (iterative loops and structured memory), they can execute universal computation.
Efficiency: The pointer mechanism significantly reduces computational costs per iteration compared to standard approaches where context size grows linearly with the plan length.
Modest Scope: The authors emphasize that while COC solves these specific planning domains effectively, the approach relies on the problem being decomposable into iterative steps with a structured memory interface. They do not claim COC solves all planning problems or that it eliminates the need for reasoning in all contexts, but rather that it addresses the specific gap between theoretical capability and empirical planning performance.

The paper concludes that the "planning policy" is learnable by LLMs, but the "execution mechanism" (arithmetic and memory management) often requires external support or architectural simplifications (like the PDA formulation) to achieve robustness.