针对大模型引导搜索的偏差问题，提出自适应剪枝方法提升鲁棒性与效率。
PAC-MCTS: Bias-Aware Pruning for Robust LLM-Guided Search and Planning
- 将节点扩展建模为带偏差约束的局部最优臂识别问题
- 在有限计算预算下减少78%的API调用，样本效率提升3倍以上
- 适用于对推理稳定性要求高的自主规划与复杂环境探索任务
随着自主推理与具身规划中搜索深度增加，候选动作空间呈指数级扩张，常超出计算预算。尽管启发式剪枝是关键应对策略，但现有方法在依赖大语言模型等代理评估器时缺乏形式化安全保证，因这些模型存在系统性偏差。本文将节点扩展建模为受限偏差 $L$ 下的局部最优臂识别（BAI）问题，推导出样本复杂度上界 $/mathcal{O}((Δ-4L)^{-2})$，揭示 $Δ> 4L$ 为安全剔除可行区间。进一步建立信息论下界 $Ω((Δ-2L)^{-2})$，刻画有偏探索的结构性极限。基于此，提出PAC-MCTS框架，动态调整置信边界以应对偏差。在Blocksworld和ALFWorld上的实验表明，相比强基线，PAC-MCTS显著提升鲁棒性与搜索效率，在严格计算预算下最多减少78%的API调用，样本效率提升超3倍。消融实验验证了评估器偏差增大时性能退化的预测行为。
原文摘要 · Abstract (English)
As search depth increases in autonomous reasoning and embodied planning, candidate action spaces expand exponentially, often exhausting computational budgets. While heuristic pruning is a critical countermeasure, existing approaches lack formal safety guarantees when guided by surrogate evaluators such as Large Language Models (LLMs), which exhibit systematic biases. We formulate node expansion as a localized Best-Arm Identification (BAI) problem under bounded bias $L$ and derive a sample complexity upper bound of $\mathcal{O}((Δ-4L)^{-2})$, identifying $Δ> 4L$ as the regime where safe elimination is feasible. We further establish an information-theoretic lower bound of $Ω((Δ-2L)^{-2})$ that characterizes the structural limits of biased exploration. Motivated by these results, we propose PAC-MCTS, a bias-aware pruning framework that dynamically adapts confidence bounds during search. Experiments on Blocksworld and ALFWorld demonstrate that PAC-MCTS consistently improves robustness and search efficiency over strong pruning baselines, achieving up to 78\% fewer API evaluations and over 3$\times$ higher sample efficiency under strict compute budgets. Ablation studies further validate the predicted degradation behavior as evaluator bias increases.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。