技術要約：エージェント・トレースからのオートマトン

問題提起

LLMベースのエージェントは、推論とツール呼び出しを交互に行いながら複雑で多段階のタスクを実行するが、生成される実行トレースは長く非構造的であることが多い。この不透明さは、安全性監査、デバッグ、および実行時のモニタリングを阻害する。既存のアプローチによる行動分析は、通常、個別のトレース単位で動作し、成功したケースのみにフィルタリングをかけたり、ワークフローの手動指定を必要としたりする。その結果、次ステップの予測と失敗予測を結びつける、共有されたクロスラン（cross-run）のトポロジーを捉えることができない。さらに、正例のみから有限オートマトンを学習することは理論的に限界がある（Gold, 1967; Angluin, 1980）であり、既存のオートマトン学習アルゴリズム（例：RPNI, EDSM）は、負例が利用できない場合に、巨大で過学習した状態空間を生成してしまうことが多い。

核心となる課題は、手動の介入なしに、予測モデリングと実行時の安全性モニタリングを可能にするため、一連の実行トレースからエージェントの挙動のコンパクトで構造的な表現を、正例のみを用いていかに復元するかである。

手法

著者らは、エージェントのトレースから決定論的かつハイパーパラメータフリーな有限状態機械（FSM）を構築する手法を提案している。この手法は、LLMエージェントが限定されたツールの集合およびアクション内で動作し、その結果、小さなアクティビティ・アルファベット（6〜42個の記号）と強い逐次的な規則性を持つという観察に基づいている。

1. アクティビティ抽出

トレースは、決定論的な抽出関数 $\phi$ を用いて、有限のアルファベット $\mathcal{A}$ からの記号のシーケンスへと変換される。この関数は以下を優先する：

1. ツール呼び出し： 関数名を抽出する。
2. アクションタグ： アクションラベル（例：[ACTION]）を抽出する。
3. コマンド抽出： コードブロックから最初のコマンドトークンを抽出する。
   一致するルールがない場合、アクティビティはロール・コンテンツ型（例：assistant:text）にデフォルト設定される。

2. FSM構築

構築は以下の3つのステップで行われる（アルゴリズム A.1）：

• 接頭辞木（Prefix Tree）： すべてのアクティビティシーケンスがトライ（trie）に挿入される。各一意の接頭辞は個別の状態を表す。これにより完璧なトレーニング適合度が得られるが、状態数は $O(\sum T_i)$ となる。
• 最終アクティビティによるマージ（Last-Activity Merge）： 「最後のアクティビティによる右合同性（last-activity right congruence）」に基づいて状態をマージする。エッジが進入するアクティビティが同一である場合（$\kappa(q) = \kappa(q')$）、状態 $q$ と $q'$ はマージされる。これにより、状態空間は $|\mathcal{A}| + 1$ 個の状態（各アクティビティにつき1つと初期状態）に削減され、決定論的な直接フォロー（directly-follows）オートマトンが作成される。
• 希少遷移のフィルタリング（Rare-Transition Filtering）： 観測回数がちょうど1回である遷移は、それがソース状態からの唯一の継続でない限り削除される。これにより、一回限りの逸脱をフィルタリングしつつ、コアとなる行動トポロジーを保持する。

3. 理論的保証

• 適合性の保持： 定理2は、マージ操作がトレーニング適合性を保持することを証明している。すなわち、接頭辞木によって受理されるあらゆるトレースは、マージされたFSMによっても受理される。
• 決定論性とコンパクト性： 定理3は、得られるFSMが決定論的であり、状態数が $|\mathcal{A}| + 1$ であることを確立している。この構築はコーパスの決定論的関数であり、再現性を保証する。
• 収束性： 命題5は収束の保証を提供する。$N$ 個のトレースがある場合、遷移が最小限の頻度で出現するという条件の下で、抽出されたFSMは高い確率で集団の直接フォロー・オートマトンと一致する。

4. 予測とモニタリング

• 次ステップ予測： 確率 $P(a_t | q_t)$ は、FSMの状態内での遷移カウントから推定され、ラプラス・スムージングまたは絶対割引（absolute discounting）によって平滑化される。
• 失敗予測： システムは、状態ごとの特徴量（訪問頻度、メッセージ長、エラー率）およびトレースレベルのアノマリー特徴量（クロスエントロピー、サプライズ）を抽出する。勾配ブースティング分類器がこれらの特徴量を用いて、成功または失敗を予測する。
• 実行時モニター： オンラインモニターは、トレースをFSMに再生し、「サイクル率（cycle rate）」（状態を再訪する頻度）などの指標を計算する。これは、学習済みのMLモデルによるモニタリングロジックを必要とせずに、トレースが成功パターンから構造的に逸脱した場合（例：タイトなループに入った場合）に早期停止をトリガーする。

主な結果

本手法は、8つのエージェントドメイン（コーディング、ウェブナビゲーション、GUI、カスタマーサービス、セーフティ）にわたる12の公開データセットを用いて評価された。アルファベットのサイズは6から42の記号であった。

• コンパクト性と適合性： 抽出されたFSMは非常にコンパクトであり、わずか7〜43の状態しか持たない。これらはすべてのデータセットにおいて、テストリプレイ適合度 $\ge 0.997$ を達成した。RPNIのベースラインと比較して、本手法は15倍から3,036倍の圧縮率を実現した（例：SWE-agentにおいて、59,510個のRPNI状態を25個のFSM状態に削減）。
• 次ステップ予測： FSM状態のコンテキストは、AWM（Agent Workflow Memory）が評価されたすべての8つのデータセットにおいて、AWMを上回る性能を示した。トップ1精度の向上幅は+0.8ppから+25.3ppであった。FSM状態による条件付けは、生のコンテキストのみの場合と比較して、クロスエントロピーを0.155ビット（21%）減少させた。
• 失敗予測： 状態ごとの行動特徴量は、ホールドアウトAUROCで最大0.94（tau2-bench telecom）に達した。本手法は、21のデータセット・アーキテクチャのペアにおいて、MLP、GRU、Transformerのベースラインを凌駕した。
• 実行効率： FSM構築は1〜110 msで完了する（RPNIの7,000〜36,000 msと比較）。トレースごとのリプレイには0.003〜0.015 msを要し、リアルタイムモニタリングが可能である。
• 早期停止： オンラインモニターは、25%のトレースチェックポイントにおいて失敗する実行を成功する実行よりも上位にランク付けすることができ（rank-AUROC 0.66）、SWE-agentにおいて32%の完了時点で早期停止をトリガーし、残りの計算資源の68%を節約した。
• 汎用性： 4つの異なるLLMのトレースから構築された単一のFSMは、それぞれのモデルに対して1.000の適合度を達成した。これは、行動トポロジーが特定のLLMよりも、デプロイメント・ハーネスやツールの制約によって形作られていることを示している。

意義と主張

本論文は、LLMエージェントは一見複雑に見えるものの、コンパクトな構造的抽象化が可能であることを主張している。主な意義は、ワークフローメモリ、次ステップ予測、失敗予測、および実行時モニタリングという4つの異なるタスクを、単一のハイパーパラメータフリーな構築へと統合する、モデルに依存しない構造的プリミティブを提供したことにある。

主な主張は以下の通りである：

1. 構造的優位性： 行動トポロジーは、特定のLLMよりもシステム（ツール、プロンプト、タスク分布）によって形作られるため、モデル不変のモニタリングが可能である。
2. 計算可能性： エージェントの限定されたアクティビティ・アルファベットにより、正例からの学習問題は扱いやすくなり、統計的に情報量の多いコンパクトで解釈可能なFSMが得られる。
3. 効率性： 本手法は、4つの個別なパイプラインを、ミリ秒単位で動作する単一の構造的プリミティブに置き換える。これは、安全性監査や実行時モニタリングへのデプロイに適している。
4. 解釈可能性： HMMや大規模なオートマトン学習器とは異なり、このFSMの状態は最後のアクティビティに直接対応している。これにより、状態ごとの分解や、解釈可能な失敗モード分析（例：失敗は新しい状態の探索ではなく、特定のループに陥ることで発生することが多いといった分析）が可能になる。

著者らは、制限事項として、FSMは観測されたトレースの直接フォローの閉包を受理すること（生成言語そのものではないこと）、およびアクティビティ抽出関数に最小限のドメイン知識が必要であることを挙げている。しかし、構造的な制約は抽出の粒度に対して堅牢であり、本アプローチが安全性および行動分析のためのデプロイ可能な基盤を提供することを強調している。