title: ALPINE: Unveiling the Planning Capability of Autoregressive Learning in
    Language Models
summary: In this paper, we present the findings of our Project ALPINE which stands for
  ``Autoregressive Learning for Planning In NEtworks." Project ALPINE initiates a
  theoretical investigation into the development of planning capabilities in
  Transformer-based language models through their autoregressive learning
  mechanisms, aiming to identify any potential limitations in their planning
  abilities. We abstract planning as a network path-finding task where the
  objective is to generate a valid path from a specified source node to a
  designated target node. In terms of expressiveness, we show that the
  Transformer is capable of executing path-finding by embedding the adjacency and
  reachability matrices within its weights. Our theoretical analysis of the
  gradient-based learning dynamic of the Transformer reveals that the Transformer
  is capable of learning both the adjacency matrix and a limited form of the
  reachability matrix. These theoretical insights are then validated through
  experiments, which demonstrate that the Transformer indeed learns the adjacency
  matrix and an incomplete reachability matrix, which aligns with the predictions
  made in our theoretical analysis. Additionally, when applying our methodology
  to a real-world planning benchmark, called Blocksworld, our observations remain
  consistent. Our theoretical and empirical analyses further unveil a potential
  limitation of Transformer in path-finding: it cannot identify reachability
  relationships through transitivity, and thus would fail when path concatenation
  is needed to generate a path. In summary, our findings shed new light on how
  the internal mechanisms of autoregressive learning enable planning in networks.
  This study may contribute to our understanding of the general planning
  capabilities in other related domains.
paper_authors._id: 66456731ff120b25ff9bb057
paper_authors.name: Siwei Wang
paper_authors._id: 66456731ff120b25ff9bb058
paper_authors.name: Yifei Shen
paper_authors._id: 66456731ff120b25ff9bb059
paper_authors.name: Shi Feng
paper_authors._id: 66456731ff120b25ff9bb05a
paper_authors.name: Haoran Sun
paper_authors._id: 66456731ff120b25ff9bb05b
paper_authors.name: Shang-Hua Teng
paper_authors._id: 66456731ff120b25ff9bb05c
paper_authors.name: Wei Chen
paper_title: ALPINE: Unveiling the Planning Capability of Autoregressive Learning in
    Language Models
paper_summary: In this paper, we present the findings of our Project ALPINE which stands for
  ``Autoregressive Learning for Planning In NEtworks." Project ALPINE initiates a
  theoretical investigation into the development of planning capabilities in
  Transformer-based language models through their autoregressive learning
  mechanisms, aiming to identify any potential limitations in their planning
  abilities. We abstract planning as a network path-finding task where the
  objective is to generate a valid path from a specified source node to a
  designated target node. In terms of expressiveness, we show that the
  Transformer is capable of executing path-finding by embedding the adjacency and
  reachability matrices within its weights. Our theoretical analysis of the
  gradient-based learning dynamic of the Transformer reveals that the Transformer
  is capable of learning both the adjacency matrix and a limited form of the
  reachability matrix. These theoretical insights are then validated through
  experiments, which demonstrate that the Transformer indeed learns the adjacency
  matrix and an incomplete reachability matrix, which aligns with the predictions
  made in our theoretical analysis. Additionally, when applying our methodology
  to a real-world planning benchmark, called Blocksworld, our observations remain
  consistent. Our theoretical and empirical analyses further unveil a potential
  limitation of Transformer in path-finding: it cannot identify reachability
  relationships through transitivity, and thus would fail when path concatenation
  is needed to generate a path. In summary, our findings shed new light on how
  the internal mechanisms of autoregressive learning enable planning in networks.
  This study may contribute to our understanding of the general planning
  capabilities in other related domains.
paper_ai_keywords: Transformer-based language models autoregressive learning planning capabilities network path-finding task adjacency matrix reachability matrix gradient-based learning dynamic Blocksworld transitivity path concatenation