Serving · Queues, batches, KV pages
Scheduling and Memory
Continuous batching swaps finished sequences for waiting ones between decode iterations. A paged KV cache makes that possible without reserving one big, unbroken block of memory for every request.
Evidence & limits
- What the further reading establishes
- Scheduling at each iteration and choosing which requests to batch can use serving capacity more efficiently for generative models.
- What this lab runs
- With the same planned arrivals and resource limits, a fixed trace compares static membership with finishing, freeing pages, and admitting new work between iterations.
- What it does not prove
- These fixed numbers only explain this workload. The trace doesn't model scheduler overhead, fairness rules, kernels, or a distributed GPU cluster.
Dataset
Serving Workload
- Source
- Course-authored synthetic arrivals
- License
- Not separately licensed
- Size
- 9 requests · mixed prompt and output lengths
Further reading
- Orca: A Distributed Serving System for Transformer-Based Generative Models
Primary · Gyeong-In Yu et al. · 2022
Introduces iteration-level scheduling and selective batching for autoregressive model serving.
- PagedAttention and vLLM
Paper · Woosuk Kwon et al. · 2023
Shows how memory allocation and continuous batching affect each other when requests have different lengths.
- Taming Throughput-Latency Tradeoff with Sarathi-Serve
Paper · Amey Agrawal et al. · 2024
Uses chunked prefills and stall-free schedules to balance throughput against token latency.
Lesson progressRestoring progress…
- CodeRestoring
- ExperimentRestoring
- CheckRestoring
Summary
Static batches keep the same members. A regular batch keeps the same requests together until the longest sequence finishes. Short sequences stop producing useful tokens sooner, so their decode slots sit idle while other requests are still waiting.
Continuous batches change each round. Continuous batching checks membership after every decode iteration. Each active sequence moves ahead by at most one token. After that, completed requests are recorded, their KV pages are freed, and eligible work from the queue can join the next iteration.
Use pages for the KV cache. A request gets fixed-size pages as its saved keys and values grow. Ceiling division gives it enough room, and each request wastes fewer than one page of unused slots.
a · b · c activeWaitingdKV allocation11 pagesDecode rule≤ 1 token / active requestmembership fixed- 1a · b · c decoded waits
- 14a finishes; its slot idlesd still waits
- drainlongest sequence finishesnext batch can enter
- Iterations
- 116
- Utilization
- 61%
- P95 wait
- 19
membership per iteration- 1a · b · c decoded waits
- 14a → completed; pages releaseidentity retained
- 15d enters the freed slotnext iteration
- Iterations
- 88
- Utilization
- 86%
- P95 wait
- 7
Keep the result in perspective. The browser comparison uses the same arrivals and resource limits for both schedulers, so you're only comparing policy on one fixed workload. The 88-versus-116 iteration result does not prove that continuous batching always wins. Admission overhead, fairness, prefill interference, and the shape of the workload still matter in production.
Knowledge check
Implementation
Allocate enough KV pages when the token count is zero, exactly fills a page, or ends partway through one.
- Signature
def allocate_kv_pages(tokens, page_size=16):- Inputs
- tokens int ≥ 0, page_size positive int
- Returns
- {pages: int, capacity: int, wastedSlots: int}
- Rule
pages = ceil(tokens / page_size); capacity = pages × page_size- Example
33 tokens, page size 16 → 3 pages, capacity 48, wasted 15
Reference solution
Approach Allocate enough KV pages when the token count is zero, exactly fills a page, or ends partway through one.
def allocate_kv_pages(tokens, page_size=16): pages = (tokens + page_size - 1) // page_size capacity = pages * page_size return { "pages": pages, "capacity": capacity, "wastedSlots": capacity - tokens, }Build cache-page accounting and one scheduler iteration in Python, then compare latency and capacity use under the two policies.
Saved results
Results created after your saved code passes its checks
Saved results
Results created after your saved code passes its checks
The replay is course data. The validation result is tied to the code you saved and checked.
Loading…