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

📄 arXiv: 2608.11716v1 📥 PDF

作者: Debanjan Dutta, Anish Chakrabarty, Swagatam Das

分类: cs.LG

发布日期: 2026-08-12

💡 一句话要点

提出深度优先搜索与Dijkstra算法的CoT实现以解决分支复杂性问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 分支复杂性 深度优先搜索 Dijkstra算法 Chain of Thought 树结构 算法优化 复杂性理论

📋 核心要点

  1. 现有方法在处理分支复杂性时缺乏具体的深度有限构造和遍历程序，限制了其应用。
  2. 本文提出了通过独特的硬注意力解码器实现深度优先搜索和Dijkstra算法的CoT，填补了理论与实践之间的空白。
  3. 实验结果表明，重用解码器可以高效计算树的Strahler数和宽度，展示了在复杂性处理上的显著提升。

📝 摘要（中文）

Chain of Thought (CoT) 提升了有界深度变换器的表达能力，并将CoT步骤数量与电路复杂性类进行了关联。本文填补了深度有限构造和遍历程序的缺失，针对分支复杂性提供了深度优先搜索（DFS）和Dijkstra算法的CoT实现。通过最多两层的独特硬注意力解码器，重用DFS解码器可在2n-1步内计算n个顶点树的Strahler数，而重用Dijkstra解码器可在n-1步内计算其宽度。由于计算给定术语的二叉树的Strahler数是 extsf{NC extsuperscript{1}}-完全的，且我们的构造处理任意n-叉树而不使用层归一化或位置编码，这为CoT层次的线性步骤范围提供了非平凡的证据。

🔬 方法详解

问题定义：本文旨在解决在分支复杂性中缺乏具体深度有限构造和遍历程序的问题。现有方法在这方面的不足限制了其在复杂性理论中的应用。

核心思路：论文提出通过Chain of Thought (CoT) 实现深度优先搜索（DFS）和Dijkstra算法，利用硬注意力解码器的特性来高效处理树结构的复杂性。

技术框架：整体架构包括两个主要模块：DFS解码器和Dijkstra解码器。DFS解码器用于计算Strahler数，而Dijkstra解码器用于计算树的宽度。

关键创新：最重要的技术创新在于使用最多两层的硬注意力解码器实现复杂度的计算，且无需层归一化或位置编码，这与现有方法显著不同。

关键设计：在设计中，DFS解码器在2n-1步内计算Strahler数，而Dijkstra解码器在n-1步内计算宽度，展示了高效的计算能力。

🖼️ 关键图片

img_0
img_1
img_2

📊 实验亮点

实验结果显示，重用DFS解码器可以在2n-1步内计算n个顶点树的Strahler数，重用Dijkstra解码器则能在n-1步内计算树的宽度。这些结果表明，相较于传统方法，本文提出的CoT实现显著提高了计算效率。

🎯 应用场景

该研究的潜在应用领域包括计算机科学中的算法优化、图论研究以及复杂性理论。通过提供高效的树结构处理方法，能够在实际应用中提升算法性能，尤其是在大规模数据处理和网络分析中具有重要价值。

📄 摘要（原文）

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.