大模型推理连续批处理与乱序调度 — 深度调研报告

所属域：大模型框架 调研日期：2026-04-26 关键词：Continuous Batching, Out-of-Order Scheduling, LLM Inference, KV Cache, PagedAttention

目录

1. 第一部分：概念剖析
2. 第二部分：行业情报
3. 第三部分：方案对比
4. 第四部分：精华整合

第一部分：概念剖析

1. 定义澄清

通行定义

连续批处理（Continuous Batching），又称迭代级调度（Iteration-Level Scheduling）或动态批处理（Dynamic Batching），是一种大语言模型推理优化技术。其核心思想是：在每次前向传播（即每个 decoding iteration）结束后，允许已完成生成的请求退出批次、新请求加入批次，而无需等待批次中所有请求同时完成。这种方式消除了传统静态批处理中因请求长度不一而导致的"队头阻塞"（Head-of-Line Blocking）问题。

**乱序调度（Out-of-Order Scheduling）**是对连续批处理的扩展，允许系统不按请求到达顺序返回结果，而是在每个 iteration 动态选择最优的请求子集执行，从而实现更高的 GPU 利用率和更低的尾部延迟。

常见误解

1. 误解一：连续批处理 = 动态批处理（与传统 DL 框架中的含义相同） 传统深度学习框架中的动态批处理通常指在推理前按请求队列大小聚合 batch size，而连续批处理是在每个 iteration 级别动态增删请求，粒度更细。

2. 误解二：乱序调度意味着结果丢失或顺序混乱 乱序调度仅指执行顺序可以乱序，最终输出结果仍然保持每个请求内部的 token 顺序正确。系统的调度器负责维护请求的独立状态。

3. 误解三：连续批处理只适合 decoding 阶段 最新的系统（如 vLLM 的 Chunked Prefill）已将连续批处理的思路扩展到 prefill 阶段，通过将长 prompt 切分为 chunk 并与 decode 交叉执行，进一步提升吞吐。

边界辨析

2. 核心架构

┌────────────────────────────────────────────────────────────────┐
│              LLM 推理连续批处理与乱序调度系统架构                │
├────────────────────────────────────────────────────────────────┤
│                                                                │
│  ┌──────────┐    ┌──────────────┐    ┌──────────────────────┐  │
│  │ 请求队列  │───→│  调度器       │───→│   GPU 执行引擎       │  │
│  │ (Request  │    │ (Scheduler)  │    │ (Execution Engine)  │  │
│  │  Queue)   │    │              │    │                      │  │
│  └──────────┘    │ 职责：        │    │ 职责：               │  │
│                  │ • 选择执行子集│    │ • 并行前向传播       │  │
│                  │ • 管理请求生命周期 │                              │
│                  │ • 优先级排序  │    │ • KV cache 读写      │  │
│                  │ • 预占/淘汰策略│    │ • 采样与 logits 输出 │  │
│                  └──────┬───────┘    └──────────┬───────────┘  │
│                         │                       │               │
│                         ▼                       ▼               │
│                  ┌──────────────┐    ┌──────────────────────┐  │
│                  │  KV Cache     │    │  监控与指标采集       │  │
│                  │  Manager      │    │  (Metrics & Profiler)│  │
│                  │              │    │                      │  │
│                  │ 职责：       │    │ 职责：               │  │
│                  │ • 内存分配   │───→│ • TTFT / TPOT 监控   │  │
│                  │ • 碎片整理   │    │ • GPU 利用率跟踪     │  │
│                  │ • 淘汰策略   │    │ • 队列深度分析       │  │
│                  └──────────────┘    └──────────────────────┘  │
│                                                                │
│  ┌──────────────────────────────────────────────────────────┐  │
│  │  数据流:  Prefill Phase ──→ Decode Phase (iteration)     │  │
│  │            │                   │                         │  │
│  │        [Chunked]          [Continuous Batching]           │  │
│  │        [Prefix Cache]     [Out-of-Order]                  │  │
│  └──────────────────────────────────────────────────────────┘  │
└────────────────────────────────────────────────────────────────┘

组件说明

3. 数学形式化

公式 1：连续批处理吞吐增益

其中 $N$ 为请求数，$L_i$ 为第 $i$ 个请求的输出长度，$B$ 为批次大小，$\bar{L}$ 为平均输出长度，$t_{\text{iter}}$ 为单次 iteration 耗时。相比静态批处理 $T_{\text{static}} = \frac{B}{L_{\max}} \cdot \frac{1}{t_{\text{iter}}}$，连续批处理的吞吐增益为 $L_{\max} / \bar{L}$。

公式 2：KV Cache 内存占用

其中 $B$ 为批次大小，$L_i$ 为序列长度，$H$ 为注意力头数，$D$ 为每头维度，$s_{\text{dtype}}$ 为数据类型字节数（FP16 为 2 字节），因子 2 对应 key 和 value 两个张量。此公式决定了调度器能容纳的最大批次大小。

公式 3：预占决策的损失函数

调度器在需要腾出 GPU 内存时，根据重计算成本、请求优先级和等待时间综合评估哪些请求应该被预占（暂停执行，KV cache 溢出到 CPU），选择损失最大的请求进行淘汰。

公式 4：迭代级调度效率

其中 $S_t$ 为第 $t$ 个 iteration 实际执行的请求集合，$B_{\max}$ 为最大批次容量。理想情况下 $\eta \to 1$，即 GPU 计算槽位几乎无浪费。

公式 5：Chunked Prefill 对 TTFT 的影响

其中 $C$ 为 chunk 大小，$B'$ 为 concurrent decode 批次大小。通过分块预填充与 decode 交叉执行，短请求的 TTFT 显著降低。

4. 实现逻辑（Python 伪代码）

from dataclasses import dataclass, field
from typing import List, Optional, Dict
from enum import Enum

class RequestStatus(Enum):
    WAITING = "waiting"
    PREFILL = "prefill"
    DECODING = "decoding"
    PREEMPTED = "preempted"
    COMPLETED = "completed"

@dataclass
class Request:
    """单个推理请求"""
    request_id: str
    prompt_tokens: List[int]
    max_new_tokens: int
    priority: float = 1.0
    status: RequestStatus = RequestStatus.WAITING
    generated_tokens: List[int] = field(default_factory=list)
    kv_cache_offsets: Optional[List[int]] = None  # KV cache 中的位置
    prefill_done: bool = False

class KVCacheManager:
    """KV Cache 管理器 — 使用 PagedAttention 或 Radix Tree"""

    def __init__(self, total_blocks: int, block_size: int):
        self.block_size = block_size  # 每个 block 存储的 token 数
        self.free_blocks = set(range(total_blocks))
        self.allocated: Dict[str, List[int]] = {}  # request_id -> block_ids
        self.radix_tree = RadixTree()  # 用于 prefix caching

    def allocate(self, request: Request, num_tokens: int) -> List[int]:
        """分配 KV cache blocks"""
        num_blocks = (num_tokens + self.block_size - 1) // self.block_size
        if len(self.free_blocks) < num_blocks:
            raise MemoryError("KV cache exhausted")
        blocks = [self.free_blocks.pop() for _ in range(num_blocks)]
        self.allocated[request.request_id] = blocks
        return blocks

    def release(self, request: Request):
        """释放请求的 KV cache"""
        blocks = self.allocated.pop(request.request_id, [])
        self.free_blocks.update(blocks)

    def evict_to_cpu(self, request: Request):
        """将 KV cache 溢出到 CPU 内存（预占策略）"""
        blocks = self.allocated.get(request.request_id, [])
        # 实际实现中会将 GPU tensor 搬运到 CPU pinned memory
        self.allocated[request.request_id] = None
        self.free_blocks.update(blocks)

class Scheduler:
    """连续批处理调度器 — 核心组件"""

    def __init__(self, max_batch_size: int, kv_cache_mgr: KVCacheManager,
                 enable_chunked_prefill: bool = True,
                 enable_out_of_order: bool = True,
                 chunk_size: int = 512):
        self.max_batch_size = max_batch_size
        self.kv_cache_mgr = kv_cache_mgr
        self.enable_chunked_prefill = enable_chunked_prefill
        self.enable_out_of_order = enable_out_of_order
        self.chunk_size = chunk_size
        self.waiting_queue: List[Request] = []
        self.running_batch: List[Request] = []

    def add_request(self, request: Request):
        """外部接口：接收新请求"""
        self.waiting_queue.append(request)

    def schedule(self) -> List[Request]:
        """每 iteration 调用：决定当前批次"""
        # Step 1: 完成请求退出
        self.running_batch = [
            r for r in self.running_batch
            if r.status != RequestStatus.COMPLETED
        ]

        # Step 2: 尝试将 waiting 请求加入 batch
        available_slots = self.max_batch_size - len(self.running_batch)
        new_requests = self.waiting_queue[:available_slots]
        self.waiting_queue = self.waiting_queue[available_slots:]

        for req in new_requests:
            if not req.prefill_done and self.enable_chunked_prefill:
                # Chunked prefill 模式
                req.status = RequestStatus.PREFILL
                req.chunk_remaining = len(req.prompt_tokens)
            else:
                req.status = RequestStatus.DECODING
                self.kv_cache_mgr.allocate(req, len(req.prompt_tokens))
            self.running_batch.append(req)

        # Step 3: 处理 prefill chunk
        batch = []
        for req in self.running_batch:
            if req.status == RequestStatus.PREFILL:
                chunk_len = min(self.chunk_size, req.chunk_remaining)
                req.chunk_remaining -= chunk_len
                if req.chunk_remaining <= 0:
                    req.prefill_done = True
                    req.status = RequestStatus.DECODING
                    self.kv_cache_mgr.allocate(req, len(req.prompt_tokens))
                batch.append((req, chunk_len))
            elif req.status == RequestStatus.DECODING:
                batch.append((req, 1))  # decode 每次推进 1 token

        # Step 4: 乱序调度 — 可选重排执行顺序
        if self.enable_out_of_order:
            batch = self._reorder(batch)

        return batch

    def _reorder(self, batch: List[tuple]) -> List[tuple]:
        """乱序调度：按优先级和剩余 token 数重排"""
        # 优先执行高优先级、短剩余长度的请求
        return sorted(batch, key=lambda x: (-x[0].priority, x[0].max_new_tokens))

    def check_preemption(self) -> List[Request]:
        """检查是否需要预占（OOM 防护）"""
        if len(self.kv_cache_mgr.free_blocks) < THRESHOLD:
            # 按损失函数选择预占请求
            preempted = sorted(
                self.running_batch,
                key=lambda r: self._preempt_loss(r),
                reverse=True
            )[:self._num_to_preempt()]
            for r in preempted:
                self.kv_cache_mgr.evict_to_cpu(r)
                r.status = RequestStatus.PREEMPTED
                self.waiting_queue.insert(0, r)
            return preempted
        return []

class ContinuousBatchingEngine:
    """连续批处理推理引擎主类"""

    def __init__(self, config):
        self.scheduler = Scheduler(
            max_batch_size=config.max_batch_size,
            kv_cache_mgr=KVCacheManager(
                total_blocks=config.num_gpu_blocks,
                block_size=config.block_size
            ),
            enable_chunked_prefill=config.chunked_prefill,
            enable_out_of_order=config.out_of_order
        )
        self.gpu_executor = GPUExecutor(model=config.model)

    def run(self):
        """主循环"""
        while True:
            # 调度决策
            batch = self.scheduler.schedule()

            # 预占检查
            preempted = self.scheduler.check_preemption()

            if not batch:
                time.sleep(0.001)  # 空转保护
                continue

            # GPU 执行
            outputs = self.gpu_executor.forward(batch)

            # 更新请求状态
            for req, output in zip(batch, outputs):
                req.generated_tokens.append(output.token_id)
                if len(req.generated_tokens) >= req.max_new_tokens:
                    req.status = RequestStatus.COMPLETED

            # 产出 stream 结果
            for req, output in zip(batch, outputs):
                yield req.request_id, output.token_id

5. 性能指标

6. 扩展性与安全性

水平扩展

• 多节点部署：Prefill 和 Decode 可分离到不同节点（DistServe 架构），各自独立水平扩展
• 张量并行 (TP)：单模型跨多 GPU 切分，每个 GPU 运行连续批处理的子集
• Pipeline 并行 (PP)：模型层间 pipeline，配合 iteration-level 调度可隐藏 bubble
• Multi-LoRA 服务：同一模型服务多个 adapter，调度器按请求携带的 adapter ID 选择加载路径

垂直扩展

• KV Cache 优化：PagedAttention 减少内部碎片率从 20-30% 降至 < 4%
• 量化：KV cache 使用 INT8/FP8 量化，可扩大有效缓存容量 2-4x
• GPU 内存复用：H2O 的 Heavy-Hitter 淘汰策略，只保留关键 KV token
• CPU Offloading：预占请求的 KV cache 溢出到 CPU pinned memory，恢复时快速加载

安全考量

• DoS 攻击防护：恶意用户发送超长 prompt 可耗尽 KV cache，需设置 prompt 长度上限和请求配额
• 资源隔离：多租户场景下，需按用户/租户分配独立 KV cache 池
• Side-channel 攻击：连续批处理中不同请求共享 GPU 计算资源，存在侧信道泄露风险
• Prompt Injection：batch 中不同请求的 prompt 不应相互影响，需隔离 attention mask
• 数据残留：KV cache 跨请求复用（prefix caching）需确保不同用户不共享敏感前缀

第二部分：行业情报

1. GitHub 热门项目

2. 关键论文

选择说明：经典高影响力论文（Orca、vLLM/PagedAttention、Sarathi、DistServe）约占 40%，最新 SOTA 研究（H2O、QServe、PowerInfer、FlashAttention-3 等）约占 60%。

3. 系统化技术博客

4. 技术演进时间线

2022 ─┬─ Orca 提出 iteration-level scheduling → 首次将操作系统批处理概念引入 LLM serving
2023 ─┼─ vLLM / PagedAttention 开源 → KV cache 碎片问题得到系统性解决，吞吐提升 2-4x
      ├─ Hugging Face TGI 发布 → Rust 高性能推理服务器
      └─ Speculative Decoding 论文 → 引入投机解码概念
2024 ─┼─ DistServe (NSDI) → Prefill-decode 分离成为主流架构方向
      ├─ Sarathi-Serve (OSDI) → Chunked prefill 解决长 prompt 队头阻塞
      ├─ SGLang 发布 → RadixAttention 实现跨请求 KV cache 精确复用
      ├─ H2O (ASPLOS) → KV cache 淘汰策略大幅减少内存占用
      ├─ Splitwise (ASPLOS) → 预填充与解码资源分区共享
      ├─ QServe (MLSys) → W4A8KV4 量化方案降低推理成本
      └─ FlashAttention-3 → 第三代注意力计算优化
2025 ─┼─ vLLM 达到 ~80K+ stars → 成为最流行的开源 LLM 推理框架
      ├─ Chunked Prefill 合并到 vLLM 主分支 → 理论落地为工程实践
      ├─ LMCache 出现 → 分布式多级 KV cache 缓存
      ├─ Multi-LoRA Serving 成为 vLLM 核心功能 → 多模型 serving 支持
      └─ 当前状态：连续批处理已成为 LLM 推理的标配技术，研究焦点转向
           Prefill-Decode 分离、投机解码与 KV cache 优化的组合创新

第三部分：方案对比

1. 历史发展时间线

2018 ─┬─ Transformer 原生架构 → 静态批处理时代，batch 内所有序列必须等长
2020 ─┼─ Megatron-LM 引入张量并行 → 多 GPU 推理成为可能，但批处理仍是静态的
2022 ─┼─ Orca 提出 iteration-level scheduling → 打破静态批处理的"同时完成"约束
      └─ 影响：开创了现代 LLM serving 的调度范式
2023 ─┼─ vLLM + PagedAttention → KV cache 内存碎片率从 20-30% 降至 4%
      ├─ 影响：吞吐提升 2-4x，成为行业基准
      ├─ TGI 发布 → Hugging Face 生态的 Rust 推理服务器
      └─ 影响：降低部署门槛，促进开源生态繁荣
2024 ─┼─ DistServe → Prefill 与 Decode 分离到不同 GPU 节点
      ├─ Sarathi → Chunked Prefill 解决长 prompt 问题
      ├─ SGLang → RadixAttention 实现跨请求 KV cache 复用
      └─ 影响：调度粒度从"请求级"细化到"阶段级"
2025 ─┼─ vLLM 集成 Chunked Prefill → 理论方案进入主流框架
      ├─ LMCache → 分布式 KV cache 缓存层
      ├─ 投机解码 + 连续批处理组合 → 进一步降低延迟
      └─ 当前状态：连续批处理成为标配，优化方向转向细粒度调度与多技术融合

2. 六种主流方案横向对比

方案 A：vLLM（PagedAttention + Continuous Batching）

方案 B：TensorRT-LLM

方案 C：SGLang（RadixAttention）

方案 D：TGI（Text Generation Inference）

方案 E：LightLLM

方案 F：DistServe（Prefill-Decode 分离）

3. 技术细节对比

4. 选型建议

第四部分：精华整合

1. The One 公式

这个公式揭示了连续批处理的本质：通过迭代级调度释放 GPU 算力 + 通过分页 KV cache 释放 GPU 显存 + 消除队头阻塞释放时间。

2. 一句话解释（费曼技巧）

想象一家餐厅的厨房：传统的静态批处理像是一个厨师必须等一桌所有菜做完才能开始下一桌，而连续批处理允许做完一道菜就上桌，同时立刻开始做另一桌的菜——厨房永远在忙，没有一口锅是空闲的。

3. 核心架构图

外部请求 → [请求队列] → [调度器] → [GPU 执行引擎] → 输出流
                 │           │            │
            优先级排序   PagedAttention   前向传播
            FIFO/HPF     Radix Tree       采样
                         KV Cache
                            │
                     CPU Offload (溢出)

4. STAR 总结

Situation（背景 + 痛点）

大语言模型的推理服务面临独特的性能挑战：自回归生成导致每个请求的 token 数不可预知，传统静态批处理在 GPU 上产生大量"空计算槽"（idle compute slots）。例如一个 batch 中有 32 个请求，其中 30 个只需生成 20 个 token 而 2 个需要 2000 个 token，那么前 1980 个 iteration 中只有 2 个槽位在真正工作，GPU 利用率不足 7%。在云计算成本高昂的背景下，这种浪费直接转化为巨大的经济成本。

Task（核心问题）

连续批处理要解决的核心问题是：如何在保持每个请求 token 序列正确性的前提下，让 GPU 的计算槽位尽可能在每一 iteration 都被有效利用。约束条件包括：(1) 每个请求的 KV cache 必须独立维护；(2) prefill 和 decode 的计算模式不同（前者 FLOPs 密集，后者 Memory Bandwidth 密集）；(3) GPU 显存有限，KV cache 可能成为瓶颈；(4) 调度器本身的开销不能抵消调度带来的收益。

Action（主流方案）

技术演进经历了三个阶段：(1) 2022 年 Orca 首次引入 iteration-level 调度，证明了连续批处理可以将吞吐提升 2-4x；(2) 2023 年 vLLM + PagedAttention 解决了 KV cache 的内存碎片问题，将碎片率从 20-30% 降至 4% 以下，使调度器能容纳更多并发请求；(3) 2024 年的大爆发：DistServe 将 prefill 与 decode 分离到不同节点独立调度，Sarathi 引入 chunked prefill 将长 prompt 切块与 decode 交叉执行，SGLang 的 RadixAttention 实现跨请求 KV cache 精确复用，H2O 引入 KV cache 淘汰策略。2025 年，这些理论方案陆续被集成到 vLLM 等主流框架中。

Result（效果 + 建议）

当前连续批处理已成为 LLM 推理的事实标准，相比静态批处理可实现 2-5x 的吞吐提升和 2-10x 的尾部延迟降低。实践建议：(1) 对于大多数场景，vLLM 是首选——吞吐高、生态成熟、功能全面；(2) 对延迟极其敏感的场景考虑 TensorRT-LLM 的编译优化；(3) 多轮对话场景 SGLang 的 prefix cache 复用率最高；(4) 超大规模部署可参考 DistServe 的 prefill-decode 分离架构。仍需关注的问题：KV cache 的跨节点管理、多模态输入的调度策略、以及连续批处理与 speculative decoding 的深度集成。

5. 理解确认问题

问题：假设一个连续批处理系统中，一个请求正在 decode 阶段（已经生成了 100 个 token），此时一个全新的长 prompt（5000 tokens）请求到达。调度器应该如何处理？请解释连续批处理与静态批处理在这两种情况下的行为差异，以及 KV cache 在这个过程中扮演了什么角色。

参考答案：

在连续批处理下：(1) 长 prompt 的 prefill 不会被阻塞——如果使用 chunked prefill，它会被切分为多个 chunk（如每个 512 tokens）与现有 decode 请求交叉执行；如果不使用 chunked prefill，调度器可能选择预占（preempt）现有的部分 decode 请求，将它们的 KV cache 溢出到 CPU，腾出 GPU 空间执行新请求的 prefill；(2) 已生成的 100 个 token 的 KV cache 被保留在 GPU 中（如果未被预占），decode 继续进行；(3) 当长 prompt 的 prefill 完成后，它进入 decode 阶段，与其他请求共享 batch。

在静态批处理下：新请求必须等待当前 batch 中所有请求完成（可能需等待数千个 iteration），造成严重的队头阻塞和 GPU 闲置。

KV cache 的角色：(1) 已生成 token 的 KV cache 是 decode 阶段的核心——它避免了重复计算已处理过的 token；(2) KV cache 的内存占用决定了调度器能容纳多少并发请求；(3) PagedAttention 通过分页管理减少碎片，使调度器能更高效地利用 GPU 显存；(4) 预占策略下，KV cache 可以被迁移到 CPU，是请求"暂停"而非"丢弃"的关键。

附录：术语表

报告生成日期：2026-04-26 数据来源：WebSearch 实时搜索、GitHub API、arXiv、官方博客 数据新鲜度：情报数据优先使用 2024-2026 年的最新信息 总字数：约 7,500 字