G15：Test-Time Compute、搜索空间与停止条件
Test-time compute 是在参数冻结后，为当前任务分配的候选生成、搜索展开、验证、回溯与聚合预算；它只有在候选具有多样性、验证信号足够可靠且停止策略受控时，才可能转化为更高成功率。
内容类型：预习教材（不代表已完成）
日期：2027-03-08
阶段：P3 · AGI Foundations 90
总路线：Day 195 / 360
周次 / 节奏：W3 · 周一概念与论文
状态：教材已备；学习未完成
主题：sampling、search、verifier、difficulty 与 inference budget
一句话定义
Test-time compute 是在参数冻结后，为当前任务分配的候选生成、搜索展开、验证、回溯与聚合预算；它只有在候选具有多样性、验证信号足够可靠且停止策略受控时，才可能转化为更高成功率。
学习目标
- 能区分 greedy、sampling、best-of-N、self-consistency、tree search 与 adaptive compute。
- 能把推理任务表示为状态、动作、候选、验证分数和终止条件。
- 能解释 base success rate、task difficulty 与 verifier quality 如何共同决定预算收益。
- 能建立 accuracy–compute–latency 三维观察，不把“输出更长”自动等同于“有效计算更多”。
核心知识
Greedy 每步选择最高概率 token，成本低但容易早期锁定错误。Sampling 从分布抽样产生多样候选；best-of-N 生成 N 个完整候选，再由 verifier 选一个；self-consistency 把不同推理样本聚合到答案；tree search 在中间状态展开、评分、剪枝和回溯；adaptive compute 则根据难度或置信度动态分配预算。
这些策略使用的是不同信息。Sampling 只利用生成分布；best-of-N 需要候选级评价；tree search 需要中间状态可表示且可评分；adaptive controller 还要估计继续计算的边际价值。如果 verifier 很差，更多搜索会扩大“找到能骗过 verifier 的错误答案”的机会。
测试时预算可包含 generated tokens、model calls、expanded nodes、verifier calls、wall time 与 monetary cost。它们不能随意合并。长输出可能是重复或发散，不代表搜索空间被有效覆盖；短程序执行加确定性验证，反而可能提供更强计算。
机制与推导
若单个独立候选正确概率为 p，有完美 verifier 时，N 个候选至少一个正确的概率为：
[ P_{hit}(N)=1-(1-p)^N ]
收益递减，且独立假设通常不成立；候选高度相关时，有效样本数远小于 N。若 verifier 对正确候选召回为 r、对错误候选有假阳性率 f，最终选择质量还取决于候选数量和排序，不再由 P_hit 决定。
搜索问题可写为 (S,A,T,s_0,G,V)：状态、动作、转移、初始状态、目标测试与 verifier。树宽 b、深 d 时，穷举节点约 O(b^d)；预算有限必须用启发式排序、beam、剪枝或迭代加深。启发式如果与真实目标错位，剪枝会永久丢弃正确路径。
Adaptive compute 的简单规则是：估计难度 d(x) 与置信度 q，在 q<τ_low 且预算未耗尽时增加候选；在 verifier 已给出确定性通过或边际收益低于成本时停止。更正式地，可比较一步额外计算的期望价值 E[Δutility|state] 与成本 c。这只是控制框架，不要求在 G15 训练难度模型。
最小练习或观察步骤
- 选择一个可验证题，画出 greedy、best-of-N 和 tree search 的状态流，不调用真实大模型也可以。
- 取
p=0.1/0.3/0.6，计算 N 从 1 到 16 时理想P_hit，观察收益递减。 - 加入候选完全相关的反例：N 次都复制同一答案，比较理想公式为何失效。
- 定义预算账本：tokens、nodes、verifier calls、latency，并说明哪个是硬上限。
- 写两个停止条件：确定性成功与预算耗尽；再写一个“继续计算可能更坏”的条件。
常见误区与边界
- 把更多输出 token 当成更多有效推理，不检查重复和状态覆盖。
- 假设候选独立，用理想公式高估 best-of-N 收益。
- 只报告最高准确率，隐藏 N 倍时延和 verifier 成本。
- 把 verifier 分数当真值，不测 precision、recall 与可被利用性。
- 搜索策略与 direct baseline 使用不同模型或提示，却归因于搜索本身。
- 从某个数学题上的 test-time scaling 推到开放世界自主智能。
研究/系统场景连接
金融零售决策可把额外计算分配给高不确定、潜在损失高的案例：简单低风险交易快速通过，复杂异常模式触发更多规则、检索或人工复核。这里的 adaptive compute 同时是风险路由；但 verifier 若来自同一模型，不能视为独立控制。可执行法规规则或人工审批更接近外部验证信号。
Agent 系统中，搜索可能产生多个计划，工具模拟器验证参数和权限，再选择可执行路径。若工具有副作用，真实执行不能被当作随意 rollout；应使用本地 stub 或沙箱。W3 只研究可逆、确定性任务，不授予外部权限。
自检问题
- Best-of-N 与 tree search 使用的信息结构有何不同？
- 候选相关性为什么降低有效预算？
- Verifier 假阳性会如何随候选数放大？
- 什么条件下应该提前停止，而不是耗尽 token？
- 为什么 accuracy–compute–latency 必须并列？
专业课程对齐
- 阅读 Scaling LLM Test-Time Compute Optimally Can Be More Effective than Scaling Model Parameters，关注任务难度、策略选择与预算分配，而非只看标题结论。
- 阅读 Tree of Thoughts，把 thought state、proposal、evaluation 与 search algorithm 分开理解。
- 阅读 Let’s Verify Step by Step，比较 outcome 与 process supervision 如何改变 verifier 信号。
深入学习提示
学习顺序建议是先画算法状态，再看语言模型输出。若不能说明节点、边和评价函数，所谓“搜索”可能只是多次采样。进一步可研究 Monte Carlo Tree Search、value of computation 或 uncertainty routing，但先在确定性 toy task 上看清候选相关性与 verifier error。W3 的目标是理解何时额外计算有边际价值，不是追求最长推理轨迹。
学后填写区
- 我选择的可验证任务：
- 三种策略的状态流：
- 预算硬上限：
- Verifier 可能犯的错误：
- 一条停止条件：