Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity

TL;DR - This paper constructs shallow hard-attention Transformers that use chain-of-thought steps to execute tree and graph algorithms. It provides a concrete witness that iterative CoT can realize branching computations beyond bounded-depth Transformers’ usual expressive limits.

• At most two-layer decoders implement depth-first search and Dijkstra’s algorithm, with Dijkstra also subsuming breadth-first search.
• Reusing these decoders computes an (n)-vertex tree’s Strahler number in (2n-1) steps and its width in (n-1) steps.
• The constructions support arbitrary n-ary trees without layer normalization or positional encodings.
• Ordered-tree/Dyck-path equivalence enables independent constructions for both measures on path representations.