LLMs have achieved remarkable progress on complex reasoning tasks, yet their reasoning mechanisms and efficiency remain unclear. This work studies the path‑finding problem on directed graphs as a symbolic abstraction of multi‑step reasoning.
We first examine architectural requirements. It is proved that a single‑layer Transformer needs at least $\Omega(N^2)$ parameters on dense graphs to implement the DFS child‑selection primitive. A two‑layer Transformer can realize full DFS with $O(N\log(N))$ parameters, showing that the second layer is both necessary and sufficient for near‑linear DFS reasoning.
The expressivity analysis is then extended to deeper models. For any $k\geq3$, a $k$‑layer Transformer implements a bounded‑reachability DFS policy with a look‑ahead horizon of $1+2^{k-3}$, indicating an exponential increase in reachable depth as the network deepens.
Beyond expressivity, with appropriately curated training data we prove that two‑layer Transformers can learn to execute DFS via gradient descent and generalize to unseen graphs.
Taken together, these results provide a mechanistic account of how Transformers perform graph search, how depth expands bounded look‑ahead, and how such reasoning algorithms can emerge through training. Review