背包 RL：训练更智能语言模型的一场计算“免费午餐”

大型语言模型 (LLM) 已经展示出通过强化学习 (RL) 进行自我提升的非凡能力。通过生成解决方案、接收反馈并调整策略，它们能够学会解决如高等数学推理等复杂问题。这个过程依赖于一个关键步骤:** 探索**——尝试多种不同的方法，或称为“rollouts”，以发现有效策略。

但问题在于，探索的计算成本极高。为成千上万个不同问题生成成千上万种可能的解决方案，会消耗海量的 GPU 时间。为了控制成本，现有方法通常为每个问题分配一个固定的、较小的探索预算——通常是每个任务 8 次尝试机会。

这种“一刀切”的方法存在一个严重缺陷:

• 对于简单问题，8 次尝试可能过多，造成资源浪费。
• 对于难题，8 次尝试可能远远不够，导致反复失败。

在这两种情况下，模型最终可能在某个特定任务上总是成功或总是失败。这会产生“零梯度”——即没有学习信号——从而浪费宝贵的计算资源。

最近的一篇论文《背包 RL: 通过优化预算分配解锁大语言模型的探索能力》 (Knapsack RL: Unlocking Exploration of LLMs via Optimizing Budget Allocation) 直面了这个问题。研究人员提出: 将探索预算分配视为一个经典的优化问题。将每个任务看作一个具有成本 (计算量) 和价值 (学习潜力) 的物品，然后利用著名的背包问题来智能分配固定预算，将更多资源投入到最需要的任务上。

图 1 我们的框架示意图，用于在任务间分配探索预算。任务被建模为具有学习价值和计算成本的物品，并通过背包问题进行优化分配。

---

背景: 策略优化中的零梯度问题

为了理解这一思想的重要性，让我们看看用于 LLM 的强化学习微调。其目标是训练模型参数 \(\theta\)，使其针对提示词 \(x\) 生成的响应 \(y\) 能够最大化奖励:

\[ \max_{\theta} \ \mathbb{E}_{y \sim \pi_{\theta}(\cdot|x)}\,[\,r(x,y)\,] \]

在数学推理任务中，奖励通常是二元的:

\[ r(x,y) = \mathbb{I}(\text{答案是正确的}) \]

一种流行的强化学习算法是群体相对策略优化 (Group Relative Policy Optimization, GRPO) 。对于一批 \(M\) 个提示词，模型为每个提示词生成 \(N\) 次 rollout。梯度更新公式如下:

\[ g(\theta) = \sum_{i=1}^{M} \sum_{j=1}^{N} \nabla_{\theta} \log \pi_{\theta}(y_{ij}|x_i) \cdot (\,r(x_i,y_{ij}) - b_i\,) \cdot c_i \]

其中:

• \(b_i\) — 提示词 \(i\) 的平均奖励 (基线) 。
• \(r - b_i\) — 该 rollout 的“优势”。

如果一个响应的奖励高于平均值，模型会增加其生成概率；如果低于平均值，则降低其生成概率。

---

关键问题: 如果一个提示词的所有 \(N\) 次 rollout 奖励都相同 (全部成功或全部失败) :

1. 全部成功: 奖励 = 1，基线 \(b_i\) = 1，优势 = 0 → 梯度 = 0。
2. 全部失败: 奖励 = 0，基线 \(b_i\) = 0，优势 = 0 → 梯度 = 0。

在这两种情况下，模型消耗了计算资源，却没有学到任何东西。

---

衡量统一预算的低效性

作者引入了**有效梯度率 **(effective-gradient-ratio) 的概念: 实际产生非零梯度的响应所占比例:

\[ \text{effective-gradient-ratio} = \frac{1}{M N} \sum_{i=1}^{M} \sum_{j=1}^N \mathbb{I}(g_{i,j} \neq 0) \]

在训练一个 70 亿参数的数学模型 (统一预算 \(N=8\)) 的过程中，追踪该指标揭示了令人担忧的趋势。

图 2 训练期间的有效梯度率和零梯度分解。训练早期: 全失败率高；训练后期: 全成功率高。

观察结果:

• 训练早期: 模型在大多数任务上失败；全失败的提示词占主导。
• 训练中期: 成功与失败混合，效率最高。
• 训练后期: 简单任务导致全成功提示词占主导；难题仍然是全失败；效率急剧下降。

---

你真正需要多少次 Rollout？

成功率为 \(p_i\) 的提示词产生非零梯度的概率为:

\[ \text{Prob} = 1 - p_i^{N} - (1 - p_i)^{N} \]

对于:

• \(p = 0.5\): 平均需要 3 次 rollout。
• \(p = 0.01\): 平均需要 100 次 rollout；要达到 90% 的确定性则需要 229 次。

图 3 获得非零梯度所需的 rollout 次数，按成功率分组。

统一的 \(N=8\) 预算仅对 \(p \in [0.1, 0.9]\) 的情况有效。

这就是计算—探索困境:

• 统一提高 \(N\) → 成本巨大。
• 过滤掉简单或困难任务 → 失去在挑战性问题上的训练机会。

---

背包 RL 解决方案

与其采用统一预算，不如更智能地重新分配固定的总计算资源。

RL 探索设置	背包问题类比
带有探索预算的任务	背包中的物品
Rollout 次数	物品重量
从预算获得的学习收益	物品价值
可用总计算量	背包容量
可用 GPU	背包的实体容器

表 1 RL 探索与背包问题之间的对应关系。

---

定义任务的“价值”

为任务 \(i\) 分配 \(N_i\) 次 rollout 的价值为:

\[ \text{Value}(N_i, p_i) = \text{ProbNonZeroGradient}(N_i, p_i) \times \text{InfoGain}(p_i) \]

• \(\text{ProbNonZeroGradient}\): \(1 - p_i^{N_i} - (1-p_i)^{N_i}\) — 出现成功与失败混合的可能性。
• \(\text{InfoGain}(p_i)\): 估计的学习潜力，近似为 \(p_i(1-p_i)^2\)。

由此可见:

• 非常简单 (\(p_i \to 1\)) 或非常困难 (\(p_i \to 0\)) 的任务价值很低。
• 在 \(p_i = 1/3\) 附近价值达到峰值——即“学习甜蜜点”。

图 4 成功率、预算与学习价值的关系。

---

实现亮点

• 估计成功率: 使用上一步观察到的成功率作为估计值。
• 回退策略: 将简单任务释放的预算重新分配给极难 (\(p=0\)) 任务，以保证它们继续参与训练。
• Rollout 均衡: 将分配的 rollout 均匀分发至各工作节点，避免 GPU 空闲。

---

实验: 概念验证

设置: 在多个 LLM 上，针对数学密集型基准测试 (AIME、AMC、MATH、MINERVA、OLYMPIAD) 和 GPQA，比较 Knapsack-GRPO 与基线 GRPO 的性能。

模型	AIME	AMC	MATH	MINERVA	OLYMPIAD	GPQA	平均
DPSK-R1-Distill-1.5B	25.3	62.1	81.4	25.8	41.7	39.1	42.9
+ GRPO	27.6	71.1	84.0	27.6	46.4	36.7	45.9
+ Knapsack-GRPO	34.0	75.1	86.7	28.5	49.7	40.3	49.7
Qwen3-4B-Base	6.6	29.9	48.0	19.4	23.1	26.4	22.9
+ GRPO	20.7	56.9	80.6	31.9	44.9	46.6	43.2
+ Knapsack-GRPO	20.8	66.0	81.0	35.7	46.2	45.5	45.1
Qwen2.5-Math-7B	12.3	41.0	61.2	11.8	26.1	22.0	26.7
+ GRPO	23.9	70.6	81.7	33.6	41.9	40.8	45.2
+ Knapsack-GRPO	24.3	77.4	83.9	34.5	44.1	43.8	47.5

表 2 不同模型和基准下的性能对比。Knapsack-GRPO 持续领先。

---

理解性能提升的原因

动态分配: 虽然平均 \(N=8\)，但困难任务有时能获得高达 93 次 rollout。

图 5 训练期间的预算分布——挑战性任务呈现长尾特征。

梯度效率提升: 有效梯度率提高了 20–40%。

图 6 Knapsack-GRPO 在训练过程中保持了高效率。

更好的学习动态: 更多任务从困难状态转变为极易状态。

图 7 提示词转换矩阵——更大比例的任务达到了“极易”状态。

图 8 任务难度最终分布——Knapsack-GRPO 产生了更多已掌握的任务。

---

2 倍效率的“免费午餐”

图 9 性能与总预算对比。Knapsack-GRPO 用一半的计算量就达到了 GRPO 的性能。

---

结论与未来方向

背包 RL 框架传达了一个明确的信息: 优化探索资源分配以匹配任务难度，可以在不增加额外计算成本的情况下，同时提升性能和效率。

未来机遇:

• 更丰富的价值函数: 更精确地建模学习潜力。
• 多维成本: 将文本长度或对话深度等因素纳入考量。
• 与先进探索方法集成: 结合树搜索 (如 AlphaGo) 等技术。

通过将计算视作需要优化而非仅仅消耗的资源，背包 RL 为训练更智能、更强大的语言模型提供了一条可持续的发展路径。