用计算资源分配框架统一建模搜索策略，揭示信息与决策价值的深层关系。
Search as Computation Allocation
- 将搜索过程建模为资源分配问题，以终端决策损失为目标优化计算投入
- 证明在不同损失函数下，信息增益与计算价值的关系：对数损失下等价于互信息，简单后悔下对应知识梯度
- 推导出加权A*作为近似计算价值最大化的结果，涵盖A*和贪心搜索作为特例
许多算法在返回最终决策前会消耗内部资源，仅通过终端输出质量进行评估。本文将此类过程形式化为终端计算分配问题：高成本的计算产生观测，更新对隐含环境的信念，且仅通过终端决策损失来衡量价值。贝尔曼方程刻画了固定预算、定价计算和精确验证下的最优分配策略。我们进一步揭示计算价值（VOC）与信息的关系：在对数损失下，互信息等于瞬时计算价值；在简单后悔下，计算价值表现为知识梯度；尽管信息增益可能严重低估计算价值，但可提供上界。多臂赌博机抽取、树模拟与节点扩展展示了该模型在不同计算拓扑下的统一应用。最后，在显式前沿分辨与启发式误差模型下，最大化近似计算价值可恢复加权A*，而标准A*与贪婪最佳优先搜索为其极限情况。该理论识别了共通的决策问题，但不主张单一获取规则普遍最优。
原文摘要 · Abstract (English)
Many algorithms spend an internal resource before returning a decision and are evaluated only by the quality of that terminal output. We formalize such procedures as terminal computation-allocation problems: costly computations produce observations, update beliefs about a latent environment, and matter only through terminal decision loss. Bellman equations characterize optimal allocation under fixed budgets, priced computation, and exact certification. We then relate value of computation (VOC) to information. Mutual information equals myopic VOC under log loss, whereas under simple regret VOC is a knowledge-gradient quantity; moreover, information gain can rank computations arbitrarily poorly, although it gives a one-sided upper bound on VOC. Bandit pulls, tree simulations, and node expansions illustrate the same model under different computation topologies. Finally, under an explicit frontier-resolution and heuristic-error model, maximizing approximate VOC recovers weighted A*, with A* and greedy best-first search as limiting cases. The theory identifies a shared decision problem without asserting that one acquisition rule is universally optimal.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。