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

Paper

Deadline-Filling Prefill Chunks: SLOWeave — An Adaptive Chunking Scheduler for LLM Serving

TL;DR — Instead of a fixed prefill chunk size, we propose SLOWeave, an online scheduler that binary-searches for the “largest prefill chunk that finishes before the earliest decode deadline” at every iteration. Against the strongest fixed-chunk baseline it improves mixed-workload goodput by 39% and long-workload goodput by 38% at a 25 ms TPOT target, and pushes those gains to 3.3× and 2.4× respectively under the strict 10 ms target (source: Abstract).

Key Idea

When serving an LLM, prefill and decode have different cost structures. Prefill processes prompts in parallel and builds the KV cache, while decode reads that cache and generates tokens one at a time (source: §1). Mixing the two on the same GPU lets a long prefill delay the next-token generation of active decodes, producing noticeable pauses in streaming responses.

Existing chunked prefill splits prompts into pieces and interleaves them with decode, but the chunk size is usually fixed (source: §1). SLOWeave’s core idea is simple: dynamically adapt the chunk size to the current deadline slack at every iteration. Make it small to protect decode latency, make it large to capture prefill efficiency, but always cap it so the chunk finishes within the next-token deadline of active requests.

In one sentence: “Whereas a fixed chunk captures only one side of the tradeoff between deadlines and slack, SLOWeave guarantees — in provable form — a local maximality property: given an accurate cost model, it maximizes prefill progress among all deadline-satisfying choices.”

Background: The Problem They Solve

The Chronic Ailment of Prefill–Decode Interference

In iteration-level serving, each iteration has active requests generate one decode token with prefill work interleaved in between. The problem is the tradeoff introduced by the chunk size control variable (source: §1, §2.2):

• Small chunks: decode interruption is short so latency is preserved, but the prompt must be split into $\lceil L/C \rceil$ pieces, paying the scheduling/kernel-launch overhead once per piece (source: §2.2).
• Large chunks: amortize overhead and produce the first token (TTFT) quickly, but cause latency spikes that break the TPOT (Time Per Output Token) target of active requests (source: §1).

The key insight the authors stress is that the right chunk size is not a “fixed point” but a conditional optimum (source: §2.2):

Here $n$ is the decode batch size, $L$ the prompt length, $D$ the TPOT target, $T$ the iteration cost function, and $\lambda$ the arrival pressure. Static tuning captures only a single point of this space. Moreover, tightening the TPOT SLO from 25 ms to 10 ms pushes the same fixed chunk past its deadline even when the workload does not change at all (source: §2.2).

The SOTA as the Authors See It

Serving-systems research has advanced greatly on the capacity side: Orca’s iteration-level scheduling, vLLM’s PagedAttention (removing KV cache fragmentation), and IO-aware kernels like FlashAttention and FlashInfer (source: §7). But the authors’ diagnosis is clear: these improvements do not decide how much prefill work to mix into latency-sensitive decode iterations (source: §2.1). There are also disaggregation approaches such as DistServe and Splitwise that physically separate prefill and decode, but they require KV-transfer costs and separate capacity planning (source: §7). SLOWeave targets this gap — the problem of controlling the prefill allowance on the same device at iteration granularity.

The New Approach: SLOWeave

Deadline Model

Let $\ell_i$ be the completion time of the last token of active request $i$ (or its prefill completion time if it just finished prefill). Given the TPOT target $D$, the next-token deadline is simply:

At scheduler time $s_t$, the iteration budget is the earliest remaining slack:

When there are no active decodes ($A_t = \varnothing$), there is no deadline constraint, so the implementation-defined maximum chunk $C_{\max}$ can be used to speed up TTFT (source: §3.1).

Adaptive Chunk Selection

For a non-empty active set, SLOWeave picks the largest integer chunk satisfying the following (source: Eq. (1), §3.2):

Here $L_t$ is the remaining length of the oldest waiting prefill and $T(n,c)$ is the iteration cost function. Thanks to monotonicity, this maximization is solved by binary search with $O(\log C_{\max})$ cost-model queries (source: §3.2, Alg. 1). The key point is that $T$ only needs to be monotone in $c$, not of any specific functional form — a profiled lookup table, a regression model, or an analytic approximation all work (source: §2.1).

Safety and Maximality (Proposition)

The theorem the authors prove is clean (source: §3.3, Proposition 1):

Theorem. Assume $T(n,c)$ predicts the next iteration time exactly and is non-decreasing in $c$. If $T(|A_t|, 0) \le B_t$, then the chunk chosen by Eq. (1) (i) finishes before the next-token deadline of every active request and (ii) processes at least as many prefill tokens as any other deadline-safe chunk in that iteration.

The proof is the definition itself: by construction $T(|A_t|, c_t^\star) \le B_t$, and since $B_t \le d_i - s_t$, (i) holds; if a safe chunk with $c' > c_t^\star$ existed, it would contradict the definition of maximality, so (ii) holds (source: §3.3).

For prediction error, leaving a margin $\delta(n,c)$ and checking $\widehat T(n,c) + \delta(n,c) \le B_t$ keeps the same theorem as long as the one-sided prediction error is bounded by $\delta$. In practice, quantile regression or P99 residual tables provide that margin (source: §3.3).

How It Works: A Concrete Walkthrough

Below is the decision flow the scheduler makes in one iteration:

  flowchart TD
    A[Active decodes A_t<br/>Waiting prefill P] --> B{Is P empty?}
    B -- Yes --> Z[Decode-only iteration<br/>c = 0]
    B -- No --> C{Is A_t empty?}
    C -- Yes --> Z2[Max-chunk prefill<br/>c = min(C_max, L)]
    C -- No --> D[Compute budget<br/>B = min_i d_i - s]
    D --> E[Binary search<br/>largest c with T(n, c) + margin <= B]
    E --> F[Prefill c tokens +<br/>decode 1 token concurrently]

Filling the Deadline, in Numbers

The monotone cost model the authors’ simulator uses by default looks like this (source: §4.1):

• Constant $0.35$ ms: scheduler/kernel overhead
• $0.90 + 0.055n$: decode batch work (linear)
• $0.40 + 0.006c$: prefill work (linear)

Let’s trace through a toy example. Say the TPOT target is $D = 25$ ms, the current decode batch is $n = 4$, and the budget left until the earliest deadline is $B_t = 10$ ms. The decode-only cost is:

$B_t = 10$ ms is plenty, so there is room to mix in prefill. Binary search finds the largest $c$ with $T(4, c) \le 10$. For $c = 1000$:

There is still slack, so it grows further. For $c = 1400$:

It exceeds the deadline, so it is infeasible. It converges near $c \approx 1350$. Fixed chunk 1024 leaves this slack on the table, and fixed chunk 2048 blows past it. SLOWeave is the only policy that fills the remaining slack right up to the deadline.

The story changes when the decode batch grows to 40. At $T(40, 0) = 0.35 + 3.10 = 3.45$ ms, each prefill token adds another $0.006$ ms. At the same $B_t = 10$ ms the chunk that fits becomes much smaller, and under extreme overload it automatically falls back to decode-only iterations (source: §3.2, Alg. 1).

Complexity and Integration Surface

• A direct implementation is one active-set scan plus binary search → $O(|A| + \log C_{\max})$ per iteration; keeping the earliest deadline in a heap gives $O(\log |A| + \log C_{\max})$ (source: §3.2).
• In a vLLM-style runtime, SLOWeave is invoked “after active sequence groups are formed, before token budget allocation”; all it does is turn the existing token budget from a fixed value into an upper bound. PagedAttention and the model kernels are semantically untouched (source: §5.1, Fig. 1, Tab. 1).

Performance Validation: Key Results

Simulation — The Main Comparison at 25 ms TPOT

Across 4 workloads (chat/mixed/long/bursty) × 5 seed average, the goodput (req/s) at a 25 ms TPOT target is as follows (source: Tab. 3, Fig. 4):

The corresponding joint SLO attainment rate (percentage of requests satisfying both TTFT and within-request P99 TPOT simultaneously, %) is (source: Fig. 4):

Three observations stand out:

1. Chat is a tie. Prompts are short (median 256 tokens, source: §4.2), so unconstrained full prefill already fits within the deadline and adaptivity creates no penalty (source: §6.1).
2. Mixed shows the complete collapse of full prefill. Full has a lower P99 TTFT than Fixed-1024 (1364 vs 2101 ms) but a P99 TPOT of 48.5 ms that blows past the 25 ms target, so only 6.9% of requests satisfy both SLOs. SLOWeave draws on the slack between these two failure modes (source: §6.1, Tab. 3).
3. In Long, Fixed-256’s TTFT exceeds 20 seconds. It holds TPOT but keeps paying iteration overhead, so the first token explodes. Full is effectively wiped out (0.1%) with a P99 TPOT of 61 ms (source: §6.1, Tab. 3).

The Gap Widens as the TPOT Target Tightens

Without re-tuning the policy at all, only switching the target among 10/25/50 ms, SLOWeave’s goodput expressed as a multiple of the “strongest static policy chosen per workload and target” is (source: Tab. 4, Fig. 4):

Two structures emerge. First, the stricter the target, the more the fixed-chunk weakness is amplified — at 10 ms, Fixed-1024 “cannot shrink” and its goodput collapses to 1.06 req/s, while SLOWeave delivers 35.7 req/s (source: §6.2). Second, at 50 ms Mixed it ties full prefill (60.5 vs 60.4 req/s), because when a full prompt fits within the slack, Eq. (1) naturally converges to full prefill. In other words, SLOWeave interpolates between “conservative chunking ↔ full prefill” without a separate operating mode (source: §6.2).

GPU Runtime — It Holds on Real Hardware

End-to-end results measured on a single node with 8×A100-80GB / 8×H100-80GB (goodput req/s, SLO attainment rate in parentheses, source: Tab. 2, Fig. 3):

Worth noting is that energy efficiency improves too. Measured in joules per SLO-satisfying request, on A100/8B mixed it drops from Default’s 18.7 J/served request to SLOWeave’s 12.4 J/served request (source: Tab. 2). On 70B-TP8 long it goes from 92.6 to 58.5 J/served request. As compute that misses the deadline and is discarded (or retried) shrinks, energy per served request improves.

Where Does the Gain Come From?

Two combined effects are at play (source: §6.3): (1) when decode is light, grow the chunk to amortize the fixed 0.4 ms prefill overhead; (2) when the decode batch grows, shrink the chunk to pin the combined iteration to the deadline. A fixed chunk captures at best one side of this tradeoff. In Tab. 3, the P99 TPOT of Fixed-256/1024 stays well below 25 ms on every workload, whereas SLOWeave pushes mixed/long up to around 25 ms, converting that slack into earlier prefill completion and goodput (source: §6.3).

Our Take: Strengths, Limitations, and Why This Work Matters

Strength — “Narrow, but Provable”

SLOWeave’s greatest virtue is its deliberate narrowness. It changes neither the model weights, nor the attention kernels, nor the KV cache layout (source: §1, Fig. 1). It can be attached by merely reinterpreting the token budget of an existing runtime as an upper bound, and it is orthogonal to disaggregation, model parallelism, and memory management (source: §7). On top of that, it layers a local safety and maximality theorem, proving “why it is safe” with a single monotone cost model rather than a heuristic. For an engineer, this combination — minimal change surface plus a correctness guarantee — substantially lowers the barrier to adoption in practice.

Second, it cares strongly about reproducibility and independence. The simulator, cost parameters, workload generators, raw runs, and aggregation code are released together, so hardware-dependent effects and scheduling trends can be validated separately (source: §1, §5.2). The statistics protocol is honest too: it avoids the “false precision” of treating millions of correlated token intervals as independent observations, reporting seed means after request-level aggregation instead (source: §4.4).

Limitations — What the Authors Admit, and What We See

The authors explicitly acknowledge the following (source: Limitations):

• The evaluation is limited to a finite set of models, accelerators, traces, and SLO targets. Real iteration costs can be non-smooth due to kernel boundaries, TP communication, memory pressure, and prefix-cache hits, and research on drift correction for these is lacking.
• The current controller assumes a shared TPOT target plus one prefill per iteration. Multi-tenant priority is backed by the earliest-deadline formulation, but starvation and admission control need separate study.
• Preemption costs and KV transfer are not modeled, and multi-node KV transfer and cross-region serving were not measured.

We can add three potential concerns. First, everything hinges on the quality of the cost predictor $\widehat T$. The theorem is a conditional statement that holds “when the prediction is accurate”. How well a monotone P99 lookup table captures abrupt kernel transitions on real hardware — as the paper itself admits — is the most fragile point (source: §5.2, Limitations). Second, joint optimization of the TTFT and TPOT SLOs implicitly converges to “goodput maximization”, but the one-prefill-per-iteration limit can deprioritize TTFT when the prefill queue is long (oldest-request-first selection mitigates this, though it is not a fundamental fix) (source: §3.4, §3.5). Third, starvation under overload is an openly acknowledged gap. A work-conserving policy cannot satisfy arbitrary arrival rates and deadlines simultaneously, and the paper offers a compromise that allows “bounded deadline violation” via an aging threshold while logging it as an explicit SLO exception (source: §3.4). That is honest, but in real operations the moment such an exception becomes visible to users, the very notion of an SLO starts to wobble.

Why This Work Matters

LLM serving has shifted its axis from “how fast tokens can be produced” to “how many, while meeting SLOs”. Yet most systems research has focused on growing capacity — larger batches, faster kernels, better memory — while the fine-grained control variable of “how much prefill to mix into a single iteration” stayed a fixed constant. SLOWeave elevates this variable to a first-class control variable, and shows that it can be optimized with a single binary search and that the optimality is provable. The paper’s contribution is providing an isolation experiment demonstrating that “adaptive chunk sizing” has value as an independent serving primitive (source: Abstract, §6.3).

What’s Next?: The Road Ahead

The authors sketch three broad directions (source: Limitations, §3.4, §3.5):

1. Hardening cost prediction — first priority goes to corrections that capture the non-smoothness from kernel boundaries, TP communication, and prefix-cache hits, plus quantifying drift as models and hardware update.
2. Heterogeneous SLO and multi-tenant extension — the paper already argues that using a per-request $D_i$ lets a single shared controller protect 10 ms interactive streams and 50 ms batch requests alike (source: §3.5). Demonstrating this and refining the design of priority-aware prediction margins $\delta_i$ is the natural follow-up.
3. Multi-prefill knapsack — today it is one prefill per iteration, but extending Eq. (1) to vectors turns it into a small knapsack problem. The authors’ remark (§3.3) that first-fit can keep the log search is a practical hint.

A direction we would add is combining with admission control. Even if SLOWeave guarantees “maximal progress within the deadline,” no policy is safe once the arrival rate itself exceeds the acceptance limit (source: §3.2). So the joint design of an iteration-level controller (SLOWeave) plus a request-level admission controller is a promising next step — for instance, research that closes the existing proposal (§3.4) of rejecting/redirecting arrivals when the predicted decode-only cost approaches $D$, using reinforcement learning or online optimization. Alongside that, an evaluation methodology that views TTFT and TPOT as a Pareto surface rather than a single scalar goodput would also be valuable. Today goodput is a binary verdict on whether both SLOs were met, but a continuous metric that reflects how closely the deadline was missed could expose finer differences between policies.

Tables from the paper

Tables converted mechanically from the arXiv e-print LaTeX source. The numbers are the paper’s own and did not pass through a model.

Table 1. Implementation surface for an iteration-level GPU runtime.

Table 2. Measured GPU runtime results. Latencies are P99 values, and a request contributes to goodput only when it satisfies both the TTFT\xspace and TPOT\xspace SLOs.

Table 3. Mean results over five seeds at the 25 ms TPOT\xspace SLO. Latencies are milliseconds and goodput is requests/s. The best fixed baseline depends on the workload; SLOWeave\xspace matches the easy chat case and leads on mixed, long, and bursty traffic.

Table 4. SLOWeave\xspace goodput relative to the strongest static policy separately selected for each workload and TPOT\xspace target.