M8-047M8: ML Systems, Engineering & ResearchCost & Latency OptimizationMedium
⚡Flashcard Drill➔Mastery:
Explain Batching Dynamics and Continuous Iteration-Level Scheduling: Throughput vs. Latency
🎯 Active Recall Self-Check (Draft First, Verify After)
Login-free practice tracker: recall core answer, audit pitfalls, and log review status.
Step 1 · Draft your concise answer & assumptions
Step 2 · Check Pitfalls & Follow-up Inquiries
📐 Mathematical Definition
⚡ One-Sentence Core Answer
Static batching increases throughput by amortizing memory-bound model weight transfers across requests at the expense of head-of-line queue blocking, whereas continuous (iteration-level) batching dynamically injects and evicts sequences at every decoding iteration, maximizing GPU saturation while slashing tail latency.
📌 Key Takeaways
- •Static batching trade-off: Amortizes memory weight loading over requests, but forces fast, short sequences to remain trapped waiting for the longest sequence (head-of-line blocking).
- •Continuous iteration-level batching: Evicts completed sequences and schedules newly arrived requests dynamically at every single autoregressive step.
- •Hardware synergy: Continuous batching strictly requires non-contiguous virtual memory management (PagedAttention) to prevent physical VRAM fragmentation.
📐 Mathematical Derivations
Batching Mechanics & Execution Scheduling:
(1) Why Batching Maximizes Throughput (Amortizing Memory Transfers):
- In autoregressive LLM decoding, generating a token requires reading all model parameters from high-bandwidth memory (HBM) to on-chip SRAM.
- For batch size , memory transfer cost is bytes for 1 token generated severe memory-bandwidth saturation.
- For batch size , reading the weights once serves concurrent tokens. Step execution duration scales as:
Because for moderate , per-token generation cost drops by nearly , drastically boosting aggregate token throughput (Tokens/sec).
(2) Why Static Batching Destroys Latency (Head-of-Line Blocking):
- The Flaw: An entire batch of sequences must run until the single longest sequence finishes generation ().
- Tail Bubbles: If Sequence 1 finishes at iteration 10 while Sequence 2 finishes at iteration 500, Sequence 1's memory sits locked and GPU compute slots run padded with zeros (idle waste) for 490 steps.
- Queuing Delay: Newly arriving queries must sit waiting in the queue until the entire legacy batch terminates.
(3) Continuous / Iteration-Level Batching (Orca / vLLM):
- Instead of scheduling at the request level, scheduling executes at the iteration step level:
- At step , the engine checks which sequences emitted an end-of-sequence token (
- Completed sequences are evicted immediately; their memory is reclaimed, and responses are returned to users.
- Newly arrived waiting requests are dynamically injected into the active batch slots.
- Result: Eliminates head-of-line blocking, maintains GPU utilization at near 100%, and cuts median user latency by .
(4) Chunked Prefill & Decode Colocation:
- A massive incoming prompt (e.g., 4096 tokens) monopolizes GPU compute during its prefill phase, stalling all active autoregressive decode sequences and causing massive TPOT latency spikes.
- Chunked Prefill partitions long prefills into chunks (e.g., 512 tokens), co-scheduling one prefill chunk alongside active decode iterations in the same batch step to maintain smooth inter-token latency SLAs.
(1) Why Batching Maximizes Throughput (Amortizing Memory Transfers):
- In autoregressive LLM decoding, generating a token requires reading all model parameters from high-bandwidth memory (HBM) to on-chip SRAM.
- For batch size , memory transfer cost is bytes for 1 token generated severe memory-bandwidth saturation.
- For batch size , reading the weights once serves concurrent tokens. Step execution duration scales as:
Because for moderate , per-token generation cost drops by nearly , drastically boosting aggregate token throughput (Tokens/sec).
(2) Why Static Batching Destroys Latency (Head-of-Line Blocking):
- The Flaw: An entire batch of sequences must run until the single longest sequence finishes generation ().
- Tail Bubbles: If Sequence 1 finishes at iteration 10 while Sequence 2 finishes at iteration 500, Sequence 1's memory sits locked and GPU compute slots run padded with zeros (idle waste) for 490 steps.
- Queuing Delay: Newly arriving queries must sit waiting in the queue until the entire legacy batch terminates.
(3) Continuous / Iteration-Level Batching (Orca / vLLM):
- Instead of scheduling at the request level, scheduling executes at the iteration step level:
- At step , the engine checks which sequences emitted an end-of-sequence token (
[EOS]) or reached max_tokens.- Completed sequences are evicted immediately; their memory is reclaimed, and responses are returned to users.
- Newly arrived waiting requests are dynamically injected into the active batch slots.
- Result: Eliminates head-of-line blocking, maintains GPU utilization at near 100%, and cuts median user latency by .
(4) Chunked Prefill & Decode Colocation:
- A massive incoming prompt (e.g., 4096 tokens) monopolizes GPU compute during its prefill phase, stalling all active autoregressive decode sequences and causing massive TPOT latency spikes.
- Chunked Prefill partitions long prefills into chunks (e.g., 512 tokens), co-scheduling one prefill chunk alongside active decode iterations in the same batch step to maintain smooth inter-token latency SLAs.
🏭 Production Trade-offs
In-Depth Analysis & Engineering Trade-offs: ① Continuous batching is impossible without PagedAttention—dynamic insertion and eviction of sequences causes severe physical memory fragmentation; without virtual memory paging, servers run out of memory despite having 50% free fragmented VRAM. ② Throughput vs. Latency Pareto knob—increasing max batch size from 16 to 128 maximizes token throughput and lowers dollar cost per token, but increases per-token generation time (TPOT) by 2-3x; platforms tune batch size strictly against contractual latency SLOs. ③ Chunked prefill preserves decode TPOT stability—un-chunked prefill requests inject 100-300ms delays into active streaming chats; chunked prefill caps prefill work per step, keeping decode iterations running like clockwork. ④ Prefill-Decode (PD) disaggregation as the ultimate separation—because prefill is compute-bound and decode is memory-bound, cutting-edge architectures deploy separate dedicated prefill GPU nodes and decode GPU nodes, transferring KV cache states over high-speed networks. ⑤ Scheduling policy trade-offs—First-Come First-Served (FCFS) ensures fairness, but Shortest-Job-First (SJF) minimizes average queuing latency across the cluster. ⑥ Interview takeaway—write out the equation, explain how static batching creates tail bubbles and head-of-line blocking, detail how continuous batching swaps sequences at every iteration step, and highlight Chunked Prefill.
⚠️ Common Interview Pitfalls
- ✕Using static request-level batching for serving mixtures of short and long prompt requests, causing extreme GPU compute idling on tail bubbles.
- ✕Attempting continuous batching without PagedAttention, triggering fatal memory fragmentation and frequent OOM panics.
- ✕Allowing large un-chunked prefill requests to monopolize batch steps, severely degrading active streaming TPOT for existing users.
🎯 Interviewer Follow-up Inquiries
- ?How does PagedAttention allocate virtual memory table blocks to prevent physical GPU memory fragmentation during continuous batching?
- ?How does Chunked Prefill mathematically balance prompt processing throughput against autoregressive decode latency guarantees?
- ?Why does Prefill-Decode (PD) disaggregated serving eliminate interference between compute-bound and memory-bandwidth-bound phases?
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
📚