🤖 AI

On the Ability of Transformers to Verify Plans

This paper introduces C*-RASP to theoretically establish that decoder-only transformers can provably learn to verify long plans in classical planning domains despite simultaneous growth in sequence length and vocabulary size, a finding supported by empirical experiments.

Original authors: Yash Sarrof, Yupei Du, Katharina Stein, Alexander Koller, Sylvie Thiébaux, Michael Hahn

Published 2026-03-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yash Sarrof, Yupei Du, Katharina Stein, Alexander Koller, Sylvie Thiébaux, Michael Hahn

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 teaching a very smart, but slightly literal-minded robot assistant how to check if a set of instructions (a "plan") will actually get a job done. Maybe the job is moving boxes from Room A to Room B, or turning off all the lights in a grid.

This paper is about figuring out when this robot can learn to check long, complicated instructions just by practicing on short, simple ones, and when it will inevitably get confused.

Here is the breakdown using some everyday analogies:

1. The Problem: The Robot Gets Lost in Long Stories

You might think, "If I teach a robot how to move a box from one room to another, it should be able to move it across a whole city."

But in the world of AI planning, robots (specifically Transformers, the brains behind models like me) often fail at this. If you train them on short plans (3 steps), they often crash and burn when you ask them to verify a long plan (100 steps). They lose track of the "story," forget where the robot is, or suggest actions that don't make sense.

The authors asked: Why does this happen? Is it because the plan is too long, or is it because the type of plan is too tricky?

2. The New Tool: A "Universal Translator" for Growing Worlds

To answer this, the researchers invented a new mathematical framework called C-RASP*.

Think of C-RASP (the old version) as a rulebook for a game played with a fixed set of Lego bricks. You know exactly which bricks you have.

The Problem: In real life, the number of objects (bricks) can grow. Maybe you start with 5 balls, but the test requires 500. The old rulebook couldn't handle a changing number of bricks.

C-RASP* is like upgrading that rulebook. It allows the robot to learn rules that work whether you have 5 balls or 5,000. It teaches the robot to focus on the pattern of the instructions rather than memorizing specific object names.

3. The Big Discovery: It's About the "Rules of the Game"

The paper found that the robot's ability to generalize (learn from short to long) depends entirely on the structure of the planning domain. They identified two types of worlds:

🟢 The "Well-Behaved" Worlds (Good News!)

In these worlds, every action has a clear, predictable effect.

The Analogy: Imagine a game of Tic-Tac-Toe. If you place an 'X', it stays an 'X'. It never magically turns into an 'O' or disappears unless you specifically remove it.
The Result: In these "Well-Formed" or "Delete-Free" worlds, the robot can learn the pattern. If it practices on short plans, it can perfectly verify long plans, even if the number of objects increases. It learns the logic, not just the memorization.

🔴 The "Chaotic" Worlds (Bad News!)

In these worlds, actions have "conditional effects" (if-then rules) or can delete things in tricky ways.

The Analogy: Imagine a game of Lights Out (a puzzle where pressing a button toggles the light and its neighbors). The effect of pressing a button depends entirely on the current state of the lights. Pressing a button might turn a light off if it's on, but turn it on if it's off.
The Result: In these worlds, the robot cannot generalize. Even if you train it on short plans, it fails on long ones. It gets stuck trying to remember the specific history of every single light switch. It's like trying to remember a phone number by counting the number of times you've dialed it, rather than just reading the digits.

4. The "Flip-Flop" and "Parity" Traps

The authors explain that the chaotic worlds are mathematically similar to two famous brain teasers:

The Flip-Flop: "Did the last switch I flipped turn the light on or off?" You have to remember the very last thing that happened.
The Parity: "Is the total number of 'on' switches even or odd?" You have to count everything.

The paper proves that standard AI robots are terrible at these specific types of logic when the lists get long. They can't count or remember the "last state" reliably over long distances.

5. The Takeaway: Reformulate the Problem

The most exciting part of the paper is the solution.

If you have a problem that is "Chaotic" (like the conditional Lights Out), the robot will fail. BUT, if you rewrite the rules of the game to make it "Well-Behaved" (by creating specific actions for every possible state, even if that means having thousands of actions instead of one), the robot suddenly becomes a genius.

In plain English:

"Don't just throw a hard problem at an AI and hope it figures it out. If the problem's rules are messy and conditional, the AI will get lost. But if you restructure the problem so that every action has a simple, predictable outcome, the AI can learn to solve it, no matter how long the plan gets."

Summary

The Goal: Can AI verify long plans after only seeing short ones?
The Answer: Only if the rules of the game are "well-behaved."
The Magic: By changing the problem structure (making it "Well-Formed"), we can make AI much smarter at planning, even with more objects and longer plans.
The Limit: If the rules involve tricky "if-this-then-that" conditions that depend on the current state, the AI will likely fail, no matter how much you train it.

1. Problem Statement

The paper addresses the inconsistent performance of Transformer-based Large Language Models (LLMs) in AI planning tasks. While LLMs show promise in generating plans, they frequently fail to generalize to longer plans or instances with more objects than seen during training. Specifically, the authors focus on plan verification: determining whether a given sequence of actions correctly solves a planning instance.

The core challenge is length generalization under variable universes. Existing theoretical frameworks (like C-RASP) assume a fixed vocabulary (token set) at both training and inference. However, in planning, the number of objects (and thus the effective vocabulary size) often grows at test time. The paper asks: Under what structural conditions can a Transformer learn to verify plans of arbitrary length and object counts, and when is this theoretically impossible?

2. Methodology

A. Theoretical Framework: C*-RASP

To address the limitation of fixed-vocabulary assumptions, the authors introduce C-RASP*, an extension of the C-RASP (Counting RASP) language.

Split Alphabet: The input alphabet is partitioned into a fixed set $\Sigma$ (predicates, actions) and a countable, growing set $C$ (object identifiers).
Symbolic Limit Transformer: The authors define a theoretical limit object representing a sequence of Transformers trained on increasing lengths and vocabulary sizes. This object must satisfy:
- Translation Invariance: Interactions depend only on relative differences (e.g., $f(c_i, c_j) = f(c_{i+\delta}, c_{j+\delta})$ ), not absolute indices or specific object IDs.
- Locality: Interactions vanish beyond a finite bandwidth.
Match Predicate: A novel operation added to C-RASP that allows the model to check if tokens in different parts of the sequence refer to the same object identity without memorizing specific IDs (e.g., checking if the arguments of an action match the arguments of a precondition).
Learning Model: They formalize an inference procedure where a model is selected to minimize a regularizer (penalizing complexity and non-local interactions) while fitting training data of length $n/2$ . They prove that if a task is expressible by a Symbolic Limit Transformer, this procedure guarantees generalization to length $n$ .

B. Planning Domain Classification

The authors categorize planning domains based on their structural properties to determine membership in C*-RASP:

Delete-Free: Actions only add facts (no deletions).
Well-Formed: Every action application strictly changes the state (no "no-op" actions; effects toggle truth values).
STRIPS: Standard planning without conditional effects (but allows deletions and no-ops).
Conditional Effects: Actions have effects dependent on the current state.

C. Empirical Setup

Domains: Three custom domains were created:
- Heavy Grippers: A robot moving balls (variants: Well-Formed, Delete-Free).
- Colors: Adding/removing colored balls from bags (variants: Well-Formed, Standard STRIPS).
- Lights Out: Toggling lights on a grid (variants: Well-Formed, Conditional Effects).
Architecture: GPT-2 based decoder-only Transformer with Absolute Positional Encodings (APE).
Training/Testing: Trained on plans of length 11–100; tested on In-Distribution (ID) 11–100 and Out-of-Distribution (OOD) 101–200. Object counts varied with plan length.

3. Key Contributions

C-RASP Framework:* The introduction of C*-RASP and the "Symbolic Limit Transformer" concept, providing the first theoretical guarantees for length generalization in Transformers when the vocabulary size (number of objects) grows at test time.
Theoretical Characterization of Plan Verification:
- Positive Result: Plan verification for Delete-Free and Well-Formed domains is in C*-RASP. Transformers can provably learn to verify these plans with perfect generalization to longer sequences and larger object sets.
- Negative Result: Plan verification for general STRIPS and domains with Conditional Effects is not in C*-RASP. These tasks reduce to the Flip-Flop or PARITY languages, which are known to be unlearnable by Transformers for length generalization.
Structural Insight: The paper demonstrates that the structural formulation of a planning problem (e.g., whether actions are well-formed) is a more critical determinant of learnability than the sheer number of actions or objects.

4. Results

Theoretical Results

Theorem 3.1 & 3.6: Established that if a domain is Delete-Free or Well-Formed, the language of valid plans is in C*-RASP (and C-RASP for fixed universes). Conversely, STRIPS and Conditional Effect domains contain instances isomorphic to Flip-Flop or PARITY, placing them outside C*-RASP.
Implication: Transformers can generalize to infinite lengths and object counts for Well-Formed/Delete-Free tasks but will fail to generalize for unconstrained STRIPS or Conditional Effect tasks, regardless of training data size.

Empirical Results

Well-Formed & Delete-Free: Models achieved near-perfect accuracy (approx. 1.0) on both ID and OOD (longer plans, more objects) for Heavy Grippers and Colors.
STRIPS (Colors): While ID accuracy was high, performance dropped significantly on OOD (longer plans), confirming the theoretical prediction of poor generalization.
Conditional Effects (Lights Out): Models performed at chance level (0.5) even on fixed object sets, confirming that the structural complexity prevents learning.
Reformulation Success: The "Lights Out" domain, when reformulated from Conditional Effects to a Well-Formed version (by expanding the action space to cover all state combinations), achieved near-perfect generalization, validating the theory that structural properties drive learnability.

5. Significance

Explaining Failure: The paper provides a rigorous theoretical explanation for why LLMs struggle with planning: many standard planning benchmarks (like STRIPS) inherently require reasoning patterns (like Flip-Flop) that Transformers cannot generalize.
Guidance for Practice: It suggests that for Transformers to be effective in planning, problems should be reformulated to be "Well-Formed" or "Delete-Free." This can be achieved by compiling conditional effects into explicit actions or ensuring state transitions are strictly monotonic.
Theoretical Advancement: The C*-RASP framework extends the understanding of Transformer expressiveness beyond fixed alphabets, offering a new lens to analyze generalization in tasks involving dynamic sets of entities (e.g., reasoning about graphs, code, or multi-agent systems where the number of agents varies).
Limitations: The theory applies to verification, not generation, and assumes standard Transformers without Chain-of-Thought (scratchpads). However, it establishes a baseline for what is possible without such expensive mechanisms.

In summary, the paper bridges formal language theory and empirical AI planning, proving that structural properties of the domain (specifically well-formedness) are the deciding factor in whether Transformers can generalize plan verification to unseen lengths and object counts.