LLM Serving Optimization with Variable Prefill and Decode Lengths
在固定 KV-cache 显存预算下研究异构 prefill/decode 长度的离线 LLM 服务调度：证明问题 NP-hard、FCFS/最短输出优先/总长度优先均有无界近似比；提出 Sorted-F 算法——用 F-metric（平均输出长度 / 批大小）平衡批并发与下游解码成本，证明常数因子近似比 ≤48；配三种 Phase-1 求解器（精确 DP、局部交换、分位贪心）与 LP 引导 / receding-horizon 变体。真实混合负载上相对 FCFS 提速 4.87×、相对 MC-SF 提速 2.09×，与 LP 下界差距仅 1.03-1.09×