LLM 在复杂推理任务上取得显著进展，但其推理机制和效率仍不清楚。本文以有向图的路径寻找问题作为多步推理的符号抽象进行研究。
首先分析模型结构需求。证明单层 Transformer 在密集图上实现 DFS 子节点选择原语至少需要 $\Omega(N^2)$ 参数规模。两层 Transformer 能以 $O(N\log(N))$ 参数实现完整的 DFS，说明第二层是实现近线性 DFS 推理的必要且充分条件。
对更深模型的表达能力进一步扩展。对任意 $k\geq3$，$k$ 层 Transformer 能实现有界可达性 DFS 策略，其前瞻视野为 $1+2^{k-3}$，表明深度带来指数级的可达范围提升。
超越表达性分析，给定精心构造的训练数据，证明两层 Transformer 可以通过梯度下降学习执行 DFS，并在未见图上实现泛化。
综合以上结果，提供了 Transformer 如何实现图搜索、深度如何扩展有限前瞻以及此类推理算法如何在训练中自然出现的机制性解释。 点评