Batching, cache allocation, and queue discipline
How to study this lesson
Read one section, trace the worked example, and try the knowledge check. Bookmark saves a shortcut; notes appear in My notebook. Mark lesson complete is your own assessment and does not mark its lab passed.
By the end, you can
- Trace static and continuous batching on mixed-length requests.
- Explain paging and prefix reuse without equating them with free capacity.
- Design a load test that exposes queueing and tail latency.
Batching changes utilization and waiting
Batching processes multiple requests together so expensive model operations can serve more than one sequence. A fixed batch can waste work on padding or wait for its longest member to finish before admitting new requests. Continuous batching makes scheduling decisions as sequences complete, allowing waiting requests to join an active workload. Its benefit depends on implementation, arrival patterns, and memory availability, rather than on the name of the feature alone.
Consider three invented decode jobs requiring two, four, and one steps, with room for two active sequences. If the first two run as a fixed batch, the third begins after step four and finishes at step five. If a new job can occupy the slot freed at step two, the one-step job finishes at step three while the four-step job still finishes at step four. This trace isolates scheduling; real kernels do not necessarily take equal time at every batch size.
Prompt processing competes with token delivery
A long prefill can consume significant compute and interfere with decoding that is trying to deliver tokens at a steady pace. Chunked prefill divides prompt processing into pieces that can be scheduled with decode work. The vLLM optimization documentation describes this mechanism and its tuning tradeoffs. Smaller chunks can improve responsiveness for existing decodes while adding scheduling overhead or delaying completion of the long prompt.
Define which experience matters before tuning. An interactive chat may prioritize time to first token and smooth streaming; an overnight extraction job may prioritize completed records per hour. These are different optimization targets. A configuration that improves aggregate output tokens per second can still make a short request wait behind many long prefills. Keep per-request timestamps for queue entry, admission, first token, and completion so the source of a regression is visible.
Pages reduce allocation waste, not the information stored
PagedAttention organizes KV-cache storage in blocks that can be mapped to logical sequences without requiring one large contiguous allocation per request. The original research connects this design to reducing fragmentation and enabling sharing. Paging does not make a token's keys and values vanish. There is still block metadata, partial-block waste, and a total physical capacity limit.
With a hypothetical page size of 16 tokens, a 17-token allocation reserves two pages, or 32 token slots. Its 15 unused slots are internal waste until further tokens occupy them. A 31-token request also reserves 32 slots but wastes only one. Small pages reduce this type of waste while potentially increasing management overhead. Admission should reserve capacity using the actual allocation unit rather than dividing free bytes by a continuous per-token estimate and rounding down only at the end.
Reuse is conditional on compatible context
Prefix caching reuses already computed states for an identical compatible token prefix. It can reduce repeated prefill work for common instructions or documents. Reuse depends on tokenization, model and adapter identity, positional behavior, and cache-key correctness. Similar-looking prose is not automatically the same token prefix, and changing an early token generally invalidates reuse for subsequent positions. A reused prefix does not eliminate the cost of generating new output tokens.
Cache keys also belong to the security design. If the service handles multiple tenants, define whether reuse is allowed across their data and how authorization-sensitive context affects the key. Do not expose cached content merely because its numerical states match. Test cold and warm workloads separately, and report hit rate. A performance claim based entirely on a repeated prompt is not representative of a workload with mostly unique contexts.
Measure the queue, including its failures
As arrival rate approaches sustainable service capacity, waiting can grow rapidly even if average kernel time stays similar. Test a specified arrival process instead of sending the next request only after the previous one completes; the latter hides queue buildup. Record completed requests, timeouts, rejected requests, cancellation behavior, and latency percentiles with their sample sizes. For a streaming service, measure both first-token and completion latency.
Compare policies on the same request trace. First-come-first-served scheduling is simple but can delay short jobs behind long ones. Length-aware policies can improve average latency while starving long requests unless fairness is explicit. Set maximum waits, per-tenant budgets, and cancellation cleanup. A good serving experiment reports the quality and latency achieved at a particular accepted throughput, with all admission and failure behavior included, so the reader can judge whether the claimed capacity meets the actual product need.
Work through the code
This finite scheduling simulation assumes all jobs are ready initially and every decode step has equal cost regardless of active batch size. It demonstrates slot reuse, not GPU throughput. Add arrival times or a batch-size-dependent step cost to explore more realistic queue behavior.
from collections import deque
def simulate(jobs, slots):
waiting = deque(jobs)
active, finished = [], {}
limit = sum(length for _, length in jobs)
for tick in range(1, limit + 1):
while waiting and len(active) < slots:
active.append(waiting.popleft())
next_active = []
for name, remaining in active:
if remaining == 1:
finished[name] = tick
else:
next_active.append((name, remaining - 1))
active = next_active
if not active and not waiting:
break
return finished
jobs = [("a", 2), ("b", 4), ("c", 1)]
finished = simulate(jobs, slots=2)
for name in sorted(finished):
print(f"{name} finishes at step {finished[name]}")
print("simulation: one equal-cost step per active sequence")
a finishes at step 2 b finishes at step 4 c finishes at step 3 simulation: one equal-cost step per active sequence
Run Python snippets locally with the prerequisites named above. The module coding lab runs directly in your browser.
Pause and reason
A paged cache has a 16-token page size. Three requests reserve 17, 31, and 33 tokens. Compute reserved token slots and internal waste, then explain why allocating from the total 81 logical tokens would undercount.
Check your understanding
A benchmark repeats one long prompt and reports much better first-token latency after its first request. What information is essential for interpreting the result?
Your notes
Explain the mechanism in your own words. Add a failure you want to test.