解耦准备与发布以实现尾部感知的代理LLM工作流调度

# 解耦就绪性与发布以实现面向尾部感知的智能体LLM工作流调度  
来源：https://arxiv.org/html/2609.10964  
冯博超 北京科技大学 中国北京  
李建江 北京科技大学 中国北京  
王浩杰 奇元实验室 中国北京  
乔林 北京科技大学 中国北京  
李英汇 奇元实验室 中国北京  
闫宇坤 奇元实验室 中国北京  
翟季东 清华大学 中国北京  
††致谢：通讯作者\。

###### 摘要  
智能体LLM工作流由交替进行的模型对话轮次与工具交互序列组成，其端到端完成时间不仅取决于推理速度，还取决于就绪轮次的释放时机。大多数运行时系统会在轮次就绪时立即释放。在资源竞争下，这种急切释放策略会积累已释放但未完成的工作；一旦提交，这些轮次就无法再被工作流层面的策略重新排序，从而增加了尾部延迟。我们提出一种尾部风险感知的轮次释放调度方法，该方法联合决定下一个释放哪个就绪轮次，以及维护多少已释放但未完成的工作量。该方法采用均值-条件风险价值（CVaR）目标来捕捉未完成工作流的演变尾部风险，在优先处理就绪轮次时融入轮次工作量的在线估计，并根据观察到的队列压力调整已释放工作预算。我们使用来自软件工程任务、多个LLM和工作流到达率的真实智能体执行轨迹来评估该方法。该方法在低负载下与急切释放表现相当，而在资源竞争下显著降低了工作流流时的P95值，实现了最高3.50倍的加速。

## 引言  
智能体LLM应用越来越多地以工作流而非孤立模型请求的形式运行，通过显式控制流、工具使用或结构化智能体程序组合多个模型调用（Khattab等 2024 (https://arxiv.org/html/2609.10964#bib.bib1)；Zheng等 2024 (https://arxiv.org/html/2609.10964#bib.bib2)；Hong等 2024 (https://arxiv.org/html/2609.10964#bib.bib3)）。典型的工作流在LLM轮次和工具执行之间交替，后续步骤依赖于先前产生的观察结果（Yao等 2023 (https://arxiv.org/html/2609.10964#bib.bib4)；Schick等 2023 (https://arxiv.org/html/2609.10964#bib.bib5)；Qin等 2024 (https://arxiv.org/html/2609.10964#bib.bib6)；Huang等 2022 (https://arxiv.org/html/2609.10964#bib.bib7)）。多个工作流可能在共享相同有限推理容量的同时并发推进。在此场景下，单个请求的延迟只是一个中间量。最终对用户重要的是工作流流时，即从工作流到达直到最后一个轮次完成的度量。这种顺序交互在涵盖网络搜索、计算机使用和通用交互任务的长期智能体环境中很常见（Liu等 2024 (https://arxiv.org/html/2609.10964#bib.bib8)；Zhou等 2024 (https://arxiv.org/html/2609.10964#bib.bib9)；Deng等 2023 (https://arxiv.org/html/2609.10964#bib.bib10)；Xie等 2024 (https://arxiv.org/html/2609.10964#bib.bib11)）。由于各阶段是顺序依赖的，当前轮次的延迟也会推迟其后的所有工具调用和LLM轮次。因此，为单个轮次所做的调度决策可能累积成端到端工作流完成时间的显著差异。

大多数智能体运行时系统隐式地将轮次就绪性与立即提交到共享LLM引擎耦合在一起（Yu等 2022 (https://arxiv.org/html/2609.10964#bib.bib12)；Kwon等 2023 (https://arxiv.org/html/2609.10964#bib.bib13)；Sun等 2024 (https://arxiv.org/html/2609.10964#bib.bib14)）。一旦满足前置依赖，新就绪的轮次就会被释放，而无需显式的调度决策。当引擎负载较轻时，这种急切释放策略几乎无害：释放的轮次能快速得到服务，很少有未完成工作积累，延迟提交带来的好处有限。但随着引擎接近饱和，情况就发生了变化。额外的释放可能只贡献很少的额外有效服务容量，但却继续增加已释放但未完成的工作量，我们称之为已承诺工作。更重要的是，已承诺的轮次不再受工作流运行时控制。当新轮次到达或工作流状态演变时，它们无法被撤回和重新考虑，导致调度器失去利用后续信息重新选择最有价值的工作流来推进的能力。这种限制并非简单的引擎排队问题。它是一个在请求进入引擎之前就产生的在线调度问题。

就绪性表明一个轮次有资格执行，但它并不决定该轮次何时应该被提交。在每个决策点，调度器必须回答两个问题：下一个应该释放哪个就绪轮次，以及是否应该释放更多工作。第一个决策决定哪个工作流获得下一次推进的机会。第二个决策决定有多少工作量变得不可撤销，以及为未来决策保留多少选择余地。这两个决策必须联合做出。如果所有就绪轮次都立即释放，排序规则几乎没有效果；而没有原则性排序规则的释放控制则无法利用工作流延迟、尾部风险和轮次工作量的差异。

为了解决上述问题，我们提出一种考虑工作流层面尾部风险的轮次释放调度算法。该算法优化一个结合了平均工作流流时与条件风险价值（CVaR）（Rockafellar和Uryasev 2000 (https://arxiv.org/html/2609.10964#bib.bib15)）的目标函数。使用该目标的占用形式，它为每个未完成的工作流分配一个瞬时延迟权重，当工作流进入尾部区域时该权重会增加。该权重除以当前轮次所需工作量的在线估计，产生一个优先级指数，该指数衡量了在单位估计推理工作量下推进一个工作流的价值。调度器还根据当前的拥塞观察维护一个释放预算。该预算定义了引擎中允许存在多少已释放但未完成的工作量，从而决定是否可以提交另一个轮次。在每个决策点，调度器首先识别当前预算允许释放的轮次，然后释放具有最大优先级指数的轮次；如果没有轮次当前可接受，则推迟释放直到系统状态改变。

总之，我们的贡献如下：  
- •我们识别了智能体LLM工作流中轮次就绪性与不可逆引擎承诺之间的隐式耦合，并将它们的分离表述为一个在线轮次释放调度问题。  
- •我们开发了一种轮次释放调度算法，该算法联合决定释放哪个就绪轮次以及是否应提交额外工作。该算法结合了从工作流尾部风险和在线轮次工作量估计导出的优先级指数，以及由观察到的引擎拥塞决定的释放预算，从而在引擎拥塞时保留未来的调度机会。  
- •我们通过匹配工作负载、跨多个工作负载轨迹、模型配置和负载水平的真实软件工程智能体轨迹的闭环重放来评估调度器。结果表明，该调度器在拥塞时保持了低负载性能，同时降低了工作流尾部延迟，工作流P95流时减少了高达71.4%，对应3.5倍的加速。

## 背景与动机  
### 智能体工作流执行  
一个工作流i在时间A_i到达，并在LLM轮次和工具阶段之间交替，直到其最终LLM轮次在时间C_i完成。我们定义其端到端流时为 T_i = C_i - A_i (1)。它包括释放等待、共享引擎执行和工具执行。由于轮次是顺序依赖的，延迟一个轮次也会推迟后续阶段。多个工作流可能并发推进，同时其LLM轮次共享相同的推理引擎。

### 拥塞下的急切释放  
一种常见的运行时策略是在轮次就绪时立即将其释放，实际上将就绪性和提交视为同一事件。这种急切释放策略在推理引擎负载较轻时效果很好。如图1 (https://arxiv.org/html/2609.10964#Sx2.F1)(a)所示，就绪轮次得到及时服务，很少有已释放但未完成的工作积累，延迟释放改善调度决策的机会很小。但随着引擎接近饱和，情况就发生了变化。图1 (https://arxiv.org/html/2609.10964#Sx2.F1)(b)说明了即使引擎已经被大量占用，新就绪的轮次仍继续被释放。这些额外的轮次可能对有效服务率贡献甚微，反而在引擎内部累积。我们将所有已释放但未完成的轮次（无论是活动还是等待中）称为已承诺轮次。一旦被承诺，轮次就留在引擎中直到完成。更重要的是，早期承诺减少了工作流运行时可用的调度灵活性。图1 (https://arxiv.org/html/2609.10964#Sx2.F1)(c)说明了这种调度选项性的损失：随着工作流老化或其状态演变，一个新就绪的轮次可能变得更有推进价值，但先前释放的轮次无法再被工作流层面的调度器撤回和重新考虑。因此，就绪性表明一个轮次有资格执行，但并不意味着立即释放总是可取的。这一区别促使了本文研究的轮次释放调度问题：下一个应该释放哪个就绪轮次，以及是否应该提交额外的工作。

图1：急切释放的负载依赖效应。在低负载下，立即释放的轮次得到快速服务，产生很少的承诺积压。在拥塞下，持续的释放导致已释放但未完成的工作在共享LLM引擎中累积，而有效服务容量没有按比例增加。当另一个轮次后来就绪或工作流变得更紧急需要推进时，先前已承诺的轮次无法被工作流运行时重新排序，导致调度选项性丧失。

## 问题表述  
### 智能体工作流与释放模型  
我们现在形式化上述执行环境。工作流i包含K_i个LLM轮次，其第k个轮次表示为v=(i,k)。连续轮次之间可能由工具执行分隔。令G_(i,k) >= 0表示轮次(i,k)之后工具阶段的持续时间。因此，就绪时间满足  
R_(i,1) = A_i, R_(i,k+1) = E_(i,k) + G_(i,k) (2)。  
因此，后续轮次的就绪性取决于前一个轮次的完成。由于每个工作流是顺序推进的，后续轮次在前一个LLM轮次及其后的工具阶段完成之前无法就绪。因此，每个活动工作流在任何时刻最多暴露一个就绪的LLM轮次。

对于每个轮次v，令R_v表示所有前置依赖完成且轮次就绪的时间。令D_v表示工作流运行时将轮次释放到共享LLM引擎的时间，令E_v表示轮次完成的时间。这些事件满足 A_i <= R_(i,k) <= D_(i,k) <= E_(i,k)。工作流i的完成时间由其最终LLM轮次决定：C_i = E_(i,K_i)。释放时间D_v将模型核心的两个状态分隔开来。在时刻t，留在引擎外的就绪轮次集合为 R(t) = {v: R_v <= t < D_v}，引擎内的轮次集合为 D(t) = {v: D_v <= t < E_v}。轮次v的释放时间 D_v 必须满足 D_v >= R_v，并且不能早于同一工作流中前一个轮次完成的时间（如果v不是第一个轮次）。此外，同一工作流内的轮次必须按顺序释放：D_(i,k+1) >= E_(i,k)。释放决策决定了哪些轮次进入引擎以及以何种顺序进入。一旦轮次v被释放（即 D_v 确定），它就被提交到引擎，直到完成（E_v），期间不能被撤回或重新调度。这种提交的不可撤销性是关键：已提交的轮次消耗了引擎资源，并锁定了工作流的调度路径，即使后来的轮次或工作流状态变化表明了更优的调度选择。

## 方法  
### 尾部风险下的轮次优先级  
到达的工作流i在时刻t的年龄为 a_i(t) = t - A_i (6)。对于任何固定阈值τ，排除与工作流完成时间无关的附加项κτ，每个工作流变分损失中依赖完成时间的部分允许占用表示  
β T_i + κ/(1-α) (T_i - τ)_+ (7)  
= ∫_{A_i}^{C_i} [β + κ/(1-α) * 1{a_i(t) > τ}] dt。  
这种表示得出了未完成工作流的瞬时持有成本率：h_i(t; τ) = β + κ/(1-α) * 1{a_i(t) > τ} (8)。量 h_i(t; τ) 是固定阈值目标在工作流i保持未完成期间增加的瞬时速率。每个未完成的工作流都获得平均流权重β。一旦其年龄超过阈值，它就获得额外的尾部风险权重κ/(1-α)。由于释放策略引发的工作流流时分布未知，我们维护其α分位数的在线估计。令T^(n)表示第n个已完成工作流的流时观测值，按完成顺序索引。从τ̂_0 >= 0开始，观测到T^(n)后，对于n >= 1，我们更新  
τ̂_n = Π_{ℝ+} [τ̂_{n-1} + ζ_{n-1} (α - 1{T^(n) <= τ̂_{n-1}})] (9)。  
这里Π_{ℝ+}表示非负实数上的投影，ζ_n > 0是步长序列。公式（9）实现了在线分位数回归：如果观测到的流时超过当前估计，估计值增加；如果低于估计值，估计值减少。这提供了对流时分布尾部的鲁棒在线跟踪。在实践中，我们使用移动窗口或衰减权重来允许分布漂移。

给定在线估计的分位数τ̂，瞬时工作流权重 h_i(t; τ̂) 指示每个未完成工作流的紧迫性。在调度决策点，我们优先处理具有高 h_i(t; τ̂) 的工作流中的轮次。然而，轮次在引擎中消耗的资源量各不相同。为了公平比较，我们定义工作流i的第k个轮次的优先级指数为：  
p_(i,k) = h_i(t; τ̂) / ŝ_(i,k) (10)。  
其中 ŝ_(i,k) 是轮次(i,k)预期工作量的在线估计。这衡量了在单位估计推理工作量下推进工作流i的价值。具有较高 p_(i,k) 的轮次应在释放时获得优先。

### 释放控制  
优先级指数解决了释放哪个轮次的问题，但没有解决释放多少工作的问题。我们引入一个基于观察到的引擎拥塞程度的释放预算。令 Q(t) 表示引擎内工作量（即已释放但未完成的工作）在时刻t的总和。我们维护一个指数平滑的拥塞指标：  
Ω(t) = λ Q(t) + (1-λ) Ω(t-Δt) (11)。  
其中 Δt 是时间步长，λ ∈ (0,1) 是平滑因子。当 Ω(t) 低于阈值 Θ 时，引擎被认为拥塞程度较低。当 Ω(t) 接近或超过 Θ 时，引擎拥塞程度较高。释放预算 B(t) 定义为引擎在拥塞程度较低时允许容纳的最大承诺工作量：B(t) = B_low 当 Ω(t) <= Θ(1-δ)，B(t) = B_high 当 Ω(t) >= Θ(1+δ)，其中 B_low > B_high 且 δ > 0。在拥塞程度较高时，预算紧缩（B_high 较低），抑制新工作提交，以防止过多承诺工作积累并保留调度灵活性。在拥塞程度较低时，预算宽松（B_low 较高），允许提交更多工作以利用可用容量。

在每个调度决策点（例如，当轮次就绪或轮次完成时），调度器执行以下操作：  
1. 计算当前承诺工作量 Q(t)。  
2. 根据 Ω(t) 确定当前释放预算 B(t)。  
3. 如果 Q(t) >= B(t)，则不释放任何新轮次（推迟释放）。  
4. 如果 Q(t) < B(t)，则从可用就绪轮次集合 R(t) 中，选择具有最高优先级指数 p_(i,k) 的轮次释放（设置其 D_v = t）。

这种策略确保仅在引擎有足够容量且释放的轮次具有高优先级时才提交新工作。它联合解决了优先级和释放控制问题，保留了调度选项性，并专注于推进对尾部风险影响最大的工作流。

## 实验设置  
我们使用来自真实软件工程智能体执行的轨迹来评估提出的方法。轨迹包括智能体解决代码修复、功能实现和调试任务时生成的工作流。每个工作流由多个LLM轮次（例如，代码生成、分析）和工具执行（例如，运行测试、读取文件）组成。我们使用多个LLM后端（例如，不同大小和速度的模型）并以可变速率重放这些轨迹以模拟不同的负载水平。我们比较以下策略：  
- **急切释放**：就绪时立即释放轮次。  
- **FIFO**：在引擎内按照释放的先进先出顺序服务轮次，但释放决策仍然是就绪时立即释放。  
- **尾部感知调度**（提出的方法）：按照方法部分描述的优先级指数和释放预算策略释放轮次。

主要度量是工作流流时（从工作流到达直到完成的时间）的分布，特别关注P50（中位数）和P95（第95百分位数）值，以评估对典型和尾部延迟的影响。

## 实验结果  
我们在多个工作负载和负载水平下评估了尾部感知调度器。图2显示了工作流流时的P95（左图）和P50（右图）相对于急切释放基线的改进（正值表示降低）。结果显示，在低负载下（归一化负载 < 0.7），所有策略表现相似，因为资源竞争很少。随着负载增加，急切释放导致尾部延迟（P95）急剧增加。相比之下，尾部感知调度器显著抑制了这种增长，在高负载下（负载 > 0.9）实现了高达71.4%的P95流时减少，对应3.5倍的加速。对于P50（中位数延迟），尾部感知调度器在低负载下略有增加（约5-10%），这是由于一些轮次的释放被延迟以保留容量，但在高负载下，它也带来了适度的减少（约15-20%），因为它避免了引擎被低优先级工作过度占用。

图3说明了调度器的运行行为。当工作流年龄（持续时间）增加时，其权重 h_i(t; τ̂) 增加，特别是当它超过估计的分位数 τ̂ 时（尾部风险增加）。因此，调度器优先处理这些较老的工作流中的轮次，即使这意味着暂时不提交新到达但年轻的轮次中的就绪轮次。这直接针对了尾部延迟。释放预算也动态变化：当引擎拥塞时，预算收紧，限制提交，直到一些工作完成；当引擎空闲时，预算扩张，允许提交更多工作以保持高利用率。

我们还进行了消融研究，分离了优先级指数和释放控制的贡献。结果显示，单独使用优先级指数（无释放控制）在非常高的负载下改善了尾部延迟，但不如组合方法有效，因为它仍然允许过多的提交。单独使用释放控制（使用简单优先级，如FIFO）在高负载下改善了尾部延迟，但不如组合方法显著，因为它没有针对最紧迫的工作流。组合使用两者提供了最佳性能，证实了联合决策的重要性。

## 结论  
本文介绍了智能体LLM工作流调度中轮次就绪性与释放决策之间的关键脱耦。我们提出了一个考虑尾部风险的调度框架，该框架联合决定了优先处理哪个就绪轮次以及维护多少已承诺工作量。实验评估表明，与传统的急切释放策略相比，我们的方法在保持低负载性能的同时，显著降低了拥塞场景下的工作流尾部延迟。未来的工作包括将该调度器集成到真实的LLM推理引擎中，探索更复杂的预算控制策略，并研究在多租户环境中的公平性方面。