💬 NLP

Modern Hopfield Networks Require Chain-of-Thought to Solve $\mathsf{NC}^1$ -Hard Problems

本論文は、標準的なモダン・ホップフィールド・ネットワークが理論的に $\mathsf{TC}^0$ 計算量クラスに限定されており、 $\mathsf{NC}^1$ 困難な問題を解決できないことを確立した上で、思考の連鎖（Chain-of-Thought）メカニズムを備えることで、それらがこれらの境界を越え、本質的に直列的なタスクを解決できることを示している。

原著者： Yang Cao, Xiaoyu Li, Yuanpeng Li, Yingyu Liang, Zhenmei Shi, Zhao Song

公開日 2026-01-26

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

CC BY 4.0

原著者： Yang Cao, Xiaoyu Li, Yuanpeng Li, Yingyu Liang, Zhenmei Shi, Zhao Song

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

全体像：超強力な図書アシスタント

**モダン・ホップフィールド・ネットワーク（MHN）**を、非常に高度で超高速な「図書アシスタント」だと想像してみてください。このアシスタントの主な仕事は、バラバラになったメモの山（入力）を見て、膨大な記憶の本の中から、最も似ている完璧なページを瞬時に見つけ出すことです。

AIの世界において、これらのアシスタントは驚異的な速さと巨大なメモリを持っていることで有名です。これらは、情報を集めるための「スーパー・プール」や、適切な詳細に焦点を当てるための「スーパー・アテンション（超集中力）」として、古い、より遅いAIシステムの一部を置き換えるために頻繁に使用されます。

しかし、この論文は根本的な問いを投げかけます。「このアシスタントは、本当はどれほど賢いのか？」 どんな問題でも解けるのでしょうか？それとも、どれほど速くても、どうしても解けない問題があるのでしょうか？

発見：「即時的」なアシスタントには天井がある

この論文の著者たちは、回路の探偵のように振る舞いました。彼らは、これらのAIアシスタントがどのような論理を扱えるのかを確認するために、その内部配線を調べました。

その結果、標準的なモダン・ホップフィールド・ネットワーク（たとえ多くの層を持っていたとしても）は、**「即時的な計算機」**のようなものであることが分かりました。これらは、多くの小さな並列タスクに分解して、すべて同時に実行できる作業を行うのが非常に得意です。コンピュータサイエンスの用語では、これらは TC0 と呼ばれるクラスに属しています。

比喩：
工場の1,000人の作業員チームを想像してください。

標準的なMHN: 各作業員がパズルのピースを受け取り、全員が同時に自分のパートを完了させます。彼らは単純な壁を非常に素早く作ることができます。
限界: もしタスクが、「前の人が作業を終えて次の人に道具を渡すのを待つ」といった、連鎖的な作業（「逐次的」なタスク）を必要とする場合、この工場は機能不全に陥ります。彼らは「ステップA、次にステップB、次にステップC」という長い連鎖を必要とするタスクを実行することができません。

この論文は、これらのネットワークが、このような種類のステップ・バイ・ステップの推論を必要とする複雑な問題を解けないことを証明しています。具体的には、以下の問題を解くことができません：

グラフ連結性: 迷路の中で、道に迷うことなく地点Aから地点Bまで歩いて行けるかどうかを判断すること。
木同型性: 2つの複雑な家系図（または組織図）が、名前こそ違えど、構造として同一であるかどうかを見分けること。

これらの問題は、NC1 と呼ばれるより難しいカテゴリーに属しています。論文は、もし数学における未解決の大きな謎（TC0とNC1が等しいという仮説）が否定されない限り、これらのAIアシスタントは、本質的にこれらのパズルを解くには**「浅すぎる」**のだと主張しています。彼らは速いのですが、深い逐次的な思考力が欠けているのです。

解決策：アシスタントに「考える帽子」を与える（Chain-of-Thought）

もし標準的なアシスタントが行き詰まっているとしたら、修正できるのでしょうか？論文は、**「はい」**と答えています。ただし、特定のツールを与える場合に限ります。それが 「Chain-of-Thought（思考の連鎖、CoT）」 です。

比喩：

CoTなし: アシスタントは、一瞬の巨大な眼差しだけで迷路を解こうとします。全体像は見えていますが、思考を「歩ませる」ことができないため、経路を見落としてしまいます。
CoTあり: 私たちはアシスタントにこう指示します。「ただ答えを推測するのではなく、手順を書き出しなさい。『まず左の道を確認する。次に右の道を確認する。それから、それらのメモを組み合わせて出口を見つける』といった具合に。」

ネットワークに中間的な「思考」（例えば、メモ帳に手順を書き出すようなこと）を生成させることで、ネットワークの性質が変わります。それは単なる「即時的な計算機」であることをやめ、「ステップ・バイ・ステップの推論者」へと進化するのです。

結果：
この「考える帽子」（Chain-of-Thought）を被せることで、モダン・ホップフィールド・ネットワークは、以前は不可能だったそれらの難しい問題（迷路や家系図など）をついに解けるようになります。ネットワークは、その本来の限界を超越するのです。

調査結果のまとめ

限界: 標準的なモダン・ホップフィールド・ネットワークは強力ですが、限界もあります。それらは超高速なフォトスキャナーのようなものです。パターンを瞬時に認識することには長けていますが、長い論理の連鎖を必要とするパズルを解くのは苦手です。複雑な迷路をナビゲートしたり、複雑な木の構造を比較したりする特定の難しい問題は解けません。
修正方法: 「Chain-of-Thought」（AIに推論のステップを一つずつ書き出させる仕組み）を追加すれば、この天井を突き破ることができます。これにより、AIはステップ・バイ・ステップの難しい問題を解く能力を獲得します。
結論: この論文は明確な境界線を引いています。標準的なMHNはメモリやパターンマッチングには優れていますが、もし深い論理的推論を行わせたいのであれば、必ずステップ・バイ・ステップで考える方法を与えなければなりません。それなしでは、彼らは高い壁に突き当たってしまうのです。

テクニカル・サマリー：モダン・ホップフィールド・ネットワークがNC1困難問題を解決するには思考の連鎖（Chain-of-Thought）を必要とする

問題提起

モダン・ホップフィールド・ネットワーク（MHN）は、プーリング層、LSTM、およびアテンション・メカニズムの有効な代替品として、ディープラーニングにおいて強力なコンポーネントとして台頭しています。近年の進歩により、その記憶容量と検索効率は向上していますが、計算能力の理論的な境界については未だ十分に解明されていません。具体的には、回路複雑性理論の観点から見たとき、MHNがどのような問題を実行可能であるかという厳密な特性付けが欠如しています。本研究が取り組む中心的な問いは、「回路複雑性の観点におけるモダン・ホップフィールド・ネットワークの根本的な限界は何か？」という点です。

手法

著者らは、MHNが要求する計算リソースを厳密に分析するために、回路複雑性理論の枠組みを採用しています。その手法は以下の通りです。

計算回路へのマッピング: 著者らは、MHNのアーキテクチャ構成要素（ホップフィールド層、カーネル化されたバリアント、および関連するフィードフォワード・ネットワークを含む）をブール回路へとマッピングします。
精度とアーキテクチャの制約: 分析は、多項式精度（ $p \le \text{poly}(n)$ ）、定数深さ（ $m = O(1)$ ）、および線形隠れ次元（ $d \le O(n)$ ）を持つネットワークに焦点を当てています。
複雑性クラスの分析: 浮動小数点演算、行列乗算、および非線形活性化関数を含む操作をシミュレートするために必要な閾値回路の深さとサイズを分析することで、これらのネットワークが属する特定の複雑性クラス（例： $\text{TC}^0$ , $\text{NC}^1$ ）を決定します。
困難性の証明: MHNが特定の複雑性クラス内にあるという上限を確立することにより、標準的な複雑性の仮定（ $\text{TC}^0 \neq \text{NC}^1$ ）の下で、それらのクラスに対して困難であることが知られている問題（具体的には $\text{NC}^1$ 困難問題）をMHNが解けないことを証明します。
思考の連鎖（CoT）による拡張: 本研究は、MHNに思考の連鎖（Chain-of-Thought: CoT）メカニズムを付加した分析へと拡張し、反復的な推論ステップによって確立された複雑性の障壁を超越できるかどうかを調査します。

主な貢献と結果

1. 標準的なMHNに対する回路複雑性の理論的上限

本論文は、多項式精度、定数深さ、および線形隠れ次元を持つあらゆるモダン・ホップフィールド・ネットワーク（またはカーネル化されたホップフィールド・ネットワーク）が、 $\text{DLOGTIME-uniform } \text{TC}^0$ 複雑性クラス内に存在することを確立しています。

定理 4.8 & 5.4: 著者らは、構成要素（ホップフィールド・アテンション行列、層の計算、およびReLUフィードフォワード・ネットワーク）が、定数深さと多項式サイズを持つ一様閾値回路によってシミュレート可能であることを証明しています。
示唆: $\text{TC}^0 = \text{NC}^1$ でない限り、これらのアーキテクチャは根本的に $\text{NC}^1$ 困難問題を解くことができません。

2. 特定の問題に対する不可能性の結果

$\text{TC}^0$ の上限に基づき、著者らは標準的なMHNが特定の $\text{NC}^1$ 困難問題を解決できないことを示しています。

無向グラフの連結性: 無向グラフにおいて2つの頂点の間にパスが存在するかどうかを判定すること。
木同型判定: 2つの彩色された木が同型であるかどうかを判定すること。
定理 6.9–6.12: これらの結果は、 $\text{TC}^0 \neq \text{NC}^1$ という仮定の下で、標準的なモダン・ホップフィールド・ネットワークおよびカーネル化されたホップフィールド・ネットワークの両方に適用されます。

3. 思考の連鎖（CoT）による限界の超越

本論文は、これらの制限が絶対的なものではないことを示しています。MHNに思考の連鎖（CoT）メカニズムを装備させることで、ネットワークは $\text{TC}^0$ の障壁を超越できます。

定理 7.4: $n$ ステップのCoTメカニズムを備えたモダン・ホップフィールド・ネットワークは、置換群 $S_5$ の単語問題（ $\text{NC}^1$ 完全問題の一つ）を解くことができます。
対比: このタスクは、多項式埋め込みサイズや対数精度を用いたとしても、CoTのない標準的な定数深さのMHNでは証明上不可能です。これは、中間的な推論ステップが計算能力を高めるというTransformerの文献における知見とも一致しています。

重要性

本論文は、標準的なモダン・ホップフィールド・ネットワークと、推論ステップによって拡張されたものとの間の、能力に関する微細な理論的境界を明確に示しています。

理論的洞察: 標準的なMHNは、経験的な成功やLSTMやアテンションのような複雑な層の代替としての能力にもかかわらず、定数深さのTransformerや他の $\text{TC}^0$ 境界を持つモデルと同じ根本的な計算上の制限を共有していることを明らかにしています。これらは本質的に、直列的な $\text{NC}^1$ 困難タスクを解くことには制限があります。
アーキテクチャへの指針: 本結果は、MHNが本質的に直列的な問題（複雑なグラフの連結性や群論の単語問題など）に取り組むためには、反復的な推論（CoTのような）を可能にするアーキテクチャの変更が必要であることを示唆しています。
統一: 本研究は、MHNとカーネル化されたMHNを同一の複雑性制約の下で理解することを統合しており、主にTransformerに焦点を当ててきた従来の複雑性分析を、この特定のエネルギーベースモデルのクラスへと拡張しています。

要約すると、本論文はモダン・ホップフィールド・ネットワークの表現力を厳密に特性化しており、反復的な推論なしでは $\text{TC}^0$ に限定されるものの、思考の連鎖メカニズムを統合することで $\text{NC}^1$ 困難問題を解決可能であることを証明しています。