IIntroduction to AI Systems Performance EngineeringTechnical textbook
Chapter 18: Request Scheduling and KV Cache Management
18.4

Chunked prefill and admission control

Limit long-prompt interference while preserving useful throughput

Before you begin

Follow a linked prerequisite when you cannot explain it from memory. Background skills without links are stated as abilities rather than hidden terminology.

  • Continuous batching
  • Prefill/decode regimes
  • Head-of-line blocking

One request with a 64,000-token prompt arrives while 24 requests are already receiving generated tokens from the 7-billion-parameter server. Scheduling the complete prompt as one prefill batch keeps the GPU busy efficiently, but active streams show a long gap before their next tokens. The request log reports a spike in inter-token delay at the same time that Nsight Systems shows the long prefill interval.

Divide the 64,000-token prompt into chunks of 1024 tokens and allow decode work between chunks. A scheduler log now shows 1024 prefill tokens followed by one-token advances for active requests. Inter-token delay falls, while total prompt-processing time can rise because smaller matrix shapes and extra scheduling boundaries reduce prefill efficiency. The measured trade gives meaning to chunked prefill.

A long prefill can occupy the GPU for many milliseconds or seconds, delaying every decode request that needs a regular token cadence. Processing the prompt in chunks creates scheduling points where decode or shorter prefill work can run. The trade is extra launches, repeated setup, and potentially less efficient attention or matrix shapes.

Chunking limits the maximum uninterrupted service quantum assigned to one prompt. A mixed iteration can also combine compute-oriented prefill work with bandwidth-oriented decode work, but the potential benefit depends on engine and kernel support. The scheduler chooses a token budget per iteration while the cache grows and attention semantics remain exact.

Current vLLM V1 documentation describes chunked prefill as enabled by default when possible, with decode work scheduled first and remaining token budget assigned to pending prefill. The documented behavior is version-specific. The stable concept is a policy that bounds prefill work per iteration and states which class receives priority.

Preserve attention semantics across chunks

A chunk processes a contiguous range of prompt positions. Its queries attend to all valid earlier positions: cached prefix tokens, tokens from completed chunks, and earlier positions within the current chunk. The engine writes K and V for the new range so the next chunk can continue without recomputing prior prompt positions.

The first chunk may begin after a prefix-cache hit. Its uncached range can start at a block boundary or inside a block, depending on the cache implementation. Later chunks append state. Cancellation between chunks should free uniquely owned blocks and release references to shared blocks without invalidating in-flight work.

Chunking changes query length and context length presented to attention kernels. The implementation needs kernels and graph variants that support those shapes efficiently. A token count that works well on one model or accelerator can produce an unfavorable matrix shape on another.

Select the token budget from latency and kernel scaling

Measure prefill duration for candidate chunk sizes at representative existing-context lengths and mixed-batch conditions. Small chunks create frequent scheduling points and protect decode cadence, but they add launches, metadata work, and smaller GEMMs. Large chunks approach monolithic prefill throughput while extending the time before active decodes can run again.

A decode-first policy can reserve one token for every selected active sequence, then fill the remaining budget with prefill tokens. The reservation protects inter-token latency under moderate load. Under sustained decode load, the remaining budget can become small and long prompts can starve. Add aging, a minimum prefill share, or a service-class guarantee when first-token progress has an objective.

The token budget is not equal to elapsed time. A prefill token, a decode token with a long context, and a multimodal encoder token can have different costs. A more accurate scheduler can use measured or predicted time, but prediction and policy overhead must remain below the iteration cadence.

Admit work using future cache and deadline demand

Before prefill starts, estimate prompt KV growth, maximum requested output, current free-block reserve, and deadline. Reserving the full maximum can underutilize memory, while reserving only the immediate chunk can admit more sequences than can safely generate. Use a bounded-risk policy and preserve enough blocks for already admitted sequences to make progress.

When capacity is insufficient, the service can defer the request, reject it with explicit overload semantics, route it to another pool, limit context under a declared policy, or preempt lower-priority work. Beginning a huge prefill and later discarding its partial KV wastes compute and can worsen overload.

Evaluate chunk size and admission together. Report TTFT by prompt length, TPOT for active decodes, input-token throughput, output-token goodput, preemptions, wasted prefill work, cache reserve, and rejection. A policy that protects decode by indefinitely delaying long prompts has not met a complete service contract.

Worked example: Setting a prefill token budget

An ongoing decode population needs iterations roughly every 60 ms. A 64,000-token prompt would take 1.8 seconds as one prefill.

  1. Measure prefill duration at candidate chunks such as 512, 2,048, and 8,192 tokens, including scheduling and cache overhead.
  2. Choose chunks whose execution leaves enough room to maintain decode cadence. A 2,048-token chunk taking 45 ms may fit; 8,192 at 170 ms violates it.
  3. Interleave chunks with decode and track the long request's TTFT. Too-small chunks may extend its completion through overhead and competition.
  4. Replay mixed traffic and inspect p99 TPOT, TTFT by prompt size, total input-token throughput, and cache reserve.

Conclusion: The 2,048-token candidate provides a scheduling point after about 45 ms and can preserve the 60 ms decode objective in this example. Smaller chunks may increase overhead; larger chunks violate decode cadence. Mixed-load replay must also verify that the long request continues to make bounded progress.

Common errors

  • Choosing chunk size from token count alone. Kernel duration depends on model, prior context, batch, and hardware.
  • Calling chunking free preemption. Partial KV remains resident and work already performed cannot always be moved cheaply.
  • Admitting prompts before checking worst-case cache growth. Partial progress can consume resources needed to recover stability.

Reference summary

Chunked prefill processes a long prompt in contiguous ranges and creates scheduling points between them. Decode work can run between chunks, while the completed prefix remains in KV. The attention computation for each chunk must include all earlier valid positions.

Small chunks improve scheduling responsiveness but add launches and smaller matrix shapes. Large chunks improve prompt throughput but extend decode interruption. Admission must also estimate future KV growth so partial long prompts do not consume the reserve needed by active sequences.

  • Reserve a decode budget to protect active streams.
  • Adapt prefill chunk size to load, prompt length, and hardware shape efficiency.
  • Reject, defer, or route requests before allocating scarce state when overload is inevitable.
  • Account for tenant priority and maximum context in admission decisions.
  • Measure wasted work from preempted or cancelled requests.

Knowledge check

How does chunk size move the system along a prefill-efficiency versus decode-latency frontier?

Show the answer guide
  • Smaller prefill chunks limit how long one prompt can occupy a scheduler iteration. Decode requests wait for a shorter interval, so their token gaps and often their tail latency improve.
  • Small chunks create smaller GEMMs and more scheduler iterations, launches, state transitions, and partial-attention work. Prompt throughput and time to first token for the long prompt can worsen because the GPU uses each chunk less efficiently.
  • Larger chunks improve matrix shape and amortize fixed overhead, so prefill tokens per second and completion time for the long prompt usually improve.
  • A large chunk can block ongoing decode for the duration of the chunk and consume more temporary memory. The selected point lies on a measured frontier between prefill efficiency and decode latency under a stated mixture of prompt and decode work.
Practice

Trace the chunked-prefill frontier

While 32 requests continuously decode from 2048-token contexts, admit one uncached 32768-token prompt. Repeat with prefill chunk sizes 128, 256, 512, 1024, 2048, 4096, and unchunked, using the same scheduler token budget and arrival trace. Record every scheduler iteration and the long prompt's progress.

Evidence to keep: Submit the server configuration and trace, a scheduler timeline for at least two chunk sizes, a table of prefill tokens per second, long-prompt TTFT, decode p50/p99 TPOT, iteration duration, and GPU utilization, plus a frontier plot. Select one chunk size under explicit latency constraints and explain the observed efficiency loss.

The scheduler now controls work and state. Quantization and speculation change the cost of the work itself and the number of target-model iterations needed for progress.

References

Sources and further reading

The lesson explanations synthesize primary papers and official references. Follow the originals for proofs, exact APIs, architecture details, and version-sensitive behavior.

  1. Orca: Iteration-Level Scheduling↗
  2. PagedAttention / vLLM↗
  3. SGLang↗
  4. NVIDIA Nsight Systems User Guide↗

    Official reference for capturing and reading CPU, CUDA API, GPU workload, and communication timelines.