注：本文包含 AI 辅助创作

• 参考链接：
  • 原始论文：(ScaleRL)The Art of Scaling Reinforcement Learning Compute for LLMs, Meta, 20251015
  • 代码地址：github.com/OpenLMLab/MOSS-RLHF

Paper Summary

• 核心总结（本文的核心贡献是 Meta 团队丰富的认知）：
  • 论文缩放方法论的一个重要见解是：可以系统地使用较小规模的消融来预测更大规模的性能，这使论文能够创建最终的可扩展 Recipe
  • 根据论文的消融实验， Off-policy 算法、损失函数和模型精度是最重要的决策
    • 其他每个决策单独影响不大，但正如论文从留一法实验中看到的，当它们全部组合时，仍然具有一些累积影响（在效率方面）
  • 渐近性能与效率 (Asymptotic performance vs. efficiency)
    • 论文发现更好的选项同时提高了效率和渐近性能，但情况并非总是如此（例如，对于 FP32，图 4(b)），当从基线方法开始进行”正向”消融时，论文首先且最主要地选择渐近性能
    • 当从 ScaleRL Recipe 进行”反向”留一法消融时，论文发现每个决策对渐近性能的影响非常小，但算法的每个组件似乎都有助于提高效率
      • 这表明变化的累积效应是相当鲁棒的
  • Generalization：虽然对泛化的全面描述超出了论文工作的范围，但论文确实观察到分布内验证与下游泛化性能之间的相关性
    • 有一些算法选择似乎更有助于泛化，作者指出了：
      • 更大的批次大小（章节 A.14）
      • 减少截断（章节 A.15）
      • 更长的生成长度（第 5 节，图 9）
      • 更大的模型规模（第 5 节，图 1）
  • 多任务强化学习 (Multi-task RL)
• 背景 & 问题：
  • RL 已成为训练 LLMs 的核心技术，然而 RL 领域缺乏与预训练阶段相当的预测性 Scaling 方法论
  • 计算预算迅速增长，但对于如何评估算法改进以 Scaling RL 计算，目前尚无原则性的理解（principled understanding）
• 论文工作：
  • 论文进行了首次大规模系统性研究，总计超过 400,000 GPU hous ，定义了一个原则性框架，用于分析和预测 LLM 中的 RL Scaling
• 论文为 RL 训练拟合了 S 形计算-性能曲线（sigmoidal compute-performance curves），并广泛消融了一系列常见的设计选择，以分析它们对渐近性能和计算效率的影响
• 论文观察到：
  • (1) 并非所有 Recipe （recipes）都能产生相似的渐近性能；
  • (2) 诸如损失聚合、归一化、课程学习以及 Off-policy 算法等细节主要调节计算效率，而不会显著改变渐近性能；

    Details such as loss aggregation, normalization, curriculum, and off-policy algorithm primarily modulate compute efficiency without materially shifting the asymptote

  • (3) 稳定、可扩展的 Recipe 遵循可预测的 Scaling 轨迹，使得能够从小规模运行中进行外推
• 结合这些见解，论文提出了一个最佳实践（best-practice） Recipe ScaleRL ，并通过成功地将单个 RL 运行扩展到 100,000 GPU hous 并预测其验证性能，证明了其有效性
• 论文的工作既提供了一个用于分析 RL Scaling 的科学框架，也提供了一个实用的 Recipe ，使 RL 训练更接近预训练中长期实现的预测性

---

Introduction and Discussion

• Scaling RL 计算正成为推进 LLMs 发展的关键范式
  • 预训练奠定了模型的基础；但随后的 RL 训练阶段释放了当今许多最重要的 LLM 能力，从 test-time thinking (OpenAI, 2024; DeepSeek, 2025) 到智能体能力 (Kimi, 2025a)
  • 例如 Deepseek-RL-Zero 使用了 100,000 H800 GPU hous 进行 RL 训练，占其预训练计算的 3.75% (DeepSeek, 2025)
  • RL 计算的这种急剧增长在前沿 LLM 的各代产品中被放大，从 o1 到 o3 增加了超过 \(10\times\) (OpenAI, 2025)，从 Grok-3 到 Grok-4 也有类似的飞跃 (xAI Team, 2025)
• 尽管用于 LLM 的 RL 计算已经大规模扩展，但我们对如何扩展 RL 的理解并未跟上；其方法论仍然更像艺术而非科学
  • 最近的 RL 突破主要由针对新颖算法的孤立研究 (例如，DAPO, (2025)) 和特定模型的训练报告所驱动，例如 MiniMax 等 (2025) 和 Magistral (2025)
  • 且这些研究提供了针对特定背景的临时解决方案，但并未说明如何开发能够随计算规模扩展的 RL 方法
• 这种 Scaling 方法论的缺乏阻碍了研究进展：
  • 由于没有可靠的方法先验地识别有前景的 RL 候选方案，进展与大规模实验绑定，这使得大多数学术界团体被边缘化
• 这项工作通过借鉴预训练中成熟的概念 Scaling Laws ，为 RL Scaling 的科学奠定了基础
  • 虽然预训练已经收敛到能够可预测地随计算规模扩展的算法 Recipe (2020; 2022; Owen, 2024)，但 RL 领域缺乏明确的标准
  • RL 从业者面临着令人眼花缭乱的设计选择，使得如何扩展以及扩展什么这些基本问题悬而未决
  • 为了解决这些问题，论文建立了一个使用类 S 形饱和曲线来预测 RL 性能的框架，该曲线描述了在同分布验证集上的期望奖励 (\(R_{C}\)) 与训练计算量 (\(C\)) 之间的关系：
    $$\boxed{ \overbrace{R_{C}-R_{0} }^{ \text{Reward Gain} } = \overbrace {(A-R_{0})}^{ \text{Asymptotic Reward Gain} } \times \frac{1}{\underbrace{1+(C_{\rm mid}/C)^{B} }_{ \text{Compute Efficiency} } } } \quad \quad \text{(fixed model and traning data)} \tag{1}$$
  • \(0\leq A\leq 1\) 代表渐近通过率
  • \(B>0\) 是决定计算效率的缩放指数
  • \(C_{\rm mid}\) 设定了 RL 性能曲线的中点
  • 注：\((A-R_{0})\) 可以理解为 渐近的奖励增益（Asymptotic Reward Gain）， \(A\) 为渐近奖励（Asymptotic Reward）
  • 理解：
    • \(A-R_0\) 是表示一个系数，越大时，整体收益 \(R_C\) 越大
    • \(C\) 是一个越大，\(C_{\rm mid}/C\) 变小，\(1+(C_{\rm mid}/C)^B\) 变小，\(\frac{1}{1+(C_{\rm mid}/C)^B}\) 变大，整体曲线如图 3 所示
• 图 3 提供了这些参数的示意图解释
• 公式 (1) 中的框架使研究人员能够从低计算量运行外推性能到高计算预算，从而能够在无需承担将每个实验都运行到其计算极限的成本的情况下，评估 RL 方法的可扩展性
• 在这个框架的指导下，论文开发了 ScaleRL ，这是一个能够可预测地随计算规模扩展的 RL Recipe
  • 在一个大规模的100,000 GPU hous 训练运行中，论文展示了 ScaleRL 的性能与论文的框架预测的扩展曲线紧密匹配（图 1）
  • 仅从训练的初始阶段外推的扩展曲线与最终观察到的性能紧密匹配，证实了论文的框架在极端计算规模下的预测能力
• ScaleRL 的设计基于一项全面的 RL Scaling 实证研究，该研究跨越了超过 400,000 GPU hous（在 Nvidia GB200 GPU 上）
• 这项研究在 8B 模型参数规模上探索了众多设计选择，其中单个运行使用高达 16,000 GPU hous，使其比在论文最大训练运行规模上进行实验便宜 6 倍
• 这项调查得出了三个关键原则：
  • RL 性能上限并非普适（RL Performance Ceilings are Not Universal） ：当我们为不同方法扩展训练计算量时，它们会遇到不同的可达到性能上限 (\(A\))
    • 这个限制可以通过诸如损失类型和批次大小等选择来改变
  • 拥抱苦涩教训（Embracing the Bitter Lesson） ：在小计算预算下表现优越的方法，在外推到大规模计算区域时可能更差（图 2）
    • 仍然可以通过使用论文的框架（公式 (1)）从早期训练动态中估计缩放参数 (\(A\), \(B\)) 来识别可扩展的方法
  • 重新评估常见智慧 ：通常被认为能提高峰值性能的干预措施（例如，损失聚合、数据课程、长度惩罚、优势归一化）主要调整计算效率 (\(B\))，而不会显著改变性能上限
• 基于这些见解，ScaleRL 通过整合现有方法而非发明新方法来实现可预测的扩展
  • 具体来说，ScaleRL 结合了异步 Pipeline-RL 设置（第 3.1 节）、强制长度中断、截断重要性采样 RL 损失 (CISPO from MiniMax-M1)、提示级损失平均、批次级优势归一化、logits 处的 FP32 精度、零方差过滤和 No-Positive-Resampling
  • 以上每个组件的贡献都在消耗 16,000 GPU hous 每次运行的留一法消融实验中得到了验证
  • ScaleRL 实现可预测地扩展，且建立了新的SOTA（图 2）
    • 与已建立的 RL Recipe 相比，它实现了更高的渐近性能和计算效率
  • ScaleRL 在跨多个训练轴增加计算量时保持了可预测的扩展性（第 5 节）
    • 包括 \(2.5\times\) 更大的批次大小、长达 32,768 个 Token 的生成长度、使用数学和代码的多任务 RL 以及更大的混合专家模型 (Llama-4 17B\(\times\)16)；
    • 其益处持续迁移到下游任务
• 总的来说，这项工作建立了一种严谨的方法论，用于成本效益地预测新 RL 算法的可扩展性

---

Preliminaries & Setup

• 论文使用 LLM 进行强化学习，其中提示 \(x\) 从数据分布 \(D\) 中采样
• 论文的设置遵循在 GPU 上的 Generator-Trainer 分离：
  • Generator GPU 使用优化的推理内核进行高通量 rollout 生成
  • Trainer GPU（其余的 GPU）运行训练后端 (FSDP) 并更新参数
• 论文分别用 \(\pi^{\theta}_{\text{gen} }\) 和 \(\pi^{\theta}_{\text{train} }\) 表示 Generator 和训练后端上具有参数 \(\theta\) 的模型
• 对于每个提示， Generator GPU 上的旧策略 \(\pi^{\theta_\text{old} }_\text{gen}\) 产生候选补全，然后被分配标量奖励
• 策略优化通过最大化一个裁剪的 Surrogate Objective 进行，对 \(x\sim D\) 和来自 \(\pi^{\theta_\text{old} }_\text{gen}\) 的 rollout 取期望

Training Regimen（安排，规划）

• 所有实验均在用于推理的 RL 领域进行，其中模型产生一个用特殊 Token（<think> … </think>）包围的思考轨迹和一个最终解决方案
• 除非另有说明，训练使用 16,384 个 Token 的序列长度：
  • 12,288 用于思考，2,048 用于解决方案，另外 2,048 用于输入提示
• 论文采用 12,288 的思考预算以加快迭代速度，并在第 5 节展示 ScaleRL 外推在使用更大思考预算 (32,768) 进行训练时仍保持预测性
• 对于数学 RL 实验，论文使用 Polaris-53K 数据集 (2025)，批次大小为 768（48 个提示，每个提示 16 次生成）
• 在论文的设置中，扩展 RL 计算对应于在训练提示上运行多个周期
• 关于训练的更多细节，包括 SFT 和超参数，见附录 A.3

Base RL Algorithm

• 作为论文在第 3 节的起点，论文从一个“基础”算法开始
  • 该算法类似于没有 KL 正则化项的 GRPO (2024)，与大规模训练报告一致 (Magistral, 2025; MiniMax, 2025)
  • 论文包含了非对称 DAPO 裁剪 (2025)，它作为避免熵崩溃和保持输出多样性的默认方法被广泛采用
• 对于给定的提示 \(x\)，旧策略 \(\pi_{\text{gen} }(\theta_{\text{old} })\) 生成 \(G\) 个候选补全 \(\{y_{i}\}_{i=1}^{G}\)，每个被分配一个标量奖励 \(r_{i}\)。论文计算优势 \(\hat{A}_{i}\) 并使用组归一化优势：
  $$\hat{A}_{i}=r_{i}-\text{mean}(\{r_{j}\}_{j=1}^{G}),\quad\hat{A}_{i}^{G}=\hat{A}_ {i}/(\text{std}(\{r_{j}\}_{j=1}^{G})+\epsilon).$$
  • 每个长度为 \(|y_{i}|\) 的补全 \(y_{i}\) 在 Token-level 的重要性采样 (IS) 比率 \(\rho_{i,t}(\theta)\) 上做出贡献，具有非对称的上限和下限裁剪阈值，类似于 DAPO (2025)：
    $$\rho_{i,t}(\theta):=\frac{\pi^{\theta}_\text{train}(y_{i,t}\mid x,y_{i,<t})}{\pi^{ \theta_{\text{old} } }_\text{gen }(y_{i,t}\mid x,y_{i,<t})}=\frac{\pi^ {\theta}_\text{train}(y_{i,t})}{\pi^{\theta_{\text{old} } }_\text{gen }(y_{ i,t})};\quad\text{clip}_{\text{asym} }(\rho,\epsilon^{-},\epsilon^{+}):=\text{ clip}(\rho,1-\epsilon^{-},1+\epsilon^{+}). \tag{2}$$
  • 论文在 Sample-level 聚合损失，即在跨样本平均之前，先平均每个样本的 Token 损失
  • Surrogate Objective 为：
    $$\mathcal{J}(\theta)=\mathbb{E}_{x\sim D,\atop\{y_{i}\}_{i=1}^{G}\sim\pi^{ \theta_{\text{old} } }_\text{gen }(\cdot|x)}\left[\frac{1}{G}\sum_{i=1}^{G}\frac{1 }{|y_{i}|}\sum_{t=1}^{|y_{i}|}\min\Bigl{(}\rho_{i,t}(\theta)\hat{A}_{i}^{G}, \text{clip}_{\text{asym} }(\rho_{i,t}(\theta),\epsilon^{-},\epsilon^{+})\hat{A}_ {i}^{G}\Bigr{)}\right]. \tag{3}$$
• 控制生成长度 (Controlling Generation Lengths)
  • 为了防止训练过程中推理输出长度爆炸性增长，这有害于训练稳定性和效率，论文使用中断 (GLM-V Team, 2025; 2025)，通过附加一个思考结束短语（例如，“</think>”）来强制停止过长的生成，示意 LLM 终止其推理并产生最终答案
  • 论文将在后面的第 4 节重新讨论这个选择，并将其与惩罚长生成的长度惩罚进行比较 (2025; Kimi Team, 2025b)

Predictive compute-scaling and fitting curves

• 与通常使用幂律拟合预测曲线的预训练不同，论文使用 S 形函数（公式 (1)）来模拟通过率与 \(\log(compute)\) 的关系
  • 论文这样做是因为论文经验发现 S 形拟合比幂律拟合更鲁棒和稳定，论文将在附录 A.4 中进一步讨论
  • 论文的选择与先前使用类 S 形幂律来捕捉有界指标（如准确率）的工作一致 (2024; 2022)
• 与预训练研究类似 (2025b; 2025)，论文发现排除非常早期的低计算区域（low-compute regime）会产生更稳定的拟合，之后训练遵循可预测的轨迹
  • 除非另有说明，论文所有的缩放拟合都在约 1.5k GPU hous 之后开始
  • 拟合过程的进一步细节在附录 A.5 中提供，论文曲线拟合的鲁棒性在附录 A.7 中讨论
  • 问题：这里是指拟合 S 形曲线时，排除早期的训练结果，理解是因为此时模型没有得到良好的训练，不排除会受波动影响较大
• 解释缩放曲线 (Interpreting scaling curves)
  • 直观地说，S 形曲线捕捉了饱和回报：
    • 在低计算区域增长缓慢，在高效缩放的中段急剧加速，然后在计算量高时饱和
  • 论文还在图 3 中提供了 S 形曲线参数 \(A,B,\text{ 和 }C_{mid}\) 的示意图解释
    • 可以看到，\(B,C_{\text{mid} }\) 主要影响运行的效率，\(A\) 表示在大型计算规模下的渐近性能
  • 关于这些参数的进一步讨论在附录 A.8 中提供
• 在留出验证集上的缩放曲线 (Scaling curve on held-out validation)
  • 与预训练实践一致 (2022; 2025)，论文在同分布验证数据上测量预测性能
  • 由于训练运行跨越多个 Epochs，论文从 Polaris-53k 数据集中随机留出 \(1,000\) 个提示用于验证，并使用其余部分进行训练
  • 缩放曲线拟合在验证点上，这些点每 100 个训练步骤测量一次平均通过率，在 \(1,000\) 个留出提示上每个提示有 16 次生成

---

An Empirical Study of RL Scaling

• 论文使用一个 8B 参数的稠密模型在可验证的数学问题上进行 RL 实验
• 使用第 2 节中描述的设置，论文研究了几个设计轴在其可预测的计算缩放行为方面，即渐近性能 (asymptotic performance, \(A\)) 和计算效率 (compute efficiency, \(B\))，如图 3 所示
• 论文将实验结构分为三个阶段
  • 首先，在 3.5k 到 4k GPU hous 的基线之上消融设计选择，因为一些实验选择在此规模之外会变得不稳定（附录 A.15）
    • 每当一个设计改变被证明是稳定的，论文就将其训练更长时间
  • 然后，将最佳选择组合成 ScaleRL ，并在第 4 节进行 16k GPU hous 的留一法 (LOO) 实验
    • 在这里，论文通过在前 8k GPU hous 上拟合并外推运行的剩余部分来评估可预测性
  • 最后，为了证明使用 ScaleRL 的可预测缩放，论文在第 5 节还考虑了具有更大批次大小、混合专家模型、多任务（数学和代码）和更长序列长度的训练设置

Asynchronous RL Setup

• 论文首先研究异步 Off-policy RL 设置 (2024) 的选择，因为它控制着训练稳定性和效率，通常独立于所有其他设计选择
• 论文考虑两种 Off-policy 学习方法：PPO-off-policy-\(k\) 和 PipelineRL-\(k\)
• PPO-off-policy-\(k\) 是异步 RL 的默认方法，先前已被 Qwen3 (2025) 和 ProRL (2025a) 使用
  • 在这种设置中，旧策略 \(\pi_{\theta^{\text{old} }_{\text{gen} } }^{op}\) 为一批 \(B\) 个提示生成推理轨迹
  • 每次梯度更新处理一个包含 \(\hat{B}\) 个提示的小批次，导致每个批次有 \(k=B/\hat{B}\) 次梯度更新
  • 在论文的实验中，论文固定 \(\hat{B}=48\) 个提示（每个提示 16 次生成），并通过设置 \(B=k\times 48\) 来改变 \(k\in \{1,8\}\)
• PipelineRL-\(k\) 是来自 Piche 等 (2025) 的一种新方法，并被 Magistral (2025) 使用
  • 在 PipelineRL-\(k\) 中， Generator 以流式方式持续产生推理轨迹
  • 每当 Trainer 完成一次策略更新时，新参数立即推送到 Generator ， Generator 继续使用更新后的权重但使用来自旧策略的陈旧 KV 缓存进行生成
  • 一旦生成完整的轨迹批次，它就被传递给 Trainer 进行下一次更新
  • 在论文的设置中，论文引入了一个参数 \(k\)：如果 Trainer 比 Generator 提前 \(k\) 步，它们就会等待
• 论文在图 4(a) 中比较了这些方法
  • PipelineRL 和 PPO-off-policy 实现了相似的渐近性能 \(A\)，但 PipelineRL 显著提高了计算效率 \(B\)；从而更快地达到上限 \(A\)
    • 因为 PipelineRL 减少了训练过程中的空闲时间
  • 这种选择以更少的 Token 产生可靠的收益，使得在较低计算预算下进行更大范围的扫描成为可能
  • 论文还改变了 PipelineRL 的最大 Off-policy 程度，并发现 \(k=8\) 是最优的，如图 4(b) 所示，论文将在附录 A.11 中进一步讨论

Algorithmic Choices

• 基于以上结果，论文采用 PipelineRL-8 作为论文更新后的基线。然后论文研究了六个额外的算法轴：
  • (a) 损失聚合， loss aggregation
  • (b) 优势归一化，advantage normalization
  • (c) 精度修正，precision fixes
  • (d) 数据课程，data curriculum
  • (e) 批次定义，batch definition
  • (f) 损失类型，loss type
• 在第 4 节，论文将最佳选项组合成一个统一的 Recipe ，称为 ScaleRL (Scale-able RL)，并在 16,000 GPU hous 的更大规模上进行留一法实验

Loss type

• 论文将非对称 DAPO 损失（公式 8）与两个最近提出的替代方案进行比较：GSPO (Qwen, 2025a) 和 CISPO (MiniMax, 2025; 2025)
• GSPO 在序列级别应用重要性采样，而不是 GRPO 的 Token-level 公式。具体来说，GSPO 将 Token-level 的 IS 比率（公式 2）改变为序列级别的比率：
  $$ \rho_{i}(\theta)=\frac{ {\pi_\text{train}(y_{i}|x,\theta)} }{ {\pi_{gen}(y_{i}|x,\theta_{\text{old} })} }$$
• CISPO 简单地将截断 IS 与普通策略梯度 (Ionides, 2008) 结合起来，其中 \(\mathbf{sg}\) 是停止梯度函数：
  $$\mathcal{J}_{\text{CISPO} }(\theta)=\underset{\begin{subarray}{c}x\sim D,\ (y_{t})_{t=1}^{G}\sim\pi_{gen}(\cdot|x,\theta_{\text{old} })\end{subarray} }{\mathbb {E} }\left[\frac{1}{T}\sum_{t=1}^{G}\sum_{t=1}^{\lvert y_{t}\rvert}\mathbf{sg}(\min(\rho_{i,t},\epsilon_{\max}))\hat{A}_{i}\log \left(\pi_\text{train}(y_{i,t}|x,y_{i<t},\theta)\right)\right] \tag{4}$$
• 图 5(a) 显示 GSPO 和 CISPO 都显著优于 DAPO，大幅提高了渐近通过率 \(A\)
• CISPO 表现出延长的近线性奖励增长，并且在训练后期略优于 GSPO，因此论文选择 CISPO 作为论文的最佳损失类型
• 关于 Off-policy 损失类型及其超参数鲁棒性的进一步讨论在第 4 节和附录 A.17 中详述

FP32 Precision for LLM logits

• Generator 和 Trainer 依赖不同的内核进行推理和训练，导致它们的 Token 概率存在小的数值不匹配 (ThinkingMachine Defeating nondeterminism in LLM inference, 2025)
  • RL 训练对此类差异高度敏感，因为它们直接影响 Surrogate Objective 中的 IS 比率
• MiniMax (2025) 发现这些不匹配在语言模型头（language model head）尤其明显，并通过在 Generator 和 Trainer 的 Head 使用 FP32 计算来缓解这个问题
  • 如图 5(b) 所示，精度修正将渐近性能 \(A\) 从 \(0.52\) 显著提高到 \(0.61\)
  • 鉴于这个明显的好处，论文将 FP32 精度修正包含在论文的 ScaleRL Recipe 中

Loss Aggregation

• 论文评估了三种聚合 RL 损失的策略：
  • (a) 样本平均（Sample average） ，每个 rollout 贡献相等（如 GRPO，附录 A.2）
  • (b) 提示平均（Prompt average） ，每个提示贡献相等（如 DAPO，附录 A.2）
  • (c) Token 平均（Token average） ，批次中的所有 Token 损失直接平均，没有中间分组
• 比较结果见附录 A.9（图 14(a)）
• 论文发现 Prompt average 实现了最高的渐近性能，因此在 ScaleRL 中使用此选择

Advantage Normalization

• 论文比较了三种优势归一化的变体：
  • (a) 提示级别（Prompt level） ，优势通过同一提示的 rollout 奖励的标准差进行归一化（如 GRPO，附录 A.2）
  • (b) 批次级别（Batch level） ，优势通过批次中所有生成的标准差进行归一化，如 Reinforce++ (2025a); Magistral (2025) 所用
  • (c) 无归一化（No normalization） ，优势计算为原始奖励减去提示生成的平均奖励，没有方差缩放（如 Dr. GRPO (2025c) 所提出）
• 比较图见附录 A.9（图 14(b)），观察到所有三种方法产生相似的性能
• 因此论文采用 Batch level 归一化，因为它在理论上合理且略好
• 这个选择在第 4 节的更大规模留一法实验中也得到了进一步证实

Zero-Variance Filtering

• 在每个批次中，一些提示在其所有生成中产生相同的奖励
  • 这些“零方差”提示具有零优势，因此贡献零策略梯度
  • 默认基线在损失计算中包含这些提示，但尚不清楚是否应将它们包含在有效批次中
• 为了测试这一点，论文将默认设置与有效批次（effective batch）方法进行比较
  • 在 effective batch approach 中，只有具有非零方差的提示被包含在损失计算中（如 Seed (2025) 所做）
• 请注意：零方差过滤不同于 DAPO (2025) 中的动态采样
  • 零方差过滤仅仅是丢弃 Prompt ，而 DAPO 是重新采样更多提示直到批次满员（until the batch is full）
  • 论文在图 6(a) 中显示使用有效批次在渐近性能上表现更好；论文将其纳入论文的 ScaleRL Recipe

Adaptive Prompt Filtering

• 已经提出了许多用于 RL 训练的数据课程策略以提高样本效率 (2025; 2025b; 2025b)
• 这里论文评估一个简单的变体，由 (2025) 引入，其关键观察是
  • 一旦一个提示对策略变得过于简单，它通常会持续保持简单
  • 由于这样的提示消耗一些计算但不再贡献有用的梯度信号（第 3.2 节），最好将它们从未来的训练中排除
• 论文通过维护一个通过率历史记录并永久移除任何通过率 \(\geq 0.9\) 的提示在后续周期中来实现这一点（论文称之为 No-Positive-Resampling）
• 在图 6(b) 中，论文将此课程与默认设置（所有提示在整个训练过程中均匀重新采样）进行比较
  • 论文看到课程提高了可扩展性和渐近奖励 \(A\)

---

ScaleRL: 有效且可预测地扩展强化学习计算 (ScaleRL: Scaling RL Compute Effectively & Predictably)

• 根据上述研究的设计维度，论文将性能最佳的设置整合到一个单一的 Recipe 中，论文称之为 ScaleRL (Scale-able RL)
• ScaleRL 是一种异步强化学习 Recipe ，它使用下面的配置：
  • 具有 8 步 Off-policy 性的 PipelineRL
  • 基于中断的长度控制进行截断（interruption-based length control for truncation）
    • 注：后文有提到，对于强制中断，论文使用思考结束短语：”Okay, time is up. Let me stop thinking and formulate a final answer now. </think>“
  • FP32 计算用于逻辑单元
  • 优化 \(\mathcal{J}_{\texttt{ScaleRL} }(\theta)\) 损失
• \(\mathcal{J}_{\texttt{ScaleRL} }(\theta)\) 损失结合了：
  • Prompt-level 损失聚合
  • Batch-level 优势归一化
    • 注意：是按照批次做 Advantage 归一化的，不是 GRPO 方法，而是类似 REINFORCE++ 方法
    • 补充：REINFORCE++ 的方法：
      • 记录历史平均奖励作为基线，判断模型是否在进步
      • 使用历史奖励的均值和方差做归一化，类似 Batch Normalization）
  • 截断重要性采样（truncated importance-sampling）REINFORCE 损失 (CISPO)
  • 零方差过滤（zero-variance filtering）
  • 无正例重采样（no-positive resampling）
    $$\begin{split}\mathcal{J}_{\texttt{ScaleRL} }(\theta)=& \underset{x\sim D,\atop\{y_{i}\}_{i=1}^{G},\sim\pi^{data}_{g\in h}( \cdot|x)}{\mathbb{E} }\left[\frac{1}{\sum_{g=1}^{G}|y_{g}|}\sum_{i=1}^{G}\sum_{t=1 }^{|y_{i}|}\mathsf{sg}(\min(\rho_{i,t},\epsilon))\hat{A}^{\text{norm} }_{i}\log \pi^{ {\theta} }_\text{train}(y_{i,t})\right],\\ \rho_{i,t}=&\frac{\pi^{ {\theta} }_\text{train}(y_{i,t})}{\pi^{ {\theta}_{add} }_{g\in h}(y_{i,t})},\hat{A}^{\text{norm} }_{i}=\hat{A}_{i}/\hat{A}_{\text{std} },0<\text{mean}(\{r_{j}\}_{j=1}^{G})<1,\text{pass_rate} (x)<0.9,\end{split}$$
  • 其中 \(\mathsf{sg}\) 是停止梯度函数
  • \(\hat{A}_{\text{std} }\) 是一个批次中所有优势 \(\hat{A}_{i}\) 的标准差
  • pass_rate\((x)\) 表示提示 \(x\) 的历史通过率

留一法消融实验 (Leave-One-Out (LOO) Ablations)

• 为了验证这些选择在组合后仍然是最优的，论文进行了留一法 (LOO) 实验：
  • 从 ScaleRL 开始，论文每次将一个维度恢复到其在第 2 节中的基线对应项
  • 这确保了每个设计决策即使在其他所有决策都存在的情况下也能做出积极贡献
• 图 7 报告了这些实验，每个实验扩展到 16k GPU hous
• 在所有维度上，ScaleRL 始终是最有效的配置，在渐近奖励或计算效率上略微优于 LOO 变体（参见图 7 表格的最后一列）
  • 由于大多数 LOO 变体达到相似的渐近通过率，论文将 sigmoid 拟合转换为幂律拟合，以通过斜率 \(B\) 突出效率差异（细节见图 7）
  • 具体来说，论文平均所有运行的渐近奖励 \(A\)，用这个固定的 \(A\) 重新拟合曲线，然后在图 7 中比较斜率（衡量效率）
  • 相应的未转换的通过率与计算曲线在附录 A.2 中提供

Error margin（误差范围）in fitting scaling curves

• 由于强化学习训练已知具有高方差 (2021)，论文使用三个独立的 ScaleRL 运行（图 8a）来估计拟合缩放系数的变异性
  • 观察到的渐近奖励和效率参数的方差作为论文的经验误差范围，用于确定两个不同运行的计算效率或渐近性能的变化是否具有统计意义 (2024)

Extrapolating Scaling Curves

• 在论文所有的 LOO 实验以及独立的 ScaleRL 运行中，论文拟合了高达 8000 GPU hous 的 sigmoid 曲线，并外推到 16000 GPU hous ，观察到预测曲线与训练点和扩展点都紧密对齐
  • 这证明了 ScaleRL 和其他稳定、可扩展的 Recipe 在大规模强化学习训练下的稳定性和可预测性

Are the design choices worth it?

• 在第 3.2 节中，某些设计选择改变了渐近性能，例如损失类型（图 5a）和 FP32 精度（图 5b）
• 但在论文使用 ScaleRL 的 LOO 实验中（图 7），这些组件单独来看似乎不那么关键（图中最后一列）
• 这就提出了一个问题：某些设计选择是否可以安全地保留其”默认”值
  • 作者认为上述问题的答案是否定的
  • 即使一个选择在组合 Recipe 中显得多余，它仍然可以提供稳定性或鲁棒性，这在其他情况下可能变得至关重要
    • 问题：如何理解显得多余又能提供稳定性或鲁棒性，是指不使用这些指标时，不同随机种子下表现差异大吗？还是说在不同的 模型规模或者数据集上表现差异大？
  • 例如，虽然 FP32 精度修复在使用 ScaleRL 训练的密集 8B 模型上差异不大（图 7），但它在 GRPO/DAPO 风格的损失中通过减轻数值不稳定性带来了巨大收益
    • 这表明它的好处超出了论文研究的特定 ScaleRL 配置
    • 为了进一步测试这一点，论文在 Scout 17Bx16 MoE 上进行了留一法实验，观察到 FP32 精度提高了整体可扩展性（图 8b）
  • 损失类型也出现了类似的情况
    • 在图 7 中，恢复到 DAPO 在 ScaleRL 内产生了与 CISPO 相似的渐近性能
    • 但如论文在附录 A.17 中讨论的那样，CISPO 对 IS 裁剪参数 \(\epsilon_{\text{max} }\) 的选择明显更鲁棒，降低了训练对超参数调整的敏感性
    • 而且它在 LOO 实验中比 DAPO 更高效（\(B=2.01\) 对比 \(B=1.77\)）
    • 这证明了即使一个经过仔细调整的 DAPO 变体在渐近性能上可能相似，也倾向于选择 CISPO 是合理的
• 总之，即使个别设计选择在组合 Recipe 中显得多余，它们通常也能以跨模型和设置泛化的方式增强训练稳定性、鲁棒性或效率
  • ScaleRL 保留这些组件不仅仅是为了在特定配置中获得边际收益，而是因为它们解决了在强化学习体系中反复出现的不稳定性和方差来源
• 注：本节的主要目标是说明，很多改进点看似在论文特定场景下没有收益，但在更通用的其他场景（随机种子，数据集，模型等）下，可能会有收益，为了保证方法的稳定性，建议加上一些确定性的改进点

---

Predictable Scaling Returns Across RL Compute Axes（跨强化学习计算轴的可预测缩放回报）

• 给定固定或增长的计算预算，哪个缩放旋钮（上下文长度、批次大小、每个提示的生成次数和模型大小）能带来最可靠的性能增益，并且论文多早可以预测到这种回报？
• 论文通过以下方式回答这个问题：
  • (i) 在每种设置的训练早期（精确地说，是目标预算的一半）拟合方程 (1) 中的饱和幂律；
  • (ii) 外推到目标预算；
  • (iii) 扩展训练以验证预测
• 在下面所有的轴线上，论文观察到清晰、可预测的拟合，其外推曲线与扩展轨迹对齐，反映了论文在 100,000 GPU hous 运行（图 1）和图 2 中的跨 Recipe 比较中看到的行为

模型规模（Model scale (MoE)）

• ScaleRL 在更大模型上是否仍然保持可预测性和稳定性？（注：即论文的 Scaling Law 是否能泛化到其他模型上）
• 使用 ScaleRL 训练 17B\(\times\)16 Llama-4 Scout MoE 表现出与 8B 模型相同的可预测缩放行为 ，具有低截断率且没有不稳定性问题（附录 A.15, A.17）
  • 图 1 显示了训练曲线
• 扩展点与拟合曲线对齐，支持了论文 Recipe 对模型规模的不变性
• 更大的 17B\(\times\)16 MoE 表现出比 8B 密集模型高得多的渐近强化学习性能，仅使用其 1/6 的强化学习训练计算量就超越了 8B 的性能

Generation length（context budget，即上下文预算）

• 将生成长度从 14k 增加到 32k 个 Token 会减缓早期进展（更低的 \(B\) 和更高的 \(C_{mid}\)），但会持续提升了拟合的渐近线 (A)
  • 提供足够的计算量后，可以产生更高的最终性能（图 9）
• 这验证了长上下文强化学习是一个提升性能上限的旋钮，而不仅仅是效率权衡
• 从拟合中做出的外推正确地预测了当训练扩展时更高的 32k Token 轨迹

Global batch size（prompts，即提示数）

• 较小的批次运行在下游基准测试中显示出早期停滞（即使分布内验证性能持续提高）
• 较大的批次可靠地改善了渐近线，并避免了论文在较小批次运行中观察到的下游停滞
• 图 10a 在中尺度上显示了相同的定性模式：
  • 小批次可能在早期表现更好，但随着计算量的增长会被超越
  • 在论文图 1 中最大的数学运行中，将批次大小增加到 2048 个提示既稳定了训练，又产生了一个可以从高达 50k GPU hous 外推到最终 100k 点的拟合

每个提示的生成次数（固定总批次）(Generations per prompt (fixed total batch))

• 对于固定的总批次，是分配更多提示还是每个提示分配更多生成次数更好？
  • 扫描每个提示的生成次数 8,16,24,32 并调整提示数以保持总批次固定，得到的拟合缩放曲线基本不变（附录 A.13）
  • 这表明在中等批次下，这种分配对于 A 和 B 都是次要选择
• 在更大批次（例如，2k+）下可能会出现更明显的差异，论文将其留待未来工作

---

Related Work

• 论文在本节中详细介绍了与论文研究最相关的两项工作
• ProRL (2025a) 证明，在大型语言模型上进行长时间的强化学习微调（约 2000 个优化步骤，批次大小 64），使用混合推理任务进行 16K GPU hous ，可以发现超越模型基础能力的新解决方案策略
  • 这种更长的训练方案在 1.5B 模型上带来了显著收益，在某些基准测试中媲美更大模型的性能
  • ProRL 的贡献在于特定的稳定性启发式方法（KL 正则化、策略重置、熵控制等），以实现 1.5B 模型的高性能
• Alibaba Group 等 (2025c), Part I: Tricks or Traps? A Deep Dive into RL for LLM Reasoning 提供了一个互补的视角
  • 在 Qwen-3 4B/8B (2025) 上的一致条件下消融了各种设计选择，并提出了一种极简组合 LitePPO
    • LitePPO 在较小规模的模型和计算量上优于更复杂的方法，如 GRPO (2024) 和 DAPO (2025)
  • 这产生了有价值的算法见解，但重点是比较实证发现，而不是缩放行为
• 这些工作都没有研究这些方法的”缩放(scaling)”特性
  • 事实上，主要的比较是在下游评估上进行的，这可能不是研究可预测缩放的正确指标
  • 正如在预训练和论文这里的工作中所做的那样，论文研究分布内留出验证集上的性能
• 与上述提到的相关工作相比，论文的工作开发并验证了一个具有预测拟合的计算-性能框架，同时在更大的计算预算（例如，比 ProRL 大 6 倍）和模型规模上运行
• 论文的研究结果产生了一个近乎 SOTA 强化学习 Recipe ，可以可预测地扩展到超过 100,000 GPU hous 而没有任何稳定性问题
• 其余相关工作推迟到附录 A.1

---

Discussion & Conclusion

• 在这项工作中，论文研究了用于大型语言模型强化学习的各种技术的缩放特性，以寻求一个可预测、可扩展的 Recipe
• 基于此使命，论文推导出一种为验证集准确率拟合预测性缩放曲线的方法，使论文能够量化强化学习方法的渐近性能和计算效率
• 使用这种方法论，论文的主要贡献是仔细进行了一系列消融实验，涉及构成强化学习 Recipe 的若干算法选项
  • 对于每次消融，论文尽可能选择具有更高渐近性能的选项，否则选择效率更高的选项
• 结合这些选择产生了 ScaleRL Recipe ，它在论文的实验中比所有现有 Recipe 缩放得更好
• 以下几点观察值得注意：
  • 计算缩放外推 (Compute scaling extrapolation)
    • 论文缩放方法论的一个重要见解是，我们可以系统地使用较小规模的消融来预测更大规模的性能
    • 这使论文能够创建最终的可扩展 Recipe
  • 最重要的决策 (Most important decisions)
    • 根据论文的消融实验， Off-policy 算法、损失函数和模型精度是最重要的决策
    • 其他每个决策单独影响不大，但正如论文从留一法实验中看到的，当它们全部组合时，仍然具有一些累积影响（在效率方面）
  • 渐近性能与效率 (Asymptotic performance vs. efficiency)
    • 对于论文许多消融实验，论文发现更好的选项同时提高了效率和渐近性能，但情况并非总是如此（例如，对于 FP32，图 4(b)）
      • 当从基线方法开始进行”正向”消融时，论文首先且最主要地选择渐近性能
    • 有趣的是，当从 ScaleRL Recipe 进行”反向”留一法消融时，论文发现每个决策对渐近性能的影响非常小，但算法的每个组件似乎都有助于提高效率
      • 这表明变化的累积效应是相当鲁棒的
  • 泛化 (Generalization)
    • 虽然论文报告了下游评估的迁移情况，但论文的主要重点是研究预测性缩放，这是通过在训练提示的留出数据集上的分布内性能曲线来表征的 (2022;2025)
      • 这仍然留下了大型语言模型从训练分布到留出测试集的泛化能力如何的问题
    • 虽然对泛化的全面描述超出了论文工作的范围，但论文确实观察到分布内验证与下游泛化性能之间的相关性
    • 但有一些算法选择似乎更有助于泛化，论文在此想指出，包括：
      • 更大的批次大小（章节 A.14）
      • 减少截断（章节 A.15）
      • 更长的生成长度（第 5 节，图 9）
      • 更大的模型规模（第 5 节，图 1）
  • 多任务强化学习 (Multi-task RL)
    • 虽然论文的实验主要集中在数学领域，但论文也在多任务强化学习训练下评估了 ScaleRL
    • 如图 11 所示，在数学和代码上联合训练为每个领域产生了清晰、平行的幂律趋势，扩展的运行保持与外推曲线对齐
    • 虽然论文的初步结果是有希望的，但彻底研究具有不同训练数据混合的多任务强化学习的计算缩放可预测性将是很有趣的

Future work

• 一个自然的下一步是为强化学习在预训练计算、模型大小和强化学习训练数据方面推导预测性的”Scaling Laws”
• 未来的研究还可以包括其他强化学习计算缩放的轴（Axes），例如结合结构化或密集奖励 (2025b;2024) 和更计算密集的生成验证器 (2025a)，以找到强化学习训练的最佳计算分配
• 最后，这里介绍的方法论框架可以应用于研究其他后训练机制的缩放行为，包括多轮强化学习、智能体交互和长形式推理
• 强化学习中有许多设计选择，因此作者认为论文的 ScaleRL Recipe 并非故事的终点
  • 作者希望论文对可扩展强化学习的关注以及预测可扩展性的方法能够激励未来的工作，进一步推动大型语言模型强化学习的前沿
  • 为了使未来的研究能够拟合计算-性能强化学习缩放曲线，论文在 www.devvrit.com/scalerl_curve_fitting 发布了一个最小代码库

---

附录 A：Appendix

A.1 Extended Related Work

• 近期涌现的一波工作将强化学习应用于提升大语言模型的推理能力；这些工作通常能在具有挑战性的任务上取得 SOTA 结果 (2024; 2025; 2025; 2025)
  • OpenAI 的 o1 系列模型证实了大规模强化学习能显著增强长程推理能力，但并未发布这些模型训练方式的任何细节
  • Deepseek R1（以及 R1-Zero）(2025) 提供了首个关于主要通过强化学习训练高性能长思维链模型的全面研究，记录了在扩展强化学习下不依赖奖励模型 (2023) 或蒙特卡洛树搜索 (2024) 而出现的涌现行为
• 这波推理发展浪潮中最早被广泛引用的 RLVR（可验证奖励）算法是 GRPO
  • GRPO 是一种无评论员、分组相对的策略梯度方法，采用 PPO 风格的裁剪，用分组基线替代学习的价值基线，以降低计算成本并稳定长思维链的信用分配
  • 虽然 GRPO 催化了快速进展，但后续工作记录了其局限性（ Token-Level 裁剪、模型崩溃风险）并推动了不同分组或序列级别的变体 (2025; 2025; 2025; 2025)
• DAPO 提出了解耦裁剪和动态采样策略优化
  • DAPO 在 GRPO 目标中解耦了 \(\epsilon_{\text{low} }\) 和 \(\epsilon_{\text{high} }\) 裁剪，并对 \(\epsilon_{\text{high} }\) 进行 Clip-Higher操作以避免熵崩溃
  • DAPO 在给定批次中对提示进行动态采样，以避免方差（或优势）为零的样本，这些样本对策略梯度没有贡献
  • DAPO 采用 Token-Level 损失聚合（注：GRPO 使用样本级损失平均）
  • 通过以上这些修改，DAPO 能够在避免强化学习训练中熵崩溃的同时超越原始 GRPO 基线
• 与此同时提出的 VAPO 是一种专为长思维链设计的价值增强型 PPO，具有强大的稳定性，并优于像 GRPO 和 DAPO 这样的无价值基线
  • VAPO 结合了价值预训练和来自 VC-PPO (2025) 的解耦广义优势估计、来自 DAPO 的损失目标修改，并提出了长度自适应的 GAE，从而形成了一个开放的 Recipe VAPO，该 Recipe 已被用于训练 Seed1.5-thinking (2025) 中的大型混合专家模型
  • 类似地，其他技术报告如 Magistral (2025)、Kimi-k1.5 (2025)、Minimax-01 (2025) 详细介绍了他们强化学习训练 Recipe 的各种细节，但并未分享关于其设计选择为何优于基线的广泛实验

A.2 面向大语言模型的强化学习：GRPO 和 DAPO (RL for LLMs: GRPO and DAPO)

GRPO (2024)

• GRPO 将 PPO (2017) 应用于具有可验证奖励的大语言模型微调
• 对于给定的提示 \(x\)，旧策略 \(\pi_{\text{gen} }(\theta_{\text{old} })\) 生成 \(G\) 个候选补全 \(\{y_i\}_{i=1}^G\)，每个补全被分配一个标量奖励 \(r_i\)
• 为了强调组内的相对质量，奖励被归一化为
  $$
  \hat{A}_i=\frac{r_i-\text{mean}(\{r_j\}_{j=1}^G)}{\text{std}(\{r_j\}_{j=1}^G)+\epsilon}.
  $$
• 每个长度为 \(|y_i|\) 的补全 \(y_i\) 通过比率在 Token-level 上做出贡献
  $$
  \rho_{i,t}(\theta)=\frac{\pi_\text{train}(y_{i,t} \mid x,y_{i,<t},\theta)}{\pi_{gen}(y_{i,t} \mid x,y_{i,<t},\theta_{\text{old} })}.
  $$
• GRPO 目标在补全和 Token 之间进行平均：
  $$
  \mathcal{J}_{\text{GRPO} }(\theta)=\mathbb{E}_{x\sim D,\atop\{y_i\}_{i=1}^G,\sim\pi_{\text{gen}(\cdot \mid x,\theta_{\text{old} })} }\left[\frac{1}{G}\sum_{i=1}^G\frac{1}{|y_i|}\sum_{t=1}^{|y_i|}\min\Big(\rho_{i,t}(\theta)\hat{A}_i,\ \operatorname{clip}(\rho_{i,t}(\theta),1\pm\epsilon)\hat{A}_i\Big)\right].
  $$
• GRPO 像 PPO 一样保留了 Token-level 的策略比率，同时使用序列级别、分组归一化的优势来在稀疏奖励下稳定学习

DAPO

• DAPO (2025) 通过两个关键修改扩展了 GRPO
• 第一个改进点：用 非对称裁剪 替代了对称裁剪，对向上和向下的偏差使用不同的阈值：
  $$ \text{clip}_{\text{asym} }(\rho,a)=\text{clip}(\rho,,1-\epsilon^{-},1+\epsilon^{+})$$
  • 其中 \(\epsilon^{-}\) 和 \(\epsilon^{+}\) 是超参数
• 第二个改进点：DAPO 将聚合方案更改为在 提示级别 操作
  • 对于给定的提示 \(x\sim D\)，旧策略产生 \(G\) 个补全 \(\{y_i\}_{i=1}^G\)，其优势为 \(\{\hat{A}_i\}\)（公式 (5)）
  • 令 \(T=\sum_{i=1}^G|y_i|\) 表示所有补全的总 Token 数
  • Token-level 比率如公式 (2) 所示
• DAPO 代理目标为
  $$
  \mathcal{J}_{\text{DAPO} }(\theta)=\mathbb{E}_{x\sim D,\atop\{y_i\}_{i=1}^G\sim\pi_{\text{gen}(-|x,\theta_{\text{old} })} }\left[\frac{1}{T}\sum_{i=1}^G\sum_{t=1}^{|y_i|}\min\Bigl(\rho_{i,t}(\theta)\hat{A}_i,\ \text{clip}_{\text{asym} }(\rho_{i,t}(\theta))\hat{A}_i\Bigr)\right].
  $$
• 这种提示级别的归一化确保每个 Token 对提示的损失贡献相等，无论其采样补全的数量或长度如何
• DAPO 还引入了在训练期间动态丢弃批次中方差为零的提示，并用更多提示填充批次直到批次满员（论文在此跳过该更改，因为其效果类似于拥有更大的批次大小）

A.3 Training Setup

• 数据集
  • 对于小规模监督微调，论文使用精心策划的推理轨迹数据混合
  • 论文通过移除琐碎的提示、丢弃超过 12\(k\) 个 Token 的解决方案轨迹，并使用 AIME 2024/2025 和 MATH-500 (2021) 基准进行去污染来过滤此数据集
  • 对于强化学习阶段，论文在大多数运行中使用 Polaris-53K 数据集 (2025)；
  • 对于同时包含数学和代码的运行，使用 Deepcoder 数据集 (2025)
• 监督微调
  • 论文使用 2M Token 的批次大小、最大序列长度 12288 和学习率 \(3\times 10^{-5}\)，在 32 个 H100 GPU 节点上使用 AdamW 优化器 (2019) 运行监督微调，总共大约 4 个轮次和 32B Token
• 强化学习
  • 论文在强化学习训练期间分配 14k 的生成预算，其中 12k Token 分配给中间推理（“思考”），随后 2k Token 用于最终解决方案和答案
  • 论文在每个批次中采样 48 个提示，每个提示有 16 个生成（即每个梯度更新步骤的总批次大小为 768 个回复）
  • 奖励分别给予正确和错误的轨迹 \(\pm 1\)
  • 使用恒定学习率 \(5\times 10^{-7}\)
  • AdamW 优化器 (2019)，其中 \(\epsilon=10^{-15}\)，权重衰减为 0.01（AdamW 中的默认值）
    • 注：较低的 \(\epsilon\) 是为了避免梯度裁剪（epsilon 下溢）(2023)
  • 100 步的线性预热
• 数学问题评估：
  • 论文使用自动化检查器，如 Sympy (2017) 或 Math-Verify 来评估数学问题在剥离思考轨迹（\(<\)think\(>\)\(\cdots\)\(<\)/think\(>\)）后最终答案的正确性
• 代码问题：
  • 对于涉及单元测试和期望输出的代码问题，论文使用自定义代码执行环境
• 硬件：
  • 论文使用 80 个 Nvidia GB200 GPU 进行单次运行
    • 3.5-4K GPU hous（用于在第 3.2 节中建立不同的设计选择）
    • 16K GPU hous 用于留一法实验（第 4 节）
    • 30k-100K GPU hous 用于论文更大规模的运行（第 5 节）
  • 论文在 GPU 之间采用 Generator-Trainer 分离
    • 对于 80 个 GPU 的实验，论文将其中的 64 个设置为 Generator ，负责使用优化的推理代码库生成推理轨迹
    • 其余的 16 个 GPU 作为 Trainer ，接收生成的轨迹，执行策略更新，并定期将更新后的参数广播回 Generator

A.4 拟合什么曲线？ (What curve to fit?)

• 预训练曲线通常使用幂律方程进行拟合 (2025; 2020; 2025)
• 在论文的情况下，这将性能建模为 \(R_C=A-D/C^B, C\geq C_0\)，其中 \(D\) 是常数，\(C_0\) 标志着超出该阈值后定律成立的计算量阈值
  • 直观地说，这意味着计算的每次倍增都会带来性能的恒定比例增益
• 但对于强化学习后训练，论文发现 S 形曲线（公式 (1)）更合适，原因如下
  • 首先，对于有界指标，如准确率或奖励，S 形曲线提供了更好的预测拟合 (2024; 2022)；论文观察到同样的情况，能够准确外推到更高的计算量（图 1）
  • 其次，幂律在低计算量时是无界的，并且通常只在超过阈值 \(C_0\) 后才进行拟合
    • 在强化学习中，总训练步数要少得多（例如，图 1 中只有约 75 个评估点可供拟合），丢弃早期点会进一步减少本已有限的拟合数据
  • 第三，根据经验，S 形拟合比幂律拟合更加稳健和稳定
    • 具体来说，考虑图 1 中所示的在 8B 稠密模型上进行的 100k GPU hous 运行
      • 当论文在 1.5k-50k GPU hous 之间拟合幂律曲线时，它预测的渐近性能为 \(A=1.0\)，这显然是错误的（实际曲线在 0.65 附近饱和）
      • 相比之下，S 形拟合给出了 \(A=0.645\) 的准确预测
    • 此外，幂律拟合对所选拟合区间高度敏感：
      • 在 (5\(\text{k}\),50\(\text{k}\)) GPU hous 上拟合则得到 \(A=0.74\)，而 S 形拟合仍然稳健，并且仍然预测 \(A=0.645\)
    • 幂律模型只有在专门在高计算量区间（例如，30k-60k GPU hous ）拟合时才能恢复正确的渐近线
      • 但论文的目标是从低计算量区间预测大规模性能，而在这些区间无法获得如此长的运行
• 考虑到这些因素，论文在整个分析中使用 S 形形式
  • S 形曲线捕捉了收益递减规律，即在低计算量区间增长缓慢，在高效缩放的中等区间急剧加速，然后在计算量高时饱和，接近有限的性能上限
• 需要注意的一点是，在高计算量区间，S 形曲线的行为与幂律相同
  • 具体来说，我们可以对 S 形曲线进行以下近似：
    $$
    \begin{align}
    R_C &=R_0+\frac{A-R_0}{1+(C_{mid}/C)^B} \quad \text{(来自公式 (1) 的 S 形曲线)} \\
    \implies R_C &\approx R_0+(A-R_0)\left(1-\frac{C^{B}_{mid} }{C^{B} }\right) \quad \text{(对于 \(C>>C_{mid}\), 高计算量区间（high compute regime）)} \\
    &=A-\frac{(A-R_0)C^{B}_{mid} }{C^{B} } \\
    &=A-\frac{D}{C^{B} }
    \end{align}
    $$
  • 其中 \(D=(A-R_0)C^{B}_{mid}\)
  • 这与本节开头提到的幂律形式相同

A.5 Fitting scaling curves

• 论文将公式 (1) 中的 S 形定律方程拟合到论文留出验证集上的平均奖励
  • 包含从 Polaris-53k (2025) 数学数据集中留出的 1,000 个提示，每 100 个训练步骤进行一次评估，每次在留出的 1,000 个提示上采样 16 个生成
• 直接拟合所有三个参数 \(\{A,B,C_{mid}\}\) 具有挑战性
  • 所以论文执行网格搜索，遍历 \(A\in\{0.450,0.455,0.460,\ldots,0.800\}\) 和 \(C_{mid}\in[100,40000]\)（搜索 100 个线性分隔的值），并对每个候选的 \(A,C_{mid}\) 拟合 \(B\)
    • 在此网格上最佳拟合（通过残差平方和衡量）作为最终曲线
  • 论文使用 SciPy 的 curve_fit 和默认初始化；改变初始化策略产生了相同的结果
  • 为了使未来的研究能够拟合计算性能强化学习缩放曲线，论文在 www.dewrit.com/scalerl_curve_fitting 发布了一个最小的代码库
• 为了估计论文拟合的误差范围，论文训练了三个独立的 ScaleRL 运行，批次大小为 768，生成长度为 14k（如第 4 节所用），如图 8a 所示
  • \(A\) 的拟合值最多变化 \(\pm 0.015\)，表明在渐近性能估计上 0.02 是一个合理的误差范围
  • 估计拟合值 \(B\) 的误差范围很困难，因为具有不同 \(A\) 值的不同算法可能对 \(B\) 有不同的误差范围
  • 为了比较算法的目的，我们可以安全地推断，如果两种方法达到相似的 \(A\) 值（在 0.02 范围内），那么当使用 \(A\) 值的平均值重新拟合时，具有较高 \(B\) 值的方法在可扩展效率方面至少同样好

A.6 Comparing algorithms

• 与大规模预训练中的观察一致，损失在初始急剧下降后进入可预测的幂律衰减阶段 (2025)，论文在强化学习中也观察到类似的两阶段行为
• 平均奖励在约第一个 epoch（约 1k 步，或对于大多数运行约 1.5k GPU hous ）期间快速、几乎线性地增加，之后曲线遵循 S 形定律行为（见图 15 查看“S 形”曲线）
• 论文的 S 形定律拟合应用于训练曲线的后一部分
• 与预训练不同，论文的主要目标不是预测固定 Recipe 的性能，而是识别哪些算法和设计选择能够可靠地扩展，并设计出具有可预测性的算法
• 实现高度稳健的拟合通常需要具有数百或数千个评估点的非常大的运行，这在论文的设置中是不切实际的，原因有两个
  • 第一个原因：在此规模上运行所有消融实验在计算上是不可行的
  • 第二个原因：论文比较的许多强化学习算法本身无法扩展到如此极端的预算：它们通常更早饱和，甚至由于不稳定性而在计算量增加时性能下降
    • 例如，论文的基线方法（第 3.2 节）在超过约 3500 GPU hous 后变得不稳定，因为过长的生成截断超过了生成的 10%，降低了有效批次大小
    • 关于此点的更多讨论见第 A.15 节
• 当论文在第 3.2 节中跨不同轴进行消融时，论文发现了能在更高计算量下提高稳定性的设计选择
  • 一些消融变体可以进一步扩展，例如，DAPO 中 \(\epsilon=0.26\) 的情况下约 5k GPU hous ，使用 FP32 精度修复（第 3.2 节）的情况下约 6k GPU hous ，以及 CISPO 的情况下约 7k GPU hous
  • 结合论文最佳的设计选择是一个稳定且可扩展的 Recipe ，这使论文能够以每次运行约 1600 GPU hous 的预算进行留一法实验
    问题：怎么还变少了？

A.7 Robustness of fits

• 对于稳定且可扩展的实验，包括从第 4 节开始的所有运行，改变拟合区间（例如，包含或排除初始 1.5k GPU hous 范围）会产生类似的可预测结果
  • 例如，在 8B 稠密模型上的 100k GPU hous 运行中，在 (1.5\(\text{k}\),50\(\text{k}\)) 上拟合得到 \(B=1.70\)，\(A=0.645\)，而 (0,100\(\text{k}\)) 得到 \(B=1.56\)，\(A=0.655\)，(0,50\(\text{k}\)) 得到 \(B=1.7,A=0.645\)，以及 (5\(\text{k}\),50\(\text{k}\)) 得到 \(B=1.67\)，\(A=0.645\)。在这些区间内，参数值保持在预期误差范围内（第 7 节）
• 此外，论文跳过低计算量区间，因为早期训练阶段，尤其是在第 3.2 节中不太稳定的设置中，常常由于短暂的不稳定性而过早达到平台期或偏离 S 形趋势（见附录 A.6, A.15）
  • 排除此区域可以使拟合专注于中高计算量范围，在该范围内饱和行为更清晰、更一致
• 1.5k GPU hous 阈值是根据经验选择的启发式方法：
  • 它大约对应于第 3.2 节中大多数实验的一个 epoch
  • 较大的截止值减少了拟合点的数量，而较小的截止值常常引入噪声
  • 论文发现 1.5k GPU hous 能在拟合稳定性和样本覆盖率之间提供最佳平衡，这与在预训练缩放分析和拟合中跳过低 FLOPs 区间的做法一致 (2025)

A.8 Interpreting Sigmoidal Curves

• 图 3 展示了一个示例拟合，说明了参数 \(A\)、\(B\) 和 \(C_{\text{mid} }\) 的影响
• 通过额外的图示扩展了这一点：图 12a、图 12b 和图 13a 分别改变了 \(B\)、\(C_{\text{mid} }\) 和 \(A\)，同时保持其他参数不变
• \(B\) 和 \(C_{\text{mid} }\) 主要影响缩放的效率 ，而 \(A\) 决定了在大计算量下可实现的渐近性能
• 在图 13b 中，论文看到一个两个运行的案例，其中一个效率高得多，因此显示出初期有希望的收益，但收敛到较低的渐近线，而另一个进展较慢，但由于更高的 \(A\) 最终超过了前者
• 在实践中，缩放策略应优先考虑提高渐近上限 \(A\) 的设计选择，然后才优化效率参数，如 \(B\) 或 \(C_{\text{mid} }\)

A.9 Forward and LOO Ablations

• 论文在图 14a-14b 中展示了第 3.2 节的额外结果
• 图 15 中绘制了第 4 节中关于通过率与计算量的留一法实验

A.10 Controlling generation length

• 推理强化学习中一个常见的担忧是控制爆炸性增长的生成长度，这会损害训练效率和稳定性（附录 A.15）
• 论文考虑两种方法：
  • (a) 中断（Interruptions），用于像 GLM-4.1V (2025) 和 Qwen3 (2025) 这样的工作；
  • (b) 长度惩罚（Length penalties），用于像 DAPO (2025)、Kimi (2025)、Magistral (2025) 和 Minimax-M1 (2025) 这样的工作

中断，Interruptions

• 通过附加一个标记性短语（例如“Okay, time is up. Let me stop thinking and formulate a final answer \(<\)/think\(>\)”）来强制停止生成，指示模型终止其推理并产生最终答案
• 在论文的设置中，中断 Token 被随机放置在 \([10k,12k]\) Token 长度之间，以诱导对不同生成长度的泛化

Length penalties

• 用于重塑奖励
• 遵循 DAPO (2025)，论文使用容忍区间 \(L_{\text{cache} }\) 来惩罚过长的补全：
  $$
  R_{\text{length} }(y)=clip\left(\frac{L_{\max}-|y|}{L_{\text{cache} } }-1,-1,0\right)
  $$
• 此惩罚仅添加到正确的轨迹上，以阻止过长的生成
  • 在长度惩罚实验中，论文设置 \(L_{\max}=14\text{k}\) 个 Token 和 \(L_{\text{cache} }=2\text{k}\) 个 Token
• 在第 4 节中，论文在 16\(\text{k}\) GPU hous 的规模上比较了长度惩罚和中断
• 在论文的最终 ScaleRL Recipe 中用长度惩罚替换中断不能提高性能

A.11 PipelineRL

• 使用基线设置，论文在 PipelineRL 中消融了 Off-policy 参数（图 4(b)）
• Off-policy 度为 4 和 8 的表现同样好，论文在第 3.1 节更新基线时采用 8 作为默认设置
  • 为什么 8 比 1 效果好？是因为横坐标不是 step，而是 GPU 时间吗？
• 为什么 PipelineRL 始终优于经典的 PPO-off-policy 方法（第 3.1 节和 第 4 节）？
  • 论文将其归因于其与 On-policy 训练更紧密的对齐
  • 在 PPO-off-policy 中，生成和训练交替进行：
    • Trainer 严格处理与所选参数 \(k\) 一样 Off-policy 的批次，基于过时的 Rollout 更新进行更新
    • PipelineRL 以流式方式运行：
      • 一旦批次可用，它就传递给 Trainer ；
      • 同样，一旦模型更新就绪，它就立即共享回 Generator ，Generator 立即使用它（包括在部分生成的轨迹的延续中）
    • 这种紧密的反馈循环使训练更接近 On-policy 状态，减少了 Generator 和 Trainer 分布之间的不匹配
• 重要的是，这种区别影响了缩放曲线的渐近性能 \(c\)，而不仅仅是效率指数 \(b\)
  • 很少有轴能以这种方式移动渐近线，使得 Off-policy 算法的选择成为强化学习后训练中最关键的设计决策之一

A.12 熵曲线：缩放批次大小 (Entropy Curves: Scaling Batch Size)

• 论文在整个训练过程中跟踪了留出验证集上的熵
  • 在所有实验中（包括批次大小、任务数量、生成长度和模型规模的变体）论文观察到熵总体一致下降
• 一个有趣的发现是，熵可能并不总是能提供对性能的预测性洞察，正如最近一些工作如 (2025) 所提出的那样
  • 在第本节中，论文绘制了批次大小为 768 和 2048 的 ScaleRL 运行的熵
    • 2048 批次大小的运行在每个阶段都实现了更强的下游性能（图 10b），但两个运行在每一步都遵循几乎相同的熵轨迹（第 A.12 节）
      • 这突出了一个重要点，尽管熵有时被用作探索的代理指标，但仅仅保持较高的熵并不能转化为更好的泛化
    • 相反，较大的批次每一步减少了有效探索，类似于较小的批次，但仍然产生了显著更好的性能——强调了批次大小是一个重要的决定性因素
• 总的来说，论文的发现表明，虽然熵在训练期间持续下降，但它不一定是下游性能的可靠预测指标
  • 这一观察结果强化了在旨在提高训练分布以及下游任务分布性能时，除了熵动态之外，还需要关注算法和缩放选择（例如，批次大小、 Off-policy 方法）的必要性

A.13 Scaling on multiple axes

• 在图 17 中提供了剩余的不同轴缩放的图表（问题：如何理解这里的轴？是指不同的维度的超参）
• 在图 18 中提供了相应的下游评估
• 论文还在表 1 中提供了 \(A,B,C_{mid}\) 的值

A.14 Downstream performance

• 在图 1、9、10b 和 18 中报告了一组具有代表性的下游评估曲线
• 这些包括具有批次大小 \(\{512,768,2048\}\) 的 ScaleRL 运行、具有 32k 生成长度的长上下文训练运行、大模型（Scout）训练运行、多任务运行（数学 + 代码）以及不同每个提示生成数量（固定批次大小）的运行
• 对于每种设置，论文绘制了性能与计算量的关系
• 结论：对于像更大批次大小、更长生成长度和更大模型大小这样的实验，下游性能更好（与验证集曲线的顺序相似）

A.15 Truncations and training instabilities

• 在论文的所有实验中，论文发现训练不稳定性通常与截断有关
  • 随着生成长度的增加，许多强化学习运行表现出波动的截断率，有时在训练过程中增加
• 在批次大小 768 的情况下，论文观察到 10-15% 范围内的截断通常会破坏训练稳定性 ，性能下降且无干预就无法恢复
  • 例子包括图 2 中扩展的 GRPO 运行，其中不稳定性与上升的截断率相关，以及第 3.2 节中使用的更新基线
• 相比之下，ScaleRL 运行更加稳定
  • 在 8B 模型上，超过 90% 的训练时间内截断率保持在 5% 以下
  • 在批次大小 2048 时，截断率略高，偶尔接近约 7%
    • 这种增加主要归因于训练期间观察到的更长的平均生成长度，这自然增加了超过预算的机会
    • 但，即使排除截断样本后，有效批次仍然很大，训练稳定性得以保持
  • 直观地说，更大的生成长度预算应有助于减少截断
  • 使用 34k 生成长度（批次 768）进行训练保持稳定（截断率短暂飙升至约 4%，但迅速降至 2% 以下）
• 更大的模型更稳健
  • 在 Scout 运行中，截断率始终低于 2%，并且在 > 90% 的训练步数中低于 1%
  • 这可能反映了更大模型调节生成长度的固有能力以及它们更强的指令遵循能力，这使得中断信号更有效
• 总结：论文建议实践者密切监控截断率
• 论文的发现表明，高截断率是不稳定性的可靠警告信号 ，而更大的模型、更高的生成预算和谨慎的设计选择（如在 ScaleRL 中）可以显著降低这种风险

A.16 Comparing Prevalent Methods

• 在图 2 中，论文将一些流行的训练 Recipe 与 ScaleRL 进行了比较，论文在此简要描述这些现有 Recipe

DeepSeek (GRPO)

• 这个 Recipe 主要遵循 DeepSeek (2025) 的工作
• 论文使用 GRPO 作为损失函数（第 A.2 节），其中 \(\epsilon_{min}=\epsilon_{max}=0.2\)，样本平均损失聚合，以及 PPO-offpolicy-8 算法
• 训练在 6k GPU hous 后由于截断（第 A.15 节）变得不稳定

Qwen2.5 (DAPO)

• 这个 Recipe 遵循 DAPO (2025)，包括 DAPO 损失函数（附录 A.2），其中 \(\epsilon_{min}=0.2,\epsilon_{max}=0.26\)（附录 A.17.1）
  • 这个 Recipe 使用 PPO-offpolicy-8 和提示平均损失聚合
  • 与原始 DAPO 论文 (2025) 的唯一区别是关于动态填充批次
    • DAPO 丢弃方差为零的提示，并采样更多提示直到批次满员
    • 在论文的代码库中，这效率不高
      • 因为对于 PPO-offpolicy 算法，Generator 会预先决定每个 Generator 将为 #prompts/#generators 生成 Rollout
      • 如果某个特定的 Generator 有更多方差为零的提示 ，它会采样更多的提示来完成其 #prompts/#generators 的份额
      • 这可能导致其他 Generator 停滞和整体速度减慢
    • 为了解决这个问题，论文保持一个更大的批次大小 1280（80 个提示，每个 16 个生成），并从批次中丢弃方差为零的提示
    • 论文注意到，丢弃后，有效批次仍然大于 768，即论文用于 ScaleRL 的大小

Magistral

• 这指的是 (2025) 中使用的 Recipe
• 这个 Recipe 包括与 DAPO 类似的 Recipe ，主要区别在于使用 PipelineRL 作为 Off-policy 算法

MiniMax

• 这指的是 (2025) 中使用的 Recipe
• 这个 Recipe 使用 CISPO 损失、LM 头部的 FP32 精度修复、PPO-offpolicy 算法和提示平均
• 与 DAPO 类似，它也丢弃方差为零的提示，因此论文也给它一个更大的批次大小 1280

A.17 Loss Type - Stability and Robustness

• GRPO/DAPO 风格的损失对裁剪比率超参数 \(\epsilon_{\text{max} }\) 的选择高度敏感；CISPO 和 GSPO 显示出远更强的稳健性
  • 例如，在附录 A.17.2 中，将 CISPO 的 \(\epsilon_{\text{max} }\) 在 \(\{4,5,8\}\) 之间变化，性能没有显著差异
• 对于 GSPO ，原始论文 (2025) 中使用的 \(10^{-4}\) 裁剪尺度在论文的设置中效果不佳
  • 论文在更广泛的尺度上进行了消融，发现确定了正确的数量级（例如，\(4\times 10^{-3}\) 及更高）以后，性能就稳定了，并且对细粒度的变化（例如，\(\{4\times 10^{-3},5\times 10^{-3}\}\)）基本不敏感

A.17.1 DAPO clipping ratios

• 在本节中，论文分析了 DAPO 损失函数（公式 (8)）中裁剪阈值 \(\epsilon_{\text{max} }\) 的作用
• \(\epsilon_{max}\) 的超参数敏感性已在先前工作中观察到
  • 例如，GRPO 通常设置 \(\epsilon_{\text{max} }=0.2\)，而 DAPO 使用 \(0.28\)
• 除了调整敏感性之外，论文发现 \(\epsilon_{\text{max} }\) 直接改变了算法的缩放行为
  • 随着 \(\epsilon_{\text{max} }\) 增加，终端奖励 \(A\) 增加，直到达到一个最佳范围，之后 \(A\) 再次下降
• 这是一个显著的效果：与许多仅改变收敛速度的超参数不同，\(\epsilon_{\text{max} }\) 控制着渐近误差本身

A.17.2 CISPO Clipping Ratios

• 论文消融了 CISPO 的较高裁剪比率，将较低裁剪比率固定为 \(0\)（图 19b）
• 在很宽的值范围内，论文发现性能差异很小，表明 CISPO 对这个超参数基本不敏感
• 这种稳健性反映了论文对 GSPO 的发现（第 A.17.3 节），并且与 DAPO/GRPO 风格的目标形成对比，后者对裁剪阈值的精确选择高度敏感
• 这种在超参数变化下的稳定性使 CISPO 成为大规模训练中默认使用的有力候选者

A.17.3 GSPO ablations

• 论文消融了 GSPO 中使用的裁剪比率尺度，如图 20a 所示
• GSPO 论文 (2025) 中给出的默认 \(10^{-4}\) 尺度对论文的 8B 模型缩放效果不是最好
• \(10^{-3}\) 尺度的表现与其他替代方案一样好，或者更好（图 20a）
• 给定这个尺度，论文进一步将上裁剪比率在 \(\{4\times 10^{-3},5\times 10^{-3}\}\) 之间变化，并发现 \(\{5\times 10^{-3}\}\) 产生了稍好的拟合（图 20b）
• GSPO 对裁剪比率的选择相当稳健
  • 确定了正确的尺度以后，大多数附近的值甚至更大的尺度表现相似
  • 这种稳健性与 DAPO 风格的损失形成鲜明对比，后者对上裁剪比率的精确值高度敏感，如第 3.2 节所述

A.17.4 GSPO vs CISPO

• 尽管具有超参数稳健性，但论文遇到了 GSPO 的稳定性问题
  • 在多次情况下，GSPO 运行在训练中期发散，导致性能突然下降
  • 对于 8B 模型，从稳定检查点重新启动可以恢复，但此策略在更大的模型（如 Scout）上失败，尽管重复重置到稳定检查点，不稳定性仍然存在
  • 虽然论文尽最大努力检查了任何实现错误，但论文没有发现
• 总的来说，虽然所有三种损失系列在调整好的设置下都可以具有竞争力，但 CISPO 在稳定性和对超参数的稳健性方面提供了最佳平衡 ，使其成为论文推荐的选择

本文介绍Python中的并发机制，并给出一种最简洁的Python并发库

---

使用协程(yield语句)

• 实现随时暂停和开始
• 完全串行的操作，无法实现时间上的并行，这里指的是不能同时进行某个操作
• 与Go语言的协程不同，Python的协程更像是一个“生成器”

---

使用线程

• 参考threading模块实现自己的线程

---

使用concurrent.futures

实现线程池模型

• 实现一般的线程池模型，代码如下，关键代码仅仅两行

  1 2 3 4 5 6 7 8 9 10 11 12

  import time from concurrent import futures def sleep_one_second(key): time.sleep(1) return "[%s]Done" % key ml = "ABCDEFGHIJ" with futures.ThreadPoolExecutor(10) as executor: res = executor.map(sleep_one_second, ml) print([r for r in res])

• 上面的代码可以在一秒内执行完成，因为共有10个线程并发

• 在实现爬虫程序时，如果需要爬取的某些数据是相对独立的，那么我们完全可以用线程池实现，而不用使用复杂的线程模块*

  实现进程池模型

• 仅仅需要修改futures.ThreadPoolExecutor为futures.ProcessPoolExecutor即可

  1 2 3 4 5 6 7 8 9 10 11 12

  import time from concurrent import futures def sleep_one_second(key): time.sleep(1) return "[%s]Done" % key ml = "ABCDEFGHIJ" with futures.ProcessPoolExecutor(10) as executor: res = executor.map(sleep_one_second, ml) print([r for r in res])

进程与线程内存区别

对全局变量的访问对比

• 线程:

  1 2 3 4 5 6 7 8 9 10 11 12

  from concurrent import futures global_list = [] def test_futures(range_num): global_list.append(range_num) print global_list return range_num with futures.ThreadPoolExecutor(8) as executor: res = executor.map(test_futures, range(10)) print "the final global_list: %s" % global_list

• • 上面的代码输出如下:

    [0]
    [0, [10, 2]
    , 1[0, 1, 2, , 32]
    , 3, [04, 1], 2, 3, 4
    [0, , 5]
    1, [0, 21, 2, [3, , 3, 044, , 51, , 6, , 75]
    2, [0, 1, 63, 7, , 2, 3[40, , 8, , 4, 9, 155, , 6, 2]6, , 7
    , 8, 7, 9, ]3
    8, 4, , 59, 6, ]
    7, 8, 9]
    the final global_list: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    the results: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

• 进程:

from concurrent import futures
global_list = []

def test_futures(range_num):
    global_list.append(range_num)
    print global_list
    return range_num

with futures.ProcessPoolExecutor(8) as executor:
    res = executor.map(test_futures, range(10))

print "the final global_list: %s" % global_list

• • 上面的代码输出如下:

    [0]
    [1]
    [2]
    [3]
    [0, 4]
    [5]
    [6]
    [7]
    [1, 8]
    [2, 9]
    the final global_list: []
    the results: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

• 原因分析

  • 线程之间共享地址空间,所以所有的线程线程访问同一个全局共享变量
  • 进程之间不共享地址空间,所以不同进程访问不同共享变量
  • 在程序中Process之间不共享地址空间,但是futures.ProcessPoolExecutor(max_workers)任务分配时受限与参数max_workers的影响,所以可以预估本地机器最多开启max_workers个进程,同一进程中地址空间共享,所以会有部分任务被分配给同一进程的不同线程,从而出现部分共享变量被不同任务访问到
  • 总结:
    • futures.ThreadPoolExecutor单进程多线程中全局变量共享
    • futures.ProcessPoolExecutor多进程多线程中每个进程内部的线程全局变量共享
    • 不同进程之间即使时全局变量也不能共享

---

Python中进程 VS 线程

• Python中由于全局解释器锁（GIL）的存在,同一进程中的所有线程使用同一个解释器对象,所以它们无法真正实现并行
• 所以在想要充分利用多核的时候,需要选择使用多进程
• 更多信息参考Process和Thread分析

---

整体说明

• 分布式系统 是由一组通过网络相互连接的独立计算节点（或计算机）组成的集合，这些节点协同工作以实现一个共同的目标，实现高效的计算和处理
• MPI（Message Passing Interface，消息传递接口） 是一个跨语言的并行计算通信协议，也是一个应用程序接口（API）标准，允许程序在分布式内存系统中高效地交换数据
  • MPI 定义了一套标准的库函数和语义规则，允许在非共享内存环境下的多个进程（通常运行在不同的处理器或计算节点上）通过发送和接收消息进行通信和协作
• mpi4py 库是一个构建在 MPI 之上的 Python 库 ，主要使用 Cython 编写
  • Cython 的目标是让 Python 代码具备 C 语言的高性能，它是 Python 的一个超集，既支持 Python 语法，又能调用 C 函数、定义 C 类型变量，从而优化 Python 代码的性能
• mpi4py 库以面向对象的方式提供了在 Python 环境下调用 MPI 标准的编程接口，这些接口构建在 MPI-2 C++ 编程接口基础之上，与 C++ 的 MPI 编程接口类似
• mpi4py 库实现了很多 MPI 标准中的接口，包括点对点通信、集合通信、阻塞/非阻塞通信、组间通信等
  • 可以在不同进程间传递任何可被 pickle 序列化的内置和用户自定义 Python 对象

---

安装 mpi4py

Mac 环境安装

• 安装 Homebrew（若已安装可跳过）：

  1	/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)"

• 安装 Open MPI（建议使用 Open MPI，因为它在 Mac 上通常更容易配置）：

  1	brew install open-mpi

  • 这一步安装依赖比较多，需要一些时间
  • 安装完成后，你可以通过运行 mpiexec --version 来验证 Open MPI 是否正确安装

• 安装 mpi4py：

  1	pip install mpi4py

  • （常见报错解法）如果你的系统中有多个 MPI 版本，或者 pip 无法找到正确的 MPI 库，你可能需要设置 MPICC 环境变量来指定 MPI 编译器。例如：

    1 2	export MPICC=/opt/homebrew/bin/mpicc # 根据你的 Open MPI 安装路径调整 pip install mpi4py

  • 在安装 mpi4py 后运行以下命令来验证安装：

    1	python -c "import mpi4py; print(mpi4py.__version__)"

Ubuntu 环境安装（待补充）

---

mpi4py 的使用

mpi4py 的操作总结（通信原语）

• mpi4py提供了并行计算所需的各种通信操作，主要分为两类：
• 点对点通信(Point-to-Point Communication) ：
  • 在两个特定进程间进行数据交换
  • 主要操作：Send/send, Recv/recv, Isend/isend, Irecv/irecv, Sendrecv/sendrecv等
• 集体通信(Collective Communication) ：
  • 涉及通信组(communicator)中的所有进程
  • 提供更高效的全局数据操作
• 不同集体通信操作对比

  操作类型	通信模式	数据流向	结果分布	典型应用场景
  Barrier/barrier	同步	无数据传输	无	进程同步
  Bcast/bcast	一对多	根 -> 所有	所有进程相同	分发配置参数
  Scatter/scatter	一对多	根 -> 各部分	每个进程不同	数据并行分解
  Gather/gather	多对一	所有 -> 根	仅根进程有结果	结果收集
  Allgather/allgather	多对多	所有 -> 所有	所有进程相同	全局信息共享
  Alltoall/alltoall	多对多	所有↔所有	每个进程不同	矩阵转置
  Reduce/reduce	多对一	所有 -> 规约 -> 根	仅根进程有结果	全局统计计算
  Allreduce/allreduce	多对多	所有 -> 规约 -> 所有	所有进程相同	需要全局结果的并行计算
  Scan/scan	多对多	前缀累积	每个进程不同	累积计算
  Reduce_scatter	多对多	先reduce再scatter	每个进程不同

• 在很多地方中，表述也使用类似 All-Gather, All-to-All, All-Reduce 等来表达
• All-Gather 和 All-to-All 的区别：
  • All-Gather 和 All-to-All 都是多对多发送数据
  • 发送数据上来看：
    • All-Gather 中，从任意进程的视角看，向不同进程发送的数据是相同的；
    • All-to-All 中则向不同进程发送不同数据，默认数据的维度和 world_size 相同，每个 receive_rank 进程会得到其他进程 send_data[receive_rank] 的数据
  • 结果上来看：All-Gather 操作后，各个进程最终的数据是相同的；All-to-All 操作后，不同进程最终的数据不同

mpi4py 使用演示

• 以下 mpi4py 示例均以小 Pythonic 风格（小写） 为例：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247

  from mpi4py import MPI import numpy as np import time def main(): comm = MPI.COMM_WORLD rank = comm.Get_rank() size = comm.Get_size() print(f"进程 {rank} 启动，共有 {size} 个进程") # 1. barrier - 进程同步 comm.Barrier() # 与 comm.barrier() 等价 # 2. bcast - 广播数据 if rank == 0: broadcast_data = {"message": "这是来自 rank=0 的 broadcast 消息", "value": 123} else: broadcast_data = None broadcast_data = comm.bcast(broadcast_data, root=0) print(f"进程 {rank} 收到 bcast 数据: {broadcast_data}") # 3. scatter - 分发数据 if rank == 0: scatter_data = [f"from-0-index-{i}" for i in range(size)] else: scatter_data = None data = comm.scatter(scatter_data, root=0) print(f"进程 {rank} 收到 scatter 数据: {data}") comm.Barrier() # 4. gather - 收集数据 if rank == 0: print(f"==开始测试更复杂的原语：==") comm.Barrier() local_data = np.arange(size * rank, size * (rank + 1), dtype=np.int32) print(f"进程 {rank} 原始数据: {local_data}") gathered_data = comm.gather(local_data, root=0) print(f"进程 {rank} 收到 gather 数据: {gathered_data}") # 5. allgather - 全收集数据 all_gathered_data = comm.allgather(local_data) print(f"进程 {rank} 收到 allgather 数据: {all_gathered_data}") # 6. alltoall - 全对全数据交换 recv_data = comm.alltoall(local_data) print(f"进程 {rank} 收到 alltoall 数据: {recv_data}") # 7. reduce - 规约操作 recv_data = comm.reduce(local_data, op=MPI.SUM, root=0) print(f"进程 {rank} 收到 reduce 数据: {recv_data}") # 8. allreduce - 全局规约操作 recv_data = comm.allreduce(local_data, op=MPI.SUM) print(f"进程 {rank} 收到 allreduce 数据: {recv_data}") time.sleep(0.1) # 高阶，任意维度的 allreduce 操作 comm.Barrier() if rank == 0: print(f"==测试任意维度的 allreduce 操作：==") comm.Barrier() all_reduce_local_data = np.array([rank*i for i in range(size+3)], dtype=np.int32) print(f"进程 {rank} 原始 all_reduce_local_data 数据: {all_reduce_local_data}") recv_data = comm.allreduce(all_reduce_local_data, op=MPI.SUM) # 输入可以是任意维度 print(f"进程 {rank} 收到 allreduce 数据: {recv_data}") comm.Barrier() time.sleep(0.1) # 9. scan - 前缀积累，按照 rank 累积 recv_data = comm.scan(local_data, op=MPI.SUM) print(f"进程 {rank} 收到 scan 数据: {recv_data}") comm.Barrier() time.sleep(0.1) # 增加：reduce_scatter - reduce_scatter规约操作 if rank == 0: print(f"==开始 reduce_scatter 演示==") local_data = np.array([rank*i for i in range(size)]) reduce_scatter_recv_data = np.array(0, local_data.dtype) # 必须将发送数据和接受数据的类型对齐，否则会出现类型不匹配的错误 print(f"进程 {rank} local_data 原始数据: {local_data}") comm.Barrier() print(f"进程 {rank} reduce_scatter_recv_data 原始数据: {reduce_scatter_recv_data}") comm.Reduce_scatter(local_data, reduce_scatter_recv_data, op=MPI.SUM) print(f"进程 {rank} 收到 Reduce_scatter 数据: {reduce_scatter_recv_data}") comm.Barrier() time.sleep(0.1) # 点对点通信函数演示 if rank == 0: print(f"==开始点对点通信演示==") # 10. send 和 recv - 阻塞式发送接收 if rank == 0: dest = 1 message = f"from {rank}, 你好，进程 1！" comm.send(message, dest=dest) print(f"进程 {rank} 发送消息到进程 {dest}") source = 1 recv_msg = comm.recv(source=source) print(f"进程 {rank} 从进程 {source} 收到消息: {recv_msg}") elif rank == 1: source = 0 recv_msg = comm.recv(source=source) print(f"进程 {rank} 从进程 {source} 收到消息: {recv_msg}") dest = 0 message = f"from {rank}, 你好，进程 0！" comm.send(message, dest=dest) print(f"进程 {rank} 发送消息到进程 {dest}") comm.Barrier() # 11. isend 和 irecv - 非阻塞式发送接收 if rank == 2: dest = 3 message = "非阻塞消息" req = comm.isend(message, dest=dest) source = 3 req_recv = comm.irecv(source=source) # 可以在这里执行其他计算 req.wait() # 等待发送完成 print(f"进程 {rank} 非阻塞发送完成") recv_msg = req_recv.wait() # 等待接收完成 print(f"进程 {rank} 收到非阻塞消息: {recv_msg}") elif rank == 3: source = 2 req_recv = comm.irecv(source=source) dest = 2 message = "非阻塞回复" req = comm.isend(message, dest=dest) # 可以在这里执行其他计算 recv_msg = req_recv.wait() # 等待接收完成 print(f"进程 {rank} 收到非阻塞消息: {recv_msg}") req.wait() # 等待发送完成 print(f"进程 {rank} 非阻塞发送完成") comm.Barrier() # 12. sendrecv - 同时发送和接收 send_val = -rank * 100 dest = (rank + 1) % size # 发送给下一个 source = (rank - 1) if rank - 1 >= 0 else size - 1 # 接收自来自上一个的 # 上面的实现是一个圆环的通信方式，节点之间消息是依次流转的 print(f"rank={rank}, dest={dest}, source={source}") # 注意：一定要对齐，A.dest = B，则必须有 B.source = A，否则下面的语句会卡死（一直等待） recv_val = comm.sendrecv(send_val, dest=dest, source=source) print(f"进程 {rank} 发送 {send_val} 到进程 {dest}，从进程 {source} 接收 {recv_val}") # 所有演示操作做完，最终同步 comm.Barrier() if rank == 0: print("\n所有进程完成演示") if __name__ == "__main__": main() # 进程 0 启动，共有 4 个进程 # 进程 2 启动，共有 4 个进程 # 进程 3 启动，共有 4 个进程 # 进程 1 启动，共有 4 个进程 # 进程 0 收到 bcast 数据: {'message': '这是来自 rank=0 的 broadcast 消息', 'value': 123} # 进程 1 收到 bcast 数据: {'message': '这是来自 rank=0 的 broadcast 消息', 'value': 123} # 进程 2 收到 bcast 数据: {'message': '这是来自 rank=0 的 broadcast 消息', 'value': 123} # 进程 3 收到 bcast 数据: {'message': '这是来自 rank=0 的 broadcast 消息', 'value': 123} # 进程 1 收到 scatter 数据: from-0-index-1 # 进程 3 收到 scatter 数据: from-0-index-3 # 进程 0 收到 scatter 数据: from-0-index-0 # ==开始测试更复杂的原语：== # 进程 2 收到 scatter 数据: from-0-index-2 # 进程 0 原始数据: [0 1 2 3] # 进程 1 原始数据: [4 5 6 7] # 进程 3 原始数据: [12 13 14 15] # 进程 1 收到 gather 数据: None # 进程 3 收到 gather 数据: None # 进程 2 原始数据: [ 8 9 10 11] # 进程 2 收到 gather 数据: None # 进程 0 收到 gather 数据: [array([0, 1, 2, 3], dtype=int32), array([4, 5, 6, 7], dtype=int32), array([ 8, 9, 10, 11], dtype=int32), array([12, 13, 14, 15], dtype=int32)] # 进程 0 收到 allgather 数据: [array([0, 1, 2, 3], dtype=int32), array([4, 5, 6, 7], dtype=int32), array([ 8, 9, 10, 11], dtype=int32), array([12, 13, 14, 15], dtype=int32)] # 进程 1 收到 allgather 数据: [array([0, 1, 2, 3], dtype=int32), array([4, 5, 6, 7], dtype=int32), array([ 8, 9, 10, 11], dtype=int32), array([12, 13, 14, 15], dtype=int32)] # 进程 3 收到 allgather 数据: [array([0, 1, 2, 3], dtype=int32), array([4, 5, 6, 7], dtype=int32), array([ 8, 9, 10, 11], dtype=int32), array([12, 13, 14, 15], dtype=int32)] # 进程 2 收到 allgather 数据: [array([0, 1, 2, 3], dtype=int32), array([4, 5, 6, 7], dtype=int32), array([ 8, 9, 10, 11], dtype=int32), array([12, 13, 14, 15], dtype=int32)] # 进程 1 收到 alltoall 数据: [1, 5, 9, 13] # 进程 0 收到 alltoall 数据: [0, 4, 8, 12] # 进程 2 收到 alltoall 数据: [2, 6, 10, 14] # 进程 3 收到 alltoall 数据: [3, 7, 11, 15] # 进程 3 收到 reduce 数据: None # 进程 1 收到 reduce 数据: None # 进程 2 收到 reduce 数据: None # 进程 0 收到 reduce 数据: [24 28 32 36] # 进程 1 收到 allreduce 数据: [24 28 32 36] # 进程 0 收到 allreduce 数据: [24 28 32 36] # 进程 3 收到 allreduce 数据: [24 28 32 36] # 进程 2 收到 allreduce 数据: [24 28 32 36] # ==测试任意维度的 allreduce 操作：== # 进程 0 原始 all_reduce_local_data 数据: [0 0 0 0 0 0 0] # 进程 2 原始 all_reduce_local_data 数据: [ 0 2 4 6 8 10 12] # 进程 3 原始 all_reduce_local_data 数据: [ 0 3 6 9 12 15 18] # 进程 1 原始 all_reduce_local_data 数据: [0 1 2 3 4 5 6] # 进程 0 收到 allreduce 数据: [ 0 6 12 18 24 30 36] # 进程 2 收到 allreduce 数据: [ 0 6 12 18 24 30 36] # 进程 1 收到 allreduce 数据: [ 0 6 12 18 24 30 36] # 进程 3 收到 allreduce 数据: [ 0 6 12 18 24 30 36] # 进程 3 收到 scan 数据: [24 28 32 36] # 进程 0 收到 scan 数据: [0 1 2 3] # 进程 1 收到 scan 数据: [ 4 6 8 10] # 进程 2 收到 scan 数据: [12 15 18 21] # 进程 3 local_data 原始数据: [0 3 6 9] # 进程 2 local_data 原始数据: [0 2 4 6] # 进程 1 local_data 原始数据: [0 1 2 3] # ==开始 reduce_scatter 演示== # 进程 0 local_data 原始数据: [0 0 0 0] # 进程 0 reduce_scatter_recv_data 原始数据: 0 # 进程 1 reduce_scatter_recv_data 原始数据: 0 # 进程 2 reduce_scatter_recv_data 原始数据: 0 # 进程 3 reduce_scatter_recv_data 原始数据: 0 # 进程 0 收到 Reduce_scatter 数据: 0 # 进程 3 收到 Reduce_scatter 数据: 18 # 进程 2 收到 Reduce_scatter 数据: 12 # 进程 1 收到 Reduce_scatter 数据: 6 # ==开始点对点通信演示== # 进程 0 发送消息到进程 1 # 进程 1 从进程 0 收到消息: from 0, 你好，进程 1！ # 进程 1 发送消息到进程 0 # 进程 0 从进程 1 收到消息: from 1, 你好，进程 0！ # 进程 2 非阻塞发送完成 # 进程 3 收到非阻塞消息: 非阻塞消息 # 进程 3 非阻塞发送完成 # 进程 2 收到非阻塞消息: 非阻塞回复 # rank=2, dest=3, source=1 # rank=3, dest=0, source=2 # rank=0, dest=1, source=3 # rank=1, dest=2, source=0 # 进程 1 发送 -100 到进程 2，从进程 0 接收 0 # 进程 0 发送 0 到进程 1，从进程 3 接收 -300 # 进程 2 发送 -200 到进程 3，从进程 1 接收 -100 # 进程 3 发送 -300 到进程 0，从进程 2 接收 -200 # # 所有进程完成演示

• 启动上述代码的命令为：

  1	mpiexec -n 4 python example.py

---

附录：传输不同维度的数据

• 在上述 allgather, alltoall, allreduce 等操作中，同一个进程传输给其他进程的数据不一定要维度完全相等，甚至类型也不一定要相同，只需要能够做对应的 MPI op 就可以
• 示例（某个元素改成列表）：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

  from mpi4py import MPI import numpy as np import time from numba.cuda import local def main(): comm = MPI.COMM_WORLD rank = comm.Get_rank() size = comm.Get_size() print(f"进程 {rank} 启动，共有 {size} 个进程") comm.Barrier() local_data = [ [0, 1, 2, 3], [4, 5, 6, 7], [ 8, 9, [10,18], 11], [12, 13, 14, 15], ] local_data = local_data[rank] print(f"进程 {rank} 原始数据: {local_data}") comm.Barrier() time.sleep(0.1) # allgather all_gathered_data = comm.allgather(local_data) print(f"进程 {rank} 收到 allgather 数据: {all_gathered_data}") comm.Barrier() time.sleep(0.1) # alltoall recv_data = comm.alltoall(local_data) print(f"进程 {rank} 收到 alltoall 数据: {recv_data}") comm.Barrier() time.sleep(0.1) # areduce recv_data = comm.reduce(local_data, op=MPI.SUM, root=0) print(f"进程 {rank} 收到 reduce 数据: {recv_data}") comm.Barrier() time.sleep(0.1) # allreduce - 全局规约操作 recv_data = comm.allreduce(local_data, op=MPI.SUM) print(f"进程 {rank} 收到 allreduce 数据: {recv_data}") comm.Barrier() time.sleep(0.1) if __name__ == "__main__": main() # 进程 2 启动，共有 4 个进程 # 进程 3 启动，共有 4 个进程 # 进程 1 启动，共有 4 个进程 # 进程 0 启动，共有 4 个进程 # 进程 0 原始数据: [0, 1, 2, 3] # 进程 1 原始数据: [4, 5, 6, 7] # 进程 3 原始数据: [12, 13, 14, 15] # 进程 2 原始数据: [8, 9, [10, 18], 11] # 进程 3 收到 allgather 数据: [[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, [10, 18], 11], [12, 13, 14, 15]] # 进程 1 收到 allgather 数据: [[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, [10, 18], 11], [12, 13, 14, 15]] # 进程 0 收到 allgather 数据: [[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, [10, 18], 11], [12, 13, 14, 15]] # 进程 2 收到 allgather 数据: [[0, 1, 2, 3], [4, 5, 6, 7], [8, 9, [10, 18], 11], [12, 13, 14, 15]] # 进程 1 收到 alltoall 数据: [1, 5, 9, 13] # 进程 0 收到 alltoall 数据: [0, 4, 8, 12] # 进程 3 收到 alltoall 数据: [3, 7, 11, 15] # 进程 2 收到 alltoall 数据: [2, 6, [10, 18], 14] # 进程 3 收到 reduce 数据: None # 进程 2 收到 reduce 数据: None # 进程 0 收到 reduce 数据: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, [10, 18], 11, 12, 13, 14, 15] # 进程 1 收到 reduce 数据: None # 进程 2 收到 allreduce 数据: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, [10, 18], 11, 12, 13, 14, 15] # 进程 0 收到 allreduce 数据: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, [10, 18], 11, 12, 13, 14, 15] # 进程 1 收到 allreduce 数据: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, [10, 18], 11, 12, 13, 14, 15] # 进程 3 收到 allreduce 数据: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, [10, 18], 11, 12, 13, 14, 15]

---

附录：导入 mpi4py 包的方式

• 必须使用：

  1	from mpi4py import MPI

• 不能使用：

  1 2	import mpi4py MPI = mpi4py.MPI

• 两种写法看似相同， 实际上不一样，第二种方法报错为 AttributeError: module 'mpi4py' has no attribute 'MPI'

• 这是因为 第二种方法 MPI 环境未初始化 ，mpi4py 要求在使用 MPI 功能前必须先初始化，而import mpi4py不会自动完成这一步

不同导入方式的差别

• 假设有两种导入方式：

  1 2 3 4 5 6

  # 方式一 from packagea import A # 方式二 import packagea A = packagea.A

• 如果 packagea 是一个包（包含 __init__.py），但 __init__.py 中未导入或暴露 A，方式二将无法通过包名直接访问 A

• 当 packagea 的 __init__.py 未显式导入或暴露 A 时，方式一（from packagea import A）仍能成功的原因与 Python 的导入机制和包结构有关

• Python 在执行 from packagea import A 时，会按以下步骤查找 A：

  • 1） 检查 packagea.__init__.py ：若 __init__.py 中定义或导入了 A，直接使用
  • 2） 搜索子模块 ：若 __init__.py 未包含 A，Python 会在 packagea 目录下查找是否存在 A.py 或 A/__init__.py
  • 3） 递归子模块 ：若仍未找到，Python 会尝试递归导入子模块中的 A（例如 packagea.module_a.A），但需显式指定路径（如 from packagea.module_a import A）

mpi4py 两种导入结果不同的原因

• 方式一成功的原因 ：当执行 from mpi4py import MPI 时：
  • 1） Python 加载 mpi4py 包，执行 __init__.py
  • 2） __init__.py 注册元路径导入器（_mpiabi._install_finder()）
  • 3） Python 发现 __all__ 中包含 MPI，但 __init__.py 中未显式定义
  • 4） 触发元路径导入器，根据系统 MPI 环境选择并加载对应的 MPI.so 文件（注意名称不一定是这个，可能是根据不同系统命名的文件）
    • 注：已确认在 ~/anaconda3/envs/xxx/lib/python3.10/site-packages/mpi4py/ 路径下不存在 MPI.so 文件
    • 虽然 mpi4py 目录下没有直接名为 MPI.so 的文件，但实际存在 MPI.mpich.cpython-310-darwin.so（针对 MPICH 实现的扩展模块） 和 MPI.openmpi.cpython-310-darwin.so（针对 OpenMPI 实现的扩展模块）
    • _mpiabi._install_finder() 的作用之一是根据系统中实际安装的 MPI 库（通过环境变量或系统命令探测），选择对应的 .so 文件
  • 5） MPI 扩展模块被加载，并绑定到 mpi4py 命名空间，导入成功
• 方式二失败的原因 ：方式一（import mpi4py 后 mpi4py.MPI）失败是因为：
  • import mpi4py 仅执行 __init__.py，不会触发元路径导入器对 MPI 的查找
  • __init__.py 中没有显式导入或定义 MPI（如 from .MPI import MPI），因此 mpi4py.MPI 不存在于命名空间中

---

附录：传统 MPI 风格函数的使用

• 在 mpi4py 中，函数名的大小写是有区别的，主要涉及两种不同的编程接口风格：Pythonic 风格（小写） 和 传统 MPI C/Fortran 风格（大写）
• 总结：
  • 小写函数 ：更 Pythonic，返回数据，适合动态数据，代码简洁，不需要管理缓冲区
  • 大写函数 ：类似 C/Fortran MPI，需要缓冲区，适合高性能计算（避免数据拷贝）

小写函数（Pythonic 风格）

• 返回数据 ，而不是修改传入的缓冲区（更符合 Python 习惯）

• 通常更简洁，适合 Python 风格的编程

• 适用于 NumPy 数组和 Python 对象（如列表、字典等）

• 以 gather 为例：

  1 2 3 4 5 6 7 8 9 10 11

  import numpy as np from mpi4py import MPI comm = MPI.COMM_WORLD rank = comm.Get_rank() size = comm.Get_size() # 使用小写 gather（返回结果，不修改传入的 recvbuf） gathered_data = comm.gather(data, root=0) if rank == 0: print("Gathered data:", gathered_data) # 输出：[0, 10, 20, ...]

• 特点：

  • gather 返回一个列表 ，包含所有进程发送的数据（仅在 root 进程有效）
  • 不需要预先分配 recvbuf ，适合动态数据

大写函数（传统 MPI 风格）

• 需要预先分配接收缓冲区（recvbuf） ，类似 C/Fortran 的 MPI 接口

• 直接修改传入的缓冲区 ，而不是返回数据

• 适用于高性能计算（特别是 NumPy 数组 ，避免数据拷贝）

• 以 gather 为例：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  import numpy as np from mpi4py import MPI comm = MPI.COMM_WORLD rank = comm.Get_rank() size = comm.Get_size() # 每个进程准备自己的数据（NumPy 数组） sendbuf = np.array([rank * 10], dtype=int) if rank == 0: # 预先分配 recvbuf（大小必须匹配） recvbuf = np.empty(size, dtype=int) else: recvbuf = None # 非 root 进程不需要 recvbuf # 使用大写 Gather（修改 recvbuf） comm.Gather(sendbuf, recvbuf, root=0) if rank == 0: print("Gathered data:", recvbuf) # 输出：[0, 10, 20, ...]

• Gather 需要预先分配 recvbuf （在 root 进程）

• 适用于高性能计算（避免 Python 对象的额外开销）

类似函数总结

小写（Pythonic）	大写（传统 MPI）	用途
bcast	Bcast	广播数据
scatter	Scatter	分散数据
gather	Gather	收集数据
allgather	Allgather	全收集
reduce	Reduce	规约计算
allreduce	Allreduce	全规约
scan	Scan	前缀计算

---

附录：分布式中 GPU 主要集体通信操作介绍

• 分布式计算中常用的集体通信（Collective Communication）操作有All-Gather、All-Reduce 和 Reduce-Scatter，主要用于多进程或多设备（如GPU）之间的数据交互

All-Gather（全收集）

• All-Gather：每个进程提供一块数据，最终所有进程收集到所有其他进程的数据，结果是一个包含所有数据的聚合
• 输入：每个进程有一块独立数据（如 data_i）
• 输出：所有进程得到相同的全量数据（[data_0, data_1, ..., data_n]）
• 举例：进程0有 A，进程1有 B，进程2有 C -> 最终所有进程得到 [A, B, C]
• 功能：参数广播、分布式训练中同步模型参数

All-Reduce（全规约）

• All-Reduce：先对所有进程的数据进行规约操作（如求和、最大值等），然后将结果分发给所有进程
• 输入：每个进程有一块数据（如 data_i）
• 计算：对所有 data_i 执行规约（如 sum(data_0, data_1, ..., data_n)）
• 输出：所有进程得到相同的规约结果（如 sum）
• 举例：进程0有 1，进程1有 2，进程2有 3 -> 求和后所有进程得到 6
• 功能：梯度聚合（如分布式训练中多卡梯度的全局求和）

Reduce-Scatter（规约散播）

• Reduce-Scatter：先对所有进程的数据进行规约操作，然后将结果按块分散到不同进程中，每个进程只获得结果的一部分
• 输入：每个进程有一块数据（如 data_i）
• 计算：规约所有数据（如 sum），然后将结果按进程数切分
• 输出：进程 i 获得结果的第 i 块
• 举例：进程0有 [1, 2]，进程1有 [3, 4]，进程2有 [5, 6] -> 全局求和为 [9, 12]，然后进程0得到 9，进程1得到 12
• 功能：分布式矩阵计算中分块结果的聚合

整体总结

操作	输入	计算步骤	输出	是否全量同步
All-Gather	每个进程一块数据	收集所有数据并广播	所有进程获得全量数据	是
All-Reduce	每个进程一块数据	规约所有数据并广播结果	所有进程获得相同的规约结果	是
Reduce-Scatter	每个进程一块数据	规约所有数据并按块分发	每个进程只获得结果的一部分	否

特别说明

• All-Reduce 可以拆分为 Reduce-Scatter + All-Gather（先局部规约后全局同步）
• 性能差异 ：All-Reduce 通常比分开的两步操作更高效（优化后的算法如 Ring-AllReduce）

---

附录：Ring-AllReduce

• Ring-AllReduce 是 All-Reduce 的一种高效实现算法，也写为 Ring AllReduce、Ring All-Reduce 等

以数据并行（DP）场景为例

• 假设有 N 个 GPU，每个 GPU 上都有全部参数和一部分数据
• 目标是保证所有 GPU 都能完成一次完整的参数更新
• 特别注意：
  • 每个 GPU 都只有一部分数据，所以需要拿到其他 GPU 的数据才能计算梯度（仅依赖自身甚至算不出任何一个参数的梯度）
  • 有很多参数，每个 GPU 都要完成所有参数的更新

Ring AllReduce 的核心思想

• Ring AllReduce 的核心思想是：
  • 先将所有 GPU 上的局部梯度数据按照参数分成不同的块（每个块包含一部分参数的局部梯度）
  • 把所有 GPU 组成一个逻辑上的环形结构 ，大家只和自己的“邻居”交流 ，然后通过多次传递 ，最终让所有人都得到完整的梯度结果

Ring AllReduce 工作流程（分两步走）

• 为了方便理解，本文假设有 4 个 GPU（A, B, C, D）

分块并传递（Reduce-Scatter 阶段）

• 这一阶段的目标是每个 GPU 负责一部分参数的梯度聚合（编码为 \(S_0, S_1, S_2, S_3\)）
• 首先，每个 GPU 把自己手里的局部梯度按照参数平均分成 N 份（每份叫一个“块”）
• 然后，大家开始轮流传递：每个 GPU 把自己一部分的“块”传给右边的邻居，同时从左边的邻居那里接收一个“块”
• 当收到邻居的“块”后，就把这个“块”和自己对应的“块”进行合并（比如求和）
• 这个过程重复进行 N-1 次，直到每个人的手里都拿到了自己负责的参数对应那部分的梯度并完成聚合
• 举个例子：
  • A 有局部梯度 \(A_0, A_1, A_2, A_3\)，下标表示参数块的索引
  • B 有局部梯度 \(B_0, B_1, B_2, B_3\)，下标表示参数块的索引
  • C 有局部梯度 \(C_0, C_1, C_2, C_3\)，下标表示参数块的索引
  • D 有局部梯度 \(D_0, D_1, D_2, D_3\)，下标表示参数块的索引
  • 假设某个 GPU 的目标是最终实现参数块 0 的梯度累加计算，即 \(S_0 = A_0+B_0+C_0+D_0\)
    • 其他 GPU 的最终目标分别是实现 1，2，3 块参数的梯度累加
• 第一轮：
  • A 把 \(A_1\) 给 B，从 D 收到 \(D_0\)
  • B 把 \(B_2\) 给 C，从 A 收到 \(A_1\)
  • C 把 \(C_3\) 给 D，从 B 收到 \(B_2\)
  • D 把 \(D_0\) 给 A，从 C 收到 \(C_3\)
  • 然后大家各自合并收到的数据：
    • A 现在有 \(A_1, A_2, A_3\), 还有 \((A_0+D_0)\)（计算后的结果）
    • B 现在有 \(B_0, B_2, B_3\), 还有 \((B_1+A_1)\)（计算后的结果）
    • C 现在有 \(C_0, C_1, C_3\), 还有 \((C_2+B_2)\)（计算后的结果）
    • D 现在有 \(D_0, D_1, D_2\), 还有 \((D_3+C_3)\)（计算后的结果）
• 第二轮：
  • A 把 \((A_0+D_0)\) 给 B，从 D 收到 \((D_3+C_3)\)
  • B 把 \((B_1+A_1)\) 给 C，从 A 收到 \((A_0+D_0)\)
  • C 把 \((C_2+B_2)\) 给 D，从 B 收到 \((B_1+A_1)\)
  • D 把 \((D_3+C_3)\) 给 A，从 C 收到 \((C_2+B_2)\)
  • 然后大家合并各自收到的数据：
    • A 现在有 \((A_0+D_0), A_1, A_2\), 还有 \((A_3+C_3+D_3)\)（计算后的结果）
    • …
    • D 现在有 \(D_0, D_1, (D_3+C_3)\), 还有 \((B_2+C_2+D_2)\)（计算后的结果）
• 这个过程会进行 \(N-1\) 次（N 是参与者的数量），最终每个人手里都会有一部分“最终总和”的数据
  • 最终得到，A 手里有 \(S_2\) ，B 手里有 \(S_3\) ，C 手里有 \(S_0\)，D 手里有 \(S_1\)

收集并广播（All-Gather 阶段）

• 所有 GPU 再次开始传递，这次传递不再进行计算，而是把自己手里已经计算好的梯度，传给右边的邻居
• 当收到邻居的数据后，就把它保存下来
• 这个过程也重复进行，直到每个人都收到了所有梯度
• 不是一般性，假定（注意：与上面不同，但是不影响推导和理解）：
  • 现在 A 手里有 \(S_0\) ，B 有 \(S_1\) ，C 有 \(S_2\) ，D 有 \(S_3\)
• 第一轮：
  • A 把 \(S_0\) 给 B
  • B 把 \(S_1\) 给 C
  • C 把 \(S_2\) 给 D
  • D 把 \(S_3\) 给 A
  • 然后大家各自保存收到的数据：
    • A 现在有了 \(S_0\) (自己的) 和 \(S_3\) (从 D 收到)
    • B 现在有了 \(S_1\) (自己的) 和 \(S_0\) (从 A 收到)
• 第二轮：
  • A 把 \(S_3\) 传递给 B
  • …
  • D 把 \(S_2\) 传递给 A
• 第三轮：
  • A 把 \(S_2\) 传递给 B，至此，B 从 A 处收到了 \(S_0, S_2, S_3\)，加上自己的 \(S_1\)，也就得到了完整的 \(S_0, S_1, S_2, S_3\)
  • 其他节点也一次类推
• 这个过程同样进行 \(N-1\) 次，最终每个人都会收集到所有的 \(S_0, S_1, S_2, S_3\)，从而得到了完整的总和

Ring AllReduce 的优点

• 高效利用带宽 ：去中心化设计是的它不会让某个节点成为瓶颈
  • 比如像传统的“参数服务器”模式，所有数据都传给一个中心服务器，而 Ring AllReduce 是让所有节点都参与数据传输和计算，充分利用了网络的带宽
• 良好的可扩展性 ：即使参与的设备数量很多，它的通信效率也能保持相对稳定
  • 非常适合大规模的分布式训练（比如训练大型深度学习模型）
• 降低延迟 ：通过分块和流水线式的传输，它能有效地减少数据同步的等待时间
• 特别说明：每个 GPU 只能和自己邻居交流这个约束，看似是限制，实际是非常巧妙地设计，是的数据通道建立一次即可，且传输是连续的

通信量对比

• Ring All-Reduce 是 All-Reduce 的一种高效实现方式，在通信量方面相比传统的All-Reduce有显著优势。
• 假设存在 \(N\) 个设备（如GPU），每个设备的数据大小为 \(\Phi\)
• 传统 All-Reduce 的原始版本中，每个GPU需要发送 \((N - 1)\Phi\) 个数据，\(N\) 个 GPU 的总通信量为
  $$N(N - 1)\Phi$$
  • 其通信量与GPU数量呈(N^2) 复杂度
• Ring All-Reduce 将每个 GPU 存储的数据顺序切分为 \(N\) 块，每块的数据量是 \(\frac{\Phi}{N}\)
  • Ring All-Reduce 包含 Reduce-Scatter 和 All-Gather 两个步骤，每个步骤都需要 \(N - 1\) 次通信，每次通信的数据量为 \(\frac{\Phi}{N}\)
  • 所以每个 GPU 的通信数据量为
    $$\frac{2(N - 1)\Phi}{N} \approx 2\Phi$$
• 与传统 All-Reduce 相比，Ring All-Reduce 的每个 GPU 通信量显著减少，且通信量与设备数量 \(N\) 无关，只受限于逻辑环中最慢的两个 GPU 的连接

---

二项分布（Binomial Distribution）

• 二项分布 ：是 \(p\) 次独立重复试验中成功的次数的离散概率分布，其中每次试验只有两种可能结果（成功或失败），成功概率为 \(p\) ，失败概率为 \(1-p\) ，其概率公式为：
  $$P(X = k)=C_{n}^{k}p^{k}(1 - p)^{n - k}$$
  • 其中 \(X\) 表示成功的次数， \(k\) 是具体的成功次数， \(C_{n}^{k}\) 是组合数
• 举例 ：如抛硬币 \(n\) 次，正面朝上的次数；多次独立射击，命中目标的次数等

---

多项分布（Multinomial Distribution）

• 多项分布 ：是二项分布的推广，用于描述在 \(n\) 次独立试验中，每次试验有 \(k\) 种互斥且完备的结果，每种结果出现的概率分别为 \(p_{1},p_{2},\cdots,p_{k}\) ，且 \(\sum_{i = 1}^{k}p_{i}=1\) ，其概率公式为：
  $$P(X_{1}=n_{1},X_{2}=n_{2},\cdots,X_{k}=n_{k})=\frac{n!}{n_{1}!n_{2}!\cdots n_{k}!}p_{1}^{n_{1}}p_{2}^{n_{2}}\cdots p_{k}^{n_{k}}$$
  • 其中 \(X_{i}\) 表示第 \(i\) 种结果出现的次数， \(n_{i}\) 是具体的次数， \(n=\sum_{i = 1}^{k}n_{i}\)
• 举例 ：如掷骰子多次，统计每个点数出现的次数；对人群进行分类调查，统计各类人群的数量等
• 多项分布与二项分布的区别 ：二项分布是针对只有两种结果的重复试验；多项分布是二项分布的推广，用于多种结果的重复试验

---

分类分布（Categorical Distribution）

• 分类分布 ：也叫范畴分布，是一种离散概率分布，用于描述一个随机变量在有限个类别中的取值概率。它是多项分布在 \(n = 1\) 时的特殊情况，其概率公式为：
  $$P(X = i)=p_{i}$$
  • 其中 \(X\) 表示随机变量， \(i\) 表示类别， \(p_{i}\) 是类别 \(i\) 出现的概率， \(\sum_{i = 1}^{k}p_{i}=1\)
• 举例 ：如一次抽奖，有多种奖品，抽到每种奖品的概率；对一个物体进行分类，它属于不同类别的概率等
• 注：强化学习中，离散动作的分布常常使用分类分布来表示（部分文献也称RL中的离散动作分布为广义伯努利分布）

---

广义伯努利分布（Generalized Bernoulli Distribution）

• 广义伯努利分布 ：是伯努利分布的推广，允许试验结果有多种，且每种结果的概率可以不同。它将伯努利分布从两种结果扩展到了多种结果的情，其概率公式为：
  $$P(X = x_{i})=p_{i}$$
  • \(X\) 是取值于 \({x_{1},x_{2},\cdots,x_{k}}\) 的随机变量，\(i = 1,2,\cdots,k\) ，且 \(\sum_{i = 1}^{k}p_{i}=1\)
• 举例 ：在一些多结果的单次试验场景中，如一次考试学生的成绩等级（优、良、中、差等）的概率分布
• 注：强化学习中，离散动作的分布常常使用分类分布来表示（部分文献也称RL中的离散动作分布为广义伯努利分布）

---

一些总结

• 二项分布是针对只有两种结果的重复试验（每次实验只有两种结果）；
• 多项分布是二项分布的推广，用于多种结果的重复试验（每次实验有多种结果）；
• 分类分布是多项分布在单次试验下的特殊情况；
• 广义伯努利分布也是对伯努利分布的推广，更侧重于单次试验有多种结果的情况，与分类分布类似，但表述上更强调对伯努利分布的扩展
  • 分类分布和广义伯努利分布形式相同，代码实现上也完全相同

最近在看一些书籍时看到一些函数空间的定义，本科学过一些，但是由于不常用忘得差不多了，本文总结一下希尔伯特空间、欧几里得空间和巴拿赫空间等函数空间的概念，本文是对相关概念的基础理解，非专业定义

• 参考博客:欧几里得空间与希尔伯特空间

---

前置说明

欧几里得空间、希尔伯特空间和巴拿赫空间属于函数空间。函数空间 = 元素 + 规则 ，即一个函数空间由 元素 与 元素所满足的规则 定义

---

概念说明

距离

距离 ：是指在一个空间中，两个元素之间的某种度量，表示它们之间的“远近”关系。对于集合 \(X\) 中的任意两个元素 \(x,y\) ，距离函数 \(d(x,y)\) 需要满足非负性、对称性、三角不等式等性质

• 满足三个属性可以简单理解为：
  • 大于0
  • A到B等于B到A
  • 满足三角不等式

范数

• 范数 ：是定义在向量空间上的一种函数，用于衡量向量的“长度”或“大小”。对于向量 \(x\) ，其范数 \(|x|\) 满足非负性、正齐次性、三角不等式
• 可简单理解为某个点到0点的距离
• 拥有范数的空间称作赋范空间

线性

• 线性 ：在数学中，线性意味着满足可加性和数乘性。对于空间 \(V\) 中的元素 \(x,y\) 以及标量 \(a,b\) ，若 \(ax + by\) 也属于 \(V\) ，则称 \(V\) 具有线性性质
• 简单理解：若一个空间为线性空间，只要我们知道了此空间的所有基，便可以用加法与数乘表示这一空间所有的元素

内积

• 内积 ：是两个向量之间的一种运算，它将两个向量映射为一个标量。对于向量 \(x,y\) ，内积 \(\langle x,y\rangle\) 满足共轭对称性、线性性、正定性
• 内积空间都是赋范空间
• 有限维内积空间便是我们最熟悉的欧几里得空间

完备性

• 完备性 ：一个空间是完备的，是指该空间中的任何柯西序列都收敛于该空间中的某个元素。柯西序列是指随着序列的推进，序列中的元素之间的距离越来越小，最终趋于零
• 柯西序列的定义和性质：
  • 柯西序列定义 ：设 \((X, d)\) 是一个度量空间， \({x_n}\) 是 \(X\) 中的一个序列。如果对于任意给定的正数 \(\epsilon>0\) ，存在正整数 \(N\) ，使得当 \(m, n>N\) 时，都有 \(d(x_m, x_n)<\epsilon\) ，则称序列 \({x_n}\) 是一个柯西序列（Cauchy sequence）。直观地说，柯西序列中的元素随着序号的增大，彼此之间的距离会越来越小，最终可以任意小
  • 柯西序列性质 ：
    • 有界性 ：在度量空间中，柯西序列一定是有界的。即存在一个正数 \(M\) 和一个点 \(x_0\in X\) ，使得对于所有的 \(n\) ，都有 \(d(x_n, x_0)\leq M\) 。
    • 唯一性 ：在完备度量空间中，柯西序列的极限是唯一的。也就是说，如果一个柯西序列收敛，那么它只能收敛到一个点
• 对完备性的简单理解：对集合中的元素取极限不超出此空间便称其具有完备性

---

整体总结

• 线性完备内积空间称作希尔伯特空间
• 线性完备赋范空间称作巴拿赫空间
• 有限维线性内积空间称作欧几里得空间，欧几里得空间是一种特殊的（有限维度）的希尔伯特空间

---

整体说明

• 为了从总体 规模为 \( N \) 的有限样本中需要抽取的样本单位数量，用于在满足特定精度要求的前提下开展抽样调查或统计分析
• 统计学中称满足特定精度的最小需要的样本总数为 有限总体校正（Finite Population Correction, FPC）
• 最小需要的样本总数常常用 \( n \)

---

有限总体校正的定义

• 有限总体校正（Finite Population Correction, FPC）样本量计算公式：
  $$ n = \frac{N \cdot Z^2 \cdot \sigma^2}{E^2 \cdot (N-1) + Z^2 \cdot \sigma^2} $$
  • 上述公式适用于总体规模 \( N \) 有限（而非无限大）的场景（例如从1000人的班级中抽样，而非从“所有中国人”中抽样）
• 各参数含义如下：
  • \( n \) ：目标样本量 ，最终需要抽取的样本数量，公式计算结果
  • \( N \) ：总体规模 ，研究对象的总数量，如某学校的总学生数、某企业的总员工数
  • \( Z \) ：Z值 ，对应指定置信水平的标准正态分布分位数，如95%置信水平对应的 \( Z \approx 1.96 \)，99%置信水平对应的 \( Z \approx 2.58 \)
  • \( \sigma^2 \) ：总体方差 ，总体中研究变量的离散程度，若总体方差未知，通常用历史数据或预调查的样本方差 \( s^2 \) 替代
  • \( E \) ：边际误差（允许误差） ，抽样结果与总体真实值的最大允许偏差，如“调查结果误差不超过3%”，则 \( E = 0.03 \)

---

有限总体校正公式适用场景

• 当总体规模 \( N \) 较大（如 \( N > 1000 \)）且抽样比例（\( n/N \)）较小时（通常小于5%），有限总体校正的影响可忽略，公式可简化为无限总体下的样本量公式：
  $$ n \approx \frac{Z^2 \cdot \sigma^2}{E^2} $$
• 当总体规模 \( N \) 有限（如 \( N < 1000 \)）或抽样比例较大（如超过5%）时，必须使用原公式（含有限总体校正项）计算 \( n \)，否则会导致样本量估算偏大，造成资源浪费

---

解析解（Analytical Solution）

• 解析解指的是通过标准的数学操作（如代数运算、积分、微分等）得到的精确表达式，该表达式可以是有限项的公式或无限级数的形式。解析解通常意味着我们能够以明确的数学形式写出问题的解答，而不需要进行数值逼近

---

闭式解（Closed-form Solution）

• 闭式解是一种特殊的解析解 ，它指的是一类可以用有限数量的标准数学操作和已知函数（如指数函数、对数函数、三角函数等基本初等函数及其组合）表达的解析解。换句话说，闭式解是可以直接计算出来的，而不是需要迭代过程或者近似方法来获得的结果

---

解析解和闭式解的区别

• 所有的闭式解都是解析解，但并非所有解析解都是闭式解。解析解可以包含无限级数或者其他非闭式的表达形式
• 当我们说一个问题是可解析求解（或有解析解）时，意味着存在一个理论上精确的数学表达式作为答案；而当我们提到闭式解时，则进一步强调了这个解可以由有限次的基本数学运算得出。

PID相关笔记

---

PID相关参考

• 一个简短的PID描述：PID控制原理，看了开头，你就会看到结尾！
  • 包含修改参数带来的系统输出变化可视化示例
• 非常详细的讲解：从不懂到会用！PID从理论到实践~

---

位置式PID

• 位置式PID在 \(k\) 时刻的直接输出为控制量 \( u(k) \)，其离散形式为：
  $$
  u(k) = K_p \color{blue}{e(k)} + K_i \color{blue}{\sum_{j=0}^{k} e(j)} + K_d \color{blue}{\left[ e(k) - e(k-1) \right]}
  $$
• 其中：
  • \( K_p, K_i, K_d \) 分别为比例、积分、微分系数；
  • \( e(k) \) 为当前时刻误差；
  • \( \sum_{j=0}^{k} e(j) \) 为历史误差累加（积分项）
• 进阶：
  • \( K_i = K_p \frac{T}{T_i} \)：积分系数（\( T_i \)为积分时间常数，\( T \)为采样时间）
  • \( K_d = K_p \frac{T_d}{T} \)：微分系数（\( T_d \)为微分时间常数）

---

增量式PID

• 增量式PID的输出是控制量的增量
  $$ \Delta u(k) = u(k) - u(k-1) $$
• 类似位置式PID ，增量式PID在 \(k\) 时刻的 \(u(k)\) 可定义为如下：
  $$
  \begin{align}
  u(k) &= u(k-1) + \color{red}{\Delta u(k)} \\
  u(k) &= u(k-1) + (K_p + K_i + K_d) \color{red}{e(k)} - (K_p + 2K_d) \color{red}{e(k-1)} + K_d \color{red}{e(k-2)} \\
  u(k) &= u(k-1) + A \color{red}{e(k)} + B \color{red}{e(k-1)} + C \color{red}{e(k-2)}
  \end{align}
  $$
• 注：一般提到增量式PID ，我们一般认为输出是 控制量的增量 \(\Delta u(k)\)

---

位置式PID到增量式PID的推导

• 位置式PID和增量式PID完全等价，只是形式不同，通过对位置式PID做一阶差分 ，即可得到增量式PID
• 位置式在 \( k-1 \) 时刻的输出 \( u(k-1) \) 为：
  $$
  u(k-1) = K_p e(k-1) + K_i \sum_{j=0}^{k-1} e(j) + K_d \left[ e(k-1) - e(k-2) \right]
  $$
• 将 \( u(k) \) 和 \( u(k-1) \) 相减等到增量 \( \Delta u(k) = u(k) - u(k-1) \)：
  $$
  \Delta u(k) = K_p \left[ e(k) - e(k-1) \right] + K_i e(k) + K_d \left[ e(k) - 2e(k-1) + e(k-2) \right]
  $$
• 整理后得到增量式PID公式：
  $$
  \Delta u(k) = (K_p + K_i + K_d) e(k) - (K_p + 2K_d) e(k-1) + K_d e(k-2)
  $$

---

增量式PID到位置式PID的推导

• 已知增量式PID的参数为A、B、C，其增量输出公式为：
  $$\Delta u(k) = A \color{red}{e(k)} + B \color{red}{e(k-1)} + C \color{red}{e(k-2)}$$
• 通过对比位置式PID的差分形式，可以推导出位置式PID参数（Kp、Ki、Kd）与增量式参数的关系如下：
• 位置式PID的输出为：
  $$u(k) = K_p \color{blue}{e(k)} + K_i \color{blue}{\sum_{j=0}^{k} e(j)} + K_d \color{blue}{\left[ e(k) - e(k-1) \right]}$$
• 增量式PID的输出是位置式的差分：
  $$\Delta u(k) = u(k) - u(k-1).$$
  • 将位置式公式代入差分表达式并整理，得到：
    $$\Delta u(k) = \left(K_p + K_i + K_d\right)e(k) + \left(-K_p - 2K_d\right)e(k-1) + K_d e(k-2).$$
• 对比系数 ，得到方程组：
  $$
  \begin{align}
  A &= K_p + K_i + K_d,\\
  B &= -K_p - 2K_d,\\
  C &= K_d
  \end{align}
  $$
• 解方程组得位置式PID的参数为：
  $$
  \begin{align}
  \color{red}{K_p} &= -B - 2C,\\
  \color{red}{K_i} &= A + B + C,\\
  \color{red}{K_d} &= C
  \end{align}
  $$

---

增量式PID和位置式PID简单对比

特性	位置式PID	增量式PID
输出形式	绝对控制量（如阀门开度）	控制增量（如步进脉冲）
积分处理	显式累加误差，易饱和	隐式累加，天然抗饱和
计算复杂度	需存储所有误差，计算量大	仅需最近几次误差，计算量小
等效性	通过差分可转化为增量式	通过累加可转化为位置式

---

附录：现实场景中的一些trick

常用形式一：使用了 \( \lambda(k-1) \)的位置式PID

• 适用场景：在一些场景中，控制变量 \( \lambda \) 需要平滑调整 ，而非完全重新计算（比如oCPX出价中）
• 常用位置式PID来输出某个变量的增量（直接计算全量 \( \lambda(k) \) 可能导致相邻时间片的出价跳跃，而基于前一时刻的 \( \lambda(k-1) \) 进行增量调整，可以保证控制量的连续性），工程师可能会将位置式PID改写为以下形式：
  $$
  \begin{align}
  \lambda(k) &= \lambda(k-1) + \color{red}{\Delta \lambda(k)} \\
  \lambda(k) &= \lambda(k-1) + \color{red}{u(k)} \\
  \lambda(k) &= \lambda(k-1) + \color{red}{\left[ K_p e(k) + K_i \sum e(k) + K_d (e(k)-e(k-1)) \right]} \\
  \end{align}
  $$
  • 理解：这是一个位置式PID ，其中 \(\lambda\) 与PID无关，属于被控对象的一部分，其中PID输出为该变量的增量：
    $$ u(k) = \color{red}{\Delta \lambda(k)} = \color{red}{\left[ K_p e(k) + K_i \sum e(k) + K_d (e(k)-e(k-1)) \right]} $$
  • 问题：当 \(e(t)\) 为0时，由于积分项的存在，\(\color{red}{\Delta \lambda(k)}\) 可能不为0，\(u(k)\) 还会持续变化，这个是否符合预期？这个问题的简单理解如下：
    • 对于系统需要 \(u(k)\) 持续增加的场景，比如系统是一个压力越来越大的弹簧，\(u(k)\) 是施加的反向力，需要逐步增大，则这种情况天然适配这种设计，持续增加的 \(u(k)\) 能与系统逐步增加的压力抵消，保持稳态
    • 对于系统不需要 \(u(k)\) 持续增加的场景，假设 \(\color{red}{\Delta \lambda(k)} > 0\)，则 \(u(k)\) 会继续增大，超调以后，积分项会逐步减少，同时 \(e(t) \neq 0\)，也会开始减小 \(\color{red}{\Delta \lambda(k)} \)，逐步地，\(\color{red}{\Delta \lambda(k)} = 0\)，然后逐步变成负值，直到 \(e(t)\) 再次为0时，此时的积分项比上一轮更小了，\(\color{red}{\Delta \lambda(k)}\) 也更小了，甚至为负，也就是说，对于积分项逐步地应该也会收敛到0
• 注：由于\(\lambda(k-1)\)中其实包含了累计误差的信息，可以进一步不考虑积分项（微分项一般不用考虑，这里顺便消除了），甚至可以简化为下面的公式形式：
  $$\lambda(k) = \lambda(k-1) + \color{blue}{K_p} \color{red}{e(k)}$$
  • 这种形式的优点：一定程度上，\(\lambda(k-1)\)中其实包含了累计误差的信息，可以在不包含 \(K_i\)的情况下实现类似积分项效果，存储和更新 \( \lambda(k-1) \) 比维护全局积分项 \( \sum e(k) \) 更简单（后者需持久化历史状态）
  • 此时也可以用增量式PID来理解这种公式，本文下面会聊到增量式PID下这种形式的含义

---

附录：增量式PID的实际使用简化

• 增量式PID可能简化为只保留 \(e_t\) 相关的项，即：
  $$u(k) = u(k-1) + \color{blue}{A} \color{red}{e(k)}$$
• 对照增量式PID的公式：
  $$
  \begin{align}
  u(k) &= u(k-1) + \color{red}{\Delta u(k)} \\
  u(k) &= u(k-1) + (K_p + K_i + K_d) \color{red}{e(k)} - (K_p + 2K_d) \color{red}{e(k-1)} + K_d \color{red}{e(k-2)} \\
  u(k) &= u(k-1) + A \color{red}{e(k)} + B \color{red}{e(k-1)} + C \color{red}{e(k-2)}
  \end{align}
  $$
• 可以看出此时相当于没有 \(C = K_d = 0\)，结合 \(B = - (K_p + 2K_d) = 0\)，进一步有 \(K_p = 0\)，最终可得：
  $$ \color{blue}{A} = K_i $$
• 也就是说，此时相当于只包含 \(K_i\) 项的位置式PID
  • 进一步理解：其实只包含 \(K_i\) 项的位置式PID ，本质上可以等价于包含 \(K_i,K_p\) 项的位置式PID（但需要 \(K_i,K_p\) 系数服从某种关系）

---

附录：oCPX下PID的理想设计方式

• oCPX的真正目标 ：oCPX的最终目标是保整个投放周期内的ROI满足约束
• 应该如何设计误差项 \(e(t)\)？
  • 如果 \(e(t)\) 表示时间片 \(t\) 的达成情况 ，则其值是根据时间片 \(t\) 内的消耗和收入计算出来的，则难以真正满足全天的ROI达成；此外，实际场景中，单个时间片的数据可能会非常稀疏 ，特别是oCPX的场景计算ROI需要用到订单数据，中小广告主的订单数据往往是非常稀疏的
    • 存在稀疏的情况。解决思路：一个思路改进是可以考虑用预估值去代替真实值，从而缓解稀疏问题
    • 难以达成全站ROI目标。解决思路：在原有PID基础上，引入累计偏差补偿项 \(\gamma \cdot \text{Global}_\text{Error}\)，确保全天ROI收敛
  • 如果 \(e(t)\) 表示截止到时间片 \(t\) 的达成情况 ，值是根据投放周期开始到 \(t\) 时间片的消耗和收入计算出来的，则 \(e(t)\) 直接表达了截止到时间片 \(t\) 的ROI达成情况，这种设计下 \(e(t)=0\) 时说明全天刚好达成
    • 可以缓解稀疏问题
    • 更贴近oCPX产品的目标
  • 结论：
    • 订单稠密的场景可以考虑使用时间片 \(t\) 的达成情况 ，再增加引入累计偏差补偿项 \(\gamma \cdot \text{Global}_\text{Error}\)，确保全天ROI收敛
    • 订单稀疏的场景使用截止到时间片 \(t\) 的达成情况 ，可以缓解稀疏问题
• 对于无法获取分时间特征（无法计算位置式PID的积分项），且无法存储上一时间片的PID输出（无法用增量式PID）的情况，如何设计PID？
  • 一个思路是使用截止到时间片 \(t\) 的达成情况 ，且仅使用 \(K_p\) 参数，这样至少目标是达成全天的ROI目标，这种方法可能导致商家存在稳态误差（因为没有积分项）
• 其他优化点：
  • 可以对 \(e(t)\) 做一个量纲映射，比如除以目标ROI以保证误差在指定范围内（特别是对于保CPS的场景，不同商家的CPS甚至不在统一量纲，想用相同的 \(K_p,K_i,K_d\) 参数来控制所有商家是困难的）：
    $$ e(t) = \frac{真实ROI-目标ROI}{\color{red}{目标ROI}}$$
  • 初期数据量较少时不要调控，因为数据还不够准确，初期就开始调控可能导致商家初期出价波动较大
  • 可以统计过去一天或多天的PID输出作为下一天的初始出价 K 值，使得PID更容易达成，也让商家初期的消耗更符合ROI目标

---

附录：PID的其他优化

积分限幅

• 现象：当因为不可抗力影响系统时，误差积分会一直增加，为了防止不可抗力消失的瞬间出现问题，可以给误差积分增加一个限制幅度（最大值）
• 举例：无人机中这个现象可以看做一段时间内是有人压着无人机不许升高；在智能算力场景可以看做是非高峰期间，无论PID如何调整，TP999都到不了目标值
• 解法：对误差积分项加一个上限，称为“积分限幅”

积分分离

• 现象：目标有修改时，误差会突然增加，短时间内误差非常大，容易出现超调
• 解法：对误差做一个条件判断，如果瞬间出现较大误差（比如超过一个阈值），可以让KI项的系数为0（注意不是清空KI项），只使用Kp项来调节；直到误差重新回到阈值以下，KI再生效

Kp上调下调差异化

• 在一些场景上，如果对超成本和欠成本有倾向，可以通过设置上调和下调不同Kp来实现，比如，对于厌恶超成本的场景，可以适当增大下调系数，提升上调系数

• 参考链接：
  • 参考博客： https://www.cnblogs.com/kyrieng/p/8694705.html

---

自信息（Self-Information）：\(I(x)\)

自信息的来源讨论

• 一条信息的信息量大小和它的不确定性有直接的关系，信息量的度量就等于不确定性的多少
• 考虑一个离散随机变量 \(x\)，随机变量的信息量由概率分布 \(p(x)\) 确定
• 我们的目标是找到一个函数 \(I(x) = f(p(x))\) (自变量是 \(p(x)\)，因为随机变量的信息量由概率分布确定)，能够衡量 \(x\) 信息内容的多少
  • 且必须是概率分布 \(p(x)\) 的单调函数?
• 现在考虑同时出现两个相互独立的随机变量 \(x\) 和 \(y\)，那么他们的信息量和应该是
  $$I(x,y) = I(x)+I(y) = f(p(x)) + f(p(y))$$
  • 同时他们的联合概率分布为
    $$p(x,y) = p(x)p(y)$$
• 由上面的两个表达式可以知道 \(f(\cdot)\) 应该是一个对数相关的函数,因为
  $$log_{a}(MN) = log_{a}M + log_{a}N$$
• 所以我们可以考虑把原始信息量定义为
  $$I(x) = f(p(x)) = -log p(x)$$
  • 其中负号是用来保证信息量是正数或者零
  • log 函数基的选择是任意的（信息论中基常常选择为 2，因此信息的单位为比特 bits；而机器学习中基常常选择为自然常数，因此单位常常被称为奈特 nats）
• \(I(x)\) 也被称为随机变量 \(x\) 的自信息(self-information)，描述的是随机变量的某个事件发生所带来的信息量

自信息精确定义

• 在信息论中，自信息（Self-Information） 是衡量单个随机事件发生时所携带的信息量的指标
  • 自信息的核心思想是：事件发生的概率越低，它携带的自信息就越大；反之，概率越高，自信息越小
• 定义：对于离散随机变量 \(X\)，若某个事件 \(x\) 发生的概率为 \(P(x)\)，则该事件的自信息定义为：
  $$
  I(x) = -\log_b P(x)
  $$
  • 底数 \(b\) 决定自信息的单位：
    • 当 \(b=2\) 时，单位为 比特（bit） （这是最常用的设定）
    • 当 \(b=e\) 时，单位为 奈特（nat）
    • 当 \(b=10\) 时，单位为 哈特（hart）
• 自信息的核心性质
  1）非负性：由于 \(0 \leq P(x) \leq 1\)，\(\log P(x) \leq 0\)，因此 \(I(x) \geq 0\)
  2）单调性：自信息与事件概率成反比

    * 若事件必然发生（\\(P(x)=1\\)），则 \\(I(x)=0\\)，该事件不携带任何新信息；
    * 若事件概率极低（\\(P(x)\rightarrow0\\)），则 \\(I(x)\rightarrow\infty\\)，该事件发生时会携带极大的信息量

  3）独立性：若两个事件 \(x\) 和 \(y\) 相互独立，则联合事件 \(xy\) 的自信息等于两个事件自信息之和，即

    $$
    I(xy) = I(x) + I(y)
    $$

---

熵（也称为信息熵）：\(H(x)\)

熵的起源讨论

• 现在假设一个发送者想传送一个随机变量的值给接收者
• 那么在这个过程中，他们传输的平均信息量可以通过求 \(I(x)=−logp(x)\) 关于概率分布 \(p(x)\) 的期望得到:
  $$
  \begin{align}
  H(x) &= \sum_{x}p(x)(-logp(x)) \\
  &= -\sum_{x}p(x)logp(x) \\
  &= -\sum_{i=1}^{n}p(x_{i})logp(x_{i})
  \end{align}
  $$
• \(H(X)\) 就被称为随机变量 \(x\) 的熵，它是表示随机变量不确定的度量，是对所有可能发生的事件产生的信息量的期望
• 从公式可得，随机变量的取值个数越多，状态数也就越多，信息熵就越大，混乱程度就越大,当随机分布为均匀分布时，熵最大，且
  $$0 ≤ H(X) ≤ logn$$
• 上式的证明如下：
  $$p(1)+p(2)+\dots+p(n)=1$$
  • 目标函数
    $$f(p(1),p(2),\dots,p(n))=-(p(1)logp(1)+p(2)logp(2)+\dots+p(n)logp(n))$$
  • 约束条件
    $$g(p(1),p(2),\dots,p(n),\lambda)=p(1)+p(2)+\dots+p(n)-1=0$$
  • 定义拉格朗日函数
    $$
    L(p(1),p(2),\dots,p(n),\lambda)=-(p(1)logp(1)+p(2)logp(2)+\dots+p(n)logp(n))+\lambda(p(1)+p(2)+\dots+p(n)-1)
    $$
  • 对 \(p(i)\) 和 \(\lambda\) 求偏导,并令其等于0得
    $$p(1)=p(2)=\dots=p(n)=\displaystyle\frac{1}{n}$$
  • 带入目标函数得
    $$
    \begin{align}
    f(\displaystyle\frac{1}{n},\frac{1}{n},\dots,\frac{1}{n}) &= -(\frac{1}{n}log\frac{1}{n} + \frac{1}{n}log\frac{1}{n} + \dots + \frac{1}{n}log\frac{1}{n}) \\
    & = -log(\frac{1}{n}) \\
    & =\log(n)
    \end{align}
    $$

熵的精确定义

• 在信息论与概率论中，熵（Entropy） 是衡量随机变量不确定性大小的核心量化指标，其本质是随机变量所有可能事件的自信息的数学期望
• 根据随机变量的类型，熵的定义分为离散型和连续型两类

离散随机变量的熵（信息熵）

• 设离散随机变量 \(X\) 的取值集合为 \(\{x_1,x_2,\dots,x_n\}\)，对应的概率分布为 \(P(X=x_i)=p_i\)（满足归一化条件 \(\sum_{i=1}^n p_i = 1\)），则 \(X\) 的熵定义为：
  $$
  H(X) = -\sum_{i=1}^n p_i \log_b p_i
  $$
  • 其中底数 \(b\) 决定熵的单位：
    • \(b=2\)：单位为 比特（bit） ，是信息论中最常用的单位
    • \(b=e\)：单位为 奈特（nat） ，适用于理论推导（自然对数）
    • \(b=10\)：单位为 哈特（hart） ，较少使用

离散随机变量的熵的核心性质

• 非负性：\(H(X) \geq 0\)，当且仅当 \(X\) 为确定事件（某一 \(p_i=1\)，其余 \(p_i=0\)）时，\(H(X)=0\)；
• 极值性：当 \(X\) 的所有取值等概率分布时，熵达到最大值 \(H_{\text{max} }(X)=\log_b n\)，此时不确定性最高；
• 可加性：若离散随机变量 \(X\) 与 \(Y\) 相互独立，则联合熵 \(H(X,Y)=H(X)+H(Y)\)

连续随机变量的熵（微分熵）

• 对于连续随机变量 \(X\)，其概率密度函数为 \(p(x)\)，则微分熵定义为：
  $$
  h(X) = -\int_{-\infty}^{\infty} p(x)\log_b p(x) dx
  $$

连续随机变量的熵 vs 离散随机变量的熵

• 微分熵不满足非负性 ，其值可以为负数（例如均匀分布 \(U(a,b)\) 的微分熵为 \(\log(b-a)\)，当 \(b-a<1\) 时熵为负）
• 微分熵的物理意义与离散信息熵略有不同，它衡量的是连续变量分布的“相对不确定性”，而非绝对信息量

自信息与熵的关系

• 两者的关系公式为：
  $$
  H(X) = \mathbb{E}[I(x)] = \sum_{x\in X} P(x) \cdot I(x) = -\sum_{x\in X} P(x)\log P(x)
  $$
• 简单来说：
  • 自信息描述单个事件的信息量
  • 熵描述整个随机变量的平均信息量

---

互信息（Mutual Information, MI）：\(I(X;Y)\)

• 在概率论与信息论中，两个随机变量 \(X\) 和 \(Y\) 的互信息（Mutual Information, MI） 用于衡量它们之间的相互依赖程度
• 互信息的核心是量化“已知一个随机变量的信息后，另一个随机变量的不确定性减少的量”

离散随机变量的互信息定义

• 若 \(X\) 和 \(Y\) 为离散随机变量，联合概率分布为 \(P(X,Y)\)，边缘概率分布分别为 \(P(X)\) 和 \(P(Y)\)，则互信息的定义为：
  $$
  I(X;Y)=\sum_{x\in X}\sum_{y\in Y}P(x,y)\log\frac{P(x,y)}{P(x)P(y)}
  $$
  • 当 \(X\) 和 \(Y\) 相互独立时，\(P(x,y)=P(x)P(y)\)，此时 \(I(X;Y)=0\)；
  • 当 \(X\) 和 \(Y\) 完全依赖时，\(I(X;Y)\) 达到最大值，等于 \(X\) 或 \(Y\) 的熵（\(H(X)\) 或 \(H(Y)\)）

连续随机变量的互信息定义

• 若 \(X\) 和 \(Y\) 为连续随机变量，联合概率密度函数为 \(p(x,y)\)，边缘概率密度函数分别为 \(p(x)\) 和 \(p(y)\)，则互信息的定义为：
  $$
  I(X;Y)=\int_{-\infty}^{\infty}\int_{-\infty}^{\infty}p(x,y)\log\frac{p(x,y)}{p(x)p(y)}dxdy
  $$

互信息的等价公式

• 互信息可以通过熵（Entropy） 和条件熵（Conditional Entropy） 推导，核心等价关系为：
  $$
  I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(X,Y)
  $$
  • \(H(X)\) 是 \(X\) 的熵，衡量 \(X\) 的不确定性
  • \(H(X|Y)\) 是给定 \(Y\) 时 \(X\) 的条件熵，衡量已知 \(Y\) 后 \(X\) 剩余的不确定性
  • \(H(X,Y)\) 是 \(X\) 和 \(Y\) 的联合熵

互信息 与 InfoNCE 的关联

• InfoNCE 损失的设计目标是最大化互信息的下界 ，而非直接计算互信息
• 当负样本数量 \(K\rightarrow\infty\) 时，InfoNCE 损失对应的下界会收敛到真实的互信息 \(I(X;Y)\)，这也是该 InfoNCE 损失函数命名的核心原因

---

题目

• 有27个参加跑步的人，每3人一组，分成9组，同一组用同一个号。就是1号3个，2号3个，3号3个……现在假设第一组的赢得了比赛，每次只有一个人到达。所有人到达的时候满足规律，1号参赛者之间都间隔一个人，2号参赛者之间都间隔2个人，3号参赛者之间都间隔3个人…9号参赛者之间都间隔9人。问27个人的到达顺序是否有解？如果有，解是什么？

---

解决方案

• 解决方案（Python 代码）

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

  def check_row(row, gap): a = abs(row[0] - row[1]) == gap b = abs(row[1] - row[2]) == gap c = abs(row[2] - row[0]) == gap abc = [a, b, c] if sum([1 if e else 0 for e in abc]) != 2: return False return True def generate_conds(ri, rest_number): size = len(rest_number) gap = ri + 2 conds = list() for i in range(size): for j in range(i+1, size): for k in range(j+1, size): row = rest_number[i], rest_number[j], rest_number[k] if check_row(row, gap): conds.append(row) return conds def backtrace(maze, ri, rest_number, all_maze): if not rest_number: data_ = [[e for e in row] for row in maze] all_maze.append(data_) return True conds = generate_conds(ri, rest_number) if not conds: return False for row in conds: local_rest = [e for e in rest_number] for e in row: # print("local rest: %s and e: %s" % (local_rest, e)) local_rest.remove(e) maze[ri] = [e for e in row] backtrace(maze, ri + 1, local_rest, all_maze) def solution(): maze = list() for i in range(9): row = [0 for _ in range(3)] maze.append(row) rest_number = list(range(1, 28)) maze[0][0] = 1 maze[0][1] = 3 maze[0][2] = 5 rest_number.remove(1) rest_number.remove(3) rest_number.remove(5) all_maze = list() # print(rest_number) # print(maze) backtrace(maze, 1, rest_number, all_maze) for maze in all_maze: print(maze) if __name__ == "__main__": solution()