Deadline-Aware Adaptive Prefill Chunking for Efficient Large Language Model Serving

1 Introduction

• A fixed chunk size cannot robustly balance interruption time, repeated launch overhead, prefill efficiency, and changing workload or SLO conditions.Small chunks limit interruptions but require more overhead-bearing iterations; large chunks amortize overhead but may violate active requests’ TPOT objectives.Source: §1 · p. 1
• SLOWEAVE admits the largest pending prefill chunk predicted to finish before the earliest active decode deadline.With no active decode, it uses a large cap to accelerate time-to-first-token.Source: §1 · p. 1
• The paper formulates chunk sizing as an online, deadline-constrained progress-maximization problem and gives an adaptive algorithm.Source: §1 · p. 1
• Under a monotone cost model, the method establishes per-iteration safety and maximality and discusses margins for prediction error.Source: §1 · p. 1

• The GPU runtime evaluation spans four request distributions, three TPOT targets, multiple accelerator and model configurations, and static baselines.Source: §3 · p. 2
• The event-driven simulator study is accompanied by its simulator, cost parameters, workload generator, raw runs, and aggregation code.Source: §3 · p. 2
• The evaluation pairs reproducible scheduling trends from simulation with hardware-specific effects measured in runtime experiments.Source: §3 · p. 2

2.1 Iteration-level LLM serving

• Continuous batching and improved KV-cache and attention systems increase serving capacity, but do not decide how much prefill work to mix into latency-sensitive decode iterations.Continuous batching admits and retires sequences between decode iterations.Source: §2.1 · p. 2
• Iteration duration is modeled as T over the active decode set and admitted prefill tokens, with a cost function nondecreasing in both arguments.The model may be a profiled lookup table, fitted regressor, or conservative analytical model; only monotonicity in chunk size is required.Source: §2.1 · p. 2

2.2 Why one chunk size is insufficient

• A fixed chunk can leave latency slack unused with a small decode batch yet exceed the token deadline as the batch grows or the TPOT target tightens.Source: §2.2 · p. 2
• Smaller chunks repeat per-iteration overhead across a prompt, potentially reducing throughput and worsening TTFT despite short individual iterations.The resulting optimum depends on the TPOT target and arrival pressure, motivating decisions from live scheduler state.Source: §2.2 · p. 2

3.1 Deadline model

• Each active request's next-token deadline is its most recent token completion time plus the TPOT objective.The scheduler uses the earliest remaining slack to constrain the iteration budget.Source: §3.1 · p. 2

3.2 Adaptive chunk selection

• SLOWEAVE selects the largest deadline-safe prefill chunk per iteration, using monotonicity for an O(log Cmax) search.The chunk is bounded by the earliest waiting prefill's remaining length; if no positive chunk fits, the scheduler runs decode only.Source: §3.2 · p. 2

3.3 Safety and maximality

• When decode-only cost is feasible and the cost model is exact and nondecreasing, the selected chunk meets every active deadline and maximizes prefill progress.With bounded one-sided prediction error, a prediction margin preserves the guarantee.Source: §3.3 · p. 3

3.4 Queueing, fairness, and overload

• Under sustained overload, strict TPOT objectives can leave no safe prefill budget; admission control and bounded deadline exceptions are offered as production controls.The aging threshold's violations are recorded explicitly as SLO exceptions.Source: §3.4 · p. 3

3.5 Heterogeneous SLOs

• Request-specific deadlines and prediction margins let the controller protect a 10 ms stream while using residual slack for a 50 ms batch request, without global chunk-size retuning.Chunk sizing is separate from queue selection; the safety argument for active decodes remains unchanged across queue disciplines.Source: §3.5 · pp. 3–4, §3.4 · p. 3

4.1 Simulator

• The event-driven simulator models each iteration as decoding one token per active request and optionally processing one prefill chunk.Its exposed default cost model uses fixed scheduler/kernel overhead and linear decode-batch and prefill terms as a transparent monotone model.Source: §4.1 · p. 4

4.2 Workloads and SLOs

• Each run generates 1,000 requests; interarrival times are exponential except for bursty traffic, which alternates between high- and low-rate states, and TPOT SLOs are swept at 10, 25, and 50 ms.Source: §4.2 · p. 4

4.3 Baselines and metrics

• Comparisons include full-prompt prefill, fixed chunks of 64, 256, and 1,024 tokens, and SLOWEAVE; goodput requires meeting both TTFT and within-request P99 TPOT SLOs.Policies share oldest-first queueing and the same continuous decode batch.Source: §4.3 · p. 4

4.4 Statistical protocol

• Metrics are aggregated within each run and averaged over five seeds, with identical request traces for policies and raw per-seed rows retained in the artifact.The protocol avoids treating millions of correlated token gaps as independent observations.Source: §4.4 · p. 4

5.1 Integration design

• The scheduler uses a profiled cost table indexed by decode batch, cached context, and candidate prefill tokens; the executor receives the selected chunk through ordinary sequence metadata.The profiler records P50 and P99 durations and enforces monotonicity along the chunk dimension; normal operation uses P99 estimates.Source: §5.1 · p. 5

5.2 Measurement protocol

• Trials use 8×A100-80GB and 8×H100-80GB nodes, multiple model configurations, five-minute warm-ups, and ten-minute measured windows.Each configuration is repeated five times with matched traces; power and request timestamps are collected.Source: §5.2 · p. 5

5.3 GPU results

• The GPU results report end-to-end latency, throughput, SLO attainment, goodput, and energy efficiency; Figure 3 summarizes measured goodput across GPU and workload configurations.Goodput is the primary endpoint under joint TTFT/TPOT SLOs.Source: Figure 3 · p. 5, §5.3 · p. 5, §5.2 · p. 5

6.1 Main comparison

• SLOWEAVE matches the other policies on chat and improves bursty goodput by 9%, with both SLOs met for 88.6% of requests.The chat case is described as one where full prefill and Fixed-1024 behave similarly to SLOWEAVE.Source: §6.1 · pp. 5–6, Table 3 · p. 6
• 59.0 vs 42.4 requests/s on mixed traffic (39%); 25.4 vs 18.4 requests/s on long-context traffic (38%) over Fixed-1024.On mixed traffic the comparator is the strongest fixed baseline; Table 3 reports mean results at the 25 ms TPOT SLO.Source: §6.1 · p. 5, Table 3 · p. 6

6.2 Changing the token-latency objective

• At 50 ms on mixed traffic, full prefill and SLOWEAVE are effectively tied at 60.5 and 60.4 requests/s; the controller recovers full prefill when prompts fit the slack.The controller therefore interpolates between conservative chunking and full prefill rather than introducing a separate operating regime.Source: §6.2 · p. 6
• At 10 ms, SLOWEAVE reaches 35.7 vs 10.7 requests/s on mixed traffic (3.3×) and 16.2 vs 6.6 requests/s on long traffic (2.4×).The strongest static policy is selected separately for each workload and TPOT target.Source: Table 4 · p. 6, §6.2 · p. 6

6.3 Where the gain comes from

• SLOWEAVE increases chunks when few sequences decode and decreases them as the decode batch grows, using slack for prefill while keeping iterations near the deadline.Fixed-256 and Fixed-1024 finish substantially earlier than the 25 ms target on all workloads, leaving spare slack unrecovered without retuning.Source: §6.3 · pp. 6–7, Figure 4 · p. 7

6.4 Cost-model calibration

• A deployment can profile T(n, c), enforce monotonicity, and interpolate measured points; reprofiling after kernel or accelerator changes updates chunk choices without retuning a policy constant.Evaluating prediction margins under real kernel variance is left to the hardware integration described in Section 5.Source: §6.4 · p. 7

LLM serving

• Serving systems address scheduling, batching, preemption, bursty arrivals, memory constraints, structured generation, and request migration; SLOWEAVE is orthogonal because it controls prefill admission within an iteration.Examples include Orca, vLLM, FastServe, AlpaServe, FlexGen, SGLang, DeepSpeed-FastGen, and Llumnix.Source: §7 · p. 7

Separating prefill and decode

• Phase separation can avoid same-device prefill–decode interference but incurs KV transfer and separate capacity planning; SLOWEAVE instead addresses colocated execution and can control quanta within a prefill pool.Related approaches also reorganize phase execution and KV-cache placement.Source: §7 · p. 7

Efficient kernels and benchmarking

• Kernel and attention methods change the shape of T(n, c), but do not remove the scheduler’s need to choose a safe prefill amount; goodput reflects coupled TTFT–TPOT objectives.General inference benchmarks emphasize scenario-specific latency and throughput rather than a single speed number.Source: §7 · pp. 7–8

8 Conclusion

• SLOWEAVE admits the largest prefill chunk that fits before the earliest active token deadline, replacing the static compromise between prompt progress and decode latency.The method has a local safety and maximality guarantee under an accurate monotone cost model.Source: §8 · p. 8
• Reproducible simulation and GPU measurements show substantial goodput gains on mixed, long-context, and bursty workloads, especially under strict token-latency targets.The runtime results demonstrate integration with iteration-level serving while preserving existing model kernels and KV-cache layout.Source: §8 · p. 8
• The controller adapts automatically to workload and SLO changes and integrates with iteration-level serving without changing model kernels or KV-cache layout.The conclusion describes the guarantee as local to the per-iteration decision.Source: §8 · p. 8

Limitations

• Real iteration costs can be non-smooth, and calibration drift across model and hardware updates needs broader deployment study.The runtime uses a profiled lookup-table predictor.Source: Limitations · p. 8
• The evaluation covers only a finite set of models, accelerators, workload traces, and SLO targets.Source: Limitations · p. 8
• The controller assumes a shared TPOT objective and one prefill chunk per iteration; multi-tenant starvation and admission control need separate study.Source: Limitations · p. 8
• Measurements omit preemption cost, KV transfer, multi-node KV transfer, and cross-region serving.Source: Limitations · p. 8