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
Next: M8-048 →
📐 Mathematical Definition
Tstep≈Tmem+B Tflop;throughput∝B,  latency∝BT_{\text{step}}\approx T_{\text{mem}}+B\,T_{\text{flop}};\qquad \text{throughput}\propto B,\ \ \text{latency}\propto B
⚡ 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 BB 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 NN model parameters from high-bandwidth memory (HBM) to on-chip SRAM.
- For batch size B=1B=1, memory transfer cost is 2N2N bytes for 1 token generated   ⟹  \implies severe memory-bandwidth saturation.
- For batch size BB, reading the NN weights once serves BB concurrent tokens. Step execution duration scales as:
Tstep(B)≈Tmemory+B⋅TcomputeT_{\text{step}}(B) \approx T_{\text{memory}} + B \cdot T_{\text{compute}}
Because Tmemory≫B⋅TcomputeT_{\text{memory}} \gg B \cdot T_{\text{compute}} for moderate BB, per-token generation cost drops by nearly 1B\frac{1}{B}, drastically boosting aggregate token throughput (Tokens/sec).

(2) Why Static Batching Destroys Latency (Head-of-Line Blocking):
- The Flaw: An entire batch of BB sequences must run until the single longest sequence finishes generation (Tmax⁡=max⁡i=1BLiT_{\max} = \max_{i=1}^B L_i).
- 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 tt, 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 2−4×2-4\times.

(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 Tstep≈Tmem+B⋅TcompT_{\text{step}} \approx T_{\text{mem}} + B \cdot T_{\text{comp}} 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.
🎯 Drill This Card Now➔
📚

Associated Knowledge Base Guides & Mindmaps

← PreviousM8-046: Explain Exact Caching vs. Semantic Caching: Architecture, Mechanics, and Hallucination Risks📋 Back to BankNext →M8-048: Explain the Cost-Quality-Latency Trilemma and Constrained Decision Framework in Production ML