🤖 AI

Beyond Accuracy and Cost: Latency-Aware LLM Query Routing for Dynamic Workloads

本論文は、最初のトークン生成までの時間（time-to-first-token）を推定する軽量なエスティメータと、精度、コスト、およびレイテンシを統合的に最適化する戦略を組み合わせた、レイテンシを考慮したクエリルーティングシステムを提案しており、標準的な負荷分散手法と比較して、応答時間を増加させることなく、精度とコストの効用を最大40%向上させることに成功している。

原著者： Shivam Patel, Akaash R. Parthasarathy, Ankur Mallick, Gauri Joshi

公開日 2026-07-22

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

CC BY 4.0

原著者： Shivam Patel, Akaash R. Parthasarathy, Ankur Mallick, Gauri Joshi

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

あなたは、それぞれ異なるスキルレベルと価格設定を持つシェフのチームを抱えている世界を想像してみてください。ミシュラン星を獲得できるほどの料理を作り上げることができますが、多額の費用がかかり、時間も長くかかるマスターシェフもいます。一方で、手早く、手頃な価格で、まともなバーガーを瞬時に作ることができる素早いラインクックもいます。人工知能の世界において、これらの「シェフ」とは、物語を書いたり、数学の問題を解いたり、ニュースを要約したりするチャットボットの背後にある頭脳である、大規模言語モデル（LLM）のことです。あなたが質問をすると、「ルーター」がどのシェフに仕事を任せるかを決定します。目標はシンプルです。最高の回答を、最も低いコストで得ることです。

しかし、ほとんどのルーターがこれまで無視してきた落とし穴があります。それは「行列」です。たとえ完璧なシェフを選んだとしても、もしそのシェフが他の注文で手一杯であれば、あなたの料理は厨房で長い間放置されることになるかもしれません。AIの世界では、この待ち時間のことを「レイテンシ（遅延）」と呼びます。チャットボットに質問をした際、もし相手が忙しければ、あなたは数分間も回転するカーソルを見つめ続けることになるかもしれません。これは問題です。なぜなら、時には単に「良い回答」だけでなく、「今すぐ」回答が必要な場合があるからです。研究者たちが解決しようとしている大きな問いは、「キッチンが混沌とした状況であっても、いかにして安く済ませつつ、優れた回答を素早く得るための適切なシェフを選ぶか」ということです。

ここで、カーネギーメロン大学とマイクロソフトの研究者による新しい研究が登場し、まさにこの問題を解決しようとしています。彼らは、現在のシステムは品質とコストのバランスを取ることは得意ですが、「レイテンシに対して無頓着（latency-agnostic）」、つまり、実際の行列がどれほど長いかに盲目であることを突き止めました。これを解決するために、チームはデジタルな水晶玉のように機能する、巧妙で軽量な「シミュレーター」を構築しました。サーバーがどれほど忙しいかを単に推測するのではなく、このシミュレーターはリアルタイムで厨房を観察します。待機している注文数、現在調理中の料理にかかる時間、さらには厨房スタッフがどのように作業をまとめて処理（バッチ処理）しているかまでもを監視します。そして、あなたの特定の注文に対して、最初のひと口（彼らが「Time-to-First-Token」と呼ぶ指標）が提供されるまで、正確にどれくらいの時間がかかるかを予測します。

この予測をルーティングシステムに組み込むことで、研究者たちは、メニューの価格やシェフの評判だけでなく、「待ち時間」をも考慮するスマートな配膳係を作り上げました。彼らはさまざまな種類の質問と、さまざまなレベルの厨房の混乱を用いてこのシステムをテストしました。結果は有望なものでした。彼らの新しい手法は、既存の標準的な手法と比較して、品質、コスト、速度のバランス（回答の「価値」）を最大40%向上させ、かつ、待ち時間を既存の優れた負荷分散技術と同等の低さに維持することに成功しました。要するに、彼らは「行列」にようやく注意を払うことで、AIチャットボットをより速く、より安く、より賢くする方法を見出したのです。

彼らの革新の核となるのは、「Serving Framework Simulation（SFS）」と呼ばれるツールです。これは、混雑した高速道路の交通管制官のようなものだと考えてください。古い手法は、単に道路上にいくつの車がいるかを数えて、移動時間を推測するだけかもしれません。しかし、SFSはよりスマートです。実際の走行条件をシミュレートします。ある車は速いが重い（長くて複雑な質問のような）こともあれば、ある車は軽くて数が多い（単純な質問のような）こともあることを理解しています。また、高速道路には車が合流するルールや、走行できる速度のルールがあることも知っています。これらのルールをシミュレートすることで、SFSは新しい車がいつ出口ランプに到着するかを正確に予測できます。

研究者たちは、単に道路上の車の数に基づいて推測する手法（彼らが「スループットベースの推定」と呼ぶ方法）は、しばしば悪い予測につながることを発見しました。もし高速道路が、低速で重いトラックで渋滞していれば、たとえ総車両数がそれほど多くなくても、新しい車は足止めを食らう可能性があります。しかし、彼らのシミュレーションは、この「交通渋滞」の効果を考慮に入れています。彼らは、短い物語の執筆から長いレポートの要約まで、さまざまなタスクでこのシステムをテストし、既存の最良のベースラインよりも「OnTimeUtility」（回答の質、コスト、および到着のタイミングを測定するスコア）を33%から40%向上させたことを確認しました。

また、非常に興味深い発見の一つは、このシステムが「バースト的（突発的）」なトラフィックをどのように扱うかという点です。ランチタイムの客のように、注文が一度に殺到する場面を想像してみてください。古いシステムはしばしば圧倒されてしまい、全員を最も安価で最も遅いシェフへと送り込み、大規模な遅延を引き起こします。しかし、新しいシステムは動的に負荷をシフトさせます。例えば、列が短い場合は単純な質問を速くて安いモデルに送り、複雑で緊急性の高い質問は、列が少し長くても全体としてより早く仕事を終えられる強力なモデルへと送る、といった具合です。この柔軟性により、需要が急増しても高いパフォーマンスを維持することができます。

さらに、チームは自分たちのシミュレーター自体が極めて高速であることも示しました。シミュレーションを実行して決定を下すのに1ミリ秒もかからないため、助けようとしているシステム自体の速度を落とすことがありません。これは極めて重要です。なぜなら、ルーターが決定を下すのに時間がかかりすぎてしまうと、時間を節約するという目的そのものが台無しになってしまうからです。彼らは、予測の精度を検証し、テストにおいて誤差率が5%未満であることを確認しました。これは、古い単純な推測方法で見られた85%の誤差率と比較して、大幅な改善です。

結局のところ、この論文は、効率的なAIの未来は、単にモデルを大きくしたり、より安いものを見つけたりすることではなく、「より優れた交通管理者」になることにあると示唆しています。「どのモデルが最適か」という知恵と、「行列がどれくらい長いか」という現実を組み合わせることで、負荷が高い状況下でも、即時性と応答性を感じさせるシステムを作ることができます。結果はシミュレーションと制御された実験に基づいたものですが、著者らは、このアプローチが、AIサービスをより信頼性が高く、ユーザーフレンドリーなものにするための実用的な道筋を提供すると信じています。

技術要約：精度とコストを超えて：動的なワークロードに対するレイテンシを考慮したLLMクエリ・ルーティング

問題提起

現代の言語クエリ・ルーターは、異なる大規模言語モデル（LLM）インスタンスにクエリを割り当てることで、応答品質（精度）と金銭的コストのトレードオフを最適化しています。しかし、既存のルーターは本質的に**レイテンシを無視（latency-agnostic）**しています。これらは精度とコストの予測に基づいてモデルを選択しますが、特定のモデルインスタンスでクエリが経験する生成レイテンシを考慮していません。

実際には、レイテンシはシステムレベルの負荷分散ポリシー（例：ラウンドロビン、最短キューへの結合）によって決定されますが、これらはモデルの精度や推論コストを考慮していません。逆に、システムレベルのレイテンシ最適化は、固定されたクエリとモデルの割り当てを前提としており、精度とコストのトレードオフを無視しています。ここにギャップが生じます。現在のルーターは、過負荷状態のインスタンスにクエリをルーティングしてしまい、長いキューイング遅延を引き起こし、サービスレベル目標（SLO）を違反させる可能性があります。一方で、システムレベルの最適化手法は、モデルプールの持つ異種混合な精度・コスト能力を活用することができません。

核心となる課題は、生成レイテンシが非決定的であり、以下の要素に依存することです：

ハードウェア仕様とモデルアーキテクチャ。
インスタンスにおける現在のワークロードの構成（プリフィル段階 vs デコード段階）。
サービングフレームワーク（例：vLLM、Sarathi-Serve）のバッチ処理およびスケジューリング・ポリシー。

新しく到着したクエリの**Time-to-First-Token（TTFT）**を正確に推定することは困難です。なぜなら、新しいクエリを既存の常駐シーケンスとどのようにバッチ処理するか（プリフィルによる計算量集約型処理とデコードによるメモリ帯域集約型処理の両方の干渉を考慮して）を、サービングフレームワークの挙ディナミクスをシミュレートする必要があるからです。

手法

著者らは、精度、コスト、およびレイテンシを共同で最適化するルーティング・フレームワークを提案しています。このシステムは、主に3つのコンポーネントで構成されています。

1. ルーティング目的

ルーターは、TTFT制約（ $\tau_i$ ）を満たしつつ、精度・コスト・ユーティリティ（ $\hat{U}_{i,j}$ ）を最大化するように、クエリ $q_i$ に対してモデルインスタンス $m(i)$ を選択します。

ユーティリティ: $\hat{U}_{i,j}(\lambda) = \hat{acc}_{i,j} - \lambda \cdot \hat{cost}_{i,j}$ 。ここで $\lambda$ は品質とコストのバランスを取ります。
制約: 選択されたインスタンスは、 $\hat{L}^{ttft}_{i,j}(t) \leq \tau_i$ を満たさなければなりません。もし制約を満たすインスタンスが存在しない場合、ルーターは推定レイテンシが最小となるインスタンスを選択します。
評価: パフォーマンスは、レイテンシ制約を満たしたクエリのユーティリティを平均するOnTimeUtilityによって測定されます（制約に違反したクエリにはゼロのユーティリティを割り当てます）。

2. サービングフレームワーク・シミュレーション（SFS）レイテンシ推定器

リアルタイムの実行を行わずにTTFTを正確に予測するために、著者らはサービングフレームワークの挙動をシミュレートする軽量な推定器を設計しました。

入力: 推定器は、現在のモデルインスタンスの状態（常駐しているリクエストの集合 $R_j(t)$ 、それらの残りのプリフィル・トークン数、および予測されるデコード長を含む）を使用します。
シミュレーション・プロセス:
1. 新しいクエリとすべての常駐クエリを含む拡張ワークロードを構築します。
2. サービングフレームワークの**継続的バッチ処理（continuous batching）**とスケジューリング・ポリシーを決定論的にシミュレートし、トークン・バッチを形成します。
3. 新しいクエリが最初のデコード・トークンを生成するまで、これらのバッチを反復処理します。
トークン・バッチ処理時間モデル: 低レベルのカーネルをシミュレートする代わりに、推定器はキャリブレーションされた線形モデル（式9）を使用して、各トークン・バッチの時間を予測します。このモデルは以下を考慮します：
- 固定オーバーヘッド。
- トークンごとの高密度層（dense layer）の計算（バッチサイズに比例）。
- アテンション計算とKVキャッシュの読み出し（デコードにおけるコンテキスト長に比例）。
- プリフィル・アテンションのコスト（プリフィル・チャンク内での二次関数的コスト）。
出力: 最初のデコード・トークンに至るまでの予測された全バッチの処理時間の合計が、TTFTの推定値となります。

3. 平均ケースの推定（リアルタイム・データがない場合）

リアルタイムのワークロードのスナップショットが入手できないシナリオ（例：サードパーティのクラウドへのルーティング）では、**限定プロセッサ共有（Limited Processor Sharing: LPS）**モデルを用いた待ち行列理論による抽象化を提案しています。これは、インスタンスを、最大 $k$ 個の同時実行クエリ間で容量を共有するサーバーとしてモデル化し、それ以外はFIFOキューで待機するものとして扱います。これにより、到着率とサービス容量に基づいた平均待ち時間の推定が可能になります。

主な貢献

共同最適化フレームワーク: 本論文は、精度・コスト・ルーティングとシステムレベルのレイテンシ最適化の間の溝を埋め、これら3つの指標に基づいてルーティング決定を行うルーターを設計することで、両者を橋渡ししています。
軽量なSFS推定器: 著者らは、オートレグレッシブなトークン・バッチ処理をシミュレートする新しいレイテンシ推定器を導入しました。これは、フル実行を必要とすることなく、プリフィルとデコードのワークロード、およびサービングフレームワークのポリシー（チャンク分割プリフィルなど）の間の複雑な相互作用を捉えることができます。
高い精度と低いオーバーヘッド: SFS推定器は、TTFT予測において5%未満の平均絶対パーセント誤差（MAPE）を達成し、テスト時のオーバーヘッドは約0.14 ms（サブミリ秒）であり、ルーティングのクリティカルパスに適しています。
堅牢性: フレームワークは、標準的なポアソン到着と、バースト性の高いマルコフ変調ポアソン過程（MMPP）到着の両方で評価され、一貫した性能向上を示しています。

実験結果

著者らは、H100 GPU上でvLLMサービングフレームワークを用いて展開された3つのQwen3モデル（0.6B, 8B, 32B）を用いて、提案手法を評価しました。彼らは、SFSベースのルーターを以下の3つのベースラインと比較しました：

ラウンドロビン: ワークロードを無視した循環的な割り当て。
最短キュー: 最もリクエストが少ないインスタンスに割り当てる（レイテンシ重視だが、精度には無頓着）。
レイテンシ非考慮（Latency-Agnostic）: レイテンシを無視してユーティリティを最大化する。

主な知見:

ユーティリティの向上: 提案手法は、標準的な負荷分散ベースライン（最短キューなど）と比較して、同じレイテンシ制約を維持しながら、精度・コスト・ユーティリティを最大40%向上させました。
OnTimeUtility: 様々なクエリ到着率において、SFSルーターは、最高のベースラインと比較してOnTimeUtilityの曲線下面積（AUC）で33%高い値を達成しました。
トレードオフ制御: ラグランジュ緩和におけるレイテンシ・ペナルティ・パラメータ $\delta$ を変化させることで、ルーターはユーティリティとレイテンシの制御可能なトレードオフ曲線を提供し、これらを効果的にバランスできないベースラインを凌駕しました。
推定器の性能: デコード干渉を無視するスループットベースのベースラインは、85%のMAPEを示しましたが、SFS推定器はこれを**5%**に減少させました。これは、完全なサービングフレームワークのダイナミクスをシミュレートすることの必要性を浮き彫りにしています。

重要性と主張

本論文は、動的なワークロードにおいて効率的なLLM展開を行うためには、精度、コスト、およびレイテンシの共同最適化が不可欠であると主張しています。著者らは、既存のルーターがレイテンシをモデル選択とは別のシステムレベルの懸念事項として扱っているために失敗しており、その結果、リソース利用が最適化されず、SLO違反を招いていると論じています。

軽量なシミュレーションベースのレイテンシ推定器をルーティング決定に直接統合することで、提案フレームワークは、強力な精度・コスト性能を維持しながら、過負荷のインスタンスを回避します。この研究は、「スマート・ルーティング」（精度/コスト）と「ロードバランシング」（レイテンシ）という、これまで分離されていた目標を効果的に統合し、（最大40%の）ユーティリティ向上を実現できることを示しています。著者らは、これを、クエリのワークロードが動的であり、かつSLOが厳格な実世界のデプロイメントにおける実用的なソリューションとして位置付けています。