早期判决，更优预算：面向计算高效RLVR的顺序自适应rollout分配

# 早期判断，更优预算：面向计算高效RLVR的序列自适应展开分配

**来源：** https://arxiv.org/html/2607.26253

Pixel Nomand¹, Elena Voss¹, Marcus Hale², Sofia Reyes¹

¹威斯康星大学麦迪逊分校 ²华盛顿大学

###### 摘要

具有可验证奖励的强化学习（RLVR）的瓶颈在于生成rollout，然而许多采样得到的提示会产生*饱和*组（所有回答正确或所有回答错误），其奖励方差为零，因此无法提供策略梯度信号。现有的补救方法要么对更大的候选池进行过采样，然后丢弃饱和提示（动态采样），从而付出高昂的额外rollout代价；要么在采样*之前*预测提示难度，这在策略不断变化的情况下是脆弱的。我们观察到，一个组的有效性通常在其rollout的前几步之内就已*决定*，因此将完整的组预算花在已经决定了的提示上是一种浪费。我们将逐步骤的rollout收集建模为一个预算受限的*序列分配*（最优停止）问题，并提出了SARA（序列自适应展开分配）。SARA为每个提示的成功率维护一个Beta后验分布，评估一个组有效性的闭式预测器，并应用一个双阈值、SPRT风格规则：对有效的组予以确认，在短暂探测后放弃饱和组，并将释放的预算重新分配到新的提示上，无需任何额外的预测rollout。我们证明了放弃的可靠性、预期的rollout节省、固定预算下的收益优势，以及有效组收益与GRPO梯度范数之间的联系。在单个GPU上使用1.5B/3B模型进行数学推理和规划时，SARA在匹配DPS（两者均低于DS oracle）的同时，比DS少使用22%的rollout；将SARA与DPS结合使用可获得最佳准确率，略高于DS，同时rollout使用量减少67%（成本近乎均匀）。

## 1 引言

具有可验证奖励的强化学习（RLVR）已成为大型语言模型（LLM）激发推理能力的核心后训练机制，应用范围从数学问题求解到多步骤规划和代码（Jaech等人，2024；Guo等人，2025；Team等人，2025；Shao等人，2024；Lightman等人，2023）。其主要成本在于*rollout生成*：每次策略更新需要消耗大量长思维链样本（Chen等人，2025a；Sui等人，2025），而决定如何分配有限的rollout预算是一个核心设计问题（Zheng等人，2025；Lin等人，2025；Aggarwal和Welleck，2025）。

请参见图注

图1：序列分配将rollout投入到结果具有对比性的地方。*左图：*固定k分配（均匀采样，或经过滤的动态采样）为每个提示生成一个完整的k个rollout组；*饱和*组（全正确或全错误，淡色显示）的奖励方差为零，不贡献GRPO梯度。*右图：*SARA一旦统计上确定了组的结果就立即放弃，并将释放的预算重新分配给新的提示，从而以约22%的更少成本组装出更多有效（混合）组。

一个反复出现的障碍是提示的贡献极不均匀。在使用基于组的估计器如GRPO（Shao等人，2024）及相关变体（Hu，2025；Liu等人，2025b；a）时，如果一个提示的采样回答*全部*正确或*全部*错误，则会产生一个零方差的奖励组，从而导致归一化优势消失（Yu等人，2025；Bae等人，2025）。这种*饱和*组并不罕见：在均匀采样下，它们通常占一个批次的大多数（图2a），因此大部分rollout预算被用于产生恰好为零的梯度。只有*有效*组（结果混合的组）才能真正驱动学习。

两类方法试图解决这种浪费。评估后过滤方法，如DAPO中的动态采样（DS）（Yu等人，2025）和在线难度过滤（Bae等人，2025），对更大的候选池进行过采样，为所有候选者生成完整组，然后丢弃饱和组；这保证了批次的清洁，但使rollout成本成倍增加，并且常常主导训练过程（Zheng等人，2025；Lin等人，2025）。离线筛选则通过静态难度或多样性预先选择有信息量的提示（Li等人，2025；Ye等人，2025；Wang等人，2025），但无法跟踪不断变化的在线策略。预测后选择方法在采样*之前*估计每个提示的难度（Chen等人，2025b；Mao等人，2026；Qu等人，2026），并优先选择有希望的提示；这不会增加额外的rollout，但将批次押注于预测，因此当策略快速变化或历史数据稀疏时，预测会出错，批次再次被污染（Zhang等人，2025；Zheng等人，2025）。这两类方法处于*预测与验证*权衡的两端：要么在为提示付费之前预测其标签，要么通过全额付费来验证它。两者都在提示级别做出决策，在组自身的rollout能够提供信息之前（选择性生成和树结构分配器也是如此（Zheng等人，2025；Zou等人，2026）），因此都没有利用组内部已有的廉价证据。

这些证据是本文工作的起点。在一个组内，有效性判断通常远在组完成之前就已经确定：一旦一个提示产生了一个正确*和*一个错误的回答，它就永远有效，因为一个混合组不可能再变成非混合的；而一系列相同的结果会迅速将成功率的后验概率集中在0或1附近。经验上（图3a），大多数组的最终标签在仅仅几个k个rollout之后就确定了，因此在已经决定的提示上花费完整的k个rollout浪费了计算资源。达成这个判断不需要额外的模型调用；它只是读取优化器本就会生成的rollout。这种早停直觉是经典序列分析（Wald, 1945; Robbins, 1952）的基础，我们将其适应于逐步骤的RLVR预算分配。

因此，我们将单个RLVR步骤重新定义为一个在提示流上的预算受限*序列分配*问题，并将其实例化为SARA（序列自适应展开分配）。SARA以批处理轮次的方式探测提示；每轮之后，它更新每个活跃提示成功率的Beta后验分布，评估一个闭式的后验预测概率，判断该组在完整大小时是否有效，并应用一个双阈值、序列概率比风格的规则：一旦组是混合的，则*确认*；一旦几乎可以肯定它是饱和的，则*放弃*；否则*继续*。在短时间探测后放弃可能饱和的提示，会释放出rollout，这些rollout被重新分配给新的提示，因此固定的预算可以组装出更多有效组（图1）。SARA与提示选择是正交的，可以与其组合，不增加预测rollout，并且只引入少数几轮同步。

##### 贡献。（1）我们识别出组有效性的*早期可判定性*，并将逐步骤的rollout收集重新定义为序列分配/最优停止问题，这是一个与提示级别选择正交的预算维度。（2）我们推导出一个闭式的Beta-二项式有效性预测器和一个双阈值停止规则，从而得到SARA——一个无需预测rollout的分配器，可以嵌入任何GRPO风格的流水线。（3）我们证明了放弃的可靠性、预期的rollout节省、相较于均匀分配的固定预算收益优势，以及一个将有效组收益与期望平方GRPO梯度联系起来的下界。（4）在单个GPU上使用1.5B/3B模型时，SARA在匹配DPS的同时，比DS少使用22%的rollout，而SARA++DPS在减少67%的rollout的情况下略优于DS。

## 2 预备知识与问题设定

##### RLVR与GRPO。设q∼D是从数据集中抽取的一个提示，o∼πθ(·|q)是策略πθ生成的一个回答。RLVR最大化期望的可验证奖励：max_θ E_(q∼D, o∼πθ(·|q)) [r(q, o)]，其中r(q, o)∈{0,1}检查正确性（Guo等人，2025；Lightman等人，2023）。相对于PPO（Schulman等人，2017），组相对策略优化（GRPO）（Shao等人，2024）通过为每个提示q采样一组k个回答{o_i}_(i=1)^k并*在组内*归一化奖励来避免使用值网络：

Â_i = (r(q, o_i) - mean({r(q, o_j)}_(j=1)^k)) / std({r(q, o_j)}_(j=1)^k),

J(θ) = E[ (1/k) Σ_i min(ρ_i Â_i, clip(ρ_i, 1±ε) Â_i) ], (1)

其中重要性比率ρ_i = π_θ(o_i|q) / π_(θ_old)(o_i|q)。后续变体保留了这种组内归一化，同时调整了稳定性、长度偏差或无评论家估计器（Yu等人，2025；Hu，2025；Liu等人，2025b；a）。

##### 有效组与饱和组。对于提示q，设γ_q = E[r(q, o)] ∈ [0,1]为其（潜在的、依赖于策略和步骤的）成功率。一个包含k个rollout的组的成功计数为S_k ∼ Bin(k, γ_q)。

###### 定义1（有效组）。如果一个组的成功计数是混合的，即1 ≤ S_k ≤ k-1，则该组是*有效*的；否则是*饱和*的（S_k ∈ {0, k}）。饱和组的奖励方差为零，因此公式(1)中的每个Â_i都为0，该组贡献*无*梯度。一个组有效的概率是Φ(γ_q) = 1 - γ_q^k - (1-γ_q)^k，对于许多简单（γ_q→1）和困难（γ_q→0）的提示，该概率接近0，并在中等难度时达到峰值。因此，在均匀采样下，每批次中有很大一部分是饱和且浪费的（图2a；参见Yu等人，2025；Bae等人，2025；Zheng等人，2025）。

请参见图注

图2：饱和组占主导地位，而SARA保持批次的有效性。*(a)*均匀采样下每组成功计数的分布（k=8）：大多数组位于s=0或s=k（梯度为零）。*(b)*训练批次中有效组的比例随时间变化：SARA（以及动态采样oracle）提供几乎完全有效的批次；预测选择恢复了大部分，但随着策略变化而退化；均匀采样导致大部分批次被浪费。

##### 逐步骤预算与两种现有补救措施。一个标准GRPO步骤抽取B个提示，每个生成k个rollout，总共花费N = B·k个rollout，但平均只获得Φ·B个有效组。*动态采样*（DS/DAPO）（Yu等人，2025）及相关的在线过滤器（Bae等人，2025；Zhang等人，2025）对候选池B̂进行过采样（|B̂| > B），为所有候选者生成完整组，并保留有效组B_t = {q ∈ B̂ : std({r(q, o_i)}) > 0}；这得到一组干净的B个有效组，但预期成本约为≈ Bk/Φ个rollout，是N的几倍。*预测选择*（Chen等人，2025b；Mao等人，2026；Qu等人，2026）从历史中估计γ_q，并采样预测难度居中的提示，不花费额外rollout，但预测出错时批次会被污染。长度控制方法则是在*每个*rollout内部压缩token（Aggarwal和Welleck，2025；Hou等人，2025；Fatemi等人，2025）；它们与决定*收集多少个*rollout是互补的。我们的目标是获得一组干净的B个有效组，同时花费比DS少得多的rollout，并且对限制预测选择的预测误差具有鲁棒性。

##### 目标。在每一步，为GRPO更新组装B个有效组，最小化所花费的rollout（和token），*仅使用*rollout本身的结果（无需辅助评估过程）。

## 3 序列自适应展开分配

### 3.1 将Rollout收集视为序列分配

在一个RLVR步骤内，我们接收到一个提示流，并且必须在rollout预算限制下组装出B个有效组。一个提示的k个rollout不必一次性生成：我们可以先生成几个，检查其结果，然后决定是继续在该提示上投入更多还是转向其他提示。这是一个有限时域的序列决策问题。对于已观察到n个rollout且其中s个成功的提示q，我们在{确认，放弃，继续}中做出选择；放弃会为其他提示释放预算。目标是最大化每单位rollout获得的有效组数量（等价地，最小化获得B个有效组所花费的rollout），仅利用观察到的结果(n, s)。我们证明这存在一个近似最优的指标策略。