你负责一个“深度研究型”智能体：模型会递归地产生候选方案树，每个节点代表一个中间方案；系统有若干验证器（语法、单测、仿真、规则检查、成本估计），每个验证器有不同延迟、算力成本和噪声，且同一状态下不同验证器的结果可能相关。线上要求单请求 2 秒内返回，平均 GPU/CPU 验证预算不超过 B，并且最终答案要尽量满足所有硬约束。请你设计一个在线方法，决定：先扩展哪个候选、先跑哪些验证器、什么时候停止递归并输出；同时说明为什么不能直接用“纯 beam search”解决。 假设你只能看到历史验证结果和当前候选的局部特征，不能预先枚举完整搜索树。请给出你的建模方式、核心方法、复杂度分析、边界条件，以及如何处理验证器相关性、重复状态、预算很小时的退化策略。
我会把它建模成一个带预算的 anytime best-first search，而不是纯 beam search。每个状态 s 维护三类量：先验成功率 p0(s)、经过部分验证后的后验 p(s)、以及一个乐观上界 U(s)；每个验证器 a 看成一次“证据查询”，有代价 c(a)，会带来后验更新和信息增益 IG(s,a)。主循环用最大堆维护候选，优先扩展 U(s) 最高、或者单位代价收益最高的状态；状态内部则先跑“信息增益/成本”最高的低价验证器，把便宜但区分度强的检查放前面。若某状态的 U(s) 已经低于当前最好状态的下界 L(best)，就直接剪枝。 如果验证动作对约束集合是单调的、且边际收益递减，可以把“选择哪些验证器”视为预算约束下的子模最大化，用贪心做近似，通常有 1-1/e 级别保证；如果每个状态上的 verifier 数量较小，则可以对单状态做 0/1 背包 DP 精确选取。整体复杂度上，展开 N 个状态、每个状态考虑 V 个验证器时，主搜索约 O(N log N + Σ V_s log V_s)；若做精确预算分配，单状态最坏是 O(V·B)，总计约 O(N·V·B)。 工程上要做四件事：第一，把不同 verifier 的分数做统一校准，转成可比较的概率或 log-odds，否则不同模型输出不能直接相乘；第二，对中间状态做规范化哈希和缓存，避免重复子树重复验证；第三，用异步执行器、超时和回退策略保证 2 秒 SLA，昂贵验证器只在 shortlist 上运行；第四，如果 verifier 之间相关，不能简单假设独立相乘，要么学习一个小型后验融合器，要么用图模型/校准器来合并证据。最终输出时，如果有完全通过所有硬约束的候选，就返回后验最高者；如果没有，就返回下界最高且风险最低的候选，并明确标注未覆盖的约束。纯 beam search 的任务是它只保留局部分高的路径，不显式建模“验证成本—信息增益—剪枝收益”，很容易把预算浪费在看起来像样、但后续验证代价高且收益低的分支上。
强答应先把任务抽象成“带噪声证据查询的预算搜索/调度”而不是泛泛说 beam search；需要讲清楚状态、动作、收益、上界/下界、停止条件和剪枝依据。最好能说明：为何用 best-first 或 branch-and-bound，何时用子模贪心，何时用 DP，为什么要做概率校准，以及验证器相关性会破坏独立假设。常见错误包括：只讲搜索框架不讲预算；把 verifier 当成无噪声黑盒；没有复杂度和退化策略；忽略重复状态、缓存、超时和 SLA；只说“按分数排序”，却没有说明分数如何与证据融合。出练习者通常会追问：上界怎么构造才可剪枝；如果 verifier 的召回高但精度差，顺序怎么排；如果预算极小甚至无法完成一次完整验证，如何设计两阶段 shortlist；如果线上分布漂移导致校准失效，怎么监控和回滚。
- 你如何构造一个“可证明不误剪”的上界函数？
- 如果 verifier 输出彼此强相关，你会用什么后验融合方法？
- 预算只够验证 1-2 个候选时，你怎样设计两阶段筛选策略？