I6Medium★ LLM Serving Essential · Throughput CorePart I · Inference, Decoding & Quantization

Continuous Batching Iteration-Level Scheduler

⚡Flashcard Drill➔

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?
Next: RadixAttention Prefix Cache Tree & LRU Eviction →
💡

Core Mental Anchor / Mnemonic

Reclaim finished slots every step, admit queued prompts immediately up to the KV budget.

📐 Mathematical Derivation & Core Formula

∑r∈Active(t)(promptr+decodedr,t)≤Bkv,∑r∈Step(t)tokensr,t≤Bstep\sum_{r \in \mathrm{Active}(t)} (\text{prompt}_r + \text{decoded}_{r,t}) \le B_{\mathrm{kv}}, \quad \sum_{r \in \mathrm{Step}(t)} \text{tokens}_{r,t} \le B_{\mathrm{step}}
### Eliminating Padding Wait via Iteration-Level Scheduling
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.
🎯 Drill This Card Now➔
← Prev: PagedAttention KV Block Allocator & MappingBack to Part I & All 105Next: RadixAttention Prefix Cache Tree & LRU Eviction →