技術的サマリー：リトライが失敗する理由 LLM エージェントパイプラインにおけるコンテキスト汚染

1. 問題定義

大規模言語モデル（LLM）のエージェントが、多段階かつツール拡張タスクで失敗した場合、標準的な慣行はタスクをリトライすることです。しかし、失敗した試行はモデルのコンテキストウィンドウ内に履歴として残存します。この「コンテキスト汚染」により、エージェントは誤った推論や誤ったツールの出力を次回の試行に持ち運び、結果として後続の試行におけるエラー率を実質的に増大させます。

この現象は実務において広く観察されています（例：エージェントが過去のミスから学習した不良エンドポイントを繰り返し参照するケース）が、この汚染がタスクの深さ、エラー率、または計算リソースの制約とどのようにスケーリングするかを定量化する形式的な理論的枠組みは存在しません。既存の文献は単一実行の信頼性や経験的な失敗の目録に焦点を当てていますが、現実世界の再試行行動を定義する「試行間ダイナミクス」をモデル化できていません。その結果、単純なリトライ戦略はしばしば膨大な計算リソースを浪費し、標準的な独立同分布（IID）仮定は、複数回試行のシナリオにおいて成功確率を著しく過大評価します。

2. 手法：コンテキスト汚染リスタートモデル（CCRM）

著者らは、このダイナミクスを形式化するために**コンテキスト汚染リスタートモデル（CCRM）**を導入しました。このモデルは、深さ $T$（$T$ 回のツール呼び出しのシーケンス）を持つパイプラインを定義し、エージェントは総予算 $B = KT$の範囲内で最大$K$ 回までの試行を行います。

中核メカニズム:

• 汚染状態 ($Z_k$): $k$ 番目の試行のコンテキスト条件を表す二値状態 $Z_k \in \{0, 1\}$。初期状態は $Z_1 = 0$（クリーン）。
• エラー率:
  • $\epsilon_0$: コンテキストがクリーンな場合 ($Z_k=0$) の基本ステップごとのエラー率。
  • $\epsilon_1$: コンテキストが汚染されている場合 ($Z_k=1$) の増大したステップごとのエラー率。ここで $\epsilon_1 > \epsilon_0$。
• 遷移ダイナミクス: 試行 $k$ が失敗した場合 ($S_k=0$)、状態は $Z_{k+1}=1$ に反転し、以降のすべての試行を汚染します。試行が成功した場合、プロセスは終了します。
• 成功確率: 単一の試行が成功する確率は $p_i = (1-\epsilon_i)^T$ です。したがって、$p_1 < p_0$ となります。

このモデルは、試行の系列をマルコフ連鎖として扱います。ここで、現在のタスクの目的において「汚染」状態への遷移は、成功が発生する（プロセス終了）か予算が尽きるまで、吸収状態として機能します。

3. 主要な貢献と理論的結果

本論文は、CCRM 枠組みの下で 5 つの主要な理論的結果を導出しました。

R1: 正確な成功の公式（定理 1）

著者らは、$K$ 回以内で成功する確率に対する閉形式の公式を導出しました。
$$P(\text{成功 in } \le K) = p_0 + (1-p_0)[1 - (1-p_1)^{K-1}]$$
この公式は、最初の試行が確率 $p_0$ を持ち、それ以降のすべての試行（失敗が前提の場合）は劣化した確率 $p_1$ を持つことを考慮しています。この構造は、信頼性工学で見られる修正幾何分布と同型ですが、ここでは試行間の汚染に適用されています。

R2: カスケードオーバーヘッドと相転移（定理 2）

本論文は、「カスケードオーバーヘッド」($\Delta K$) を定量化しました。これは、目標とする成功確率 $1-\delta$ を達成するために、クリーンなリスタート（IID）基準と比較して CCRM が必要とする追加の試行回数です。

• 普遍的な下限: 汚染は常に正のオーバーヘッド ($\Delta K > 0$) を生じさせます。
• 相転移: 汚染比率 $\epsilon_1/\epsilon_0$ が増加する（またはパイプラインの深さ $T$ が増加する）につれて、システムは相転移を起こします。「超臨界」領域では、必要な試行回数 $\Delta K$ は無限大に発散しますが、IID 基準は有界のままです。これは、汚染比率が高い深いパイプラインが、単純なリトライでは実用的に解けなくなる理由を説明します。

R3: 最適予算配分（定理 3）

総予算 $B$ が固定されている場合、成功確率を最大化する最適パイプラインの深さ $T^*$ を特定します。その閉形式解は以下の通りです。
$$T^* = \sqrt{B \cdot \frac{\log(1/(1-\epsilon_1))}{\log(1/(1-\epsilon_0))}}$$
この結果は、より強力な汚染（より大きな $\epsilon_1/\epsilon_0$）が、比例して小さい最適深さ $T^*$ を要求することを示しています。これは、汚染状態に入るリスクを最小化するために、より短く浅いパイプラインを推奨するものです。

R4: 情報理論的下限（定理 4）

Le Cam の手法と二仮説構成（IID モデルと CCRM を区別するもの）を用いて、著者らは、$K_{CCRM} - O(1)$ 回未満の試行回数では、いかなる方策も $1-\delta$ の成功確率を達成できないことを証明しました。これにより、導出された公式が定数倍の精度までタイトであることが確立されました。

R5: クリーンリスタートの優位性（定理 5）

本論文は、リトライ前にコンテキストウィンドウをクリアする（$Z_k=0$ にリセットする）ことが、標準的な「汚染された」リトライ戦略を厳密に凌駕することを証明しました。改善比率は明示的に導出され、コンテキストのクリアが要する試行回数を大幅に減少させることが示されています。

4. 実証的検証

著者らは、合成モンテカルロ実験とSWE-bench Verifiedからの実世界データの両方を用いて、CCRM モデルを検証しました。

• 合成検証: 30,000 回の試行による実験は、理論的な成功公式がシミュレーションデータと誤差 $\le 0.003$ で一致することを確認しました。カスケードオーバーヘッドにおける相転移は、予測通り観察されました。
• 実世界データ（SWE-bench）:
  • 同一の問題に対してエージェントが連続して試行を行う Verdent（SWE-bench Verified）のデータを用いて、著者らは CCRM モデルを適合させました。
  • 結果: 標準的な IID モデルは、pass@3 率を17.4 パーセントポイント過大評価しました（98.6% と予測に対し、実際は 81.2%）。
  • 適合: CCRM モデルは、誤差 0.001 未満でデータに適合しました。
  • 推論: 適合させたパラメータは、カスケード比率 $\epsilon_1/\epsilon_0 = 7.1$ を示唆しており、失敗した試行がステップごとのエラー率を 7.1 倍に増加させることを意味します。
  • 比較: 対照的に、独立した新規開始リトライを使用するベンチマーク（例：USEagent、OpenHands）は、IID 予測と実際の性能の間に大きな乖離を示しますが、著者らはこれをコンテキスト汚染ではなく、相関したタスクの難易度に起因すると帰属させています。これは CCRM の範囲外である別の現象です。

5. 意義と主張

本論文は、LLM パイプラインにおける試行間のコンテキスト汚染を分析する最初の形式的枠組みを提供すると主張しています。その意義は以下の点にあります。

1. 誤解の是正: ツール拡張エージェントにおける連続リトライにおいて、IID 仮定が根本的に欠陥があり、信頼性の過大評価につながることを実証。
2. 実行可能な原則: 最適予算配分 ($T^*$) に対する閉形式解を提供し、履歴を保持するよりもコンテキストをクリアする方が厳密に優位であることを証明。
3. 理論的厳密性: 情報理論的下限を確立し、リトライ戦略が無効になる相転移を特定。
4. 実践的ガイダンス: 汚染比率が高い場合、基本エラー率 $\epsilon_0$ を低下させること（微調整やより良い推論を通じて）は、増大したエラー率 $\epsilon_1$ も同時に低下させるため、超線形的な利益をもたらすことを示唆。

著者らは、汚染状態の二値性、試行内でのステップごとの独立性の仮定、および独立リトライに影響を与える相関したタスク難易度の除外など、限界を認めつつ、範囲を控えめに維持しています。彼らは CCRM を基礎的なステップとして位置づけ、試行間の汚染と試行内のマルコフダイナミクスを組み合わせることは未解決の問題であると指摘しています。