Head-of-Line Blocking in LLM Serving and Why Chunked Prefill Isn't Enough

Why Head-of-Line Blocking Happens in LLM Serving, and Why Chunked Prefill Isn't a Complete Solution

When a single long prefill request stalls the entire batch for hundreds of milliseconds, the motivation behind Chunked Prefill becomes obvious. But what if you enable Chunked Prefill and p99 latency goes up instead? The culprit is usually one of three things: a poorly chosen chunk size, accumulated FlashAttention inefficiency from mixed batches, or increased KV cache fragmentation pressure causing frequent preemptions.

Head-of-Line Blocking: How a Long Prefill Monopolizes the GPU Step

Every iteration in LLM serving follows a simple pattern: the scheduler assembles a batch, the GPU processes it, and the next iteration begins. The problem is the extreme difference in compute cost between prefill and decode.

Prefill processes all input tokens in a single pass. A 4096-token request occupies an entire GPU step with its attention computation. On an A100 80GB with Llama-3-8B, that step takes 200–400 ms. Decode generates one token per request per step, coming in at 5–15 ms per step.

Orca (Yu et al., 2022) introduced iteration-level scheduling and established continuous batching, but the long-prefill problem remained under FCFS-based schedulers. When a 4096-token prefill enters the batch, all 32 decode requests sit idle for that entire step. One request monopolizing the GPU for 300 ms causes TPOT (Time Per Output Token) to spike across the entire batch — that's Head-of-Line Blocking.

Non-FCFS schedulers don't solve this easily either. Preemption-based schedulers interrupt an in-progress prefill and process decodes first, but preemption requires swapping out or discarding the request's KV cache. That means recomputation costs. Under workloads with many long requests, back-to-back preemptions cause throughput to drop sharply.

How Chunked Prefill Works and Its Intended Trade-offs

Sarathi-Serve (Agrawal et al., 2023) takes a different approach. With chunk_size=512, a 4096-token prefill is split into 8 chunks, and each step combines one prefill chunk with the current decode requests. The authors call this "Decode-Maximal Batching."

The intended trade-off is clear: shorter individual steps (300 ms → ~30 ms) mean decode requests get scheduled more frequently, stabilizing TPOT. The cost is that the full prefill now spans 8 steps, so TTFT (Time To First Token) increases.

TTFT_chunked ≈ (N_tokens / chunk_size) × T_chunk_step
TPOT_spike   ≈ T_chunk_step       (with chunking)
TPOT_spike   ≈ T_prefill_step     (without chunking — tens of times larger)

Measured results from the Sarathi paper: on LLaMA-13B on an A6000, decode throughput improves up to 10×, E2E throughput 1.33×. On LLaMA-33B on A100, decode throughput improves 4.25× and E2E 1.25×.

Three Conditions Where Chunked Prefill Fails

Chunks that are too small accumulate kernel launch overhead

The FlashAttention kernel needs enough tokens to fully utilize GPU SMs. Drop to chunk_size=64 and attention computation overhead grows 3×, total prefill time 5×. These numbers come from direct measurements in CompactAttention (2025). Launching a kernel per chunk, reloading that chunk's KV data, then moving to the next chunk — this loop actually reduces GPU utilization.

This is why vLLM raised the default from 512 (v0.4.2) to 2048 (v0.8.2). Small chunks hit a point where kernel launch overhead exceeds compute cost, and throughput degrades.

FlashAttention shape inefficiency in mixed prefill+decode batches

FlashAttention fills SMs efficiently when the Q sequence length is uniform and large. Mixing a prefill chunk (Q length 512) with decode requests (Q length 1) in the same batch produces wildly mismatched Q shapes in the attention computation. This mismatch disrupts FlashAttention's tile-size optimization and lowers SM utilization. Furthermore, as the number of splits increases, memory bandwidth contention between prefill CTAs and decode CTAs intensifies.

Microsoft Research's POD-Attention (ASPLOS 2025) directly addresses this by separating the two phases of attention computation in mixed prefill+decode batches and processing them in parallel. The fact that this paper exists is itself evidence that mixed-batch inefficiency is not negligible.

KV cache block fragmentation increases

vLLM's PagedAttention manages the KV cache in fixed-size blocks (16 tokens by default). Splitting prefill into chunks means KV cache is allocated incrementally across multiple steps for a single request. If chunk_size isn't an exact multiple of the block size, each chunk introduces internal fragmentation in the last block. With many concurrent requests and fine-grained chunking, eviction pressure rises, and when preemption occurs, throughput inverts.

TTFT, TPOT, and p99 Trends by chunk_size

Combining the vLLM documentation with Sarathi experimental results, the following trends emerge for Llama-3-8B on A100 80GB with mixed-length workloads.

The high p99 at chunk_size=256 seems counterintuitive — smaller chunks should let decodes run more often. But kernel launch overhead and frequent KV cache allocations lower the overall processing rate, pushing p99 up. "Smaller chunks are better" breaks down here.

# Balanced TTFT/TPOT — mixed workloads
vllm serve meta-llama/Meta-Llama-3-8B \
    --enable-chunked-prefill \
    --max-num-batched-tokens 2048

# Maximize throughput — batch-oriented workloads
vllm serve meta-llama/Meta-Llama-3-8B \
    --enable-chunked-prefill \
    --max-num-batched-tokens 8192

In vLLM V1 (0.8.x and later), chunked prefill is enabled by default. If --max-num-batched-tokens is not specified, the default is 2048.

Scheduler Policy and Chunked Prefill

Chunked Prefill reduces HoL blocking by equalizing step lengths, but it can't be considered in isolation from scheduler policy. vLLM's chunked prefill scheduler uses a Decode-Maximal approach: fill the batch with decode requests first, then use the remaining token budget (max_num_batched_tokens) to add prefill chunks. This isn't plain FCFS with chunks bolted on — the priority ordering itself changes.

Preemption-based schedulers provide stronger HoL control but carry KV cache swap costs. In practice, the Chunked Prefill + Decode-Maximal Batching combination has lower overhead than preemption alone. Preemption is better treated as a safety net — useful for cases where even a large chunk_size leaves certain extreme requests (very long inputs with a small chunk budget) stuck in the batch too long.

Choosing chunk_size Based on Workload Characteristics

Three factors drive the decision: input length distribution, SLO type, and model size.

Workloads with short inputs (under 512 tokens) aren't prefill-bound to begin with. Enabling Chunked Prefill has minimal effect, and lowering chunk_size only adds kernel overhead. Set --max-num-batched-tokens high, or skip chunked prefill entirely.

If TTFT matters — real-time dialogue, for instance — use a larger chunk_size to complete prefills quickly. If TPOT matters — streaming responses or code generation — stay at 2048 or below and interleave decodes frequently.

Model size matters too. For 70B+ models, the decode step itself is heavy, so a single prefill chunk has relatively little impact on TPOT. For 8B and smaller models, decode is light and each chunk hits harder — smaller chunk sizes, 2048 or below, are warranted.

The "p99 went up" scenario almost always comes from running defaults without accounting for these three factors. Either fragmentation pressure triggers frequent preemptions, chunk_size is too small and kernel overhead compounds, or FlashAttention inefficiency in mixed batches erodes throughput. No single setting is the problem — the regression happens when all three conditions interact at once.