I6Medium★ LLM Serving Essential · Throughput CorePart I · Inference, Decoding & Quantization
Continuous Batching Iteration-Level Scheduler
Schedule requests at each decoding iteration so newly queued requests fill freed slots immediately instead of waiting for the longest request.
⏱️ Time:
O(|Batch|) 每解码步调度💾 Space:
O(|Waiting| + |Running|)🎯 Interactive Self-Practice Loop (Attempt Before Peeking)
Practice in 4 steps: recall mechanism, complete core lines, check edge cases, and log mastery locally.
Step 1 · Mechanism Recall & Stability Self-Check
Step 2 · Complete Key Implementation Lines
class ContinuousBatchScheduler:
"""Iteration-level LLM scheduler admitting new waiting requests as soon as slots & KV budget open."""
def __init__(self, max_batch_size: int, kv_token_budget: int):
self.max_batch_size =
self.kv_token_budget = kv_token_budget
self.waiting = [] # list of dicts: {id, prompt_len, remaining_gen}
self.running = [] # list of dicts: {id, used_kv, remaining_gen}
self.finished_ids = []
def submit(self, req_id: str, prompt_len: int, gen_len: int) -> None:
self.waiting.append({"id": req_id, "prompt_len": prompt_len, "remaining_gen": gen_len})
def step(self) -> list:
# 1. Admit waiting requests within concurrency & KV budget
used_kv_total =
while self.waiting and len(self.running) < self.max_batch_size:
nxt = self.waiting[0]
if used_kv_total + nxt["prompt_len"] + 1 > self.kv_token_budget:
break
self.waiting.pop(0)
self.running.append({"id": nxt["id"], "used_kv": nxt["prompt_len"], "remaining_gen": nxt["remaining_gen"]})
used_kv_total += nxt["prompt_len"]
# 2. Run one iteration step across all active requests
stepped_ids = []
still_running = []
for req in self.running:
req["used_kv"] += 1
req["remaining_gen"] -= 1
stepped_ids.append(req["id"])
if req["remaining_gen"] <= 0:
self.finished_ids.append(req["id"])
else:
still_running.append(req)
self.running = still_running
return stepped_ids
Step 3 · Verify Boundary Cases & Assertions
Step 4 · Follow-Up Drill & Review Outcome
Q1: What is Chunked Prefill and why does it improve Continuous Batching latency?
💡
Core Mental Anchor / Mnemonic
Reclaim finished slots every step, admit queued prompts immediately up to the KV budget.
📐 Mathematical Derivation & Core Formula
### Eliminating Padding Wait via Iteration-Level Scheduling
Static batching waits until every sequence in a batch hits
Continuous batching frees completed sequences after every single forward step and admits waiting requests whenever concurrency and KV cache budgets permit.
Static batching waits until every sequence in a batch hits
[EOS], leaving slots idle after short generations finish.Continuous batching frees completed sequences after every single forward step and admits waiting requests whenever concurrency and KV cache budgets permit.
🔄 Tensor Dimensions & Shape Flow
waiting queue -> check max_batch & kv_budget -> admit to running -> step all active -> free finished
🛡️ Numerical Stability & Pitfalls Checklist
- Enforce both batch-count caps and cumulative KV token budgets before admitting new requests.
- Plan preemption (recompute or CPU swap) when active decode lengths outgrow remaining KV cache capacity.
💻 Reference Code Implementation
class ContinuousBatchScheduler:
"""Iteration-level LLM scheduler admitting new waiting requests as soon as slots & KV budget open."""
def __init__(self, max_batch_size: int, kv_token_budget: int):
self.max_batch_size = max_batch_size
self.kv_token_budget = kv_token_budget
self.waiting = [] # list of dicts: {id, prompt_len, remaining_gen}
self.running = [] # list of dicts: {id, used_kv, remaining_gen}
self.finished_ids = []
def submit(self, req_id: str, prompt_len: int, gen_len: int) -> None:
self.waiting.append({"id": req_id, "prompt_len": prompt_len, "remaining_gen": gen_len})
def step(self) -> list:
# 1. Admit waiting requests within concurrency & KV budget
used_kv_total = sum(r["used_kv"] for r in self.running)
while self.waiting and len(self.running) < self.max_batch_size:
nxt = self.waiting[0]
if used_kv_total + nxt["prompt_len"] + 1 > self.kv_token_budget:
break
self.waiting.pop(0)
self.running.append({"id": nxt["id"], "used_kv": nxt["prompt_len"], "remaining_gen": nxt["remaining_gen"]})
used_kv_total += nxt["prompt_len"]
# 2. Run one iteration step across all active requests
stepped_ids = []
still_running = []
for req in self.running:
req["used_kv"] += 1
req["remaining_gen"] -= 1
stepped_ids.append(req["id"])
if req["remaining_gen"] <= 0:
self.finished_ids.append(req["id"])
else:
still_running.append(req)
self.running = still_running
return stepped_ids
🧪 Runnable Assertions & Validation
Copy and run directly in Python / Jupyter:
sched = ContinuousBatchScheduler(max_batch_size=2, kv_token_budget=30)
sched.submit("r1", prompt_len=4, gen_len=1)
sched.submit("r2", prompt_len=4, gen_len=3)
sched.submit("r3", prompt_len=4, gen_len=2)
s1 = sched.step() # runs r1, r2; r1 finishes!
s2 = sched.step() # r3 immediately enters batch alongside r2 without waiting for r2 to finish!
assert s1 == ["r1", "r2"], f"Step 1 mismatch: {s1}"
assert s2 == ["r2", "r3"], f"Step 2 must admit r3 immediately: {s2}"
print("✓ Continuous Batching scheduler assertion passed")🎯 Core Follow-up Inquiries & Reference Answers
Q1:What is Chunked Prefill and why does it improve Continuous Batching latency?
A long prompt (e.g., 16k tokens) stalls concurrent decode iterations if processed in one monolithic pass. Chunked Prefill splits long prefills into bounded chunks co-scheduled alongside decode tokens, keeping inter-token latency smooth.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.