Chunked Prefill: Smoothing Out Your Tail Latency

In large language model (LLM) serving, the most common source of operational instability is not throughput, but tail latency. For Site Reliability Engineers (SREs) and ML engineers, a p99 latency spike is often more damaging than a slightly lower average throughput because it violates Service Level Objectives (SLAs) and causes cascading timeouts in downstream systems. The root cause of these spikes is often head-of-line (HoL) blocking in the inference scheduler. Chunked prefill is the architectural solution that decouples the heavy computation of processing input prompts from the generation of output tokens, effectively smoothing out the latency distribution.

The Head-of-Line Blocking Problem

To understand chunked prefill, we must first look at the traditional inference loop. An LLM inference request has two distinct phases: prefill and decode.

1. Prefill: The model processes the entire input prompt (the context window) in parallel to generate the first output token. This is compute-intensive but completes quickly relative to generation.
2. Decode: The model generates subsequent tokens one by one (autoregressively). Each token generation depends on the previous one, making it inherently sequential and memory-bound.

In a naive scheduler, a request occupies a GPU memory block (a "block" or "sequence") for its entire lifetime. If a long prompt arrives while a short request is in the decode phase, the scheduler must wait. The long prefill computation blocks the GPU resources, delaying the decode step for the short request. This is classic head-of-line blocking.

Consider a scenario with two requests:

• Request A: A 10-token summary task.
• Request B: A 10,000-token document analysis task.

If Request A starts decoding while Request B is still prefilling, Request A’s decode step is delayed until Request B’s prefill completes. If many such long requests arrive, the p99 latency for short, simple requests can skyrocket because they are stuck behind the "long tail" of prefill computations.

How Chunked Prefill Works

Chunked prefill solves this by breaking the prefill phase into smaller, schedulable units. Instead of treating a 10,000-token prompt as a single atomic operation that blocks the GPU, the scheduler splits it into chunks (e.g., 256 tokens per chunk).

The mechanism operates as follows:

1. Chunking: The input prompt is divided into fixed-size chunks.
2. Interleaved Scheduling: In each scheduling step, the GPU computes both:
   • Decode steps: Generating the next token for active requests.
   • Prefill chunks: Processing a chunk of a new request’s prompt.
3. Continuous Pipeline: As long as there is compute budget, the scheduler fills the remaining capacity with prefill chunks from waiting requests.

This allows the system to make progress on the decode phase of Request A even while Request B is still being preprocessed. The key insight is that prefill and decode can run concurrently on the same batch, provided the scheduler manages the KV cache correctly.

Reducing Tail Latency

The primary benefit of chunked prefill is the reduction of p99 latency. By allowing short decode requests to proceed without waiting for long prefill requests to complete, the scheduler ensures that all requests receive regular GPU time slices.

Smoothing the Latency Distribution

Without chunked prefill, the latency distribution is bimodal:

• Short requests have low latency but high variance due to HoL blocking.
• Long requests have high latency and high variance due to their size.

With chunked prefill, the latency distribution becomes more uniform. Short requests are no longer penalized by long prefill tasks. The p99 latency drops because the worst-case delay (waiting for a massive prefill) is amortized across multiple scheduling steps.

Worked Scenario

Imagine a server with a batch size of 8.

• Requests 1–7: In the decode phase, each generating one token.
• Request 8: A new, long prompt arriving.

Without Chunked Prefill: The scheduler cannot start Request 8’s prefill until Requests 1–7 complete their current decode steps. If Requests 1–7 are slow (e.g., due to memory bandwidth limits), Request 8 waits. If another long request arrives, it waits for Request 8. This creates a queue where long requests block the pipeline.

With Chunked Prefill: The scheduler allocates compute to Requests 1–7 for their decode steps. Simultaneously, it allocates remaining compute to Process Chunk 1 of Request 8. As soon as Chunk 1 is done, the scheduler moves to Chunk 2 of Request 8 and the next decode step for Requests 1–7. This ensures that no request starves, and the overall throughput remains high while latency variance decreases.

Trade-offs and Complexity

Chunked prefill is not free. It introduces several engineering trade-offs:

1. Memory Fragmentation: Splitting prompts into chunks can lead to inefficient KV cache usage if not managed carefully. Systems like vLLM use PagedAttention to mitigate this by allocating memory in fixed-sized blocks, but the scheduler must track which chunks belong to which sequences.
2. Scheduler Complexity: The llm scheduling logic must now handle partial completions. It needs to track the state of each chunk and ensure that the final chunk of a prompt is processed before the first decode step begins. This adds overhead to the control plane.
3. Compute Overhead: There is a small overhead in managing the chunking logic and ensuring that the KV cache is updated correctly between chunks. However, this is typically negligible compared to the GPU compute cost.

Conclusion

Chunked prefill is a critical optimization for modern LLM serving systems. By decoupling the prefill and decode phases, it eliminates head-of-line blocking and smooths out tail latency. For ML engineers and SREs, this means more predictable SLAs, higher effective throughput, and a more robust system under variable load. While it introduces complexity in memory management and scheduling, the benefits in latency consistency make it an essential performance optimization for production-grade LLM inference.

The shift from atomic prefill to chunked prefill represents a fundamental change in how we view inference workloads: not as monolithic tasks, but as pipelines that can be interleaved for maximum efficiency.