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.

通过自回归学习机制，本文在理论上研究了 Transformer-based 语言模型在规划能力方面的发展，揭示了其在路径规划上的潜在限制，同时通过实验证明了这些理论洞察力。