Spectral Journey: How Transformers Predict the Shortest Path

📄 arXiv: 2502.08794v1 📥 PDF

作者: Andrew Cohen, Andrey Gromov, Kaiyu Yang, Yuandong Tian

分类: cs.LG

发布日期: 2025-02-12

备注: 12 pages

💡 一句话要点

Transformer学习最短路径：揭示谱分解与路径规划的关联

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: Transformer 最短路径 图神经网络 谱分解 路径规划 图嵌入 可解释性

📋 核心要点

  1. 大型语言模型的能力显著提升，但其规划和推理能力仍存在争议，需要可控数据环境下的深入研究。
  2. 该研究训练Transformer预测图上的最短路径，旨在通过分析模型内部表示来理解其规划能力。
  3. 实验表明，Transformer能够学习图的嵌入表示，且该表示与线图的谱分解密切相关，并据此提出了新的路径查找算法。

📝 摘要（中文）

本文研究了从头开始训练的仅解码器Transformer语言模型，用于预测简单连通无向图上的最短路径。该研究旨在通过精心控制的数据来研究模型的行为，并解释学习到的表示和逆向工程内部执行的计算。研究结果表明：（1）两层仅解码器语言模型可以学习预测包含最多10个节点的简单连通图上的最短路径。（2）模型学习到的图嵌入与线图的谱分解相关。（3）基于这些见解，作者提出了一种新的近似路径查找算法Spectral Line Navigator (SLN)，该算法通过贪婪地选择线图谱嵌入空间中的节点来找到最短路径。

🔬 方法详解

问题定义：该论文旨在研究decoder-only Transformer语言模型在预测图上最短路径时的学习机制。现有方法缺乏对模型内部表示和计算过程的深入理解，难以解释模型如何进行规划和推理。

核心思路：论文的核心思路是利用图上的最短路径预测任务作为实验平台，通过分析模型学习到的图嵌入表示，揭示模型进行路径规划的内在机制。作者假设模型可能利用了图的某种谱性质来进行路径选择。

技术框架：该研究训练了一个两层的decoder-only Transformer语言模型，输入为图的节点序列，输出为最短路径的节点序列。模型的目标是最小化预测序列与真实最短路径序列之间的交叉熵损失。训练完成后，作者分析了模型学习到的节点嵌入表示，并将其与线图的谱分解进行比较。

关键创新：该研究最重要的创新点在于发现了Transformer学习到的图嵌入与线图的谱分解之间的关联。基于这一发现，作者提出了一种新的近似路径查找算法Spectral Line Navigator (SLN)，该算法利用线图的谱嵌入空间进行贪婪搜索，从而找到最短路径。

关键设计：模型采用两层Transformer解码器结构，使用标准的自注意力机制和前馈神经网络。训练数据包含随机生成的简单连通无向图，节点数量最多为10个。损失函数为交叉熵损失，优化器为Adam。SLN算法的关键在于计算线图的谱分解，并利用谱嵌入空间中的距离作为节点选择的依据。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，两层Transformer模型可以学习预测包含最多10个节点的简单连通图上的最短路径。更重要的是，模型学习到的图嵌入与线图的谱分解高度相关。基于此，作者提出的SLN算法在某些图结构上表现出良好的性能，验证了谱分解在路径规划中的潜在作用。

🎯 应用场景

该研究的潜在应用领域包括机器人导航、网络路由优化、以及其他需要进行路径规划的场景。通过理解Transformer如何学习图的表示和进行路径规划，可以为开发更高效、更可解释的AI系统提供新的思路。此外，该研究提出的SLN算法也可能在某些特定场景下提供一种新的路径查找解决方案。

📄 摘要（原文）

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.