ALPINE: Unveiling the Planning Capability of Autoregressive Learning in
  Language Models
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.
66456731ff120b25ff9bb057
Siwei Wang
66456731ff120b25ff9bb058
Yifei Shen
66456731ff120b25ff9bb059
Shi Feng
66456731ff120b25ff9bb05a
Haoran Sun
66456731ff120b25ff9bb05b
Shang-Hua Teng
66456731ff120b25ff9bb05c
Wei Chen
ALPINE: Unveiling the Planning Capability of Autoregressive Learning in
  Language Models
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.
Theory and experiments show that Transformer-based models, while capable of learning path-finding through embedding adjacency matrices, struggle with identifying reachability through transitivity in network planning tasks.
Transformer-based language models autoregressive learning path-finding gradient-based learning adjacency matrix reachability matrix Blocksworld transitivity