論文の概要: Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity

• arxiv url: http://arxiv.org/abs/2608.11716v1
• Date: Wed, 12 Aug 2026 06:57:08 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-08-13 19:07:54.483851
• Title: Chain-of-Thought Shows the Path to a Tree: Realizing Branching Complexity
• Title（参考訳）: 木への道のり:枝分かれの複雑さを実現する
• Abstract要約: 思考の連鎖(CoT)は、有界深度変換器の表現的天井を持ち上げる。 深度優先探索(DFS)とDijkstraアルゴリズムのCoT実現について述べる。 経路表現の両測度について独立的に構成する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: Chain of Thought (CoT)は境界深度変換器の表現的天井を持ち上げ、CoTステップの数を回路複雑性クラスに結びつける。 ほとんど失われているのは、明示的で奥行きのある構造を持つ具体的なインスタンス化であり、そのような特徴付けが前提となっている。 分岐複雑性のためにこのギャップを埋めます。 ディープファーストサーチ(DFS)とダイクストラアルゴリズム(Dijkstraアルゴリズム)をCoTで実現し、後者は2層以上のユニークなハードアテンションデコーダを用いて、それらを共有計算基板として用いる: DFSデコーダの再利用は4層で2n-1$ステップで$n$-vertexツリーのストラー数を得る。 項として与えられる二分木のストラー数を計算することは \textsf{NC\textsuperscript{1}}-完全であり、構造は層正規化や位置エンコーディングを伴わない任意の$n$-ary木を扱うので、これはCoT階層の線形ステップ構造に対する非自明な証である。 順序木とダイクパスの間の古典的単射を爆発させることは、その経路が横切るにつれて経路を放出するDFS構造によって実現され、経路表現の両測度に対して独立した構成を与える。

関連論文リスト

• From Leaves to Clusters: Depth-Efficient SAT-Oracle Synthesis Based on the HRSE Model [11.402462649149918]
  クラスタ化合成木(CST)はSATオーラクルのための深層合成フレームワークである。 CST は階層的な合成木の個々の節をクラスタに分類し、インスタンス依存の節レベルの並列性を公開する。 CSTは、標準的なSATLIBベンチマークにおいて、最先端(SOTA)ベースライン上のオラクルの回路深さを68%$--94%$で削減する。
  論文  参考訳（メタデータ） (2026-07-13T11:08:54Z)
• Asymptotically Optimal Circuit Depth for Diagonal Unitary Synthesis and Compilation on Two-Dimensional Grids [12.16068230936605]
  対角ユニタリ(Diagonal Unitary)は、量子演算のリソース集約型クラスである。 合成と編集を共同で行う。 GPFを2次元近傍グリッドにコンパイルすることは、この最適性を保っていることを示す。
  論文  参考訳（メタデータ） (2026-06-16T06:51:26Z)
• Circuit Complexity of Hierarchical Knowledge Tracing and Implications for Log-Precision Transformers [2.688207424884465]
  経験的に、再帰不変木で訓練されたトランスフォーマーエンコーダは、置換不変ショートカットに収束する。 これらの知見は, 階層構造に基づく事前知識追跡のための構造認識的目的と反復的メカニズムを動機付けている。
  論文  参考訳（メタデータ） (2026-03-25T01:10:42Z)
• TreeGPT: Pure TreeFFN Encoder-Decoder Architecture for Structured Reasoning Without Attention Mechanisms [0.16244541005112745]
  TreeGPTは、構造化推論タスクのための純粋なTreeFFNエンコーダデコーダ設計の可能性を探る無注意ニューラルネットワークアーキテクチャである。 我々はARC Prize 2025データセットに対するアプローチを評価し、TreeGPTは3.16Mパラメータを使用して99%の精度を達成している。
  論文  参考訳（メタデータ） (2025-09-06T00:39:33Z)
• ProtInvTree: Deliberate Protein Inverse Folding with Reward-guided Tree Search [77.55575655986252]
  ProtInvTreeはタンパク質逆フォールディングのための報酬誘導ツリー検索フレームワークである。 シークエンス生成は、意図的に、ステップワイズな意思決定プロセスとして再構成される。 検索深度と幅を広げて、再トレーニングすることなく、フレキシブルなテストタイムスケーリングをサポートする。
  論文  参考訳（メタデータ） (2025-06-01T09:34:20Z)
• Don't Get Lost in the Trees: Streamlining LLM Reasoning by Overcoming Tree Search Exploration Pitfalls [83.89771461061903]
  検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 検証者による木探索アルゴリズムの最近の進歩は、大規模言語モデル(LLM)の推論能力を大幅に向上させた。 意味論的に等価なコンテンツを持つ冗長な状態による$textitover-Exploration$と、検証器のスコアリングにおける高いばらつきに起因する$textitunder-Exploration$である。 各種木探索アルゴリズムに適合するフレキシブルなプラグアンドプレイシステムであるFETCHを提案する。
  論文  参考訳（メタデータ） (2025-02-16T16:12:01Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  本稿では、よく知られたトランスフォーマーアーキテクチャを基盤とした、ランクの新たな特徴付けについて述べる。 関数 $f$ のランクは、単一層変換器が要求する思考ステップの EmphChain の最小値に対応していることを示す。 また、マルチヘッド単一層トランスをキャプチャするマルチヘッドランクの概念を導入し、有界なマルチヘッドランクを持つ関数クラスのPAC学習性の解析を行う。
  論文  参考訳（メタデータ） (2025-01-22T16:30:58Z)
• Joint Hierarchical Representation Learning of Samples and Features via Informed Tree-Wasserstein Distance [26.56040530884434]
  本稿では,Tree-Wasserstein Distance (TWD) を用いて,サンプルと特徴の階層的表現を学習するための教師なし手法を提案する。 本手法は2つのデータモードを交互に構成する。まず1つのモードのツリーを構築し、次にそのツリーに基づいて他のモードのTWDを計算し、最終的にTWDを用いて第2のモードのツリーを構築する。 本稿では,提案手法をハイパーボリックグラフ畳み込みネットワークに前処理として組み込むことができ,リンク予測やノード分類タスクの性能を向上させることができることを示す。
  論文  参考訳（メタデータ） (2025-01-07T08:54:42Z)
• A Closer Look at Branch Classifiers of Multi-exit Architectures [103.27533521196817]
  一定の複雑さのブランチはすべてのブランチを同じに保ちますが、複雑性の増大と複雑性の低下は、それぞれバックボーンの遅かれ早かれ複雑なブランチを配置します。 知識の整合性を利用して,背骨に枝を追加する効果を探索する。 以上の結果から,複雑性が増大する分岐は,背骨の特徴的抽象的階層を最小限に破壊することが明らかとなった。
  論文  参考訳（メタデータ） (2022-04-28T08:37:25Z)
• Towards Bi-directional Skip Connections in Encoder-Decoder Architectures and Beyond [95.46272735589648]
  本稿では,デコードされた機能をエンコーダに戻すための後方スキップ接続を提案する。 我々の設計は、任意のエンコーダ・デコーダアーキテクチャにおいて前方スキップ接続と共同で適用することができる。 本稿では,2相ニューラルネットワーク探索(NAS)アルゴリズム,すなわちBiX-NASを提案する。
  論文  参考訳（メタデータ） (2022-03-11T01:38:52Z)
• RIM-Net: Recursive Implicit Fields for Unsupervised Learning of Hierarchical Shape Structures [18.5420635041504]
  RIM-Netは階層構造の教師なし推論のための暗黙の場を学習するニューラルネットワークである。 RIM-Netによる階層構造推論の品質,一貫性,解釈可能性を示す。
  論文  参考訳（メタデータ） (2022-01-30T09:31:24Z)
• Robustifying Algorithms of Learning Latent Trees with Vector Variables [92.18777020401484]
  Recursive Grouping (RG) と Chow-Liu Recursive Grouping (CLRG) のサンプル複雑性について述べる。 RG,CLRG,Neighbor Joining (NJ) およびSpectral NJ (SNJ) をトラッピングした内積を用いて強化する。 我々は、潜在木の構造学習において、最初の既知のインスタンス依存の不合理性の結果を導出する。
  論文  参考訳（メタデータ） (2021-06-02T01:37:52Z)
• A constrained recursion algorithm for batch normalization of tree-sturctured LSTM [0.29008108937701327]
  木構造LSTMは階層上の長距離相互作用を考える上で有望な方法である。 提案手法はバッチ数などのハイパーパラメータチューニングに有効である。
  論文  参考訳（メタデータ） (2020-08-21T10:31:45Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。