On the Ability of Transformers to Verify Plans

• URL: http://arxiv.org/abs/2603.19954v1
• Date: Fri, 20 Mar 2026 13:55:29 GMT
• Title: On the Ability of Transformers to Verify Plans
• Abstract summary: We analyze the ability of decoder-only models to verify whether a given plan correctly solves a given planning instance.<n>We introduce C*-RASP, an extension of C-RASP designed to establish length generalization guarantees for transformers.<n>Our results identify a large class of classical planning domains for which transformers can provably learn to verify long plans.
• Score: 50.65678452287009
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Quantitative Bounds for Length Generalization in Transformers [58.175107357008876]
  We study the problem of length generalization (LG) in transformers.<n>LG occurs when the internal behavior of the transformer on longer sequences can be "simulated" by its behavior on shorter sequences.
  arXiv  Detail & Related papers  (2025-10-30T21:31:36Z)
• Unlocking Out-of-Distribution Generalization in Transformers via Recursive Latent Space Reasoning [50.99796659680724]
  This work investigates out-of-distribution (OOD) generalization in Transformer networks using a GSM8K-style modular arithmetic on computational graphs task as a testbed.<n>We introduce and explore a set of four architectural mechanisms aimed at enhancing OOD generalization.<n>We complement these empirical results with a detailed mechanistic interpretability analysis that reveals how these mechanisms give rise to robust OOD generalization abilities.
  arXiv  Detail & Related papers  (2025-10-15T21:03:59Z)
• The Role of Sparsity for Length Generalization in Transformers [58.65997625433689]
  We propose a new theoretical framework to study length generalization for the next-token prediction task.<n>We show that length generalization occurs as long as each predicted token depends on a small (fixed) number of previous tokens.<n>We introduce Predictive Position Coupling, which trains the transformer to predict the position IDs used in a positional coupling approach.
  arXiv  Detail & Related papers  (2025-02-24T03:01:03Z)
• Enhancing Transformers for Generalizable First-Order Logical Entailment [51.04944136538266]
  This paper studies the generalizable first-order logical reasoning ability of transformers with their parameterized knowledge.<n>We propose TEGA, a logic-aware architecture that significantly improves the performance in first-order logical entailment.
  arXiv  Detail & Related papers  (2025-01-01T07:05:32Z)
• Interpreting Affine Recurrence Learning in GPT-style Transformers [54.01174470722201]
  In-context learning allows GPT-style transformers to generalize during inference without modifying their weights. This paper focuses specifically on their ability to learn and predict affine recurrences as an ICL task. We analyze the model's internal operations using both empirical and theoretical approaches.
  arXiv  Detail & Related papers  (2024-10-22T21:30:01Z)
• A Formal Framework for Understanding Length Generalization in Transformers [14.15513446489798]
  We introduce a rigorous theoretical framework to analyze length generalization in causal transformers.<n>We experimentally validate the theory as a predictor of success and failure of length generalization across a range of algorithmic and formal language tasks.
  arXiv  Detail & Related papers  (2024-10-03T01:52:01Z)
• What Algorithms can Transformers Learn? A Study in Length Generalization [23.970598914609916]
  We study the scope of Transformers' abilities in the specific setting of length generalization on algorithmic tasks. Specifically, we leverage RASP -- a programming language designed for the computational model of a Transformer. Our work provides a novel perspective on the mechanisms of compositional generalization and the algorithmic capabilities of Transformers.
  arXiv  Detail & Related papers  (2023-10-24T17:43:29Z)
• From Interpolation to Extrapolation: Complete Length Generalization for Arithmetic Transformers [7.011373967209572]
  We show that transformer models are able to generalize to long lengths with the help of targeted attention biasing. We demonstrate that using ABC, the transformer model can achieve unprecedented near-perfect length generalization on certain arithmetic tasks.
  arXiv  Detail & Related papers  (2023-10-18T14:10:47Z)
• Masked Language Modeling for Proteins via Linearly Scalable Long-Context Transformers [42.93754828584075]
  We present a new Transformer architecture, Performer, based on Fast Attention Via Orthogonal Random features (FAVOR) Our mechanism scales linearly rather than quadratically in the number of tokens in the sequence, is characterized by sub-quadratic space complexity and does not incorporate any sparsity pattern priors. It provides strong theoretical guarantees: unbiased estimation of the attention matrix and uniform convergence.
  arXiv  Detail & Related papers  (2020-06-05T17:09:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.