Heddle: A Distributed Orchestration System for Agentic RL Rollout

A1 主要贡献

本文研究的核心问题是，在 Agentic 强化学习（RL）中，rollout（数据收集）阶段是主要的性能瓶颈，消耗了超过80%的训练时间。这一瓶颈源于 Agentic Trajectory（即LLM与外部工具的多步交互）生成时间的“长尾效应”：少数复杂的多步交互（即“掉队者”或“长尾轨迹”）显著延长了整个 rollout 的完成时间（makespan），导致大量计算资源闲置（如图1所示）。

图1：Agentic RL rollout 阶段的掉队者效应。短轨迹完成后，资源会闲置等待长尾轨迹。
图1：Agentic RL rollout 阶段的掉队者效应。短轨迹完成后，资源会闲置等待长尾轨迹。

为了精确分析此瓶颈，作者将全局 rollout makespan 公式化为批次中最慢轨迹 T 的完成时间：

公式1
公式1

该公式揭示了三个可优化的系统问题，这些问题共同导致了长尾轨迹的执行效率低下：
1. 排队延迟（$T_{queue}$）：现有的“以步骤为中心”（step-centric）的调度策略（如轮询）忽略了轨迹的上下文，导致长尾轨迹在多个步骤中反复排队，累积了严重的延迟。
2. 干扰开销（$N_{tokens}^{(i)} \cdot T \cdot \alpha^{(i)}$）：不合理的任务放置（placement）策略会导致长尾轨迹与大量短轨迹在同一设备上执行，增加了计算和内存竞争，从而放大了干扰系数 $\alpha$，增加了每个 token 的生成时间。
3. 过高的单位token时间（$T$）：僵化和同构的资源分配策略未能为长尾轨迹（延迟敏感）分配更高模型并行度的资源来加速计算，导致基础的单位 token 时间过长。

针对上述问题，本文提出了 Heddle，一个以“轨迹为中心”（trajectory-centric）的分布式系统，旨在通过优化 Agentic RL rollout 执行的时间（when）、地点（where）和方式（how）来解决长尾瓶颈。

Heddle 的核心创新和贡献如下：
- 严谨的瓶颈分析：首次将 rollout makespan 分解为排队延迟、干扰开销和单位 token 时间三个关键瓶颈，为系统优化提供了清晰的目标。
- 轨迹级调度（Trajectory-level Scheduling）：通过运行时预测和渐进式优先级调度，动态识别并优先执行长尾轨迹，最小化其累积排队延迟（$T_{queue}$）。
- 轨迹感知放置（Trajectory-aware Placement）：采用预排序动态规划和机会性迁移相结合的策略。初始阶段，它将长尾轨迹和短轨迹在空间上隔离，以最小化干扰系数 $\alpha$；运行时，利用工具调用的空闲间隙进行无阻塞的轨迹迁移，纠正预测偏差。
- 轨迹自适应资源管理（Trajectory-adaptive Resource Management）：打破同构资源分配的限制，为延迟敏感的长尾轨迹分配高模型并行度的资源以降低单位 token 时间 $T$，同时为吞吐量敏感的短轨迹分配低模型并行度的资源。
- 系统实现与评估：实现了 Heddle 系统，并在多种 Agentic RL 负载下进行评估，结果表明 Heddle 能有效解决长尾瓶颈，与最先进的基线系统相比，端到端 rollout 吞吐量最高提升了 2.5 倍。

图2：编码 Agent 的长尾分布。输出 token 数和工具执行时间的分布都高度倾斜。
图2：编码 Agent 的长尾分布。输出 token 数和工具执行时间的分布都高度倾斜。
图3：现有的 Agentic RL 框架。LLM 生成和工具执行被解耦，导致了以步骤为中心的（step-centric）设计，忽略了轨迹的整体性。
图3：现有的 Agentic RL 框架。LLM 生成和工具执行被解耦，导致了以步骤为中心的（step-centric）设计，忽略了轨迹的整体性。

A3 背景知识与关键挑战

2.1 Agentic RL

Agentic 强化学习（Agentic RL） 将大型语言模型（LLM）提升为能够与动态环境交互的自主代理。与静态推理任务不同，Agentic RL 使 LLM 能够在多步 rollout 过程中综合高级计划并执行决策。在 rollout 阶段，LLM 代理生成多步轨迹：在每一步中，它会生成逻辑推理、调用外部工具，并观察结果状态以调整下一步行动，这个循环持续到达到终止状态。在训练阶段，积累的交互轨迹用于通过 PPO 【【35，Proximal policy optimization algorithms，2017，arXiv】】 或 GRPO 【【36，Deepseekmath: Pushing the limits of mathematical reasoning in open language models，2024，arXiv】】 等算法优化代理的策略。例如，一个编码代理在处理一个高级编程需求时，会生成一个多步轨迹，包括制定计划、检索代码库、生成代码片段、触发验证测试，并根据反馈进行迭代调试。如图1所示，这个循环过程将标准的单次推理请求转变为一个由 LLM 生成和外部工具执行复杂交错的长期运行的 Agentic 轨迹。Agentic RL 是 Claude Code 【【7，Claude 3.7 Sonnet and Claude Code，2025，Anthropic】】、Deep Research 【【30，Introducing Deep Research，2025，OpenAI】】 和 OpenClaw 【【4，OpenClaw — Personal AI Assistant，2026，GitHub】】 等生产级系统的基础，这些系统通过长期的工具交互来解决复杂任务。随着 Agentic RL 集成到 LLM 开发流程中，rollout 效率成为关键瓶颈。

2.2 系统特性

标准的 RL 训练步骤包括三个阶段：(1) rollout（轨迹生成），(2) inference（奖励和参考计算），以及 (3) training（策略模型更新）。如先前工作【【17，Taming the long-tail: Efficient reasoning rl training with adaptive drafter，2025，arXiv】】、【【33，Seer: Online context learning for fast synchronous llm reinforcement learning，2025，arXiv】】所量化，rollout 阶段主导了 RL 训练流程，其瓶颈根本上源于显著的“掉队者效应”（straggler effect）。这种掉队者效应源于 Agentic 轨迹固有的长尾分布。如图2所示，对于一个代表性的编码代理任务，token 生成和工具执行时间都高度倾斜。虽然大多数轨迹计算量小且能快速终止，但一小部分需要广泛的多步推理和长时间的工具交互。在同步框架中，这些异常值成为主要的掉队者，迫使整个集群闲置，从而极大地增加了完成时间（makespan）并降低了 RL 训练吞吐量。

图4：归一化的 Agentic 轨迹完成时间的累积分布函数（CDF）。
图4：归一化的 Agentic 轨迹完成时间的累积分布函数（CDF）。

最终，rollout 的完成时间由最长的轨迹决定。为了量化这一点，图4展示了使用 Verl 【【37，Hybridflow: A flexible and efficient rlhf framework，2025，EuroSys】】 和 SGLang 【【57，Sglang: Efficient execution of structured language model programs，2024，NeurIPS】】 进行 Agentic RL rollout 时的轨迹完成时间分布，该时间已根据最大时间进行归一化。分析显示出严重的延迟尾部，最大完成时间超过中位数的4倍以上。由于 token 数量（$N_{tokens}$）是算法内生的，而工具执行（$T_{tool}$）被卸载到弹性的无服务器基础设施【【5，Function Compute，2026，Alibaba Cloud】】、【【6，AWS Lambda，2014，Amazon Web Services】】、【【21，Ditto: Efficient serverless analytics with elastic parallelism，2023，ACM SIGCOMM】】、【【55，Jolteon: Unleashing the promise of serverless for serverless workflows，2024，USENIX NSDI】】，我们的公式（公式1）分离出三个以 GPU 为中心的目标：排队延迟（$T_{queue}$）、由竞争引起的干扰开销（$N_{tokens} \cdot (\alpha - 1) \cdot T$）和基础单位 token 时间（$N_{tokens} \cdot T$）。基础单位 token 时间是指在批处理大小为1时，无竞争情况下的平均 token 生成时间。

2.3 挑战

基于系统特性分析，我们识别出 Agentic RL rollout 优化中的三个关键挑战：最小化排队延迟的调度问题、最小化干扰开销的放置问题，以及最小化基础单位 token 时间的资源分配问题。

调度（Scheduling）。如图3所示，现有框架【【3，Slime: An LLM post-training framework for RL Scaling，2025，GitHub】】、【【37，Hybridflow: A flexible and efficient rlhf framework，2025，EuroSys】】将 LLM 生成与工具执行解耦，将每个步骤视为无状态请求。因此，调度默认采用轮询（round-robin）【【15，Performance modeling and design of computer systems: queueing theory in action，2013】】策略，这种策略忽略了 Agentic 轨迹的整体性，迫使长尾轨迹在多个步骤中累积过多的排队延迟。虽然基于时长的优先级调度是一种潜在的解决方案，但 Agentic rollout 的高度随机性使得静态预测无效。如图5所示，相同的提示（prompt）由于动态的环境反馈，经常产生长度差异极大的轨迹。例如，共享同一提示的两个轨迹 $t_1$ 和 $t_2$ 可能生成相似的初始代码；但如果 $t_2$ 未通过示例测试，它会触发多个修正步骤，从而极大地延长其轨迹。这种不可预测性使得最小化排队延迟成为一个根本性挑战。

图5：不同提示下的轨迹长度分布。相同提示（例如，prompt index 15附近）可以产生长度差异巨大的轨迹（如 $t_1$ 和 $t_2$）。
图5：不同提示下的轨迹长度分布。相同提示（例如，prompt index 15附近）可以产生长度差异巨大的轨迹（如 $t_1$ 和 $t_2$）。

放置（Placement）。现有框架【【3，Slime: An LLM post-training framework for RL Scaling，2025，GitHub】】、【【37，Hybridflow: A flexible and efficient rlhf framework，2025，EuroSys】】依赖于缓存亲和性（cache-affinity）或最少负载（least-load）放置策略，但这两种策略都无法缓解掉队者效应。缓存亲和性策略将轨迹静态绑定到特定的 rollout worker 以最大化前缀缓存命中率。然而，未知的轨迹时长不可避免地会引发严重的负载不平衡，导致一些 worker 过早空闲，而另一些则因长尾轨迹而停滞。相反，最少负载均衡策略在每一步都重新分配轨迹，这会产生高昂的缓存重计算开销，并通过将长尾轨迹与众多短轨迹放置在一起，加剧了长尾轨迹的干扰系数 $\alpha$。如图6所示，均衡 worker 负载无意中导致长尾轨迹在更高的批处理大小下执行，通过增加内存和计算竞争而增加了单位 token 时间。最终，现有的放置方法因缺乏对 Agentic RL rollout 的全局、轨迹感知的视角而无法解决掉队者问题。

图6：长尾轨迹的干扰。随着批处理大小的增加，长尾轨迹的归一化最大完成时间显著增加。
图6：长尾轨迹的干扰。随着批处理大小的增加，长尾轨迹的归一化最大完成时间显著增加。

资源管理（Resource Management）。现有框架【【3，Slime: An LLM post-training framework for RL Scaling，2025，GitHub】】、【【37，Hybridflow: A flexible and efficient rlhf framework，2025，EuroSys】】在所有 rollout worker 上强制执行僵化、同构的 GPU 配置，忽略了 Agentic 轨迹的内在异构性。具体来说，大量的短轨迹是吞吐量受限的，它们受益于较低的模型并行度（MP）以最小化相对通信开销。相反，长尾轨迹是延迟受限的，需要较高的 MP 来减少单位 token 时间。如图7所示（其中 4x2 表示4个 worker，每个 worker 2个GPU），存在一个延迟-吞吐量的权衡：扩展数据并行性可以最大化吞吐量，但牺牲了模型并行性，严重增加了单位 token 时间。因此，如图11(a)所示，每个 worker 处理一个 Agentic 轨迹。在同构配置下，资源配置不足的长尾轨迹会产生更高的单位 token 时间。这种不匹配需要轨迹自适应的资源管理，动态调整 MP 度数以使 GPU 资源与特定的工作负载需求相匹配。

图7：不同资源分配策略下的性能。随着模型并行度的增加，单位 token 时间减少，但总吞吐量也随之下降。
图7：不同资源分配策略下的性能。随着模型并行度的增加，单位 token 时间减少，但总吞吐量也随之下降。

Heddle 概览

我们提出了Heddle，一个通过解耦设计（如图8所示）来缓解 Agentic RL 掉队者问题的分布式系统。它将全局编排与本地执行分离：一个控制平面（control plane）负责决定轨迹执行的时间（when）、地点（where）和方式（how），而一个数据平面（data plane）则处理底层的运行时任务。

图8：Heddle 概览。
图8：Heddle 概览。

控制平面（Control Plane）。控制平面是 Heddle 的中央大脑，维护着集群资源和 Agentic 轨迹状态的全局视图。它由三个协同工作的模块组成，共同优化 rollout 过程。
- 轨迹级调度器（when）。调度器使用一个可训练的运行时预测器，该预测器融合了静态提示分析和动态运行时上下文来估计轨迹长度。由于随着轨迹上下文的积累，预测保真度单调提高，调度器采用渐进式优先级调度。通过迭代地优化长度估计，它提升长尾轨迹的优先级，给予它们执行优先权，以最小化累积排队延迟（$T_{queue}$）。
- 轨迹感知放置器（where）。该组件通过一个两阶段策略将 Agentic 轨迹映射到 rollout worker。初始阶段，预排序动态规划在空间上将长尾轨迹与短轨迹分离开，以最小化长尾轨迹的干扰系数（$\alpha$）。在运行时，该引擎监控因预测精度变化（例如，最初被错误分类的长尾轨迹）而导致的负载偏差。一旦检测到，它会触发机会性的轨迹迁移，指示数据平面在非阻塞的工具执行间隙迁移轨迹。
- 资源管理器（how）。该组件用一个轨迹自适应的资源分配计划取代了同构配置，该计划根据每个 Agentic 轨迹的特定并行需求量身定制。它为延迟敏感的长尾轨迹分配高模型并行度（MP）以加速单位 token 时间（$T$），同时为以吞吐量为导向的短轨迹使用较低的 MP 度数。

工具管理器（Tool Manager）。工具管理器通过弹性的无服务器后端来协调工具调用，消除了集群管理的开销。通过利用 FaaS 优化【【26，ORION and the three rights: Sizing, bundling, and prewarming for serverless {DAGs}，2022，USENIX OSDI】】、【【55，Jolteon: Unleashing the promise of serverless for serverless workflows，2024，USENIX NSDI】】，它有效地缓解了冷启动延迟并吸收了 Agentic rollout 期间的瞬时计算爆发。按使用付费的计费模式相比于过度配置的静态资源，降低了总拥有成本。

数据平面（Data Plane）。数据平面由一组自适应的 rollout worker 组成，它们执行密集的 Agentic 工作负载。在收到控制平面的指令后，这些 worker 会实例化异构的 worker，以协调模型推理和工具执行的交错进行。
- 机会性状态迁移。数据平面通过利用模型推理和工具执行之间的自然边界来掩盖迁移开销。当一个轨迹触发工具调用时，worker 会释放其 GPU 资源。Heddle 利用这个空闲间隙执行轨迹迁移，将 KV 缓存传输到控制平面指定的目标 worker，而不会阻塞关键执行路径。
- 运行时遥测。数据平面通过将实时的执行指标（如当前轨迹上下文、工具执行延迟和缓存使用情况）流式传输回控制平面，从而闭合反馈循环。这些遥测数据使运行时轨迹预测器能够纠正其估计，并使调度器能够为后续步骤优化优先级。

A2 方法细节

4 轨迹级调度器

为了缓解公式1中长尾轨迹的排队延迟，我们提出了轨迹级调度，将 agentic rollout 从以步骤为中心的范式转变为以轨迹为中心的范式。由于这种方法依赖于轨迹识别，我们首先引入渐进式轨迹预测，以在运行时动态识别潜在的长尾轨迹。

4.1 渐进式轨迹预测

问题。传统的提示分析方法【【16，History rhymes: Accelerating llm reinforcement learning with rhymerl，2025，arXiv】】、【【33，Seer: Online context learning for fast synchronous llm reinforcement learning，2025，arXiv】】、【【59，Streamrl: Scalable, heterogeneous, and elastic rl for llms with disaggregated stream generation，2025，arXiv】】依赖于静态机制，即使用历史数据预先估计 agentic 轨迹的长度。然而，这些方法无法捕捉 agentic rollout 的动态、多步特性。在像 PPO 【【35，Proximal policy optimization algorithms，2017，arXiv】】和 GRPO 【【36，Deepseekmath: Pushing the limits of mathematical reasoning in open language models，2024，arXiv】】这样的 RL 算法中，一个单一的提示会为优势估计生成一组 agentic 轨迹样本。为了鼓励探索，通常会采用高采样温度，这天生就会导致高的输出方差。此外，轨迹长度还由动态的环境反馈决定。例如，在一个编码代理中，相同的提示可能会产生不同的轨迹：$t_1$ 可能在一步内通过示例测试用例，而 $t_2$ 可能需要多个修正步骤，从而显著延长 $t_2$ 的生命周期。因此，如图5所示，同一组内的轨迹表现出显著的长度差异（即组内方差）。这种运行时的随机性使得静态预测对于精确的 agentic 轨迹预测是无效的。

图9：渐进式轨迹预测。预测器利用累积的上下文（包括LLM生成和工具输出）来逐步优化长度估计，并且预测过程与工具执行并行，以掩盖开销。
图9：渐进式轨迹预测。预测器利用累积的上下文（包括LLM生成和工具输出）来逐步优化长度估计，并且预测过程与工具执行并行，以掩盖开销。

方法。我们提出渐进式轨迹预测，以利用 agentic 交互的迭代特性。如图9所示，随着 LLM 生成和工具输出丰富了 agentic 轨迹的上下文，预测器会单调地优化长度估计。值得注意的是，初始步骤的执行计划作为一个强烈的语义指标，为预测提供了一个准确的早期估计。为了训练预测器，我们收集历史轨迹并将其分解为（上下文，剩余长度）元组。我们利用这些数据来微调一个轻量级的预训练回归模型（即 Qwen-0.6B）。在运行时，Heddle 在每一步之后调用这个模型来更新估计，并逐步减少不确定性。我们通过高效的模型设计解决了潜在的开销问题。首先，训练成本微不足道。这个轻量级的回归模型只需要几分钟就能收敛。其次，作为微服务部署，该模型由于其紧凑的参数大小，产生的推理延迟可以忽略不计。至关重要的是，如图9所示，预测是与工具执行异步执行的。这种并行性有效地掩盖了推理成本，确保了 agentic 轨迹的关键路径上没有额外的开销。

4.2 渐进式优先级调度

问题。如图3所示，现有的 Agentic RL 框架【【3，Slime: An LLM post-training framework for RL Scaling，2025，GitHub】】、【【37，Hybridflow: A flexible and efficient rlhf framework，2025，EuroSys】】是为无状态交互设计的，通常将 LLM 生成与工具执行解耦。在这种范式下，系统将一个 Agentic 轨迹看作是一个零散的独立请求序列，而不是一个连续的生命周期。因此，调度默认采用与轨迹无关的轮询策略，其中执行量子被严格限制为单个步骤，而不管轨迹的累积进度如何。具体来说，每当一个轨迹从工具执行返回时，它都被视为一个新的 LLM 生成请求，并被置于等待队列的末尾。对于一个需要 $N$ 个步骤的长尾轨迹，这在 $N$ 个不同的调度轮次中施加了反复的排队惩罚。通过对长尾轨迹施加复合的排队延迟，这种方法对全局 rollout 的完成时间（makespan）是有害的。

算法1：渐进式优先级调度。
算法1：渐进式优先级调度。

方法。为了优化 rollout 的完成时间，我们使用了渐进式优先级调度（Progressive Priority Scheduling, PPS），这是对最长处理时间优先（Longest-Processing-Time-First, LPT）原则【【13，Bounds on multiprocessing timing anomalies，1969，SIAM journal on Applied Mathematics】】的一种自适应近似。LPT 通过严格优先处理长时任务来最小化批处理的完成时间，从而减轻了由尾部掉队者引起的集群范围的空闲。PPS 通过将渐进式轨迹预测动态地映射到调度优先级来实施这一原则。随着执行的展开和预测保真度的提高，PPS 会对每个 rollout worker 的待处理队列中的 LLM 推理请求进行重新排序。这确保了被识别出的长尾轨迹能优先于短轨迹获得执行权。为了严格执行 LPT 原则，我们在 SGLang 【【57，Sglang: Efficient execution of structured language model programs，2024，NeurIPS】】中集成了抢占式执行。该机制将优先级扩展到等待队列之外，使得高优先级的待处理生成请求能够中断正在执行的低优先级请求。具体来说，每当一个待处理请求的优先级高于最低优先级的活动请求时，系统会抢占优先级最低的活动请求，将其放回等待队列，同时保留其前缀缓存。高优先级请求则立即被提升到新空出的位置。这保证了高优先级请求的即时执行，从而显著减少了长尾轨迹的排队延迟。算法1展示了详细的伪代码。

5 轨迹感知放置

为了缓解公式1中长尾轨迹的干扰因子，我们提出了轨迹感知的放置策略。我们首先将放置优化问题进行形式化。随后，我们介绍了我们的解决方案：最优的预排序动态规划算法，并辅以运行时轨迹迁移。

5.1 问题形式化

在 Agentic rollout 中，部署了多个 LLM rollout worker 以通过并行批处理机制并发执行轨迹。然而，这由于 GPU 资源竞争，不可避免地为 token 计算带来了干扰。我们假设平均基础单位 token 时间（批大小=1）是一个常数 $T$，并让 $L$ 表示轨迹长度函数。给定 $n$ 个 Agentic 轨迹 {$t_1, . . . , t_n$} 和 $m$ 个 LLM rollout worker，我们寻求一个分区策略 {$g_1, . . . , g_m$}，其中 $g_i$ 包含一组 Agentic 轨迹 {$t_{i1}, . . . , t_{ik}$}，并且 $g_i$ 被分配给第 $i$ 个 worker。我们将 $F(g_i)$ 定义为组 $g_i$ 的干扰因子。为了最小化全局 rollout 的完成时间，我们将优化目标定义为：

公式2
公式2

目标是最小化 $m$ 个组的完成时间，其中组的执行时间是其干扰因子与其最长轨迹时长的乘积。这个优化问题本质上是 NP-hard 的。在异构设置中（即 worker 的资源配置不同），搜索空间按 $O(m^n)$ 扩展；即使在同构情况下，复杂度也由第二类斯特林数 $S(n, m)$【【40，Enumerative combinatorics volume 1 second edition，2011，Cambridge studies in advanced mathematics】】决定。这种组合爆炸使得精确枚举不可行。此外，干扰函数 $F$ 缺乏封闭形式的解析表达式，这阻止了使用现成的求解器。这些障碍排除了在 Agentic RL rollout 期间进行精确求解的可能性，因此需要我们专门的预排序动态规划算法。

5.2 预排序动态规划

我们的放置算法基于一些简化的前提。首先，我们假设轨迹长度是先验已知的。由于初始预测仍然存在估计误差（§ 4.1），我们通过轨迹迁移（§ 5.3）来处理预测偏差。其次，我们将集群建模为具有相同资源配置的同构 worker。我们将在 § 6 中放宽此约束，将我们的解决方案扩展到异构 worker 配置。最后，我们假设干扰因子是一个单调递增的函数，仅由 Agentic 轨迹组的大小决定，这个属性在标准工作负载下经验性地成立。

我们得出了一个关键的结构性洞察：
引理 5.1. 给定按长度降序排列的 Agentic 轨迹，存在一个最优分区策略，其中每个组都构成排序后列表的一个连续子序列。
证明：考虑一个最优分区，其中有两个（可推广到 $m$ 个）组 $g_1$ 和 $g_2$，其中 $t_1 \in g_1$ 且 $L(t_1) \ge \dots \ge L(t_n)$。假设该分区不连续。那么存在 $t_i \in g_2$ 使得 $L(t_i) > L(t_{i+1})$，其中 $t_{i+1} \in g_1$。我们交换 $t_i$ 和 $t_{i+1}$。由于组的大小不变，根据前述前提，干扰因子 $F(g_1)$ 和 $F(g_2)$ 保持不变。在 $g_1$ 中，完成时间仍然由 $t_1$ 决定，因为 $L(t_1) \ge L(t_i)$，所以 $g_1$ 的完成时间不变。在 $g_2$ 中，用较短的 $t_{i+1}$ 替换 $t_i$ 确保了最大轨迹长度不增加。因此，全局 rollout 的完成时间不增加。通过迭代交换最终会得到一个满足引理 5.1 的连续分区 {$g^*_1, g^*_2$}，而不会增加原始最优分区的 rollout 完成时间。

利用这一洞察，我们按降序对 Agentic 轨迹进行预排序，并对分区施加连续性约束，这保证了在此约束下导出的最优解是全局最优的。

动态规划。在预排序的基础上，我们的问题变得类似于线性划分问题【【39，The Algorithm Design Manual，2020】】。连续分区约束将搜索空间从第二类斯特林数 $S(n, m)$ 减小到 $\binom{n-1}{m-1}$。虽然显著减小，但这个数量级对于运行时枚举来说仍然是难以处理的。为了解决这个问题，我们提出了一个动态规划算法，该算法能有效地解决最优分区问题。
- 状态初始化。我们定义 $dp[i][j]$ 为将前 $i$ 个轨迹划分到 $j$ 个 worker 上的最优完成时间。初始化侧重于单个 worker 的情况（$j = 1$）。对于 $i \in [1, n]$，我们设置 $dp[i][1] = L(t_1) \times T \times F({t_1, \dots, t_i})$，边界条件为 $dp[0][0] = 0$。在此公式中，$L(t_1)$ 代表最大轨迹长度，$F$ 捕捉了干扰因子，$T$ 表示基础单位 token 时间。
- 状态转移。状态转移函数定义如下：

$$\begin{aligned} dp[i][j]=\min_{k=1}^{i-1}\max\left\{\begin{aligned}&dp[k][j-1],\\&L(\tau_{k+1})\times T\times F(\{\tau_{k+1},\dots,\tau_i\})\end{aligned}\right\} \end{aligned}$$

公式3递归地识别出将第 $j$ 个组与前 $j-1$ 个组分开的最优划分索引 $k$。变量 $k$ 遍历所有可行的分割位置（即 $k \in [1, i-1]$），将 {$t_1, \dots, t_k$} 分配给前面的 worker，将 {$t_{k+1}, \dots, t_i$} 分配给当前的第 $j$ 个 worker。内部的 max 运算符模拟了并行执行的特性，即全局完成时间由最慢的 worker 的完成时间决定。关键是，由于是降序排序，$L(t_{k+1})$ 代表了当前组中的主导长度。最后，外部的 min 运算符选择最小化全局完成时间的 $k$，确保了 worker 之间的负载均衡。

预排序和动态规划的结合产生了基于引理 5.1 的全局最优解。图10说明了该算法的流程。其时间复杂度为 $O(n^2m)$，相比于组合基线的 $O(\binom{n-1}{m-1})$ 大大降低。然而，对于大规模工作负载，$O(n^2m)$ 仍然计算量巨大。为了进一步减轻开销，我们在排序后聚合低于定义阈值的短轨迹。这种启发式方法减少了有效输入大小 $n$，在对解决方案质量影响可忽略的情况下显著加速了执行。

图10：放置算法的图示。该算法包括输入预排序、动态规划求解和系统执行三个阶段。
图10：放置算法的图示。该算法包括输入预排序、动态规划求解和系统执行三个阶段。

为了导出干扰因子 $F(g_i)$，我们采用基于性能分析器的模拟方法。我们首先构建一个性能分析器，来刻画在不同批处理大小下的单位 token 时间。这些性能数据被输入到一个模拟器中，该模拟器模拟 $g_i$ 中轨迹的并发执行，捕捉依赖于批处理的干扰和排队延迟。我们实现了一个轻量级的、基于 Rust 的路由器来分发 LLM 生成请求。该组件维护必要的轨迹元数据，包括放置分配、预测长度和预排序排名。在初始化期间，路由器与 LLM rollout worker 同步。然后，它从控制平面接收分区策略，并将每个轨迹路由到其指定的 worker，严格执行从预排序动态规划中导出的放置决策。

5.3 轨迹迁移

预排序动态规划算法在假设预测完全准确的情况下优化放置。然而，如 § 4.1 所述，仅基于提示的估计存在固有的方差。完全依赖这种静态分配会加剧未预料到的长尾轨迹的资源竞争。为了缓解这个问题，我们采用了一种运行时机制，根据渐进式的预测更新来调整放置。

我们采用轨迹迁移来动态纠正负载不平衡。当一个轨迹的预测长度更新时，轨迹路由器会确定其在排序顺序中的新排名。为避免重新运行昂贵的动态规划算法，我们按比例调整原始分区的大小，这些大小由每个组的大小 {$c_1, \dots, c_m$} ($c_i = |g_i|$) 定义，与剩余活动轨迹的数量 $n^*$ 成比例。具体来说，第 $i$ 个组的有效容量变为 $c_i \times \frac{n^*}{n}$。利用这些调整后的大小，路由器为轨迹的新排名确定合适的 worker，并在目标 worker 与当前主机不同时执行迁移。为了减轻长尾轨迹的预填充（prefill）开销，我们实现了一种实时的 KV 缓存迁移机制。在重新分配时，路由器识别出驻留的前缀缓存，并通过 GPU-Direct RDMA 启动到目标 worker 的直接传输，确保高吞吐量和低延迟的传输。为了管理并发迁移并防止端点冲突，我们实现了一个轨迹感知的传输调度器。路由器按轨迹长度的降序对迁移请求进行优先级排序。在每个调度周期中，它贪婪地选择最长的可用轨迹的迁移请求，跳过任何与已选择或正在运行的迁移请求共享源或目标 worker 的请求。这个传输调度器迭代地构建严格并行、不冲突的迁移请求批次。通过优先处理长轨迹并强制端点独占，该策略最大化了带宽利用率，同时确保了关键长尾轨迹的及时迁移。

6 轨迹自适应资源管理器

为了在保持短轨迹高吞吐量的同时，降低长尾轨迹的基础单位 token 时间（公式1中的 $T$），我们提出了一个轨迹自适应的资源管理器。我们正式定义了分配问题，并采用模拟退火算法来高效地收敛到近优解。

6.1 问题形式化

在Heddle的 Agentic rollout 中，我们部署了具有异构资源配置和模型并行策略的多个LLM worker。如图11(b)所示，我们的核心洞察是为长尾轨迹配置具有更高模型并行度的 worker（以最小化单位 token 时间），同时为短轨迹分配具有较低模型并行度的 worker（以最大化吞吐量）。形式上，我们在 $m$ 个 worker 之间分配总共 $N = \sum_{i=1}^{m} N_i$ 的GPU预算，这些 worker 的模型并行度（MP）为 {$m_1, \dots, m_m$}。转向异构 worker 使得原始的放置问题（§ 5.1）变得复杂，因为它需要联合优化轨迹分区 {$g_i$} 和MP分配 {$m_i$}。为了保持问题的可解性，我们将其分解为两个可管理的子问题，即映射和资源分配，通过一个两阶段的启发式方法——排序初始化的模拟退火来解决。

图11：异构资源分配的洞察。(a) 同构配置下，长尾轨迹导致资源闲置。(b) 异构配置下，为长尾轨迹分配更高模型并行度（MP=4）可以减少其执行时间，从而缩短整体完成时间。
图11：异构资源分配的洞察。(a) 同构配置下，长尾轨迹导致资源闲置。(b) 异构配置下，为长尾轨迹分配更高模型并行度（MP=4）可以减少其执行时间，从而缩短整体完成时间。

6.2 排序初始化的模拟退火

映射。我们映射策略的关键洞察是，在§ 5.2中建立的轨迹排序可以作为一个强有力的结构性先验。具体来说，分区{$g_1, \dots, g_m$} 本身就是按照它们的预测长度降序排列的。由于我们的目标是将长尾轨迹分配给具有更高模型并行度的 worker（以最小化单位 token 时间），我们同样将 worker 资源{$w_1, \dots, w_m$}按照它们的模型并行度降序排列。然后，我们确定性地将第 $i$ 个轨迹分区 $g_i$ 分配给拥有 $N_i$ 个GPU的第 $i$ 个 worker。

资源分配。优化GPU分配{$N_1, \dots, N_m$}至关重要，因为每个 $N_i$ 决定了分区 $g_i$ 的单位 token 时间以及最终的全局完成时间（§ 5.1）。一个简单的基线方法是穷举所有有效的分配，对每种分配通过预排序动态规划（DP）算法评估完成时间，并选择全局最小值。然而，单次DP执行需要O($n \cdot m^2$)的时间，对于 $n = 6400$ 和 $m = 16$ 的情况，大约需要42毫秒（§ 7.5）。考虑到总GPU预算 $N = \sum_{i=1}^{m} N_i$，有效分配的数量与 $\binom{N-1}{m-1}$ 成比例。因此，在这个组合爆炸的空间中进行穷举搜索在计算上是不可行的。

为了有效地探索这个空间，我们使用模拟退火启发式算法。我们通过一个随机化、排序的分配来初始化搜索：每个容量 $N_i$ 从预定义的模型并行度中采样，然后将得到的数组按降序排序。我们将初始退火温度设置为初始状态的估计完成时间，该时间是通过应用排序初始化的映射并执行预排序DP算法来确定轨迹放置而计算得出的。在每次搜索迭代中，我们通过随机应用三种状态转换之一来扰动当前分配：重新分配、拆分或合并。虽然我们无条件地接受能够减少总体完成时间的提议分配，但我们也以一个与温度相关的概率接受次优状态，以逃离局部最优。当温度降到预定阈值 $\epsilon$ 以下时，搜索终止，从而为 Agentic rollout 产生最终配置。算法2详细描述了此伪代码。

算法2：排序初始化的模拟退火。
算法2：排序初始化的模拟退火。

通过将排序初始化的映射与基于模拟退火的分配相结合，我们创建了一个强大的异构管理启发式算法。前者将长尾轨迹与高MP worker对齐，后者则在组合搜索空间中导航以优化GPU供应。这些机制共同减轻了长尾轨迹的计算瓶颈，并保持了短轨迹的吞吐量，最终最小化了全局 rollout 的完成时间。

A4 实验环境

A5 实验结果

7.1 总体性能

实验内容：对比 Heddle 与 Slime、Verl 和 Verl 在三种不同工作负载（编码、搜索、数学）和三种模型规模（Qwen3-8B, 14B, 32B）下的端到端 rollout 吞吐量（tokens/s）。
实验结果：如图12所示，Heddle 在所有测试场景下均显著优于基线系统。具体来说，Heddle 的吞吐量比 Verl 提升了 1.4-2.3倍，比 Verl 提升了 1.1-2.4倍，比 Slime 提升了 1.2-2.5倍。
分析结论：性能提升随着模型规模的增加而更加显著，因为大模型会加剧计算和内存竞争，从而放大长尾轨迹的干扰效应，严重影响基线系统性能。Heddle 通过其轨迹感知的放置策略有效缓解了这一瓶颈。基线系统之间，Slime 在编码和数学任务上表现较好，因为它通过定制的路由器缓解了负载不均；而 Verl 在搜索任务（序列短、交互频繁）上表现更好，因为其缓存感知策略在这种场景下更有效。Heddle 的策略则同时优化了缓存命中率和长尾干扰，因此在所有任务上都取得了最佳性能。

图12：不同工作负载和模型下 Agentic RL 系统的 rollout 吞吐量。Heddle 在所有配置下均表现最佳。
图12：不同工作负载和模型下 Agentic RL 系统的 rollout 吞吐量。Heddle 在所有配置下均表现最佳。

7.2 轨迹级调度的有效性

实验内容：

  1. 预测精度：评估 Heddle 的渐进式轨迹预测器与两种基于提示的基线（模型驱动和历史数据驱动）的精度。指标为长尾轨迹的召回率和预测长度与实际长度的皮尔逊相关系数。
  2. 调度性能：将 Heddle 的渐进式优先级调度（PPS）与 FCFS、Round-Robin (RR) 和 Autellix【【25，Autellix: An efficient serving engine for llm agents as general programs，2025，arXiv】】（最短作业优先）进行比较。衡量指标为 rollout 时间和最长轨迹的累积排队延迟。

实验结果：
1. 预测精度：如图13所示，Heddle 的预测器在召回率和相关系数上均优于基线。此外，Heddle-2（第二步后的预测）优于 Heddle-1（第一步后的预测），证明了利用运行时上下文能逐步提高预测准确性。
2. 调度性能：如图14所示，Heddle 将端到端 rollout 时间减少了 1.1-1.26倍。性能提升主要来自于对最长轨迹排队延迟的显著降低。

分析结论：Heddle 的渐进式预测和优先级调度机制能有效识别并优先处理长尾轨迹，从而显著减少其排队延迟，缩短整体 rollout 时间。

图13：不同工作负载和模型下渐进式轨迹预测的精度。Heddle 的预测精度随着步骤增加而提升，并显著优于基线。
图13：不同工作负载和模型下渐进式轨迹预测的精度。Heddle 的预测精度随着步骤增加而提升，并显著优于基线。
图14：轨迹级调度器的性能。Heddle（右侧条形）显著降低了排队延迟（红色部分），从而减少了总 rollout 时间。
图14：轨迹级调度器的性能。Heddle（右侧条形）显著降低了排队延迟（红色部分），从而减少了总 rollout 时间。

7.3 轨迹感知放置的有效性

实验内容：将 Heddle 的轨迹感知放置策略与两种基线策略（最少负载和缓存感知）进行比较，衡量端到端 rollout 吞吐量。
实验结果：如图15所示，Heddle 的吞吐量比两种基线高出 1.2-1.5倍。
分析结论：缓存感知策略因静态分配导致严重的负载不平衡，而最少负载策略虽然能平衡负载，但忽略了轨迹的整体性，导致对长尾轨迹的高干扰。Heddle 通过结合预排序动态规划和运行时迁移，明确地最小化了关键长尾轨迹的完成时间，从而优化了整体 rollout 完成时间。

图15：轨迹感知放置的性能。Heddle 在所有工作负载上都实现了最高的吞吐量。
图15：轨迹感知放置的性能。Heddle 在所有工作负载上都实现了最高的吞吐量。

7.4 资源管理器的有效性

实验内容：将 Heddle 的轨迹自适应资源管理与两种同构资源分配基线（Fix-1：吞吐量优化，MP=1；Fix-8：延迟优化，MP=8）进行比较。衡量指标为端到端 rollout 吞吐量和活跃轨迹数量随时间的变化。
实验结果：如图16(a)所示，Heddle 比两种静态基线实现了 1.1-1.3倍的加速。图16(b)显示，Fix-1 策略虽然初始吞吐量高，但长尾轨迹处理缓慢，成为瓶颈；Fix-8 策略虽然能加速长尾轨迹，但整体吞吐量低下。
分析结论：Heddle 解决了延迟与吞吐量的权衡问题，通过动态为长尾轨迹提供低延迟执行，同时为短轨迹维持高吞吐量，从而在整体性能上超越了静态配置。

图16：轨迹自适应资源管理的性能。(a) Heddle 的吞吐量优于两种固定配置。(b) Heddle（黑色虚线）能比其他方法更快地完成所有轨迹。
图16：轨迹自适应资源管理的性能。(a) Heddle 的吞吐量优于两种固定配置。(b) Heddle（黑色虚线）能比其他方法更快地完成所有轨迹。

7.5 系统开销

实验内容：量化 Heddle 引入的系统开销，包括数据平面（预测和迁移开销）和控制平面（放置和资源管理算法开销）。
实验结果：如表1所示，预测和迁移的开销通常可以被工具执行时间所掩盖，即使在工具执行时间极短的情况下，其暴露的开销相对于每步几十秒的 LLM 生成时间也可以忽略不计。如表2所示，控制平面的算法开销与总 rollout 时间相比也微不足道。
分析结论：Heddle 引入的系统开销极小，不会对整体性能产生负面影响。

表1：Heddle 中的预测和迁移开销。
表1：Heddle 中的预测和迁移开销。

表2：Heddle 中的算法开销。
表2：Heddle 中的算法开销。

A7 补充细节

8 讨论

异步 RL。异步 RL 【【59，Streamrl: Scalable, heterogeneous, and elastic rl for llms with disaggregated stream generation，2025，arXiv】】通过部分 rollout 【【41，Kimi k1.5: Scaling reinforcement learning with llms，2025，arXiv】】提升了 RL 吞吐量，但需要陈旧性阈值来防止梯度偏差并保持训练收敛。虽然这个最大陈旧性要求维持了训练的稳定性，但它并未解决长尾 Agentic 轨迹的瓶颈问题。Heddle 可以无缝地与有陈旧性限制的异步 RL 集成，加速这些掉队者而不会引入额外的策略分歧或策略陈旧性。

PD 分离。预填充-解码（Prefill-decode, PD）分离【【32，Splitwise: Efficient generative llm inference using phase splitting，2024，ACM/IEEE ISCA】】、【【58，DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving，2024，USENIX OSDI】】通过在预填充和解码阶段应用异构模型并行（MP）来优化 LLM 服务。然而，它在每个阶段的 worker 池内保持同构的 MP。Heddle 与此方法是正交的，并且可以无缝集成以提供阶段内的异构性。例如，Heddle 可以在预填充池内为长尾轨迹动态分配更高的模型并行度，从而进一步加速 Agentic rollouts。

推测解码。推测解码（Speculative decoding, SD）【【17，Taming the long-tail: Efficient reasoning rl training with adaptive drafter，2025，arXiv】】、【【23，Fast inference from transformers via speculative decoding，2023，ICML】】通过使用一个小的草稿模型生成候选 token，然后由目标模型并行验证来加速 LLM 解码。然而，由于被拒绝 token 的计算开销，SD 在大批量时会降低吞吐量。SD 不适用于以预填充为主的 Agentic RL 任务，因为在频繁的步骤中短生成使得工具输出的预填充成为主要的 rollout 瓶颈。但 Heddle 通过优化预填充阶段仍然是有效的。对于以解码为主的工作负载，Heddle 与 SD 是正交的，并且可以无缝集成。例如，Heddle 可以动态地将长尾轨迹路由到高模型并行度的 worker 以减少解码时间，同时应用 SD 来进一步最小化解码时间。

A5 结论

本文提出了 Heddle，一个以轨迹为中心的框架，通过缓解由长尾、多步 Agentic 轨迹引起的掉队者效应来优化 Agentic RL 的 rollout 阶段。通过将长尾轨迹的执行时间分解为排队、干扰和基础单位 token 时间，Heddle 采用了一种协同的编排方法，集成了以轨迹为中心的调度、放置和资源管理。我们的评估表明，Heddle 有效地解决了长尾瓶颈，与最先进的基线系统相比，实现了高达 2.5 倍的吞吐量提升。