Best-of-$\infty$ -- Asymptotic Performance of Test-Time LLM Ensembling

本文研究了基于多数投票的无限次测试时 LLM 集成（Best-of-$\infty$）的渐近性能，并提出了一种基于答案一致性的自适应生成方案及多模型加权集成方法，通过混合整数线性规划优化权重，在有限计算预算下显著提升了模型表现。

要点

这篇论文就像是在探讨一个非常有趣的问题：当我们面对一个超级聪明但偶尔会犯迷糊的“大语言模型”（LLM）时，我们该如何用最少的力气，让它给出最正确的答案？

想象一下，你正在参加一场高难度的数学竞赛，你请了一位天才助手（LLM）来帮你解题。这位助手很厉害，但他有时候会走神，或者给出几个不同的答案。

1. 核心概念：从“问一次”到“问无数次”

• 传统的做法（Best-of-N）：
  你让助手把同一道题做 5 遍（N=5），然后看哪个答案出现得最多，就选哪个。这就像你问 5 个朋友同一个问题，谁说得最多你就信谁。

  • 问题： 如果你问 100 次，准确率会更高；问 1000 次，准确率几乎完美。但是，问 1000 次太费时间、太费钱了（计算成本太高）。

• 论文的终极目标（Best-of-∞）：
  作者想达到一种“理想状态”：如果让助手无限次地做题，直到我们100% 确定哪个是正确答案，那个答案就是“最佳答案”。但这在现实中是不可能的，因为我们没有无限的时间。

2. 创新方案一：聪明的“自适应”策略（见好就收）

论文提出了一种**“自适应采样”的方法，就像是一个精明的侦探**。

• 以前的做法（固定 N）： 不管题目多简单，都死板地让助手做 100 遍。
  • 比喻： 就像你问“今天天气好吗？”，不管答案多明显，你都非要问 100 个人才肯信。这太浪费了。
• 新的做法（自适应）：
  • 如果助手前 3 次都回答“是晴天”，而且大家意见高度一致，侦探就会想：“这题太简单了，没必要再问了，直接选‘晴天’吧！”（停止生成）。
  • 如果助手前 10 次回答五花八门（有的说晴，有的说雨，有的说雪），侦探就会想：“这题很难，大家还在纠结，我得继续问更多人，直到大家意见统一为止。”（继续生成）。
• 效果： 简单题省时间，难题多花时间。最终在同样的预算下，准确率比死板地做固定次数要高得多。

3. 创新方案二：组建“梦之队”（LLM 集成）

作者还发现，与其只依赖一个超级助手，不如组建一个**“专家顾问团”**。

• 场景： 你有 5 个不同的 AI 助手。
  • 助手 A 擅长代数，但几何很烂。
  • 助手 B 几何很好，但代数一般。
  • 助手 C 虽然整体水平中等，但在某些特定领域有奇招。
• 以前的做法： 你只选那个“平均分最高”的助手，或者让 5 个人各做一遍，然后少数服从多数（大家权重一样）。
• 论文的做法（加权投票）：
  • 作者设计了一个**“混合整数线性规划”（听起来很复杂，其实就是一个超级计算器**）。
  • 这个计算器会分析：在解决这类问题时，助手 A 的贡献应该占 10%，助手 B 占 40%，助手 C 占 50%……
  • 比喻： 就像组建一支足球队。你不需要让所有球员都踢前锋，而是根据每个人的特长（有的擅长防守，有的擅长射门），给他们分配不同的出场权重。
• 神奇之处： 有时候，一个“较弱”的助手，因为能弥补“强助手”的短板，加入团队后反而能让整体表现超过任何单个最强的助手。这就是**“互补效应”**。

4. 总结：这篇论文解决了什么？

1. 省钱省力： 通过“见好就收”的自适应策略，用更少的计算量（Token）达到了更高的准确率。
2. 强强联合： 证明了通过科学地给不同 AI 分配“投票权重”，可以让一群 AI 组成的团队，发挥出比任何单个 AI 都强的能力。
3. 理论突破： 他们把“如何分配权重”这个问题，变成了一个数学上可以完美求解的公式（MILP），找到了理论上的最优解。

一句话总结：
这就好比在考试时，你不再死板地让一个学生做 100 遍题，而是根据题目难度灵活决定问几次；同时，你不再只依赖一个“学霸”，而是组建了一个由不同特长学生组成的“智囊团”，并科学地分配他们的投票权，最终用最小的代价，拿到了最完美的分数。

技术摘要

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

随着大型语言模型（LLM）在复杂推理任务（如数学解题、科学问答）中的能力不断提升，测试时计算（Test-time Compute） 的扩展策略成为提升模型性能的关键。

• Best-of-N (BoN) 策略：生成 $N$ 个答案，根据某种标准（如奖励模型、多数投票）选择最佳答案。
• 核心痛点：
  1. 理论极限与资源限制：理论上，当 $N \to \infty$ 时，基于多数投票（Majority Voting）的准确率会收敛到一个理想的极限值（Best-of-∞）。但在实际应用中，无限生成样本是不可行的。
  2. 固定预算的低效性：传统的固定 $N$ 策略（如固定生成 10 次或 100 次）无法根据问题的难易程度动态调整资源。简单问题可能只需少量样本即可确定答案，而复杂问题则需要更多。
  3. 多模型集成优化困难：在使用多个 LLM 组成集成（Ensemble）时，如何分配不同模型的权重以最大化 Best-of-∞ 的准确率是一个复杂的优化问题。现有的梯度下降方法往往因目标函数的非凹性（Non-concavity）而失效。

本文旨在解决：如何在有限的推理预算下，通过自适应采样逼近 Best-of-∞ 的性能，并找到多模型集成的最优权重配置。

---

2. 方法论 (Methodology)

论文提出了两个核心模块：基于贝叶斯推断的自适应采样 和 基于混合整数线性规划（MILP）的集成权重优化。

2.1 自适应采样方案 (Adaptive Sampling)

为了在有限样本下逼近 Best-of-∞，作者设计了一个动态停止机制（Algorithm 1）：

• 非参数贝叶斯建模：由于 LLM 生成的答案空间未知（可能是无限的），作者使用 狄利克雷过程 (Dirichlet Process, DP) 先验 $DP(H, \alpha)$ 对答案分布进行建模。
• 贝叶斯因子 (Bayes Factor, BF) 停止准则：
  • 定义假设：$H_0$（当前最高频答案不是真实多数）vs $H_1$（当前最高频答案是真实多数）。
  • 计算贝叶斯因子 $BF = P(D|H_1) / P(D|H_0)$，量化数据支持 $H_1$ 的证据强度。
  • 停止规则：当 $BF$ 超过预设阈值 $B$ 或达到最大样本数 $N_{max}$ 时停止采样。
• 优势：对于简单问题，模型能迅速达成共识，提前停止采样；对于困难问题，则继续采样直到置信度足够。这比固定 $N$ 策略显著节省了计算资源。

2.2 多模型集成与权重优化 (LLM Ensemble & Weight Optimization)

将框架扩展到多个 LLM 的集成：

• 加权多数投票：从 $K$ 个模型中按权重 $w_i$ 随机选择一个模型生成答案，最终取多数投票结果。
• 优化目标：寻找权重向量 $w$，使得 Best-of-∞ 的准确率最大化。
• 理论突破 (MILP 公式化)：
  • 作者证明了在 $N \to \infty$ 的极限下，正确答案的判定区域在权重单纯形（Simplex）上表现为 多面体 (Polytope) 结构。
  • 最大化正确回答的问题数量等价于寻找一个点 $w$，使其落入尽可能多的“正确回答多面体”中。
  • 该问题被形式化为一个 混合整数线性规划 (MILP) 问题。尽管一般 MILP 是 NP-hard，但在实际规模（$K \approx 10$ 个模型，$N \approx 1000$ 个问题）下，现代求解器（如 HiGHS）可以高效求解。
• 最大间隔解 (Max-Margin Solution)：为了在有限 $N$ 下获得更好的鲁棒性，作者在优化中引入了间隔 $\xi$，选择位于解空间最内部的权重，以应对有限样本的波动。

---

3. 主要贡献 (Key Contributions)

1. Best-of-∞ 的有限样本逼近：提出了一种基于狄利克雷过程和贝叶斯因子的自适应采样算法，能够在保证高置信度的前提下，显著减少达到 Best-of-∞ 性能所需的平均样本数（相比固定 $N$ 策略减少 2-5 倍计算量）。
2. 多模型集成的最优权重理论：首次将 LLM 集成中的最佳权重寻找问题转化为 MILP 问题。证明了在极限情况下，该优化问题具有多面体结构，从而避免了梯度下降法在非凹目标函数上的失效，提供了可证明的最优解。
3. 大规模实验验证：
   • 构建了超大规模数据集：涉及 11 个开源 LLM（参数规模 4B-32B）和 4 个高难度推理基准（AIME2024/2025, GPQA-DIAMOND, MATH500）。
   • 每个模型 - 问题对生成了至少 80 个答案（远超通常的 8 次），总生成 Token 数巨大。
   • 开源了生成的答案数据集和代码。

---

4. 实验结果 (Results)

• 自适应采样的效率：
  • 在 MATH500 等数据集上，自适应算法仅需平均约 3 个样本即可达到固定 $N=10$ 的准确率；平均约 10 个样本即可达到固定 $N=100$ 的准确率。
  • 在 Token 消耗上，自适应方法比固定采样方法节省了显著的推理成本。
• 集成优于单模型：
  • 通过 MILP 优化的加权集成，其 Best-of-∞ 准确率始终高于任何单个模型。
  • 案例：在 AIME2025 上，GPT-OSS-20B 的极限准确率为 90.0%，Nemotron-Nano-9B 为 73.0%，但两者的加权集成达到了 93.3%。这证明了弱模型在集成中可以通过互补性贡献价值。
• 权重泛化性：
  • 仅需少量训练问题（如 5 个）即可学习到的权重，就能在测试集上接近最佳单模型性能。
  • 跨数据集迁移（如在 AIME2024 训练权重用于 AIME2025）也表现出良好的效果。
• 与其他选择方法的对比：
  • 在 Best-of-5 (Bo5) 设置下，多数投票（Majority Voting）的表现优于随机选择、自置信度（Self-certainty）、奖励模型（Reward Models）以及 LLM-as-a-judge 方法。

---

5. 意义与影响 (Significance)

1. 理论深度：将 LLM 推理的极限性能分析与运筹学（MILP）结合，为多模型集成提供了严谨的数学框架，解决了长期存在的“如何最优混合模型”的难题。
2. 实用价值：提出的自适应采样方案为实际部署提供了高效的推理策略，能够在不增加（甚至减少）推理成本的情况下，显著提升复杂任务（如数学竞赛、科学问答）的准确率。
3. 资源释放：论文释放了大规模生成的推理数据（包含数万个问题的数百个候选答案），为后续研究测试时扩展（Test-time Scaling）和模型集成提供了宝贵的基准数据。
4. 范式转变：证明了在推理阶段，通过智能地组合多个模型和动态分配计算资源，可以突破单一模型的性能瓶颈，且这种提升不依赖于模型参数的进一步增加。

总结：这篇论文通过理论推导和大规模实验，确立了“自适应采样 + 最优集成权重”作为提升 LLM 推理性能的有效范式，展示了在有限计算预算下逼近理论极限的可行性。