On the Ability of Transformers to Verify Plans
Not on the map. Why?
Abstract (arXiv)
Transformers have shown inconsistent success in AI planning tasks, and theoretical understanding of when generalization should be expected has been limited. We take important steps towards addressing this gap by analyzing the ability of decoder-only models to verify whether a given plan correctly solves a given planning instance. To analyse the general setting where the number of objects -- and thus the effective input alphabet -- grows at test time, we introduce C*-RASP, an extension of C-RASP designed to establish length generalization guarantees for transformers under the simultaneous growth in sequence length and vocabulary size. Our results identify a large class of classical planning domains for which transformers can provably learn to verify long plans, and structural properties that significantly affects the learnability of length generalizable solutions. Empirical experiments corroborate our theory.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 41 of its 65 references that are in the map. First posted on arXiv 20 Mar 2026.
Builds on
41 of 65 references.
References · 41
- 2022ReAct: Synergizing Reasoning and Acting in Language Modelscited by 8,695
- 2021Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolationcited by 1,103
- 2022PlanBench: An Extensible Benchmark for Evaluating Large Language Models on Planning and Reasoning about Changecited by 382
- 2023The Impact of Positional Encoding on Length Generalization in Transformerscited by 327
- 2022Exploring Length Generalization in Large Language Modelscited by 206
- 2023What Algorithms can Transformers Learn? A Study in Length Generalizationcited by 199
- 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
- 2021Thinking Like Transformerscited by 184
- 2021Inductive Biases and Variable Creation in Self-Attention Mechanismscited by 144
- 2024On the Self-Verification Limitations of Large Language Models on Reasoning and Planning Taskscited by 142
- 2023Generalized Planning in PDDL Domains with Pretrained Large Language Modelscited by 139
- 2022Overcoming a Theoretical Limitation of Self-Attentioncited by 113
29 more
- 2024LLMs Still Can't Plan; Can LRMs? A Preliminary Evaluation of OpenAI's o1 on PlanBenchcited by 94
- 2023Exposing Attention Glitches with Flip-Flop Language Modelingcited by 75
- 2024Why are Sensitive Functions Hard for Transformers?cited by 74
- 2023Generalization on the Unseen, Logic Reasoning and Degree Curriculumcited by 73
- 2023SayCanPay: Heuristic Planning with Large Language Models using Learnable Domain Knowledgecited by 49
- 2023Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languagescited by 49
- 2024A Formal Framework for Understanding Length Generalization in Transformerscited by 45
- 2019ASNets: Deep Learning for Generalised Planningcited by 42
- 2022Plansformer: Generating Symbolic Plans using Transformerscited by 41
- 2024Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformerscited by 39
- 2025Self-Improving Transformers Overcome Easy-to-Hard and Length Generalization Challengescited by 31
- 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26
- 2024Universal Length Generalization with Turing Programscited by 25
- 2023Automating the Generation of Prompts for LLM-based Action Choice in PDDL Planningcited by 24
- 2024Two Stones Hit One Bird: Bilevel Positional Encoding for Better Length Extrapolationcited by 24
- 2024Position Coupling: Improving Length Generalization of Arithmetic Transformers Using Task Structurecited by 23
- 2022Learning Generalized Policies Without Supervision Using GNNscited by 22
- 2025Knee-Deep in C-RASP: A Transformer Depth Hierarchycited by 12
- 2024Chasing Progress, Not Perfection: Revisiting Strategies for End-to-End LLM Plan Generationcited by 11
- 2025Softmax Transformers are Turing-Completecited by 9
- 2024Learning Lifted STRIPS Models from Action Traces Alone: A Simple, General, and Scalable Solutioncited by 8
- 2025The Role of Sparsity for Length Generalization in Transformerscited by 8
- 2025Quantitative Bounds for Length Generalization in Transformerscited by 8
- 2025Non-Asymptotic Length Generalizationcited by 7
- 2025Language Models For Generalised PDDL Planning: Synthesising Sound and Programmatic Policiescited by 7
- 2025Born a Transformer -- Always a Transformer? On the Effect of Pretraining on Architectural Abilitiescited by 6
- 2025Symmetry-Aware Transformer Training for Automated Planningcited by 5
- 2024Interchangeable Token Embeddings for Extendable Vocabulary and Alpha-Equivalencecited by 2
- 2025From Next Token Prediction to (STRIPS) World Modelscited by 2
Built on by
Citing papers per year: 2026: 2.
2 papers.