Researchers have found conditions under which transformer models can provably learn to verify AI plans — not generate them, just check whether a given plan actually solves a given problem.
The paper, posted to arXiv, analyzes decoder-only transformer architectures on plan verification tasks. The core challenge: as planning problems grow, both the sequence length and the number of objects — effectively the vocabulary — expand at test time, which breaks most theoretical guarantees. To handle this, the authors introduce C*-RASP, an extension of an existing formal framework called C-RASP, designed specifically to give length-generalization guarantees when both dimensions grow simultaneously. They identify a large class of classical planning domains where transformers can learn to verify long plans, and they run empirical experiments that back up the theory.
The distinction between planning and plan verification matters. Generating a valid plan is hard; checking whether a proposed plan is correct is generally easier — yet even verification has proven inconsistent for transformers in practice. Understanding exactly where transformers succeed and where they structurally cannot is the kind of theoretical grounding the field has mostly lacked. If verification can be made reliable, it becomes a useful building block for AI systems that need to audit their own outputs.
The research does not claim transformers can plan well — only that they can, under specific conditions, learn to tell a good plan from a bad one. That is a narrower claim than the AI planning discourse usually traffics in, which is precisely what makes it useful.