Dynamic MoE サービングの定数競合アルゴリズムを証明──ランダム化主問題で競合比 \Theta(1) を達成

論文概要

Dynamic Mixture-of-Experts (MoE) サービングにおけるランダム化主問題の競合比について、従来知られていた $O(\sqrt{\log k})$ の上界を改善し、任意の数の専門家（expert）に対して競合比が $\Theta(1)$ となる定数競合アルゴリズムを証明した。著者である Ian D'Ambrosio 氏は、逆数最大サービスコストの削減、有限接線包絡線、および Lazy Threshold Rounding を組み合わせた削減手法を構築し、さらにその完全な還元と丸め処理の合成を Lean 4 によって機械検証している。

新規性と貢献

本研究の最大の学術的貢献は、Dynamic MoE サービングのランダム化主問題における競合比のオーダーを $\Theta(1)$ に引き下げ、理論的な最適性を証明した点にある。実用面での貢献として、導出されたアルゴリズムの全還元、丸め構成、および定量化されたメイン定理が、定理証明支援系 Lean 4 を用いて厳密に機械検証されている点が挙げられ、アルゴリズムの正確性が形式的に保証されている。

提案手法の詳細

提案手法の核心は、逆数最大サービスコストを、被覆行スパリティ 2 を持つ正のボディの追跡（Chasing Positive Bodies at resource augmentation one and covering sparsity two）へと帰着させる点にある。具体的には以下のコンポーネントで構成される。

有限接線包絡線による各逆数エピグラフの定数ファクター近似
蓄積されたサービスを移動へと変換する加算的な正のリセット
正のボディアルゴリズムのリソース拡張を取り除く非拡張的バランス投影

これらにより得られた分数パスと Lazy Threshold Rounding を組み合わせることで、以下のバウンドが導出される。 $\mathbb{E}[\text{ALG}] \le 10 C_{\text{PB}} \text{OPT} + (5 C_{\text{PB}} + 2) k + 16$ ここで $C_{\text{PB}}$ は被覆スパリティ 2 における絶対定数である。決定論的な有理数制御と新たな独立リプレイが形式証明に付随している。

評価・考察

本研究は純粋なアルゴリズム理論・形式検証の論文であり、実際の GPU クラスタを用いたスループット測定ベンチマーク等の実験的評価は実施されていない。その代わり、Lean 4 を用いた厳密な形式検証により、 $E[ALG] \le 10 C_{PB} OPT + (5 C_{PB} + 2) k + 16$ という理論的バウンドが絶対的な確実性を持って示されている。

応用例と今後の展望

大規模言語モデル (LLM) の推論基盤において、動的な負荷分散や MoE モデルの効率的なサービングインフラを構築する際のアルゴリズム設計に基礎的な知見を提供する。国内のクラウドベンダーや LLM 基盤開発企業（例えば大規模モデルの商用 API を運用する事業者など）において、莫大なリソースを消費する MoE サービングの動的割り当て最適化の理論的裏付けとして参照される価値がある。今後の課題としては、機械検証された制御アルゴリズムを実際のの大規模推論ランタイムへと統合し、実運用環境におけるオーバーヘッドを検証することが挙げられる。

結論

Dynamic MoE サービングにおけるランダム化主問題の競合比が $\Theta(1)$ であることが証明され、その一連の証明は Lean 4 によって機械検証された。理論と形式検証の双方において、動的サービングアルゴリズムの設計に確固たる数学的基盤をもたらす成果である。

注釈

Mixture-of-Experts (MoE): 入力ごとに適切な専門家ネットワークを選択して処理を行う、大規模言語モデルのアーキテクチャ手法。
Lean 4: 数学の定理やプログラムの仕様が正しいことをコンピュータで厳密に検証するための定理証明支援系言語。