49 lines
2.5 KiB
Markdown
49 lines
2.5 KiB
Markdown
---
|
||
title: "Hardware-Aware Prefix Scheduler"
|
||
created: 2026-06-28
|
||
updated: 2026-06-28
|
||
type: concept
|
||
tags: [speculative-decoding, llm-serving, scheduling, throughput-optimization]
|
||
sources: [DSpark]
|
||
---
|
||
# Hardware-Aware Prefix Scheduler
|
||
|
||
硬件感知前缀调度器是 [[DSpark]] 的核心系统级创新，将投机解码的验证长度选择形式化为**全局吞吐量最大化问题**。与静态阈值方法不同，调度器根据实时引擎负载动态为每个请求分配验证预算。
|
||
|
||
## 问题形式化
|
||
|
||
考虑 $R$ 个活跃请求的批次。请求 $r$ 的置信度序列为 $\{c_{r,1}, ..., c_{r,\gamma}\}$，前缀存活概率为累积乘积 $a_{r,j} = \prod_{i \le j} c_{r,i}$。
|
||
|
||
总批大小：$B = \sum_{r=1}^{R} (1 + \ell_r)$
|
||
|
||
期望接受 token 数：$\tau = \sum_{r=1}^{R} \left(1 + \sum_{j=1}^{\ell_r} a_{r,j}\right)$
|
||
|
||
目标：最大化期望系统吞吐量 $\Theta = \tau \cdot \text{SPS}(B)$，其中 $\text{SPS}(B)$ 是预录的引擎吞吐量表（steps per second vs batch size）。
|
||
|
||
## 贪心算法（Algorithm 1）
|
||
|
||
1. 全局排序所有候选前缀扩展（按 $a_{r,j}$ 降序）
|
||
2. 逐条接纳最高存活概率的 token，$O(1)$ 查表更新 $\Theta$
|
||
3. **早停**：$\Theta$ 下降时立即停止——确保因果性（不泄露未来 token 信息），满足 lossless speculative decoding 的非预期性（non-anticipating property）
|
||
|
||
## 生产适配（Section 5.2）
|
||
|
||
理论算法在真实基础设施中面临两个冲突：
|
||
|
||
**异步调度**：ZOS（Zero-Overhead Scheduling）要求下一步的批大小在当前步完成前已知。方案：使用两步前的置信度输出来估计截断容量 $K$，将入场过程转化为动态 top-$K$ 选择——排序保持精确，仅容量估计有轻微延迟。
|
||
|
||
**非平滑硬件曲线**：真实 $\text{SPS}(B)$ 呈锯齿状阶梯退化，早停可能陷入局部最小。方案：移除早停，做无约束全局搜索——ZOS 驱动的异步设计天然形成因果屏障（截断决策依赖两步前的历史预测），避免了未来 token 泄露。
|
||
|
||
## 效果
|
||
|
||
在 DeepSeek-V4 生产部署中（Section 5.4）：
|
||
- 轻负载时自动分配更长验证预算（从 MTP-1 的静态 2 token 扩展到 4-6 token）
|
||
- 高并发时自动收缩验证长度，防止资源争用
|
||
- 将服务 Pareto 前沿外移：V4-Flash 在中等 SLA 下吞吐量提升 51%，V4-Pro 提升 52%
|
||
|
||
## 参考
|
||
|
||
- [[DSpark]]
|
||
- [[confidence-scheduled-verification|置信度调度验证（Confidence-Scheduled Verification）]]
|
||
- [[prefix-survival-probability|前缀存活概率（Prefix Survival Probability）]]
|