The scheduler decides who runs. The memory manager decides who can run. In a modern serving engine, those two conversations happen every decode step, and the answers are entangled.

The scheduling loop

At a high level, a serving engine repeats this loop:

1. Admit. Look at waiting requests and available KV blocks. Choose a set to run.
2. Build the batch. Assemble prefill and decode work for this iteration.
3. Allocate. Reserve KV blocks for new tokens and new sequences.
4. Execute. Launch kernels for attention, MLP, sampling.
5. Append. Write new keys and values into the cache.
6. Emit. Detokenize and stream completed tokens.
7. Finish. Free blocks for completed requests and admit more.

Every step has a policy. Admission can be FIFO, priority, fair-share, or deadline-aware. Allocation can be contiguous, paged, or hierarchical. Preemption can swap to CPU, recompute, or reject. The engine’s behavior under load is the sum of these choices.

Paged allocation in practice

The KV cache is divided into fixed-size physical blocks. Each request has a block table. A logical block index maps to a physical block ID. The attention kernel receives the block table and gathers the right keys and values.

This design has several consequences:

• Allocation is incremental. A request gets blocks as it grows. It does not reserve its maximum context upfront.
• Free memory can be non-contiguous. The allocator can use any free block; the block table hides the layout.
• Sharing is possible. If two requests have the same prefix, their block tables can point at the same physical blocks. Reference counts track ownership.
• Preemption is feasible. Dropping a request’s blocks is a matter of updating tables, not moving a giant contiguous buffer.

The block size matters. A 16-token block is common. If sequences end at arbitrary lengths, the last block is partially wasted. The expected waste per sequence is roughly half a block. With millions of tokens in flight, that adds up, but it is far less than reserving the full context.

Prefix caching and the radix tree

Consider a chat product with a 3,000-token system prompt and tool definitions. Every request repeats that prefix. Without caching, every request pays 3,000 tokens of prefill. With caching, the first request pays it, and later requests reuse the KV blocks.

The engine needs a way to find the longest cached prefix for an incoming token sequence. A radix tree is a natural data structure: each edge is a token span, each node represents a shared prefix, and leaves represent cached sequences. SGLang’s RadixAttention popularized this design. vLLM’s automatic prefix caching uses a hash-based block index with similar goals.

Cache hits change the scheduling problem:

• A request with a long cached prefix needs less prefill compute, so it can start decoding sooner.
• A cache miss may force a full prefill, which can block the batch.
• Eviction policy decides which shared prefixes survive. LRU is common, but tenant fairness may require per-tenant quotas.
• Cache hits must be validated. A hash collision or stale entry would produce wrong outputs, so implementations use full block hashes and careful invalidation.

Prefix caching is one of the highest-leverage optimizations for RAG, agents and chat. It is also easy to overstate: if your prompts are unique, there is nothing to share.

Chunked prefill

A long prompt is a scheduling hazard. A 64K-token prefill can occupy the GPU for hundreds of milliseconds, during which every decoding request stalls. Users see a freeze in their token stream. This is often worse than a slightly slower first token for the long request.

Chunked prefill splits the prompt into chunks and schedules them alongside decode work. Instead of one giant prefill, the engine does:

• a chunk of prefill for request A,
• a decode step for the active batch,
• another chunk of prefill,
• another decode step,
• and so on.

The long request’s TTFT increases because its prefill is spread out. But other users’ ITL stays stable. Many engines expose a token budget per iteration, balancing prefill and decode work.

The policy question: how much prefill can run before decode latency suffers? Too little and long prompts starve; too much and every stream stutters. Measure ITL p99 under mixed workloads, not just average TTFT.

Preemption

When memory runs out, the scheduler has three options:

1. Reject the new request with an error or a retry hint. Simple, honest, bad for availability.
2. Swap the request’s KV blocks to CPU memory and restore them later. Saves GPU memory but adds PCIe traffic and latency.
3. Recompute the request later by discarding its cache and re-running prefill. Saves memory but wastes compute.

The right choice depends on the workload. A short request is cheap to recompute; a long one is expensive. Swap is attractive when CPU memory is plentiful and the request will resume soon. Rejection is sometimes the best signal to an upstream autoscaler, but it must be deliberate.

Preemption interacts with fairness. If a tenant’s requests are repeatedly preempted, their latency is effectively unbounded even though the system is “up.” Track preemption rates per tenant.

Fairness and isolation

A shared serving cluster needs a policy for contention. Options include:

• FIFO with per-tenant concurrency caps. Simple and predictable.
• Weighted fair queueing. Each tenant gets a share of capacity proportional to weight.
• Priority classes. Interactive traffic beats batch traffic.
• Deadline-aware scheduling. Requests with tighter SLOs are admitted first, subject to starvation controls.

Without isolation, one tenant with long prompts can consume most of the KV cache and starve everyone else. This is not a hypothetical: a single retry loop or a bulk import can do it.

What the engine exposes

A good engine gives operators visibility into:

• running and waiting request counts,
• KV blocks used, free and cached,
• prefix-cache hit rate,
• preemption and recompute counts,
• TTFT and ITL histograms,
• per-model, per-tenant token throughput and cost.

These are not just dashboards. They are inputs to autoscaling and admission control. If you scale on GPU utilization alone, you will be late. Scale on queue depth, TTFT and cache pressure.

A worked policy

Suppose you run a multi-tenant chat service with three traffic classes:

• Interactive: p95 TTFT < 700 ms, p95 ITL < 60 ms.
• Agent: p95 TTFT < 2 s, p95 ITL < 120 ms, but many sequential calls.
• Batch: no latency SLO, minimize cost.

A reasonable policy:

• Reserve a baseline of KV capacity for interactive traffic.
• Give agent traffic a separate queue with a bounded share.
• Run batch work only when interactive queue depth is below a threshold.
• Enable prefix caching globally, but cap per-tenant cache share so one tenant cannot evict everyone else.
• Chunk prefill above 8K tokens to protect ITL.
• Preempt batch before interactive; swap rather than recompute for long contexts.

This is a design, not a universal answer. The point is that every clause corresponds to a measurable behavior. “Be fair” is not a policy until you define the metric and the enforcement.

Next: the kernels that actually execute this plan — fusion, FlashAttention, CUDA graphs, and why launch overhead can dominate a decode step.