🤖 machine learning

Efficiently Representing Algorithms With Chain-of-Thought Transformers

本論文は、Chain-of-Thoughtトランスフォーマーが、チューリングマシンのシミュレーションに必要とされる二次的なオーバーヘッドを大幅に上回る、多項式対数（ポリログ）のオーバーヘッドのみでWord RAMアルゴリズムを効率的にシミュレートできることを実証するものである。

原著者： Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill

公開日 2026-06-19

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Yanhong Li, Anej Svete, Ashish Sabharwal, William Merrill

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

想像してみてください。あなたは、複雑なパズルを解こうとしている超スマートなロボット（Transformer）です。自分自身を助けるために、ロボットは最終的な答えを出す前に、思考をステップごとに書き残すことが許されています。これは**連鎖的思考（Chain-of-Thought: CoT）**と呼ばれます。

長い間、科学者たちは、このロボットが理論的にはあらゆる問題を解決できることを知っていました。それは、1930年代の古典的なコンピュータ（チューリングマシン）と同じです。しかし、一つ問題がありました。その古典的なコンピュータは、非常に長い紙の巻物を読んでいるようなものです。真ん中にある特定の単語を見つけるためには、最初からそこまでゆっくりと目をスクロールしていかなければなりません。これは遅くて非効率的です。

現実世界のコンピュータ（および教科書で学ぶアルゴリズム）は異なります。それらは、魔法のファイルキャビネットを持つ司書のようなもので、棚のどれほど深い場所にあっても、どんなファイルでも瞬時に取り出すことができます。これはWord RAMと呼ばれます。

問題：
論文ではこう問いかけています。「私たちの超スマートなロボットは、その『思考トークン』を使って、あの魔法の司書のように振る舞うことができるのか、それとも遅いスクロール読者のままなのか？」

これまでの研究では、ロボットは何でもできるとされていましたが、それには膨大な追加時間（例えば、ステップ数を二乗するような時間）が必要でした。もし司書のタスクが100ステップで済むはずなのに、ロボットが正しい場所にスクロールする方法を見つけるためだけに10,000ステップもかかるとしたら、それはあまりにも遅すぎて役に立ちません。

解決策：
この論文の著者たちは、こう言っています。「はい、ロボットは司書になれます。しかも、教科書に書かれている通り、ほぼ同等の速さで実行できます。」

彼らは、いくつかの巧妙なトリックを使うことで、これらの効率的な「即時アクセス」アルゴリズムを、ごくわずかな追加時間（「多項対数（polylogarithmic）」のオーバーヘッド、つまり「非常に小さく管理可能な量の追加ステップ」という意味）だけでシミュレートできることを示しました。

彼らがどのように行ったのか、ロボットの3つの異なる「衣装（アウトフィット）」を使って説明します。

1. 「成長するバックパック」（多項対数幅）

ロボットが、パズルが大きくなるにつれて少しずつ大きくなるバックパックを持っていると考えてください。

仕組み: ロボットは、思考をバイナリ数字（0と1）のリストとして書き留めます。バックパックには数値全体を一度に保持できる大きさがあるため、ロボットは瞬時に数値を比較し、正しいファイルを見つけることができます。
落とし穴: バックパックは成長する必要があります。パズルが巨大になれば、ロボットにはより大きなバックパックが必要です。これは「万能な」ロボットではありません。新しいパズルのサイズごとに、カスタムサイズのバックパックが必要なのです。

2. 「魔法の見えないインク」（連続的CoT）

ロボットが単に紙に言葉を書くだけでなく、自分にしか見えない、光り輝く透明なメモを残していると考えてください。

仕組み: ロボットは、数字のすべてのビット（例えば 101101）を書き出す代わりに、その数字全体を表す単一の「光るベクトル（数学的な形状）」を書き込みます。ロボットは、この光るメモを次のステップへと持ち運ぶことができます。
トリック: ロボットが特定の数値を読み取る必要があるとき、彼はその光るメモに「ズームイン」します。もし計算のために数字をビットごとに分解する必要があれば、光るメモをビットごとに「展開」し、計算を行い、そして次のステップのために再び「巻き戻して」光るメモに戻すことができます。
メリット: ロボットのサイズは一定（固定幅）のままですが、迷子になることなく複雑なデータを追跡するために、この「魔法のインク」を使用します。

3. 「メモリ・ループを持つロボット」（ハイブリッド・モデル）

ロボットが標準的な脳（Transformer）を持ちつつ、その下に小さな連続的なループ状のテープ（線形RNN）が走っていると考えてください。

仕組み: 標準的な脳は、思考の全履歴を振り返るのが得意です。ループ・テープは、直近の過去を記憶するのが得意です。
トリック: ロボットは、パズルを進める間、このループ・テープを使って「光るメモ」（2番目の方法のようなもの）を保持します。これには魔法のインクは必要ありません。単に、状態を前方に運ぶためにテープを使用するだけです。これにより、魔法のインクを用いた方法と同じ効率的な「即時アクセス」シミュレーションを、より標準的で物理的な構造を用いて実行できます。

大きな教訓

この論文は、Chain-of-Thoughtは、単なる古いコンピュータをシミュレートするための遅くて不器用な方法ではないということを証明しています。これらの特定のアーキテクチャのトリックを使うことで、Transformerは、リストのソートや地図上の最短経路探索といった現代の効率的なアルゴリズムを、設計通りの速度に近い速さで実行できるのです。

彼らは、ロボットを遅いスクロール読者のように扱うことで発生していた「二次的なペナルティ（巨大な減速）」を取り除きました。今や、ロボットは現代的な司書のように振る舞い、ファイルを瞬時に掴み、教科書的な問題を効率的に解くことができるのです。

要約すると： この論文は、適切なツールさえあれば、AIモデルは単なる遅い理論上の機械ではなく、私たちが毎日使っているコンピュータと同じように、効率的で実用的な問題解決者になれることを示しています。

技術要約：Chain-of-Thought Transformerによるアルゴリズムの効率的な表現

問題提起

Chain-of-Thought（CoT）トランスフォーマーは、原理的にはチューリング完全であり、あらゆるアルゴリズムをシミュレート可能であることが確立されているが（Pérez et al., 2021; Merrill and Sabharwal, 2024）、既存の理論的構成はチューリングマシン（TM）のシミュレーションに依存している。このアプローチは根本的な非効率性を導入する。すなわち、TMはランダムアクセスメモリ（RAM）を持たず、データのアクセスに線形走査を必要とするためである。その結果、標準的な教科書的アルゴリズム（例： $n$ 個の要素のソートやダイクストラ法の実行）をTMベースのCoTでシミュレートする場合、本来の計算量に対して二次的なオーバーヘッド（ $O(t^2)$ ）が発生してしまう。

本論文は、理論的な普遍性と実用的な効率性の間のギャップに対処する。具体的には、CoTトランスフォーマーが、TMシミュレーションに伴う二次的なペナルティを負うことなく、現代のアルゴリズムの標準的な抽象化であるWord RAMモデル（ $O(\log n)$ ビットのワードに対する単位コスト操作とランダムメモリアクセスを想定するモデル）上で記述されたアルゴリズムを直接シミュレートできるかどうかを問うものである。

手法

著者らは、3つの異なるアーキテクチャ設定において、Word RAMプログラムをCoTトランスフォーマーを用いて直接シミュレートすることを提案している。核心となる課題は、残差ストリーム内で $w$ ビットのワード（ここで $w = \Theta(\log(n+t))$ ）を、効率的な読み書き操作を維持しながらどのように表現し操作するかである。

1. 多項対数幅トランスフォーマー（有限精度）

アーキテクチャ: 固定精度を持ち、幅が $O(\log^2 n)$ で成長するトランスフォーマー。**右端一意ハードアテンション（UHAT）**を利用する。
表現: 整数はバイナリベクトルとして残差ストリーム内に格納される。
メカニズム: メモリへの書き込みのたびに、アドレスと値のビットペアのシーケンスとしてCoTトランスクリプトにログを残す。読み取りは、クエリアドレスに一致する最も右側のメモリブロックを特定することによって行われる。
計算量:
- 一般的なWord RAM命令：1回のRAMステップあたり $O(w^2)$ のCoTトークン。
- 乗算を含まない命令：1回のRAMステップあたり $O(w)$ のCoTトークン。
- 総オーバーヘッド： $O(t \log^2(n+t))$ または $O(t \log(n+t))$ 。

2. 連続的CoTを備えた固定幅トランスフォーマー

アーキチャ: 固定幅の対数精度トランスフォーマーであり、推論ステップにおいて離散的なトークンではなく**連続ベクトル（ソフトトークン）**を出力する。
表現: 値はレイヤー正規化ハッシュ（Layer-Norm Hashes）（ $\phi(v)$ ）を用いてエンコードされる。これは、内積による等価性チェックを可能にする単位ノルムベクトル表現である。
メカニズム:
- シリアライズ: ハッシュ $\phi(v)$ をバイナリビットストリームに変換するには、反復的な除算（ $\lfloor v/2 \rfloor$ と $v \mod 2$ の計算）が必要である。これは、ステップ $s$ における値 $v$ が $v \le s$ を満たす「制限付き」Word RAMの正規形によって可能となる。
- 永続性: ソフトトークンは永続的なレジスタとして機能し、デコーディングステップを越えて現在の状態（ $\phi(v)$ ）を保持する。これにより、値を再シリアライズする必要なく状態を運ぶことができる。
- オラクル: 複雑な算術演算は、シリアライズされたビットストリーム上で動作するTMオラクル・サブルーチンによって処理され、結果はハッシュ表現へとデシリアライズされる。
計算量: $O(t \cdot \kappa(w))$ デコーディングステップ。ここで $\kappa(w)$ は1つの命令のTMコストである。フラットな命令セットの場合、これは $O(t \log^2(n+t))$ （フル算術）または $O(t \log(n+t))$ （単純算術）となる。

3. ハイブリッド・トランスフォーマー-RNNモデル

アーキテクチャ: 単一の線形RNN層によって拡張された固定幅トランスフォーマー。
メカニズム: この設定では、前述のモデルの連続的なソフトトークンの代わりに、RNNの隠れ状態を用いて永続性を維持する。RNNは、以前の連続ベクトルが担っていた反復的なビット抽出および再構成（シリアライズ／デシリアライズ）を実行する。
計算量: 連続CoTの結果と一致する： $O(t \cdot \kappa(w))$ ステップ。

主な貢献

直接的なWord RAMシミュレーション: 本論文は、CoTトランスフォーマーが中間層としてのチューリングマシンを経由することなく、Word RAMアルゴリズムを直接シミュレートできることを証明している。
タイトなオーバーヘッド境界:
- 離散CoT（多項対数幅）の場合、オーバーヘッドは命令あたり $O(w^2)$ となり、情報理論的な下限である $\Omega(w)$ に対し、対数因子1つ分を除いて一致する。
- 乗算を含まない命令セットの場合、オーバーヘッドは正確に $O(w)$ となり、これは離散CoTにとって最適である。
- これは、TMベースのシミュレーションが $O(t^2)$ ステップを必要とするのと鮮明な対照をなしている。
効率化のためのアーキテクチャ拡張: 著者らは、固定幅トランスフォーマーが連続CoTまたは線形RNN層のいずれかで拡張されることで、これらの効率的なシミュレーションを実現できることを示している。これらの最小限の拡張は、固定幅離散モデルに固有のビット抽出と状態保持のボトルネックを解消する。
制限付きWord RAMの等価性: ステップ $s$ における値が $s$ によって制限される「制限付き」Word RAMへ任意のWord RAMをシミュレートできることを示す技術的補題。これは、固定幅設定におけるビット抽出の証明を容易にする。

結果

本論文は、CoTトランスフォーマーが、 $n$ に対して多項対数的なオーバーヘッド（具体的には $O(\log^2 n)$ または $O(\log n)$ ステップ）のみで教科書的なアルゴリズムを実行できることを確立している。

ソート: $O(n \log n \cdot \text{polylog}(n))$ ステップで実行可能。
ダイクストラ法: $O((E + V \log V) \cdot \text{polylog}(n))$ ステップで実行可能。
命令セット: これらの結果は、「フラット」な命令セット（入れ子構造の式を含まないもの）に対して成立する。フル算術セット（ $\times, \div, \mod$ を含む）の場合、オーバーヘッドは $O(\log^2 n)$ となり、単純算術セット（ $\times, \div, \mod$ を除く）の場合は $O(\log n)$ に減少する。

意義と主張

本論文は、トランスフォーマーの理論的能力（チューリング完全性）と、アルゴリズム的推論に必要な実用的な効率性の間のギャップを埋めるものである。CoTが近最適（near-optimal）なオーバーヘッドでWord RAMをシミュレートできることを示すことで、著者らは、アルゴリズムシミュレーションに必要だと従来想定されていた「二次的な増大」は、TMという抽象化によるアーティファクト（人工的な現象）であり、トランスフォーマー自体の固有の限界ではないと主張している。

その意義は以下の点にある：

理論的正当化: CoT推論モデルが複雑なアルゴリズム的タスクを効率的に解決できることに対し、理論的な根拠を提供し、理論的な表現力と推論モデル（例：Snell et al., 2024; DeepSeek-AI, 2025）の経験的な観察結果を一致させた。
アーキテクチャへの洞察: 固定幅モデルにおいて効率的なアルゴリズムシミュレーションを実現するには、特定の現実的な拡張（連続CoTまたはRNN層）が十分であることを示しており、これらの機能が実用的なアルゴリズム推論において重要であることを示唆している。
最適性: 提案されたシミュレーションが離散CoTにおいて本質的にタイトであり、情報理論的な下限と一致していることを実証している。

著者らは、これらの拡張（連続CoTやRNN層）がどの程度厳密に必要であるか、また、これらの拡張が現在のモデルにおける実用的なアルゴリズム推論に利益をもたらすかについては、未解決の問いであるとして、謙虚な姿勢を保っている。