Transformer depth enables exponential increase in graph search reachability

A two-layer transformer is both necessary and sufficient to implement near-linear DFS reasoning on dense graphs. For models with k layers where k is at least 3, the reachability horizon for a bounded-reachability DFS policy increases exponentially at 1 + 2^(k-3).