Metraipolis › archive › dc_1475da21bdbf

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.11716
License (as archived)
CC0-1.0
Archived
2026-10-19T05:39:54.361Z
SHA-256 of the archived text
73d321847617b03f18d627cad84958a5e999770ec3f1aef9896c8a4873e49ca0
Stable URL of this page
https://metraipolis.com/documento/dc_1475da21bdbf

How to cite

Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity — arXiv:2608.11716 — arXiv (en), https://arxiv.org/abs/2608.11716 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_1475da21bdbf (Metraipolis archive dc_1475da21bdbf, sha256 73d321847617b03f18d627cad84958a5e999770ec3f1aef9896c8a4873e49ca0)
BibTeX
@misc{dc1475da21bdbf,
  title = {Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity — arXiv:2608.11716},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.11716},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_1475da21bdbf; sha256 73d321847617b03f18d627cad84958a5e999770ec3f1aef9896c8a4873e49ca0},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.11716. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-13 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2608.11716 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T05:18:32.486Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).