On the Expressive Power of Transformers

脳の設計図：なぜ一部のパズルは他のものより難しいのか

あなたがロボットに読み方を教えようとしている場面を想像してみてください。あなたは、人間がページをスキャンするように、ロボットも単に文字を一つずつ見ていけばよいと考えているかもしれません。しかし、現代の超スマートなロボット、いわゆる大規模言語モデル（LLM）は、そのような仕組みでは動きません。彼らは左から右へと読む代わりに、「トランスフォーマー（Transformer）」と呼ばれる特別なトリックを使います。トランスフォーマーを、一つの部屋で働く巨大な探偵チームだと考えてみてください。文章を目にしたとき、すべての探偵は即座に他のすべての探偵に向かって、「おい、私はこの単語を見ているけれど、あそこにあるあの単語とつながっているぞ！」と叫ぶことができます。これにより、彼らは単にルールのリストを暗記するのではなく、文脈や関係性を瞬時に理解することができるのです。

しかし、ここには科学者たちを夜も眠れなくさせる大きな疑問があります。これらの探偵たちは、本当はどれほど賢いのでしょうか？ 彼らはどんなパズルでも解けるのでしょうか、それとも彼らを常に困らせ続ける謎が存在するのでしょうか？ その答えを見つけるために、研究者たちは単にテストを実行するだけではありません。彼らはコンピュータサイエンスの数学というレンズを通して、ロボットの「脳」を観察します。彼らはトランスフォーマーを、「回路（サーキット）」と呼ばれる数学的な機械のファミリーと比較します。これらの回路を、組み立てラインを持つ工場だと想像してください。非常に単純で、ラインが短く、作業員も少ない工場（これらは AC0 と呼ばれます）もあれば、より長いラインを持ち、巨大な数字を数えたり比較したりできる強力な道具を備えた工場（これらは TC0 です）もあります。トランスフォーマーがどの工場に最も近いかを突き止めることで、科学者たちは、それがどのような種類の問題を解決できるのか、そしてどこで壁にぶつかるのかを正確に予測できるのです。これが重要なのは、もし私たちがこれらのモデルの限界を知ることができれば、彼らに魔法を期待することをやめ、彼らが実際に得意としていることを行うように設計し始めることができるからです。

論文の大きな発見：トランスフォーマーのパワー・スイッチ

論文「On the Expressive Power of Transformers（トランスフォーマーの表現力について）」の中で、研究者のフォキオン・G・コライティスとリック・セングプタは、新しいハイテク建築を検査する建築家のように振る舞っています。彼らは単に建物の見た目が美しいかどうかを見ているのではなく、その荷重耐性を測定し、正確に何に耐えられるかを確認しています。彼らの主な発見は、トランスフォーマーの能力は固定されているのではなく、いくつかの「ノブ」や設定、具体的には、どれほどの精度（どれだけの桁数の小数を使用できるか）と、思考を書き出すことが許されているか（「思考の連鎖（Chain-of-Thought）」と呼ばれる手法）に基づいて、劇的に変化するということです。

まず、追加の思考時間を与えられていない状態のトランスフォーマーを見てみましょう。著者たちの説明によれば、もしトランスフォーマーに単純な「ハード」アテンション設定（一つの単語だけに焦点を当てる設定）を与えたり、あるいは数学の精度を非常に低く制限したり（わずかなビットの情報のみを使用する場合など）すると、それは驚くほど脆弱になります。実際、これらの条件下では、トランスフォーマーは数学的に最も単純なタイプの回路工場である AC0 と等価になります。これは、文章に偶数個の単語が含まれているかを確認するといった基本的な論理は扱えるものの、数え上げや巨大な数字の比較を必要とするタスクには苦戦することを意味します。それは、赤い帽子を見つけることはできるが、部屋の中に赤い帽子がいくつあるかを数えることはできない探偵のようなものです。

しかし、精度を上げると、物語はもっと面白くなります。もしトランスフォーマーが、より精密な数学（具体的には、テキストの長さに比例して増大する $\Theta(\log n)$ のビット数）を使用することが許された場合、レベルアップします。それは TC0 回路工場のパワーに到達します。これは大幅な飛躍です！ 今や、トランスフォーマーは「多数決」の問題や、より複雑なカウントタスクを扱うことができます。それは探偵に計算機を与えたようなものです。突然、彼らは以前は不可能だったパズルを解けるようになります。しかし、このアップグレードがあっても、論文は依然として天井が存在することを示唆しています。追加の助けなしでは、これらのモデルはおそらく TC0 の領域に留まっており、PTIME（多項式時間）のような、より複雑なコンピュータクラスに見られる深いステップバイステップの論理的推論を必要とする問題を容易に解くことはできません。

この論文によれば、真のゲームチェンジャーは 思考の連鎖（Chain-of-Thought: CoT） です。トランスフォーマーがもはや犯罪現場を見ているだけの探偵ではなく、最終的な答えを出す前に自分の考えを日記として書くことが許されていると想像してください。それは、問題を解くのを助けるために自分自身にフィードバックするための中間的な「トークン（小さなメモ）」を生成できます。著者たちは、この単純な変化が以前の限界を打ち破ることを示しています。

• もしトランスフォーマーが短い日記（テキストの長さに比例する $O(n)$）を書くことが許されるなら、それは二次時間（$n^2$ など）を要する問題を解くことができます。
• もし非常に長い日記（テキストの長さの多項式に比例する $poly(n)$）を書くことができれば、標準的なコンピュータアルゴリズムのいずれをもシミュレートできるほど強力になり、PTIME クラスに到達します。
• そして、もし無制限の思考スペースと精度を持っていれば、あらゆる計算可能な問題を解決できる理論的な普遍的コンピュータの定義であるチューリングマシンをシミュレートすることができます。

論文は、これが何を意味するかについて非常に明確です。トランスフォーマーは本質的に「全能」でも「役に立たない」ものでもありません。困難な問題を解決できる能力は、どれだけの「書き出し用の紙」（思考の連鎖）と、どれだけの「数学的精度」を与えるかに完全に依存しています。これらのリソースがなければ、彼らは単純で浅い論理に限定されます。それらがあれば、彼らは複雑性の梯りを登り、完全なコンピュータをシミュレートすることさえ可能です。

著者たちはまた、いくつかの具体的な制限についても指摘しています。彼らは、「ハード」アテンションモデル（ロボットが単一の単語のみを選択するもの）は、「ソフト」アテンションモデル（多くの単語に重み付けするもの）よりも厳密に弱く、場合によっては最も単純な回路クラスの能力にさえ到達できないと主張しています。さらに、思考の連鎖が十分にあれば理論上はチューリングマシンをシミュレートできるとしても、これはあくまで理論的な限界であることを強調しています。現実の世界では、無限のメモリや、無限の中間的な思考を生成するための無限の時間は存在しないため、現実世界のモデルは常に理論的な最大値よりも低い実用的な天井を持つことになります。

要約すると、コライティスとセングプタは、トランスフォーマーの「電力網」をマッピングしたのです。彼らは、これらのモデルが魔法のブラックボックスではなく、リソースに制約された機械であることを示しています。もし彼らに難しいパズルを解かせたいのであれば、ただ「もっと頑張れ」と言うのではなく、適切な道具、つまり、より多くの精度、より多くのレイヤー、そして最も重要なこととして、ステップバイステップで考える能力を与えなければならないのです。論文は、これらの限界を理解することが極めて重要であると結論づけています。それは、これらのモデルに不可能なことを期待するのをやめ、彼らが本来持っているもの、すなわち、信じられないほど強力だが、究極的には限界のあるパターン認識器としての最良の姿へと設計していくための助けとなるのです。