用Transformer预测图的最短路径，发现其内部有谱分析机制。
Spectral Journey: How Transformers Predict the Shortest Path
- 用两层Decoder-only模型在10节点图上学习最短路径。
- 模型学到的图嵌入与线图的谱分解高度相关。
- 基于谱嵌入提出新算法SLN，可高效近似找最短路径。
仅解码器结构的Transformer显著提升了大语言模型的能力，但其是否具备真正的规划或推理能力仍存争议。为推进研究，我们采用精心设计的数据，在简单、连通、无向图上从零训练解码器-only Transformer，以预测最短路径。该设定下模型的表征和动态可解释。主要发现：(1) 两层解码器模型可在含最多10个节点的连通图上成功学习最短路径预测；(2) 模型学得的图嵌入与线图的谱分解存在强相关性；(3) 借助该发现，提出一种新型近似路径查找算法Spectral Line Navigator (SLN)，通过贪婪选择线图谱嵌入空间中的节点来寻找最短路径。
原文摘要 · Abstract (English)
Decoder-only transformers lead to a step-change in capability of large language models. However, opinions are mixed as to whether they are really planning or reasoning. A path to making progress in this direction is to study the model's behavior in a setting with carefully controlled data. Then interpret the learned representations and reverse-engineer the computation performed internally. We study decoder-only transformer language models trained from scratch to predict shortest paths on simple, connected and undirected graphs. In this setting, the representations and the dynamics learned by the model are interpretable. We present three major results: (1) Two-layer decoder-only language models can learn to predict shortest paths on simple, connected graphs containing up to 10 nodes. (2) Models learn a graph embedding that is correlated with the spectral decomposition of the line graph. (3) Following the insights, we discover a novel approximate path-finding algorithm Spectral Line Navigator (SLN) that finds shortest path by greedily selecting nodes in the space of spectral embedding of the line graph.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。