連續批次處理

I-00 追蹤了單筆請求從進入閘道器到串流結束的完整過程。真實的推論服務引擎則要同時處理大量請求，並在每一次模型迭代（iteration）決定下一步要執行哪些請求的哪些片段。現代排程器不採用單一固定的 batch size，而是在每一步判斷：還能放進多少 prompt token、decode token、進行中的序列與 KV 區塊，才不會超出延遲目標或耗盡記憶體。

本篇教學將實作一個精簡的迭代級排程器（iteration-level scheduler）：先依來源釐清批次術語的不同定義，接著實作「優先排入 decode、剩餘預算切給分塊 prefill」的排程策略，加入依明確規則運作的搶占（preemption）與過載時的有界背壓（bounded backpressure）拒絕機制，最後產出一份可逐輪重播核對的 iteration 軌跡。

術語會隨引擎與文獻而異

這些名詞並不是通用的同義詞。Triton 的「dynamic batcher」是在執行前把等待中的請求合併成一批；它的迭代式序列（iterative sequences）文件則把 continuous、iteration-level 與 inflight batching 描述為「在每個 iteration 步驟組成批次」的策略（NVIDIA Triton 批次機制）。Orca 則以 iteration-level scheduling 之名提出這套機制（Yu et al., OSDI 2022）。比較不同系統時，務必指明引擎與實際排程規則。

為什麼批次化能幫助 Decode

批次很小時，decode 花在從 HBM 讀取模型權重的時間，通常多於實際運算的時間。把多條進行中的序列湊在一起執行，就能讓同一次權重讀取分攤給多個 token 的更新運算。批次變大因此可能拉高整體吞吐量，但每一步也可能變慢，並占用更多 KV 記憶體。

因此，推論排程器每一輪至少要同時平衡四項限制：

• 這一個 iteration 准許放進來的總 token 工作量；

• 同時處於活躍狀態的序列條數；

• 當下與後續輸出持續增加所需的 KV 區塊餘裕；以及

• 等待中與執行中請求之間的延遲目標與優先序規則。

光是把所有序列槽位塞滿並不夠：一次放進一筆好幾千個 token 的長提示，可能卡住正在串流輸出的 decode 請求；一次收進太多持續變長的序列，則可能迫使引擎在生成途中搶占請求，甚至觸發 OOM。

靜態批次與請求級動態批次

假設同一批的 8 筆請求分別要產生 20, 45, 80, 120, 150, 90, 60, 200 個輸出 token。在簡化的輸出槽位示意中，把 prefill 結束時產生的首個 token 算作第 1 回合，並暫不考慮輸入提示的長短差異。這批綁在一起的 8 筆請求共要跑 200 個輸出回合（1 次 prefill 加上 199 次 decode），開出 8 × 200 = 1,600 個輸出槽位，實際產出的有效 token 卻只有：

20 + 45 + 80 + 120 + 150 + 90 + 60 + 200 = 765 useful tokens
wasted slots = 1,600 - 765 = 835
waste ratio  = 835 / 1,600 = 52.19%

請求級動態批次（request-dynamic batching）雖然能縮短請求在入口等待湊成批次的時間，但只要湊成批次後仍得綁在一起等到 200 個 token 的最慢請求跑完，長短不齊的輸出依然會浪費同樣的 835 個槽位。

迭代級排程則會在請求完成的當下立刻釋放槽位，並可在下一個 iteration 補進等待中的請求。以同樣 200 個抽象回合來看，8 槽位引擎若每一輪都跑滿 8 個有效 decode，理論上限就是填滿全部 1,600 個輸出槽位；真實系統的有效產出會低於這個上限，因為分塊 prefill、取樣、KV 記憶體安全餘裕與排程器本身都會消耗資源。至於同一時間區間內能多跑完幾筆請求，取決於遞補請求的輸入長度與 prefill 成本；要估算容量，必須先給定明確的工作負載模型，不能只靠槽位算術。

分塊 Prefill 與最大化 Decode 排程

允許新請求在生成途中加入後，只要長提示獨占整個 iteration，prefill 與 decode 就會互相干擾。Sarathi-Serve 以分塊 prefill 搭配 stall-free 排程解決這個問題：每個批次先替所有進行中的 decode 各排 1 個 token，再把剩餘的 token 預算分給 prefill 區塊（chunk），讓新提示加入時不必暫停進行中的 decode（Agrawal et al., OSDI 2024）。本篇把這種 decode 優先的組批方式稱為最大化 decode 排程。vLLM V1 也在可行時預設啟用分塊 prefill，並在 max_num_batched_tokens 預算內先排入所有待處理的 decode，再排 prefill（vLLM 最佳化與調校指南）。區塊大小是一道取捨：區塊愈大，prefill 的運算效率愈高，但 ITL 尖峰也可能愈明顯；區塊太小雖能維持 decode 節奏，卻會增加 kernel 啟動開銷，以及對先前區塊的重複注意力讀取。

我們的模擬器在每個 iteration 依序執行以下七個步驟：

1. 檢查當前 iteration 新抵達的請求；

2. 若高優先序請求抵達時活躍槽位已滿，只有在等待佇列還有空位可容納被搶占的請求時，才搶占活躍集合中剩餘工作量最大的一般優先序請求；否則改走一般的有界排隊或拒絕流程；

3. 一般優先序請求依序排入固定上限的等待佇列，超出上限者直接拒絕；

4. 將等待佇列前端的請求補進空出的活躍槽位；

5. 為每一筆已完成 prefill 的活躍請求優先排入 1 個 decode token；

6. 將當輪剩餘的 token 預算分配給未完成 prefill 的活躍請求，每筆單輪最多推進 3 個 prefill token；以及

7. 當請求完成最後一段 prefill 時同步吐出第 1 個輸出 token，並在當輪結束時移除已完成全部輸出的請求；只有第 2 個以後的輸出 token 才會消耗 decode 預算。

為了方便手算核對佇列與優先序狀態，模擬器假設被搶占的請求能以零轉移成本保留既有進度（相當於理想化的卸載），且只限制活躍序列槽位、等待佇列深度與單輪 token 預算，不模擬實體 KV 區塊配置。真實引擎的搶占都有代價。以 vLLM V1 為例，預設的搶占模式是 RECOMPUTE 而非 SWAP：引擎會釋放被搶占請求占用的 KV 快取空間，等記憶體足夠時再重新計算這些狀態（vLLM 最佳化與調校指南）。

固定排程器的測試情境

測試請求清單：

在 iteration 1，高優先序的 C 抵達並搶占 A，因為此刻 A 剩餘的工作量（3 + 3 = 6）大於 B（1 + 2 = 3）；接著 C 在同一個 iteration 跑完 2 個 prefill token 並吐出唯一的輸出 token，當場完工退場。到了 iteration 2，新抵達的 D 補進空出的活躍槽位，E 排進等待佇列跟在 A 後面，而第 3 筆同時抵達的 F 因為兩格等待佇列已滿而直接被拒，讓過載透過明確的背壓訊號立刻浮現，而非在佇列裡無聲逾時。

完整範例：追蹤各個 Iteration

依照上述排程規則，逐輪執行的預期軌跡如下：

各筆請求的首個輸出與完成 iteration 彙整如下：

由於模擬器只計算離散的 token 預算，並未模擬 GPU kernel 實際耗時，這份軌跡驗證的是排程順序與准入邊界，而非真實硬體延遲。

建立排程模擬器

將以下程式碼存為 simulate_scheduler.py：

import json
from pathlib import Path

MAX_ACTIVE = 2
MAX_QUEUE = 2
TOKEN_BUDGET = 6
PREFILL_CHUNK = 3
MAX_ITERATIONS = 200
PRIORITY_PREEMPTION = True

REQUESTS = [
    {"id": "A", "arrival": 0, "priority": "normal", "prompt": 6, "output": 3},
    {"id": "B", "arrival": 0, "priority": "normal", "prompt": 4, "output": 2},
    {"id": "C", "arrival": 1, "priority": "high", "prompt": 2, "output": 1},
    {"id": "D", "arrival": 2, "priority": "normal", "prompt": 4, "output": 2},
    {"id": "E", "arrival": 2, "priority": "normal", "prompt": 1, "output": 1},
    {"id": "F", "arrival": 2, "priority": "normal", "prompt": 1, "output": 1},
]

states = {
    item["id"]: {
        **item,
        "prompt_remaining": item["prompt"],
        "output_remaining": item["output"],
        "first_output": None,
        "completed": None,
        "preemptions": 0,
        "result": "pending",
    }
    for item in REQUESTS
}
active = []
waiting = []
trace = []

def remaining_work(request_id):
    state = states[request_id]
    return state["prompt_remaining"] + state["output_remaining"]

def enqueue(request_id):
    if len(waiting) >= MAX_QUEUE:
        states[request_id]["result"] = "rejected"
        return False
    states[request_id]["result"] = "waiting"
    waiting.append(request_id)
    return True

if not (0 < MAX_ACTIVE <= TOKEN_BUDGET and MAX_QUEUE >= 0 and PREFILL_CHUNK > 0):
    raise ValueError("invalid scheduling budgets")
if len(states) != len(REQUESTS) or any(x["prompt"] < 1 or x["output"] < 1 for x in REQUESTS):
    raise ValueError("unique IDs and positive lengths required")

for iteration in range(MAX_ITERATIONS):
    record = {"iteration": iteration, "decode": [], "prefill": [], "prefill_emitted": [], "preempted": [], "rejected": []}

    for item in [x for x in REQUESTS if x["arrival"] == iteration]:
        request_id = item["id"]
        if len(active) < MAX_ACTIVE:
            active.append(request_id)
            states[request_id]["result"] = "active"
        elif item["priority"] == "high" and PRIORITY_PREEMPTION:
            victims = [rid for rid in active if states[rid]["priority"] == "normal"]
            if victims and len(waiting) < MAX_QUEUE:
                victim = max(victims, key=remaining_work)
                active.remove(victim)
                states[victim]["preemptions"] += 1
                states[victim]["result"] = "waiting"
                waiting.insert(0, victim)
                active.append(request_id)
                states[request_id]["result"] = "active"
                record["preempted"].append(victim)
            elif not enqueue(request_id):
                record["rejected"].append(request_id)
        elif not enqueue(request_id):
            record["rejected"].append(request_id)

    while waiting and len(active) < MAX_ACTIVE:
        request_id = waiting.pop(0)
        active.append(request_id)
        states[request_id]["result"] = "active"

    budget = TOKEN_BUDGET
    for request_id in list(active):
        state = states[request_id]
        if state["prompt_remaining"] == 0 and state["output_remaining"] > 0 and budget > 0:
            state["output_remaining"] -= 1
            budget -= 1
            record["decode"].append(request_id)
            if state["first_output"] is None:
                state["first_output"] = iteration

    for request_id in list(active):
        state = states[request_id]
        if state["prompt_remaining"] > 0 and budget > 0:
            amount = min(PREFILL_CHUNK, state["prompt_remaining"], budget)
            state["prompt_remaining"] -= amount
            budget -= amount
            record["prefill"].append([request_id, amount])
            if state["prompt_remaining"] == 0:
                state["output_remaining"] -= 1
                state["first_output"] = iteration
                record["prefill_emitted"].append(request_id)

    completed_now = []
    for request_id in list(active):
        state = states[request_id]
        if state["prompt_remaining"] == 0 and state["output_remaining"] == 0:
            state["completed"] = iteration
            state["result"] = "completed"
            active.remove(request_id)
            completed_now.append(request_id)

    record["completed"] = completed_now
    record["queue"] = list(waiting)
    record["active"] = list(active)
    record["unused_budget"] = budget
    assert len(waiting) <= MAX_QUEUE and len(active) <= MAX_ACTIVE
    assert 0 <= budget <= TOKEN_BUDGET
    trace.append(record)

    terminal = all(state["result"] in {"completed", "rejected"} for state in states.values())
    if terminal:
        break

artifact = {
    "termination": "all_terminal" if terminal else "iteration_limit",
    "policy": {
        "max_active": MAX_ACTIVE,
        "max_queue": MAX_QUEUE,
        "token_budget": TOKEN_BUDGET,
        "prefill_chunk": PREFILL_CHUNK,
    },
    "trace": trace,
    "requests": {
        request_id: {
            "first_output": state["first_output"],
            "completed": state["completed"],
            "preemptions": state["preemptions"],
            "result": state["result"],
        }
        for request_id, state in states.items()
    },
}
Path("request_summary.json").write_text(json.dumps(artifact["requests"], indent=2))
print(json.dumps(artifact, indent=2))

執行指令：

python simulate_scheduler.py > scheduler_trace.json

檢查輸出結果：A.preemptions=1、F.result="rejected"，且 C 在 iteration 1 完成、B 在 iteration 2 完成、D 在 iteration 4 完成、A 與 E 在 iteration 5 完成；程式也會另外寫出 request_summary.json。若 termination 欄位出現 "iteration_limit"，代表工作負載未能在上限輪數內排空，不能視為正常跑完的模擬。

歷史吞吐量結果真正證明了什麼

Orca 論文在 16 張 A100-40GB GPU 上執行 GPT-3 架構的 175B FP16 模型，使用合成請求與強制指定的輸出長度受測；在依生成 token 數正規化後的中位數端對端延遲同為 190 ms 的條件下，回報吞吐量是 FasterTransformer 的 36.9 倍（6.81 對 0.185 requests/s）（Yu et al., OSDI 2022）。這是在上述條件下，Orca 整套系統對照「由請求級批次排程器驅動的 FasterTransformer」所得的差距，並非連續批次在任何部署環境都能複製的通用倍數。

Anyscale 2023 年的基準測試以單張 A100-40GB 執行 OPT-13B，基線是 Hugging Face Pipelines 的單純靜態批次。結果顯示，連續批次的實作吞吐量最高達 8×，再加上連續批次專用記憶體最佳化的 vLLM 最高達 23×。吞吐量實驗是一次突發送出 1,000 筆請求（每筆 512 個輸入 token，輸出長度取自截斷指數分布），量測的並非受線上 SLO 限制的容量。作者也表示並未分析哪一項最佳化對 vLLM 的效能貢獻最大，只推測與它動態（而非預先）保留 KV 空間有關。因此，不能把 8× 到 23× 的差距說成「單靠 PagedAttention」的功勞（Anyscale 基準測試，2023）。

刻意破壞的案例

無上限佇列

把 MAX_QUEUE 改成無限大，並讓每個 iteration 湧入 8 筆新請求，但系統每輪只能消化 2 筆。等待佇列每輪約增加 6 筆請求。連續批次能讓 GPU 持續滿載，但只要抵達率高於服務率，就消化不了湧入的請求；正式環境仍需要有界佇列、附帶重試政策的明確拒絕，或依優先序卸除負載。

未分塊的長提示 Prefill

放任一筆 6,000 個 token 的長提示獨占整個 iteration，讓正在串流輸出的 decode 請求全部在後面乾等。此時整體 token 吞吐量或許依然好看，正在串流的使用者卻會看到 ITL 突然飆高。分塊（chunking）能限制單一排程週期內進入的 prompt 工作量；I-03 介紹的 prefill/decode 資源池實體分離，則是架構更重的另一條路線。

未計入成本的驅逐機制

激進的排程模式在 KV 記憶體見底時，可能會暫停或驅逐已經開始生成的序列。TensorRT-LLM 的舊版執行期調整指南對比了兩種模式：MAX_UTILIZATION 積極排入請求，代價是 KV 快取達到上限時可能得暫停請求；預設的 GUARANTEED_NO_EVICT 則採取較保守的准入控制，保證已開始的請求不會被暫停（TensorRT-LLM 執行期選項）。實際上線前務必確認所部署引擎後端與版本的預設策略，只要可能觸發搶占，效能追蹤就必須把重算（recompute）或交換（swap）的耗時一併算進去。

動手實作

請分別執行以下三種排程變體：

1. 上述基準策略（Baseline）；

2. 將 PREFILL_CHUNK 改為 6；以及

3. 將 PRIORITY_PREEMPTION 設為 False，讓高優先序的 C 改進等待佇列排隊。

針對每種變體回報：

• 每筆請求的首個輸出與完成 iteration；

• 等待佇列的最大長度；

• 搶占次數與拒絕次數；

• 每個 iteration 未用完的 token 預算；以及

• 當 prefill 消耗預算時，是否有任何已進入 decode 階段的請求被迫等待。

接著維持基準預算設定，在第 0 到第 9 個 iteration 每輪額外塞入 2 筆一般優先序請求（每筆皆為 6 個輸入 token、3 個輸出 token，並賦予唯一 ID），同時測試「活躍槽位與等待佇列雙雙客滿時，又來一筆高優先序請求」的情境。請驗證等待佇列長度永遠不會超過 2，且過載會直接反映為明確拒絕，而不會暗中堆積成無上限佇列。

三種初始變體的完成 iteration 對照表如下（- 代表遭到拒絕；首個輸出時間與剩餘預算可直接查閱 scheduler_trace.json）。抵達分支 if len(active) < MAX_ACTIVE: 會讓剛抵達的請求優先搶下空著的活躍槽位，排在原本佇列中的請求之前。這條規則是為了讓教學程式保持簡單，並非公平性建議；真實排程器還需要等待時間加權（aging）、期限與取消處理，才能避免排隊請求發生飢餓（starvation）。

可量測的完成標準

本篇排程器實作須滿足以下所有條件才算通過：

• 所有請求長度、預算上限、優先序與排程規則皆明確列出；

• 任一 iteration 的 decode 與 prefill token 總和皆不超過 6；

• 基準策略中沒有任何單次 prefill 分塊超過 3 個 token；

• A 剛好被搶占 1 次，且後續能帶著既有進度恢復執行；

• 兩格等待佇列客滿時 F 被明確拒絕，且高優先序搶占也不會讓等待佇列超額；

• 首個輸出與完成 iteration 完全吻合範例表格；

• 持續過載測試中，等待佇列長度始終維持在 2 以下；

• 引用歷史上的 8×、23× 與 36.9× 結果時，皆完整保留模型、硬體／基線、指標與分母條件；以及

• 未將 Anyscale 測試中 vLLM 的額外領先幅度單獨歸因於 PagedAttention。

提取練習

1. 迭代級排程（iteration-level scheduling）與請求級動態批次（request-dynamic batching）核心差異為何？

2. 為什麼單步 token 預算比單純限制序列條數更能反映真實排程成本？

3. 分塊 prefill（chunked prefill）主要解決什麼延遲問題？

4. 為什麼連續批次無法消除過載時的排隊現象？

5. 教學模擬器的簡化搶占免費保留了什麼狀態，而採重算（recompute）策略的引擎會丟掉什麼？

6. 為什麼不能把 Anyscale 測出的 23× 直接當成 PagedAttention 單一機制的加速倍率？

解答

1. 迭代級排程能在每一次自迴歸步驟之間立刻移除已完成的請求並補進新工作，不必把整批請求綁死到最長序列跑完為止。

2. 兩者各占一個序列槽位，但一段 prompt 分塊會在同一個 iteration 處理並快取多個 token，一般 decode 步驟則只處理 1 個 token、新增 1 筆 KV 項目。

3. 分塊 prefill 限制單一 iteration 內能與進行中 decode 一起執行的 prompt 工作量，藉此限縮長提示卡住串流 ITL 的時間，代價是 prefill 效率會降低一些。

4. 只要請求抵達率長期高於系統可持續消化的服務率，多出來的請求不是塞進佇列就是被拒絕；批次最佳化只能把服務率推近硬體上限，無法改寫這條流量守恆定律。

5. 模擬器無償保留了已完成的部分 prefill 與 decode 進度；採用重算策略的真實引擎則會直接釋放被搶占請求的 KV 區塊，等恢復執行時再重做 prefill 運算。

6. 該基準測試量測的是 vLLM 結合連續批次、分頁記憶體管理與多項引擎最佳化的離線突發整體表現，作者並未單獨拆離出 PagedAttention 個別貢獻的比例。

本文不涵蓋的內容

I-02 將進一步把單 token 的 KV 狀態換算成分頁區塊容量；I-04 加入單機前綴重用與分散式快取感知路由；I-03 評估將 prefill 與 decode 拆到獨立資源池的分離式架構；I-07 則會把這套排程機制放進開迴路（open-loop）壓測，實測容量上限與 SLO 達成率。

來源與延伸閱讀

• Yu, G., Jeong, J. S., Kim, G. W., et al. "Orca: A Distributed Serving System for Transformer-Based Generative Models." OSDI, 2022。迭代級排程與特定條件下 36.9× FasterTransformer 對照實驗的第一手論文。usenix.org

• Agrawal, A., Kedia, N., Panwar, A., et al. "Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve." OSDI, 2024。分塊 prefill 與 stall-free（decode 優先）排程的第一手論文。arxiv.org/abs/2403.02310

• vLLM Project. "Optimization and Tuning." 現行文件，查閱日期 2026-11-02。vLLM V1 預設啟用分塊 prefill、decode 優先排程與重算式搶占的官方說明。docs.vllm.ai

• NVIDIA Triton Inference Server. "Batchers." 現行文件，查閱日期 2026-11-02。區分請求級動態批次與迭代式／連續／inflight 批次的官方說明。docs.nvidia.com

• Daniel, C., Shen, C., Liang, E., and Liaw, R. "How Continuous Batching Enables 23x Throughput in LLM Inference While Reducing p50 Latency." Anyscale, 2023-06。完整保留模型、硬體、比較基線與未拆離單一最佳化前提的廠商突發壓測報告。anyscale.com

• NVIDIA TensorRT-LLM. "Useful Runtime Options." 現行文件，查閱日期 2026-11-02。容量排程器與驅逐策略語意的官方說明。nvidia.github.io