Scheduler Budget 与 Admission Control

Continuous batching 还需要两层资源决策

Continuous Batching说明每轮重组 active batch；Scheduler budget 决定这一轮做多少工作，Admission control 决定新请求是否获得长期状态容量。

iteration token/compute budget：本轮 decode tokens、prefill chunks、speculative verification tokens 总量及其不同成本权重；
sequence/slot budget：active requests 数、CUDA Graph bucket、sampling/metadata slots；
KV block budget：当前 prompt blocks、未来增长 reservation、prefix shared refs、fragmentation 与 safety margin；
policy：priority/FIFO/deadline/fairness、preemption、reject/queue。

它们不是同一个数字。一个 decode token 读取长 KV，而一个 prefill token 属于大 GEMM/chunk；简单相加只可作为 scheduler 近似预算，实际需用 measured cost model 校准。

Iteration budget：decode 优先与 chunked prefill

设每轮 budget 为 6 token-work，已有 2 个 decode requests 各前进一步，长 prompt 还剩 12 tokens，prefill chunk cap 为 4：

tick 0: decode=2, prefill=4, prompt_remaining=8
tick 1: decode=2, prefill=4, prompt_remaining=4
tick 2: decode=2, prefill=4, prompt_remaining=0

每轮满足：

C_{decode}+C_{prefill}\le C_{iteration}

这里把 token 当等成本只是教学模型。生产可给 prefill/decode/spec tokens 不同权重，或直接限制 batch token 数、prefill tokens、sequences、blocks 多个维度。Decode-first 有助于控制 active 请求 TPOT，但可能让新请求 TTFT 饥饿；prefill 占比过高则拉长 iteration，伤害全部 decode。

Chunked Prefill把长 prompt 拆开，提供预算插入点；它增加 launches/调度边界，且后续 chunk 会读取更长历史。

KV admission：保守 reservation 与乐观 overcommit

请求 $r$ 的当前 prompt blocks：

b_r^{prompt}=\left\lceil\frac{T_r^{prompt}}{B_{block}}\right\rceil

若按最大输出长度保守预留：

b_r^{reserve}=\left\lceil\frac{T_r^{prompt}+T_r^{max\_new}}{B_{block}}\right\rceil

取 block size 4、capacity 4 blocks：

A: prompt=6, max_new=6 → current=2 blocks, reserve=3
B: prompt=4, max_new=4 → current=1 block, reserve=2

保守策略先接 A 后只剩 1 block，B 排队；总 reservation 3。乐观策略当前只用 3 blocks，可同时接 A/B，但当长度跨 block 边界时 used 增长到 4，继续增长需要 preempt 一个请求。本例按遍历顺序在 step 2 preempt A，释放其 3 blocks；这不是推荐公平策略，只展示未来容量风险。

真实 reservation 还要考虑：

Prefix Cache命中 blocks 的 shared refcount 与 copy-on-write tail；
Sliding Window层是否在 $W$ 后封顶，而 global layers 继续增长；
KV 量化或 MLA 的每 block bytes/metadata；
block fragmentation、CUDA Graph/workspace/NCCL safety margin；
beam/speculative tentative blocks 与 rollback；
output limit 可被客户端修改、stop 提前结束或请求取消。

可运行的 budget/admission 模拟

import math,platform
from dataclasses import dataclass

@dataclass
class Request:
    name:str; prompt:int; max_new:int
    def prompt_blocks(self,block_size): return math.ceil(self.prompt/block_size)
    def reserved_blocks(self,block_size): return math.ceil((self.prompt+self.max_new)/block_size)

def iteration_budget_trace(prompt_tokens,decode_requests,budget,chunk_size):
    remaining=prompt_tokens; trace=[]; tick=0
    while remaining>0:
        decode=min(decode_requests,budget)
        prefill=min(remaining,chunk_size,budget-decode)
        assert decode+prefill<=budget
        remaining-=prefill
        trace.append({"tick":tick,"decode_tokens":decode,
                      "prefill_tokens":prefill,"remaining_prompt":remaining})
        tick+=1
    return trace

def conservative_admission(requests,capacity,block_size):
    admitted=[]; reserved=0
    for request in requests:
        need=request.reserved_blocks(block_size)
        if reserved+need<=capacity:
            admitted.append(request.name); reserved+=need
    return admitted,reserved

def optimistic_growth(requests,capacity,block_size):
    used=sum(r.prompt_blocks(block_size) for r in requests)
    lengths={r.name:r.prompt for r in requests}; active=list(requests); trace=[]
    assert used<=capacity
    for step in range(max(r.max_new for r in requests)):
        for request in active[:]:
            if step>=request.max_new: active.remove(request); continue
            old=math.ceil(lengths[request.name]/block_size)
            lengths[request.name]+=1; new=math.ceil(lengths[request.name]/block_size)
            used+=new-old
            if used>capacity:
                used-=new; del lengths[request.name]; active.remove(request)
                trace.append((step,request.name,"preempted",used))
            else: trace.append((step,request.name,"advanced",used))
    return trace

def main():
    budget_trace=iteration_budget_trace(12,2,6,4)
    assert budget_trace==[
        {"tick":0,"decode_tokens":2,"prefill_tokens":4,"remaining_prompt":8},
        {"tick":1,"decode_tokens":2,"prefill_tokens":4,"remaining_prompt":4},
        {"tick":2,"decode_tokens":2,"prefill_tokens":4,"remaining_prompt":0}]
    requests=[Request("A",6,6),Request("B",4,4)]; block_size=4; capacity=4
    conservative,reserved=conservative_admission(requests,capacity,block_size)
    assert conservative==["A"] and reserved==3
    growth=optimistic_growth(requests,capacity,block_size)
    assert (2,"A","preempted",2) in growth
    print(f"python={platform.python_version()}")
    print(f"iteration_budget=6 decode_requests=2 prefill_prompt=12 chunk_size=4")
    print(f"budget_trace={budget_trace}")
    print(f"block_size={block_size} capacity_blocks={capacity}")
    print(f"requests={[r.__dict__ for r in requests]}")
    print(f"conservative_admitted={conservative} reserved_blocks={reserved}")
    print(f"optimistic_prompt_blocks={sum(r.prompt_blocks(block_size) for r in requests)} growth_trace={growth}")

if __name__=="__main__": main()

完整文件位于 examples/scheduler_admission.py。实际 conservative 只接 A 并 reservation 3 blocks；optimistic 同时接 A/B，decode 增长到 step 2 时 A 被 preempt，used 降为 2 blocks。

模拟没有 GPU 时间、priority 或 prefix sharing，不能证明哪种策略性能更好。它验证预算守恒和“当前可放下≠未来可完成”的容量不变量。

Policy、指标与失败场景

Admission 可选择：

conservative：按最大可能长度预留，OOM/preemption 少，但 blocks 可能长期闲置、吞吐低；
optimistic：按当前+短期增量接纳，利用率高，但需可靠 preemption/queue/reject；
probabilistic/profiled：按输出长度分布/SLO reservation，需防分布漂移与租户滥用；
priority/deadline aware：高优先级抢占低优先级，必须防 starvation/抖动。

必须同时报告 admission rate、queue time、reject/preempt 次数、recompute/swap bytes、KV utilization、TTFT/TPOT 与 SLO goodput。只提高 active sequences 可能让每 iteration 更慢，最终 goodput 下降。

常见错误：

token budget 超限仍把所有 decode/preill 塞进一轮；
prompt 与 max_new 的 off-by-one（首 token emitted/cache 错位）；
preempt 后 block refcount 没释放或 shared prefix 被误释放；
recompute preemption 不记录未来 prefill 成本；
queue timeout 只断客户端，不从 scheduler 移除；
Graph bucket/allocator workspace 未计入 capacity safety；
admission 使用字符长度而不是 token ids。

Request Lifecycle定义 queued/admitted/cancelled/timed-out 终态和清理；本页定义资源决策。PagedAttention提供 block allocator，Continuous Batching执行每轮 active set。

服务可靠性、Backpressure 与 Observability把 slow-consumer credits、deadline/cancel 竞态与在线 finish/queue/KV 指标补到 scheduler 周围；接纳请求不代表必须在客户端不读时继续生成。