M4-063M4: Sequences & TransformersKV Cache & Inference OptimizationsHard
⚡Flashcard Drill➔Mastery:

Chunked Prefill and Piggyback Hybrid Batch Scheduling

🎯 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: M4-064 →
📐 Mathematical Definition
chunked:prefill split into c chunks;mix with decode⇒utilize both resources\text{chunked}: \text{prefill split into }c\ \text{chunks};\qquad \text{mix with decode}\Rightarrow\text{utilize both resources}
⚡ One-Sentence Core Answer
Chunked prefill splits lengthy prompt computations into fixed-size chunks and interleaves them with ongoing decode steps within the same batch iteration, preventing long prefills from causing decode latency spikes.

📌 Key Takeaways

  • •
    Problem: Long prefills monopolize GPU compute for hundreds of milliseconds, stalling concurrent decode steps and causing severe Time-Per-Output-Token (TPOT) tail latency jitter
  • •
    Mechanism: Chunked prefill (Sarathi-Serve) slices long prompts into chunks of size CC (e.g., 512 tokens), co-scheduling one chunk with BB decode tokens in a single execution step
  • •
    Benefits: Normalizes execution latency per iteration, eliminates scheduling starvation, and improves GPU compute utilization via hybrid GEMM-GEMV batching

📐 Mathematical Derivations

Mathematical Mechanism: Latency Jitter in Naive Continuous Batching: When a long prompt of length L=4096L = 4096 arrives, executing its prefill in one step takes Tprefill≫TdecodeT_{\text{prefill}} \gg T_{\text{decode}} (e.g., 150 ms150\text{ ms} vs 15 ms15\text{ ms}). All ongoing decode streams pause for 150 ms150\text{ ms}, creating an unacceptable 10×10\times spike in P99 TPOT. Chunked Prefill Formulation: The prompt is partitioned into M=⌈L/C⌉M = \lceil L / C \rceil chunks: P=[C1,C2,…,CM]P = [C_1, C_2, \dots, C_M]. At step kk, chunk CkC_k is executed. The attention computation for chunk CkC_k attends to: QCk∈RC×d,K=[Kcached(1:k−1);KCk],V=[Vcached(1:k−1);VCk]Q_{C_k} \in \mathbb{R}^{C \times d}, \quad K = [K_{\text{cached}(1:k-1)}; K_{C_k}], \quad V = [V_{\text{cached}(1:k-1)}; V_{C_k}] This is causal cross-attention against historical KV cache plus causal self-attention within CkC_k. Hybrid Batch Scheduling: In each iteration, the scheduler constructs a batch containing Ntokens=C+BdecodeN_{\text{tokens}} = C + B_{\text{decode}}, where CC is the prefill chunk size and BdecodeB_{\text{decode}} is the number of active decode tokens. The unified tensor X∈R(C+Bdecode)×dX \in \mathbb{R}^{(C + B_{\text{decode}}) \times d} is processed in a single forward pass, keeping per-iteration execution time tightly bounded.

🏭 Production Trade-offs

Deep Dive & Engineering Trade-offs: ① TTFT vs TPOT Trade-off: Chunked prefill slightly extends Time-to-First-Token (TTFT) for the incoming long prompt (due to multiple chunk steps and kernel overhead) in exchange for dramatic reductions in TPOT jitter for all active decode requests. ② Kernel Complexity: The attention kernel must support mixed ragged batches where some sequences perform chunked cross-attention over variable-length caches while others perform single-token decoding (supported in FlashAttention-2/3 and vLLM). ③ Compute Efficiency: Merging a prefill chunk (C=512C=512) with decode tokens converts small GEMVs into larger GEMMs, raising GPU Tensor Core utilization without saturating memory bandwidth. ④ Chunk Size Tuning: If CC is too small (e.g., 64), kernel launch overhead and low arithmetic intensity reduce throughput; if CC is too large (e.g., 2048), decode latency jitter reappears. Typical values are C∈[256,1024]C \in [256, 1024]. ⑤ Interview Strategy: Explain the root cause of TPOT jitter, sketch the chunked attention formulation, and demonstrate how balancing token counts achieves both predictable latency and high hardware utilization.
⚠️ Common Interview Pitfalls
  • ✕
    Believing chunked prefill speeds up TTFT (it slightly slows down TTFT for the individual request to protect global TPOT)
  • ✕
    Ignoring the requirement for causal cross-attention kernels capable of handling past KV history during chunk processing
  • ✕
    Setting the chunk size arbitrarily without considering GPU compute saturation thresholds
🎯 Interviewer Follow-up Inquiries
  • ?
    How does FlashAttention support mixed ragged sequences containing both prefill chunks and decode tokens?
  • ?
    What is the mathematical relationship between chunk size CC and GPU Tensor Core saturation?
⚡
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

← PreviousM4-062: Methods to Reduce KV Cache Memory Footprint📋 Back to BankNext →M4-064: Speculative Decoding Variants: Medusa, EAGLE, and Multi-Token Prediction