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

The paper introduces explicit, depth-bounded Chain-of-Thought (CoT) realizations of graph traversal algorithms and branching complexity measures using Transformer decoders with unique hard attention. The authors provide the first CoT constructions of depth-first search (DFS) and Dijkstra's algorithm (which subsumes breadth-first search) using at most two-layer, two-head and two-layer, single-head hard-attention decoders, respectively. These traversal realizations serve 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 the tree's width in n − 1 steps with three layers. The paper also exploits the classical bijection between ordered trees and Dyck paths—realized algorithmically by the DFS construction—to give independent CoT constructions for both measures on the path representation.

The main contributions are summarized as follows: "We give the first CoT realizations of general graph traversal (DFS and Dijkstra) by hard-attention Transformer decoders, each requiring at most two layers and two heads, and show that Dijkstra realization yields a step-count advantage over comparison-based implementations by replacing the search for a minimum-distance vertex with a single constant-time attention operation. Additionally, We use these traversal realizations as a shared computational substrate to give explicit, small-depth CoT constructions for two independent notions of branching complexity, the Strahler number and width of a tree, providing a concrete, non-trivial instantiation of the CoT-rank framework after Barceló et al. (2025) on a measure already known to be NC1-complete in the binary case (Ganardi and Lohrey, 2026), generalized here to arbitrary ordered trees. Finally, Exploiting the classical bijection between trees and Dyck paths, realized algorithmically by our DFS construction, we give independent CoT constructions for both measures on the path representation, and show that the resulting constructions do not transfer readily across the bijection without change in mechanism or layer count."

The paper's key theorems are:

• Theorem 5: A two-layer, two-head Transformer decoder can simulate the depth-first traversal DFS on any simple directed graph G = (V, E, A) in O(V + E) chain-of-thought steps.

• Theorem 6: "A two-layer, single-head Transformer decoder can simulate the Dijkstra algorithm Dkst on any simple connected directed graph G = (V, E, A) with A = R>0 in exactly V − 1 chain-of-thought steps."

• Theorem 7: A single-layer, two-head Transformer decoder can simulate Algorithm 1 in the 2(m − 1) CoT-steps (for reconstructing a tree from a Dyck path).

• Theorem 8: A four-layer, two-head Transformer decoder can compute st(GT), the Strahler number of a tree GT during the simulation of DFS in exactly 2n − 1 CoT steps, where n denotes the number of vertices in GT.

• Theorem 11: A four-layer, single-head Transformer decoder can compute st(ψ(w)), the Strahler number of a tree corresponding to the Dyck word w in exactly n CoT steps, where n = w.

• Theorem 13: A three-layer single-head Transformer decoder can find the width of a tree wd(GT) during the simulation of Dkst in exactly n − 1 steps, where n denotes the number of vertices in GT.

• Theorem 16: A two-layer single-head Transformer decoder can find wd(ψ(w)) for a Dyck word w in exactly n CoT steps, where w = n.

The paper notes that "computing the Strahler number of a binary tree given as a term is NC1-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." The constructions avoid auxiliary primitives like layer normalization, which prior CoT constructions relied on.

The paper also discusses the relationship between the tree and path representations: The DFS realization of Theorem 5 is the map from tree to path, since a traverse step is exactly an up-step and a backtrack step is exactly a down-step. It raises the question of whether CoT realizability is closed under bijective changes of representation, and hence, in general, under composition? The paper concludes that "the CoT realizations of the Strahler number for path and tree inputs exhibit remarkably little structural synergy — beyond their shared adherence to (2) — despite the bijective correspondence between the two input representations via ϕ and ψ."

The paper's limitations include that several of our constructions invoke the bilinear operation, though this stays within the established conventions of this line of work rather than constituting a departure from them. It also notes that Theorem 11 concludes with the final values M and c, the closing operation M + 1[c ≥ 2] that fixes the Strahler number sits marginally outside the CoT iteration.

Improvements to AI Systems:

1. Constant-Time Minimum Search via Attention: Replace iterative or comparison-based minimum-finding loops (e.g., in pathfinding, scheduling, or resource allocation) with a single hard-attention operation, as demonstrated by the Dijkstra decoder. An improved AI system can perform graph traversal (e.g., shortest-path, BFS) in exactly V−1 steps regardless of graph density, yielding O(1) per-node cost for the minimum-distance selection—a speedup over O(log n) or O(n) comparison-based approaches.

2. Depth-Bounded CoT for Recursive Tree Metrics: Enable AI systems to compute structural complexity measures (e.g., Strahler number, tree width) on arbitrary n-ary trees using fixed, small-depth Transformer decoders (2–4 layers) without layer normalization or positional encodings. This allows for efficient, parallelizable computation of branching complexity in hierarchical data (e.g., parse trees, organizational charts, circuit layouts) in linear steps (2n−1 or n−1), with provable correctness.

3. Unified Traversal Substrate for Multi-Task Reasoning: Reuse a single DFS or Dijkstra decoder as a shared computational backbone for multiple downstream tasks (e.g., computing tree metrics, reconstructing trees from paths, validating graph properties). An improved AI system can perform multi-step reasoning on graphs with minimal architectural overhead, reducing parameter count and improving sample efficiency by transferring the traversal mechanism across tasks.

4. Bijection-Aware Representation Switching: Leverage the algorithmic realization of the tree↔Dyck-path bijection (via DFS) to allow AI systems to switch between input representations (tree vs. path) on the fly. This enables a system to choose the most efficient representation for a given computation—e.g., computing Strahler number on a tree in 2n−1 steps vs. on a Dyck path in n steps—without retraining, by dynamically invoking the appropriate decoder.

5. Explicit CoT Step Budgeting: Use the paper’s exact step-count guarantees (e.g., exactly n−1 steps for Dijkstra, 2n−1 for DFS-based Strahler) to design AI systems with predictable inference latency. This is critical for real-time or resource-constrained applications (e.g., robotics navigation, embedded systems) where worst-case reasoning depth must be bounded.

6. Hard-Attention Primitives for Interpretable Reasoning: Adopt unique hard-attention mechanisms (as opposed to soft attention) to make intermediate CoT steps more interpretable and verifiable. An improved AI system can produce traceable, discrete reasoning steps (e.g., visit node 3, backtrack to node 2) that are easier to audit, debug, and align with formal specifications—useful for safety-critical AI.

7. Compositional CoT without Auxiliary Primitives: Build AI systems that compose multiple algorithmic decoders (e.g., DFS → Strahler, Dijkstra → width) without relying on layer normalization or positional encodings, reducing architectural complexity and improving robustness to input length variations. This enables modular, plug-and-play reasoning components that can be combined for novel tasks (e.g., computing both branching measures simultaneously from a single traversal).

8. NC1-Completeness Witness for Efficient Reasoning: Use the paper’s construction of an NC1-complete problem (Strahler number) in the linear-step CoT regime to benchmark and improve AI systems’ reasoning capabilities on formally hard problems. An improved system can be tested against this known-hard measure to validate its scaling behavior and identify where it falls short of optimal step complexity.

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-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.