論文要約：Diagnosing CFG Interpretation in LLMs

この論文は、大規模言語モデル（LLM）が、推論時に提示された新規な文脈自由文法（CFG）を、構文、振る舞い、意味の 3 つの層において正しく解釈・適用できる能力を評価し、その限界を明らかにする研究です。

1. 背景と問題定義

LLM はエージェントシステム（ツール呼び出し、API 編成、ドメイン固有言語の生成など）に統合されつつありますが、これらのタスクでは、動的に定義された機械可読なインターフェース（JSON スキーマや関数シグネチャなど）に厳密に従う出力が求められます。

• 核心的な課題: LLM は、提示された新規な CFG に対して、単に表面的なパターンを記憶から引き出しているだけなのか、それとも形式的な論理を内部化して構造的に一般化できるのか？
• 現状の課題: 「ほぼ正しい」出力は実用的なエージェントには不十分であり、ネストされたループの論理誤りやデリミタの欠落は、実行時の致命的な失敗を招きます。既存の評価は表面的な流暢さに偏っており、構文、振る舞い、意味の 3 層を分離した厳密な診断が不足していました。

2. 提案手法：ROBOGRID

著者らは、文法解釈能力を評価するための診断フレームワーク**「ROBOGRID」**を提案しました。これは、決定論的なグリッドワールド環境を用いて、コードと振る舞いの明確なマッピングを実現します。

評価の 3 層（階層的評価）

文法解釈の失敗を特定するために、以下の 3 つの指標を用います：

1. 構文妥当性 (Syntax Validity Rate, SVR): 出力が CFG の生成規則に準拠しているか。
2. 振る舞い等価性 (Behavioral Equivalence Rate, BER): 生成されたプログラムが実行された際、目標状態（ロボットの位置や所持品など）に到達するか。
3. 意味正しさ (Semantic Correctness Rate, SCR): 生成された抽象構文木（AST）が、真の論理構造（Ground-truth）と構造的に同一か。

制御可能なデータ生成

LLM の推論能力を「表面的な記憶」から切り離すため、以下のパラメータを制御してデータを生成します：

• 構造的複雑性: 再帰の最大深さ（Recursion Depth）、制御フローの分岐密度（Else-Branch Probability）、式複雑性（Expression Depth）。
• 表面実装: 構文スタイル（ブロック形式、C 風、S-expr）、語彙の親しみやすさ。
  • Alien Lexicons（異星語彙）: 既存の知識（例：loop, if）に依存できないよう、すべてのキーワードを不透明なトークン（例：v_xkqm）に置換します。これにより、LLM が提示された EBNF 文法のみから純粋に記号的推論を行うかをテストします。

評価タスク

1. 文法性判定: 与えられた文字列が文法的に正しいか判定。
2. 目標条件付き生成: 目標状態に到達するプログラムを生成。
3. 指示からコードへの生成: 自然言語指示を、指定された文法に従ってコードに変換（最も困難なタスク）。

3. 主要な結果と知見

複数の SOTA モデル（GPT-5 シリーズ、Qwen3、DeepSeek-V3.2 など）を用いた実験から、以下の重要な発見が得られました。

階層的な劣化（Hierarchical Degradation）

すべてのモデルで、SVR > BER > SCR という一貫した階層的な劣化が観測されました。

• モデルは構文は正しく生成できることが多いですが、深い再帰や複雑な構造になると、振る舞いや意味の整合性が急激に失われます。
• 特に、構文が正しくても論理的な実行経路が誤っているケースが多く見られました。

構造的密度への脆弱性

• 再帰深度: 再帰深度が増加するにつれ、性能は非線形的に急激に低下します。深度 20 付近では、意味の整合性（SCR）はほぼ 0% まで崩壊します。
• 分岐密度: else ブランチの確率が高い場合、モデルは複数の実行パスを追跡できず、スコープ管理に失敗します。

語彙的親しみやすさへの依存（Semantic Bootstrapping）

• Alien Lexicons の影響: 親しみのあるキーワード（Natural）を使用する場合に比べ、不透明なトークン（Alien）を使用すると性能が大幅に低下します。
• これは、LLM が提示された文法規則そのものを推論しているのではなく、事前学習で得た「loop なら繰り返し」といった意味的なヒューリスティック（意味的ブートストラッピング）に依存して動作していることを示唆しています。

プロンプト戦略の影響

• CoT（Chain of Thought）の必要性: CoT を使用しない場合、特に深い再帰構造において性能は極めて低くなります。CoT は階層的な状態追跡を維持するために機能的に不可欠です。
• Few-shot の限界: 少量の例示（Few-shot）は、深い再帰構造においては性能向上に寄与せず、場合によってはノイズとして機能し、0-shot 以下になることもあります。

4. 失敗モードの分類

分析により、LLM の失敗は以下の 3 つの層に分類されました：

1. 構文的脆弱性: 生成規則の違反、デリミタの不一致、スコープ違反。
2. 振る舞いの不一致: 構文は正しいが、論理述語の逆転や数値計算ミスにより目標に到達できない。
3. 意味的漂流（Semantic Drift）: 実行結果は正しいが、AST 構造が真の論理と異なる（例：式の事前評価による構文の平坦化、深いネストでの論理ブロックの重複）。

5. 結論と意義

• 結論: 現在の SOTA LLM は、表面的な構文規則には従うことができますが、構造的密度（深い再帰や高頻度な分岐）が増すと、論理的忠実性を維持する能力が崩壊します。これは、純粋な記号的帰納ではなく、意味的な事前知識への過度な依存によるものです。
• 意義:
  • 信頼性の高い文法非依存（grammar-agnostic）なエージェントを構築するには、単なるプロンプトエンジニアリングや表面レベルの調整を超え、堅牢な記号的帰納と高密度な階層構造における状態追跡能力の向上が必要です。
  • 本研究で提案された ROBOGRID と 3 層評価フレームワークは、LLM の構造的推論能力を診断し、限界を特定するための標準的なベンチマークとして機能します。

この研究は、LLM を単なるテキスト生成器ではなく、形式的な仕様を厳密に解釈する「コンテキスト内インタプリタ」として扱う際の、現在の技術的ギャップを浮き彫りにする重要な貢献です。