技術要約：LLM推論スループット向上のためのマルチビン・バッチング（Multi-Bin Batching）

問題提起

大規模言語モデル（LLM）の推論システムは、ハードウェアの利用率とスループットを最大化するためにバッチングに依存しています。しかし、標準的な静的バッチング（Static Batching）は、**実行時間の不均一性（heterogeneous execution times）**による重大な非効率性に直面します。静的バッチでは、最も長い生成時間を要するリクエスト（ストラグラー／遅延リクエスト）が完了するまで、サービングユニットがロックされてしまいます。これにより、実行時間の短いリクエストが早期に終了しても、次のバッチが開始されるまで待機しなければならず、リソースの過小利用が発生します。コンティニュアス・バッチング（反復レベルのスケジューリング）は、リクエストがバッチ内を動的に出入りすることを可能にすることでこの問題を緩和しますが、本論文の著者らは、出力長の変動によって引き起こされるストラグラー効果を解決することに焦点を当て、静的バッチングのフレームワーク自体を最適化することを目指しています。

手法：マルチビン・バッチング（Multi-Bin Batching）

本論文では、入力リクエストを予測された（またはオラクルによる）出力長に基づいて複数の「ビン（bin）」にグループ化する制御ポリシーであるマルチビン・バッチングを提案しています。

コア・アルゴリズム

1. ビニング（Binning）: 可能なサービス時間（出力長）の範囲を、$k$ 個のビン（境界 $[l_{i-1}, l_i]$）に分割します。
2. 割り当て（Assignment）: 入力リクエストを、推定された、あるいは既知のサービス時間に基づき、特定のビンに割り当てます。
3. バッチ形成（Batch Formation）: 各ビン内でサイズ $B$ のバッチを形成します。
4. ディスパッチ（Dispatch）: 完了したバッチを処理用のセントラルキューに送ります。

リクエストを類似した実行時間を持つもの同士でグループ化することで、最大サービス時間がバッチの所要時間を支配してしまうことによる「計算の無駄」を最小限に抑えます。

理論的枠組み

著者らは、システムをポアソン到着を伴う単一サーバー待ち行列システムとしてモデル化しています。サービス時間が独立同一分布（i.i.d.）であるという仮定の下で、バッチの期待サービス時間を分析しています。

• 一様分布: サービス時間が $[l_{min}, l_{max}]$ で一様に分布する場合、著者らは、各ビンが等しい確率質量を持つときにスループットが最大化されることを導き出しました。最適な決定境界は線形となります：$l_i = l_{min} + \frac{i}{k}(l_{max} - l_{min})$。
• 指数分布: 指数分布に従うサービス時間に対して、著者らは期待サービス時間の上界と、切断指数分布の順序統計量を用いた最適な境界を導出しています。
• スループット分析: 理論的分析により、ビン数 $k$ が増加するにつれて、バッチの期待サービス時間は減少し、システムのスループットは理想的な静的バッチング容量（バッチのサービス時間が単一リクエストの平均サービス時間に等しい状態）に近づくことが証明されています。最大容量の $\epsilon$ 以内のスループットを達成するために必要なビン数は、$O(1/\epsilon)$ でスケールします。

主な貢献

1. 新しいスケジューリング戦略: 静的バッチングにおけるストラグラー効果を最小化するために、長さ認識型のビニング・ポリシーを導入しました。
2. 理論的な最適性: マルチビン・バッチングが、$k \to \infty$ において静的バッチング・モデルの下で漸近的なスループット最適性を達成すること、および特定のスループット向上を実現するために必要なビン数の特性を証明しました。
3. 実証的な検証: 実世界のLLM推論ワークロード（llama.cpp および Llama-3.2-3B-Instruct を使用）を用いて、静的バッチング、ネイティブのコンティニュアス・バッチング、およびオラクル長と推定長を用いたマルチビン・バッチングを包括的に比較実験を行いました。

実験結果

著者らは、2つのワークロード（制御された一様長ワークロードと、長さが多様なDollyデータセット）で手法を評価しました。

1. 制御されたオラクル長ワークロード

• 設定: 1,024 リクエスト、バッチサイズ 32、ターゲット長の一様分布（500–2000 トークン）。
• 結果: $k=16$ のマルチビン・バッチングは 1,380.48 tokens/s を達成し、標準的な静的バッチング（534.23 tokens/s）と比較して 158.4% の向上を実現しました。
• 比較: この結果は、ネイティブのコンティニュアス・バッチングのベースライン（1,348.49 tokens/s）をわずかに上回り、十分に細かい粒度の長さグループ化が、制御された不均一性の下でコンティニュアス・バッチングに接近、あるいは凌駕できることを示しました。

2. Dolly データセット（オラクル長）

• 設定: 1,478 リクエスト、バッチサイズ 64、実世界の長さ分布。
• 結果: オラクル長に基づく $k=8$ のマルチビン・バッチングは 965.97 tokens/s を達成し、静的バッチング（273.53 tokens/s）に対して 253.1% の向上を実現しました。
• ギャップ: 静的バッチングに対しては劇的な改善を見せたものの、ネイティブのコンティニュアス・バッチングのベースライン（1,200.07 tokens/s）には 19.5% 未満の差で及びませんでした。

3. Dolly データセット（推定長）

• 設定: プロンプトのプリフィル（prefill）隠れ状態に基づく軽量な予測器を使用して長さを推定。
• 結果: 推定長を用いたマルチビン・バッチング（$k=8$）は 684.02 tokens/s を達成し、静的バッチングに対して 150.1% の向上を実現しました。
• 精度: 予測器は高い隣接ビン精度（$k=8$ で 94.89%）を達成しており、これはほとんどのエラーが隣接するビン内に局在していることを意味します。
• ギャップ: 推定による結果は、コンティニュアス・バッチングのベースラインよりも 43.0% 低い値となりました。これは予測エラーの影響を浮き彫りにしていますが、実用的なエスティメータ（推定器）が依然として大幅な利得をもたらすことを裏付けています。

4. エラーに対する堅牢性

対称的な隣接ビンエラーを用いたシミュレーションでは、予測エラーの確率が増加するにつれてスループットは緩やかに低下しますが、マルチビン・ポリシーは中程度のノイズに対しては堅牢であり続けることが示されました。

意義と主張

本論文は、マルチビン・バッチングを現代的なコンティニュアス・バッチング・システム（vLLM や SGLang など）の代替品としてではなく、補完的なスケジューリング原理として位置付けています。

• 静的な非効率性の緩和: この手法は、不均一な実行時間に起因する静的バッチング固有の非効率性を大幅に軽減します。
• 長さ情報の役割: 結果は、正確な長さ情報が強力なスケジューリング信号であることを強調しています。不完全な推定であっても、大幅なスループット向上が可能です。
• 統合の可能性: 著者らは、長さ認識型のグルーピングが、スループットとレイテンシのトレードオフをさらに最適化するために、キュー・クラス、アドミッション・コントロールの決定、またはレプリカ・ルーティング・ポリシーを通じて、現代のサービング・システムに統合できることを示唆しています。
• 限界: 著者らは、マルチビン・バッチングがコンティニュアス・バッチングとの差を縮めるものの、さらなる統合や適応戦略なしには、複雑な実世界のワークロードにおいてその差を完全に埋めることはできないと認めています。理論的分析は出力長の不均一性の影響を切り離して扱っており、生産システムにおける他のコスト（例：プリフィルとデコードの相互作用の複雑さ）はモデル化していませんが、実証結果にはこれらの要素が含まれています。