Search papers, labs, and topics across Lattice.
This paper addresses the limitations of bounded-depth Transformers by providing concrete implementations of Chain of Thought (CoT) for depth-first search (DFS) and Dijkstra's algorithm, demonstrating their ability to handle branching complexity. The authors introduce unique hard-attention decoders that efficiently compute the Strahler number and width of arbitrary n-ary trees, achieving significant performance improvements in linear steps. These results not only highlight the expressive power of CoT but also establish a practical framework for traversing complex tree structures without the need for layer normalization or positional encodings.
CoT implementations can compute complex tree metrics in linear time, showcasing the potential of bounded-depth Transformers to tackle branching complexity effectively.
Chain of Thought (CoT) lifts the expressive ceiling of bounded-depth Transformers, with characterizations tying the number of CoT steps to circuit complexity classes. What remains largely missing are concrete instantiations with explicit, depth-bounded constructions, and the traversal procedures such characterizations presuppose. We close this gap for branching complexity. We give CoT realizations of depth-first search (DFS) and of Dijkstra algorithm, the latter subsuming breadth-first search, by unique hard-attention decoders of at most two layers, and use them as a shared computational substrate: reusing the DFS decoder yields the Strahler number of an $n$-vertex tree in $2n-1$ steps with four layers, and reusing the Dijkstra decoder yields its width in $n-1$ steps with three. Since computing the Strahler number of a binary tree given as a term is \textsf{NC\textsuperscript{1}}-complete, and our constructions handle arbitrary $n$-ary trees without layer normalization or positional encodings, this is a non-trivial witness for the linear-step regime of the CoT hierarchy. Exploiting the classical bijection between ordered trees and Dyck paths, itself realized by our DFS construction, which emits the path as it traverses, we give independent constructions for both measures on the path representation.
