📊 statistics

Strategic Scaling of Test-Time Compute: A Bandit Learning Approach

该论文提出了一种基于多臂老虎机学习的自适应测试时计算分配方法，通过动态估计查询难度并优先将计算资源分配给高难度且可解的实例，在数学和代码基准测试中显著提升了大语言模型的性能与计算效率。

原作者： Bowen Zuo, Yinglun Zhu

发布于 2026-04-24

📖 1 分钟阅读☕ 轻松阅读

原作者： Bowen Zuo, Yinglun Zhu

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲了一个关于如何更聪明地“花钱”让 AI 变强的故事。

想象一下，你是一位餐厅经理，手里有一笔固定的预算（比如 1000 元），你要给 100 位顾客点菜。你的目标是让尽可能多的顾客吃到满意的饭菜。

1. 以前的做法：平均主义（Uniform Allocation）

以前的 AI 做法很简单：不管顾客点的是“白开水”还是“满汉全席”，每桌都发 10 块钱的餐费。

结果：点白开水的顾客（简单问题）觉得钱花多了，浪费；点满汉全席的顾客（难题）觉得钱不够，厨师做不出好菜，最后顾客不满意。
问题：这种“一刀切”的方法效率很低，钱没花在刀刃上。

2. 这篇论文的新招：像“老虎机”一样聪明地分配（Bandit Learning）

作者提出了一种新方法，把每个问题看作一台老虎机（Slot Machine）。

核心思想：我们不知道哪台机器（哪个问题）能赢大奖（解出答案），也不知道哪台机器是“死机”（无解）。我们需要通过边玩边学，动态调整投入的钱。
具体操作：
1. 先尝一口：给每个问题都试一点点（比如每桌先给 1 块钱）。
2. 看反馈：
  - 如果这 1 块钱就让顾客吃到了满意的菜（问题很简单），立刻停止投入，把剩下的钱省下来。
  - 如果这 1 块钱还没解决问题，但看起来有希望（问题很难但能解），继续加钱，多给厨师一点时间。
  - 如果试了很多次，发现这桌客人根本点不到菜（问题无解），果断放弃，别浪费钱了。

3. 这个新方法有多厉害？（三大绝招）

绝招一：见好就收（针对简单问题）

对于简单的数学题（比如"1+1 等于几”），AI 试一次就知道答案了。新方法会立刻停止生成多余的回答，把省下的算力留给那些难啃的骨头。

绝招二：好钢用在刀刃上（针对难题）

对于复杂的奥数题，新方法会持续投入，直到 AI 终于解出来为止。它不会像以前那样，给简单题和难题一样的资源，导致难题“吃不饱”。

绝招三：识别“死局”（针对无解问题）

这是最精彩的部分。有些问题可能根本无解（比如让 AI 算出“圆的周长是 3"）。

以前的做法：不管有没有解，都死磕到底，浪费大量算力。
新方法（熵值策略）：AI 发现，如果一个问题怎么算都算不出像样的答案（回答乱七八糟、格式错误），它的“混乱度”（熵）就很低。这时候，算法会聪明地放弃，不再在这个无解的问题上浪费一分钱，转而把资源投给那些“有希望解出来”的难题。

4. 实际效果如何？

作者在数学（MATH-500, AIME25）和编程（LiveCodeBench）的测试中验证了这种方法：

同样的预算，新方法让 AI 做对题目的数量提升了 10% 到 15%。
这就好比，以前花 1000 元只能让 80 个顾客满意，现在同样的 1000 元，能让 90 多个顾客满意！
甚至在某些情况下，新方法用一半的钱就能达到旧方法用双倍钱的效果。

总结

这篇论文就像给 AI 配了一位精明的管家。
以前，AI 是“撒胡椒面”，不管难易，平均用力，浪费严重。
现在，AI 学会了**“看人下菜碟”**：

简单的，少花钱；
难的但能解的，多花钱；
根本解不开的，直接放弃。

这种**“动态调整、好钢用在刀刃上”**的策略，让 AI 在同样的算力成本下，变得更强、更聪明。

1. 研究背景与问题定义 (Problem)

背景：
近年来，大语言模型（LLM）的性能提升已从单纯依赖“训练时计算量”（Training-time Compute）转向“测试时计算量”（Test-time Compute, TTC）。现有的测试时扩展方法（如 Best-of-N 采样、一致性检查等）通过生成多个回答并选择最佳者来提升质量。然而，这些方法通常采用均匀分配（Uniform Allocation）策略，即对所有查询（Query）分配相同的计算预算（如生成次数）。

核心问题：

效率低下： 均匀分配忽略了查询难度的差异。简单问题（如基础算术）和复杂问题（如多步推理）获得相同的计算资源，导致简单问题资源浪费，而复杂问题资源不足。
现有方法的局限：
- 部分自适应方法仅针对单个查询内部进行计算分配，未考虑跨查询的资源重新分配。
- 部分多查询分配方法（如两阶段策略）需要先训练辅助模型或进行预计算，引入了额外的计算开销和训练成本。
目标： 如何在固定的总计算预算下，自适应地在不同难度的查询间分配计算资源，以最大化正确回答的查询比例？

2. 方法论 (Methodology)

作者提出将测试时计算分配问题建模为一个全新的纯探索型多臂老虎机（Pure Exploration Bandit Learning）问题。

2.1 问题形式化

动作（Action）： 每个待解决的查询 $x$ 被视为一个老虎机的“臂”。
反馈（Feedback）： 每次对查询 $x$ 分配计算（生成一个回答），都会获得一个奖励分数 $r(x, y)$ （由奖励模型或真值验证器提供）。
目标： 在总预算 $B$ $B$ 的限制下，最大化被正确回答的查询数量。
- 定义正确性：若生成的回答 $y$ 的得分 $r(x, y) \ge \gamma$ （阈值），则视为正确。
- 优化目标： $\max \frac{1}{n} \sum I(\text{query } x \text{ is solved})$ ，受限于 $\sum c(x_i) \le B$ 。

2.2 核心算法框架 (Algorithm 1: Elimination)

作者设计了一个自适应的消除算法（Elimination Algorithm），主要包含两个核心组件：

探索规则（Exploration Rule）：
- 在每一轮中，算法对当前**活跃集（Active Set）**中的所有查询生成 $K$ 个新回答。
- 活跃集包含那些尚未被“自信地”判定为已解决的查询。
消除规则（Elimination Rule）：
- 对于每个查询，如果新生成的回答中最高分超过了预设的消除阈值 $\gamma$ ，则该查询被视为“已解决”，并从活跃集中移除，不再分配后续计算资源。
- 如果未达到阈值，则保留在活跃集中，继续分配计算资源。

2.3 扩展策略 (Extensions)

为了应对不同场景，作者提出了多种探索策略的变体：

UCB (Upper Confidence Bound)： 优先选择经验奖励高且不确定性大的查询。
Gap-based： 优先选择得分接近消除阈值的查询。
Entropy-based (熵策略)： 创新点。优先选择生成回答多样性高（熵值高）的查询。
- 原理： 研究发现，可解的难题往往能生成多样化的有效回答（高熵），而不可解的难题往往生成无效或格式错误的回答（低熵）。该策略能有效识别并聚焦于“可解”的难题，避免在“不可解”问题上浪费算力。
流式与 Token 控制： 算法支持流式查询（查询逐个到达）和基于 Token 数量的细粒度预算控制。

2.4 理论分析

定理 1： 证明了该自适应算法所需的总预算 $B_{ours}$ 为 $\tilde{\Theta}(\sum \frac{1}{\Delta_x})$ ，其中 $\Delta_x$ 是查询 $x$ 的正确率。
对比： 均匀分配策略所需的预算为 $\Omega(\max \frac{|S|}{\Delta_x})$ 。
结论： 在查询难度差异较大（异质性强）的情况下，自适应算法在理论上显著优于均匀分配，计算效率可提升 $O(n)$ 倍（ $n$ 为查询数量）。

3. 主要贡献 (Key Contributions)

新视角与形式化： 首次将 LLM 测试时计算分配问题形式化为多臂老虎机学习问题，连接了测试时扩展与强化学习/在线学习社区。
通用算法框架： 提出了一种灵活的自适应算法框架，支持多种探索策略（包括新颖的熵策略），无需额外训练辅助模型，即可在流式或 Token 受限场景下工作。
理论保证： 提供了严格的理论证明，表明战略性的自适应分配在计算效率上严格优于均匀分配和两阶段（Explore-then-Commit）策略。
实证突破： 在数学和代码基准测试中，证明了该方法在相同预算下能显著提升性能。

4. 实验结果 (Results)

作者在多个基准数据集（MATH-500, AIME25, LiveCodeBench）和多种模型（Llama-3, Qwen3, DeepSeek-R1, Gemini 等）上进行了广泛实验。

性能提升：
- MATH-500: 在平均计算预算下，性能提升最高达 11.10%（相对提升 15.04%）。
- AIME25: 性能提升最高达 10.82%（相对提升 14.44%）。
- LiveCodeBench: 性能提升最高达 11.23%（相对提升 15.29%）。
计算效率（Efficiency Gain）：
- 在达到相同准确率的情况下，自适应方法所需的计算量仅为均匀分配方法的 1/2 到 1/4（即效率提升 2x 到 4x）。
- 例如，在 MATH-500 上，使用 16 单位预算的自适应方法，达到了均匀分配方法需要约 32 单位预算才能达到的效果。
难例分析 (MATH-500-Hard)：
- 在包含“不可解”问题的困难子集中，Entropy 策略表现最佳。它能识别出那些虽然难但“可解”的问题（高熵），并避免在那些无论生成多少次都无法解决的“不可解”问题（低熵/无效输出）上浪费资源。
消融实验：
- 算法对超参数（如每轮生成数 $K$ 、消除阈值 $\gamma$ ）具有鲁棒性。
- 在 Token 预算严格匹配（Token-matched）的情况下，算法依然优于基线。

5. 意义与总结 (Significance)

资源优化： 该研究为解决 LLM 推理成本高昂的问题提供了有效方案。通过“好钢用在刀刃上”，将有限的计算资源集中在最需要且最有希望解决的查询上，显著降低了推理成本。
无需训练： 与许多需要训练额外奖励模型或调整器的方法不同，该方法完全基于推理时的自适应策略，即插即用，降低了部署门槛。
理论深度： 将测试时扩展问题与经典的多臂老虎机理论结合，为理解 LLM 的推理行为提供了新的理论视角，证明了“战略分配”在数学上的优越性。
通用性： 框架不仅适用于数学推理，也适用于代码生成等需要验证的场景，且能处理流式输入，具有广泛的实际应用价值。

总结： 这篇论文提出了一种基于多臂老虎机学习的自适应计算分配框架，通过动态识别查询难度并优先分配资源给“可解”的难题，在无需额外训练的情况下，显著提升了 LLM 在复杂推理任务中的性能与计算效率。