mlsanityData to 14 Oct 2026

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

arXiv 2605.06113 ↗First posted 7 May 2026cs.DCcited by 0

On the map: Efficient LLM inference and serving → Serving systems and request scheduling

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.

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.

Builds on

20 of 33 references.

Closest ancestors · 8

Same direction, newest first

  1. 2026Position: LLM Serving Needs Mathematical Optimization and Algorithmic Foundations, Not Just Heuristics2 May
  2. 2025LLM Serving Optimization with Variable Prefill and Decode Lengths8 Aug
  3. 2024Efficient LLM Scheduling by Learning to Rank28 Aug
  4. 2024Efficient Interactive LLM Serving with Proxy Model-based Sequence Length Prediction12 Apr
  5. 2024Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve4 Mar
  6. 2024DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving18 Jan
  7. 2023Response Length Perception and Sequence Scheduling: An LLM-Empowered LLM Inference Pipeline22 May
  8. 2023Fast Distributed Inference Serving for Large Language Models10 May

Other references · 12

  1. 2023Efficient Memory Management for Large Language Model Serving with PagedAttentioncited by 5,944
  2. 2021Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsitycited by 3,073
  3. 2019Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelismcited by 1,868
  4. 2023SGLang: Efficient Execution of Structured Language Model Programscited by 1,141
  5. 2023Splitwise: Efficient generative LLM inference using phase splittingcited by 558
  6. 2024DynamoLLM: Designing LLM Inference Clusters for Performance and Energy Efficiencycited by 112
  7. 2024Don't Stop Me Now: Embedding Based Scheduling for LLMscited by 35
  8. 2025Online Scheduling for LLM Inference with KV Cache Constraintscited by 19
  9. 2025Optimizing LLM Inference: Fluid-Guided Online Scheduling with Memory Constraintscited by 19
  10. 2025Quantifying the Energy Consumption and Carbon Emissions of LLM Inference via Simulationscited by 12
  11. 2025Adaptively Robust LLM Inference Optimization under Prediction Uncertaintycited by 10
  12. 2026A Universal Load Balancing Principle and Its Application to Large Language Model Servingcited by 8

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2026RouteBalance: Fused Model Routing and Load Balancing for Heterogeneous LLM Serving
  2. 2026Nitsum: Serving Tiered LLM Requests with Adaptive Tensor Parallelism
  3. 2026DualMap: Enabling Both Cache Affinity and Load Balancing for Distributed LLM Serving
  4. 2026Calibrate, Then Route: A Measured Study of Learned Request Routing for Disaggregated LLM Serving
  5. 2024Intelligent Router for LLM Workloads: Improving Performance Through Workload-Aware Load Balancing
  6. 2026CacheRoute: Planned Prefix-Affinity Routing for Large-Scale LLM Serving
  7. 2026FLYING SERVING: On-the-Fly Parallelism Switching for Large Language Model Serving
  8. 2025gLLM: Global Balanced Pipeline Parallelism System for Distributed LLM Serving with Token Throttling