Seminar: Project ALPINE: Unveiling The Planning Capability of Autoregressive Learning in Language Models

Abstract: Planning is a crucial element of both human intelligence and contemporary large language models (LLMs). In this talk, I introduce the project ALPINE, which initiates a theoretical investigation into the emergence of planning capabilities in Transformer-based LLMs via their next-word prediction mechanisms. We model 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. Our mathematical characterization shows that Transformer architectures can execute path-finding by embedding the adjacency and reachability matrices within their weights. Furthermore, our theoretical analysis of gradient-based learning dynamics reveals that LLMs can learn both the adjacency and a limited form of the reachability matrices. These theoretical insights are then validated through experiments, which demonstrate that Transformer architectures indeed learn the adjacency and an incomplete reachability matrices, consistent with our theoretical predictions. When applying our methodology to the real-world planning benchmark Blocksworld, our observations remain consistent. Additionally, our analyses uncover a fundamental limitation of current Transformer architectures in path-finding: these architectures cannot identify reachability relationships through transitivity, which leads to failures in generating paths when concatenation is required. These findings provide new insights into how the internal mechanisms of autoregressive learning facilitate intelligent planning and deepen our understanding of how future LLMs might achieve more advanced and general planning-and-reasoning capabilities across diverse applications.

Bio: Wei Chen is a Principal Researcher at Microsoft Research Asia and Chair of the MSRA Theory Center. He is a Fellow of both IEEE and ACM, and has been recognized as one of Elsevier’s Highly Cited Chinese Researchers and among the top 2% scientists worldwide by the Stanford ranking. He also serves as a guest professor at several universities including Tsinghua University, Shanghai Jiao Tong University, HKUST (Guangzhou), and Shenzhen University. His research interests include online learning and optimization, social and information networks, network game theory and economics, distributed computing, and fault tolerance. He has authored two monographs on information and influence propagation in social networks, and received several awards such as the 2021 ICDM 10-Year Highest-Impact Paper Award and the William C. Carter Award at DSN 2000. He is actively involved in academic service, including editorial and conference roles, and serves on key committees of the Chinese Computer Federation. He received his Ph.D. in computer science from Cornell University, and bachelor’s and master’s degrees from Tsinghua University. More details are available on his homepage at http://research.microsoft.com/en-us/people/weic/.