BalanceRoute 是部署于 vllm-ascend 之上的集中式 stateful proxy 框架,利用分段线性 F-score 捕获 barrier 同步下 safe/overflow 的 $(G{-}1)$ 倍不对称性,以两阶段贪心+子集选择在毫秒级完成 DP decode 路由。BR-0 无需预测即降低不均衡 4.1×/吞吐+11.8%;BR-H 加 binary termination classifier 达 +15.4%,优势随 $G$ 超线性放大至 +34.5%($G{=}16$)。
DP decode 的 barrier 同步使每步延迟由最重 worker 决定;KV-cache 随生成单调增长且迁移代价极高(sticky assignment),加上到达非平稳、决策窗口 < 100 ms,现有通用启发式(Random / RR / P2C / JSQ)对 LLM decode 结构无感知。Chen et al. (2026) 报告生产部署中 >40% 加速器时间因 barrier 空闲而浪费。

Paper Figure 1, verbatim (caption: "Data-parallel decode under barrier synchronization").
图 1 直观对比:均衡分配时所有 worker 近乎同时到达 barrier(利用率 88–94%);不均衡时 straggler 将步延迟拉高,轻载 worker 空闲等待。每步空闲在 request 生命期内逐步累积,随 $G$ 按 order-statistics 增长。
问题形式化:
System scope:
核心机制 — 分段线性 F-score: 度量将候选子集 $Q$ 分配给 worker $g$ 对单步不均衡 $I(k)$ 的边际效应:
$$F_g(Q) = \Delta_s(Q) - G \cdot (\Delta_s(Q) - m_g)_+$$
其中 $\Delta_s(Q) = \sum_{i \in Q} s_i$ 为候选总 prefill 负载,$m_g = M(k) - L_g(k)$ 为 safe margin。
| 区域 | 条件 | F-score 行为 | 物理意义 |
|---|---|---|---|
| Safe regime | $\Delta_s(Q) \leq m_g$ | $F_g(Q) = \Delta_s(Q)$ | 每单位负载减少 1 单位 deficit |
| Overflow regime | $\Delta_s(Q) > m_g$ | $F_g(Q) = G \cdot m_g - (G{-}1) \cdot \Delta_s(Q)$ | 每单位溢出增加 $(G{-}1)$ 单位不均衡 |
交叉点处不对称性为 $(G{-}1)$ 倍:$G{=}16$ 时一单位溢出产生 15 倍不均衡代价。
BR-H 扩展: 将 F-score 推广到 horizon 折扣形式:
$$F_g(Q) = \alpha \, (\mathbf{1}^\top \mathbf{d}) \, \Delta_s(Q) - \beta \, (\Delta_s(Q) \, \mathbf{1} - \mathbf{m}_g)_+^\top \mathbf{d}$$
其中 $\mathbf{d} = (1, \gamma, \ldots, \gamma^H)^\top$ 为折扣向量,$\mathbf{m}_g$ 为 horizon margin 向量。BR-0 是 $H{=}0, \alpha{=}1, \beta{=}G$ 的特例。BR-H 仅需二元终止分类器(request 是否在 $H$ 步内结束),而非完整长度回归——论文论证 binary classifier 捕获 routing-relevant signal 比 full-length regressor 更可靠,因为噪声增长快于信号。
核心技术壁垒: 分段线性 F-score 将 barrier 同步的物理约束(max-load 决定步延迟)精确编码为一个具有尖锐交叉的目标函数,使 safe-margin fill 与 overflow 的不对称代价可在 $O(1)$ 内求值。这个洞见将需要整数规划的在线调度问题化简为毫秒级两阶段贪心+子集选择,且给出了最优结构(overflow 代价随 $G$ 线性放大)。现有通用负载均衡文献中没有类似的 barrier-aware 分段评分函数。

Paper Figure 2, verbatim (caption: "System architecture. A stateful proxy maintains the cluster snapshot and runs the BR-H rule.").
系统采用三层架构:控制面(Stateful Python/uvloop Proxy)、Prefill Tier(kv_producer)、Decode Tier(kv_consumer)。Proxy 维护 Cluster Snapshot 并在每个 decode step 运行 BR-H rule。
关键数据流:① Client request 经 Payload Mutator 改写(设 max_tokens=1 触发 prefill-only)→ ② Prefill 完成后返回 KV handle,request 进入 Prompt Pool → ③ BR-H Dispatcher 从 Cluster Snapshot $\sigma(k) = \{\mathcal{A}_g(k), L_g(k), \hat{c}_i(k)\}$ 读取状态,运行 horizon F-score 选择最优 (worker, subset) 分配 → ④ SSE telemetry 回传 per-token 进度,增量更新 snapshot。
Request lifecycle: arrival → payload mutation → prefill (separate tier) → KV handle into prompt pool → BR-H dispatch with global F-score → decode on assigned worker → SSE completion telemetry → snapshot update.
Scheduler: BR-H Dispatcher 是一等公民,其 queuing discipline 是两阶段 F-score 最大化(非 FCFS / SJF / priority)。调度粒度为 per-step batch admission(非 per-request)。
KV / memory manager: KV-cache 分配由下层 vllm-ascend PagedAttention 管理(page-level allocation),BR-H 仅通过 concurrency cap $B$ = max_num_seqs 控制 admission。无独立 eviction 策略——request 自然结束后释放。
Cross-node communication: Prefill→Decode KV transfer 经 MooncakeConnector(RDMA-based),decode 内部 TP all-reduce 经 NVLink/HCCS。
两阶段算法流程:
| 符号 | 含义 | 首次出现 |
|---|---|---|
| $G$ | DP worker 数量 | §2.2 |
| $B$ | 每 worker 最大并发 request 数 | §2.2 |
| $k$ | 离散 decode step 索引 | §2.2 |
| $s_i$ | Request $i$ 的 prefill token 数(路由时已知) | §2.2 |
| $o_i$ | Request $i$ 的总 decode 步数(路由时未知) | §2.2 |
| $w_i^{(j)}$ | Request $i$ 在第 $j$ 步的 KV 负载,$= s_i + j - 1$ | §2.2 |
| $L_g(k)$ | Worker $g$ 在步 $k$ 的总 KV 负载 | §2.2 |
| $M(k)$ | 最重 worker 负载,$= \max_g L_g(k)$ | §2.2 |
| $I(k)$ | 步 $k$ 的总不均衡,$= G \cdot M(k) - \sum_g L_g(k)$ | §2.2 |
| $m_g$ | Worker $g$ 的 safe margin,$= M(k) - L_g(k)$ | §2.2 |
| $\Delta_s(Q)$ | 候选子集的总 prefill 负载,$= \sum_{i \in Q} s_i$ | §2.2 |
| $F_g(Q)$ | 分段线性 F-score | §3.1 |
| $\alpha, \beta, \gamma$ | BR-H 超参:reward 缩放、overflow 惩罚、折扣因子 | §4.1 |
| $H$ | 常数 lookahead horizon | §4 |
| $\mathbf{d}$ | 折扣向量 $(1, \gamma, \ldots, \gamma^H)^\top$ | §4.1 |
| $\mathbf{m}_g$ | Horizon margin 向量 $(m_{g,0}, \ldots, m_{g,H})^\top$ | §4.1 |
| $S_{\text{greedy}}$ | Stage 1→2 切换阈值 | §3.2 |
| $R_{\max}$ | Stage 2 候选子集上限 | §3.2 |
Eq. (1) — BR-0 F-score: $F_g(Q) = \Delta_s(Q) - G \cdot (\Delta_s(Q) - m_g)_+$
F-score 分解为 reward(deficit 填充收益)减去 penalty(overflow 代价乘以 $G$)。Safe regime 下 penalty 为零,每单位负载一单位收益。Overflow regime 下每单位溢出产生 $(G{-}1)$ 单位不均衡代价——因为新 max-load 抬高了 barrier,所有 $G$ 个 worker 都必须等到新 max。
Eq. (2) — BR-H horizon F-score: $F_g(Q) = \alpha (\mathbf{1}^\top \mathbf{d}) \Delta_s(Q) - \beta (\Delta_s(Q) \mathbf{1} - \mathbf{m}_g)_+^\top \mathbf{d}$
将单步 F-score 在 $H$ 步 horizon 上求和,几何折扣 $\gamma$ 使近期预测权重更高。$\alpha, \beta$ 从理论值 $(1, G)$ 解耦为可调参数,补偿预测噪声。逻辑上:未来 $H$ 步中每一步的 overflow 都按该步的 margin 独立判断是否激活惩罚。
Throughput/latency model: 论文给出 per-step time 近似为 $T(x) = ax + b$,其中 $x$ 为 worker 总 KV-cache footprint,$a$ 为带宽系数,$b$ 为固定开销。DP load balancing 在 $ax \gg b$ 时最有价值(长上下文、大 batch、低带宽硬件)。这不是显式优化目标,而是 regime 分析。
单调性分析: $F_g(Q)$ 在 safe regime 内单调递增(reward 线性增长),在 overflow regime 单调递减(penalty 超线性增长)。最优在 $\Delta_s(Q) = m_g$(boundary)处取得——这是 interior optimum 而非 boundary max,因为越过 $m_g$ 后收益急剧翻转为代价。
| # | 检验项 | 判定 |
|---|---|---|
| 1 | F-score 在 $m_g$ 处的连续性 | ✓ — 在 $\Delta_s = m_g$ 处左右极限一致 $= m_g$,但导数不连续 |
| 2 | BR-0 → BR-H 特例归约 | ✓ — $H{=}0$ 时 $\mathbf{d} = (1)$, $\mathbf{m}_g = (m_g)$,取 $\alpha{=}1, \beta{=}G$ 恢复 Eq. (1) |
| 3 | 极端情况 $G{=}1$ | ✓ — $I(k) = 0$ 恒成立,F-score 退化为常数,路由无意义 |
| 4 | 极端情况 $m_g{=}0$(满载 worker) | ✓ — $F_g = -(G{-}1)\Delta_s < 0$,正确表示任何 admission 都纯增不均衡 |
| 5 | Stage 2 starvation guard | ✓ — 最优子集非正分时仍分配单 request,保证 waiting pool 不无限增长 |
| 6 | 目标一致性:$F_g$ 最大化 ↔ $I(k)$ 最小化 | ✓ — $F_g$ 定义为 $-\Delta I(k)$,最大化 F-score 等价于最小化单步不均衡增量 |
Framework-specific 额外检验:

Paper Table 1, verbatim (caption: "Main results. G=8, heavy load, 4P1D topology.").
所有 BR 行在所有指标上完全支配所有基线行。BR-0(无预测)将 Proprietary 上不均衡从 JSQ 的 215k 降至 52k(4.1×),吞吐从 843 提升至 943 tok/s(+11.8%)。Deployed BR-H (ExactMatch) 达 977 tok/s(+15.4%),且 TPOT P95 78.8 ms 为所有方法最低——吞吐增益不以尾延迟为代价。

Paper Figure 3, verbatim (caption: "Per-worker KV-cache workload on Proprietary Data, G=8.").
四面板对比 1,500 步 decode 段的 8 worker 瞬时 KV 负载。Random(左上)worker 轨迹散布 220k–340k 范围;JSQ(右上)收窄至 200k–320k 但仍有显著漂移;BR-0(左下)将全部 8 worker 压缩到 240k–290k 窄带;BR-H ExactMatch(右下)进一步收紧至 240k–275k。Horizon 信息的增量价值在视觉上直观可辨。

Paper Figure 4, verbatim (caption: "Scaling on Proprietary Data across G ∈ {4, 8, 16}.").
BR-H 吞吐优势随 $G$ 超线性增长:+13.4%($G{=}4$, 415 vs 366)→ +21.5%($G{=}8$, 1029 vs 847)→ +34.5%($G{=}16$, 1247 vs 927)。拟合 $\Delta \propto G^{0.69}$。BR-0 增长较平($\Delta \propto G^{0.44}$),BR-H-over-BR-0 的增量从 +2% 扩大到 +12%,预测价值在大规模下被放大。
反直觉现象:$G{=}16$ 时 P2C (688k) 和 JSQ (676k) 的不均衡反而比 RR (616k) 更差——"聪明"的经典启发式在大规模下反效果。

Paper Figure 6, verbatim (caption: "Per-worker KV-cache workload under BR-H deployed with empirical-survival predictor, H=80, G=8.").
Survival 预测器下 worker 带宽压缩在 225k–250k 范围,trace-mean 不均衡 40,757(BR-0 为 51,927,ExactMatch 为 36,277)。Stage-1 confidence gate 使长尾 request 回退到保守锚 $H$,增益主要来自分类器有信心的 request。
| 数据集 | Requests | Mean prompt | Mean output | 特点 |
|---|---|---|---|---|
| Proprietary | 8,000 | 3,197 | 1,185 | 重尾输出分布,生产级 |
| Azure-2024 | 10,000 | 4,652 | 1,052 | 公开可复现,conversation split,filtered output > 1000 |
两个 trace 均在重载(集群近饱和)下评估。Azure-2024 过滤掉短输出 request 是因为 decode-stage 不均衡仅在长输出时占主导。
| Step | 论证环节 | 依据 | 关键量 | ||
|---|---|---|---|---|---|
| 1 | DP decode 的 barrier 同步使每步延迟 = $\max_g L_g(k)$,idle 随 $G$ 按 order-statistics 增长 | §2.1 形式化 + Chen et al. (2026) 报告 >40% waste | $I(k) = G \cdot M(k) - \sum_g L_g(k)$ | ||
| 2 | 通用启发式(RR/P2C/JSQ)不感知 LLM-specific 结构(sticky + 单调增长 KV + 毫秒决策) | §1 定性论证 + §6 实验(基线不均衡 100k–438k) | 四个 hardness property | ||
| 3 | 分段线性 F-score 从 $I(k)$ 的边际效应推导,揭示 safe/overflow 的 $(G{-}1)$ 倍不对称性 | §3.1 代数推导 Eq. (1) | 交叉点 $\Delta_s = m_g$ | ||
| 4 | 两阶段分解:充裕容量下贪心 $O( | R_{\text{wait}} | )$ + 稀缺容量下优先队列子集选择 $O(G \cdot R_{\max})$ | §3.2 算法设计 | 阈值 $S_{\text{greedy}}$ |
| 5 | Horizon 折扣扩展:仅需二元终止分类器而非全长度回归,噪声增长快于信号 | §4 Eq. (2) + BR-0 特例归约 | $(\alpha, \beta, \gamma)$ | ||
| 6 | 集中式 stateful proxy + above-the-engine 集成实现零引擎修改部署 | §5 系统架构 | SSE telemetry + payload mutation | ||
| 7 | BR-0 不均衡降至 52k(JSQ 的 1/4),吞吐 +11.8%;BR-H 达 +15.4%,TPOT P95 同时最低 | §6.2 Table 1 | 977 vs 843 tok/s | ||
| 8 | 优势随 $G$ 超线性增长 $\Delta \propto G^{0.69}$,从 +13.4% 到 +34.5% | §6.3 Table 2 + Figure 4 | 1247 vs 927 tok/s at $G{=}16$ |
代码开放状态: [实现未公开] — BalanceRoute proxy 代码未开源。部署在 vllm-ascend 之上,基线实现基于 vLLM 的 router 策略。
关键实现细节:
核心技术壁垒展开: F-score 求值本身是 $O(1)$ 的 piecewise-linear 函数。真正的工程壁垒在于维护毫秒级更新的 Cluster Snapshot $\sigma(k)$:
PrefillerBudget 背压控制| 维度 | 设计 |
|---|---|
| 粒度 | Per decode-step batch admission(非 per-request 逐个) |
| 抢占 | 不支持(sticky assignment by design,迁移 KV-cache 成本太高) |
| 准入控制 | concurrency cap $B$ = max_num_seqs per worker;超限 request 留在 prompt pool 等待下一步 |
| 饥饿防护 | Stage 2 最优子集非正分时仍强制分配单 request |
| 公平性 | 无 per-tenant/per-priority 保证;最小化全局 $I(k)$ 隐式平衡 worker 负载 |
| Admission frequency | 每个 decode step 一次(sub-100 ms 周期) |
| 维度 | 设计 |
|---|---|
| KV-cache allocation | 由下层 vllm-ascend PagedAttention 管理(page-level) |
| BR-H 感知 | 仅通过 $L_g(k)$(总 KV footprint)和 $B$(slot cap)间接控制 |
| 碎片化 | 不涉及——PagedAttention 处理 |
| 驱逐/重用 | 不涉及——request 自然结束释放,无 prefix cache/radix tree |
| Swap to CPU/disk | 不涉及——由引擎层处理 |
| Before (JSQ/P2C) | After (BR-0/BR-H) | |
|---|---|---|
| 决策信号 | 队列长度 or 随机 | F-score(感知 safe margin + overflow 不对称) |
| 容量区分 | 无 | 两阶段:abundant capacity greedy / scarce capacity subset selection |
| 未来感知 | 无 | BR-H: horizon discounted F-score + binary termination classifier |
| 全局视图 | 无(per-request independent decision) | 有(centralized snapshot 驱动 batch-level decision) |
| Workload regime | BalanceRoute | Baseline (JSQ) | Why |
|---|---|---|---|
| Short output, low $G$ ($G{=}4$) | +13.4% throughput (BR-H) | baseline adequate | 少量 worker 的 order-statistics gap 小,F-score safe/overflow 不对称不显著 |
| Long output, moderate $G$ ($G{=}8$) | +15.4% (deployed BR-H), 4.1× imbal reduction | 215k imbalance | KV-cache 增长使 load variance 放大,F-score 的 $(G{-}1)$ 不对称充分发挥 |
| Long output, large $G$ ($G{=}16$) | +34.5% (oracle BR-H), 5.8× imbal reduction | 676k imbalance | order-statistics gap 按 $G$ 增长,baseline 的 "smart" heuristic 反效果 |
| Short output (filtered out) | 不适用 | 不适用 | Decode-stage imbalance 不占主导;prefill latency dominates |
| Prompt-recurrent workload | ExactMatch 最优 | — | Prompt-hash CDF predictor 高精度 |
| No recurrence | Survival 最优 | — | Marginal CDF fallback,无 per-prompt state |
论文未报告但可推断的 lose regime: (i) 极短输出 (< 100 tokens)——KV 增长不显著,$ax \ll b$,F-score 增益趋零。(ii) 极低并发、单 request per worker——Stage 2 子集选择退化为无意义。(iii) 非 barrier-synchronized 系统(如 pure pipeline 或 async decode)——$I(k)$ 定义不适用。
cudagraph_mode=FULL_DECODE_ONLY),未报告额外 tuning| 指标 | 定义 |
|---|---|
| Average imbalance | trace mean of per-step (max − min) KV workload across $G$ workers |
| TPOT P95 | 95th-percentile time-per-output-token (ms) — decode 尾延迟 |
| Throughput | output tokens per second(仅输出,不含输入) |
仅报告 decode-stage 指标(prefill 不受 decode-tier routing 影响)。
| 维度 | 设计 |
|---|---|
| User-facing API | OpenAI-compatible(通过 proxy 转发,client 无感知) |
| Internal API | Payload mutation(kv_role, max_tokens 字段改写) |
| Config surface | $S_{\text{greedy}}$, $R_{\max}$, $H$, $\alpha$, $\beta$, $\gamma$, predictor choice (Survival / ExactMatch) |
| Tuning guidance | 论文未报告系统化调参方法;仅展示两组 $(\beta, \gamma)$ 均可 |
| Protocol | HTTP + SSE(per-token streaming telemetry) |
Migration cost from vLLM: 部署 BalanceRoute proxy 为独立 Python 进程,无需修改 vllm-ascend 引擎二进制。核心改动:(i) 配置 proxy 为 client 入口;(ii) 配置 prefill/decode tier 的 kv_role;(iii) 部署 MooncakeConnector 支持 cross-tier KV transfer。无 vLLM 代码修改要求——above-the-engine 设计。
| 维度 | 定位 |
|---|---|
| Serving stage | Decode only(prefill 在独立 tier,proxy 仅路由 decode admission) |
| Concurrency regime | Mid-to-high($G{=}4$–$16$ workers, $B$ requests/worker) |
| Hardware affinity | 验证在 Ascend 910C;算法 hardware-agnostic(依赖 per-step time $\propto$ KV footprint,任何 bandwidth-bound decode 均适用)。在 bandwidth/overhead ratio 高的硬件上(长上下文 decode)收益最大 |
| Ecosystem integration | 独立 Python proxy + 未修改 vllm-ascend workers;above-the-engine,无引擎侵入 |
| Migration path | (1) 部署 stateful proxy 进程;(2) 配置 prefill/decode tier 的 kv_role;(3) 接入 MooncakeConnector;(4) 调整 $(\beta, \gamma)$ 或直接用 BR-0(零配置) |
对现有 vLLM 部署的影响: 需要从 co-located serving 迁移到 PD-disaggregated 架构——这本身是一个重大架构变更。若已有 PD-disaggregation,则 BalanceRoute 仅需插入 proxy layer(增量改动小)。BR-0 的 pool-bypass path 甚至不需要 prompt pool 基础设施。