Serving large language models at scale is complicated by the fact that requests do not have fixed costs: their workloads expand during decoding, and completion times are unknown. When a synchronization barrier forces lightly loaded workers to wait for the slowest worker each iteration, this imbalance directly translates into wasted capacity. A new paper on arXiv formalizes this loss as aggregate workload imbalance and proposes a joint admission and assignment problem that accounts for "sticky" requests and capacity limits.

The authors introduce a short lookahead mechanism that uses predicted completions of ongoing requests to make better routing decisions. For the exact optimization without lookahead, they prove a theoretical guarantee: under independent geometric decode lengths, bounded 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 the number of workers. The comparison also extends to capacity-aware round robin, random routing, and power-of-two-choices.

To make the approach practical, the authors develop BalanceRoute approximations that connect the formulation to real routing systems. Experiments using up to 144 NPUs with both proprietary and public traces show lower workload spread and higher throughput than the baselines, complementing the theoretical results. The work highlights the value of treating workload growth as a first-class concern in LLM serving infrastructure.