💻 computer science

Continuum: Efficient and Robust Multi-Turn LLM Agent Scheduling with KV Cache Time-to-Live

本論文は、マルチターン LLM エージェントワークフローにおけるツール呼び出しの一時停止中に動的な TTL 機構を用いて KV キャッシュを選択的に保持する新しい KV キャッシュ管理システム「CacheTTL」を導入し、既存の淘汰ポリシーと比較してジョブ完了時間を 8 倍以上改善し、スループットを向上させることを示す。

原著者： Hanchen Li, Runyuan He, Qiuyang Mang, Qizheng Zhang, Huanzhi Mao, Xiaokun Chen, Hangrui Zhou, Alvin Cheung, Joseph Gonzalez, Ion Stoica

公開日 2026-05-06

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Hanchen Li, Runyuan He, Qiuyang Mang, Qizheng Zhang, Huanzhi Mao, Xiaokun Chen, Hangrui Zhou, Alvin Cheung, Joseph Gonzalez, Ion Stoica

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたは、熟練のシェフ（AI）が多数の顧客のために複雑な料理を同時に調理する、極めて効率的で超高速なキッチンで働いていると想像してください。

問題：「一時停止と再開」のキッチン

通常の AI チャットボットでは、シェフは料理を完成させて提供し、すぐに次の料理に取り掛かります。キッチンが混雑すると、シェフは現在の料理の半調理済みの材料を捨てて、新しい注文のスペースを確保します。これは単純なチャットには問題なく機能します。

しかし、現代の AI「エージェント」は異なります。彼らは単に会話するだけでなく、行動します。彼らは考え、その後ツール（天気予報の確認やウェブ検索など）を呼び出し、結果を待ち、その後 同じ料理の調理を続けます。

現在のシステムには以下の欠陥があります：

シェフが料理の調理を開始する。
シェフがツールを呼び出すために一時停止する（例：「天気を確認」）。
シェフが「一時停止」しているため、キッチンシステムはその注文が完了したと判断する。他の注文のスペースを確保するために、半調理済みの材料（KV キャッシュ）を廃棄する。
ツールが 2 秒で完了する。シェフは再開の準備が整う。
大惨事： 材料がなくなっている！シェフは遠くの倉庫から材料を再購入する（CPU へのオフロード）か、最初からすべてを再調理する（再計算）必要がある。
さらに悪いことに、材料が捨てられたため、シェフは再び調理台のスペースを得るために他の顧客の列に並ばなければならない。

これは繰り返し発生します。エージェントが問題を解決するために 20 ステップを要する場合、作業のやり直しと列への並ぶことを 20 回も無駄に行う可能性があります。

解決策：CacheTTL（「準備維持」タイマー）

研究者たちは CacheTTL という新しいシステムを構築しました。これは、すべての注文に対してシェフに特別な**「準備維持」タイマー**を与えるようなものです。

シェフがツールを呼び出すために一時停止した際に、すぐに材料を廃棄するのではなく、システムはこう言います：「待て！このシェフは 2 秒後に戻ってくるかもしれない。材料をカウンターに一定時間（Time-To-Live、TTL）置いておこう。」

その仕組みを簡単に説明します：

スマートな予測： システムは履歴を確認します。「通常、シェフが『天気を確認』を呼び出すと約 2 秒かかる。『ウェブを検索』を呼び出すと 5 秒かかる。」
タイマー： その予測に基づいてタイマーを設定します。ツール呼び出しが 2 秒かかると予想される場合、材料は 2.5 秒間カウンターに残ります。
効果：
- シェフが時間通りに戻ってきた場合： 材料はまだあります！シェフは中断した場所から再開できます。再調理も、列に並ぶ必要もありません。
- シェフが遅れた場合： ツールが 2 秒ではなく 10 秒かかった場合、タイマーが切れます。システムは他の注文のスペースを確保するために、材料を安全に廃棄し、キッチンの混雑を防ぎます。

なぜこれがこれまでのものより優れているのか？

従来のシステムは、材料を保持すべきかどうかを推測しようとしましたが、見ていたのは一つのことだけでした：「材料を再購入するのは高いか？」彼らはより大きな問題を見落としていました：「シェフが仕事に戻るために列に並ぶのはどのくらいかかるか？」

CacheTTL は両方を考慮します：

料理を再作るコスト。
列に並ぶコスト（キューイング遅延）。

それは、全体として最も多くの時間を節約するために、材料をカウンターに置く最適な時間を計算します。

結果

研究者たちは、ソフトウェアのバグを解決し、ウェブを検索し、コードを記述する実世界の AI エージェントでこれをテストしました。その結果、以下がわかりました：

速度： 一部の現実世界のテストでは、エージェントがタスクを完了するまでの時間が最大で8 倍速くなりました。
効率： キッチン（GPU）は、詰まることなく一度に多くの注文を処理できました。
堅牢性： ツール呼び出しが予想より長くかかった場合でも、システムはクラッシュしたり詰まったりせず、単にタイマーを切らせて次の処理に進みました。

要約

CacheTTL は、シェフが電話をするために一時停止したとしても、調理が終わったわけではないことを知っている、賢いキッチンマネージャーのようなものです。材料を適切な時間だけ準備された状態に保つことで、シェフが最初からやり直したり、列に並んだりすることを防ぎ、キッチン全体をより滑らかで高速に稼働させます。

技術概要：CacheTTL

問題定義

大規模言語モデル（LLM）推論エンジンは、現在、キー・バリュー（KV）キャッシュ管理に対して「ターン終了時」の排除ポリシーに依存しています。これらのシステムでは、リクエストのデコーディングが完了すると、新しい着信リクエストへの利用最大化を図るため、その KV キャッシュは GPU メモリから排除されます。標準的なマルチターンチャットボットには効果的ですが、このポリシーは ReAct パラダイムに従うエージェントワークロード（例：ソフトウェアエンジニアリングエージェント、ツール利用エージェント）では機能しません。

エージェントワークフローでは、推論ステップが外部ツール呼び出しと交互に実行されます。これらのツール呼び出しは、人間の入力速度よりも短いことが多い pauses を導入しますが、標準的なエンジンでは KV キャッシュの排除をトリガーするのに十分な長さです。エージェントがツール呼び出しから戻り、次の推論ステップを開始する際、システムは以下のいずれかを選択せざるを得ません：

プレフィックスを再計算（プリフィル）し、重大なレイテンシを発生させる。
（オフロードが有効な場合）CPU メモリから KV キャッシュを再読み込みし、ターンごとのキューイング遅延を導入する。再読み込みが高速であっても、リクエストは他のアクティブなリクエストが GPU メモリを解放するまで、キューで待機しなければならない。

既存の解決策はこの課題を包括的に解決できていません：

InferCeptは再読み込みコストを考慮しますが、蓄積するターンごとのキューイング遅延を無視しており、可変のツール実行時間に対する堅牢性が欠如しています。
AutellixおよびPieは静的ワークフローに焦点を当てているか、動的なツール呼び出しに対する特定の保持ポリシーを欠いています。
静的保持戦略は、ツール呼び出しが予想以上に時間がかかる場合、GPU メモリのデッドロックを招くリスクがあります。

核心的な課題は、予測不可能なツール実行時間中に GPU メモリを独占することなく、再計算やキューイング遅延を回避するために KV キャッシュを十分に長く保持することです。

手法：CacheTTL

著者は、KV キャッシュ保持のためのTime-to-Live（TTL）メカニズムを導入するサービングシステムCacheTTLを提案します。即時排除の代わりに、CacheTTL は計算された期間、GPU メモリ内で KV キャッシュを選択的にピン留めします。

1. コスト・ベネフィット・ユーティリティモデル

CacheTTL は、キャッシュ保持のコストと排除を回避するベネフィットのトレードオフをモデル化することで、最適な TTL（ $\tau$ ）を決定します。

コスト（ $Cost(\tau, r)$ ）： GPU メモリを占有することによる機会コストです。リクエストのメモリ使用量をアクティブなリクエストの平均メモリフットプリントで割った値に、TTL 期間（ $\tau$ ）を乗じて計算されます。これは、ピン留めされたキャッシュによってブロックされる他のリクエストに追加されるレイテンシを表します。
ベネフィット（$Benefit(r)$）： 回避された 2 つのコストの合計です：
1. CacheMissCost： KV キャッシュを再構築（プリフィル）するか、CPU から再読み込むのに必要な時間。
2. OutofOrderCost： リクエストが排除され、GPU メモリが利用可能になるまでキューで待機した場合に発生するターンごとのキューイング遅延。この項は決定的であり、InferCept などの先行研究と CacheTTL を区別します。これは、残りのステップ数と現在の進行度の相関を測定する**メモリフルネス係数（ $\eta$ ）**によってスケーリングされます（例：固定長のプログラムは高いメモリフルネスを持ちます）。

2. TTL 計算

システムは、期待される正味ベネフィットを最大化することで最適な TTL（ $\tau^*$ ）を計算します：
$\tau^* = \arg\max_{\tau} \left( P(\tau, f) \times Benefit(r) - Cost(\tau, r) \right)$
ここで、 $P(\tau, f)$ はツール呼び出し $f$ が時間 $\tau$ 以内に完了する確率であり、過去のツール呼び出し記録からの経験的累積分布関数（CDF）を用いて推定されます。

コールドスタート処理： 歴史的データが乏しい場合、CacheTTL は指数分布の仮定またはグローバル平均から導出された固定 TTL にデフォルトします。
堅牢性： ツール呼び出しが TTL を超えた場合、KV キャッシュは自動的に排除され、無期限のメモリ占有や潜在的なデッドロックを防ぎます。

3. スケジューリングとシステム設計

プログラムレベルの FCFS： CacheTTL は、TTL とプログラムレベル（リクエストレベルだけでなく）でのファースト・カム・ファースト・サービス（FCFS）ポリシーを組み合わせます。これにより、同じエージェントプログラムに属するリクエストが連続性を維持するために優先されます。
TTL 認識型優先度： スケジューラは、マルチキー優先度タプルを割り当てます：
1. 中断ステータス。
2. TTL ステータス： アクティブな TTL（ピン留め）を持つリクエストは、ピン留めされていないものよりも優先されます。
3. プログラムレベルの到着時刻。
実装： vLLMの上に構築され、モジュール式のツール呼び出しハンドラを備えています。このハンドラは LLM 出力を解析してツール呼び出しを特定し、リクエスト間隔を記録し、TTL 値をスケジューラに伝達します。この設計は最小限のオーバーヘッド（約 1,000 行の Python）を追加し、CPU/SSD オフロードとも互換性があります。

主要な貢献

問題の特定： 既存の KV キャッシュ排除ポリシーは、ターンごとのキューイング遅延とツール呼び出し時間の可変性を無視することで、エージェントのパフォーマンスを劣化させることを特定しました。
CacheTTL システム： TTL メカニズムを活用して KV キャッシュを動的に保持する新規サービングシステム。プリフィル/再読み込みコストとメモリ競合コストのバランスを取ります。
新規コストモデル： 排除によるキューイング遅延ペナルティを定量化するOutofOrderCost項の導入と、異なるワークロード構造に適応するためのメモリフルネス係数の導入。
堅牢性： 最大保持時間を強制することで予測不可能なツール実行時間に対応し、デッドロックやメモリ圧迫を防ぎます。

実験結果

著者は、Llama-3.1（8B/70B）、Gemma-3（12B）、GLM-4.5（355B）を用いて、A100、H100、B200 などの各種ハードウェア上でSWE-Bench、BFCL、OpenHandsワークロードを評価しました。

レイテンシ削減： CacheTTL は、ベースライン（vLLM、Autellix、InferCept）と比較して、平均ジョブ完了時間を1.12 倍から 3.66 倍削減します。企業 A の内部テストベッドでの実世界の SWE エージェントテストでは、遅延が最大8.18 倍改善されました。
スループット： スループットは1.10 倍から 3.22 倍向上しました。
堅牢性： ベースラインが蓄積されたキューイング遅延により大幅に劣化するのに対し、システムはターン数の増加に伴い安定したパフォーマンスを維持します。
互換性： CacheTTL は CPU および SSD オフロードと組み合わせた場合でもベースラインを上回り、そのスケジューリング上の利点がメモリオフロード技術と直交していることを示しています。
オーバーヘッド： スケジューリングオーバーヘッドは無視できるレベル（単一桁ミリ秒）であり、エンドツーエンドのレイテンシ削減に比べてはるかに小さいです。

意義と主張

本論文は、CacheTTLが、マルチターンエージェントワークロード向けに特別に設計された、最初の堅牢でツール認識型の KV キャッシュ管理戦略を提供すると主張しています。「ターン終了時」の排除からTTL ベースの保持ポリシーへ移行することで、このシステムは LLM 推論と外部ツール実行の間のギャップを効果的に埋めます。

著者は、そのアプローチがモジュール式であり、既存の推論エンジンに最小限の変更で統合可能であることを強調しています。彼らは、原理に基づいたツール認識型 KV 管理が、エージェントワークフローがより複雑で多ターン化するにつれて、効率的なエージェントサービングの未来にとって不可欠であると論じています。論文は、エージェントサービングに関するさらなる研究を促進するため、トレース、コード、テストベッドをオープンソース化することで結論付けています。