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

• URL: http://arxiv.org/abs/2608.11716v1
• Date: Wed, 12 Aug 2026 06:57:08 GMT
• Title: Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity
• Abstract summary: Chain of Thought (CoT) lifts the expressive ceiling of bounded-depth Transformers.<n>We give CoT realizations of depth-first search (DFS) and of Dijkstra algorithm.<n>We give independent constructions for both measures on the path representation.
• Score: 22.2188018390594
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• From Leaves to Clusters: Depth-Efficient SAT-Oracle Synthesis Based on the HRSE Model [11.402462649149918]
  Clustered Synthesis Tree (CST) is a deep synthesis framework for SAT oracles.<n>CST group the individual clause leaves of a hierarchical synthesis tree into clusters, exposing instance-dependent clause-level parallelism.<n>CST reduces the oracle's circuit depth over the state-of-the-art (SOTA) baseline by $68%$--$94%$ on the standard SATLIB benchmarks.
  arXiv  Detail & Related papers  (2026-07-13T11:08:54Z)
• Asymptotically Optimal Circuit Depth for Diagonal Unitary Synthesis and Compilation on Two-Dimensional Grids [12.16068230936605]
  Diagonal unitaries are a resource-intensive class of quantum operations.<n>We address synthesis and compilation jointly.<n>We show that compiling GPF onto a two-dimensional nearest-neighbor grid preserves this optimality.
  arXiv  Detail & Related papers  (2026-06-16T06:51:26Z)
• Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers [2.688207424884465]
  Empirically, transformer encoders trained on recursion-invariant trees converge to permutation-invariant shortcuts.<n>These findings motivate structure-aware objectives and iterative mechanisms for prerequisite-sensitive knowledge tracing on deep hierarchies.
  arXiv  Detail & Related papers  (2026-03-25T01:10:42Z)
• TreeGPT: Pure TreeFFN Encoder-Decoder Architecture for Structured Reasoning Without Attention Mechanisms [0.16244541005112745]
  TreeGPT is an attention-free neural architecture that explores the potential of pure TreeFFN encoder-decoder design for structured reasoning tasks.<n>We evaluate our approach on the ARC Prize 2025 dataset, where TreeGPT achieves 99% accuracy using 3.16M parameters.
  arXiv  Detail & Related papers  (2025-09-06T00:39:33Z)
• ProtInvTree: Deliberate Protein Inverse Folding with Reward-guided Tree Search [77.55575655986252]
  ProtInvTree is a reward-guided tree-search framework for protein inverse folding.<n>It reformulates sequence generation as a deliberate, step-wise decision-making process.<n>It supports flexible test-time scaling by expanding the search depth and breadth without retraining.
  arXiv  Detail & Related papers  (2025-06-01T09:34:20Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>Recent advancements in tree search algorithms guided by verifiers have significantly enhanced the reasoning capabilities of large language models (LLMs)<n>We identify two key challenges contributing to this inefficiency: $textitover-exploration$ due to redundant states with semantically equivalent content, and $textitunder-exploration$ caused by high variance in verifier scoring.<n>We propose FETCH, a flexible, plug-and-play system compatible with various tree search algorithms.
  arXiv  Detail & Related papers  (2025-02-16T16:12:01Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We present a novel characterization of rank, grounded in the well-known Transformer architecture.<n>We show that the rank of a function $f$ corresponds to the minimum number of emphChain of Thought steps required by a single-layer Transformer.<n>We also introduce the notion of the multi-head rank that captures multi-head single-layer transformers, and perform the analysis of PAC-learnability of the classes of functions with bounded multi-head rank.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• Joint Hierarchical Representation Learning of Samples and Features via Informed Tree-Wasserstein Distance [26.56040530884434]
  We propose an unsupervised method for learning hierarchical representations of samples and features via Tree-Wasserstein Distance (TWD)<n>Our method alternates between the two data modes. It first constructs a tree for one mode, then computes a TWD for the other mode based on that tree, and finally uses the resulting TWD to build the second mode's tree.<n>We show that our method can be integrated into hyperbolic graph convolutional networks as a pre-processing technique, improving performance in link prediction and node classification tasks.
  arXiv  Detail & Related papers  (2025-01-07T08:54:42Z)
• A Closer Look at Branch Classifiers of Multi-exit Architectures [103.27533521196817]
  Constant-complexity branching keeps all branches the same, while complexity-increasing and complexity-decreasing branching place more complex branches later or earlier in the backbone respectively. We investigate a cause by using knowledge consistency to probe the effect of adding branches onto a backbone. Our findings show that complexity-decreasing branching yields the least disruption to the feature abstraction hierarchy of the backbone.
  arXiv  Detail & Related papers  (2022-04-28T08:37:25Z)
• Towards Bi-directional Skip Connections in Encoder-Decoder Architectures and Beyond [95.46272735589648]
  We propose backward skip connections that bring decoded features back to the encoder. Our design can be jointly adopted with forward skip connections in any encoder-decoder architecture. We propose a novel two-phase Neural Architecture Search (NAS) algorithm, namely BiX-NAS, to search for the best multi-scale skip connections.
  arXiv  Detail & Related papers  (2022-03-11T01:38:52Z)
• RIM-Net: Recursive Implicit Fields for Unsupervised Learning of Hierarchical Shape Structures [18.5420635041504]
  RIM-Net is a neural network which learns implicit fields for unsupervised inference of hierarchical shape structures. We show the quality, consistency, and interpretability of hierarchical structural inference by RIM-Net.
  arXiv  Detail & Related papers  (2022-01-30T09:31:24Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  We present the sample complexities of Recursive Grouping (RG) and Chow-Liu Recursive Grouping (CLRG) We robustify RG, CLRG, Neighbor Joining (NJ) and Spectral NJ (SNJ) by using the truncated inner product. We derive the first known instance-dependent impossibility result for structure learning of latent trees.
  arXiv  Detail & Related papers  (2021-06-02T01:37:52Z)
• A constrained recursion algorithm for batch normalization of tree-sturctured LSTM [0.29008108937701327]
  Tree-structured LSTM is promising way to consider long-distance interaction over hierarchies. Proposal method is effective for hyper parameter tuning such as the number of batches.
  arXiv  Detail & Related papers  (2020-08-21T10:31:45Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.