Probing Structural Mathematical Reasoning in Language Models with Algebraic Trapdoors

技術的概要：代数的トラップドアを用いた言語モデルにおける構造的数学的推論の探査

問題定義
標準的な数学的推論ベンチマーク（例：GSM8K、MATH、ProofNet）は、通常、検証が解法よりも困難ではないという対称性を示す。この対称性は計算流暢性を有利に評価するが、「構造的推論」、すなわち命名された定理の展開、代数的パターンの認識、および適用可能な構造的優先順位の特定という能力を評価するには不十分である。さらに、標準的なスコアリングは「誤った答えへのコミット」と「誠実な棄権」を混同し、両方をゼロ点の失敗として扱う。

本論文は、群 $SL(3, \mathbb{Z})$ 内で暗号学的な検証者 - 証明者の非対称性を活用することで、この対称性を打破するように設計されたベンチマークスイートを紹介する。核心的な課題は、各問題の答えが「トラップドア」データ $(N, K)$ を保有する構築者によって $O(1)$ の閉形式で計算可能である一方、このデータを欠く解法者にとっては、ヒューリスティックな構造的検出か、あるいは決定可能性が未知のアルゴリズム的問い（具体的には $SL(3, \mathbb{Z})$ における所属問題）のいずれかに直面する点にある。

手法
このベンチマークは、秘密のペア $(N, K)$（ここで $K \subseteq SL(3, \mathbb{Z}/N)$）から有限生成部分群 $H \subseteq SL(3, \mathbb{Z})$ を生成することによって構築された 4 つのファミリーで構成される。生成元はニールセン・スクランブリング（生成元を深くネストされた積として書き換える）およびメンニッケ・シアーを用いて難読化され、その結果、行列成分は $10^{40}$ に達する。

1. ファミリー I（所属）: 生成元と候補行列が与えられたとき、所属を決定する。「YES」には明示的な単語、「NO」には mod-$p$ 還元による証明が存在するが、$SL(3, \mathbb{Z})$ における一般的な所属問題は決定不能である。
2. ファミリー II（リスト・プライム YES/NO）: 大きな素数のリストに対して、$(A, B)$ が生成する部分群が $SL(3, \mathbb{F}_p)$ へ全射するかどうかを判定する。答えは、構築者には $O(1)$ であるが解法者には構造的検出を必要とする直交構造（スミス標準形）の検出に依存する。
3. ファミリー III（合同拡張 YES/NO）: $H$ が合同拡張 $\pi^{-1}(K)$ かどうかを判定する。「悪い素数」とは、$K$ が真部分群である $N$ の因子である。
4. ファミリー IV（指数）: 正確な指数 $[SL(3, \mathbb{Z}) : H]$ または「無限/未知」を出力する。このファミリーには 3 つのサブファミリーが含まれる：
   • v1: $H = SL(3, \mathbb{Z})$（指数 1）。mod-$p$ 分析を通じて、一般的な無限指数部分群と区別できない。
   • v2: $H = \pi^{-1}(K)$（有限指数）。余核は計算可能だが、核の包含関係は所属問題を解くことを必要とする。
   • v3: $H = \langle g_1, g_2 \rangle \subset \Gamma(N)$（性質 (T) による無限指数）。余核のみの推論は誤った有限の答えをもたらす。正しい推論には無限性の認識が必要である。

評価設定
著者は、最先端の 2 つのモデル、GPT Pro (thinking) と Gemini を評価した。重要なのは、プロンプトにおいて部分群が有限指数であると断言していない点である。この設計は、モデルに余核の計算（容易）と核の包含関係の検証（困難/未知）を区別させ、「較正テスト」を強制する。

著者は4 段階のスコアリング分類を提案する：

1. コミット - 正解: 正しい具体的な答えを出力。
2. コミット - 不正解: 誤った具体的な答えを出力。
3. 棄権 - 正解: 真値が無限/未知である場合（v3）に「無限/未知」と出力。
4. 棄権 - 不正解: 真値が特定の整数である場合（v1, v2）に「無限/未知」と出力。

主要な結果
本論文は 5 つの詳細な推論トレースを報告する：

• 構造的推論（ファミリー II および III）: 両モデルとも、構造的検出を必要とする事例（例：マクローリンの定理、バーンサイドの定理、またはコクセター表示の識別）を成功裏に解決した。
  • Gemini は命名された定理のマッチングに依存し、数秒で短い宣言的な応答（例：$S_4$ に対するコクセター表示の認識）を生成した。
  • GPT は構成的導出に依存し、第一原理から交換子恒等式を導き出し、行列を因数分解するのに数分〜数時間を要した。
• 較正テスト（ファミリー IV-v2、インスタンス X10）:
  • GPT は、真値が 25 桁の整数であるインスタンスに152 分を費やした。これは余核の計算に成功したが、明示的に核側の所属問題をボトルネックとして認識した。構成的検証（必要なすべてのシアーを証明するには失敗した）を試みた後、計算された上限にコミットするのではなく、「DON'T KNOW」で棄権した。これは、開放決定可能性の境界における較正されたメタ認知を示している。
  • Gemini は推論トレースを生成できず、数分後に内部エラーを表面させた。
• SL(2, Z) ベースライン（ファミリー V）:
  • 決定可能な $SL(2, \mathbb{Z})$ ベースラインでテストされた際、GPT は有限指数と無限指数を区別するために、連分数、スタリングス・フォールディング、ラインデマイスター - シライアー、ニールセン還元を含む完全なランク 1 ツールキットを成功裏に展開した。
  • Gemini は同じベースラインで長時間の計算後にクラッシュし、出力を生成できなかった。

意義と主張
本論文は、このベンチマークが標準的な答えキーのスコアリングでは隠蔽されてしまうモデル行動の 4 段階分類を露呈させると主張する。その主な貢献は以下の通りである：

1. 較正された棄権の証拠: 152 分間の GPT のトレースは、最先端モデルが証明が不完全であることを認識し、部分的な計算（余核）が利用可能であってもコミットを拒否できる能動的な「メタ認知層」を有しているという、現在存在する最も強力な証拠を提供する。
2. アーキテクチャ的非対称性: 結果は、推論アーキテクチャの根本的な違いを示唆する。著者は、GPT に対して3 層モデル（命名された定理 $\to$ 第一原理 $\to$ 較正された棄権）を、Gemini に対して単一層モデル（命名された定理のみ）を提案する。後者では、フォールバック機構の欠如が、主要なヒューリスティックが失敗した際に無限ループやクラッシュを引き起こす。
3. プロンプト設計の診断的価値: 本論文は、プロンプトから「有限指数」という約束を省略することが重要な設計選択であることを実証する。それがなければ、核/余核の非対称性はモデルに決定可能性の境界と対峙させ、「棄権」を失敗ではなく、測定可能かつ意味のある行動とする。
4. 計算流暢性を超えて: このベンチマークは、大整数演算を実行できるモデルと、構造的優先順位（アシュバッハークラス、性質 (T)、合同部分群性質）を展開し、アルゴリズム的限界を認識できるモデルを区別する。

著者は、このベンチマークが「命名された定理を知っていること」と「優雅なフォールバック機構を持っていること」を成功裏に分離し、現在のモデルが構造的推論を実行できる一方で、ニールセン・グラフ探索のようなアルゴリズム的戦略をより高いランクへ一般化する能力は、依然として調査を要する固有の領域であることを明らかにしたと結論づける。