Multi-stage Flow Scheduling for LLM Serving

Yijun Sun, Xudong Liao, Songrun Xie, Hao Chen, Han Tian, Wenxue Li, Yiming Zhang, Kai Chen

Abstract

Meeting stringent Time-To-First-Token (TTFT) requirements is crucial for LLM applications. To improve efficiency, modern LLM serving systems adopt disaggregated architectures with diverse parallelisms, introducing complex multi-stage workflows involving reusable KV-block retrieval, collective communication, and P2D transfer. Flows from dependent stages overlap within and across requests on shared bottleneck links, making TTFT highly susceptible to network contention and necessitating stage-aware scheduling. Unfortunately, most existing works schedule flows in a stage-agnostic manner, leading to uncoordinated contention that constitutes a primary cause of SLO violations. In this paper, we present MFS, a holistic multi-stage flow scheduling mechanism designed to maximize TTFT SLO attainment. At its core, MFS approximates the Least-Laxity-First (LLF) scheduling policy without requiring precise knowledge of a request's remaining slack. It achieves this through a Defer-and-Promote principle implemented through a Reverse Multi-Level Queue (RMLQ) structure. By dynamically promoting task precedence as effective laxity diminishes, MFS prioritizes flows with less laxity while preventing requests with loose SLOs from prematurely consuming network bandwidth. We implement MFS as a pluggable module integrated into vLLM and evaluate it on a 32-GPU testbed. Our results demonstrate that MFS improves TTFT SLO attainment by 1.2x–2.4x.

The Challenge: Network Contention in Disaggregated LLMs

In modern Large Language Model (LLM) serving, performance is primarily measured by Time-To-First-Token (TTFT). To handle the computational demands of massive models, systems have moved toward "disaggregated" architectures. In these setups, the prefill phase (processing the input prompt) and the decode phase (generating subsequent tokens) are often handled by distinct GPU pools.

Generating that first token is not a single atomic operation but a three-stage relay race of network flows:

  1. KV-cache retrieval: Fetching previous conversation history from remote nodes to enable context reuse.
  2. Collective communication: Synchronizing data across GPUs during model execution (e.g., Expert Parallelism or Sequence Parallelism).
  3. Prefill-to-Decode (P2D) transfer: Sending the final activation results from prefill nodes to decoding nodes.
Figure 3: Multi-stage flows contending for bandwidth on bottleneck links in a spine-leaf topology.

Traditional data center networks treat these flows as independent entities. This leads to "traffic jams" where a non-urgent data transfer—such as a P2D transfer for a request with a distant deadline—blocks a critical synchronization step for an urgent request. This uncoordinated contention, occurring both within a single request and across multiple concurrent requests, is a primary driver of Service Level Objective (SLO) violations.

MFS: Multi-stage Flow Scheduling

To address these bottlenecks, we introduce MFS, a holistic scheduler that understands the dependencies between these stages. MFS operates on two core principles designed to manage network laxity effectively.

The Defer-and-Promote Principle

Instead of attempting to complete every network task as quickly as possible, MFS intentionally defers non-urgent transfers. For example, the final P2D stage can often be delayed slightly to save bandwidth for the "execution" stages (like collective communication) that would otherwise stall the GPU. This prevents requests with loose deadlines from prematurely consuming bandwidth at the expense of urgent ones.

Reverse Multi-Level Queue (RMLQ)

Traditional network schedulers often demote tasks as they consume more resources to ensure fairness. MFS does the opposite: it initializes flows in low-priority queues and promotes them to higher priority as their "laxity"—the remaining slack time before a deadline is missed—diminishes.

Figure 5: Visualization of intra-request and inter-request contention across different model layers and flow types.

To determine urgency without requiring perfect future knowledge, MFS utilizes two key metrics:

  • Minimal Link Utilization (MLU): For the final P2D stage, MFS calculates the exact bandwidth required to meet the deadline.
  • Relative Layer Index (RLI): For internal execution stages, MFS prioritizes flows based on the current neural network layer being processed. This ensures the "front of the line" always has the resources to move forward, exploiting the structural determinism of LLM inference.

Key Insights and Evaluation

A central insight of this work is that finishing a task "too early" in a congested network can be detrimental. If a request with a 500ms deadline finishes in 100ms, it likely hogged bandwidth that could have saved a different request from missing a 200ms deadline. MFS explicitly regulates this "earliness" to maximize overall system utility.

We evaluated MFS using production traces from Alibaba's Qwen workloads and the Mooncake dataset for long-context scenarios. Testing across architectures including Mixtral, DBRX, and Llama3, we observed:

  • SLO Improvement: MFS improved TTFT SLO attainment by 1.2× to 2.4× over state-of-the-art baselines like Fair Sharing and Shortest Job First (SJF).
  • Reduced GPU Stalls: The time GPUs spent waiting for network synchronization (Collective Completion Time) was reduced by up to 52%.
  • Increased Throughput: MFS allows serving systems to sustain 1.17× to 1.46× higher request rates while maintaining deadline compliance.

Conclusion

MFS demonstrates that by making the network "stage-aware," we can significantly improve the efficiency of disaggregated LLM serving. By coordinating flows based on their actual impact on the GPU execution pipeline and their proximity to deadlines, MFS resolves the uncoordinated contention that plagues modern AI infrastructure.

Summary updated

Abstract

Meeting stringent Time-To-First-Token (TTFT) requirements is crucial for LLM applications. To improve efficiency, modern LLM serving systems adopt disaggregated architectures with diverse parallelisms, introducing complex multi-stage workflows involving reusable KV-block retrieval, collective communication, and P2D transfer. Flows from dependent stages overlap within and across requests on shared bottleneck links, making TTFT highly susceptible to network contention and necessitating stage-aware scheduling. Unfortunately, most existing works schedule flows in a stage-agnostic manner, leading to uncoordinated contention that constitutes a primary cause of SLO violations. In this paper, we present MFS, a holistic multi-stage flow scheduling mechanism designed to maximize TTFT SLO attainment. At its core, MFS approximates the Least-Laxity-First (LLF) scheduling policy without requiring precise knowledge of a request's remaining slack. It achieves this through a Defer-and-Promote principle implemented through a Reverse Multi-Level Queue (RMLQ) structure. By dynamically promoting task precedence as effective laxity diminishes, MFS prioritizes flows with less laxity while preventing requests with loose SLOs from prematurely consuming network bandwidth. We implement MFS as a pluggable module integrated into vLLM, and evaluate it on a 8-server, 32-GPU testbed as well as through large-scale simulations. Our results demonstrate that MFS effectively outperforms state-of-the-art baselines, improving the TTFT SLO attainment by 1.2x--2.4x.
BibTeX
@misc{sun2026multi,
  author = {Yijun Sun and Xudong Liao and Songrun Xie and Hao Chen and Han Tian and Wenxue Li and Yiming Zhang and Kai Chen},
  title = {{Multi-stage Flow Scheduling for LLM Serving}},
  year = {2026},
  eprint = {2603.17456},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2603.17456},
}
Figure