🤖 machine learning

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

This paper demonstrates that Chain-of-Thought reasoning with bounded-depth, hard-attention Transformers can explicitly realize depth-first search and Dijkstra's algorithm to compute the Strahler number and width of arbitrary trees, providing a non-trivial witness for the linear-step regime of the CoT hierarchy's expressive power.

Original authors: Debanjan Dutta, Anish Chakrabarty, Swagatam Das

Published 2026-08-13

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Debanjan Dutta, Anish Chakrabarty, Swagatam Das

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a super-smart robot how to think. You give it a picture of a maze and ask it to find the exit. In the past, these robots were like fast readers who could only glance at the whole picture once and guess the answer. They were great at spotting patterns, but if the problem required a long, step-by-step journey—like walking through a maze, remembering where you turned, and backtracking when you hit a dead end—they often got lost. They couldn't "think out loud" or take notes.

Then, scientists discovered a trick called "Chain of Thought" (CoT). Instead of just guessing the final answer, the robot is allowed to write down a series of intermediate steps, like a human solving a math problem on scratch paper. This turns the robot into a traveler that can actually walk through the maze, one step at a time. But here's the big question: Can this robot actually perform complex, real-world tasks like navigating a tree structure or finding the shortest path, or is it just good at simple tricks? This paper dives into that question, treating the robot's "thought process" as a literal journey through a forest of data, proving that with the right instructions, it can do some surprisingly deep math and logic.

The Paper's Big Adventure: Teaching Robots to Walk Through Trees

This paper is like a set of blueprints for teaching a robot how to explore a forest and measure its complexity. The authors, Debanjan Dutta, Anish Chakrabarty, and Swagatam Das, show that a specific type of AI model (a Transformer) can be programmed to act like a hiker with a compass, capable of performing two classic computer science tasks: Depth-First Search (DFS) and Dijkstra's Algorithm.

Think of a tree not as a plant, but as a family tree or a branching map.

DFS is like a hiker who picks a path, walks as far as they can until they hit a dead end, then backtracks to the last fork and tries the next path. It's a "go deep, then go back" strategy.
Dijkstra's Algorithm is like a hiker trying to find the shortest path to every campsite in a forest, carefully checking distances and updating their map as they go.

The authors proved that they can build a "hard-attention" robot (a very specific, strict type of AI) that can do these walks. They didn't just say "it's possible"; they built the actual machine.

To do the DFS walk, they used a robot with just two layers of thinking and two attention heads (like two pairs of eyes looking at different things).
To do the Dijkstra walk, they used a robot with two layers and one attention head.

Why does this matter? Because once the robot can walk these paths, it can solve much harder problems. The authors showed that by reusing the "DFS robot," they could calculate something called the Strahler number (a measure of how "branchy" or complex a tree is) in exactly 2n - 1 steps for a tree with n vertices. They also showed that by reusing the "Dijkstra robot," they could calculate the width of the tree (the widest part of the forest) in n - 1 steps.

The Magic of the "Tree-to-Path" Trick

Here is where the story gets really playful. There is a famous mathematical trick that turns a 3D tree structure into a 1D line, like folding a map flat. This is called a Dyck path. Imagine walking up a hill for every branch you go down, and walking down the hill for every branch you go back up. If you draw this walk, you get a wavy line that never goes below the ground and ends where it started.

The authors discovered something fascinating: You can teach the robot to walk the tree or to walk the line.

They built a robot that walks the tree and calculates the Strahler number.
They built a different robot that walks the line (the Dyck path) and calculates the same Strahler number.

But here is the twist: The robot that walks the tree needs four layers of thinking to do the job, while the robot that walks the line needs four layers as well (though with a different internal setup). The authors found that you can't just take the "tree robot" and magically make it work on the "line" without changing its gears. The way the robot thinks about a tree is fundamentally different from how it thinks about a line, even though they represent the same thing. This suggests that the "language" of the tree and the "language" of the line are not easily interchangeable for these robots.

What This Proves (and What It Doesn't)

The authors are very careful about what they claim. They didn't just run a simulation and say, "Hey, it looks like it works!" They mathematically proved that these specific robots, with their specific number of layers and attention heads, can perform these tasks exactly.

What they proved: They showed that with 2n - 1 steps (for the tree) or n - 1 steps (for the width), these robots can solve problems that are known to be very hard (specifically, problems in a class called NC1). This is a big deal because it shows that "Chain of Thought" isn't just a magic trick for simple questions; it's a powerful tool that lets robots handle complex, recursive logic.
What they ruled out: They showed that you don't need fancy extra tools like "layer normalization" (a common trick in AI to keep numbers stable) to do this. The robot can do it with just the basic building blocks of attention and math.
The "No" part: They also showed that you can't just assume that if a robot can solve a problem on a tree, it can automatically solve it on the line version of that tree. The mechanism has to be rebuilt from scratch for the new shape.

The Takeaway for a Curious Teen

Imagine you have a robot that can only look at one thing at a time. If you ask it to find the exit of a maze, it might get confused. But if you tell it, "Take a step, write down where you are, then take another step," it becomes a master explorer.

This paper is the proof that these "step-by-step" robots are powerful enough to do serious math. They can count the branches of a tree, find the shortest path through a forest, and even translate between different ways of drawing the same map. The authors didn't just guess; they built the exact instructions (the "blueprints") for these robots and showed that they work perfectly.

The most exciting part is that they did this without needing any additional shortcuts or extra hardware. They just used the robot's ability to pay attention to the right things at the right time. It's like showing that a human with a pencil and paper can solve a puzzle that a computer without paper couldn't even begin to understand. And while the robot can walk the tree or the line, it needs a different pair of shoes for each path—it can't just swap them out without changing how it walks.

In short, this paper is a roadmap showing that with the right "Chain of Thought," AI can stop just guessing and start truly exploring.

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

Problem Statement
While recent theoretical work (Merrill and Sabharwal, 2024; Barceló et al., 2025) establishes that Chain-of-Thought (CoT) prompting allows bounded-depth Transformers to escape the complexity-class limitations of single-pass inference—specifically reaching the class $\mathsf{NC}^1$ with linear step counts—these results largely rely on existence proofs or exhaustive characterizations. A significant gap remains in providing concrete, explicit, depth-bounded constructions that realize non-trivial algorithmic traversals and recursion. Specifically, there is a lack of explicit CoT implementations for graph traversal algorithms (DFS, BFS, Dijkstra) and their application to computing branching complexity measures, such as the Strahler number and tree width, without relying on auxiliary primitives like layer normalization or positional encodings.

Methodology
The authors construct explicit CoT realizations using unique hard-attention Transformer decoders. The framework adheres to the following constraints:

Architecture: Decoders utilize unique hard attention (selecting the smallest index among ties) and standard feed-forward networks (FFNs) with ReLU activations.
Simplifications: The constructions avoid layer normalization and positional encodings, relying instead on word embeddings and the autoregressive generation process to maintain state.
Mechanism: The authors employ bilinear maps (following Rizvi-Martel et al., 2024) within the FFN blocks to perform necessary arithmetic operations (e.g., comparing distances, updating counters) that standard linear layers cannot achieve in a single step.
Representations: The work analyzes two representations of trees:
1. Direct Tree Representation: Input as an adjacency matrix or term structure.
2. Dyck Path Representation: A bijection where a tree is flattened into a lattice path (Dyck word) via DFS traversal (up-steps for traversal, down-steps for backtracking).

Key Contributions and Results

Explicit Traversal Realizations:
- DFS: A two-layer, two-head decoder simulates Depth-First Search on any simple directed graph in $O(|V| + |E|)$ CoT steps. The construction distinguishes between "traverse" and "backtrack" operations using attention heads to select the next unvisited neighbor or the parent vertex.
- Dijkstra/BFS: A two-layer, single-head decoder simulates the Dijkstra algorithm (and BFS as a special case with weights $\{1, \infty\}$ ) in exactly $|V|-1$ steps. This offers a computational advantage over comparison-based implementations by replacing the search for a minimum-distance vertex with a constant-time attention operation.
Branching Complexity on Trees:
- Strahler Number: By reusing the DFS realization, the authors construct a four-layer, two-head decoder to compute the Strahler number of an $n$ -vertex tree in $2n-1$ steps. This generalizes the known $\mathsf{NC}^1$ -completeness of Strahler number computation for binary trees to arbitrary $n$ -ary trees.
- Tree Width: By reusing the Dijkstra realization, a three-layer, single-head decoder computes the width of a tree in $n-1$ steps.
Branching Complexity on Dyck Paths:
- Exploiting the bijection between ordered trees and Dyck paths, the authors provide independent constructions for the same measures on the path representation.
- Strahler Number on Paths: A four-layer, single-head decoder computes the Strahler number of the tree corresponding to a Dyck word $w$ in $|w|$ steps.
- Width on Paths: A two-layer, single-head decoder computes the width in $|w|$ steps.
- Reconstruction: A single-layer, two-head decoder simulates the inverse map (Algorithm 1), reconstructing the tree adjacency matrix from a Dyck word in $2(m-1)$ steps.
Compositionality and Transfer:
- The paper investigates whether CoT realizations transfer across the tree-path bijection. While the bijection exists, the authors find that the mechanisms required to compute Strahler number and width differ significantly between the two representations. Direct computation on the tree representation often requires fewer layers than a composite approach (Tree $\to$ Path $\to$ Measure), suggesting that CoT realizability is not trivially closed under bijective changes of representation without architectural adjustment.

Significance and Claims
The paper claims to provide the first explicit CoT realizations of general graph traversal (DFS and Dijkstra) and branching complexity measures using hard-attention decoders.

Theoretical Witness: The construction serves as a non-trivial, concrete witness for the linear-step regime of the CoT hierarchy. By computing the Strahler number (an $\mathsf{NC}^1$ -complete problem) without layer normalization, it demonstrates that such augmentations are not strictly necessary for CoT to reach $\mathsf{NC}^1$ .
Algorithmic Substrate: The traversal decoders act as a shared computational substrate, allowing for the reuse of traversal logic to compute complex structural properties (Strahler number, width) with minimal additional depth.
Limitations: The authors acknowledge that their constructions are not necessarily unique and that alternative formulations may exist. They note that while they use bilinear maps, these are standard in theoretical Transformer analysis. Furthermore, the final step of fixing the Strahler number (applying the condition $M + 1[c \ge 2]$ ) sits marginally outside the iterative CoT loop in some constructions.

The work bridges the gap between abstract complexity characterizations of CoT and concrete algorithmic implementations, proving that Transformers can execute specific, recursive graph algorithms step-by-step within a bounded depth and linear step count.

The Paper's Big Adventure: Teaching Robots to Walk Through Trees

The Magic of the "Tree-to-Path" Trick

What This Proves (and What It Doesn't)

The Takeaway for a Curious Teen

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

More like this