技術サマリー: HeraSys

問題提起

大規模言語モデル（LLM）の普及により、アプリケーション開発は単純なシングルターンの対話から、有向非巡回グラフ（DAG）で表される複雑なマルチテナント・エージェンティック・ワークフローへと移行しました。既存のサービングシステムは、主に単一のワークフロー内のパフォーマンス最適化、あるいはワークフロー内の依存関係（例：LLM推論のバッチング）に焦点を当てています。しかし、これらのアプローチは並行するワークフローを独立したインスタンスとして扱うため、マルチテナント環境において以下の2つの決定的な非効率性を引き起こします。

1. 計算の冗長性: 並行するクエリは、同じドキュメントチャンクの埋め込み、同一データの取得、あるいは同様のコンテキストを用いた同一ツールの呼び出しといった、構造的な共通性を共有することがよくあります。現在のモジュール設計には、これらの重複を検出するためのグローバルな視点が欠けており、システムは冗長なタスクを実行することを余儀なくされます。
2. スケジューリングの非効率性と不公平性: 現実世界のワークロードは高い異質性を示し、短いタスク（例：単純なQA）と長いタスク（例：多段階の推論）が混在しています。従来のFirst-Come-First-Served（FCFS）のようなスケジューリングポリシーは、長いタスクが短いタスクを遅延させるヘッド・オブ・ライン（HOL）ブロッキングに陥ります。逆に、短いタスクを厳格に優先する（例：Shortest Job First）手法は、長いタスクのスターベーション（飢餓状態）を引き起こし、公平性とテールレイテンシを低下させます。

メソドロジー

著者らは、二層の最適化アーキテクチャを通じて、並行するマルチワークフロー・シナリオを最適化するために設計された、きめ細かなエンドツーエンドのサービングシステムであるHeraSysを提案しています。

1. 実行前最適化: セマンティック・グラフ・フュージョン（Semantic Graph Fusion）

HeraSysは、実行前に流入するクエリのグローバルなコンテキストを分析することで、リクエストレベルの隔離を打破します。

• ノード・セマンティック・シグネチャ: システムは、オペレータの型、パラメータ、入力データ、および先行するノードのシグネチャに基づいて、各タスクノードに一意のハッシュ・シグネチャを割り当てます。これにより、システムは、異なるクエリ間で論理的には独立しているが計算上は等価なタスクを特定できます。
• トポロジカル・フュージョン: 短い時間窓内に到着する並行クエリに対して、システムは冗長なノードを融合（フュージョン）します。新しいクエリ内のノードが、すでに準備待ちキューにあるノードと一致する場合、その新しいノードは実行グラフから削除され、そのダウンストリームの依存関係は既存のノードへとリダイレクトされます。
• 非同期キャッシュ再利用: 時間窓外のリクエストに対しては、完了したノードの結果を再利用するか、現在実行中のノードが終了するのを待機して出力を共有します。
• 優先度調整: 融合されたノードには、すべてのマージされた論理ノードの寄与の合計として計算される、より高いスケジューリング優先度が割り当てられ、複数のダウンストリームパスを同時に加速させます。

2. ランタイム最適化: ロード認識型結合スケジューリング（Load-Aware Joint Scheduling）

ランタイムスケジューラは、実行順序とリソース割り当てを動的に管理し、平均レイテンシと長いテールタスクに対する公平性のバランスを取ります。

• 動的残り時間推定: システムは、オフラインプロファイリングとオンライン実行の進捗を組み合わせることで、各クエリの残りサービス時間（$\hat{S}_q$）を推定します。長いデコーディング・オペレータは、きめ細かなプリエンプション（中断）と正確な追跡を可能にするために、逐次的なサブノードへと分解されます。
• ノード寄与度指標: 指標（$\phi_v$）は、ダウンストリームのワークロード、パスの長さ、および並列ブランチに基づいて、クエリの進捗に対するノードの寄与を定量化します。
• リソース・スキューイングとパーティショニング: スターベーションを防ぐため、システムは残り時間の分布から導出された動的な閾値に基づいて、クエリを「長い」ものと「短い」ものに分類します。重いノードに対して最小限のリソース予約を強制することで、短いタスクが低レイテンシのために優先される一方で、長いクエリのヘビーなノードが保証されたリソースシェアを受け取れるようにします。
• 結合優先度関数: スケジューラは、以下の3つの要素のバランスをとる複合優先度関数 $\pi_v$ を用いて、準備完了ノードの順序を決定します。
  1. 動的最短残り時間優先（SRTF）: 平均レイテンシを最小化します。
  2. トポロジカルな寄与: ダウンストリームの作業をアンロックするクリティカルなノードを優先します。
  3. アンチ・スターベーション: 長いタスクにおけるヘビーなノードの優先度を高めます。
• 適応型実行: システムは、システム負荷に基づいてバッチサイズとパイプライン分解の粒度を動的に調整します。高負荷時にはスループットを向上させるためにバッチングを強化し、低負荷時にはデータ並列性を活用してレイテンシを削減するためにパイプライン分割を増やします。

主な貢献

1. 二層最適化アーキテクチャ: HeraSysは、実行前のグラフ融合とランタイムの動的スケジューリングを統合することで、従来の要求レベルの隔離を克服し、リソース利用率とスケジューリング効率の結合最適化を実現するシステムを導入しました。
2. クエリを跨ぐグラフノード再利用: セマンティック・シグネチャのマッチングを通じて、ワークフロー間で冗長な計算サブグラフを特定し排除するメカニズムを提供します。これにより、計算オーバーヘッドを大幅に削減します。
3. ロード認識型結合スケジューリング戦略: 動的なタスク分類、偏ったリソース割り当て、および適応型バッチングを統合し、エンドツーエンドのレイテンシを効果的に削減しながら、長いテールタスクに対する公平性を確保する戦略です。
4. 実装と評価: 著者らは、バックエンドとしてvLLMを使用し、NVIDIA RTX 4090 GPUを搭載したサーバー上にHeraSysを実装し、広範な比較を通じてその有効性を実証しました。

実験結果

著者らは、多様なワークロード（リランキングあり/なしのRAG、Web検索、および混合シナリオ）において、様々な並行度（6から300）の下で、LangGraph、LlamaIndex、および最先端のシステムであるAyoと比較してHeraSysを評価しました。

• レイテンシ削減: 厳格なレイテンシ保証条件下において、HeraSysはベースラインと比較してP99レイテンシを最大2.17倍、P95レイテンシを最大1.94倍削減しました。混合ワークロードにおいて、P99レイテンシで2.17倍の改善を達成しました。
• スループット向上: 本システムは、ベースラインと比較してサービングスループットを最大1.85倍向上させました。
• アブレーション研究: 実験により、グラフフューザ（Graph Fuser）を削除するとスループットが約1.16倍低下すること、また、リソーススキューイングなしでSRTFスケジューリングのみを使用した場合は、フルシステムと比較してP99レイテンシが22.3%増加することが確認され、結合最適化アプローチの必要性が強調されました。
• 公平性: リソーススキューイング・メカニズムは、純粋なSRTF戦略に共通するスターベーションの問題を効果的に緩和し、短いタスクの応答性を大きく損なうことなく、長いタスクに対してより予測可能なサービス品質（QoS）を提供しました。

意義と主張

本論文は、HeraSysが、単一のリクエスト最適化から協調的なクロスワークフロー最適化へと焦点を移すことで、LLMサービング・インフラストラクチャにおける重要な進歩を提供すると主張しています。微細な構造的共通性を活用し、リソースの競合を動的にバランスさせることで、HeraSysはマルチテナントのエージェンティック・ワークフローにおける固有の冗長性とスケジューリングの課題に対処します。著者らは、このアプローチが、より効率的でスケーラブルかつ公平なLLMアプリケーション・サービングシステムの構築に向けた洞察を提供し、最終的には計算リソースの消費と運用コストを削減しつつ、ユーザー体験を向上させるものであると述べています。