Agentic CPU-GPU Scheduling for Heterogeneous AI Workloads — L2 #

1. TL;DR #

把异构工具调度形式化为「每个工具选 gpu_now / gpu_queue / cpu 三选一、受 VRAM 预算约束」的 DAG makespan 最小化问题；用「LLM 决策 + 算法监控器扩展观测」的协同设计，在 13 个场景全部达到暴力枚举最优映射，零离线训练，胜过 HEFT/UCB1/StarPU/all-GPU。核心是观测与决策分离。

2. Q1 / Q2 / Q3 #

Q1 — 痛点 #

现有 agentic 编排框架（LangGraph、LangChain）对所有 GPU-capable 工具默认走 GPU-first 策略，但这被证明是次优的：

• 19 个工具中真正 GPU-preferred 的只有 11 个（$s>5\times$），4 个 ambiguous（$0.5\leq s\leq 5\times$），1 个 CPU-preferred（doc_merger，$0.4\times$，因 PCIe 传输开销主导），3 个 device-neutral（无 GPU 实现）。
• 静态 profile 在运行时会失效，原因有二：Factor A（GPU 利用率争用） 让并发工具的单工具时延比隔离时高 43–250%、E2E 达隔离上界的 $2.7\times$；Factor B（VRAM 容量争用） 让 all-GPU 映射直接 OOM 而非仅仅变慢。
• 经典方法都不合适：HEFT/bandit 用固定或局部估计，抓不到争用下的全局交互；RL device placement 需要数千 episode 离线训练、跨 workload 泛化差。

Q2 — 方法 #

设计一个 agentic scheduler，把 LLM 与算法化 runtime monitor 组成闭环（Figure 2）：offline profiler 产出 tool cards → LLM scheduler 消费 cards + 运行时反馈、输出下一轮 device mapping → runtime monitor 观测执行结果、更新时延估计、在内存压力下暴露有界 what-if 探测。

核心技术壁垒：monitor 的设计原则是只扩展 LLM 能观测到的信息、绝不规定采用哪个映射（running averages / symmetric reprobe / swap reprobe / exploration hints），使 LLM 在不枚举 $3^n$ 完整映射空间的前提下，把「组合上遥远」的替代方案变成一条被实测过的 what-if 证据（详见 §7）。

Q3 — 结果 #

跨 13 个场景（串行 S1–S4、并行争用 S5–S10、VRAM 受限三选一 S11–S13）全部达到暴力枚举 oracle 映射：S1–S10 上 LLM 与 UCB1 都 10/10（HEFT-CF 2/10，StarPU 6/10），但 LLM 从 profile card 在 round 0 就达到、UCB1 需多轮探索；三选一场景 S11/S12/S13 分别在 R2/R1/R3 收敛到 oracle。零离线训练。

3. 架构 / 方法图 #

系统是三组件闭环：offline profiler → tool cards → LLM scheduler → device mapping → DAG execution → runtime monitor → 反馈回 prompt。

Paper's Figure 2, verbatim (caption: "System architecture. The offline profiler generates tool cards; the LLM scheduler selects a device mapping; the runtime monitor feeds back measured latency, feasibility, and bounded what-if probes for subsequent scheduling rounds.").

这张图是理解全文的关键：注意 monitor 位于 DAG 执行与 LLM 之间，它不计算调度，只把上一轮映射的后果转成可追加到下一轮 prompt 的观测。这正是「观测/决策分离」的物理落点。

问题本身的动机由 Figure 1 给出——同一 DAG 在 GPU-first（被争用串行化）与 dependency-aware（并行）两种放置下 E2E 差异巨大：

Paper's Figure 1, verbatim (caption: "Motivating example of heterogeneous placement for an agentic workflow ... A naive GPU-first policy may serialize execution under GPU contention, while a dependency-aware placement improves parallelism and reduces latency ...").

图中只展示 CPU/GPU 二元放置；完整形式化进一步把「立即 GPU」与「排队 GPU」在 VRAM 预算下区分开——这是本文相对经典二元调度的关键词汇扩展。

monitor 的每轮过程由 Algorithm 1 描述，其结构最好用状态流表达（原文无对应流程图）：

这里唯一的「主动」分支（reprobe → 失败触发 swap reprobe）就是 §4.5 里 S13 的 C↔B 交换被发现的机制路径。

4. 作者证明 #

无形式化作者证明 — 仅实证。 本文明确承认「no formal convergence guarantee」（§5）：monitor 引导 LLM 在 1–3 轮内到达 oracle 是本套件上的经验观察，exploration policy 仍是启发式，未证明「任意起点都能到达全局最优」。理想情况下应给出的保证是：在有界 reprobe/swap 预算下，从任意可行起点到达 oracle 的收敛性或后悔界。

尽管如此，问题的形式化 (§2.1) 是严谨的。记号表：

四个 load-bearing 方程与物理意义：

动作集（把二元放置扩为三选一，gpu_queue 是本文形式化新意）：

$$a_{v}\in\mathcal{A}=\{\texttt{cpu},\texttt{gpu\_now},\texttt{gpu\_queue}\}.$$

VRAM 预算约束（只有 gpu_now 计入同时占用；排队任务顺序 admit、等待时不占）：

$$\sum_{v\in\mathcal{G}_{\mathrm{now}}(t)}m(v)\leq M.$$

端到端时延为 sink 节点完成时间的最大值（makespan，用 max 而非 sum，因为输出以最后一个 sink 完成为准）：

$$T_{\mathrm{e2e}}(G,\pi,S)=\max_{v\in\mathrm{Sink}(G)}C_{v}.$$

目标是在依赖可行 + GPU 内存可行下最小化 makespan：

$$\min_{\pi,S}\;T_{\mathrm{e2e}}(G,\pi,S).$$

最小 6 项检查：

1. 量纲/单位一致：$\tau, C_v, T_{\mathrm{e2e}}$ 均为时间（ms）；$m(v), M$ 均为内存（MB）。✓
2. 约束覆盖三模式：cpu 不占 GPU；gpu_now 占 VRAM；gpu_queue 等待时不占、admit 时付 load 开销。三种模式与 Eq (2) 求和范围（仅 $\mathcal{G}_{\mathrm{now}}$）自洽。✓
3. 目标可行域非空：全 cpu 映射总是可行（不触碰 VRAM），故 (4) 的可行集非空。✓
4. makespan 单调性：把某工具从慢设备移到快设备（不违反约束）不会增大对应路径完成时间——与 Table 2 中 oracle 把 vector_search 移 CPU 后 E2E 从 988→812 ms 一致。✓
5. NP-hardness 归约：去掉 gpu_queue 后即「带资源容量约束的前驱约束异构调度」，已知 NP-hard；加入 gpu_queue 只扩大放置空间，难度不降。✓
6. 约束-目标耦合：VRAM 约束 (2) 与目标 (4) 通过 $\mathcal{G}_{\mathrm{now}}$ 耦合——把工具塞进 gpu_now 降低隔离时延但可能触发争用或 OOM，正是 §2.1 para 5 描述的三向 trade-off。✓

method-core 的 before/after diff（相对经典异构调度）：

before（HEFT/StarPU/RL placement）	after（本文）
二元 CPU/GPU 放置，无内存约束	三选一 {cpu, gpu_now, gpu_queue} + 显式 VRAM 预算
依赖手工 cost model 或数千 episode 训练	LLM in-context 推理，零训练
固定/局部估计，抓不到争用全局交互	monitor 把争用后果实测成 running avg / what-if 反馈
调度器自己探索完整映射（如 bandit 逐 arm）	monitor 有界 reprobe/swap 暴露替代，LLM 直接改写

5. 实验与数据 #

工具库画像是全文实证基座——19 工具在 NVIDIA RTX A5500 + AMD EPYC 7713 上隔离测 30 次取中位数：



Paper's Table 1, verbatim (caption: "The 19-tool library, profiled in isolation ... the rightmost column reports the resulting single-shot speedup CPU/(GPU+Load), which collapses below 1× for almost every tool once load cost is amortized over a single invocation.").

读者应注意最右列：gpu_queue 单次调用 speedup 对除 bert_base(1.81×)、llama_1b(2.86×)、llama_3b(3.22×) 外全部塌到 1× 以下——说明排队模式几乎从不在单次调用速度上取胜，它的价值在于可行性（VRAM 压力下）。

争用如何击穿静态 profile 由 Table 2（场景 S5）给出：



Paper's Table 2, verbatim (caption: "Per-tool latency (ms) in scenario S5. Isolated ... All-GPU ... Oracle offloads vector_search_x15 to CPU. Δ1 is All-GPU vs. Isolated; Δ2 is Oracle vs. All-GPU ...").

关键反直觉点：oracle 把 vector_search_x15 移到 CPU，它自己慢了 78%，但另外三个工具各获 18–44% 缓解，E2E 从 988→812 ms。正确决策跟随争用结构而非任一工具的隔离 profile。

主结果是归一化到 oracle 的 E2E（S1–S10，1.0 即 oracle 下界）：



Paper's Figure 5, verbatim (caption: "End-to-end latency normalized to the brute-force oracle for S1–S10 ... (a) Precedence-constrained; (b) fan-out with parallel contention. Adaptive strategies report the best of 20 rounds ...").

在高增益场景 S2/S4，agentic scheduler 冷/热启动都达 oracle，分别较 all-GPU 提速 $2.60\times$ / $2.83\times$；fan-out (b) 面板上策略分化更明显——HEFT-CF 6 个里只 1 个 4/4，StarPU 退化到 all-GPU 吃满争用惩罚。

映射精度对照见 Table 4：



Paper's Table 4, verbatim (caption: "Oracle-mapping accuracy under precedence-constrained placement (S1–S4) and GPU-utilization contention (S5–S10). Each entry reports the best match, out of four tool placements, achieved over 20 rounds. Bold entries indicate 4/4 oracle matches.").

总计：HEFT-CF 2/10、UCB1 10/10、StarPU 6/10、LLM 10/10。LLM 与 UCB1 精度打平，但 LLM 在 round 0 从 card 直达，UCB1 需逐 arm 探索——这是「同精度、更省探索」的核心卖点。

三选一 VRAM 受限结果见 Table 5：



Paper's Table 5, verbatim (caption: "Three-way placement results under explicit VRAM accounting. 'Oracle-map E2E' and 'LLM best-map E2E' report measured latency as μ±σ ... In S13, the best-found mapping differs from oracle only in off-critical-path tool D ...").

memory-aware greedy 基线在 S11/S13 分别 6837/4685 ms，而 LLM 达 oracle（S11 1715 ms、S13 1566 ms）——greedy 发现不了「把一个强 GPU 工具推到 gpu_queue 反而腾出 VRAM 放更值钱的立即 GPU 工具」。

6. 论证链 #

#	步骤	依据（paper-internal）
1	GPU-first 默认策略次优：19 工具中仅 11 真 GPU-preferred，1 个 CPU-preferred，杠杆主要来自 4 个 ambiguous 工具	Table 1 speedup 列
2	静态 profile 在运行时失效：Factor A 使单工具时延 +43–250%、E2E 达 $2.7\times$；Factor B 使 all-GPU 直接 OOM	Table 2；Table 1 Load 列；S13 R0 OOM
3	因此需要 monitor 提供 §2.3 缺失的可观测性；monitor 只扩展观测、不做决策	§2.3 收尾；§3.2 monitor 定位
4	有 profile 时 LLM 靠 ratio test 在 round 0 直出 oracle（S5：C 的 CPU 时间可藏在争用后的 GPU 瓶颈之后）；无 profile 时 monitor 的 what-if（D→gpu:625ms < 当前 best 751ms）纠正错误语义先验	Figure 3；Figure 4
5	VRAM 受限下单工具 reprobe 不够，失败触发 swap reprobe，暴露 C↔B 两工具交换（A+C=1098MB≤1100MB），R3 达 oracle	§4.5 三阶段；Algorithm 1 L3–14
6	每个 monitor 机制都必要：去掉任一机制 S13 掉到 1/4，LLM-only 直接 OOM 0/4	Appendix A / Table 6

7. 实现 cross-reference #

[实现未公开] —— L1 未记录任何开源仓库或 file:line。调度 LLM 为 DeepSeek-R1-Distill-Qwen-32B-AWQ，由 vLLM 服务，跑在与工具执行 GPU 分离的专用 GPU 上（§3.3），但代码与 prompt 完整模板未公开。最接近的可复现参照：monitor 是纯算法组件（Algorithm 1 已给伪代码），LLM 调用可用任意 vLLM/OpenAI-兼容后端复刻。

核心技术壁垒（展开）：难以复制的不是 LLM 本身、也不是任一单独探测，而是 monitor「只暴露实测证据、绝不推荐映射」的克制式接口设计。它把三类信息喂给 prompt——running averages（应对 Factor A 争用）、single-tool reprobe（应对 Factor B 单工具替代）、swap reprobe（应对必须两工具交换才能腾 VRAM 的情形）——却始终不附带 recommendation。这个「观测/决策分离」让 LLM 能在不枚举 $3^n$ 的前提下把组合上遥远的映射（如 S13 的 C↔B 交换）当作一条已被测量的 what-if 采纳，同时保留在 monitor 证据与软性 ratio 规则冲突时推翻规则的自由（Figure 4 中 round-3 flip D）。Appendix A 的消融证明四个机制互补不冗余——去掉任一个都塌到 1/4 或 OOM，说明壁垒在于机制组合 + 接口克制，而非某个单点。

关键实现细节（易漏 trick）：

1. amplified tools：base 工具太短无法产生稳定争用，作者把同一计算重复 $k$ 次构造 bert_base_x12 等放大工具，保持计算画像、把时延/内存压力缩放到研究争用所需区间（§3.1）——不做放大就复现不出 Table 2 的争用数字。
2. VRAM 测量漂移的容忍：Figure 7 显式披露 prompt 里的 mem=627/463/417 与主表 656/486/442 因重新 profiling 而不一致，但 LLM 只对「它在 prompt 里实际看到的值」推理，故收敛不受影响（Figure 7 caption）——揭示该设计对 profile 噪声的鲁棒性来自「就地观测」而非精确标定。