技術要約：ニューロ・シンボリック構文解析：CYKアルゴリズムによるニューラルネットワークの形成

問題提起

本論文は、現在の大規模言語モデル（LLM）およびトランスフォーマー型アーキテクチャにおける根本的な限界に対処している。それは、複雑なアルゴリズム的知識を訓練データから確実に学習し、外挿（extrapolate）することができないという点である。トランスフォーマーは単純なタスクにおいて「グロッキング（grokking）」（過学習を超えた汎化）を示すことがあるが、コック・ヤンガー・カザミ（CYK）のような複雑な解析アルゴリズムをゼロから学習するといった、高度なアルゴリズム的汎化には苦戦する。著者らは、トランスフォーマーに既知のアルゴリズムをデータのみから発見することを期待するのは過大な期待であり、これらのモデルは単なる「大規模な言語メモリ」として機能することが多いと主張している。核心となる問題は、行列とベクトルの積によって制御されるニューラルネットワークのアーキテクチャ内に、既知のアルゴリズムを直接エンコードできるか否かである。これは、膨大なスケールと訓練を通じて能力が受動的に創発することを待つのではなく、直接的な手法を用いるものである。

手法

著者らは、CYKアルゴリズムをニューラルネットワークのフレームワークに直接注入するために設計された、シンプルな再帰型ニューラルネットワークアーキテクチャであるCYKNNを提案している。この手法は、以下の3つの主要なコンポーネントに基づいている。

1. ホログラフィック還元表現（HRRs）: 2次元のCYK解析テーブルと記号的な文法規則をエンコードするために、著者らはHRRを利用している。このフレームワークでは、記号はランダムなベクトルから派生した行列として表現される。これらの表現の特定の特性として、ある記号とその逆（例：$[a]^\oplus$ と $[a]^\ominus$）は、行列乗算において互いに打ち消し合い、単位行列に近似する。これにより、一連の記号をテトリスのピースのように代数的に操作できる「ホリスティック（全体論的）」な操作が可能になる。

2. 行列演算によるアルゴリズムの注入:

   • 表現: CYKテーブルのセル $P[i, j]$ は、分散型の行列として表現される。文法規則（例：$A \to BC$）は、非終端記号の逆表現と順方向表現から構築された重み行列（$W$）としてエンコードされる。
   • ホリスティックな更新: テーブルのセルを一つずつ埋めていくループ処理（古典的な $O(n^3)$ のCYKアルゴリズム）を行う代わりに、著者らは更新ステップを単一の行列・ベクトル乗算 $P' = PRP$として定式化している。ここで、$P$は現在のテーブルの状態であり、$R$ は文法規則をエンコードしている。この操作は、構成要素を結合するロジックを並列に実行することを理論的に実現している。
   • 精緻化: $O(n^3)$ の複雑性を単一の操作へと集約することによって導入される近似誤差を軽減するため、アーキテクチャには**対角デコーダ（Diagonal Decoder, Dd）**が含まれている。このモジュールは、分散行列から特定の対角成分の情報を抽出し、信号を浄化して、精緻化のために再帰ループへとフィードバックする。

3. アーキテクチャ（CYKNN）: ネットワークは以下で構成される：

   • ホログラフィックエンコーダ（He）: 入力トークンを初期行列 $P_0$ へと変換する。
   • 単項モジュール（U）: 最初の対角成分を初期化するために単項文法規則を適用する。
   • 二項モジュール（B）: 二項規則の適用を伝播させるための核となる操作 $P_{i+1} = P_i R_B P_i$ を実装する。
   • 対角デコーダ（Dd）: 分散行列から記号的な内容を抽出し、精緻化する。

主な貢献

• アルゴリズムの直接注入: 本論文は、既知の複雑なアルゴリズム（CYK）が、暗黙的に学習されるのではなく、ニューラルネットワークのアーキテクチャの中に明示的に形作られるという、新しいニューロ・シンボリック手法を提示している。
• 線形代数によるホリスティックな推論: 動的計画法（解析テーブルを埋めるプロセス）の反復的なロジックが、HRRの特性を活用することで、データの状態を単一の操作で変化させるホリスティックな行列・ベクトル乗算へと翻訳できることを示している。
• アルゴリズム的タスクにおける優れた性能: 提案されたCYKNNは、たとえそれらが20B以上のパラメータを持つ大規模なモデルであっても、あるいはLoRAで微調整されたとしても、特定のCYK解析タスクにおいて既存の最先端LLMを凌駕する性能を示した。

実験結果

著者らは、CYKNNを以下の2種類のトランスフォーマーベースのモデルと比較評価した：

1. 微調整済みモデル: CYKタスクに対してLoRAを用いて微調整された Qwen2.5-1.5B および Qwen3-8B。
2. インコンテキスト学習（ICL）モデル: 数発の例示（few-shot examples）を用いた gpt-oss-20B および Gemma-27B。

結果:

• CYKNNの優位性: 特に正しい文法規則で初期化された場合、CYKNNは、小規模なテストセット（長さ5-8）およびフルテストセットの両方において、比較対象となったすべてのLLMよりも有意に高いF値（F-measure）を達成した。
• LLMの限界: 微調整されたQwenモデルは性能が悪く、アルゴリズム構造を学習するのではなく、接頭辞の関連性を記憶してしまう傾向があった。これらは、非常に長いシーケンス（>12トークン）においてのみ、ランダムに初期化されたCYKNNを上回ったが、これはアルゴリズムを誘導できていないことを示唆している。インコンテキスト学習モデルは、適合率（precision）は高いものの再現率（recall）が低く、保守的で非アルゴリズム的なテーブル充填を行っていることが示された。
• 初期化への感度: CYKNNの性能は、文法行列の初期化に大きく依存していた。ランダムな初期化では性能が低下したが、特定の文法規則を用いて初期化することで、高い精度へと収束することが可能となった。
• 汎化: シーケンスの長さの変化に苦戦するトランスフォーマーとは異なり、CYKNNはシーケンス長に関してより直感的な挙動を示し、より複雑な文法においても性能を維持した。

意義と主張

本論文は、ニューロ・シンボリックな手法への異なるアプローチへの道を開くものであると主張している。著者らは、アルゴリズムが既知であるならば、巨大なトランスフォーマーの「創発的な能力」に頼るのではなく、これらのアルゴリズムをニューラルアーキテクチャに直接エンコードするという、実行可能な代替案が存在すると述べている。

その意義は、以下の実証にある：

1. アルゴリズムがアーキテクチャを形作る: ニューラルネットワークは、単に統計的なパターンを学習するだけでなく、行列・ベクトル演算を通じて特定のアルゴリズム的ロジック（CYK）を具現化するように設計できる。
2. ニューロ・シンボリック・タスクにおける効率性: 厳密なアルゴリズムへの準拠が求められるタスク（解析など）においては、特化したアルゴリズム的形状を持つネットワークが、数十億のパラメータを持つ汎用的な大規模LLMをも凌駕することができる。
3. 「グロッキング」への代替: 複雑なアルゴリズム的タスクにおいて、トランスフォーマーがデータから解法を「グロック」するのを待つことは非効率であり、しばしば失敗する。アルゴリズム的構造を明示的に注入することこそが、より堅牢な経路である。

著者らは、使用した文法が単純であり、現在の実装が計算量的に最適化されていないことを認めつつも、文法の単純さによってさえ、現在のトランスフォーマーベースのLLMの限界を露呈させるには十分であったと主張している。