技術要約：Transformerによる擬似乱数の学習

問題提起

本論文は、Transformerモデルが、広く用いられている擬似乱数生成器（PRNG）の一種である**置換コンジュゲート生成器（PCG: Permuted Congruential Generators）**によって生成されたシーケンスを学習し、予測する能力について調査している。Transformerは様々なアルゴリズム的タスクにおけるインコンテキスト学習（ICL）において成功を収めてきたが、統計的なランダム性テストをパスするように設計されたデータの中に隠された決定論的なパターンを解明する能力があるのかという根本的な疑問が残っている。

PCGは、線形合同生成器（LCG）よりも著しく困難な課題を提示する。LCGは単純な線形回帰（$s_i = (a s_{i-1} + c) \mod m$）に従うが、PCGは出力 $x_i$ を得る前に、隠れた状態 $s_i$ に対して複雑な関数 $f$ を適用する。この関数には、ビットシフト、XOR、回転、および切り詰めが含まれる。これらの操作は、基礎となる線形構造を隠蔽するように設計されており、法（modulus）や乗数（multiplier）の知識を前提とする古典的な代数的攻撃に対する耐性を持たせている。著者らは、Transformerが生成器のパラメータに関する明示的な知識なしに、これらの隠れた回帰関係や置換構造を発見できるかどうかを判断し、そのような学習のメカニズムと限界を理解することを目的としている。

手法

実験設定

本研究では、いくつかのPCGバリアント（XSLRR, XSHRR, XSHRS）および切断型LCG（TLCG）を用いた制御されたベンチマークを利用している。

• 生成器: 内部状態 $s_i$ はLCGを通じて進化し、出力 $x_i = f(s_i)$ は特定の置換を通じて導出される。著者らは、法 $m$（$2^{14}$ から $2^{22}$ まで）および出力サイズ（例：16ビットの状態から8ビットの出力）を変化させている。
• データセット: 以下の2つの設定を採用している：
  1. 個別（Separate）: 単一の生成器タイプに対して学習およびテストを行う。
  2. 混合（Combined）: すべての生成器タイプが混在した状態で学習およびテストを行い、異なる置換ルールをモデルに識別させる必要がある。
  • データセットは、未知の乗数（$a$）および増分（$c$）を用いて生成されたシーケンスで構成されており、汎化性能をテストしている。
• モデルアーキテクチャ: Rotary Positional Embeddings（RoPE）を備えたGPTスタイルのデコーダーのみのTransformerを使用。実験では、モデルの深さ（1–6レイヤー）、幅（アテンションヘッド）、および語彙サイズ（出力ビット幅に基づく）をスケールさせている。
• 学習: 次のトークンを予測するために、クロスエントロピー損失を用いて自己回帰的に学習を行う。学習は、バッチサイズ512で最大100kステップまで行われる。

主要技術

1. カリキュラム学習: 大きな法（$m \ge 2^{20}$）の場合、直接的な学習はしばしば失敗し、長期的な停滞を招く。著者らは、小さな法のデータを用いながら大きな法のデータセットに混合していくカリキュラム戦略を導入している。混合比率 $\alpha$ は、学習ステップに応じて指数関数的に減衰する。
2. 事前学習による初期化: 小さな法で学習されたモデルを、より大きな法のタスクの重みの初期化に使用し、学習された埋め込み構造を転移させる。
3. 解釈可能性分析: 著者らは、入力データをモデルがどのように表現しているかを理解するために、トークン埋め込みに対する主成分分析（PCA）およびアテンションパターンの分析を行っている。

主要な貢献と結果

1. 成功したインコンテキスト予測

Transformerは、複数のPCGバリアントにおけるインコンテキスト予測を正常に実行でき、未知のパラメータ（$a, c$）に対しても汎化することができる。

• 性能: モデルは約512個のインコンテキスト要素を観察した後、多様なPCGバリアントに対して90%以上の精度を達成する。
• 堅牢性: 出力が大幅に切り詰められた場合（例：状態の最高ビットのみを保持する場合）でも、予測は堅牢であり、モデルはランダムな推測を大幅に上回る性能を示す。
• 汎化: この能力は、法と乗数の事前知識を必要とする公開されている古典的な攻撃を超えている。

2. スケーリング則

本論文は、成功的な予測に必要なコンテキスト長に関する特定のスケーリング則を特定している：

• コンテキスト長 vs. 法: 90%の精度を超えるために必要なインコンテキスト・シーケンス要素の数は、$\sqrt{m}$ に比例してスケールする。これはLCGで見られる $m^{0.25}$ のスケーリングよりも急峻であり、PCGの置換によって導入された情報の隠蔽を反映している。
• モデルサイズ: より大きなモデル（深さや幅の増加）は、同じ精度に達するために必要な観測要素の数が少なくなる。これは、スケールによってより効率的な戦略開発が可能になることを示唆している。

3. カリキュラム学習の必要性

大きな法（$m \ge 2^{20}$）において、固定された計算予算内での直接的な学習は、損失減少がほとんどない長期の停滞フェーズをもたらす。

• カリキュラムの有効性: 小さな法からのデータを取り入れること（例：$m=2^{18}$ の学習に $m=2^{16}$ のデータを混合する）により、停滞フェーズが解消され、安定した学習率の範囲が広がり、最終的なパフォーマンスが大幅に向上する。
• 事前学習: 小さな法のモデルから重みを初期化することは、離散的な形式のカリキュラムとして機能し、モデルが初期の停滞フェーズをスキップして収束を早めることを可能にする。

4. 解釈可能性と表現

学習された表現の分析は、新たな構造的洞察を明らかにしている：

• ビット単位のクラスタリング: 埋め込み行列のPCAは、トークンがビット単位の回転不変な構造、具体的には連続するゼロのラン（例：$Z(1), Z(2,1)$）の数と配置に基づいて自発的にクラスター化することを示している。
• 転移可能性: このクラスタリング構造は異なる法の間でも持続しており、これが事前学習による初期化が効果的である理由を説明している。すなわち、モデルは生成器に固有の不変性を内部化しているのである。
• 生成器の分離: 混合学習の設定において、モデルの中間活性化（具体的には第3層のMLP）は、生成器のアイデンティティに関する明示的な監督なしに、異なるPRNGバリアントを自発的に区別している。

重要性と主張

本論文は、Transformerが、生成器のパラメータに関する明示的な知識に依存する古典的な代数的攻撃を凌駕し、ランダムに見えるように設計されたデータの中から隠れた決定論的パターンを解明する驚異的な能力を持っていることを実証していると主張している。

本研究は、Transformerが複雑なPRNG構造を学習できる一方で、明確なスケーリングの制約に直面していることを強調している。コンテキスト長が $\sqrt{m}$ に従って成長する必要があること、および大きな法に対してカリキュラム学習が必要であることは、これらのモデルが未知の領域に対して汎化できる一方で、特定の学習戦略なしに任意に巨大または複雑な生成器を「解読」できる段階にはまだ至っていないことを示唆している。

埋め込み空間における回転不変なクラスタリングの特定は、これらのモデルがどのように汎化するかについてのメカニズム的な説明を提供している。すなわち、モデルは特定のシーケンスを記憶するのではなく、基礎となるアルゴリズムの対称性に基づいて入力を表現することを学習しているのである。これは、ニューラルネットワークがモジュロ演算や置換ベースのタスクをどのように処理するかについて、アルゴリズム的推論と統計的パターン認識の間の架け橋となる新しい視点を提供する。

著者らは、Transformerは非暗号学的なPRNGの予測には効果的に接近できるものの、完全なメカニズム的解明と、暗号学的に安全な生成器を攻撃する能力の探求が重要な今後の方向性であると結論付けている。