💬 NLP

When Does Tool Use Increase the Expressive Power of Finite-Precision Recurrent Models?

本論文は、有限状態のツールは有限精度の回帰モデルに対して計算能力を殆ど追加しない一方で、単一の最小限の無限状態ツール（読み書き可能なテープ）がそれらをチューリング完全にするという明確な二分法を確立しており、この能力は選択的アフィン状態空間モデルによって具体的に実現されている。

原著者： Nikola Zubić, Qian Li, Yuyi Wang, Davide Scaramuzza

公開日 2026-07-08

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

CC BY 4.0

原著者： Nikola Zubić, Qian Li, Yuyi Wang, Davide Scaramuzza

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

想像してみてください。あなたは、非常に賢いけれど、少し忘れっぽいロボットを所有しています。このロボットは「有限精度回帰モデル（Finite-Precision Recurrent Model）」です。平たく言えば、情報をステップごとに処理するコンピュータプログラムですが、メモリが極めて小さく固定されています（例えば、100マスしかないメモ帳のようなものです）。このメモリが小さく固定されているため、このロボットには限界があります。単純で繰り返しの多いパターンしか解けません。無限に数を数えたり、長い物語を覚えたり、前後を行ったり来たりする必要がある複雑なパズルを解いたりすることはできません。

この論文は、シンプルな問いを投げかけています。もし、この忘れっぽいロボットに「道具」を与えたらどうなるでしょうか？

著者たちの発見によれば、答えは「どのような種類の道具を与えるか」によって完全に決まります。彼らは、明確な「どちらか一方」という分岐点を見つけ出しました。

1. 「有限」の道具：小さな計算機

あなたのロボットに、基本的な計算しかできず、一度に一つの数字しか表示できない小さな画面を持つ計算機を与えたと想像してください。

結果： ロボットはそれほど賢くなりません。単に、計算機が何をしているかを覚えておくために、自分自身のメモリをほんの少し消費するだけです。
例え： メモリの小さい人に、付箋（ポストイット）を渡すようなものです。一つのことを書き留めることはできますが、それでも複雑な謎を解くことはできません。ロボットは依然として「有限状態」のままです。単純で繰り返しの多いタスクしか実行できません。
論文の主張： もし道具自体が限られたメモリと限られたコマンドしか持っていない場合、ロボットはその道具のメモリを自分の頭の中に「コピー」できてしまいます。そのため、新しい能力はほとんど得られません。

2. 「無限」の道具：無限のテープ

次に、ロボットに（古いカセットテープや巻物のような）無限に長い「テープ」を与えたと想像してください。ロボットができることは、以下の3つだけです。

現在の位置にある記号を読み取る。
新しい記号を書き込む。
ヘッドを左または右に一歩動かす。

結果： 突然、ロボットは天才になります。どんなに複雑であっても、コンピュータで解けるあらゆる問題を解けるようになります。それは「チューリング完全」になったのです。
例え： メモリの小さい人に、図書館を与えたようなものです。たとえ脳が小さくても、図書館の中をあちこち歩き回り、棚にメモを読み書きすることができます。これにより、彼らは最も難しい数学の問題を解いたり、小説を書いたり、暗号を解読したりできるようになります。「無限のテープ」が外部の脳として機能するのです。
論文の主張： この単純な無限テープがたった一つあるだけで、単純なロボットを汎用コンピュータへと変貌させることができます。ロボットには、この無限の力を制御するために、（テープ上の「どこ」にいるか、そして「今何を考えているか」を覚えるための）ごくわずかな内部メモリさえあればよいのです。

「魔法」の要素：選択性（Selectivity）

この論文は、これが単なる理論上の話ではなく、**選択的状態空間モデル（Selective State-Space Model: SSM）**と呼ばれる現代的なAIアーキテクチャにおいて実際に機能することを示しています。

例え： 標準的なロボットを、固定されたレールの上を進む列車だと考えてください。彼らは常に同じように進みます。一方、「選択的」なロボットは、目の前にあるものに応じて進路を変えられる列車のようなものです。
著者たちは、この「進路を変えられる」ロボットに、わずかなメモリと無限のテープを与えれば、あらゆるコンピュータプログラムを完璧にシミュレートできることを証明しました。「選択性」（入力に基づいて挙動を変えること）こそが、無限の力への扉を開く鍵なのです。

「等価性」テスト（具体的な例）

これを証明するために、著者たちは特定のテストを用いました。それは、**「2つの長い数字の列が同一であるかどうかをチェックする」**というテストです。

道具がない場合： もし数字の列が1,0iles桁あったら、ロボットはそれらを照合するために1,000桁分のメモリを持つ脳を必要とします。もし100万桁あったら、100万桁のメモリが必要です。小さなロボットには不可能です。
テープという道具がある場合： ロボットは最初の列をテープに書き込み、その後、行ったり来たりしながら2番目の列と比較することができます。彼は「今、何番目の桁を比較しているか」を覚えるための、ごくわずかな内部メモリさえあればよいのです。テープが重労働を引き受けてくれるからです。

まとめ

この論文は、**「道具が存在するからといって、AIが賢くなるわけではない」**と結論付けています。

もし道具が小さく限定的なら、AIも限定的なままです。
もし道具が「無限のメモリテープ」（たとえ非常に単純なコマンドしか持っていなくても）であり、かつ、そのテープを制御するための特定の「選択的」なメカニズムを備えているならば、AIは無限の力を手に入れます。

これにより、AIが外部ツールを使用することを許可された場合、どれだけの「脳の力（内部メモリ）」が必要になるのかについて、正確な地図が示されました。巨大なノートがあれば、巨大な脳は必要ないのです。

技術要約：ツール利用は有限精度の再帰モデルの表現力をいつ向上させるのか？

問題提起

現代のシーケンスモデルは、トークン生成と外部ツール（計算機、コードインタープリタ、検索システムなど）への呼び出しを交互に行うエージェントとして、ますます展開されている。その経験的な成功は明白であるが、根本的な理論的問いが未解決のままである。すなわち、**「どのような特定のツールが、固定された有限精度の再帰モデルの計算表現力を向上させ、それはどの程度向上させ、内部メモリコストはどの程度になるのか？」**という問いである。

既存の文献は、固定された有限精度の再帰モデル（状態空間モデル（SSM）を含む）が有限オートマトン（FSM）と同等であり、正規言語のみを認識することを確立している。思考の連鎖（Chain-of-thought）によるデコーディングは、生成ステップ数に制約された限定的な利得しか提供しない。本論文は、外部ツールへのアクセスがこの計算の景観をどのように変化させるかについて、アーキテクチャレベルの正確な特徴付けを行い、単に限定的なメモリを追加するだけのツールと、計算能力を根本的に拡張するツールの区別を試みる。

手法

著者らは、シーケンスモデルを、有限のコマンド／観測インターフェースを介してオラクルと相互作用する決定性有限状態コントローラとして抽象化している。

コントローラモデル: $B$ ビットの内部状態を持つコントローラは、最大 $2^B$ 個の構成を持つFSMとしてモデル化される。これは入力を読み込み、その後、トークンの生成、ツールのコマンド発行、観測の受信、または停止を行う生成フェーズに入る。
ツールインターフェース: 本論文では、2つの異なるクラスのツールを分析している：
1. 有限状態有界インターフェース・オラクル: 有限のメモリ集合と、有限のコマンド／観測アルファベットを持つツール。
2. 無界テープ・オラクル: 無界のテープ上での局所的な読み取り／書き込み／移動操作（チューリングマシンのテープに類似）をサポートする、最小限の無限状態ツール。
実現: 理論的な構成は、有限精度の選択的アフィンSSM（selective affine SSMs）へとマッピングされる。著者らは、遷移行列が選択的（現在の観測トークンに依存する）であれば、任意の観測駆動型有限状態コントローラは、バイナリのワンホット隠れ状態、 $\{0, 1\}$ 遷移行列、およびゼロバイアスを持つ1層のSSMによって正確に実現できることを証明している。

主な貢献と結果

1. 有限状態ツールは（ほとんど）何も加えない

本論文は、「積状態シミュレーション（product-state simulation）」定理を確立している。ツール自体がメモリ集合 $M$ と有限のインターフェースを持つ有限状態マシンである場合、コントローラはそのツールの状態を内部化できる。

結果: 拡張されたシステムは依然として有限状態マシンである。内部メモリコストは $\log_2 |M| + O(1)$ ビットしか増加しない。
示唆: 有限状態のツールは、認識可能な言語のクラスを正規言語以上に高めることはない。インターフェースの有限性が不可欠であり、そうでなければ、任意の初期化やコマンドから観測へのマップが非正規な振る舞いをエンコードしてしまう可能性がある。

2. 最小限の無界ツールがチューリング完全性を実現する

著者らは、局所的な読み取り／書き込み／移動コマンドをサポートする「テープ・オラクル」を定義している。

結果: コントローラは、このテープ・オラクルと相互作用する場合、 $O(\log |Q| + \log |\Gamma|)$ ビットの内部メモリ（ここで $Q$ はチューリングマシンの状態集合、 $\Gamma$ はテープアルファベットである）を持つことで、単一テープのチューリングマシンをシミュレートできる。
チューリング完全性: システムはチューリング完全となる。コントローラはテープを保持する必要はなく、シミュレートされるマシンの現在の状態と動作モードのみを保持すればよい。
具体的な分離: 本論文は、等価性問題 $EQ_n$ $E Q_{n}$ （2つの $n$ $n$ ビット文字列が等しいかどうかの判定）を用いた具体的な指数関数的下界を提供している。
- ツールなしの場合: $EQ_n$ を解くには、少なくとも $2^n$ 個の状態を持つコントローラが必要である。
- テープアクセスがある場合: 定数サイズのコントローラ（ $n$ に依存しない）が、すべての $n$ に対して $EQ_n$ を解くことができる。

3. 選択的SSMによる正確な実現

本論文は、上述の理論的な有限状態コントローラが単なる抽象的な構成ではなく、特定のニューラルアーキテクチャによって正確に実現可能であることを証明している。

アーキテクチャ: 以下の条件を満たす、1層の有限精度選択的アフィンSSM：
- バイナリのワンホット隠れた状態。
- エントリが $\{0, 1\}$ に含まれる遷移行列。
- ゼロバイアス。
- 選択性（Selectivity）: 遷移行列 $A_\omega$ は現在の観測トークン $\omega$ に依存する。
選択性の重要性: 著者らは、選択性が極めて重要なアーキテクチャ上の要素であることを強調している。固定された線形時不変な再帰（非選択的）では、この設定において任意の有限制御を実装することはできない。
次元: 隠れ次元は $d = O(|Q| \cdot |\Gamma|)$ であり、ワンホットエンコーディングを使用した場合、シミュレートされるマシンの状態空間のサイズに対して線形である。

4. 正確なリソース計量（補足結果）

補足資料では、リソース境界を精緻化している：

対数的シミュレーション: マシンの記述を固定されたリードアウトにハードコードし、テープを外部メモリとして使用することで、 $O(\log B)$ の再帰ビットで任意の $B$ 状態チューリングマシンをシミュレートできる。これにより、次元は $O(|Q|)$ から $O(\log |Q|)$ へと改善される。
直接実現の不可能性: 外部メモリなしでは、任意の $B$ 状態の遷移マップを単一のアフィン再帰更新で正確に実現するために、正確に $B-1$ の全再帰次元が必要となる。これは、対数的な利得が外部テープへの状態のオフロードに厳密に依存していることを裏付けている。

意義と主張

本論文は、ツール拡張された再帰計算の精密なリソース計量の全体像を提供することを目的としている。その主要な意義は、以下の鋭い二分法を確立した点にある：

有限状態ツールは、表現力のクラスという観点では計算量的に「無料」であるが（正規言語のまま）、小さな線形メモリコストを伴う。
無界テープツールは、コントローラが選択性をサポートしている場合に限り、最小限の対数的内部メモリコストで、表現力を劇的に飛躍させる（チューリング完全性へ）。

本研究は、ツール使用がいつパワーを高めるのかという問いを解決している。それは、コントローラ自身ではなく、ツールの状態空間とインターフェースによって完全に支配されている。これらの結果は、訓練、近似、または確率的な議論に頼ることのない、正確な構成と無条件の下界に基づいている。結論として、現代のSSMの「選択的」な性質（遷移が入力に依存すること）こそが、これらのモデルが外部メモリと組み合わされた際に正確な有限制御として機能することを可能にする特定のメカニズムであり、有限精度のモデルとチューリング完全な計算との間の溝を埋めるものであるとしている。