# Tackling the Data-Parallel Load Balancing Bottleneck in LLM Serving: Practical Online Routing at Scale

arXiv: https://arxiv.org/abs/2605.06113 · HTML: https://mlsanity.com/paper/2605.06113/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Serving systems and request scheduling, one of 12 directions in Efficient LLM inference and serving.
- Builds on 20 of its 33 references that are in the map.
- First posted on arXiv 7 May 2026.

## Placed in

- Efficient LLM inference and serving / [Serving systems and request scheduling](https://mlsanity.com/inference/serving-systems-and-request-scheduling/)

## Builds on (most cited first, 20 of 20)

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity](https://mlsanity.com/paper/2101.03961/) (2021)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [SGLang: Efficient Execution of Structured Language Model Programs](https://mlsanity.com/paper/2312.07104/) (2023)
- [DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving](https://mlsanity.com/paper/2401.09670/) (2024)
- [Splitwise: Efficient generative LLM inference using phase splitting](https://mlsanity.com/paper/2311.18677/) (2023)
- [Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve](https://mlsanity.com/paper/2403.02310/) (2024)
- [Fast Distributed Inference Serving for Large Language Models](https://mlsanity.com/paper/2305.05920/) (2023)
- [DynamoLLM: Designing LLM Inference Clusters for Performance and Energy Efficiency](https://mlsanity.com/paper/2408.00741/) (2024)
- [Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline](https://mlsanity.com/paper/2305.13144/) (2023)
- [Efficient LLM Scheduling by Learning to Rank](https://mlsanity.com/paper/2408.15792/) (2024)
- [Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction](https://mlsanity.com/paper/2404.08509/) (2024)
- [Don't Stop Me Now: Embedding Based Scheduling for LLMs](https://mlsanity.com/paper/2410.01035/) (2024)
- [Online Scheduling for LLM Inference with KV Cache Constraints](https://mlsanity.com/paper/2502.07115/) (2025)
- [Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraints](https://mlsanity.com/paper/2504.11320/) (2025)
- [Quantifying the Energy Consumption and Carbon Emissions of LLM Inference via Simulations](https://mlsanity.com/paper/2507.11417/) (2025)
- [Adaptively Robust LLM Inference Optimization under Prediction Uncertainty](https://mlsanity.com/paper/2508.14544/) (2025)
- [A Universal Load Balancing Principle and Its Application to Large Language Model Serving](https://mlsanity.com/paper/2601.17855/) (2026)
- [LLM Serving Optimization with Variable Prefill and Decode Lengths](https://mlsanity.com/paper/2508.06133/) (2025)
- [Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics](https://mlsanity.com/paper/2605.01280/) (2026)

## Abstract (arXiv)

Data-parallel (DP) load balancing has emerged as a first-order bottleneck in large-scale LLM serving. When a model is sharded across devices via tensor parallelism (TP) or expert parallelism (EP) and replicated across many DP workers, every decode step ends in a synchronization barrier whose latency is set by the most heavily loaded worker; even modest persistent imbalance across DP workers compounds, step after step, into a substantial fraction of wasted compute. The problem is hard for reasons specific to LLM decoding: assignments are sticky (migrating KV caches has a high cost), per-request loads grow over time, arrivals are non-stationary, and the router must decide within a sub-100,ms decode budget over hundreds of waiting requests and tens of workers. We present BalanceRoute, a family of practical online routing algorithms that target this bottleneck. The first, BR-0, requires no prediction infrastructure and uses a piecewise-linear F-score that captures the sharp asymmetry between admissions that fill safe margin and those that overflow into the envelope; a two-stage decomposition keeps per-step cost compatible with millisecond-scale scheduling. The second, BR-H, generalizes BR-0 with a short, constant lookahead H and a lightweight termination-classifier interface, extending the F-score to a horizon-discounted form. We deploy BalanceRoute on a 144-NPU cluster and evaluate against vLLM baselines on both a proprietary production trace and the public Azure-2024 trace. Across both workloads, BalanceRoute substantially reduces average DP imbalance and improves end-to-end serving throughput.