Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents

以下は、論文「Measuring the Unmeasurable: Markov Chain Reliability for LLM Agents」の詳細な技術的サマリーです。

1. 問題定義

大規模言語モデル（LLM）エージェントは、計画立案、ツール呼び出し、結果の観測、およびリトライを行う逐次的なソフトウェアシステムとして、ますます広く展開されるようになっています。しかし、その信頼性は現在、スカラーベンチマーク指標（例：pass@k、passk、および信頼性減衰曲線 RDC）を用いて評価されています。これらの指標には、以下の 3 つの決定的な限界があります。

1. 分布洞察の欠如: 結果を単一の数値に要約するだけで、背後にある成功までの時間分布を特定していません。
2. 適合度の検証不足: 観測された実行トレースが、仮定された分布を実際に支持しているかどうかを検証していません。
3. 不確実性の無視: 有限のトレース長に起因する不確実性を定量化できておらず、「フォールバックツールを追加したらどうなるか」や「ステップ予算を増やしたら信頼性がどう変化するか」といった反事実的な問いに答えることが困難です。

著者らは、LLM エージェントの信頼性は、単なる最終的な通過率ではなく、明示的な不確実性とモデル検証を伴う初回到達問題（失敗する前にいつ成功に到達するか）として扱うべきであると主張しています。

2. 手法：TRACETOCHAIN

本論文では、生のエージェント実行トレースを監査可能な吸収離散時間マルコフ連鎖（DTMC）に変換する再現性のあるパイプラインTRACETOCHAINを提案します。この手法は、以下の 4 つの主要な段階で構成されます。

A. 状態構築（特徴量化とクラスタリング）

• 入力: 推論ステップ、ツール呼び出し、観測結果からなる生トレース。
• プロセス:
  1. 特徴量化: 規則ベースの特徴量（ツールタイプ、エラーコードなど）または学習済みエンコーダを用いて、ステップをベクトル表現にマッピングします。
  2. クラスタリング: 階層的クラスタリング（Ward 法）により、これらのベクトルを離散的な遷移状態（$S_T$）にクラスタリングします。クラスタ数はシルエットスコアによって選択されます。
  3. 結果マッピング: トレースは、成功（$\oplus$）または致命的な失敗（$\ominus$）で終了し、これらが吸収状態として機能します。

B. 遷移推定

• モデル: システムは DTMC $\hat{M} = (\hat{Q}, \hat{R}^\oplus, \hat{R}^\ominus)$ を適合させます。ここで、$\hat{Q}$ は遷移状態間の遷移を表し、$\hat{R}^\oplus, \hat{R}^\ominus$ は成功または失敗へ脱出する確率を表します。
• 推定: パラメータは、未観測だが妥当な遷移に対するゼロ確率を防ぐために、**ラプラス平滑化付き最尤推定（MLE）**を用いて推定されます。

C. 適合度（GoF）プロトコル

マルコフ抽象化が有効であることを保証するため、パイプラインは複合的な診断テストを採用します。

1. コルモゴロフ・スミルノフ（KS）検定: 初回到達時間（成功までの時間）の実験的累積分布関数（CDF）を、適合済み連鎖から導出された解析的 CDF と比較します。
2. 赤池情報量基準（AIC）: 記憶要件が満たされていることを確認するため、1 次マルコフモデルを 2 次モデルと比較します。

• 判断: 連鎖は、$p_{KS} > 0.05$ かつ $\Delta AIC > 0$ の場合にのみ受け入れられます。拒否された場合、トレースコーパスをセグメント化するか、再特徴量化を行う必要があります。

D. 不確実性の定量化

パイプラインは、以下の手法を用いてすべての信頼性指標に対する信頼区間を提供します。

• ディリクレ事後区間: パラメータの不確実性を定量化するために、ラプラス平滑化付き MLE から導出されます。
• ノンパラメトリックブートストラップ: 適合済み連鎖の変動性を推定するために、トレースをリサンプリングします。

3. 主要な貢献と理論的枠組み

A. 指標の統合

本論文は、pass@k、passk、および信頼性減衰曲線（RDC）が競合する指標ではなく、単一の成功初回到達分布の射影であることを証明しています。

• RDC（$R(d)$）: $d$ ステップ以内に成功する確率。
• $pass_k$: $k$ 回の独立した試行がすべて成功する確率（$R_\infty^k$）。
• **$pass@k$:**$k$回の試行のうち少なくとも 1 回が成功する確率（$1 - (1-R_\infty)^k$）。
• 定理: これらの関係は i.i.d.（独立同一分布）の仮定の下で成立します。逸脱は、試行間の隠れた相関を示唆します。

B. 展開のための解析的ツール

基本行列 $N = (I - \hat{Q})^{-1}$ を用いて、著者らは以下の閉形式解を導出します。

1. ホライズン信頼性: ベンチマークを再実行することなく、任意のステップ予算に対する $R(d)$ を計算します。
2. 摂動感度: 局所的な変更（例：フォールバックツールの追加）がグローバルな信頼性に与える影響を、1 次感度分析を用いて推定します。
3. NHPP 極限: 稀な失敗の領域において、適合済みエージェント連鎖が古典的な Goel–Okumoto 非斉次ポアソン過程（NHPP）モデルに収束することを示し、現代のエージェント信頼性と古典的なソフトウェア信頼性理論を架橋します。

4. 結果と検証

著者らは、シミュレーション研究と実証的ケーススタディを通じて TRACETOCHAIN を検証しました。

• シミュレーション研究 SS1（数値的）: さまざまな連鎖サイズにおいて、閉形式の信頼性計算がモンテカルロシミュレーションと一致することを検証しました。
• シミュレーション研究 SS7（GoF 診断）:
  • 真の 1 次マルコフ連鎖から生成されたトレースの 100% を正しく受け入れました。
  • AIC レイヤーが依存性を検出した 2 次連鎖から生成されたトレースの 100% を正しく拒否しました。
• シミュレーション研究 SS9（保持データ検証）:
  • 7 つの制御された MAST 様式フレームワークでテストし、厳密な 50/50 の適合/テスト分割を行いました。
  • 結果: 適合済み連鎖は、保持された信頼性減衰曲線を正確に予測しました。
    • 最大 $L_{RDC}^\infty$ 誤差:0.053（中央値：0.048）。
    • KS 検定 p 値: すべてのフレームワークが合格（$p > 0.05$）、最小 $p = 0.78$。
  • これは、パイプラインが訓練データに過剰適合することなく、背後にある成功までの時間分布を回復することを示しています。
• 実証的ケーススタディ（SS6）: 7 つの実世界のエージェントフレームワーク（ReAct、Reflexion、ToolFormer など）に適用されました。パイプラインは、漸近信頼性（$R_\infty$）によってフレームワークを正しくランク付けし、それらの特定の RDC 形状を可視化しました。

5. 意義と影響

• スカラーから構造的へ: LLM エージェントの評価を、静的なスカラースコアから、結果だけでなく実行のプロセスも捉える動的で監査可能な信頼性モデルへと移行させます。
• 監査可能な信頼性: 信頼性の主張に対して「証明書」（GoF テスト＋不確実性区間）を提供し、エージェント評価の「ブラックボックス」性質に対処します。
• 反事実的推論: 適合済み連鎖に対する摂動分析を用いて、「リトライメカニズムを追加すると信頼性にどのような影響があるか」などの「もし〜なら」という問いに答えることを可能にし、完全なベンチマークを再実行するコストを回避します。
• 指標の調和: 異なるベンチマーク指標が、同じ背後分布の数学的にリンクした射影であることを示すことで、指標間の混乱を解消します。
• 実用性: このパイプラインは、制御されたトレースデータ（MAST など）での使用に即座に対応可能であり、安定したステップレベルの特徴量が利用可能になれば、SWE-bench や $\tau$-bench などの複雑なベンチマークへの適用も計画されています。

要約すると、TRACETOCHAINは、生 LLM エージェントのトレースを、信頼性が高く、診断可能で、予測的なシステム依存性のモデルへと変換するための、厳密で数学的基盤に裏打ちされた枠組みを提供します。