Source-linked AI summary
FlowPrefill: Decoupling Preemption from Prefill Scheduling Granularity to Mitigate Head-of-Line Blocking in LLM Serving
Chia-chi Hsieh, Zan Zong, Xinyang Chen, Jianjiang Li, Jidong Zhai, Lijie Wen
TL;DR
Heterogeneous LLM workloads make prefill-phase HoL blocking and TTFT SLO attainment difficult, while fixed chunking trades responsiveness against efficiency and scheduling overhead. FlowPrefill decouples preemption granularity from scheduling frequency through operator-level preemption and event-driven scheduling. On real-world production traces, it sustains 4.7×–5.6× higher request rates than DistServe at the same SLO guarantee.
Problem
Prefill-phase HoL blocking from long requests makes heterogeneous TTFT SLO attainment difficult in LLM serving.
Method
FlowPrefill decouples preemption granularity from scheduling frequency using operator-level preemption and event-driven scheduling.
Results
4.7×–5.6× higher request rates than DistServe are sustained at the same SLO guarantee on real-world production traces.
Takeaways & Limitations
FlowPrefill provides a goodput-oriented foundation for multi-SLO LLM serving while mitigating prefill-induced HoL blocking.
Takeaways & Limitations
FlowPrefill requires TTFT prediction for slack calculation and SLO-aware batching, using a polynomial fitted to offline prefill profiles.
Abstract
from arXiv · showhide
The growing demand for large language models (LLMs) requires serving systems to handle many concurrent requests with diverse service level objectives (SLOs). This exacerbates head-of-line (HoL) blocking during the compute-intensive prefill phase, where long-running requests monopolize resources and delay higher-priority ones, leading to widespread time-to-first-token (TTFT) SLO violations. While chunked prefill enables interruptibility, it introduces an inherent trade-off between responsiveness and throughput: reducing chunk size improves response latency but degrades computational efficiency, whereas increasing chunk size maximizes throughput but exacerbates blocking. This necessitates an adaptive preemption mechanism. However, dynamically balancing execution granularity against scheduling overheads remains a key challenge. In this paper, we propose FlowPrefill, a TTFT-goodput-optimized serving system that resolves this conflict by decoupling preemption granularity from scheduling frequency. To achieve adaptive prefill scheduling, FlowPrefill introduces two key innovations: 1) Operator-Level Preemption, which leverages operator boundaries to enable fine-grained execution interruption without the efficiency loss associated with fixed small chunking; and 2) Event-Driven Scheduling, which triggers scheduling decisions only upon request arrival or completion events, thereby supporting efficient preemption responsiveness while minimizing control-plane overhead. Evaluation on real-world production traces shows that FlowPrefill improves maximum goodput by up to 5.6$\times$ compared to state-of-the-art systems while satisfying heterogeneous SLOs.
1 Introduction
FlowPrefill addresses prefill-phase HoL blocking in heterogeneous LLM serving by decoupling preemption granularity from scheduling frequency. Its operator-level preemption and event-driven scheduling improve responsiveness and goodput under diverse SLOs.
- Motivation: Diverse workloads require serving systems to meet heterogeneous latency SLOs while maximizing goodput.Goodput is defined as the maximum sustainable request rate under an SLO attainment goal.
- Motivation: Long prefill computations can delay incoming high-priority requests, causing queuing delays and TTFT SLO violations.Existing scheduling approaches do not fully address HoL blocking caused by long prefill computations.
- Challenges: Fixed execution granularity creates a trade-off: finer granularity improves responsiveness but increases execution and control-plane overhead.Coarser granularity worsens blocking, while frequent scheduling checks add unnecessary overhead.
- FlowPrefill: FlowPrefill uses operator-level preemption to interrupt execution at operator boundaries and event-driven scheduling triggered by request arrivals or completions.This decouples preemption from scheduling granularity while supporting SLO-aware prioritization.
- Evaluation: Up to 5.6× higher goodput than baselines and 3.1× tighter SLOs are achieved on real-world production traces.The evaluation includes systems such as DistServe and vLLM.
2 Background
Transformer inference separates compute-bound parallel prefill from memory-bound autoregressive decoding. Although PD disaggregation removes interference between phases, it concentrates prefill contention and leaves long requests able to cause HoL blocking.
- Transformer Inference: Transformer inference consists of stacked layers containing self-attention mechanisms and feed-forward networks.A prompt is processed in parallel during prefill to initialize the KV cache and predict the first subsequent token.
- Transformer Inference: During decoding, generated tokens are appended autoregressively and processed iteratively until termination.The predicted token is appended to the sequence before the next iteration.
- Resource Demands: Prefill is compute-bound because it processes all input tokens in parallel using GEMMs, whereas decode is memory-bound because it uses autoregressive GEMVs.Prefill reuses model weights across tokens, while decode repeatedly fetches weights from HBM.
- Disaggregated Serving: PD disaggregation places prefill and decode on separate GPU instances, eliminating interference from compute-intensive prefill bursts on decode latency.The architecture separates the two workloads spatially.
- HoL Blocking: A single long-context request can monopolize a prefill GPU for hundreds of milliseconds, delaying subsequent requests and threatening diverse TTFT SLOs.Disaggregation shifts contention entirely to prefill instances.
3 Motivation
Fixed chunking exposes a conflict between preemption responsiveness, computational efficiency, and scheduling overhead. Batching is beneficial for short requests but can inflate latency and SLO risk for long requests.
- Motivation: The motivation experiments characterize bounds from preemption granularity and workload asymmetries in prefill batching.The experiments were conducted on an NVIDIA A100-SXM.
- Preemption Granularity v.s. Efficiency: Fixed chunking mitigates HoL blocking through chunk-boundary preemption but reducing granularity creates a conflict between responsiveness, efficiency, and scheduling overhead.Chunked Prefill and Layered Prefill use fixed chunking strategies for long inputs.
- Preemption Granularity v.s. Efficiency: Excessively small execution units degrade hardware efficiency through redundant memory accesses and kernel-launch overheads.Coupling scheduling decisions to these boundaries also creates unnecessary control-plane overhead.
- Workload Asymmetry in Prefill Batching: For short requests, increasing batch size rapidly improves throughput before saturation while latency grows only modestly.Batching multiple short requests helps saturate GPU parallelism while maintaining SLO compliance.
- Workload Asymmetry in Prefill Batching: For long requests, batching provides minimal throughput gains but causes linear latency inflation and increases TTFT SLO-violation risk.Long requests can saturate the GPU individually, limiting the benefit of larger batches.
4 Overview
FlowPrefill is a goodput-oriented serving architecture that decouples preemption from scheduling granularity to mitigate prefill HoL blocking. It concentrates its optimizations in prefill instances while retaining separate decode instances.
- Overview: FlowPrefill enables timely preemption without sacrificing throughput by decoupling preemption from scheduling granularity.The design targets the responsiveness-throughput trade-off created by fixed granularity.
- System Architecture: The system comprises a Proxy, Prefill Instances, and Decode Instances, with primary optimizations concentrated in the prefill instances.Each prefill instance contains a Request Queue, Execution Pool, and Scheduler.
- System Architecture: The Request Queue tracks request states for admission control and scheduling, while the Execution Pool runs the selected work.Completed requests return results to the Proxy and are removed from the queue.
- System Architecture: Decode instances reuse native execution logic and schedule decode requests with first-come-first-served policy.The design and evaluation focus exclusively on the prefill phase.
5 Method
FlowPrefill combines operator-level cooperative preemption with event-driven, SLO-aware scheduling to decouple interruption granularity from scheduling frequency. It prioritizes requests using slack-aware deadlines, batches compatible work, and preempts running executions when events warrant.
- 5.1 Operator-Level Preemption: Operator-level preemption interrupts execution after core operators complete, avoiding request splitting while preserving kernel semantics and throughput.FlowPrefill inserts lightweight checks between operators such as qkv_proj, attn, o_proj, gate_up_proj, and down_proj.
- 5.1 Operator-Level Preemption: Cooperative preemption waits for the current operator to finish before safely suspending execution after a scheduler signal.The scheduler signals the execution pool and waits for an acknowledgment rather than interrupting execution immediately.
- 5.2 Event-Driven Scheduling: Event-driven scheduling makes decisions only on request arrival or completion events, reducing the overhead of frequent scheduling checks.This decouples scheduling decisions from execution granularity while supporting timely responses to high-priority requests.
- 5.2 Event-Driven Scheduling: S-EDF assigns priority using deadline and slack, with predicted TTFT informing whether requests can still meet their SLOs.Requests with the earliest deadline and non-negative slack receive the highest priority, while infeasible requests can be proactively deprioritized.
- 5.2 Event-Driven Scheduling: SLO-aware batching admits compatible requests when the highest-priority request’s remaining time can accommodate predicted batch latency and the token budget is not exceeded.Algorithm 2 ranks all requests, selects the highest-priority request, attempts compatible batching, and then checks whether the running execution should be preempted.
- 5.2 Event-Driven Scheduling: FlowPrefill’s example uses arrival events to submit a low-priority request, then preempt it and submit a higher-priority request when the latter arrives.The example covers submit, preempt, and resume control commands for two requests with different priorities.
6 Evaluation
Evaluation on QwenTrace and additional compatibility studies show that FlowPrefill sustains higher goodput, supports tighter SLOs, and reduces preemption blocking while preserving efficiency across serving settings and model types.
- End-to-End Performance: 4.7×–5.6× higher request rates than DistServe are sustained by FlowPrefill across three models on QwenTrace.It also outperforms DistServe-CP2K and DistServe-CP8K by up to 2.0× and 4.5×, respectively.
- Scheduling Ablations: SLO-aware batching and S-EDF maintain higher performance under high load by selecting deadline-feasible batches and deprioritizing requests unlikely to meet their SLOs.These mechanisms prevent sharp drops in SLO attainment as request rates increase.
- End-to-End Performance: FlowPrefill supports 1.5×–2.3× tighter SLOs than DistServe-CP2K and 2.1×–3.1× tighter SLOs than DistServe-CP8K.The comparison uses fixed request rates and scaled latency requirements.
- Runtime Analysis: 3.5×–4.2× lower average preemption blocking time than layer-level preemption is achieved with all observed latencies below 4.5 ms.Operator-level preemption therefore provides near non-blocking interruption for high-priority requests.
- Runtime Analysis: FlowPrefill maintains high SLO attainment with throughput comparable to the baseline, indicating that operator-level preemption preserves responsiveness without measurable efficiency loss.The study reports that lightweight operator-boundary checks avoid the frequent scheduling interventions required by chunk- and layer-level scheduling.
- System Compatibility: FlowPrefill improves TBT SLO attainment by up to 1.6× under PD-colocation and achieves up to 1.6× higher goodput and 2.4× tighter SLO attainment on an MoE model.The operator-level design extends to MoE gate and expert operators.
7 Related Work
Prior LLM serving systems improve execution efficiency, batching, memory management, or phase scheduling, while chunked and layer-level approaches address HoL blocking with coarse preemption. FlowPrefill instead targets severe prefill-induced HoL blocking through fine-grained preemption and efficient scheduling.
- Aggregated LLM Serving Systems: Earlier systems optimize performance within unified execution models using continuous batching, fine-grained KV-cache management, or decode-prefill interleaving.These approaches include Orca, vLLM, and SARATHI.
- Preemption-Based Scheduling: Chunked-prefill approaches combine coarse-grained preemption with EDF-style prioritization to reduce HoL blocking from long requests.Their primary mechanism is prioritization around chunk boundaries.
- Preemption-Based Scheduling: FlowPrefill directly addresses severe long-prefill HoL blocking through fine-grained preemption and efficient scheduling.This distinguishes it from approaches relying primarily on prioritization and coarse-grained interruption.
8 Conclusion
FlowPrefill mitigates prefill-induced HoL blocking under heterogeneous SLOs by decoupling preemption granularity from scheduling frequency. On production traces, it achieves substantially higher request rates at the same SLO guarantee while preserving execution efficiency.
- Conclusion: FlowPrefill combines operator-level preemption with event-driven scheduling to achieve near non-blocking responsiveness without sacrificing execution efficiency.The system is designed for goodput-oriented online LLM serving under heterogeneous SLO requirements.
- Conclusion: 4.7×–5.6× higher request rates than DistServe are sustained at the same SLO guarantee on real-world production traces.The conclusion also reports substantial latency improvement compared with vLLM.