論文の概要: Efficiently Representing Algorithms With Chain-of-Thought Transformers

• arxiv url: http://arxiv.org/abs/2606.19697v1
• Date: Thu, 18 Jun 2026 01:49:29 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-19 18:23:39.603307
• Title: Efficiently Representing Algorithms With Chain-of-Thought Transformers
• Title（参考訳）: Chain-of-Thought変換器を用いたアルゴリズムの効率的な表現
• Authors: Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill,
• Abstract要約: 思考の連鎖変換器はチューリングマシンをシミュレートし、任意の計算を行う。 我々は,CoTエンファンカンが多対数オーバーヘッドのみのWord RAMアルゴリズムを$n$で効率的にシミュレートできることを示す。
• 参考スコア（独自算出の注目度）: 45.60818649759173
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The increasing popularity of \emph{reasoning} models -- language models that output a series of reasoning or thought tokens before producing an answer -- is justified, in part, by theoretical results showing that chain-of-thought (CoT) transformers can simulate Turing machines, and thus perform arbitrary computation. However, the Turing machine, while suitable for complexity-theoretic analysis, is not convenient, intuitive, or efficient for discussing algorithms. Algorithms are typically designed and analyzed at a higher level of abstraction, captured by the \emph{Word RAM} model with random-access memory and unit-cost operations on $\bigO(\log n)$-bit words. As a result, Word RAM algorithms can be substantially more efficient than their Turing machine counterparts, raising the question: \emph{Can CoT transformers efficiently simulate Word RAM algorithms?} For instance, can they sort $n$ items in $\bigO(n \log n)$ steps or run Dijkstra's algorithm in $\bigO(E + V \log V)$ steps? We answer affirmatively, up to poly-logarithmic overhead. We first establish this for finite-precision transformers with poly-logarithmic width and rightmost unique hard attention, then strengthen the result to two more practical settings with finite width and log-precision: \emph{continuous} CoT, where reasoning takes the form of vectors rather than tokens, and a \emph{hybrid} architecture in which transformer layers sit atop a recurrent (linear RNN) layer. In all three cases, we find that CoT \emph{can} efficiently simulate any Word RAM algorithm with only a poly-logarithmic overhead in $n$. This overhead reduces to log-square when the Word RAM has a ``flat'' instruction set, and only logarithmic for multiplication-free flat instructions -- in stark contrast to known CoT simulations of Turing machines, which require quadratic overhead over Word RAM.
• Abstract（参考訳）: 答を生成する前に一連の推論や思考トークンを出力する言語モデルである 'emph{reasoning} モデルの人気は、理論的な結果から部分的には、チェーン・オブ・ソート (CoT) トランスフォーマーがチューリングマシンをシミュレートし、任意の計算を行うことができることを示している。 しかし、チューリングマシンは複雑性理論解析に適しているが、アルゴリズムの議論には便利、直感的、あるいは効率的ではない。 アルゴリズムは一般に、ランダムアクセスメモリと$\bigO(\log n)$-bitワード上のユニットコスト操作を備えた \emph{Word RAM} モデルによって、より高レベルの抽象化で設計され、分析される。 その結果、Word RAMアルゴリズムはチューリングマシンよりもはるかに効率が良く、質問を提起する: \emph{Can CoT transformerはWord RAMアルゴリズムを効率的にシミュレートする。 例えば、$n$の項目を$\bigO(n \log n)$ stepsでソートするか、$\bigO(E + V \log V)$ stepsでDijkstraのアルゴリズムを実行できますか? 我々は多言語的オーバーヘッドまで肯定的に答える。 まず,多対数幅の有限精度変圧器と,直交(線形RNN)層上にトランスフォーマー層を配置する「emph{continuous} CoT」と「emph{hybrid" アーキテクチャ」という,有限幅および対数精度のより実用的な2つの設定について検討する。 これら3つのケースにおいて、CoT \emph{can} は任意の Word RAM アルゴリズムを効率よくシミュレートする。 このオーバーヘッドは、Word RAMが ``flat'' 命令セットを持ち、乗算不要なフラット命令のための対数しか持たない場合、対数二乗に減少する。

関連論文リスト

• On the Computational Hardness of Transformers [14.73362105392153]
  この結果から, トランスフォーマーの効率は, 独立評価値のLH$よりも高いことがわかった。 小さな埋め込み方式では、$LH$アテンションヘッドは別々に$LHN2 + o(1)$時間を必要とする。 大規模な埋め込み方式では、$LHN+ o(1)$算術演算を使用して別々に$LH$アテンションヘッドを計算することができる。
  論文  参考訳（メタデータ） (2026-03-11T21:48:43Z)
• Unifying Graph Measures and Stabilizer Decompositions for the Classical Simulation of Quantum Circuits [0.0]
  我々は、$n$-qubit 回路をシミュレートする2つの新しいアルゴリズムを提示する。 提案アルゴリズムは単純で、線形メモリしか必要とせず、自明に並列であり、ZX-ダイアグラムの単純化ルーチンとうまく相互作用する。
  論文  参考訳（メタデータ） (2026-03-06T15:27:23Z)
• Asymptotic yet practical optimization of quantum circuits implementing GF($2^m$) multiplication and division operations [1.1694898979785655]
  乗算演算と除算演算に最適化された量子回路を提案する。 我々のアシラフリーGF乗算回路はゲートカウントの複雑さが$O(mlog3)$である。 我々は,CNOTとToffoliゲート数の両方の削減を含む,$m$の暗号関連値に対して,実用的な利点を示す。
  論文  参考訳（メタデータ） (2025-11-25T18:43:08Z)
• Efficient Turing Machine Simulation with Transformers [6.70318953627082]
  定ビットサイズ変換器はチューリング完全であることが知られている。 既存の構成には、シミュレーションされたチューリングマシンステップ当たりの$(s(n))$チェーン・オブ・シントステップが必要である。 我々は任意の$(t(n),s(n)$-bounded multi-tape TM が定数ビットサイズ変換器でシミュレート可能であることを証明した。
  論文  参考訳（メタデータ） (2025-09-28T01:30:39Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)

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

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