技術的サマリー：エージェントワークフローにおける制約駆動型オンラインリソース割り当て

問題定義

本論文は、エージェントシステムの展開における重要なギャップ、すなわち、平均的な性能・コスト・レイテンシのフロンティアの最適化から、厳格なインスタンス固有の制約の充足への移行という課題に取り組んでいる。近年の研究は、性能、コスト、レイテンシのトレードオフを最適化することでエージェントの効率を向上させているが、現実世界の展開では、特定のワークフローが厳格な予算（$B$）と固定されたデッドライン（$D$）内で完了することが求められることが多い。

核心的な問題は制約駆動型オンラインリソース割り当てである。依存関係が構造化されたワークフロー（ノードがサブタスク、エッジが依存関係を表す有向非巡回グラフ）が与えられたとき、実行主体は、現在実行可能なサブタスクに対してリソース（ベースモデルの選択と並列サンプリング幅）を動的に割り当てる必要がある。目的は、平均コストやレイテンシを最小化することではなく、総コストが $B$ 以下かつ総時間が $D$ 以下となるように、ワークフロー全体が成功して完了する確率を最大化することである。

これは、有限ホライズンの確率的オンライン割り当て問題として定式化される。状態は、完了したサブタスクの集合、残存予算、残存時間によって定義される。課題は、可能な実行経路の組み合わせ爆発、確率的な結果（サブタスクの成功/失敗）、およびワークフロー全体にわたるリソース消費の相互依存性にある。モデルやサンプリング戦略の静的な割り当ては不十分である。なぜなら、最適な決定は、変化する状態、残存制約、および観測された確率的イベントに依存するからである。

手法：モンテカルロポートフォリオプランニング（MCPP）

この扱いにくい最適化問題を解決するため、著者はモンテカルロポートフォリオプランニング（MCPP）、すなわち軽量なクローズドループプランナーを提案する。

1. 問題定式化

ワークフローは $I = (G, M, \Phi, B, D)$ としてモデル化される。ここで、$G$ はサブタスクグラフ、$M$ は利用可能なモデルの集合、$\Phi$ は各サブタスク - モデルペアに対する推定成功確率（$p_{v,m}$）と期待生成長さ（$\ell_{v,m}$）を含む。
目的は、以下の式を最大化する方策 $\pi$ を見出すことである：
$$J(\pi) = \Pr_{\pi} (T_{solve} \le D, C_{\pi} \le B)$$
厳密な動的計画法は理論的には可能であるが、状態空間（完了したサブタスクの組み合わせ）と行動空間（準備できたすべてのノードに対するモデルおよびサンプリング幅の選択）が指数的に膨大であるため、計算的に扱いにくい。

2. MCPP アルゴリズム

MCPP は、1 ステップのポートフォリオロールアウトバックアップを用いて最適な決定則を近似する。

• 候補行動セット: 各状態において、プランナーは候補行動の集合 $\tilde{A}(s)$ を構築する。この集合には、準備できたノードに対する特定の割り当てが含まれ、さらに単純な継続方策のポートフォリオ $\Pi_0$ によって拡張される。ポートフォリオ内の各方策は、「リトライ-$k$"戦略であり、すべての将来の実行可能サブタスクに特定のモデル $m$ とサンプリング幅 $k$ を割り当てるものである。
• モンテカルロ推定: 各候補の現在の行動 $a$ に対して、プランナーはワークフローの実行をシミュレートすることでその値を推定する。$a$ を適用し、確率的な結果（どのサブタスクが成功するか）をサンプリングし、状態を更新した後、ワークフローが完了するか制約に違反するまで、各継続方策 $\mu \in \Pi_0$ に従う。
• 選択: 行動 $a$ の値は、ポートフォリオ内のすべての継続方策における最大成功確率として推定される：$\hat{Q}_{\Pi_0}(s, a) = \max_{\mu \in \Pi_0} \hat{Q}_{\mu}(s, a)$。推定値が最も高い行動が実行のために選択される。
• クローズドループ再計画: 選択された行動を実行し、実際の結果を観測した後、プランナーは状態（残存予算、時間、完了したサブタスク）を更新して再計画を行う。これにより、システムは確率的な失敗やリソース消費にリアルタイムで適応できる。

3. 理論的保証

本論文は、「安全な改善」の分析を提供する。有限サンプルのモンテカルロ誤差、候補セット近似誤差、および成功率/長さの推定誤差の範囲内で、MCPP 方策は、ポートフォリオ内の最良のベース方策と同等かそれ以上の制約付き完了確率をもたらすことが証明されている。これにより、プランナーは、単純な静的戦略（常に同じモデルとサンプリング幅を使用するなど）よりも決して劣らないことが保証されつつ、先読みを通じて大幅な改善の可能性を提供する。

主要な貢献

1. 問題定式化: 著者は制約駆動型オンラインリソース割り当ての設定を導入し、目的を平均効率フロンティアの最適化から、特定のワークフローインスタンスに対する厳格な予算およびデッドライン制約の充足確率の最大化へと転換させた。
2. アルゴリズムの提案: 著者は、シミュレートされたロールアウトを通じて制約付き完了確率を直接推定し、観測された結果に基づいて再計画を行うクローズドループプランナーMCPPを提案した。これは、単純な継続方策のポートフォリオを用いて将来の値を近似することで、網羅的な動的計画法を回避する。
3. 実証的検証: この手法は、依存関係が構造化された 2 つのベンチマーク、すなわちCodeFlow（コード生成と検証）およびProofFlow（形式的推論と証明生成）で評価された。
4. ロバスト性分析: 本論文は、入力推定値（成功率と生成長さ）にノイズがある場合でも MCPP が効果的であることを示した。これは、現実世界の展開において一般的なシナリオである。

実験結果

実験は、さまざまな予算（$B$）およびデッドライン（$D$）制約を用いて、CodeFlow および ProofFlow ベンチマークで行われた。

• 性能: MCPP は、サブタスク全体に予算を静的に割り当てるUniformや、下流の計画なしにオンラインで局所的にリトライするRetryを含む強力なベースラインを一貫して上回った。
• 厳格な制約: 改善は、厳格な制約下（例：B = \0.05$）で最も顕著であった。MCPP は、デッドラインが中程度に実行可能になった時点で急速に高い成功率を達成できたのに対し、ベースラインは大幅に低いままだった。
• 行動の多様性: 除去実験により、モデルポートフォリオの拡大（複数のモデルの使用）およびロールアウト幅ポートフォリオの豊かさ（サンプリング幅の多様化）に伴って性能が向上することが示された。これは、単一のグローバル戦略を使用するのではなく、特定のノードや状態に対して適切なモデルと計算強度を選択することの重要性を浮き彫りにしている。
• ロバスト性: 成功率の推定値にノイズがある場合（$\sigma=0.3$ のガウスノイズ）、MCPP の低下は約 6 パーセントポイントに留まり、不完全なプロファイル推定に対する耐性を示した。
• スケーラビリティ: この手法は、より大規模なワークフロー（より多くのサブタスク）に対して効果的にスケーリングされ、特に静的割り当てが中間結果に適応できない制約のあるシナリオにおいて、ベースラインに対する優位性を維持している。
• 効率性: オンライン計画のオーバーヘッドは中程度（標準構成では通常 5 秒未満）であり、リアルタイム実行に実用的である。

意義と主張

本論文は、その主な意義が、現実世界のエージェント展開におけるインスタンス固有の成功条件への対応にあると主張している。以前の研究は「性能・コスト・レイテンシフロンティア」（平均効率）の改善に焦点を当てていたのに対し、本研究は予算と時間を、成功か失敗かを定義する厳格な制約として扱う。

著者は、より良いフロンティアが、特定の制約下で自動的により良い行動方策につながるわけではないと論じている。MCPP は、ユーザーの特定の $B$ および $D$ 要件を満たす確率を直接最適化することで、このギャップを埋める。本論文は、MCPP がベース方策に対して安全な改善を提供し、制約のある環境で一貫した改善を示すと控えめに主張しており、全体的な最適性を主張したり、ワークフロー生成の一般問題（これは別の上位タスクとして扱われる）を解決したりするものではない。この研究は、ワークフロー構造と統計プロファイルが利用可能であると仮定した、エージェントシステムの実行段階に対する実用的なソルバーとして位置づけられている。