Load Balancing with Evolving Workloads in Large-Scale Language Model Serving

Serving large language models requires assigning requests whose workloads grow during processing and whose completion times are unknown. With a synchronization barrier, lightly loaded workers wait for the slowest worker at every decode iteration. We model this loss through aggregate workload imbalance and formulate a joint admission and assignment problem with sticky requests and capacity limits. Short lookahead incorporates predicted completions of ongoing requests. For exact optimization without lookahead, we prove a comparison under independent geometric decode lengths, bounded independent nondegenerate prompt sizes, and batched releases satisfying a cumulative supply condition. The long-run expected imbalance improvement over first come, first served admission with request-count join-shortest-queue grows at least as the square root of the product of worker capacity and the logarithm of worker count, in the stated scaling regime. The comparison extends to capacity-aware round robin, random routing, and power of two choices. BalanceRoute approximations connect the formulation to practical routing. Experiments using up to 144 NPUs with proprietary and public traces show lower workload spread and higher throughput than the evaluated baselines. These empirical results complement the guarantee for exact optimization.