🤖 machine learning

BlendServe: Optimizing Offline Inference for Auto-regressive Large Models with Resource-aware Batching

BlendServeは、リソースのオーバーラップとプレフィックス共有を効果的に組み合わせるためにリソース認識型のプレフィックスツリーを導入することで、オフラインの自己回帰型大規模モデル推論を最適化し、vLLMやSGLangといった業界標準に対して最大1.44倍のスループット向上を実現するシステムです。

原著者： Yilong Zhao, Shuo Yang, Kan Zhu, Lianmin Zheng, Baris Kasikci, Yang Zhou, Jiarong Xing, Ion Stoica

公開日 2026-06-09

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

CC BY 4.0

原著者： Yilong Zhao, Shuo Yang, Kan Zhu, Lianmin Zheng, Baris Kasikci, Yang Zhou, Jiarong Xing, Ion Stoica

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

あなたは、カスタムロボット（これらはAIモデルです）を製造する、大規模で高速な工場を運営していると想像してください。あなたの仕事は、数千件の注文（リクエスト）を処理してロボットを組み立てることです。

以前は、ロボットを素早く作りたい場合、2種類の注文のどちらかを選択しなければなりませんでした。

「重量級の力仕事」注文： 多くの筋肉（計算資源/Compute）を必要としますが、ストレージ容量（メモリ）はほとんど必要としません。例えば、「強力な腕を持つが、収納スペースを持たないロボット」を作る注文のようなものです。
「重量級のストレージ」注文： 筋肉はほとんど必要としませんが、膨大な量のストレージスペースを必要とします。例えば、「小さな腕しか持たないが、巨大な倉庫を内蔵したロボット」を作る注文のようなものです。

問題点：工場のフロアにおけるボトルネック

あなたの工場には、主に2つのリソースがあります。

筋肉マシン（計算資源/Compute）： 高速ですが、待ち時間が発生すると疲れてしまいます。
ストレージ棚（メモリ/Memory）： 容量は大きいですが、効率的に使われないと詰まってしまいます。

旧来の方法（ナイーブなバッチ処理）：
以前の工場では、単に注文が届いた順に処理していました。もし「重量級の力仕事」の注文が10件並んでいれば、筋肉マシンはフル稼働しますが、ストレージ棚は空のまま無駄になります。次に「重量級のストレージ」の注文が10件続けば、ストレージ棚は満杯になりますが、筋肉マシンは手持ち無沙汰に、ただ手をこまねいて待つことになります。

これは、トラックにレンガだけを詰め込んだり、次に羽毛だけを詰め込んだりするようなものです。これらを混ぜ合わせることができれば、もっと多く積み込めるはずなのに、トラック（コンピュータチップ）は時間の半分、空の状態になってしまいます。

新しい問題：
また、多くの注文が全く同じ最初のステップ（例：「ロボットを青く塗る」）を共有している場合を利用する「プレフィックス共有（Prefix Sharing）」というテクニックも使われていました。これらの注文を連続して行えば、青く塗る作業を一度だけで済ませ、その結果を再利用できます。

しかし、「共有（『青く塗る』の注文をまとめて行うこと）」のために最適な順番（＝同じ工程をまとめること）を選ぶと、どうしても「重量級の力仕事」の注文をまとめ、「重量級のストレージ」の注文をまとめることになってしまいます。これは「混ぜる」戦略を台無しにし、再びマシンを半分空の状態にしてしまうのです。

解決策：BlendServe

この論文の著者たちは、BlendServeと呼ばれるシステムを作り出しました。これは、仕事の順番を並べ替えて、両方の良いとこ取りができる超スマートな工場マネージャーのようなものです。

1. 「リソース認識型」ツリー：
BlendServeは、単純な一本の列ではなく、すべての注文を巨大な「家系図（ファミリーツリー）」として整理します。

枝（Branches）： 同じ開始ステップを共有する注文のグループ（プレフィックス共有）。
ラベル（Labels）： すべての枝には、どれだけの「筋肉」と「ストレージ」が必要かを示すラベルが付いています。

2. 「デュアルスキャナー」アルゴリズム：
これが魔法のトリックです。マネージャーは単に列を歩き回るのではなく、ツリーの両端から同時に作業を行います。

左側から「重量級の力仕事」の注文を掴みます。
右側から「重量級のストレージ」の注文を掴みます。
そして、それらを同じバッチの中に一緒に入れます。

結果：
これにより、工場が稼働するとき、筋肉マシンが懸命に働く一方で、ストレージ棚も同時に満たされていきます。両者が互いに助け合っているのです。トラックには、レンガと羽毛が完璧に混ざり合い、隙間なく積み込まれます。

なぜこれが重要なのか

この論文は、BlendServeが「共有ステップ」を維持しながらも、この巧妙な混合を行うことで、以下のことが実現できると主張しています。

現在のトップシステム（vLLMやSGLangなど）と比較して、工場を最大44%高速化できる。
**理論上の「完璧な」速度の90%**に到達できる。完璧な速度を時速100マイルだとすると、BlendServeは時速90マイルに到達できるのに対し、他のシステムは時速60〜70マイル程度にとどまるイメージです。

課題（そして、どのように解決したか）

論文では、AIがテキストを一単語ずつ生成していくため、「重量級のストレージ」注文が正確にどれくらい時間がかかるかを予測するのは難しいことを認めています。これを解決するために、BlendServeは注文の小さなサンプルに対して簡単な「テスト走行」を行い、それらがどれくらいの時間を要するかを推測し、その推測に基づいて完璧なミックスを構築します。たとえ推測が多少外れたとしても、システムはオンザフライ（即座に）で調整できるほど堅牢です。

要約すると、 BlendServeはコンピュータをアイドル状態にさせないためのスマートなスケジューラーです。異なるタイプのAIタスクを混ぜ合わせることで、コンピュータの「脳（計算資源）」と「メモリ（記憶）」を完璧に調和させ、オフラインのAI処理をより高速に、より安価に実現します。

テクニカルサマリー: BlendServe

問題提起

オフライン・バッチ推論は、モデル評価やデータキュレーションといった、レイテンシに敏感ではない大規模言語モデル（LLM）のタスクにおいて、コスト効率の高いソリューションとして台頭しています。低レイテンシを優先するオンライン推論とは異なり、オフライン推論は、緩和された時間枠内でスループット（秒あたりのトークン数）を最大化することを目指します。

チャンクド・プリフィル（Sarathi-Serve）やオペレータ・レベルのオーバーラップ（NanoFlow, Orion）といった既存のスループット最適化技術は、単一のバッチ内での計算リソースとメモリリソースのバランスを取ることに焦点を当てています。しかし、これらの手法は、アプリケーションの多様性が増すにつれて収穫逓減に直面します。現代のLLMワークロードは、極めて異なるリソース需要を示します：

計算集約型（Compute-intensive）: 入力シーケンスは長いが出力が短いタスク（例：文書要約、MMLUなどのベンチマーク）。これらはGPUの演算ユニットを飽和させる一方で、メモリ帯域幅は十分に活用されません。
メモリ集約型（Memory-intensive）: 出力シーケンスが長いタスク（例：ビデオ生成、推論/Reasoning）。これらは自己回帰的なデコードフェーズにおいてメモリ帯域幅を飽和させる一方で、演算ユニットは十分に活用されません。

バッチが主に一方のリクエストタイプで構成される場合、ハードウェアリソースは不均衡な状態となり、スループットが制限されます。さらに、リソースのオーバーラップを最大化するためにリクエストを単純に並べ替えることは、**プレフィックス共有（prefix sharing）**と衝突することがよくあります。プレフィックス共有を最大化する順序（通常、プレフィックスツリー上の深さ優先探索：DFS）は、バッチを単一のリソースタイプが支配する状態にする可能性があります。一方で、リソースのオーバーラップを最大化する順序は、プレフィックスの局所性を破壊してしまう可能性があります。

メソドロジー: BlendServe

BlendServeは、オフライン推論のスループットを最大化するために、リソース認識型バッチング（resource-aware batching）とプレフィックス共有を調和させるように設計されたサービングシステムです。そのコア設計は、主に以下の3つのコンポーネントで構成されています。

1. パフォーマンスモデリングと計算密度

BlendServeは、計算密度（compute density） $\rho$ という指標を導入しています。これは、リクエストにおける計算量依存オペレータの時間と、メモリ依存オペレータの時間の比として定義されます。

リクエストレベル: $\rho(r) = \frac{\text{Comp}(r)}{\text{Mem}(r)}$ 。高い $\rho$ は計算集約型のワークロードを示し、低い $\rho$ はメモリ集約型のワークロードを示します。
バッチレベル: システムは、総実行時間 $T$ を、計算時間（ $T_{comp}$ ）、メモリ時間（ $T_{mem}$ ）、およびプレフィックス共有率（ $s$ ）の関数としてモデル化します。目標は、冗長な計算を最小限に抑えつつ、計算操作とメモリ操作のオーバーラップを最大化することで $T$ を最小化することです。
出力推定: 自己回帰的な生成では出力長が未知であるため、BlendServeはウォームアップフェーズ中にサンプリング戦略を採用します。プロンプトのセマンティクスとタスクタイプに基づいて出力長分布を推論し、サンプリングされたリクエストを用いて、同じプレフィックス部分木内にある未サンプリングのリクエストの密度を推定します。

2. リソース認識型プレフィックスツリー

プレフィックス共有とリソースオーバーラップのトレードオフを管理するために、BlendServeはリソース認識型プレフィックスツリーを構築します。

構造: SGLangなどで使用されている、ノードが共有されたプロンプトセグメントを表すトライ（Trie）構造に基づいています。
拡張: 各ノードには、その部分木に含まれるすべてのリクエストの計算密度が注釈として付与されます。
ソートと分割: システムは各レイヤーのノードを計算密度に基づいてソートし、計算集約型のノードを左側に、メモリ集約型のノードを右側に配置します。グローバルな順序付けを乱す外れ値を処理するために、**条件付きノード分割（conditional node splitting）**技術が使用されます。ノードの密度が隣接するノードから大きく逸脱している場合、そのノードは分割され、再配置されます。これにより、より良いリソースバランスを実現するために、小さなプレフィックスセグメントを再計算するという制御されたコストが発生します。

3. デュアルスキャニング・アルゴリズム

最終的なリクエストスケジュールを生成するために、BlendServeはデュアルスキャニング・アルゴリズムを採用しています。

メカニズム: このアルゴリズムは、ソートされたプレフィックスツリーの左端（計算集約型）と右端（メモリ集約型）から同時にスキャンを行います。
バッチ形成: ツリーのルートと一致するターゲットとなるグローバルな計算密度（ $\rho_{target}$ ）を達成するために、必要なメモリパーティション（ $M_L$ および $M_R$ ）を動的に計算します。これらのパーティションを埋めるために両端からリクエストを選択することで、各バッチに計算集約型とメモリ集約型のリクエストのバランスの取れた混合が含まれるようにします。
結果: このアプローチは、プレフィックスの階層構造（高いプレフィックス共有の維持）を保持しながら、リクエストをインターリーブしてハードウェアリソースのオーバーラップを最大化します。

4. 分散デプロイメント

BlendServeは、**データ並列性（DP）およびテンソル並列性（TP）**をサポートしています。

DPでは、中央集中型のプレフィックスツリーは、バランスの取れたワークロードを確保するように異なるランクに割り当てられるサブツリーに分解されます。
TPでは、通信オーバーヘッドを計算とオーバーラップさせる既存のパイプライン戦略と統合し、大規模なデプロイメントとの互換性を維持します。

主な貢献

ワークロードの多様性の分析: 多様なLLMアプリケーション（チャット、コーディング、ビデオ生成）がいかに相反するリソース需要（計算 vs メモリ）を生み出し、既存のバッチング戦略を制限するかについての詳細な特性評価。
リソース認識型プレフィックスツリー: プレフィックス構造を保持しながらリソース需要（計算密度）をエンコードする新しいデータ構造。これにより、システムはプレフィックス共有とリソースオーバーラップの両方を同時に考慮できます。
デュアルスキャニング・アルゴリズム: ソートされたプレフィックスツリーを両端からスキャンすることで、リクエストのタイプを効果的にブレンドし、プレフィックス共有を犠牲にすることなくリソースのオーバーラップを最大化するヒューリスティックなスケジューリングアルゴリズム。
プロトタイプと評価: NanoFlowおよびSGLang上に構築されたフル実装。複数のモデル（Llama-3-8B/70B, Qwen-2.5, DeepSeek）および多様な合成ワークロードを用いて評価。

実験結果

著者らは、業界標準のベースライン（vLLM, SGLang）および最先端のスループット指向システム（NanoFlow）と比較して、BlendServeを評価しました。

スループットの加速:
- vLLM および SGLang と比較して、BlendServeは最大 1.44倍 のスループット向上を実現しました。
- スループットの現在の最先端である NanoFlow と比較して、BlendServeは平均 20.84% 高いスループットを提供します。
最適性ギャップ: BlendServeは、理論的な最適スループットの平均 86.55%（特定の構成では最大 90%）を達成しており、完璧なリソースオーバーラップとプレフィックス共有が可能である場合の限界に効果的に近づいていることを示しています。
リソース利用率: 計算とメモリの使用率の可視化により、BlendServeが推論ステップ全体で安定したバランスの取れたリソース利用を維持しているのに対し、NanoFlow-DFSのようなベースラインは、大幅な変動とリソースの低利用期間を示すことが確認されました。
プレフィックス共有: リソースバランスのためにリクエストを再配置しているにもかかわらず、BlendServeは標準的なDFS走査によって達成可能な最大プレフィックス共有率の 97% を維持しています。
スケーラビリティ: システムはデータ並列性（DP）に対してほぼ線形なスケーリングを示し、異なるモデルサイズ（7Bから72B）およびハードウェア構成においても効果的です。

意義と主張

本論文は、BlendServe が、リソースのオーバーラップとプレフィックス共有という、伝統的に相反する2つの目的を成功裏に調和させた、オフライン・バッチ推論のために特別に最適化された最初のサービングシステムであることを主張しています。

著者らは、LLMアプリケーションが多様化するにつれ、バッチ内のリソース需要が均一であるという仮定はもはや有効ではないと述べています。オフライン推論の緩和されたレイテンシ制約を利用してリクエストを再配置することで、BlendServeは従来のバッチ内最適化では達成できなかった大幅なスループット向上を実現します。本システムは、プレフィックスキャッシュの効率性を損なうことなく、最適なスループット（90%）に到達できることを証明しており、コスト効率の高い高スループットLLM推論のための堅牢なソリューションを提供します。