Staggered Batch Scheduling: Co-optimizing Time-to-First-Token and Throughput for High-Efficiency LLM Inference

Abstract

As Large Language Model (LLM) inference scales to complex distributed architectures involving Data Parallelism (DP) and Expert Parallelism (EP), traditional immediate-dispatch scheduling mechanisms introduce significant inefficiencies. This paper proposes Staggered Batch Scheduling (SBS), a method that deliberately buffers requests to form optimal batches, thereby eliminating device-side queuing and "parallelization bubbles." Deployed on a production H800 cluster serving DeepSeek-V3, SBS achieves up to a 40% reduction in Time-to-First-Token (TTFT) and a 20% boost in system throughput.

Introduction

The deployment of massive Mixture-of-Experts (MoE) models, such as DeepSeek-V3, has necessitated a shift toward sophisticated serving architectures. Modern systems often employ Prefill/Decode (P/D) separation and hybrid parallelism strategies like DP+EP. However, traditional schedulers, designed for continuous service, often fail in these discrete batch-processing environments.

Expand

Source, p. 3

In these setups, immediate dispatch leads to Head-of-Line (HOL) blocking and synchronization-induced "bubbles," where faster GPUs remain idle while waiting for stragglers. This mismatch between continuous scheduling and discrete execution degrades both latency and throughput.

Methodology

Staggered Batch Scheduling (SBS) replaces immediate dispatch with a window-based allocation strategy, shifting the queue from the fragmented device side to the manageable scheduler side.

• Adaptive Interval Scheduling: Requests are buffered at the scheduler for a short, dynamic interval calculated from moving averages of execution times and network latency.
• Multi-tier State Synchronization: To prevent synchronization drift, SBS employs a triple-check protocol involving quiescence polling, asynchronous completion signaling, and safety watchdogs.
• Load-Aware Global Allocation: The buffering window allows the scheduler to perform global optimization. Using a "Water-Filling" bin-packing algorithm, SBS allocates requests at the chunk level, prioritizing capacity utilization.

Expand

Source, p. 4

• Dual-Objective Batched Decode: For the Decode phase, SBS uses an Interquartile Range (IQR) method to identify and mask memory-heavy outliers, balancing both compute load and KV cache footprint across DP units.

Results and Discussion

Evaluations were conducted on real-world production workloads using an NVIDIA H800 cluster serving DeepSeek-V3. The results demonstrate that SBS significantly outperforms state-of-the-art immediate-dispatch baselines:

• Latency: TTFT was reduced by 30% to 40% at sub-80% load levels.
• Throughput: Prefill phase QPS increased by 12.9% to 22.8%, while aggregate Decode throughput rose by approximately 15%.
• Efficiency: By eliminating parallelization bubbles, Prefill chunk utilization surged from ~52% to ~88%, effectively reclaiming wasted compute cycles.
• Stability: The IQR-aware strategy reduced KV cache load variance by 40%, successfully suppressing stragglers and preventing memory exhaustion outliers.

Conclusion

SBS demonstrates that deliberate delay in request dispatch can paradoxically accelerate overall processing by enabling global optimization. By aligning scheduling granularity with execution reality, SBS provides a scalable foundation for high-efficiency inference in next-generation MoE models. Future work will focus on further mitigating synchronization drift in highly volatile workload environments.