test time scaling调研
分类:
1.1-3关于小模型推理计算下比大模型更具有优势
2.4关于搜索方法
3.5-6关于RM训练
1.Large Language Monkeys: Scaling Inference Compute with Repeated Sampling
Abstract
探索了通过增加生成样本的数量来扩展推理计算的另一种方式
在多个任务和模型中，覆盖率随着样本数量的增加而增加，覆盖率可以跨越四个数量级 (从1-10000次)
在可以自动验证答案的领域（如编程和形式证明），这些覆盖率的提高直接转化为性能的提升
探讨了在没有自动验证器的领域中，如何从许多生成的样本中识别正确的样本，这是未来研究的一个重要方向
Introduction
重复采样的有效性由两个关键属性决定:
1.覆盖范围: 随着样本数量的增加，我们可以使用生成的任何样本解决多少比例的问题
2.精度: 在我们必须从生成的样本集合中选择最终答案的设置中，我们可以识别正确的样本吗
观察结果:
1.覆盖范围随着样本数量几乎呈对数线性增长几个数量级 (state-of-the-art 最先进的)
2.在没有自动验证器的领域，我们展示了像多数投票和奖励模型评分这样的验证方法在大约100个样本之后达到瓶颈
Scaling Repeated Sampling
发现: 对于小模型，重复采样的提升显著
这里先粗略用FLOP来作为成本效益参考，当然重复采样可以利用高批量大小和专门的优化来提高相对于单次尝试推理工作负载的系统吞吐量
Harnessing Repeated Sampling Requires Precision
对于gsm8k和MATH
三种选择方法: 多数投票, 奖励模型+最佳N, 奖励模型+多数投票
但是100次后趋于稳定，和覆盖率差距变大
对于代码问题的验证出现的两个问题
1.SWE-bench Lite测试套件的错误测试
11.3%的问题存在不稳定的测试套件，这些套件在对同一候选解决方案运行时并不总是产生一致的结果，具体可见附录中的例子
2.CodeContest上的误报
问题有多种答案的输出，但是测试用例只有一个特定正确输出
Discussion and limitation
改进方向:
1.提升重复采样
不同采样温度，多轮交互反馈，从之前的尝试中学习
2.提升采样和推理的系统
3.验证器
总体感受: 这篇论文相对来说比较水，有价值的就是那个幂律分布，以及提出验证器的边际效应问题
2.Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameters
Abstract
目前两种主要的test-time computation:
1.基于打分器评估和指导模型的解答过程
2.让模型根据它收到的输入（提示）的难度来调整自己的回答策略
发现: 不同测试时计算方法的有效性取决于提示的难度，提出compute-optimal的策略
idea: 给定具有挑战性的query，能否使LLM在测试时最有效地利用额外的计算，以提高其响应的准确性
A Unified Perspective on Test-Time Computation: Proposer and Verifier
两个方式引起LLM分布的修改:
1.输入阶段，给输入prompt加一些多余的tokens
2.多次采样，对这些生成的候选答案进行修改或调整(这里的描述没有太看懂)
对于proposal distribution的修改: 微调模型使得模型自我批评，不引入额外的token
对于verifier的优化: best of N, 树搜索
How to Scale Test-Time Computation Optimally
期望简单的问题可以修改解决，困难的问题并行抽样解决
verifer可以使用各种搜索算法
optimal scaling strategy
3.1中的公式1就是在一个时间预算N下，找到最好的模型$\theta$ —> 是一个最优策略框架
Estimating Question Difficulty for Compute-Optimal Scaling
定义问题难度: 没有使用MATH的标注，而是使用pass@1率(采样2048次)区分5个难度级别，根据难度动态调整计算资源
评估: 不使用oracle answer，而是通过学习到的验证器对最终答案的平均分数进行分箱处理
需要对评估难度所花费的计算资源和应用计算最优策略之间进行权衡 —> 总的计算资源=判断难度+该难度下分配的计算资源N
Scaling Test-Time Compute via Verifiers
优化验证器以用来test-time-scale
训练PRM模型
详细过程: 使用一个800k数据集抽取10%
使用方法: 使用PRM在最后一步的预测作为完整答案分数，然后就是是best of N加权
通过搜索优化PRM
beam search的方法: 对解决方案的第一步采样N个初始预测，筛选出最高得分的N/M个步骤，从每个候选者中，对下一步采样M个提议，总共得到N种前缀…
lookahead search的方法: PRM用temp=0采样，预先搜索会向前模拟几步选取最高策略，筛选出最高得分的N/M个步骤，从每个候选者中，对下一步采样M个提议…
搜索的分析结果
beam width和lookahead step的设置可以参考
结果: 第9页的内容已经足够详细了
3.Smaller, Weaker, Yet Better: Training LLM Reasoners via Compute-Optimal Sampling
Abstract
提出利用较弱模型生成的合成数据来提升较强模型的推理能力
发现在固定采样预算下，使用较弱的SoTA LM生成的数据训练出的推理器比使用较强SoTA LM的数据训练出的推理器性能更好
Introduction
1.在固定计算预算下采样WC和SE模型
考察三个指标: 覆盖率，多样性，误报率
WC比SE在前两个要更强，但是误报率更高
2.对于WC和SE的数据应用三种微调的方式
知识蒸馏，自我改进，weak-to-strong的新范例，具体就是下面三种
学生模型微调: 探讨了是否可以用WC模型替代SE模型进行高质量的知识蒸馏
WC模型微调: 研究了WC模型使用自身生成的数据（自我改进）与使用SE模型生成的数据（知识蒸馏）的效果
SE模型微调: 测试了使用WC模型生成的数据是否能改进SE模型，提出了弱到强改进（W2S-I）的新范式
实验设置和结论的一些细节
在误报率的检测上，评估方式可以使用强大模型评估，这个和人工评估的效果是差不多的
对于微调模型的评估上，可以贪婪解码，也可以多次采样(开do sample) Takeaway 总结
未完待续~~~
4.AlphaZero-Like Tree-Search can Guide Large Language Model Decoding and Training
Abstract
研究目的: 提出一种新型的树搜索学习框架(TS-LLM)
研究背景: 当前方法依赖于预训练模型作为值函数，并且只适用于搜索深度较浅的问题
方法: TS-LLM采用类似AlphaZero的算法，并引入了学习到的值函数，使其能够适应各种规模的语言模型和不同深度的搜索任务
Introduction
之前工作的问题:
1.树搜索算法中的价值函数是通过提示LLM获得的，精心设置prompt，可扩展性差
2.最大深度不够，深度为7或10
TS-LLM的特点:
1.可扩展性好，参数范围
2.深度64
3.或许可以将搜索后的数据作为训练标签
Enhancing LLMs with Tree Search
两种动作空间设计，各有优缺点:
1.句子级别的
2.token级别的—>对于那些未明确定义中间步骤的任务
奖励模型设计: 有两个奖励模型，一个是价值模型，还有一个是ORM
训练RM模型是使用TD强化学习算法训练整个流程，而训练ORM使用最终奖励为目标，都是以MSEloss为损失函数
搜索方法: 共有5种
可以关注下$MCTS-\alpha$方法
论文中使用$MCTS-rollout$
聚合方式:
TS-LLM通过进行多次树搜索或一次搜索中的多次生成（例如，设置BFS的波束宽度大于1）来生成N个完整的答案，然后对这些答案进行聚合
树内搜索高效但多样性降低，文中提出了树间搜索，具体差别还在看
三种聚合方法:
多数投票: 选择被多次选择的答案
ORM-Max: 选择具有最大预测奖励的答案
ORM-Vote: 对所有答案的预测奖励进行累加，选择总和最大的答案
计算量问题:？
Experiments
奖励函数上将之前论文中用提示词生成的和论文中训练的奖励函数结合起来对比
为了公平比较，没有使用pass@k，而是使用了equal-token的方法
最后将搜索树生成的内容采样迭代$\pi_{\theta}$
结果:
1.MCTS相比之下是最好的，表明了价值反向传播的重要性
2.TS-LLM在聚合多个搜索结果时通常表现更好，但在小规模问题上，其改进效果不如CoT-SC方法
3.由于树搜索算法已经通过价值函数和ORM进行了优化，进一步聚合带来的额外好处有限
5.MATH-SHEPHERD: VERIFY AND REINFORCE LLMS STEP-BY-STEP WITHOUT HUMAN ANNOTATIONS
Abstract
提出了一个数学解题奖励模型MATH-SHEPHERD，为每一步分配一个奖励分数
自动构建数学推理任务的过程监督数据集，无需人工注释
Method
ORM可以自动标注，PRM注释成本高，都用二元交叉熵计算
自动标记的方法: 硬估计和软估计
硬估计是这个step能到达正确答案就设置为1，软估计是这个step搜索n次能到达正确答案m次，分数为m/n
6.RRM: ROBUST REWARD MODEL TRAINING MITIGATES REWARD HACKING
Abstract
指出现有奖励模型训练方法的一个关键问题: 无法区分上下文信号和无关的伪影
为了解决这个问题，作者提出了一个因果框架，并引入了一种数据增强技术来消除这些伪影，提高了奖励模型的稳健性
Introduction
RLHF的hacking issue: 最大化了奖励函数，但没有真正符合人类的预期偏好
例子: LLM倾向于生成更长的回复，以显得更详细或更具解释性，利用了人类评分者对较长内容的偏见
传统RM无法区分真正的上下文偏好信号和虚假的上下文无关组件
奖励模型: 在给定提示$x$的情况下，响应$y1$优于$y2$的概率$P(y_1 \succ y_2|x)$
方案一Bradley-Terry:
假设有一个reward model
方案二配对排序模型:
比Bradley-Terry模型更灵活，因为它有更大的函数类容量，能够更好地拟合数据(没太懂，后面阅读一下这里的论文)
使用语言模型的下一个token预测能力来格式化样本
输出 “A” 或 “B” 作为更受偏好的响应
reward hacking: 比如响应的长度、格式（如使用粗体或列表标记）或特定的模式（如特定的n-grams或表情符号）。这些都不是由提示内容驱动的偏好，而是与上下文无关的伪影
因果推断:
未完待续~~~
7.Improve Mathematical Reasoning in Language Models by Automated Process Supervision
提出了一种新颖的分治式蒙特卡罗树搜索算法，名为OmegaPRM，整个过程无需任何人工注释，用于有效收集高质量的过程监控数据
1.定位错误点的方式
原本的定位方式是Math-Shepherd中所提及的方法
这里使用二分搜索，中间步骤采样几次后续步骤若有推理成功的方案，往后找下一个二分点，若没有推理成功的方案，往前找二分点
2.构建一棵树
根节点只有query，其他节点包含query和先前推理步骤(state)并且有k个往下推理的rollout 术语: rollout展开
同时节点存储数据，$N(s)$是经过该状态次数，$MC(s)$预测值，$Q(s,r)$由一个公式计算出来作为选择路径的参考价值(包含惩罚长rollout的部分)
3.选择
将当前节点的状态值Q加上探索价值U，$U(s)$也是用PUCT的变体算法计算
4.二分搜索
5.更新节点参数
看不太懂，论文写得有点乱
8.Rewarding Progress: Scaling Automated Process Verifiers for LLM Reasoning
提出两个问题:
1.PRM模型测量什么
每一步过程奖励为采取该步骤之前和之后得出正确最终答案的可能性的变化—>使用强化学习中的优势
2.需要什么自动数据收集策略来训练PRM
prover policy是与基本策略互补，可以和基本策略产生的步数产生对比
这里基本策略的best of K就是一个好的方法
训练一个PAV(过程优势验证器)
9.Quiet-STaR: Language Models Can Teach Themselves to Think Before Speaking
它通过在每个标记后生成理由来解释未来文本，并使用 REINFORCE 算法来优化理由生成
可以在各种非结构化文本数据中学习推理
运行步骤:
1.对于一段输入并行生成理由，理由用两个新的special token包装
2.加一层MLP，产生一个权重，决定了在生成下一个词元的预测时，应该在多大程度上结合理由生成的预测和基础语言模型的预测
3.使用REINFORCE算法用于优化理由，应用”教师强制”的技术，通过在损失函数中包含不仅预测思考之后的词元，还包括后续词元的概率
并行生成的实现方法:
1.保存query中每一个token的隐藏层
2.设计对角线注意力
启发:
1.自我迭代
2.solid token有用
3.计算并行，mcts并行
10.ReFT: Reasoning with REinforced Fine-Tuning
ReFT: 用SFT预热模型，然后采用在线强化学习PPO算法，进一步微调模型
这里和RLHF有区别吗—>其实没有，只是第一次在数学上的运用罢了
11.Dualformer: Controllable Fast and Slow Thinking by Learning with Randomized Reasoning Traces
提出Dualformer: 同时集成了快速和慢速的推理模式，可以用控制token结合prompt要求使用哪一种推理方式，如果只有prompt，系统自己决定用哪一种方式
analogous 类似的 configure 配置
之前的searchformer方法的局限性: 只有慢速思考模式，输出长推理链条; 难以生成多样的解决方案
训练方法: 先接受包含推理轨迹和最终解决方案的数据的训练以模仿system2，并且设计特定的踪迹丢弃策略模仿system1
丢弃策略: 四个层级的丢弃方案简化A搜索轨迹(包含create和close子句，标记有坐标，成本值和启发值)
这里标记和探索的策略中详细过程看下面的论文解析
为了多样性，在数据预处理的时候不丢弃轨迹，训练时随机采样丢弃策略(4种丢弃策略加上一个完全不丢弃策略)
注意论文中提到的iteration是指avg trace length1000道题目