演讲人： Siwei Wang MSRA, Theory Center
时间： 2024-11-25 16:00-2024-11-25 17:00
地点：FIT 1-222
内容：

Planning is a crucial element of both human intelligence and contemporary large language models (LLMs). In this paper, we initiate 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.

个人简介:

Dr. Siwei Wang obtained his bachelor and Ph.D degrees from the Institute for Interdisciplinary Information Sciences (IIIS), Tsinghua University. Now he is a senior researcher at MSRA, Theory Center. His research focuses on developing solutions to address challenges in controlling/decision-making systems in artificial intelligence. Typically, he models and analyzes the systems through the lens of mechanism design, mathematics optimization, and algorithms. His recent studies are on the analysis of online learning models (e.g., bandits problems and reinforcement learning) and transformer-based language models.