Scheduling around reuse

Keep the CPU and GPU working together

Two questions are waiting. One needs only a 40-token suffix because its handbook is cached. The other needs a fresh 12,040-token prompt. Behind them, twenty users are already receiving answers. Picking the next batch is now more complicated than taking the first few requests from a queue.

The scheduler must reconcile reusable work, memory availability, prompt processing, ongoing decoding, and the time it spends making those decisions. Improving GPU kernels helps only when the next batch reaches the GPU promptly. Improving cache reuse helps only when the requests with reusable state get a useful opportunity to run.

Cache-aware ordering is a policy choice

A cache-aware schedulercache-aware schedulingOrdering waiting work using information about reusable cached state, while also respecting resource and priority constraints.See in glossary → uses information about retained prefixes when ordering waiting work. For example, longest-prefix-match ordering prefers requests with more reusable input. SGLang’s pinned scheduling-policy code includes longest-prefix-match, depth-first weighting, and first-come-first-served alternatives; these are distinct choices rather than synonyms for RadixAttention. Scheduling policies at v0.5.20

Imagine a queue containing questions about handbook A, handbook B, and handbook A again. If GPU capacity cannot keep both handbooks resident, alternating them can repeatedly discard and rebuild useful state. Processing related work together can reduce that churn. This is a cache locality problem: the order of otherwise valid computations changes how much reusable data survives between them.

But a very large cached prefix does not necessarily imply a short job. A request with 20,000 cached tokens and a 10,000-token suffix may still require more prompt work than a cold 100-token request. The cache match is one signal. A full estimate also needs uncached length, current resource demand, and the response-length uncertainty that remains after prefill.

Fairness is another constraint. If requests for handbook A arrive continuously, an ordering that always favors its warm prefix can make a cold request wait too long. The implementation’s priority rules and policy settings matter. We should evaluate waiting-time distributions alongside token hit rate, rather than assuming that maximum reuse is automatically the best user experience.

Admission is different from ordering

After selecting a promising request, the scheduler still has to fit it into the available memory and token budget. Ordering asks which request should be considered first? Admission asks can this request run safely with the requests already admitted?

A nearly complete cache hit can make prefill cheap while still reserving substantial decode state. The prefix itself occupies memory, and new output tokens will grow the request’s cache. The model’s weights, temporary buffers, cached inactive prefixes, and active sequences also compete for GPU memory.

This is why one tuning knob cannot express the whole scheduling problem. SGLang documents separate controls for memory allocation, running-request limits, and prefill chunk size. Their effects depend on the model and workload. Treat those settings as resource budgets to be measured, not universal “faster” switches. Hyperparameter tuning

A useful experiment holds the arrival trace fixed and changes one budget. If raising the running-request limit improves throughput but worsens long-tail token latency, the change has exposed a tradeoff. If it causes memory pressure or repeated retractions, the system may be spending more work recovering than it gains from concurrency.

Chunk the long prompt

The vLLM chapter on chunked prefill introduced the basic idea: divide a long prompt into smaller pieces so its processing does not occupy one uninterrupted step. SGLang also supports chunked prefill. The relevant question here is how chunk size interacts with scheduler overhead and cache reuse.

Suppose an 8,192-token uncached suffix is divided into four 2,048-token chunks. The engine has several opportunities to advance other work between those chunks, subject to the selected execution path. If 6,144 tokens are already reusable, only the remaining portion needs new prompt computation. The actual work budget should therefore reflect missing state rather than the original input length alone.

Smaller chunks generally reduce the longest prompt-processing step, but they also produce more scheduling rounds and can make GPU work less efficient. Some modes batch prefill and decode together; other configurations constrain how they are combined. A conceptual timeline is useful, provided it does not imply that every version and hardware backend implements the same mixing policy.

The CPU can become the exposed bottleneck

Before a GPU batch runs, the host may need to collect requests, match prefixes, update memory mappings, prepare metadata, and launch work. A simple loop performs that preparation, waits for the GPU, handles its outputs, and starts again.

If CPU preparation takes 3 milliseconds and GPU execution takes 10, a serial iteration takes 13 milliseconds. The GPU is productive for only ten of those thirteen. Reusing more prompt state or accelerating a kernel can make the GPU stage shorter, revealing the host overhead more sharply.

Overlap schedulingoverlap schedulingPreparing future batches on the CPU while current GPU work executes, with synchronization to preserve dependencies.See in glossary → arranges CPU preparation for a future batch while the current GPU batch is executing. SGLang’s v0.4 design discussion explains the motivation and its handling of dependencies between consecutive steps. The objective is to hide CPU work behind GPU work when possible. SGLang team, v0.4 scheduler

For a long pipeline of equally sized independent stages, an ideal steady-state interval approaches the larger of the CPU and GPU times. The first preparation and the final drain still cost time. Dependencies, synchronization, and changes in batch shape can reduce the overlap actually achieved. If CPU work takes longer than GPU execution, the GPU must still wait for it.

Try the pipeline

The widget models a fixed 8,192-token prompt with a simplified mixed batch. Each batch has CPU preparation, prompt work at 256 tokens per millisecond, and 4 milliseconds of decode work. These are teaching assumptions, not measured rates. It permits one batch of CPU lookahead and keeps GPU execution serialized.

With 2,048-token chunks and 3-millisecond CPU preparation, each GPU step lasts 12 milliseconds. Four sequential steps take 60 milliseconds. Overlap reduces the total to 51: three milliseconds to prepare the first batch, followed by four GPU steps. It does not make CPU work disappear; it moves most of that work off the exposed critical path.

Now increase CPU preparation to 16 milliseconds. The host takes longer than each GPU step, so GPU gaps appear again. Then reduce the chunk size. A shorter individual GPU step may improve opportunities for interactive progress while making CPU preparation a larger fraction of the pipeline. That is why both a latency trace and a total-throughput measurement are useful.

Dependencies still have to be respected

The next token of a request depends on the previous token. Overlap cannot violate that mathematical dependency. An engine can prepare metadata whose structure is known, retain placeholders for results that are not yet available, and resolve values when the necessary GPU work finishes. It must still synchronize before a dependent consumer uses those values.

Memory lifetime creates similar constraints. A CPU thread must not recycle or overwrite a buffer that an asynchronous GPU operation is reading. The pinned scheduler contains explicit streams, event coordination, and shared-buffer barriers. Those details are essential for correctness even though our two-lane visualization omits them. Scheduler at v0.5.20

Consequently, “zero-overhead scheduler” is a description of a performance goal and measured circumstances. It is not a claim that cache lookup, scheduling, and allocation consume no CPU cycles. It also does not mean that Python work is irrelevant on a deployment with a different model, larger batches, or slower host cores.

For the handbook assistant, a useful tuning order is to identify the bottleneck first. A poor hit rate suggests examining request structure and cache capacity. Long exposed host gaps suggest examining preparation and synchronization. Decode stalls during large prefills suggest examining chunking and, eventually, separating the stages. Each change addresses a different part of the request’s waiting time.

Sources and further reading

• SGLang scheduling-policy source: concrete request-ordering choices.
• SGLang scheduler source: admission, execution loops, and synchronization.
• Zero-overhead batch scheduler announcement: historical motivation and measurements.
• Tuning guide: current configuration guidance, checked September 24, 2026.