提出首个确定性常数竞争力的动态专家服务算法,无需随机化即可稳定高效分配GPU资源。
A Deterministic Constant-Competitive Algorithm for Dynamic Mixture-of-Experts Serving
- 设计确定性算法,通过路径压缩与整数舍入实现低延迟调度
- 理论保证服务成本与最优解相差不超过10倍常数,移动开销可控
- 全程机器验证,适用于大规模动态负载场景的系统设计
动态混合专家服务需在工作负载变化时将k个副本GPU分配给m个专家。每轮在线算法根据当前负载选择整数副本数,支付瓶颈服务成本与副本迁移成本,且无法预知未来负载。此前黄、娄、肖给出了一个O(√log k)竞争力的随机算法。本文证明存在一个确定性O(1)竞争力算法:对任意专家数及k≥1,均有ALG_det ≤ 10 C_PB OPT + (5 C_PB + 8)k + 16,其中C_PB是正体追逐问题在资源增强一和覆盖稀疏度二下的绝对常数。因此,对所有k≥1,CR_det(k) ≤ 10 C_PB,即为Θ(1)。该乘法因子不依赖专家数、副本预算、时间范围或负载值。故渐近性能无需随机化。证明分两层:有限切线包络、可求和正重置与非扩张平衡投影,将倒数最大服务成本归约为确定性精确预算分数路径;新提出的确定性舍入定理,将每条路径转化为整数分配,服务失真≤3,迁移代价≤分数迁移+6k。完整推导、舍入定理、因果组合与量化主定理均以Lean 4机器验证,唯一科学前提为正体结果。该定理仅针对上述分配模型,未包含网络拓扑、共享边拥塞或路由决策。
原文摘要 · Abstract (English)
Dynamic Mixture-of-Experts Serving allocates k replica GPUs among m experts as workloads change. At each round, the online algorithm sees the current workload, chooses integral replica counts, and pays bottleneck service cost plus replica movement. It does not know future workloads. Huang, Lou, and Xiao gave an O(sqrt(log k))-competitive randomized algorithm for this problem. We prove a deterministic O(1)-competitive algorithm. For every number of experts and every k>=1, the algorithm satisfies ALG_det <= 10 C_PB OPT + (5 C_PB + 8) k + 16, where C_PB is the absolute constant from Chasing Positive Bodies at resource augmentation one and covering sparsity two. Consequently, CR_det(k)<=10 C_PB for every k>=1, so CR_det(k)=Theta(1). The multiplicative factor does not depend on the number of experts, replica budget, horizon, or workload values. Thus randomization is not needed for the asymptotic guarantee. The proof has two layers. A finite tangent envelope, summable positive resets, and a nonexpansive balanced projection reduce reciprocal-max service costs to a deterministic exact-budget fractional path. A new deterministic rounding theorem converts every such path to integral allocations with service distortion three and movement bounded by the fractional movement plus 6k. The complete reduction, rounding theorem, causal composition, and quantified main theorem are machine-checked in Lean 4 relative to the positive-body result as the sole scientific source premise. The theorem concerns the allocation model above. It does not include network topology, shared-edge congestion, or routing decisions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。