Planning with Transformers: Chain of Computation and Structured Context Windows

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.